mlsanityData to 7 Oct 2026

The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation

arXiv 2406.11686 ↗First posted 17 Jun 2024cs.LG cs.AI stat.MLcited by 4

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

Abstract (arXiv)

In this paper, we study the offline RL problem with linear function approximation. Our main structural assumption is that the MDP has low inherent Bellman error, which stipulates that linear value functions have linear Bellman backups with respect to the greedy policy. This assumption is natural in that it is essentially the minimal assumption required for value iteration to succeed. We give a computationally efficient algorithm which succeeds under a single-policy coverage condition on the dataset, namely which outputs a policy whose value is at least that of any policy which is well-covered by the dataset. Even in the setting when the inherent Bellman error is 0 (termed linear Bellman completeness), our algorithm yields the first known guarantee under single-policy coverage. In the setting of positive inherent Bellman error varepsilonBE > 0, we show that the suboptimality error of our algorithm scales with √varepsilonBE. Furthermore, we prove that the scaling of the suboptimality with √varepsilonBE cannot be improved for any algorithm. Our lower bound stands in contrast to many other settings in reinforcement learning with misspecification, where one can typically obtain performance that degrades linearly with the misspecification error.

Key facts. Cited by 4 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 46 references that are in the map. First posted on arXiv 17 Jun 2024.

Builds on

26 of 46 references.

Closest ancestors · 16

Same direction, newest first

  1. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPs22 May
  2. 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage5 Feb
  3. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learning30 Jan
  4. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints28 Dec
  5. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game31 May
  6. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps25 Mar
  7. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar
  8. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity28 Feb
  9. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  10. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learning5 Feb
  11. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  12. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
4 more
  1. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  2. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  3. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul
  4. 2020MOPO: Model-based Offline Policy Optimization27 May

Other references · 10

  1. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  2. 2019Introduction to Online Convex Optimizationcited by 793
  3. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  4. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  5. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  6. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  7. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  8. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  9. 2023Provable Guarantees for Generative Behavior Cloning: Bridging Low-Level Stability and High-Level Behaviorcited by 33
  10. 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcited by 24

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 2.

4 papers.

  1. 2024Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learningcited by 9
  2. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theorycited by 1
  3. 2026On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coveragecited by 0
  4. 2026When Does Trajectory-Level Supervision Permit Efficient Offline Reinforcement Learning?cited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learning
  2. 2026Lifted Bellman Linear Programming for Offline Reinforcement Learning
  3. 2025Bellman Calibration for V-Learning in Offline Reinforcement Learning
  4. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  5. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation
  6. 2024A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
  7. 2025Stability and Generalization for Bellman Residuals
  8. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning