# Scalable Online Exploration via Coverability

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- First posted on arXiv 11 Mar 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective](https://mlsanity.com/paper/2502.10581/) (2025)
- [Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Bandits](https://mlsanity.com/paper/2502.06051/) (2025)
- [Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits](https://mlsanity.com/paper/2505.20268/) (2025)
- [RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation](https://mlsanity.com/paper/2406.01389/) (2024)
- [Can RLHF be More Efficient with Imperfect Reward Models? A Policy Coverage Perspective](https://mlsanity.com/paper/2502.19255/) (2025)
- [SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignment](https://mlsanity.com/paper/2505.21395/) (2025)
- [Multiple-policy Evaluation via Density Estimation](https://mlsanity.com/paper/2404.00195/) (2024)
- [A Unifying View of Coverage in Linear Off-Policy Evaluation](https://mlsanity.com/paper/2601.19030/) (2026)
- [Improved Bounds for Reward-Agnostic and Reward-Free Exploration](https://mlsanity.com/paper/2602.16363/) (2026)
- [The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration](https://mlsanity.com/paper/2602.01453/) (2026)

## Abstract (arXiv)

Exploration is a major challenge in reinforcement learning, especially for high-dimensional domains that require function approximation. We propose exploration objectives -- policy optimization objectives that enable downstream maximization of any reward function -- as a conceptual framework to systematize the study of exploration. Within this framework, we introduce a new objective, L1-Coverage, which generalizes previous exploration schemes and supports three fundamental desiderata: 1. Intrinsic complexity control. L1-Coverage is associated with a structural parameter, L1-Coverability, which reflects the intrinsic statistical difficulty of the underlying MDP, subsuming Block and Low-Rank MDPs. 2. Efficient planning. For a known MDP, optimizing L1-Coverage efficiently reduces to standard policy optimization, allowing flexible integration with off-the-shelf methods such as policy gradient and Q-learning approaches. 3. Efficient exploration. L1-Coverage enables the first computationally efficient model-based and model-free algorithms for online (reward-free or reward-driven) reinforcement learning in MDPs with low coverability. Empirically, we find that L1-Coverage effectively drives off-the-shelf policy optimization algorithms to explore the state space.