mlsanityData to 14 Oct 2026

Settling the Sample Complexity of Model-Based Offline Reinforcement Learning

arXiv 2204.05275 ↗First posted 11 Apr 2022stat.ML cs.IT cs.LGcited by 83

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

Abstract (arXiv)

This paper is concerned with offline reinforcement learning (RL), which learns using pre-collected data without further exploration. Effective offline RL would be able to accommodate distribution shift and limited data coverage. However, prior algorithms or analyses either suffer from suboptimal sample complexities or incur high burn-in cost to reach sample optimality, thus posing an impediment to efficient offline RL in sample-starved applications. We demonstrate that the model-based (or "plug-in") approach achieves minimax-optimal sample complexity without burn-in cost for tabular Markov decision processes (MDPs). Concretely, consider a finite-horizon (resp. γ-discounted infinite-horizon) MDP with S states and horizon H (resp. effective horizon frac11-γ), and suppose the distribution shift of data is reflected by some single-policy clipped concentrability coefficient Cstarclipped. We prove that model-based offline RL yields varepsilon-accuracy with a sample complexity of [ begincases fracH4SCclippedstarvarepsilon2 & (finite-horizon MDPs) fracSCclippedstar(1-γ)3varepsilon2 & (infinite-horizon MDPs) endcases ] up to log factor, which is minimax optimal for the entire varepsilon-range. The proposed algorithms are "pessimistic" variants of value iteration with Bernstein-style penalties, and do not require sophisticated variance reduction. Our analysis framework is established upon delicate leave-one-out decoupling arguments in conjunction with careful self-bounding techniques tailored to MDPs.

Key facts. Cited by 83 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 2 of its 8 references that are in the map. First posted on arXiv 11 Apr 2022.

Builds on

2 of 8 references.

Closest ancestors · 1

Same direction, newest first

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar

Other references · 1

  1. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 15; 2023: 23; 2024: 13; 2025: 19; 2026: 13.

83 papers.

Sort:

By area:

  1. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
  2. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 55
  3. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  4. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
  5. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  6. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  7. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 30
  8. 2023RLIF: Interactive Imitation Learning as Reinforcement Learningcited by 30
  9. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  10. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 29
  11. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
  12. 2026Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statisticcited by 21
38 more
  1. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  2. 2023Offline Learning in Markov Games with General Function Approximationcited by 18
  3. 2023Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexitycited by 17
  4. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 16
  5. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  6. 2024Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Modelscited by 16
  7. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  8. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraintscited by 15
  9. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15
  10. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 15
  11. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 14
  12. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  13. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  14. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 13
  15. 2022Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networkscited by 12
  16. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  17. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coveragecited by 12
  18. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
  19. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 11
  20. 2023Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithmscited by 10
  21. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 10
  22. 2026Beyond Pessimism: Offline Learning in KL-regularized Gamescited by 10
  23. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  24. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  25. 2024Learning from Sparse Offline Datasets via Conservative Density Estimationcited by 9
  26. 2025A Unified Theoretical Analysis of Private and Robust Offline Alignment: from RLHF to DPOcited by 8
  27. 2023A Survey on Offline Model-Based Reinforcement Learningcited by 7
  28. 2024Latent Safety-Constrained Policy Approach for Safe Offline Reinforcement Learningcited by 7
  29. 2023Optimal Sample Complexity of Stable Discounted Markov Decision Processescited by 6
  30. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 6
  31. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  32. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 6
  33. 2026Offline Two-Player Zero-Sum Markov Games with KL Regularizationcited by 6
  34. 2022A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDPcited by 5
  35. 2022Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexitycited by 5
  36. 2023Provably Efficient Offline Goal-Conditioned Reinforcement Learning with General Function Approximation and Single-Policy Concentrabilitycited by 5
  37. 2025Offline Learning for Combinatorial Multi-armed Banditscited by 5
  38. 2025Recursive Entropic Risk Optimization in Discounted MDPs: Sample Complexity Bounds with a Generative Modelcited by 5

50 most cited of 83 All 83 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  2. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability
  3. 2021Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning
  4. 2021Nearly Horizon-Free Offline Reinforcement Learning
  5. 2023Offline Reinforcement Learning with Additional Covering Distributions
  6. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?
  7. 2026On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coverage
  8. 2023Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Data