When evaluating a reinforcement learning (RL) agent, we typically rely on two gold standards of theoretical performance: regret minimization and Probably Approximately Correct (PAC) bounds. Regret tracks the cumulative reward the agent misses out on while learning, aiming for a sublinear growth rate (like $O(\sqrt{T})$ or $O(\log T)$). PAC frameworks, on the other hand, guarantee that after a finite number of steps, the agent will output a "good enough" ($\epsilon$-optimal) policy with high probability.
For years, these metrics were treated as sufficient proxies for good behavior. However, a closer look reveals a troubling theoretical loophole known as the regret-convergence gap.
Consider an agent whose cumulative regret grows logarithmically, $O(\log T)$. This is widely celebrated as an optimal rate of growth. Yet, mathematically, $\log T$ approaches infinity as time $T$ goes to infinity. This means the agent can continue to make explicit, severe mistakes infinitely often throughout its lifespan, as long as the intervals between those mistakes grow exponentially longer (e.g., making a mistake at step 2, 4, 8, 16, and so on). The agent never truly settles into the optimal policy; it merely blunders less frequently.
To bridge this gap, recent research has shifted toward stronger, more stringent guarantees: Uniform-PAC bounds and Constant Regret. These frameworks ensure that an agent doesn't just improve on average, but actually converges to—and stays at—the optimal policy.
The Failure Modes of Standard Metrics
The core issue is that standard metrics do not guarantee policy convergence. As noted by Zhou et al. (2021), an agent can minimize regret while still deviating from optimal behavior indefinitely.
Standard PAC frameworks suffer from a reciprocal flaw. A traditional PAC guarantee requires you to choose a fixed accuracy target ($\epsilon$) before learning begins. The algorithm then bounds the number of episodes in which the agent's performance falls short of that specific threshold. However, this framework provides no insurance if you later decide you need a more precise policy, nor does it prevent the agent from settling into a slightly suboptimal strategy forever without ever reaching peak performance.
Furthermore, algorithmic stability does not imply optimality. As demonstrated by Lim et al. (2025) in the context of function approximation, an RL algorithm can be perfectly stable and gravitate toward a unique mathematical fixed point while still failing to capture the best possible behavior for the given task.
| Metric | What it guarantees | What it permits |
|---|---|---|
| Sublinear Regret | Total losses grow slower than time ($O(\sqrt{T})$) | Making severe mistakes infinitely often |
| Standard PAC | Limited mistakes for a fixed error threshold $\epsilon$ | Never finding the true optimal policy ($\epsilon \to 0$) |
| Uniform-PAC | Limited mistakes for any $\epsilon$ simultaneously | Temporary exploration errors bounded across all scales |
| Constant Regret | Total losses plateau at a fixed constant $C$ | Zero suboptimal decisions after a finite learning period |
Uniform-PAC: A Unified Framework
To resolve these conflicting limitations, Dann et al. (2017) introduced the Uniform-PAC framework. A Uniform-PAC guarantee unifies regret and PAC by requiring that for any target accuracy $\epsilon > 0$ chosen at any time, the number of steps where the agent's policy is $\epsilon$-suboptimal is bounded by a function that scales gracefully with $\epsilon$.
Crucially, this bound holds uniformly across the entire infinite horizon. By forcing the mistake bound to apply to all values of $\epsilon$ simultaneously, a Uniform-PAC guarantee ensures that as $\epsilon$ approaches zero, the agent's policy must asymptotically converge to the exact optimal policy. To prove this was achievable, the authors developed UBEV, an algorithm that leverages time-uniform confidence bounds to maintain tight, continuous estimates of environment transitions.
Scaling to Complex Environments
While early Uniform-PAC results were restricted to simple tabular environments, the framework has been extended to handle high-dimensional spaces using function approximation:
- Linear Environments: Chen et al. (2022) established the first uniform-PAC sample complexity bounds for infinite-horizon discounted linear kernel MDPs. They introduced a "discounted data inheritance" technique to carry over information across long horizons, ensuring the agent stops making persistent small errors.
- Nonlinear Environments: To handle complex, nonlinear dynamics, Wu et al. (2023) utilized the eluder dimension—a metric for the complexity of a function class. By employing a multi-level partitioning scheme, they proved that model-based RL can achieve Uniform-PAC guarantees even when approximating highly nonlinear reward and transition functions.
- Constrained Systems: In real-world deployments, agents must often respect safety or resource boundaries. Kozuno et al. (2024) designed a primal-dual policy gradient algorithm for constrained MDPs that provides Uniform-PAC guarantees alongside "last-iterate convergence," meaning the policy safely settles on the target behavior rather than oscillating. This builds on a broader foundation of making model-free algorithms reliable under strict, step-by-step peak constraints, as explored by Bai et al. (2023).
The Ultimate Goal: Constant Regret
If Uniform-PAC represents an agent that eventually stops making large mistakes, Constant Regret represents the ideal limit: an agent that stops making any suboptimal decisions after a finite period of time.
In a constant regret scenario, the cumulative regret curve flattens out entirely. The total regret is bounded by a fixed constant $C$, meaning that as $T \to \infty$, the agent acts with absolute perfection. As emphasized by Papini et al. (2021) and Zhang et al. (2024), breaking away from infinite-horizon regret growth requires exploiting specific structural properties of the environment.
1. Geometric Separation (The UNISOFT Condition)
How can an agent confidently stop exploring? Papini et al. (2021) identified a fundamental geometric condition in linear MDPs called UNISOFT (Universally Spanning Optimal FeaTures).
In a linear MDP, the transitions and rewards are determined by a feature mapping. If the features of the optimal actions span the entire underlying feature space, the agent can learn everything it needs to know about the environment's geometry solely by behaving optimally. Under this condition, an algorithm like LSVI-LEADER can shrink its uncertainty so rapidly that the exploration bonus for suboptimal actions drops below their suboptimality gap, causing the agent to permanently cease choosing them. Zhang et al. (2023) expanded this idea to representation selection with their ReLEX framework, showing that agents can achieve constant regret by adaptively selecting representations from a candidate pool that minimize uncertainty for optimal state-action pairs.
2. Environment Determinism
Standard RL algorithms often suffer from a regret growth rate proportional to $\sqrt{T}$ because they must continuously sample transitions to average out environmental noise. However, if an environment is perfectly deterministic, this ongoing exploration is wasteful.
Zhou et al. (2023) designed variance-dependent algorithms that automatically adapt to the randomness of the world. In highly stochastic environments, they maintain minimax-optimal regret, but in zero-variance (deterministic) settings, their model-based and model-free approaches collapse to a constant regret plateau, eliminating the dependency on the total number of episodes.
The Computational Feasibility of Long-Term Optimality
Demanding that an agent converge to a flawless policy over an infinite horizon sounds computationally daunting. If the agent must plan for the infinite future without making mistakes, does the optimization problem become intractable?
Theoretical foundations suggest otherwise. Early work in the field, such as Polynomial-Time Reinforcement Learning of Near-Optimal Policies, demonstrated that computing near-optimal policies for known MDPs can be completed in polynomial time by leveraging spectral radius bounds and mixing times. Similarly, Chatterjee et al. (2008) showed that optimizing infinite-horizon objectives based on the limit superior (limsup) or limit inferior (liminf) of rewards remains computationally efficient and sits within the complexity class $\text{NP} \cap \text{coNP}$.
More recently, Grand-Clément et al. (2023) tackled the challenge of computing Blackwell optimal policies—policies that remain optimal for all discount factors sufficiently close to 1. By introducing the Blackwell discount factor via tools from algebraic number theory, the authors proved that long-term average and Blackwell optimality can be reduced to standard discounted MDPs. This reduction operates in weakly-polynomial time without requiring restrictive structural assumptions like ergodicity or unichain transitions.
Ultimately, these computational guarantees complement the statistical power of Uniform-PAC and constant regret. They prove that designing agents capable of eliminating mistakes entirely over the long run is not only statistically necessary to bridge the regret-convergence gap, but also computationally practical.
Key Foundational Work
Efficient Reinforcement Learning (1994) — contributed 3 concept elements to this direction.
Polynomial-Time Reinforcement Learning of Near-Optimal Policies (2002) — contributed 1 concept elements to this direction.