# Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation

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

## Key facts

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

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 26 of 26)

- [Off-Policy Deep Reinforcement Learning without Exploration](https://mlsanity.com/paper/1812.02900/) (2018)
- [Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction](https://mlsanity.com/paper/1906.00949/) (2019)
- [QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulation](https://mlsanity.com/paper/1806.10293/) (2018)
- [Learning Hand-Eye Coordination for Robotic Grasping with Deep Learning and Large-Scale Data Collection](https://mlsanity.com/paper/1603.02199/) (2016)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Learning to Drive in a Day](https://mlsanity.com/paper/1807.00412/) (2018)
- [Deep Reinforcement Learning framework for Autonomous Driving](https://mlsanity.com/paper/1704.02532/) (2017)
- [Supersizing Self-supervision: Learning to Grasp from 50K Tries and 700 Robot Hours](https://mlsanity.com/paper/1509.06825/) (2015)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Safe Policy Improvement with Baseline Bootstrapping](https://mlsanity.com/paper/1712.06924/) (2017)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Supervised Reinforcement Learning with Recurrent Neural Network for Dynamic Treatment Recommendation](https://mlsanity.com/paper/1807.01473/) (2018)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Evaluating Reinforcement Learning Algorithms in Observational Health Settings](https://mlsanity.com/paper/1805.12298/) (2018)
- [Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency](https://mlsanity.com/paper/2102.02981/) (2021)
- [Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL](https://mlsanity.com/paper/2012.08005/) (2020)
- [Learning When-to-Treat Policies](https://mlsanity.com/paper/1905.09751/) (2019)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Instabilities of Offline RL with Pre-Trained Neural Representation](https://mlsanity.com/paper/2103.04947/) (2021)
- [A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting](https://mlsanity.com/paper/2011.01075/) (2020)
- [Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison](https://mlsanity.com/paper/2003.03924/) (2020)
- [Adaptive estimation of High-Dimensional Signal-to-Noise Ratios](https://mlsanity.com/paper/1602.08006/) (2016)

## Built on by (most cited first, 30 of 71)

- [ArCHer: Training Language Model Agents via Hierarchical Multi-Turn RL](https://mlsanity.com/paper/2402.19446/) (2024)
- [Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient](https://mlsanity.com/paper/2210.06718/) (2022)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [A Review of Off-Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2212.06355/) (2022)
- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps](https://mlsanity.com/paper/2203.13935/) (2022)
- [Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian](https://mlsanity.com/paper/2211.00716/) (2022)
- [On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL](https://mlsanity.com/paper/2206.10770/) (2022)
- [The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learning](https://mlsanity.com/paper/2305.15703/) (2023)
- [Finetuning from Offline Reinforcement Learning: Challenges, Trade-offs and Practical Solutions](https://mlsanity.com/paper/2303.17396/) (2023)
- [Harnessing Mixed Offline Reinforcement Learning Datasets via Trajectory Weighting](https://mlsanity.com/paper/2306.13085/) (2023)
- [Survival Instinct in Offline Reinforcement Learning](https://mlsanity.com/paper/2306.03286/) (2023)
- [Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Sets](https://mlsanity.com/paper/2205.10671/) (2022)
- [Learning Bellman Complete Representations for Offline Policy Evaluation](https://mlsanity.com/paper/2207.05837/) (2022)
- [When is Realizability Sufficient for Off-Policy Reinforcement Learning?](https://mlsanity.com/paper/2211.05311/) (2022)
- [Agent-Controller Representations: Principled Offline RL with Rich Exogenous Information](https://mlsanity.com/paper/2211.00164/) (2022)
- [Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints](https://mlsanity.com/paper/2212.13861/) (2022)
- [Qsharp: Provably Optimal Distributional RL for LLM Post-Training](https://mlsanity.com/paper/2502.20548/) (2025)
- [Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregression](https://mlsanity.com/paper/2310.11428/) (2023)
- [Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward](https://mlsanity.com/paper/2206.06426/) (2022)
- [Oracle Inequalities for Model Selection in Offline Reinforcement Learning](https://mlsanity.com/paper/2211.02016/) (2022)
- [Minimax Instrumental Variable Regression and L2 Convergence Guarantees without Identification or Closedness](https://mlsanity.com/paper/2302.05404/) (2023)
- [Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problems](https://mlsanity.com/paper/2307.12975/) (2023)
- [Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient](https://mlsanity.com/paper/2210.00750/) (2022)
- [Behavior Prior Representation learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2211.00863/) (2022)
- [Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data](https://mlsanity.com/paper/2307.04354/) (2023)
- [Offline Data Enhanced On-Policy Policy Gradient with Provable Guarantees](https://mlsanity.com/paper/2311.08384/) (2023)
- [Bellman Residual Orthogonalization for Offline Reinforcement Learning](https://mlsanity.com/paper/2203.12786/) (2022)
- [A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learning](https://mlsanity.com/paper/2306.07818/) (2023)

## 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.