Gap Dependent Regret Bounds in Reinforcement Learning

48 concepts28 papers2 proposals

When evaluating reinforcement learning (RL) and bandit algorithms, theorists often rely on worst-case (minimax) regret bounds. These bounds typically scale as $O(\sqrt{T})$, where $T$ is the number of time steps or episodes. This square-root growth implies that an agent must keep making mistakes at a steady, albeit slowing, rate forever.

But in practice, we often observe that good algorithms converge to the optimal policy much faster than $O(\sqrt{T})$ would suggest. Why is there a gap between theory and reality?

The answer lies in the structure of the environment itself. Worst-case analysis assumes a malicious environment where a suboptimal action might be nearly indistinguishable from the optimal one. However, real-world tasks often feature a distinct sub-optimality gap ($\Delta$)—a clear margin separating the value of the best choice from the second-best choice. When such a gap exists, an agent can quickly identify and permanently avoid inferior actions, causing cumulative regret to shift from a polynomial $\sqrt{T}$ growth rate to a much slower logarithmic $\log T$ growth rate.


The Intuition: When Confidence Intervals Clear the Gap

To understand why a sub-optimality gap fundamentally changes the learning rate, consider a simple multi-armed bandit problem with two arms. Arm A yields an expected reward of $1.0$, and Arm B yields $0.8$. The sub-optimality gap here is $\Delta = 0.2$.

When the agent first begins interacting with the environment, its estimates of the rewards are highly uncertain. We can visualize this uncertainty as a confidence interval around each arm's estimated value. The width of these confidence intervals shrinks at a rate of $O(1/\sqrt{n})$, where $n$ is the number of times that specific arm has been pulled.

Early Stage: High Uncertainty (Regret grows as √T)
Arm A (Optimal):    [--------|--------]  (True value: 1.0)
Arm B (Suboptimal):     [--------|--------]  (True value: 0.8)
                         ^ Overlap means the agent can easily mistake B for A.

Later Stage: Uncertainty drops below the Gap (Regret grows as log T)
Arm A (Optimal):      [--|--]
Arm B (Suboptimal): [--|--]
                       ^ No overlap. The agent confidently avoids Arm B.

In the early stages, the confidence intervals overlap significantly. The agent cannot tell whether Arm B is truly worse or if it has just been unlucky. To protect against the possibility that Arm B might actually be the optimal choice, the agent must continue to explore it.

However, once the agent has pulled Arm B enough times for its confidence interval to shrink smaller than the gap itself ($O(1/\sqrt{n}) < \Delta$), the overlap vanishes. At this point, an optimistic algorithm can see with high statistical confidence that Arm B is inferior. The agent will rarely ever pull Arm B again, doing so only occasionally to ensure that its environment hasn't changed.

Mathematically, the number of samples required to reach this threshold scales as $O(1/\Delta^2)$. Beyond this point, the expected number of mistakes scales only as $(\log T)/\Delta^2$. If the gap $\Delta$ is a fixed, positive constant, the polynomial exploration phase is short, and the long-term regret is dominated by this logarithmic growth.


From Bandits to Markov Decision Processes

This gap-dependent behavior was first thoroughly explored in simpler settings like contextual bandits. For instance, John Langford et al. demonstrated in The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information that organizing exploration into growing epochs allows agents to achieve logarithmic regret when clear performance margins exist between choices.

In full Reinforcement Learning, the problem becomes significantly more complex because actions do not just yield immediate rewards; they also dictate state transitions. Amir-massoud Farahmand formalized this dynamic as the action-gap phenomenon in Action-Gap Phenomenon in Reinforcement Learning. The author proved that an agent's policy performance can converge to the optimum exponentially faster than its internal value function estimates. Even if the agent has a noisy, inaccurate estimate of the state-value function, it will still make the correct decision as long as the estimation error is smaller than the action gap.

For tabular Markov Decision Processes (MDPs), Max Simchowitz et al. showed in Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs that standard optimistic exploration algorithms naturally inherit these instance-dependent logarithmic bounds. This confirmed that algorithms do not need to be redesigned to exploit "easy" environments; their existing optimism automatically adapts to the local geometry of the reward function.

Similarly, Kunhe Yang et al. established in Q-learning with Logarithmic Regret that simple, model-free Q-learning achieves logarithmic cumulative regret by leveraging these sub-optimality gaps, matching the theoretical efficiency of more complex, memory-intensive model-based methods.


Scaling to High Dimensions with Function Approximation

While tabular MDPs isolate the core mechanism of gap-dependence, real-world RL requires function approximation to handle massive or continuous state spaces. Function approximation introduces a major challenge: states are no longer independent. An error in estimating the value of a suboptimal action in State $X$ can generalize and corrupt the value estimate of an optimal action in State $Y$, potentially blurring the sub-optimality gap.

To resolve this, Dongruo Zhou et al. provided the first instance-dependent analysis for linear models in Logarithmic Regret for Reinforcement Learning with Linear Function Approximation. They proved that if a strictly positive minimum sub-optimality gap exists across the state space, an agent using linear function approximation can successfully transition from square-root to logarithmic regret.

This line of work has expanded rapidly across several dimensions:


From Global Gaps to Fine-Grained Analysis

Early gap-dependent theory suffered from a significant limitation: it relied on the global minimum gap ($\Delta_{\min}$). If an environment had a clear separation between actions everywhere except for one obscure, rarely visited state where two actions were nearly identical, $\Delta_{\min}$ would approach zero. The theoretical bound would blow up, reverting to a pessimistic worst-case rate even though $99\%$ of the environment was easy to solve.

To bridge this gap between theory and practical performance, recent research has shifted toward more localized, fine-grained definitions of environment difficulty.

Instead of looking at local value-function differences, Christoph Dann et al. introduced the concept of the "return gap" in Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning. This framework scales the regret bound based on the reachability of states under optimal or near-optimal policies, ensuring that hard-to-distinguish actions in unvisitable states do not penalize the agent's overall performance guarantees.

Taking localization a step further, Haochen Zhang et al. developed an analytical framework in Q-Learning with Fine-Grained Gap-Dependent Regret that bounds exploration using individual action suboptimality gaps rather than a single global bottleneck.

Coarse Global Analysis (Pessimistic)
Regret ∝ 1 / Δ_min  (Driven by the single hardest state in the entire MDP)

Fine-Grained Analysis (Realistic)
Regret ∝ ∑ (1 / Δ_s,a) (Each state-action pair is bounded by its own local clarity)

By analyzing optimal and suboptimal actions separately in their proofs, the authors prevented the high-frequency visitation noise of optimal actions from drowning out the signal needed to isolate suboptimal choices. This allows the agent to exploit local environment structures, freezing exploration in clear-cut states while continuing to carefully evaluate states with narrower margins.


Generalization Beyond Standard Online RL

The intuition that sub-optimality gaps accelerate learning has proven to be a unifying principle across several distinct branches of optimization and decision-making:

Offline Reinforcement Learning

In offline RL, the agent cannot interact with the environment and must learn strictly from a pre-collected dataset. Thanh Nguyen-Tang et al. established the first instance-dependent bounds for offline RL with linear function approximation in On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation. They showed that when the offline data distribution covers an environment with a distinct action gap, pessimistic offline algorithms can identify the optimal policy significantly faster than standard minimax rates predict.

Risk-Sensitive Reinforcement Learning

When agents are optimized for safety or stability using non-linear risk measures (like exponential utility), worst-case bounds are notoriously pessimistic. However, Yingjie Fei et al. introduced the concept of "cascaded gaps" in Cascaded Gaps: Towards Logarithmic Regret for Risk-Sensitive Reinforcement Learning, proving that risk-sensitive agents also unlock logarithmic regret growth when optimal risk-adjusted paths are well-separated from suboptimal alternatives.

Multi-Agent Games

In multi-agent settings, the moving-target problem makes convergence difficult to guarantee. Yet, Shinji Ito et al. extended gap-dependent analysis to multi-agent systems in Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback, proving that two-player zero-sum games achieve fast logarithmic convergence under bandit feedback when a clear gap separates the Nash equilibrium strategies from suboptimal moves.

Inverse Optimization

Even in preference learning, the gap phenomenon holds true. Shinsaku Sakaue et al. demonstrated in Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel-Young Loss Perspective and Gap-Dependent Regret Analysis that if an observed agent's decision space contains a distinct gap, a learner trying to infer that agent's internal reward function can achieve a constant cumulative error. In this scenario, the learner effectively stops accumulating regret entirely after a finite number of observations.

Summary

Worst-case bounds are vital for safety-critical guarantees, but they obscure why reinforcement learning algorithms perform so well in practice. By shifting the analytical lens from worst-case environments to instance-dependent structures, gap-dependent analysis proves that clarity breeds efficiency. When the optimal path is clearly separated from the alternatives, statistical uncertainty quickly drops below the threshold of ambiguity, allowing agents to stop exploring mistakes and start exploiting optimal behavior.

Key Foundational Work

The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information (2007) — contributed 1 concept elements to this direction.
Action-Gap Phenomenon in Reinforcement Learning (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_gap_dependent_regret_bounds_399bd812,
  title = {gap-dependent regret bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/gap-dependent-regret-bounds/rdr_399bd812c58743c1a3429726fd3298bf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_gap_dependent_regret_bounds_399bd812_v1,
  title = {gap-dependent regret bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/gap-dependent-regret-bounds/rdr_399bd812c58743c1a3429726fd3298bf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake