Abstract: Statistical performance bounds for reinforcement learning (RL) algorithms can be critical for high-stakes applications like healthcare. This paper introduces a new framework for theoretically measuring the performance of such algorithms called Uniform-PAC, which is a strengthening of the classical Probably Approximately Correct (PAC) framework. In contrast to the PAC framework, the uniform version may be used to derive high probability regret guarantees and so forms a bridge between the two setups that has been missing in the literature. We demonstrate the benefits of the new framework for finite-state episodic MDPs with a new algorithm that is Uniform-PAC and simultaneously achieves optimal regret and PAC guarantees except for a factor of the horizon.
Introduction
In Reinforcement Learning (RL) theory, performance is typically measured using two distinct frameworks: Probably Approximately Correct (PAC) and Regret. PAC researchers focus on sample complexity—the number of episodes required before an algorithm consistently selects a near-optimal policy. Conversely, Regret researchers focus on the cumulative reward lost over time compared to an optimal agent.
While these metrics are related, they possess different properties that make them difficult to reconcile. A low-regret algorithm might still make catastrophic mistakes infinitely often (albeit with decreasing frequency), while a PAC algorithm might stop learning once it reaches a specific performance threshold. This paper proposes a way to bridge this divide with a new framework called Uniform-PAC.
The Uniform-PAC Framework
The core issue with existing guarantees is their "one-sided" nature. Regret bounds allow for occasional maximal suboptimality, which is unacceptable in sensitive domains like healthcare. Traditional PAC bounds only hold for a fixed accuracy level ($\epsilon$) and do not guarantee eventual convergence to the optimal policy.
As shown in Figure 1, Uniform-PAC acts as a missing link. An algorithm is Uniform-PAC if, with high probability, it selects an $\epsilon$-optimal policy for all $\epsilon > 0$ simultaneously, with a sample complexity that scales polynomially with $1/\epsilon$. This framework ensures both rapid learning and eventual optimality, providing a "gold standard" for RL theory.
The UBEV Algorithm
To achieve these guarantees, the authors introduce UBEV (Upper Bounding the Expected Next State Value), an optimistic algorithm for episodic Markov Decision Processes (MDPs). UBEV incorporates two key innovations:
- Law of Iterated Logarithm (LIL) Bounds: Instead of standard confidence intervals, UBEV uses LIL-based bounds that hold uniformly over time. This allows the algorithm to be valid at every step without prior knowledge of the total time horizon.
- Direct Value Concentration: Rather than learning transition dynamics first, UBEV incorporates the value function directly into its concentration analysis. This mathematical shortcut improves sample complexity by a factor of the number of states ($S$).
Empirical Evaluation
The authors evaluated UBEV against established algorithms—including UCRL2, MBIE, and MoRMax—using synthetic MDPs with varying state spaces ($S=5, 50, 200$).
As illustrated in Figure 5, UBEV demonstrates significant empirical superiority, learning faster than other frequentist algorithms across all tested environments. The use of LIL bounds provides much tighter confidence intervals than the conservative union bounds used by older methods, leading to faster convergence to the optimal policy.
Conclusion
UBEV is the first algorithm proven to achieve near-optimal performance in both PAC and regret metrics simultaneously. While the current analysis is limited to tabular RL and has a sub-optimal dependence on the episode horizon ($H$), it establishes a rigorous foundation for future work. The major remaining challenge is extending these Uniform-PAC guarantees to large-scale RL using function approximation, where tabular representations are no longer feasible.
Summary updated