# Offline Reinforcement Learning with Realizability and Single-policy Concentrability

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

## Key facts

- Cited by 123 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 35 of its 56 references that are in the map.
- First posted on arXiv 9 Feb 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 35)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Off-Policy Deep Reinforcement Learning without Exploration](https://mlsanity.com/paper/1812.02900/) (2018)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [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)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [AlgaeDICE: Policy Gradient from Arbitrary Experience](https://mlsanity.com/paper/1912.02074/) (2019)
- [Imitation Learning via Off-Policy Distribution Matching](https://mlsanity.com/paper/1912.05032/) (2019)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [GenDICE: Generalized Offline Estimation of Stationary Values](https://mlsanity.com/paper/2002.09072/) (2020)
- [OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimation](https://mlsanity.com/paper/2106.10783/) (2021)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Reinforcement and Imitation Learning via Interactive No-Regret Learning](https://mlsanity.com/paper/1406.5979/) (2014)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Reinforcement Learning via Fenchel-Rockafellar Duality](https://mlsanity.com/paper/2001.01866/) (2020)
- [Toward the Fundamental Limits of Imitation Learning](https://mlsanity.com/paper/2009.05990/) (2020)
- [Provably Efficient Imitation Learning from Observation Alone](https://mlsanity.com/paper/1905.10948/) (2019)
- [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)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL](https://mlsanity.com/paper/2012.08005/) (2020)
- [Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation](https://mlsanity.com/paper/1910.07186/) (2019)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)

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

- [Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient](https://mlsanity.com/paper/2210.06718/) (2022)
- [Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer](https://mlsanity.com/paper/2405.16436/) (2024)
- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Provable Offline Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.14816/) (2023)
- [The Importance of Online Data: Understanding Preference Fine-tuning via Coverage](https://mlsanity.com/paper/2406.01462/) (2024)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [Leveraging Offline Data in Online Reinforcement Learning](https://mlsanity.com/paper/2211.04974/) (2022)
- [Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcare](https://mlsanity.com/paper/2305.01738/) (2023)
- [Dataset Reset Policy Optimization for RLHF](https://mlsanity.com/paper/2404.08495/) (2024)
- [Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps](https://mlsanity.com/paper/2203.13935/) (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)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Performative Reinforcement Learning](https://mlsanity.com/paper/2207.00046/) (2022)
- [Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2205.13589/) (2022)
- [Offline Imitation Learning with Suboptimal Demonstrations via Relaxed Distribution Matching](https://mlsanity.com/paper/2303.02569/) (2023)
- [Beyond Uniform Sampling: Offline Reinforcement Learning with Imbalanced Datasets](https://mlsanity.com/paper/2310.04413/) (2023)
- [Offline Reinforcement Learning with Instrumental Variables in Confounded Markov Decision Processes](https://mlsanity.com/paper/2209.08666/) (2022)
- [Seizing Serendipity: Exploiting the Value of Past Success in Off-Policy Actor-Critic](https://mlsanity.com/paper/2306.02865/) (2023)
- [Survival Instinct in Offline Reinforcement Learning](https://mlsanity.com/paper/2306.03286/) (2023)
- [Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity](https://mlsanity.com/paper/2306.11626/) (2023)
- [Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Sets](https://mlsanity.com/paper/2205.10671/) (2022)
- [Machine Learning for Large-Scale Optimization in 6G Wireless Networks](https://mlsanity.com/paper/2301.03377/) (2023)
- [Reinforcement Learning in Low-Rank MDPs with Density Features](https://mlsanity.com/paper/2302.02252/) (2023)
- [Offline Learning in Markov Games with General Function Approximation](https://mlsanity.com/paper/2302.02571/) (2023)
- [B-Coder: Value-Based Deep Reinforcement Learning for Program Synthesis](https://mlsanity.com/paper/2310.03173/) (2023)
- [Contrastive Representation for Data Filtering in Cross-Domain Offline Reinforcement Learning](https://mlsanity.com/paper/2405.06192/) (2024)
- [When is Realizability Sufficient for Off-Policy Reinforcement Learning?](https://mlsanity.com/paper/2211.05311/) (2022)
- [Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning](https://mlsanity.com/paper/2305.10282/) (2023)
- [Offline Primal-Dual Reinforcement Learning for Linear MDPs](https://mlsanity.com/paper/2305.12944/) (2023)

## Abstract (arXiv)

Sample-efficiency guarantees for offline reinforcement learning (RL) often rely on strong assumptions on both the function classes (e.g., Bellman-completeness) and the data coverage (e.g., all-policy concentrability). Despite the recent efforts on relaxing these assumptions, existing works are only able to relax one of the two factors, leaving the strong assumption on the other factor intact. As an important open problem, can we achieve sample-efficient offline RL with weak assumptions on both factors? In this paper we answer the question in the positive. We analyze a simple algorithm based on the primal-dual formulation of MDPs, where the dual variables (discounted occupancy) are modeled using a density-ratio function against offline data. With proper regularization, we show that the algorithm enjoys polynomial sample complexity, under only realizability and single-policy concentrability. We also provide alternative analyses based on different assumptions to shed light on the nature of primal-dual algorithms for offline RL.