mlsanityData to 7 Oct 2026

Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation

arXiv 2111.10919 ↗First posted 21 Nov 2021cs.LG stat.MLcited by 69

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

Abstract (arXiv)

We consider the offline reinforcement learning problem, where the aim is to learn a decision making policy from logged data. Offline RL -- particularly when coupled with (value) function approximation to allow for generalization in large or continuous state spaces -- is becoming increasingly relevant in practice, because it avoids costly and time-consuming online data collection and is well suited to safety-critical domains. Existing sample complexity guarantees for offline value function approximation methods typically require both (1) distributional assumptions (i.e., good coverage) and (2) representational assumptions (i.e., ability to represent some or all Q-value functions) stronger than what is required for supervised learning. However, the necessity of these conditions and the fundamental limits of offline RL are not well understood in spite of decades of research. This led Chen and Jiang (2019) to conjecture that concentrability (the most standard notion of coverage) and realizability (the weakest representation condition) alone are not sufficient for sample-efficient offline RL. We resolve this conjecture in the positive by proving that in general, even if both concentrability and realizability are satisfied, any algorithm requires sample complexity polynomial in the size of the state space to learn a non-trivial policy. Our results show that sample-efficient offline reinforcement learning requires either restrictive coverage conditions or representation conditions that go beyond supervised learning, and highlight a phenomenon called over-coverage which serves as a fundamental barrier for offline value function approximation methods. A consequence of our results for reinforcement learning with linear function approximation is that the separation between online and offline RL can be arbitrarily large, even in constant dimension.

Key facts. Cited by 69 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 26 of its 53 references that are in the map. First posted on arXiv 21 Nov 2021.

Builds on

26 of 53 references.

Closest ancestors · 5

Same direction, newest first

  1. 2021Instabilities of Offline RL with Pre-Trained Neural Representation8 Mar
  2. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency5 Feb
  3. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  4. 2020Batch Value-function Approximation with Only Realizability11 Aug
  5. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison9 Mar

Other references · 21

  1. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  2. 2019Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reductioncited by 833
  3. 2018QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulationcited by 730
  4. 2016Learning Hand-Eye Coordination for Robotic Grasping with Deep Learning and Large-Scale Data Collectioncited by 312
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  6. 2018Learning to Drive in a Daycited by 266
  7. 2017Deep Reinforcement Learning framework for Autonomous Drivingcited by 224
  8. 2015Supersizing Self-supervision: Learning to Grasp from 50K Tries and 700 Robot Hourscited by 208
  9. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  10. 2017Safe Policy Improvement with Baseline Bootstrappingcited by 141
  11. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  12. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
9 more
  1. 2018Supervised Reinforcement Learning with Recurrent Neural Network for Dynamic Treatment Recommendationcited by 101
  2. 2018Practical Contextual Bandits with Regression Oraclescited by 92
  3. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  4. 2018Evaluating Reinforcement Learning Algorithms in Observational Health Settingscited by 60
  5. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  6. 2019Learning When-to-Treat Policiescited by 49
  7. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  8. 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcited by 24
  9. 2016Adaptive estimation of High-Dimensional Signal-to-Noise Ratioscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 22; 2023: 18; 2024: 11; 2025: 9; 2026: 9.

69 papers.

Sort:

By area:

  1. 2024ArCHer: Training Language Model Agents via Hierarchical Multi-Turn RLcited by 212
  2. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  3. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  4. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 92
  5. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  6. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  7. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  8. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  9. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  10. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  11. 2023Finetuning from Offline Reinforcement Learning: Challenges, Trade-offs and Practical Solutionscited by 26
  12. 2023Harnessing Mixed Offline Reinforcement Learning Datasets via Trajectory Weightingcited by 22
38 more
  1. 2023Survival Instinct in Offline Reinforcement Learningcited by 20
  2. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  3. 2022Learning Bellman Complete Representations for Offline Policy Evaluationcited by 17
  4. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  5. 2022Agent-Controller Representations: Principled Offline RL with Rich Exogenous Informationcited by 15
  6. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraintscited by 15
  7. 2023Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregressioncited by 14
  8. 2025Qsharp: Provably Optimal Distributional RL for LLM Post-Trainingcited by 14
  9. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  10. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learningcited by 13
  11. 2023Minimax Instrumental Variable Regression and L2 Convergence Guarantees without Identification or Closednesscited by 13
  12. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  13. 2022Behavior Prior Representation learning for Offline Reinforcement Learningcited by 12
  14. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 12
  15. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  16. 2023Offline Data Enhanced On-Policy Policy Gradient with Provable Guaranteescited by 11
  17. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10
  18. 2023A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learningcited by 9
  19. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  20. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  21. 2024Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learningcited by 8
  22. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  23. 2022A Complete Characterization of Linear Estimators for Offline Policy Evaluationcited by 7
  24. 2022Reliable Conditioning of Behavioral Cloning for Offline Reinforcement Learningcited by 6
  25. 2023On the Theory of Risk-Aware Agents: Bridging Actor-Critic and Economicscited by 6
  26. 2024The Perils of Optimizing Learned Reward Functions: Low Training Error Does Not Guarantee Low Regretcited by 6
  27. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  28. 2023Unified Off-Policy Learning to Rank: a Reinforcement Learning Perspectivecited by 4
  29. 2024Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learningcited by 4
  30. 2024Advancing Investment Frontiers: Industry-grade Deep Reinforcement Learning for Portfolio Optimizationcited by 4
  31. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximationcited by 4
  32. 2024Primal-Dual Spectral Representation for Off-policy Evaluationcited by 4
  33. 2025Inverse Reinforcement Learning with Just Classification and a Few Regressionscited by 4
  34. 2023VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximationcited by 3
  35. 2023The Optimal Approximation Factors in Misspecified Off-Policy Value Function Estimationcited by 3
  36. 2024Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear qπ-Realizability and Concentrabilitycited by 3
  37. 2022Offline Robot Reinforcement Learning with Uncertainty-Guided Human Expert Samplingcited by 2
  38. 2024Model-Free Robust φ-Divergence Reinforcement Learning Using Both Offline and Online Datacited by 2

50 most cited of 69 All 69 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  2. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  3. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  4. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation
  5. 2021Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning
  6. 2023What can online reinforcement learning with function approximation benefit from general coverage conditions?
  7. 2024Is Value Learning Really the Main Bottleneck in Offline RL?
  8. 2024Leveraging Unlabeled Data Sharing through Kernel Function Approximation in Offline Reinforcement Learning