mlsanityData to 7 Oct 2026

Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity

arXiv 2208.05767 ↗First posted 11 Aug 2022cs.LG stat.MLcited by 85

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

Abstract (arXiv)

This paper concerns the central issues of model robustness and sample efficiency in offline reinforcement learning (RL), which aims to learn to perform decision making from history data without active exploration. Due to uncertainties and variabilities of the environment, it is critical to learn a robust policy -- with as few samples as possible -- that performs well even when the deployed environment deviates from the nominal one used to collect the history dataset. We consider a distributionally robust formulation of offline RL, focusing on tabular robust Markov decision processes with an uncertainty set specified by the Kullback-Leibler divergence in both finite-horizon and infinite-horizon settings. To combat with sample scarcity, a model-based algorithm that combines distributionally robust value iteration with the principle of pessimism in the face of uncertainty is proposed, by penalizing the robust value estimates with a carefully designed data-driven penalty term. Under a mild and tailored assumption of the history dataset that measures distribution shift without requiring full coverage of the state-action space, we establish the finite-sample complexity of the proposed algorithms. We further develop an information-theoretic lower bound, which suggests that learning RMDPs is at least as hard as the standard MDPs when the uncertainty level is sufficient small, and corroborates the tightness of our upper bound up to polynomial factors of the (effective) horizon length for a range of uncertainty levels. To the best our knowledge, this provides the first provably near-optimal robust offline RL algorithm that learns under model uncertainty and partial coverage.

Key facts. Cited by 85 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 26 of its 51 references that are in the map. First posted on arXiv 11 Aug 2022.

Builds on

26 of 51 references.

Closest ancestors · 9

Same direction, newest first

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  2. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity28 Feb
  3. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  4. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings13 May
  5. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  6. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  7. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  8. 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
  9. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 17

  1. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 334
  2. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  3. 2020Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observationscited by 235
  4. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  5. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  6. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  7. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  8. 2013Data-Driven Robust Optimizationcited by 84
  9. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  10. 2017Reinforcement Learning under Model Mismatchcited by 52
  11. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 49
  12. 2020Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionalitycited by 49
5 more
  1. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  2. 2019Distributionally Robust Reinforcement Learningcited by 40
  3. 2020Distributional Robustness and Regularization in Reinforcement Learningcited by 39
  4. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  5. 2018Robust Markov Decision Process: Beyond Rectangularitycited by 24

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 24; 2024: 21; 2025: 29; 2026: 9.

85 papers.

Sort:

By area:

  1. 2024Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizercited by 109
  2. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  3. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  4. 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
  5. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 35
  6. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 35
  7. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  8. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  9. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 28
  10. 2023Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlationcited by 25
  11. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  12. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
38 more
  1. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  2. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  3. 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 21
  4. 2023Survival Instinct in Offline Reinforcement Learningcited by 20
  5. 2023On the Foundation of Distributionally Robust Reinforcement Learningcited by 18
  6. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  7. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 17
  8. 2025Robust LLM Alignment via Distributionally Robust Direct Preference Optimizationcited by 17
  9. 2023Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexitycited by 16
  10. 2023Single-Trajectory Distributionally Robust Reinforcement Learningcited by 15
  11. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  12. 2024Distributionally Robust Constrained Reinforcement Learning under Strong Dualitycited by 15
  13. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 15
  14. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learningcited by 13
  15. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coveragecited by 12
  16. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
  17. 2023Robust Markov Decision Processes without Model Estimationcited by 11
  18. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
  19. 2024Model-Free Robust Reinforcement Learning with Sample Complexity Analysiscited by 9
  20. 2024Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularizationcited by 8
  21. 2025MOBODY: Model Based Off-Dynamics Offline Reinforcement Learningcited by 8
  22. 2024Tackling Data Corruption in Offline Reinforcement Learning via Sequence Modelingcited by 7
  23. 2024Latent Safety-Constrained Policy Approach for Safe Offline Reinforcement Learningcited by 7
  24. 2025State-Aware Perturbation Optimization for Robust Deep Reinforcement Learningcited by 7
  25. 2025Robust Deep Reinforcement Learning in Robotics via Adaptive Gradient-Masked Adversarial Attackscited by 7
  26. 2023Bring Your Own (Non-Robust) Algorithm to Solve Robust MDPs by Estimating The Worst Kernelcited by 6
  27. 2024Constrained Reinforcement Learning Under Model Mismatchcited by 6
  28. 2025Wolfpack Adversarial Attack for Robust Multi-Agent Reinforcement Learningcited by 6
  29. 2026Safe Exploration via Policy Priorscited by 6
  30. 2024Roping in Uncertainty: Robustness and Regularization in Markov Gamescited by 5
  31. 2025Linear Mixture Distributionally Robust Markov Decision Processescited by 5
  32. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  33. 2025Dual-Robust Cross-Domain Offline Reinforcement Learning Against Dynamics Shiftscited by 5
  34. 2023DOMAIN: MilDly COnservative Model-BAsed OfflINe Reinforcement Learningcited by 4
  35. 2025Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Modelcited by 4
  36. 2025Tailored Primitive Initialization is the Secret Key to Reinforcement Learningcited by 4
  37. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
  38. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3

50 most cited of 85 All 85 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2024Robust Offline Reinforcement Learning for Non-Markovian Decision Processes
  2. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  3. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  4. 2021DROMO: Distributionally Robust Offline Model-based Policy Optimization
  5. 2021Revisiting Design Choices in Offline Model-Based Reinforcement Learning
  6. 2023Selective Uncertainty Propagation in Offline RL
  7. 2025Long-Horizon Model-Based Offline Reinforcement Learning Without Explicit Conservatism
  8. 2025Semi-pessimistic Reinforcement Learning