# Active Coverage for PAC Reinforcement Learning

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

## Key facts

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

## Builds on (most cited first, 30 of 41)

- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Reinforcement Learning with Prototypical Representations](https://mlsanity.com/paper/2102.11271/) (2021)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [URLB: Unsupervised Reinforcement Learning Benchmark](https://mlsanity.com/paper/2110.15191/) (2021)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation](https://mlsanity.com/paper/2111.10919/) (2021)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration](https://mlsanity.com/paper/2008.07737/) (2020)
- [Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint](https://mlsanity.com/paper/2106.03787/) (2021)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [The Importance of Non-Markovianity in Maximum State Entropy Exploration](https://mlsanity.com/paper/2202.03060/) (2022)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)

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

- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [Towards Instance-Optimality in Online PAC Reinforcement Learning](https://mlsanity.com/paper/2311.05638/) (2023)
- [The Value of Reward Lookahead in Reinforcement Learning](https://mlsanity.com/paper/2403.11637/) (2024)
- [RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation](https://mlsanity.com/paper/2406.01389/) (2024)
- [From Relative Entropy to Minimax: A Unified Framework for Coverage in MDPs](https://mlsanity.com/paper/2601.11890/) (2026)
- [Improved Bounds for Reward-Agnostic and Reward-Free Exploration](https://mlsanity.com/paper/2602.16363/) (2026)
- [kappa-Explorer: A Unified Framework for Active Model Estimation in MDPs](https://mlsanity.com/paper/2602.20404/) (2026)
- [Robust PAC Learning of Concurrent Stochastic Games](https://mlsanity.com/paper/2609.04189/) (2026)

## 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.