mlsanityData to 7 Oct 2026

Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs

arXiv 2203.09251 ↗First posted 17 Mar 2022cs.LG stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

In probably approximately correct (PAC) reinforcement learning (RL), an agent is required to identify an ε-optimal policy with probability 1-δ. While minimax optimal algorithms exist for this problem, its instance-dependent complexity remains elusive in episodic Markov decision processes (MDPs). In this paper, we propose the first nearly matching (up to a horizon squared factor and logarithmic terms) upper and lower bounds on the sample complexity of PAC RL in deterministic episodic MDPs with finite state and action spaces. In particular, our bounds feature a new notion of sub-optimality gap for state-action pairs that we call the deterministic return gap. While our instance-dependent lower bound is written as a linear program, our algorithms are very simple and do not require solving such an optimization problem during learning. Their design and analyses employ novel ideas, including graph-theoretical concepts (minimum flows) and a new maximum-coverage exploration strategy.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 27 of its 61 references that are in the map. First posted on arXiv 17 Mar 2022.

Builds on

27 of 61 references.

References · 27

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  4. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  5. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  6. 2020Exploration-Exploitation in Constrained MDPscited by 146
  7. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  8. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  9. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  10. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  11. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  12. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
15 more
  1. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  2. 2020Adaptive Reward-Free Explorationcited by 77
  3. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 62
  4. 2019Pure Exploration with Multiple Correct Answerscited by 60
  5. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  6. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  7. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  8. 2018Exploration in Structured Reinforcement Learningcited by 34
  9. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  10. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  11. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  12. 2020An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Banditscited by 26
  13. 2020Adaptive Sampling for Best Policy Identification in Markov Decision Processescited by 20
  14. 2021A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPscited by 15
  15. 2021Regret Analysis in Deterministic Reinforcement Learningcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 2; 2024: 4; 2025: 7; 2026: 1.

17 papers.

Sort:

By area:

  1. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  2. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  3. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  4. 2022Asymptotic Instance-Optimal Algorithms for Interactive Decision Makingcited by 7
  5. 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
  6. 2024The Value of Reward Lookahead in Reinforcement Learningcited by 6
  7. 2024Test-Time Regret Minimization in Meta Reinforcement Learningcited by 5
  8. 2024Model-Free Active Exploration in Reinforcement Learningcited by 5
  9. 2024Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysiscited by 4
  10. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  11. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  12. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
5 more
  1. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  2. 2025Policy Testing in Markov Decision Processescited by 1
  3. 2025DP-SPRT: Differentially Private Sequential Probability Ratio Testscited by 1
  4. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  5. 2026When Do Multi-Agent Systems Outperform? Analysing the Learning Efficiency of Agentic Systemscited by 1