Research map / Bandits and online learning / RL theory and MDPs
Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
Max Simchowitz, Kevin G. Jamieson
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use StrongEuler with gap-dependent clipped regret analysis | StrongEuler on episodic tabular MDPs · Episodic tabular MDPs | cumulative regret: C_{\mathcal{M}} \log T | Improved |
| Interpolate the gap-dependent bound with the minimax regime | StrongEuler on episodic tabular MDPs · Episodic tabular MDPs | cumulative regret: \sqrt{HSAT \log(T) \log(\tfrac{MT}{\delta})} + H^4 S A (S \vee H) \log^2 \tfrac{TM}{\delta} | Improved |
| Exploit state-action gaps and clip small optimistic surpluses | Optimistic algorithms for episodic MDPs · Episodic tabular MDPs | cumulative regret: C_{\mathcal{M}} \log T | Improved |
| Apply the StrongEuler bound to contextual bandit instances | StrongEuler · Contextual bandit instances | cumulative regret: the factors of H under the square roots can be refined to a 1 | Improved |
| Apply the StrongEuler bound to MDPs with bounded rewards | StrongEuler · MDPs with \mathcal{G}-bounded rewards, \mathcal{G} \lesssim 1 | cumulative regret: the factors of H under the square roots can be replaced by a 1/H | Improved |
| Rely on optimism in the stated worst-case instance | Existing optimistic algorithms for finite-horizon MDPs · MDPs with one gap \mathtt{gap}_{\mathtt{min}}=\epsilon and other state gaps at least 1/2 | regret lower bound: \frac{S}{\mathtt{gap}_{\mathtt{min}}}\log (1/\delta) | Hurt |
| Use optimism without a diameter or ergodicity dependence in the bound | StrongEuler · Episodic tabular MDPs | regret bound dependence: depend only on H and not on the diameter D | Improved |
Closest papers by meaning
- Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs (NeurIPS 2025 · similarity 0.94)
- Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning (NeurIPS 2021 · similarity 0.92)
- Gap-Dependent Bounds for Federated $Q$-Learning (ICML 2025 · similarity 0.89)
- Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition (ICLR 2025 · similarity 0.89)
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 2024 · similarity 0.87)
- Position: Constants are Critical in Regret Bounds for Reinforcement Learning (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
