# Optimistic PAC Reinforcement Learning: the Instance-Dependent View

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 25 references that are in the map.
- First posted on arXiv 12 Jul 2022.

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

- [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)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [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)
- [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)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [A Unifying View of Optimism in Episodic Reinforcement Learning](https://mlsanity.com/paper/2007.01891/) (2020)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [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)
- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs](https://mlsanity.com/paper/2203.09251/) (2022)
- [A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs](https://mlsanity.com/paper/2106.13013/) (2021)

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

- [Leveraging Offline Data in Online Reinforcement Learning](https://mlsanity.com/paper/2211.04974/) (2022)
- [Diversifying AI: Towards Creative Chess with AlphaZero](https://mlsanity.com/paper/2308.09175/) (2023)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [Active Coverage for PAC Reinforcement Learning](https://mlsanity.com/paper/2306.13601/) (2023)
- [Towards Instance-Optimality in Online PAC Reinforcement Learning](https://mlsanity.com/paper/2311.05638/) (2023)
- [Test-Time Regret Minimization in Meta Reinforcement Learning](https://mlsanity.com/paper/2406.02282/) (2024)
- [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)
- [Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms](https://mlsanity.com/paper/2411.00707/) (2024)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [When Do Multi-Agent Systems Outperform? Analysing the Learning Efficiency of Agentic Systems](https://mlsanity.com/paper/2602.08272/) (2026)
- [Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2410.02994/) (2024)
- [Q-Learning with Fine-Grained Gap-Dependent Regret](https://mlsanity.com/paper/2510.06647/) (2025)
- [Provably Efficient Partially Observable Risk-Sensitive Reinforcement Learning with Hindsight Observation](https://mlsanity.com/paper/2402.18149/) (2024)
- [On-line Learning in Tree MDPs by Treating Policies as Bandit Arms](https://mlsanity.com/paper/2605.04979/) (2026)
- [Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedback](https://mlsanity.com/paper/2605.23182/) (2026)

## Abstract (arXiv)

Optimistic algorithms have been extensively studied for regret minimization in episodic tabular MDPs, both from a minimax and an instance-dependent view. However, for the PAC RL problem, where the goal is to identify a near-optimal policy with high probability, little is known about their instance-dependent sample complexity. A negative result of Wagenmaker et al. (2021) suggests that optimistic sampling rules cannot be used to attain the (still elusive) optimal instance-dependent sample complexity. On the positive side, we provide the first instance-dependent bound for an optimistic algorithm for PAC RL, BPI-UCRL, for which only minimax guarantees were available (Kaufmann et al., 2021). While our bound features some minimal visitation probabilities, it also features a refined notion of sub-optimality gap compared to the value gaps that appear in prior work. Moreover, in MDPs with deterministic transitions, we show that BPI-UCRL is actually near-optimal. On the technical side, our analysis is very simple thanks to a new "target trick" of independent interest. We complement these findings with a novel hardness result explaining why the instance-dependent complexity of PAC RL cannot be easily related to that of regret minimization, unlike in the minimax regime.