mlsanityData to 7 Oct 2026

Offline Reinforcement Learning with Realizability and Single-policy Concentrability

arXiv 2202.04634 ↗First posted 9 Feb 2022cs.LG stat.MLcited by 122

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

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.

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

Builds on

35 of 56 references.

Closest ancestors · 12

Same direction, newest first

  1. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  2. 2021OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimation21 Jun
  3. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  4. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  5. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm17 Mar
  6. 2021Instabilities of Offline RL with Pre-Trained Neural Representation8 Mar
  7. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  8. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  9. 2020Batch Value-function Approximation with Only Realizability11 Aug
  10. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul
  11. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  12. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison9 Mar

Other references · 23

  1. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  2. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  3. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  5. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  6. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  7. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 187
  8. 2019Imitation Learning via Off-Policy Distribution Matchingcited by 182
  9. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  10. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  11. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  12. 2020GenDICE: Generalized Offline Estimation of Stationary Valuescited by 122
11 more
  1. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  2. 2014Reinforcement and Imitation Learning via Interactive No-Regret Learningcited by 116
  3. 2020Reinforcement Learning via Fenchel-Rockafellar Dualitycited by 100
  4. 2020Toward the Fundamental Limits of Imitation Learningcited by 96
  5. 2019Provably Efficient Imitation Learning from Observation Alonecited by 78
  6. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  7. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  8. 2019Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimationcited by 48
  9. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  10. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 32
  11. 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: 2022: 22; 2023: 35; 2024: 24; 2025: 25; 2026: 16.

122 papers.

Sort:

By area:

  1. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  2. 2024Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizercited by 109
  3. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  4. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  5. 2024The Importance of Online Data: Understanding Preference Fine-tuning via Coveragecited by 55
  6. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  7. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  8. 2023Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcarecited by 41
  9. 2024Dataset Reset Policy Optimization for RLHFcited by 41
  10. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  11. 2022Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequalitycited by 32
  12. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
38 more
  1. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  2. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  3. 2022Performative Reinforcement Learningcited by 25
  4. 2023Offline Imitation Learning with Suboptimal Demonstrations via Relaxed Distribution Matchingcited by 24
  5. 2023Beyond Uniform Sampling: Offline Reinforcement Learning with Imbalanced Datasetscited by 24
  6. 2023Seizing Serendipity: Exploiting the Value of Past Success in Off-Policy Actor-Criticcited by 20
  7. 2023Survival Instinct in Offline Reinforcement Learningcited by 20
  8. 2022Offline Reinforcement Learning with Instrumental Variables in Confounded Markov Decision Processescited by 19
  9. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  10. 2023Machine Learning for Large-Scale Optimization in 6G Wireless Networkscited by 18
  11. 2024Contrastive Representation for Data Filtering in Cross-Domain Offline Reinforcement Learningcited by 18
  12. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  13. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  14. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
  15. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  16. 2023Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexitycited by 16
  17. 2023B-Coder: Value-Based Deep Reinforcement Learning for Program Synthesiscited by 16
  18. 2024Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Modelscited by 16
  19. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  20. 2022Federated Offline Reinforcement Learningcited by 13
  21. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learningcited by 13
  22. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learningcited by 13
  23. 2024Performative Reinforcement Learning in Gradually Shifting Environmentscited by 13
  24. 2022Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networkscited by 12
  25. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  26. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  27. 2025KL-Regularized RLHF with Multiple Reference Models: Exact Solutions and Sample Complexitycited by 11
  28. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10
  29. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guaranteescited by 10
  30. 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coveragecited by 9
  31. 2023A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learningcited by 9
  32. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  33. 2024Learning from Sparse Offline Datasets via Conservative Density Estimationcited by 9
  34. 2024Efficient Prompt Caching via Embedding Similaritycited by 9
  35. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 9
  36. 2024Energy-Based Preference Model Offers Better Offline Alignment than the Bradley-Terry Preference Modelcited by 9
  37. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 9
  38. 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8

50 most cited of 122 All 122 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  2. 2024A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
  3. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  4. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  5. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  6. 2023Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Data
  7. 2021Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning
  8. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency