In reinforcement learning (RL), we typically measure success through two lenses: Regret (how much reward did we lose while learning?) and PAC complexity (how many samples do we need to find a "good enough" policy?). While these metrics are standard, they share a subtle, often overlooked flaw: they do not guarantee that an agent will ever actually settle on the optimal strategy.
Recent research is shifting focus toward a more rigorous standard—Uniform-PAC guarantees and Asymptotic Convergence—to ensure that agents don't just perform well on average, but eventually become "truth-finders" that identify and stick to the best possible behavior.
The Regret Trap: Being Mostly Right Forever
To understand why standard metrics fail, consider an agent minimizing cumulative regret. A sublinear regret bound means that as time goes on, the frequency of mistakes decreases. However, as noted by Ayfer Ozgur and Cem Kalkanlı in Asymptotic Convergence of Thompson Sampling, this doesn't prevent the agent from making suboptimal choices infinitely often.
Imagine an agent that chooses a bad action once every million steps, then once every billion steps, and so on. Its total regret grows so slowly that it technically "minimizes" it, yet it never truly learns to stop making that mistake. Yuanzhou Chen, Jiafan He, and Quanquan Gu argue in On the Sample Complexity of Learning Infinite-horizon Discounted Linear Kernel MDPs that in infinite-horizon settings, this persistent error is a major theoretical gap. Sublinear regret allows for "infinite mistakes" as long as they are rare.
The PAC Limitation: Snapshots vs. Stability
Probably Approximately Correct (PAC) guarantees offer a different perspective: they bound the number of steps where an agent's policy is not $\epsilon$-optimal. But as Dongruo Zhou and colleagues point out in Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation, a standard PAC guarantee is a "one-time" promise. It ensures you find a good policy once, but it doesn't stop the agent from deviating back into suboptimality later during its exploration.
The solution is the Uniform-PAC bound. Unlike standard PAC, a Uniform-PAC bound provides a global guarantee: it bounds the total number of steps across the entire infinite timeline where the agent's policy is significantly suboptimal. This forces the agent to eventually converge to the optimal policy and stay there.
Convergence of Math vs. Convergence of Quality
A common misconception is that if an algorithm's values (like Q-values) converge to a fixed point, the resulting policy must be optimal. Han-Dong Lim and Donghwan Lee 0002 clarify this distinction in Understanding the theoretical properties of projected Bellman equation, linear Q-learning, and approximate value iteration.
They demonstrate that an algorithm can be mathematically stable—gravitating toward a unique, predictable fixed point—while that fixed point itself represents a mediocre or even poor strategy. This is especially prevalent when using function approximation (like linear models or neural networks), where the "best" the model can represent might still be far from the true optimal.
The Cost of Certainty
Achieving these stronger guarantees isn't free. Yuanzhou Chen and Jiafan He identify a performance trade-off: algorithms designed for Uniform-PAC guarantees often exhibit higher cumulative regret than those optimized purely for regret.
This happens because ensuring eventual optimality requires a more persistent and structured form of exploration. To be 100% certain of the "truth," as Ayfer Ozgur describes it, the agent must spend more time verifying its knowledge, leading to a higher "up-front" cost in exchange for the guarantee of never making a mistake again in the limit.