mlsanityData to 7 Oct 2026

What are the Statistical Limits of Offline RL with Linear Function Approximation?

arXiv 2010.11895 ↗First posted 22 Oct 2020cs.LG cs.AI math.OCcited by 135

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

Abstract (arXiv)

Offline reinforcement learning seeks to utilize offline (observational) data to guide the learning of (causal) sequential decision making strategies. The hope is that offline reinforcement learning coupled with function approximation methods (to deal with the curse of dimensionality) can provide a means to help alleviate the excessive sample complexity burden in modern sequential decision making problems. However, the extent to which this broader approach can be effective is not well understood, where the literature largely consists of sufficient conditions. This work focuses on the basic question of what are necessary representational and distributional conditions that permit provable sample-efficient offline reinforcement learning. Perhaps surprisingly, our main result shows that even if: i) we have realizability in that the true value function of every policy is linear in a given set of features and 2) our off-policy data has good coverage over all features (under a strong spectral condition), then any algorithm still (information-theoretically) requires a number of offline samples that is exponential in the problem horizon in order to non-trivially estimate the value of any given policy. Our results highlight that sample-efficient offline policy evaluation is simply not possible unless significantly stronger conditions hold; such conditions include either having low distribution shift (where the offline data distribution is close to the distribution of the policy to be evaluated) or significantly stronger representational conditions (beyond realizability).

Key facts. Cited by 135 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 28 of its 71 references that are in the map. First posted on arXiv 22 Oct 2020.

Builds on

28 of 71 references.

Closest ancestors · 5

Same direction, newest first

  1. 2020Batch Value-function Approximation with Only Realizability11 Aug
  2. 2020On Reward-Free Reinforcement Learning with Linear Function Approximation19 Jun
  3. 2020MOReL : Model-Based Offline Reinforcement Learning12 May
  4. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison9 Mar
  5. 2019Behavior Regularized Offline Reinforcement Learning26 Nov

Other references · 23

  1. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  2. 2019Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reductioncited by 833
  3. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  4. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  5. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 285
  6. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  7. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  8. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  9. 2017Safe Policy Improvement with Baseline Bootstrappingcited by 141
  10. 2018More Robust Doubly Robust Off-policy Evaluationcited by 141
  11. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  12. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
11 more
  1. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 118
  2. 2016Optimal and Adaptive Off-policy Evaluation in Contextual Banditscited by 111
  3. 2018Supervised Reinforcement Learning with Recurrent Neural Network for Dynamic Treatment Recommendationcited by 101
  4. 2017Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Predictioncited by 93
  5. 2019Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learningcited by 75
  6. 2020DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correctioncited by 71
  7. 2018Evaluating Reinforcement Learning Algorithms in Observational Health Settingscited by 60
  8. 2019Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Samplingcited by 36
  9. 2020Accountable Off-Policy Evaluation With Kernel Bellman Statisticscited by 36
  10. 2020Minimax Value Interval for Off-Policy Evaluation and Policy Optimizationcited by 11
  11. 2020On the Sample Complexity of Reinforcement Learning with Policy Space Generalizationcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 2; 2021: 33; 2022: 36; 2023: 24; 2024: 18; 2025: 16; 2026: 6.

135 papers.

Sort:

By area:

  1. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  2. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  3. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  4. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  5. 2021Offline RL Without Off-Policy Evaluationcited by 150
  6. 2024Provably Robust DPO: Aligning Language Models with Noisy Feedbackcited by 133
  7. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  8. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  9. 2023Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learningcited by 116
  10. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  11. 2022Robust Reinforcement Learning using Offline Datacited by 95
  12. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 92
38 more
  1. 2022When Should We Prefer Offline Reinforcement Learning Over Behavioral Cloning?cited by 86
  2. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  3. 2024Is Value Learning Really the Main Bottleneck in Offline RL?cited by 82
  4. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  5. 2022When does return-conditioned supervised learning work for offline reinforcement learning?cited by 73
  6. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 69
  7. 2021DR3: Value-Based Deep Reinforcement Learning Requires Explicit Regularizationcited by 66
  8. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  9. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  10. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiencycited by 54
  11. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  12. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  13. 2021The Difficulty of Passive Learning in Deep Reinforcement Learningcited by 50
  14. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learningcited by 42
  15. 2021Bootstrapping Fitted Q-Evaluation for Off-Policy Inferencecited by 40
  16. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  17. 2021Instabilities of Offline RL with Pre-Trained Neural Representationcited by 38
  18. 2022Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Errorcited by 31
  19. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  20. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  21. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  22. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  23. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  24. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  25. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  26. 2021Fast Rates for the Regret of Offline Reinforcement Learningcited by 26
  27. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  28. 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
  29. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  30. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficientcited by 24
  31. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  32. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  33. 2022Offline Reinforcement Learning with Instrumental Variables in Confounded Markov Decision Processescited by 19
  34. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  35. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  36. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  37. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  38. 2022Learning Bellman Complete Representations for Offline Policy Evaluationcited by 17

50 most cited of 135 All 135 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2023Offline Reinforcement Learning with Additional Covering Distributions
  2. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  3. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  4. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps
  5. 2021Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning
  6. 2025Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear qπ-Realizability and Concentrability
  7. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  8. 2023Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Data