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

arXiv: https://arxiv.org/abs/2203.13935 · HTML: https://mlsanity.com/paper/2203.13935/

## Key facts

- Cited by 34 papers in the map (data through 14 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.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 30 of 34)

- [Off-Policy Deep Reinforcement Learning without Exploration](https://mlsanity.com/paper/1812.02900/) (2018)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Off-Policy Evaluation via the Regularized Lagrangian](https://mlsanity.com/paper/2007.03438/) (2020)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Provably Good Batch Reinforcement Learning Without Great Exploration](https://mlsanity.com/paper/2007.08202/) (2020)
- [Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation](https://mlsanity.com/paper/2111.10919/) (2021)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Approximate Policy Iteration Schemes: A Comparison](https://mlsanity.com/paper/1405.2878/) (2014)
- [Instabilities of Offline RL with Pre-Trained Neural Representation](https://mlsanity.com/paper/2103.04947/) (2021)
- [Exploration in Structured Reinforcement Learning](https://mlsanity.com/paper/1806.00775/) (2018)

## Built on by (most cited first, 30 of 34)

- [Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient](https://mlsanity.com/paper/2210.06718/) (2022)
- [The Importance of Online Data: Understanding Preference Fine-tuning via Coverage](https://mlsanity.com/paper/2406.01462/) (2024)
- [Leveraging Offline Data in Online Reinforcement Learning](https://mlsanity.com/paper/2211.04974/) (2022)
- [Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality](https://mlsanity.com/paper/2212.09900/) (2022)
- [Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian](https://mlsanity.com/paper/2211.00716/) (2022)
- [On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL](https://mlsanity.com/paper/2206.10770/) (2022)
- [Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Sets](https://mlsanity.com/paper/2205.10671/) (2022)
- [Reinforcement Learning in Low-Rank MDPs with Density Features](https://mlsanity.com/paper/2302.02252/) (2023)
- [Offline Multitask Representation Learning for Reinforcement Learning](https://mlsanity.com/paper/2403.11574/) (2024)
- [Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learning](https://mlsanity.com/paper/2301.12714/) (2023)
- [Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage](https://mlsanity.com/paper/2302.02392/) (2023)
- [Offline Reinforcement Learning in Large State Spaces: Algorithms and Guarantees](https://mlsanity.com/paper/2510.04088/) (2025)
- [A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learning](https://mlsanity.com/paper/2306.07818/) (2023)
- [Scaling Marginalized Importance Sampling to High-Dimensional State-Spaces via State Abstraction](https://mlsanity.com/paper/2212.07486/) (2022)
- [Distributional Shift-Aware Off-Policy Interval Estimation: A Unified Error Quantification Framework](https://mlsanity.com/paper/2309.13278/) (2023)
- [On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond](https://mlsanity.com/paper/2401.03301/) (2024)
- [Bi-Level Offline Policy Optimization with Limited Exploration](https://mlsanity.com/paper/2310.06268/) (2023)
- [Bayesian Safe Policy Learning with Chance Constrained Optimization: Application to Military Security Assessment during the Vietnam War](https://mlsanity.com/paper/2307.08840/) (2023)
- [Adversarially Trained Weighted Actor-Critic for Safe Offline Reinforcement Learning](https://mlsanity.com/paper/2401.00629/) (2024)
- [A Unified Linear Programming Framework for Offline Reward Learning from Human Demonstrations and Feedback](https://mlsanity.com/paper/2405.12421/) (2024)
- [The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2406.11686/) (2024)
- [VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximation](https://mlsanity.com/paper/2302.12780/) (2023)
- [Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach](https://mlsanity.com/paper/2305.13289/) (2023)
- [Robust Knowledge Transfer in Tiered Reinforcement Learning](https://mlsanity.com/paper/2302.05534/) (2023)
- [Offline Reinforcement Learning with Additional Covering Distributions](https://mlsanity.com/paper/2305.12679/) (2023)
- [Stackelberg Batch Policy Learning](https://mlsanity.com/paper/2309.16188/) (2023)
- [Online Reinforcement Learning with Passive Memory](https://mlsanity.com/paper/2410.14665/) (2024)
- [Offline Constrained Reinforcement Learning under Partial Data Coverage](https://mlsanity.com/paper/2505.17506/) (2025)
- [A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory](https://mlsanity.com/paper/2508.07746/) (2025)
- [A Fast Convergence Theory for Offline Decision Making](https://mlsanity.com/paper/2406.01378/) (2024)

## 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.