mlsanityData to 7 Oct 2026

Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning

arXiv 1703.07710 ↗First posted 22 Mar 2017cs.LG cs.AI stat.MLcited by 175

Not on the map. Why?

Abstract (arXiv)

Statistical performance bounds for reinforcement learning (RL) algorithms can be critical for high-stakes applications like healthcare. This paper introduces a new framework for theoretically measuring the performance of such algorithms called Uniform-PAC, which is a strengthening of the classical Probably Approximately Correct (PAC) framework. In contrast to the PAC framework, the uniform version may be used to derive high probability regret guarantees and so forms a bridge between the two setups that has been missing in the literature. We demonstrate the benefits of the new framework for finite-state episodic MDPs with a new algorithm that is Uniform-PAC and simultaneously achieves optimal regret and PAC guarantees except for a factor of the horizon.

Key facts. Cited by 175 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Mar 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 42; 2022: 37; 2023: 33; 2024: 27; 2025: 21; 2026: 15.

175 papers.

Sort:

By area:

  1. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  2. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  3. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  4. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  5. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  6. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  7. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  8. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  9. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  10. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  11. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  12. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
38 more
  1. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  2. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  3. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  4. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  5. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  6. 2021From Machine Learning to Robotics: Challenges and Opportunities for Embodied Intelligencecited by 35
  7. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 34
  8. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  9. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  10. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  11. 2023Fast Rates for Maximum Entropy Explorationcited by 32
  12. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  13. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  14. 2022Chain of Thought Imitation with Procedure Cloningcited by 30
  15. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  16. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  17. 2021Online Apprenticeship Learningcited by 28
  18. 2021Provable RL with Exogenous Distractors via Multistep Inverse Dynamicscited by 28
  19. 2021NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RLcited by 27
  20. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  21. 2021Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environmentscited by 26
  22. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
  23. 2022Revisiting Simple Regret: Fast Rates for Returning a Good Armcited by 25
  24. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  25. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  26. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  27. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  28. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  29. 2021Reinforcement learning for linear-convex models with jumps via stability analysis of feedback controlscited by 21
  30. 2022Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Pathcited by 21
  31. 2023Accelerating Exploration with Unlabeled Prior Datacited by 21
  32. 2021Linear Systems can be Hard to Learncited by 20
  33. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  34. 2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
  35. 2022Online Policy Optimization for Robust MDPcited by 19
  36. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  37. 2022Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learningcited by 18
  38. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17

50 most cited of 175 All 175 (JSON)