Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs

Max Simchowitz, Kevin G. Jamieson

Abstract

This paper establishes that optimistic algorithms attain gap-dependent and non-asymptotic logarithmic regret for episodic MDPs. In contrast to prior work, our bounds do not suffer a dependence on diameter-like quantities or ergodicity, and smoothly interpolate between the gap dependent logarithmic-regret, and the $\widetilde{\mathcal{O}}(\sqrt{HSAT})$-minimax rate. The key technique in our analysis is a novel "clipped" regret decomposition which applies to a broad family of recent optimistic algorithms for episodic MDPs.

Introduction

In Reinforcement Learning (RL), the performance of a learning agent is typically quantified by regret: the cumulative difference between the rewards an optimal policy would have collected and those actually earned by the agent. Historically, theoretical analysis of regret has been divided into two distinct paradigms.

Minimax analysis focuses on the worst-case scenario, providing robust bounds that typically scale with $\sqrt{T}$ (where $T$ is the total time). While reliable, these bounds are often overly pessimistic for "easy" environments where the optimal action is significantly better than the alternatives. Conversely, gap-dependent analysis focuses on specific instances where a "gap" exists between the best and second-best actions. These analyses yield logarithmic regret ($\log T$), which is significantly more efficient as $T$ grows.

However, existing gap-dependent results have historically been limited by two major caveats: they were either purely asymptotic (valid only as $T \to \infty$) or they relied on restrictive assumptions like ergodicity or small "diameter-like" quantities (the ease of traveling between any two states). This paper bridges this gap, providing finite-time logarithmic regret without requiring the environment to be globally connected.

The "Clipped" Regret Decomposition

The primary contribution of this work is a novel analytical framework called the "Clipped" Regret Decomposition. The authors apply this technique to StrongEuler, a model-based optimistic algorithm that utilizes Bernstein-style confidence bonuses to maintain an optimistic estimate of the environment's value function.

In standard RL analysis, researchers typically bound the "surplus"—the error in the agent's value estimate. The innovation here lies in "clipping" these surpluses to zero whenever they are significantly smaller than the sub-optimality gaps of the actions. By ignoring these negligible errors, the analysis prevents the regret bound from being inflated by difficult-to-reach states or complex global connectivity issues. This localization allows the authors to prove that the agent stops selecting sub-optimal actions at a logarithmic rate, regardless of the MDP's global diameter.

Key Insights and Theoretical Results

1. Optimism is Sufficient

A significant takeaway is that standard optimistic algorithms (such as UCB-style value iteration) are already capable of achieving logarithmic regret. We do not necessarily need more complex or specialized algorithms; rather, we needed more sophisticated analytical tools to prove these properties under general conditions.

2. Smooth Interpolation

The resulting regret bound is not a simple logarithmic function. Instead, it is a unified formula that naturally adapts to the environment's difficulty. When $T$ is small, the bound behaves like $\sqrt{T}$, matching the minimax rate. As $T$ increases and the agent gathers enough data to distinguish between actions, the bound smoothly transitions to a $\log T$ scaling.

3. The Minimum Gap Penalty

The analysis reveals a fundamental cost of optimism: the regret necessarily depends on the reciprocal of the smallest non-zero sub-optimality gap in the MDP. This occurs because the agent must explore sufficiently to ensure that even a "nearly-optimal" action is not actually the best one. The authors provide a new lower bound confirming that this dependence on the minimum gap and the state space $|S|$ is unavoidable for this class of optimistic algorithms.

Conclusion and Future Work

This work provides a high-probability regret bound of $C_M \log(T/\delta)$ that holds for all $T \ge 1$, where $C_M$ is an instance-specific constant. This represents a significant step forward in making RL theory more applicable to real-world scenarios where environments are not necessarily ergodic.

Despite these advances, several open questions remain. The bounds currently include a "burn-in" period (a gap-independent term) that researchers hope to reduce. Additionally, while the analysis is tailored for model-based methods, extending the "clipping trick" to model-free algorithms like Q-learning or to settings with function approximation (linear or neural RL) remains a promising frontier for future research.

Summary updated

Abstract

This paper establishes that optimistic algorithms attain gap-dependent and non-asymptotic logarithmic regret for episodic MDPs. In contrast to prior work, our bounds do not suffer a dependence on diameter-like quantities or ergodicity, and smoothly interpolate between the gap dependent logarithmic-regret, and the $\widetilde{\mathcal{O}}(\sqrt{HSAT})$-minimax rate. The key technique in our analysis is a novel "clipped" regret decomposition which applies to a broad family of recent optimistic algorithms for episodic MDPs.
BibTeX
@inproceedings{simchowitz2019non,
  author = {Max Simchowitz and Kevin G. Jamieson},
  title = {{Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=6wEE3pGBV2d},
}
Figure