In reinforcement learning (RL), an agent's performance is often measured by its regret—the difference between the total reward an optimal agent would collect and the reward the learning agent actually accumulates. For tabular Markov Decision Processes (MDPs) with $S$ states, $A$ actions, and a horizon $H$, information theory dictates a fundamental lower bound on minimax regret: any algorithm must incur at least $\Omega(\sqrt{SAHT})$ regret over $T$ steps.
However, a persistent gap long remained between theory and practice. The upper bounds of standard exploration algorithms frequently scaled with an extra factor of $\sqrt{S}$, yielding regret bounds like $\widetilde{O}(S\sqrt{AHT})$ or $\widetilde{O}(\sqrt{S^2 AHT})$. This discrepancy meant that in environments with massive state spaces, theoretical guarantees suggested algorithms would perform significantly worse than what the fundamental limits of the problem required. Closing this "state-space regret gap" has been a major focus of modern RL theory.
The Root of the Gap: Transition Estimation vs. Value Estimation
Why did early algorithms suffer from this sub-optimal $\sqrt{S}$ scaling? The issue stems from how uncertainty is quantified.
Consider a model-based algorithm that tries to learn the transition probability matrix $P(s'|s,a)$. If the algorithm constructs confidence intervals for $P$ at every single state-action pair independently, it must account for the fact that there are $S$ possible next states. Under standard Hoeffding-style concentration inequalities, the error in estimating the transition vector scales with $\sqrt{S}$. When these errors are propagated through the Bellman optimality equations over the horizon $H$, the $\sqrt{S}$ penalty directly infects the final regret bound. As noted by Leon et al., this square-root dependency heavily limits the theoretical efficiency of traditional model-based frameworks in environments with vast state spaces.
Direct Value Concentration and Bernstein Inequalities
To bypass this penalty, researchers realized they did not need to learn the full transition dynamics perfectly; they only needed to estimate the value of the next states accurately.
In a breakthrough work, Azar et al. introduced the UCBVI algorithm. Instead of placing confidence bounds on the transition probabilities $P$, the authors applied tighter concentration inequalities—specifically empirical Bernstein inequalities—directly to the optimal value function $V^*$.
Why does this work? A Hoeffding bound considers only the worst-case range of a random variable. A Bernstein bound, however, scales with the variance of the random variable. In an MDP, the variance of the next-state value function satisfies a crucial law of total variance: when summed over an entire episode trajectory, the total variance is bounded by $H^2$, rather than $H^2 \times S$. By leveraging this algebraic property, Azar et al. showed that the errors do not accumulate independently across all $S$ states, successfully matching the minimax lower bound and eliminating the extra $\sqrt{S}$ factor.
Evaluating the Optimal Bias Function
Another intuitive way to eliminate the state-space gap is to shift focus from transition models to the relative differences between states. In infinite-horizon average-reward settings, the absolute value of a state matters less than its bias—how much better or worse it is to start in state $A$ versus state $B$.
Zhang et al. leveraged this insight in their EBF (Estimate the Bias Function) algorithm. Traditional methods suffer from the $\sqrt{S}$ gap because they evaluate transition models globally. By focusing directly on the state-pair differences of the optimal bias function, the authors avoided the need to resolve the entire transition matrix. This targeted estimation allowed them to improve previous theoretical bounds by a factor of $\sqrt{S}$, aligning the upper bound with the known mathematical lower limits of learning efficiency.
Closing the Gap Across RL Paradigms
The effort to eliminate the $\sqrt{S}$ scaling gap has forced advancements across multiple algorithmic families beyond value iteration:
- Posterior Sampling: Model-based Bayesian methods like Thompson Sampling also suffered from sub-optimal state scaling. Agrawal et al. resolved this by introducing an optimistic posterior sampling method. By taking multiple samples from a boosted Dirichlet posterior to construct an extended MDP, the authors matched the theoretical lower bound for large time horizons, removing the $\sqrt{S}$ sub-optimality.
- Policy Optimization: Model-free policy-gradient methods traditionally lagged behind value-based methods in sample efficiency, often exhibiting a performance gap proportional to $\sqrt{S}$. Wu et al. closed this gap with RPO-SAT. By introducing a "Stable at Any Time" (SAT) property and a novel reference-based value estimator, the authors proved that policy optimization can achieve minimax optimal regret, demonstrating that model-free policy methods do not inherently need to pay a state-space penalty.
Open Frontiers in State-Space Scaling
While the gap has been successfully closed for standard episodic tabular MDPs, achieving optimal state-space scaling remains an active challenge in more complex settings:
- Non-Episodic and Single-Stream RL: In infinite-horizon, non-episodic scenarios where an agent learns from a continuous stream of experience without resets, Talebi et al. point out that a $\sqrt{S}$ gap still persists between upper and lower bounds. Eliminating this factor without the luxury of episodic resets remains an open problem.
- Adversarial and Scale-Free Environments: When rewards or transitions are adversarial, or when reward scales are unknown, the state-space dependency often degrades. For instance, Chen notes that scale-free RL frameworks currently exhibit a regret bound scaling at a rate of $S^{1.5}$, leaving a clear gap compared to the linear $S$ dependency achieved by scale-aware algorithms. Similarly, Zhao et al. highlight that adversarial linear mixture MDPs still face significant gaps between upper bounds and lower bounds regarding state space size and episode length.
Key Foundational Work
Minimax Regret Bounds for Reinforcement Learning (2017) — contributed 1 concept elements to this direction.
Optimistic posterior sampling for reinforcement learning: worst-case regret bounds (2017) — contributed 1 concept elements to this direction.
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2017) — contributed 1 concept elements to this direction.