mlsanityData to 7 Oct 2026

Active Coverage for PAC Reinforcement Learning

arXiv 2306.13601 ↗First posted 23 Jun 2023cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

Collecting and leveraging data with good coverage properties plays a crucial role in different aspects of reinforcement learning (RL), including reward-free exploration and offline learning. However, the notion of "good coverage" really depends on the application at hand, as data suitable for one context may not be so for another. In this paper, we formalize the problem of active coverage in episodic Markov decision processes (MDPs), where the goal is to interact with the environment so as to fulfill given sampling requirements. This framework is sufficiently flexible to specify any desired coverage property, making it applicable to any problem that involves online exploration. Our main contribution is an instance-dependent lower bound on the sample complexity of active coverage and a simple game-theoretic algorithm, CovGame, that nearly matches it. We then show that CovGame can be used as a building block to solve different PAC RL tasks. In particular, we obtain a simple algorithm for PAC reward-free exploration with an instance-dependent sample complexity that, in certain MDPs which are "easy to explore", is lower than the minimax one. By further coupling this exploration algorithm with a new technique to do implicit eliminations in policy space, we obtain a computationally-efficient algorithm for best-policy identification whose instance-dependent sample complexity scales with gaps between policy values.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 41 of its 56 references that are in the map. First posted on arXiv 23 Jun 2023.

Builds on

41 of 56 references.

References · 41

  1. 2018Exploration by Random Network Distillationcited by 966
  2. 2018Diversity is All You Need: Learning Skills without a Reward Functioncited by 734
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  6. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  7. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  8. 2021Reinforcement Learning with Prototypical Representationscited by 179
  9. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  10. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  11. 2020Exploration-Exploitation in Constrained MDPscited by 146
  12. 2021URLB: Unsupervised Reinforcement Learning Benchmarkcited by 138
29 more
  1. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  2. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  3. 2020Batch Value-function Approximation with Only Realizabilitycited by 103
  4. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  5. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  6. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  7. 2021Reward is enough for convex MDPscited by 82
  8. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  9. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  10. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  11. 2020Adaptive Reward-Free Explorationcited by 77
  12. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 69
  13. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 62
  14. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  15. 2021Concave Utility Reinforcement Learning: the Mean-Field Game Viewpointcited by 54
  16. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  17. 2022The Importance of Non-Markovianity in Maximum State Entropy Explorationcited by 35
  18. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  19. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  20. 2021Leveraging Good Representations in Linear Contextual Banditscited by 29
  21. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  22. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparisoncited by 22
  23. 2020Active Model Estimation in Markov Decision Processescited by 20
  24. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  25. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  26. 2020A Provably Efficient Sample Collection Strategy for Reinforcement Learningcited by 15
  27. 2021A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPscited by 15
  28. 2021Dealing With Misspecification In Fixed-Confidence Linear Top-m Identificationcited by 11
  29. 2019Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewardscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 0; 2026: 4.

8 papers.

  1. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  2. 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
  3. 2024The Value of Reward Lookahead in Reinforcement Learningcited by 6
  4. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  5. 2026From Relative Entropy to Minimax: A Unified Framework for Coverage in MDPscited by 1
  6. 2026Improved Bounds for Reward-Agnostic and Reward-Free Explorationcited by 1
  7. 2026kappa-Explorer: A Unified Framework for Active Model Estimation in MDPscited by 0
  8. 2026Robust PAC Learning of Concurrent Stochastic Gamescited by 0