mlsanityData to 14 Oct 2026

When is Realizability Sufficient for Off-Policy Reinforcement Learning?

arXiv 2211.05311 ↗First posted 10 Nov 2022cs.LGcited by 17

Not on the map. Why?

Abstract (arXiv)

Model-free algorithms for reinforcement learning typically require a condition called Bellman completeness in order to successfully operate off-policy with function approximation, unless additional conditions are met. However, Bellman completeness is a requirement that is much stronger than realizability and that is deemed to be too strong to hold in practice. In this work, we relax this structural assumption and analyze the statistical complexity of off-policy reinforcement learning when only realizability holds for the prescribed function class. We establish finite-sample guarantees for off-policy reinforcement learning that are free of the approximation error term known as inherent Bellman error, and that depend on the interplay of three factors. The first two are well known: they are the metric entropy of the function class and the concentrability coefficient that represents the cost of learning off-policy. The third factor is new, and it measures the violation of Bellman completeness, namely the mis-alignment between the chosen function class and its image through the Bellman operator. In essence, these error bounds establish that off-policy reinforcement learning remains statistically viable even in absence of Bellman completeness, and characterize the intermediate situation between the favorable Bellman complete setting and the worst-case scenario where exponential lower bounds are in force. Our analysis directly applies to the solution found by temporal difference algorithms when they converge.

Key facts. Cited by 17 papers in the map (data through 14 Oct 2026). Builds on 39 of its 63 references that are in the map. First posted on arXiv 10 Nov 2022.

Builds on

39 of 63 references.

References · 39

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,417
  3. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  4. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 339
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  6. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 286
  7. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 269
  8. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 227
  9. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  10. 2019A Theoretical Analysis of Deep Q-Learningcited by 215
  11. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 188
  12. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
27 more
  1. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  2. 2018More Robust Doubly Robust Off-policy Evaluationcited by 141
  3. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 136
  4. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 123
  5. 2020GenDICE: Generalized Offline Estimation of Stationary Valuescited by 122
  6. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  7. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 119
  8. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learningcited by 111
  9. 2020Batch Value-function Approximation with Only Realizabilitycited by 104
  10. 2020Reinforcement Learning via Fenchel-Rockafellar Dualitycited by 100
  11. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  12. 2022The Role of Coverage in Online Reinforcement Learningcited by 83
  13. 2019Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learningcited by 75
  14. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  15. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 71
  16. 2020GradientDICE: Rethinking Generalized Offline Estimation of Stationary Valuescited by 70
  17. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiencycited by 56
  18. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  19. 2019Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimationcited by 48
  20. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  21. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learningcited by 42
  22. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  23. 2022On Well-posedness and Minimax Optimal Rates of Nonparametric Q-function Estimation in Off-policy Evaluationcited by 33
  24. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  25. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparisoncited by 22
  26. 2022Learning Bellman Complete Representations for Offline Policy Evaluationcited by 17
  27. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10

Built on by

Cited by year

Citing papers per year: 2023: 6; 2024: 4; 2025: 7.

17 papers.

Sort:

By area:

  1. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
  2. 2024ArCHer: Training Language Model Agents via Hierarchical Multi-Turn RLcited by 228
  3. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 13
  4. 2023Free from Bellman Completeness: Trajectory Stitching via Model-based Return-conditioned Supervised Learningcited by 13
  5. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  6. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guaranteescited by 10
  7. 2023A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learningcited by 9
  8. 2024A Natural Extension To Online Algorithms For Hybrid RL With Limited Coveragecited by 5
  9. 2024OMPO: A Unified Framework for RL under Policy and Dynamics Shiftscited by 5
  10. 2025Enhancing PPO with Trajectory-Aware Hybrid Policiescited by 4
  11. 2025Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Designcited by 3
  12. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
5 more
  1. 2024Regularized Q-Learning with Linear Function Approximationcited by 2
  2. 2025Convergence of Policy Mirror Descent Beyond Compatible Function Approximationcited by 2
  3. 2025Quantum Non-Linear Bandit Optimizationcited by 2
  4. 2025Fitted Q-Evaluation without Bellman Completeness via Occupancy Weightingcited by 2
  5. 2025Offline Constrained Reinforcement Learning under Partial Data Coveragecited by 1