# A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs

arXiv: https://arxiv.org/abs/2106.13013 · HTML: https://mlsanity.com/paper/2106.13013/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 29 references that are in the map.
- First posted on arXiv 24 Jun 2021.

## Builds on (most cited first, 17 of 17)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [Exploration in Structured Reinforcement Learning](https://mlsanity.com/paper/1806.00775/) (2018)
- [An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits](https://mlsanity.com/paper/2010.12247/) (2020)
- [Adaptive Sampling for Best Policy Identification in Markov Decision Processes](https://mlsanity.com/paper/2009.13405/) (2020)
- [Experimental Design for Regret Minimization in Linear Bandits](https://mlsanity.com/paper/2011.00576/) (2020)

## Built on by (most cited first, 15 of 15)

- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RL](https://mlsanity.com/paper/2410.20254/) (2024)
- [Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs](https://mlsanity.com/paper/2203.09251/) (2022)
- [Optimistic PAC Reinforcement Learning: the Instance-Dependent View](https://mlsanity.com/paper/2207.05852/) (2022)
- [Can Q-Learning be Improved with Advice?](https://mlsanity.com/paper/2110.13052/) (2021)
- [On Gap-dependent Bounds for Offline Reinforcement Learning](https://mlsanity.com/paper/2206.00177/) (2022)
- [Active Coverage for PAC Reinforcement Learning](https://mlsanity.com/paper/2306.13601/) (2023)
- [Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition](https://mlsanity.com/paper/2410.07574/) (2024)
- [Asymptotic Instance-Optimal Algorithms for Interactive Decision Making](https://mlsanity.com/paper/2206.02326/) (2022)
- [Towards Instance-Optimality in Online PAC Reinforcement Learning](https://mlsanity.com/paper/2311.05638/) (2023)
- [Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning](https://mlsanity.com/paper/2206.00796/) (2022)
- [On the Complexity of Representation Learning in Contextual Linear Bandits](https://mlsanity.com/paper/2212.09429/) (2022)
- [Query-Reward Tradeoffs in Multi-Armed Bandits](https://mlsanity.com/paper/2110.05724/) (2021)
- [Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamics](https://mlsanity.com/paper/2202.05799/) (2022)
- [State-free Reinforcement Learning](https://mlsanity.com/paper/2409.18439/) (2024)

## Abstract (arXiv)

We derive a novel asymptotic problem-dependent lower-bound for regret minimization in finite-horizon tabular Markov Decision Processes (MDPs). While, similar to prior work (e.g., for ergodic MDPs), the lower-bound is the solution to an optimization problem, our derivation reveals the need for an additional constraint on the visitation distribution over state-action pairs that explicitly accounts for the dynamics of the MDP. We provide a characterization of our lower-bound through a series of examples illustrating how different MDPs may have significantly different complexity. 1) We first consider a "difficult" MDP instance, where the novel constraint based on the dynamics leads to a larger lower-bound (i.e., a larger regret) compared to the classical analysis. 2) We then show that our lower-bound recovers results previously derived for specific MDP instances. 3) Finally, we show that, in certain "simple" MDPs, the lower bound is considerably smaller than in the general case and it does not scale with the minimum action gap at all. We show that this last result is attainable (up to poly(H) terms, where H is the horizon) by providing a regret upper-bound based on policy gaps for an optimistic algorithm.