PAC reinforcement learning

PAC stands for probably approximately correct, a framework borrowed from supervised learning theory. The promise is modest on purpose: we do not demand the exactly optimal policy with certainty, only one that is approximately correct (within ε of optimal) with high probability (at least 1−δ). Those two knobs, ε and δ, make the guarantee falsifiable and let us count how much data buys it.

In RL, PAC guarantees usually bound the number of timesteps on which the agent acts more than ε-suboptimally — the count of "mistakes" — rather than wall-clock convergence. An algorithm is PAC-MDP if that count is polynomial in S, A, 1/(1−γ), 1/ε and log(1/δ). Classic results like R-MAX and delayed Q-learning are proved this way, by combining optimism with concentration bounds on estimated rewards and transitions.

PAC says nothing about which mistakes happen when, only that there are few in total. That makes it weaker than a regret bound in some respects and stronger in others; choosing the right notion depends on whether early errors are catastrophic or merely expensive.