# Instance-Dependent Confidence and Early Stopping for Reinforcement Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 41 references that are in the map.
- First posted on arXiv 21 Jan 2022.

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

- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World](https://mlsanity.com/paper/1703.06907/) (2017)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Model-Based Reinforcement Learning for Atari](https://mlsanity.com/paper/1903.00374/) (2019)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [Optimal policy evaluation using kernel-based temporal difference methods](https://mlsanity.com/paper/2109.12002/) (2021)
- [Reanalysis of Variance Reduced Temporal Difference Learning](https://mlsanity.com/paper/2001.01898/) (2020)
- [Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning](https://mlsanity.com/paper/2106.14352/) (2021)
- [ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm](https://mlsanity.com/paper/2008.12690/) (2020)

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

- [Optimal Sample Complexity of Stable Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.07477/) (2023)
- [Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning](https://mlsanity.com/paper/2206.00796/) (2022)
- [A Framework for History-Aware Hyperparameter Optimisation in Reinforcement Learning](https://mlsanity.com/paper/2303.05186/) (2023)
- [Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize](https://mlsanity.com/paper/2407.10955/) (2024)
- [To bootstrap or to rollout? An optimal and adaptive interpolation](https://mlsanity.com/paper/2411.09731/) (2024)

## Abstract (arXiv)

Various algorithms for reinforcement learning (RL) exhibit dramatic variation in their convergence rates as a function of problem structure. Such problem-dependent behavior is not captured by worst-case analyses and has accordingly inspired a growing effort in obtaining instance-dependent guarantees and deriving instance-optimal algorithms for RL problems. This research has been carried out, however, primarily within the confines of theory, providing guarantees that explain textitex post the performance differences observed. A natural next step is to convert these theoretical guarantees into guidelines that are useful in practice. We address the problem of obtaining sharp instance-dependent confidence regions for the policy evaluation problem and the optimal value estimation problem of an MDP, given access to an instance-optimal algorithm. As a consequence, we propose a data-dependent stopping rule for instance-optimal algorithms. The proposed stopping rule adapts to the instance-specific difficulty of the problem and allows for early termination for problems with favorable structure.