In reinforcement learning (RL) theory, "regret" measures the difference between what an agent actually earned and what an optimal agent could have earned. For years, a persistent tension has existed between upper bounds (the performance we can prove an algorithm achieves) and lower bounds (the mathematical limit of how well any algorithm can possibly perform).
When these two bounds do not meet, it signals a gap in our understanding. It suggests either that our algorithms are inefficient or that our mathematical proofs are not yet sharp enough to capture the true difficulty of the problem. A major thrust of current research is dedicated to closing these gaps across increasingly complex settings, from non-stationary environments to multi-agent games.
The Policy Optimization Disconnect
Policy optimization (PO) methods like PPO and TRPO are the workhorses of modern deep RL, yet they have historically lagged behind value-based methods in theoretical guarantees. In the tabular setting, value-based algorithms reached "minimax optimality"—where the upper and lower bounds match—long ago. Policy-based methods, however, often suffered from sub-optimal bounds that scaled poorly with the state space.
Tianhao Wu and colleagues addressed this in Nearly Optimal Policy Optimization with Stable at Any Time Guarantee. They identified that standard KL-divergence regularization was part of the problem. By switching to $\ell_2$ regularization and a novel "Reference V estimator," they proved that policy-based methods could finally match the sample efficiency of value-based counterparts. Similarly, Han Zhong and Tong Zhang analyzed an optimistic version of PPO in A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes, pushing the regret from $K^{3/4}$ toward the optimal $K^{1/2}$ rate in linear environments.
Navigating Non-Stationary and Adversarial Worlds
Most classical RL theory assumes a "stationary" world where the rules of physics and rewards never change. In reality, environments drift. This introduces a "dynamic regret" challenge: how do you compete with an optimal strategy that is itself a moving target?
A significant gap has existed between the $K^{3/4}$ regret achieved by early non-stationary algorithms and the $K^{2/3}$ lower bound known from simpler bandit problems. Ahmed Touati and Pascal Vincent attacked this in Efficient Learning in Non-Stationary Linear Markov Decision Processes using a "smooth forgetting" mechanism.
Furthermore, Weichao Mao and Kaiqing Zhang have focused on the "episode length" ($H$) parameter. In Is Model-Free Learning Nearly Optimal for Non-Stationary RL?, they showed that model-free methods could be computationally efficient while nearing the information-theoretic limits, though a small discrepancy in how the bounds scale with $H$ remains a target for future refinement.
From Single Agents to Structured Games
When multiple agents interact, the "environment" includes the strategies of other players, making the learning problem non-stationary by definition. In zero-sum Markov games, the goal is often to reach a Nash Equilibrium.
Researchers like Jieping Ye and Zhuoran Yang have worked to bridge the gap between the empirical success of decentralized policy optimization and its theoretical foundations. In Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions, they achieved the optimal $\sqrt{T}$ regret bound by exploiting specific transition structures, such as factored models. This is a major step forward, as previous multi-agent methods often converged at much slower, sub-optimal rates.
Refining the Fundamental Limits
Why do these gaps exist in the first place? In their influential technical note, On Lower Bounds for Regret in Reinforcement Learning, Ian Osband and Benjamin Van Roy argued that many upper bounds are "loose" because they don't account for the local variance of the Bellman equation.
Closing these gaps requires two simultaneous efforts:
- Algorithmic Innovation: Developing mechanisms like "Restart" strategies for non-stationarity or "Pessimism" for offline data (as seen in Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism by Paria Rashidinejad).
- Analytical Sharpening: Using more sophisticated tools to prove tighter lower bounds that reflect the true difficulty of specific environment structures, such as the "dynamics constraints" introduced by Andrea Tirinzoni in A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs.
The ultimate goal of this research direction is a "tight" theory of RL: a state where for any given problem—whether it involves delayed feedback, multi-objective trade-offs, or unknown transitions—we have an algorithm that performs exactly as well as the laws of information theory allow.