In the quest for optimal reinforcement learning (RL) algorithms, researchers rely on the alignment of upper and lower bounds for regret. Regret, defined as the difference between the total reward an optimal agent would receive and the reward a learning agent actually collects, serves as the primary metric for efficiency. This technical note by Ian Osband and Benjamin Van Roy serves as a critical "course correction" for the theoretical RL community, identifying a significant flaw in widely cited lower bounds and proposing a more optimistic path forward.
The Discrepancy in Regret Bounds
For over a decade, a discrepancy has persisted in the literature regarding the fundamental limits of RL performance. The UCRL2 algorithm (Jaksch et al., 2010) suggested a lower bound of $\Omega(\sqrt{DSAT})$, where $D$ is the diameter of the Markov Decision Process (MDP), $S$ is the number of states, $A$ is the number of actions, and $T$ is time. Conversely, the REGAL paper (Bartlett and Tewari, 2009) claimed a much more pessimistic lower bound of $\Omega(D \sqrt{SAT})$.
If the REGAL bound were correct, it would imply that current state-of-the-art algorithms are significantly sub-optimal, scaling poorly with the diameter of the environment. Osband and Van Roy set out to determine whether this linear scaling with $D$ is a physical reality or a mathematical artifact.
A Hard MDP Construction
To investigate these bounds, the authors utilize an information-theoretic approach, constructing a "hard" MDP designed to be difficult for any agent to learn. This construction focuses on a two-state system where transitions are governed by small perturbations, making it challenging to distinguish between optimal and sub-optimal policies.
As shown in the figure above, the MDP consists of two states ($R=0$ and $R=1$). The transitions are parameterized by $\delta$ and $\epsilon$, creating a scenario where an agent must spend significant time in the environment to accurately estimate the transition probabilities. By applying standard proof machinery—including KL divergence and Pinsker’s inequality—to this specific construction, the authors deconstruct the previous claims made in the REGAL paper.
The Double-Counting Fallacy
Through their analysis, Osband and Van Roy identify what they term a "double-counting" fallacy in the REGAL lower bound (specifically Theorem 6). The previous proof assumed that an agent incurs a large regret, proportional to the diameter $D$, at every single timestep it makes a mistake.
However, the authors argue that in a true MDP, a single bad decision might lead to a sequence of states where no further "new" regret is incurred beyond what was already accounted for by the initial error. Their technical argument demonstrates that standard information-theoretic techniques only support a $\sqrt{D}$ scaling in the lower bound, rather than a linear $D$ scaling. Specifically, they show that one can only prove a lower bound of $\Omega(\sqrt{D_{ow}SAT})$, where $D_{ow}$ is the one-way diameter—a significantly weaker bound than previously claimed.
Conclusion: A New Conjecture
The paper concludes that the lower bound established in the REGAL paper is likely invalid and should be treated as an unproven conjecture. In its place, the authors formally propose Conjecture 1: that the lower bounds suggested by Jaksch et al. (2010) are actually unimprovable.
This shift in perspective suggests that the RL community should stop trying to raise lower bounds to meet pessimistic upper bounds. Instead, future research should focus on refining algorithm analysis—perhaps by utilizing the Bellman equation for local variance—to lower the upper bounds of existing algorithms to match the more optimistic $\sqrt{D}$ scaling. This alignment would bring MDP regret analysis into closer harmony with recent PAC-RL findings in finite-horizon settings.