mlsanityData to 14 Oct 2026

The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model

arXiv 2305.16589 ↗First posted 26 May 2023cs.LG cs.IT math.ITcited by 52

Not on the map. Why?

Cited by 29 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

This paper investigates model robustness in reinforcement learning (RL) to reduce the sim-to-real gap in practice. We adopt the framework of distributionally robust Markov decision processes (RMDPs), aimed at learning a policy that optimizes the worst-case performance when the deployed environment falls within a prescribed uncertainty set around the nominal MDP. Despite recent efforts, the sample complexity of RMDPs remained mostly unsettled regardless of the uncertainty set in use. It was unclear if distributional robustness bears any statistical consequences when benchmarked against standard RL. Assuming access to a generative model that draws samples based on the nominal MDP, we provide a near-optimal characterization of the sample complexity of RMDPs when the uncertainty set is specified via either the total variation (TV) distance or chi-squared divergence. The algorithm studied here is a model-based method called distributionally robust value iteration, which is shown to be near-optimal for the full range of uncertainty levels. Somewhat surprisingly, our results uncover that RMDPs are not necessarily easier or harder to learn than standard MDPs. The statistical consequence incurred by the robustness requirement depends heavily on the size and shape of the uncertainty set: in the case w.r.t.~the TV distance, the minimax sample complexity of RMDPs is always smaller than that of standard MDPs; in the case w.r.t.~the chi-squared divergence, the sample complexity of RMDPs far exceeds the standard MDP counterpart.

Key facts. Cited by 52 papers in the map (data through 14 Oct 2026). Builds on 54 of its 94 references that are in the map. First posted on arXiv 26 May 2023.

Builds on

54 of 94 references.

References · 54

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2019Fine-Tuning Language Models from Human Preferencescited by 2,150
  3. 2018Is Q-learning Provably Efficient?cited by 487
  4. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
  5. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 335
  6. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  7. 2020Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observationscited by 238
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2019Action Robust Reinforcement Learning and Applications in Continuous Controlcited by 174
  10. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
  11. 2021Robust Reinforcement Learning on State Observations with Learned Optimal Adversarycited by 135
  12. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
38 more
  1. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  2. 2021OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimationcited by 121
  3. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  4. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 96
  5. 2022Robust Reinforcement Learning using Offline Datacited by 96
  6. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  7. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
  8. 2013Data-Driven Robust Optimizationcited by 85
  9. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
  10. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 83
  11. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 83
  12. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  13. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  14. 2018Benchmarking Reinforcement Learning Algorithms on Real-World Robotscited by 65
  15. 2020Q-learning with Logarithmic Regretcited by 60
  16. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  17. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 55
  18. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  19. 2017Reinforcement Learning under Model Mismatchcited by 52
  20. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  21. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 50
  22. 2020Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionalitycited by 49
  23. 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
  24. 2019Distributionally Robust Reinforcement Learningcited by 42
  25. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
  26. 2020Distributional Robustness and Regularization in Reinforcement Learningcited by 40
  27. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 36
  28. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 36
  29. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 32
  30. 2020Robustifying Reinforcement Learning Agents via Action Space Adversarial Trainingcited by 30
  31. 2021Medical Dead-ends and Learning to Identify High-risk States and Treatmentscited by 28
  32. 2022What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?cited by 22
  33. 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 22
  34. 2020Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopescited by 19
  35. 2022Online Policy Optimization for Robust MDPcited by 19
  36. 2023Single-Trajectory Distributionally Robust Reinforcement Learningcited by 16
  37. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  38. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 6; 2024: 19; 2025: 16; 2026: 11.

52 papers.

Sort:

By area:

  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  2. 2026Maximum Likelihood Reinforcement Learningcited by 36
  3. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 26
  4. 2023Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlationcited by 25
  5. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  6. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 25
  7. 2023On the Foundation of Distributionally Robust Reinforcement Learningcited by 18
  8. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 18
  9. 2023Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexitycited by 17
  10. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  11. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 16
  12. 2024Distributionally Robust Constrained Reinforcement Learning under Strong Dualitycited by 15
38 more
  1. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 14
  2. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  3. 2024Model-Free Robust Reinforcement Learning with Sample Complexity Analysiscited by 9
  4. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  5. 2024Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularizationcited by 8
  6. 2024Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorizationcited by 6
  7. 2025Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guaranteescited by 6
  8. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 6
  9. 2024Roping in Uncertainty: Robustness and Regularization in Markov Gamescited by 5
  10. 2025Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Modelcited by 5
  11. 2025Linear Mixture Distributionally Robust Markov Decision Processescited by 5
  12. 2024Model-Free Robust φ-Divergence Reinforcement Learning Using Both Offline and Online Datacited by 4
  13. 2024Tractable Equilibrium Computation in Markov Games through Risk Aversioncited by 4
  14. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 3
  15. 2025Robust Policy Expansion for Offline-to-Online RL under Diverse Data Corruptioncited by 3
  16. 2023Efficient Action Robust Reinforcement Learning with Probabilistic Policy Execution Uncertaintycited by 2
  17. 2024Sequential Decision-Making under Uncertainty: A Robust MDPs reviewcited by 2
  18. 2024RRLS : Robust Reinforcement Learning Suitecited by 2
  19. 2025Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learningcited by 2
  20. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  21. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 2
  22. 2024Bootstrapping Expectiles in Reinforcement Learningcited by 1
  23. 2025Near-Optimal Sample Complexities of Divergence-based S-rectangular Distributionally Robust Reinforcement Learningcited by 1
  24. 2025Optimism as Risk-Seeking in Multi-Agent Reinforcement Learningcited by 1
  25. 2025Provably Efficient Sample Complexity for Robust CMDPcited by 1
  26. 2025Distributionally Robust Online Markov Game with Linear Function Approximationcited by 1
  27. 2025Perturbation-mitigated USV Navigation with Distributionally Robust Reinforcement Learningcited by 1
  28. 2024Learning Optimal Distributionally Robust Stochastic Control in Continuous State Spacescited by 0
  29. 2025Temporal Robustness in Discrete Time Linear Dynamical Systemscited by 0
  30. 2025Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximationcited by 0
  31. 2026Distributionally Robust Cooperative Multi-Agent Reinforcement Learning via Robust Value Factorizationcited by 0
  32. 2026Robust Transfer Learning with Side Informationcited by 0
  33. 2026Data-driven robust Markov decision processes on Borel spaces: performance guarantees via an axiomatic approachcited by 0
  34. 2026Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guaranteescited by 0
  35. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0
  36. 2026Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RLcited by 0
  37. 2026Stationary Robust Mean-Field Games under Model Mismatchescited by 0
  38. 2026Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attackscited by 0

50 most cited of 52 All 52 (JSON)