mlsanityData to 7 Oct 2026

Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL

arXiv 2012.08005 ↗First posted 14 Dec 2020cs.LG cs.AIcited by 55

Not on the map. Why?

Cited by 35 in Offline RL and imitation learning from data, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Several practical applications of reinforcement learning involve an agent learning from past data without the possibility of further exploration. Often these applications require us to 1) identify a near optimal policy or to 2) estimate the value of a target policy. For both tasks we derive exponential information-theoretic lower bounds in discounted infinite horizon MDPs with a linear function representation for the action value function even if 1) realizability holds, 2) the batch algorithm observes the exact reward and transition functions, and 3) the batch algorithm is given the best a priori data distribution for the problem class. Our work introduces a new `oracle + batch algorithm' framework to prove lower bounds that hold for every distribution. The work shows an exponential separation between batch and online reinforcement learning.

Key facts. Cited by 55 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Dec 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 22; 2022: 18; 2023: 7; 2024: 4; 2025: 3; 2026: 1.

55 papers.

Sort:

By area:

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  2. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  3. 2021Offline RL Without Off-Policy Evaluationcited by 150
  4. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  5. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  6. 2022When Should We Prefer Offline Reinforcement Learning Over Behavioral Cloning?cited by 86
  7. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  8. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 69
  9. 2021DR3: Value-Based Deep Reinforcement Learning Requires Explicit Regularizationcited by 66
  10. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  11. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  12. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
38 more
  1. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  2. 2021Instabilities of Offline RL with Pre-Trained Neural Representationcited by 38
  3. 2022Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Errorcited by 31
  4. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  5. 2022Data-Driven Offline Decision-Making via Invariant Representation Learningcited by 31
  6. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  7. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  8. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  9. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  10. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  11. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  12. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  13. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  14. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  15. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  16. 2023Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregressioncited by 14
  17. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  18. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  19. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learningcited by 13
  20. 2021Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximationcited by 11
  21. 2021Uncertainty Estimation Using Riemannian Model Dynamics for Offline Reinforcement Learningcited by 10
  22. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithmcited by 10
  23. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10
  24. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guaranteescited by 10
  25. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  26. 2022A Complete Characterization of Linear Estimators for Offline Policy Evaluationcited by 7
  27. 2022Reliable Conditioning of Behavioral Cloning for Offline Reinforcement Learningcited by 6
  28. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  29. 2023Model-based Offline Reinforcement Learning with Local Misspecificationcited by 5
  30. 2024Experiment Planning with Function Approximationcited by 5
  31. 2023What can online reinforcement learning with function approximation benefit from general coverage conditions?cited by 4
  32. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximationcited by 4
  33. 2023VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximationcited by 3
  34. 2024Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear qπ-Realizability and Concentrabilitycited by 3
  35. 2021The Curse of Passive Data Collection in Batch Reinforcement Learningcited by 2
  36. 2021Exploiting Action Impact Regularity and Exogenous State Variables for Offline Reinforcement Learningcited by 2
  37. 2023A Unified Framework of Policy Learning for Contextual Bandit with Confounding Bias and Missing Observationscited by 2
  38. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2

50 most cited of 55 All 55 (JSON)