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
Deploying reinforcement learning (RL) in high-stakes domains, such as healthcare or industrial control, necessitates rigorous theoretical guarantees to prevent catastrophic failures. Historically, the RL community has relied on two primary frameworks to quantify performance: Probably Approximately Correct (PAC) and Regret.
PAC guarantees that an algorithm will make only a finite number of mistakes relative to a pre-defined accuracy level $\epsilon$. However, PAC algorithms often cease learning once this threshold is reached, potentially remaining suboptimal indefinitely. Conversely, Regret bounds the cumulative error over time. While useful, a low regret bound does not distinguish between a few large errors and many small ones, and an algorithm with optimal regret might still make an infinite number of mistakes over an infinite horizon.
This paper identifies a fundamental gap: neither framework ensures that an algorithm will converge to the true optimal policy with high probability. To address this, the authors propose "Uniform-PAC," a stronger framework that bridges these two disparate approaches.
The Uniform-PAC Framework
The authors introduce Uniform-PAC as a more robust performance metric. An algorithm is considered Uniform-PAC if, with high probability, it selects an $\epsilon$-optimal policy for all episodes except for a polynomial number of times, and this holds simultaneously for all $\epsilon > 0$.
This framework serves as the "missing bridge" in RL theory. A Uniform-PAC guarantee can be mathematically converted into both standard PAC bounds and high-probability regret bounds without sacrificing optimality. Crucially, the authors prove that PAC and Regret can be mutually exclusive; in certain scenarios, achieving sub-linear expected regret actually precludes achieving a finite PAC bound. This occurs because minimizing expected regret over an infinite horizon may require the algorithm to pull suboptimal arms indefinitely to confirm their suboptimality.
The UBEV Algorithm
To demonstrate the achievability of Uniform-PAC, the authors present UBEV (Upper Bounding the Expected Next State Value), an optimistic planning algorithm for episodic Markov Decision Processes (MDPs).
The core innovation of UBEV lies in its use of finite-time law of the iterated logarithm (LIL) confidence bounds. Traditional RL algorithms typically employ Hoeffding-style confidence intervals that shrink at a rate of $\sqrt{\log(T)/n}$, where $T$ is the total number of episodes. Since $T$ increases indefinitely, these algorithms are often forced into excessive exploration. In contrast, UBEV utilizes LIL bounds that shrink at a much tighter rate of $\sqrt{(\log \log n)/n}$. This statistical refinement allows UBEV to update its policy after every episode and exploit high-performing policies much faster by avoiding the trap of infinite exploration.
Experimental Evaluation
The authors evaluated UBEV using synthetic, randomly generated episodic MDPs with varying state spaces ($S \in \{5, 50, 200\}$), 3 actions, and a time horizon of $H=10$. Transition probabilities were sampled from a Dirichlet distribution, and rewards were sparse and deterministic.
Theoretically, UBEV achieves a Uniform-PAC bound of $\tilde{O}(S^2AH^4/\epsilon^2)$ and a high-probability regret bound of $\tilde{O}(H^2\sqrt{SAT})$. These bounds are near-optimal, matching known lower bounds for state ($S$), action ($A$), and time ($T$) complexity, with only minor overhead in the horizon ($H$).
Empirically, UBEV significantly outperforms existing optimism-based algorithms such as UCRL2, MBIE, and UCBVI. As shown in the performance plots, UBEV (represented by the solid red line) converges toward the optimal return much more rapidly than its competitors across all tested state space sizes. The tighter LIL confidence bounds enable the algorithm to identify and prune suboptimal paths early in the learning process.
Discussion and Future Work
While UBEV provides a powerful theoretical and practical advancement, its current formulation is limited to tabular, finite-state episodic MDPs. Extending the Uniform-PAC framework to infinite-horizon settings and environments requiring function approximation (such as Deep RL) remains a significant challenge. Nevertheless, the introduction of Uniform-PAC and the application of LIL bounds represent a major step toward more reliable and efficient reinforcement learning systems.
Summary updated