mlsanityData to 14 Oct 2026

What can online reinforcement learning with function approximation benefit from general coverage conditions?

arXiv 2304.12886 ↗First posted 25 Apr 2023stat.ML cs.LGcited by 4

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

Abstract (arXiv)

In online reinforcement learning (RL), instead of employing standard structural assumptions on Markov decision processes (MDPs), using a certain coverage condition (original from offline RL) is enough to ensure sample-efficient guarantees (Xie et al. 2023). In this work, we focus on this new direction by digging more possible and general coverage conditions, and study the potential and the utility of them in efficient online RL. We identify more concepts, including the Lp variant of concentrability, the density ratio realizability, and trade-off on the partial/rest coverage condition, that can be also beneficial to sample-efficient online RL, achieving improved regret bound. Furthermore, if exploratory offline data are used, under our coverage conditions, both statistically and computationally efficient guarantees can be achieved for online RL. Besides, even though the MDP structure is given, e.g., linear MDP, we elucidate that, good coverage conditions are still beneficial to obtain faster regret bound beyond widetildeO(√T) and even a logarithmic order regret. These results provide a good justification for the usage of general coverage conditions in efficient online RL.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 37 of its 61 references that are in the map. First posted on arXiv 25 Apr 2023.

Builds on

37 of 61 references.

Closest ancestors · 11

Same direction, newest first

  1. 2022Leveraging Offline Data in Online Reinforcement Learning9 Nov
  2. 2022The Role of Coverage in Online Reinforcement Learning9 Oct
  3. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  4. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  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. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  11. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison9 Mar

Other references · 26

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2017Learning Complex Dexterous Manipulation with Deep Reinforcement Learning and Demonstrationscited by 715
  3. 2020AWAC: Accelerating Online Reinforcement Learning with Offline Datasetscited by 671
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  5. 2017A Tutorial on Thompson Samplingcited by 433
  6. 2023Efficient Online Reinforcement Learning with Offline Datacited by 363
  7. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  8. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  9. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  10. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  11. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  12. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
14 more
  1. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  2. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  3. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 161
  4. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  5. 2020Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networkscited by 87
  6. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  7. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  8. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  9. 2022Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximationcited by 31
  10. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  11. 2020Online Sparse Reinforcement Learningcited by 25
  12. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 18
  13. 2022Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Explorationcited by 11
  14. 2020A maximum-entropy approach to off-policy evaluation in average-reward MDPscited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2025Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limitscited by 7
  2. 2025The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspectivecited by 6
  3. 2024Coverage Analysis of Multi-Environment Q-Learning Algorithms for Wireless Network Optimizationcited by 2
  4. 2026From Relative Entropy to Minimax: A Unified Framework for Coverage in MDPscited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2023Offline Reinforcement Learning with Additional Covering Distributions
  2. 2026On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coverage
  3. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  4. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  5. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  6. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  7. 2024A Natural Extension To Online Algorithms For Hybrid RL With Limited Coverage
  8. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures