# Beyond No Regret: Instance-Dependent PAC Reinforcement Learning

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 45 references that are in the map.
- First posted on arXiv 5 Aug 2021.

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?](https://mlsanity.com/paper/2005.00527/) (2020)
- [Exploration in Structured Reinforcement Learning](https://mlsanity.com/paper/1806.00775/) (2018)
- [Planning in Markov Decision Processes with Gap-Dependent Sample Complexity](https://mlsanity.com/paper/2006.05879/) (2020)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Nearly Minimax Optimal Reward-free Reinforcement Learning](https://mlsanity.com/paper/2010.05901/) (2020)
- [Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model](https://mlsanity.com/paper/1806.01492/) (2018)
- [Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning](https://mlsanity.com/paper/2106.14352/) (2021)
- [Task-Optimal Exploration in Linear Dynamical Systems](https://mlsanity.com/paper/2102.05214/) (2021)

## Built on by (most cited first, 30 of 41)

- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes](https://mlsanity.com/paper/2201.11206/) (2022)
- [Leveraging Offline Data in Online Reinforcement Learning](https://mlsanity.com/paper/2211.04974/) (2022)
- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2206.09421/) (2022)
- [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)
- [ReVar: Strengthening Policy Evaluation via Reduced Variance Sampling](https://mlsanity.com/paper/2203.04510/) (2022)
- [Instance-optimal PAC Algorithms for Contextual Bandits](https://mlsanity.com/paper/2207.02357/) (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)
- [Gap-Dependent Unsupervised Exploration for Reinforcement Learning](https://mlsanity.com/paper/2108.05439/) (2021)
- [Maximum diffusion reinforcement learning](https://mlsanity.com/paper/2309.15293/) (2023)
- [Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards](https://mlsanity.com/paper/2303.05606/) (2023)
- [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)
- [Towards Instance-Optimality in Online PAC Reinforcement Learning](https://mlsanity.com/paper/2311.05638/) (2023)
- [Optimal Sample Complexity of Stable Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.07477/) (2023)
- [Adaptive Exploration for Multi-Reward Multi-Policy Evaluation](https://mlsanity.com/paper/2502.02516/) (2025)
- [Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning](https://mlsanity.com/paper/2206.00796/) (2022)
- [What Are the Odds? Improving the foundations of Statistical Model Checking](https://mlsanity.com/paper/2404.05424/) (2024)
- [Test-Time Regret Minimization in Meta Reinforcement Learning](https://mlsanity.com/paper/2406.02282/) (2024)
- [Model-Free Active Exploration in Reinforcement Learning](https://mlsanity.com/paper/2407.00801/) (2024)
- [Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge](https://mlsanity.com/paper/2312.12558/) (2023)
- [Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysis](https://mlsanity.com/paper/2406.07455/) (2024)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/2506.06521/) (2025)
- [Hardness in Markov Decision Processes: Theory and Practice](https://mlsanity.com/paper/2210.13075/) (2022)
- [SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP](https://mlsanity.com/paper/2406.02165/) (2024)
- [Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Design](https://mlsanity.com/paper/2506.09508/) (2025)

## Abstract (arXiv)

The theory of reinforcement learning has focused on two fundamental problems: achieving low regret, and identifying ε-optimal policies. While a simple reduction allows one to apply a low-regret algorithm to obtain an ε-optimal policy and achieve the worst-case optimal rate, it is unknown whether low-regret algorithms can obtain the instance-optimal rate for policy identification. We show this is not possible -- there exists a fundamental tradeoff between achieving low regret and identifying an ε-optimal policy at the instance-optimal rate. Motivated by our negative finding, we propose a new measure of instance-dependent sample complexity for PAC tabular reinforcement learning which explicitly accounts for the attainable state visitation distributions in the underlying MDP. We then propose and analyze a novel, planning-based algorithm which attains this sample complexity -- yielding a complexity which scales with the suboptimality gaps and the "reachability" of a state. We show our algorithm is nearly minimax optimal, and on several examples that our instance-dependent sample complexity offers significant improvements over worst-case bounds.