mlsanityData to 7 Oct 2026

The Role of Coverage in Online Reinforcement Learning

arXiv 2210.04157 ↗First posted 9 Oct 2022cs.LG cs.AI math.OCcited by 82

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

Coverage conditions -- which assert that the data logging distribution adequately covers the state space -- play a fundamental role in determining the sample complexity of offline reinforcement learning. While such conditions might seem irrelevant to online reinforcement learning at first glance, we establish a new connection by showing -- somewhat surprisingly -- that the mere existence of a data distribution with good coverage can enable sample-efficient online RL. Concretely, we show that coverability -- that is, existence of a data distribution that satisfies a ubiquitous coverage condition called concentrability -- can be viewed as a structural property of the underlying MDP, and can be exploited by standard algorithms for sample-efficient exploration, even when the agent does not know said distribution. We complement this result by proving that several weaker notions of coverage, despite being sufficient for offline RL, are insufficient for online RL. We also show that existing complexity measures for online RL, including Bellman rank and Bellman-Eluder dimension, fail to optimally capture coverability, and propose a new complexity measure, the sequential extrapolation coefficient, to provide a unification.

Key facts. Cited by 82 papers in the map (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 36 of its 58 references that are in the map. First posted on arXiv 9 Oct 2022.

Builds on

36 of 58 references.

Closest ancestors · 11

Same direction, newest first

  1. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  2. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learning5 Feb
  3. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  4. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  5. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  6. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  7. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  8. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  9. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  10. 2020Batch Value-function Approximation with Only Realizability11 Aug
  11. 2020On Reward-Free Reinforcement Learning with Linear Function Approximation19 Jun

Other references · 25

  1. 2015Continuous control with deep reinforcement learningcited by 3,279
  2. 2018QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulationcited by 730
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2016Deep Reinforcement Learning for Dialogue Generationcited by 286
  6. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  7. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  8. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  9. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  10. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  11. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  12. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
13 more
  1. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  2. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  3. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  4. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  5. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  6. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  7. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  8. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  9. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  10. 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
  11. 2021Sparsity in Partially Controllable Linear Systemscited by 9
  12. 2019Exploration-Enhanced POLITEXcited by 8
  13. 2022Asymptotic Instance-Optimal Algorithms for Interactive Decision Makingcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 16; 2024: 28; 2025: 20; 2026: 14.

82 papers.

Sort:

By area:

  1. 2024Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferencescited by 176
  2. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  3. 2024Self-Improvement in Language Models: The Sharpening Mechanismcited by 102
  4. 2024Building Math Agents with Multi-Turn Iterative Preference Learningcited by 66
  5. 2024The Importance of Online Data: Understanding Preference Fine-tuning via Coveragecited by 55
  6. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  7. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  8. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  9. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
  10. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  11. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  12. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 20
38 more
  1. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  2. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  3. 2025Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspectivecited by 16
  4. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalentscited by 15
  5. 2023Lower Bounds for Learning in Revealing POMDPscited by 14
  6. 2024Bayesian Design Principles for Offline-to-Online Reinforcement Learningcited by 14
  7. 2025Qsharp: Provably Optimal Distributional RL for LLM Post-Trainingcited by 14
  8. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  9. 2023Unsupervised Behavior Extraction via Random Intent Priorscited by 13
  10. 2024On the Performance of Empirical Risk Minimization with Smoothed Datacited by 13
  11. 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
  12. 2023Offline Data Enhanced On-Policy Policy Gradient with Provable Guaranteescited by 11
  13. 2024Offline Reinforcement Learning: Role of State Aggregation and Trajectory Datacited by 11
  14. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guaranteescited by 10
  15. 2022Eluder-based Regret for Stochastic Contextual MDPscited by 9
  16. 2024Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RLcited by 9
  17. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  18. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  19. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  20. 2024Off-Policy Evaluation in Markov Decision Processes under Weak Distributional Overlapcited by 7
  21. 2025Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limitscited by 7
  22. 2023On the Theory of Risk-Aware Agents: Bridging Actor-Critic and Economicscited by 6
  23. 2024The Value of Reward Lookahead in Reinforcement Learningcited by 6
  24. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  25. 2024Hybrid Preference Optimization for Alignment: Provably Faster Convergence Rates by Combining Offline Preferences with Online Explorationcited by 6
  26. 2024A Natural Extension To Online Algorithms For Hybrid RL With Limited Coveragecited by 5
  27. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  28. 2024Hybrid Reinforcement Learning from Offline Observation Alonecited by 5
  29. 2024Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamicscited by 5
  30. 2026Coverage Improvement and Fast Convergence of On-policy Preference Learningcited by 5
  31. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  32. 2023What can online reinforcement learning with function approximation benefit from general coverage conditions?cited by 4
  33. 2023Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning? A Theoretical Perspectivecited by 4
  34. 2024Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learningcited by 4
  35. 2024Advancing Investment Frontiers: Industry-grade Deep Reinforcement Learning for Portfolio Optimizationcited by 4
  36. 2025Improving Environment Novelty Quantification for Effective Unsupervised Environment Designcited by 4
  37. 2025Can RLHF be More Efficient with Imperfect Reward Models? A Policy Coverage Perspectivecited by 4
  38. 2025MOORL: A Framework for Integrating Offline-Online Reinforcement Learningcited by 4

50 most cited of 82 All 82 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  2. 2023Offline Reinforcement Learning with Additional Covering Distributions
  3. 2021Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning
  4. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  5. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  6. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  7. 2026PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structure
  8. 2022On Gap-dependent Bounds for Offline Reinforcement Learning