mlsanityData to 7 Oct 2026

Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps

arXiv 2203.13935 ↗First posted 25 Mar 2022cs.LG stat.MLcited by 34

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

Abstract (arXiv)

We consider a challenging theoretical problem in offline reinforcement learning (RL): obtaining sample-efficiency guarantees with a dataset lacking sufficient coverage, under only realizability-type assumptions for the function approximators. While the existing theory has addressed learning under realizability and under non-exploratory data separately, no work has been able to address both simultaneously (except for a concurrent work which we compare in detail). Under an additional gap assumption, we provide guarantees to a simple pessimistic algorithm based on a version space formed by marginalized importance sampling (MIS), and the guarantee only requires the data to cover the optimal policy and the function classes to realize the optimal value and density-ratio functions. While similar gap assumptions have been used in other areas of RL theory, our work is the first to identify the utility and the novel mechanism of gap assumptions in offline RL with weak function approximation.

Key facts. Cited by 34 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 34 of its 53 references that are in the map. First posted on arXiv 25 Mar 2022.

Builds on

34 of 53 references.

Closest ancestors · 12

Same direction, newest first

  1. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  2. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  3. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  4. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  5. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  6. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  7. 2021Instabilities of Offline RL with Pre-Trained Neural Representation8 Mar
  8. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  9. 2021Fast Rates for the Regret of Offline Reinforcement Learning31 Jan
  10. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  11. 2020Batch Value-function Approximation with Only Realizability11 Aug
  12. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul

Other references · 22

  1. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  2. 2019Introduction to Multi-Armed Banditscited by 475
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  5. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  6. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  7. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  8. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  9. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  10. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  11. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  12. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
10 more
  1. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  2. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  3. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  4. 2020Q-learning with Logarithmic Regretcited by 59
  5. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  6. 2014Approximate Policy Iteration Schemes: A Comparisoncited by 39
  7. 2018Exploration in Structured Reinforcement Learningcited by 34
  8. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 17
  9. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
  10. 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: 2022: 7; 2023: 12; 2024: 8; 2025: 3; 2026: 4.

34 papers.

Sort:

By area:

  1. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  2. 2024The Importance of Online Data: Understanding Preference Fine-tuning via Coveragecited by 55
  3. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  4. 2022Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequalitycited by 32
  5. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  6. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  7. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  8. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  9. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  10. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learningcited by 13
  11. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guaranteescited by 10
  12. 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coveragecited by 9
22 more
  1. 2023A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learningcited by 9
  2. 2022Scaling Marginalized Importance Sampling to High-Dimensional State-Spaces via State Abstractioncited by 7
  3. 2023Distributional Shift-Aware Off-Policy Interval Estimation: A Unified Error Quantification Frameworkcited by 6
  4. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  5. 2023Bi-Level Offline Policy Optimization with Limited Explorationcited by 5
  6. 2023Bayesian Safe Policy Learning with Chance Constrained Optimization: Application to Military Security Assessment during the Vietnam Warcited by 4
  7. 2024Adversarially Trained Weighted Actor-Critic for Safe Offline Reinforcement Learningcited by 4
  8. 2024A Unified Linear Programming Framework for Offline Reward Learning from Human Demonstrations and Feedbackcited by 4
  9. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximationcited by 4
  10. 2023VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximationcited by 3
  11. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
  12. 2023Robust Knowledge Transfer in Tiered Reinforcement Learningcited by 1
  13. 2023Offline Reinforcement Learning with Additional Covering Distributionscited by 1
  14. 2023Stackelberg Batch Policy Learningcited by 1
  15. 2024Online Reinforcement Learning with Passive Memorycited by 1
  16. 2025Offline Constrained Reinforcement Learning under Partial Data Coveragecited by 1
  17. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theorycited by 1
  18. 2024A Fast Convergence Theory for Offline Decision Makingcited by 0
  19. 2026Continuous-time reinforcement learning: ellipticity enables model-free value function approximationcited by 0
  20. 2026On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coveragecited by 0
  21. 2026Efficient Exploration for Iterative Nash Preference Optimizationcited by 0
  22. 2026Deep Weighted Bellman Residual Minimization for Q^* Estimationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?
  2. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  3. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  4. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  5. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  6. 2024Harnessing Density Ratios for Online Reinforcement Learning
  7. 2025Semi-pessimistic Reinforcement Learning
  8. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage