mlsanityData to 7 Oct 2026

On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL

arXiv 2206.10770 ↗First posted 21 Jun 2022cs.LG cs.AI stat.MLcited by 27

Not on the map. Why?

Abstract (arXiv)

We study reward-free reinforcement learning (RL) under general non-linear function approximation, and establish sample efficiency and hardness results under various standard structural assumptions. On the positive side, we propose the RFOLIVE (Reward-Free OLIVE) algorithm for sample-efficient reward-free exploration under minimal structural assumptions, which covers the previously studied settings of linear MDPs (Jin et al., 2020b), linear completeness (Zanette et al., 2020b) and low-rank MDPs with unknown representation (Modi et al., 2021). Our analyses indicate that the explorability or reachability assumptions, previously made for the latter two settings, are not necessary statistically for reward-free exploration. On the negative side, we provide a statistical hardness result for both reward-free and reward-aware exploration under linear completeness assumptions when the underlying features are unknown, showing an exponential separation between low-rank and linear completeness settings.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). Builds on 37 of its 81 references that are in the map. First posted on arXiv 21 Jun 2022.

Builds on

37 of 81 references.

References · 37

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2020Learning Invariant Representations for Reinforcement Learning without Reconstructioncited by 424
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  5. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  10. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  11. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  12. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
25 more
  1. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  2. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  3. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  4. 2020Batch Value-function Approximation with Only Realizabilitycited by 103
  5. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  6. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  7. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  8. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  9. 2020Adaptive Reward-Free Explorationcited by 77
  10. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  11. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  12. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 69
  13. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  14. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  15. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  16. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  17. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  18. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  19. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  20. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  21. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  22. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  23. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
  24. 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10
  25. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 10; 2024: 10; 2025: 1; 2026: 3.

27 papers.

Sort:

By area:

  1. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  2. 2022Spectral Decomposition Representation for Reinforcement Learningcited by 35
  3. 2023Optimistic Active Exploration of Dynamical Systemscited by 32
  4. 2023Provable Reward-Agnostic Preference-Based Reinforcement Learningcited by 25
  5. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  6. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  7. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  8. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  9. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  10. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  11. 2024Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learningcited by 13
  12. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
15 more
  1. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 9
  2. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  3. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  4. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 7
  5. 2024Beyond Optimism: Exploration With Partially Observable Rewardscited by 6
  6. 2024Experiment Planning with Function Approximationcited by 5
  7. 2024Uncertainty-Aware Reward-Free Exploration with General Function Approximationcited by 5
  8. 2023Low-Rank MDPs with Continuous Action Spacescited by 4
  9. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  10. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  11. 2024Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Taskscited by 1
  12. 2026Improved Bounds for Reward-Agnostic and Reward-Free Explorationcited by 1
  13. 2025Thompson Sampling-Based Learning and Control for Unknown Dynamic Systemscited by 0
  14. 2026The Horizon Threshold in Cooperative Multi-Agent Reward-Free Explorationcited by 0
  15. 2026Rank-Then-Act: Reward-Free Control from Frame-Order Progresscited by 0