mlsanityData to 7 Oct 2026

Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning

arXiv 2303.02783 ↗First posted 5 Mar 2023cs.LG cs.AI stat.MLcited by 44

Not on the map. Why?

Abstract (arXiv)

We consider the problem of learning a control policy that is robust against the parameter mismatches between the training environment and testing environment. We formulate this as a distributionally robust reinforcement learning (DR-RL) problem where the objective is to learn the policy which maximizes the value function against the worst possible stochastic model of the environment in an uncertainty set. We focus on the tabular episodic learning setting where the algorithm has access to a generative model of the nominal (training) environment around which the uncertainty set is defined. We propose the Robust Phased Value Learning (RPVL) algorithm to solve this problem for the uncertainty sets specified by four different divergences: total variation, chi-square, Kullback-Leibler, and Wasserstein. We show that our algorithm achieves tildeO(|S||A| H5) sample complexity, which is uniformly better than the existing results by a factor of |S|, where |S| is number of states, |A| is the number of actions, and H is the horizon length. We also provide the first-ever sample complexity result for the Wasserstein uncertainty set. Finally, we demonstrate the performance of our algorithm using simulation experiments.

Key facts. Cited by 44 papers in the map (data through 7 Oct 2026). Builds on 26 of its 47 references that are in the map. First posted on arXiv 5 Mar 2023.

Builds on

26 of 47 references.

References · 26

  1. 2017Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real Worldcited by 1,401
  2. 2017Sim-to-Real Transfer of Robotic Control with Dynamics Randomizationcited by 616
  3. 2017Robust Adversarial Reinforcement Learningcited by 439
  4. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 334
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  6. 2016Distributionally Robust Stochastic Optimization with Wasserstein Distancecited by 182
  7. 2021Robust Reinforcement Learning on State Observations with Learned Optimal Adversarycited by 133
  8. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  9. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  10. 2018The Limits and Potentials of Deep Learning for Roboticscited by 104
  11. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  12. 2022Robust Reinforcement Learning using Offline Datacited by 95
14 more
  1. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
  2. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  3. 2019Robust Reinforcement Learning for Continuous Control with Model Misspecificationcited by 76
  4. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  5. 2020Robust Reinforcement Learning using Adversarial Populationscited by 64
  6. 2017Reinforcement Learning under Model Mismatchcited by 52
  7. 2021Distributionally Robust Learningcited by 44
  8. 2018Soft-Robust Actor-Critic Policy-Gradientcited by 37
  9. 2019Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPscited by 37
  10. 2015Distributionally Robust Counterpart in Markov Decision Processescited by 32
  11. 2019A Bayesian Approach to Robust Reinforcement Learningcited by 32
  12. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  13. 2014Empirical Q-Value Iterationcited by 7
  14. 2013Empirical Dynamic Programmingcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 13; 2024: 11; 2025: 13; 2026: 7.

44 papers.

Sort:

By area:

  1. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  2. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  3. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 35
  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. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  7. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  8. 2023On the Foundation of Distributionally Robust Reinforcement Learningcited by 18
  9. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  10. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 17
  11. 2025Robust LLM Alignment via Distributionally Robust Direct Preference Optimizationcited by 17
  12. 2023Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexitycited by 16
32 more
  1. 2024Distributionally Robust Constrained Reinforcement Learning under Strong Dualitycited by 15
  2. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 15
  3. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coveragecited by 12
  4. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
  5. 2023Wasserstein Distributionally Robust Policy Evaluation and Learning for Contextual Banditscited by 9
  6. 2024Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularizationcited by 8
  7. 2023Bring Your Own (Non-Robust) Algorithm to Solve Robust MDPs by Estimating The Worst Kernelcited by 6
  8. 2025Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guaranteescited by 6
  9. 2025Linear Mixture Distributionally Robust Markov Decision Processescited by 5
  10. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  11. 2025Tail-Risk-Safe Monte Carlo Tree Search under PAC-Level Guaranteescited by 4
  12. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
  13. 2024Tractable Equilibrium Computation in Markov Games through Risk Aversioncited by 3
  14. 2025Hybrid Cross-domain Robust Reinforcement Learningcited by 3
  15. 2025DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertaintycited by 3
  16. 2023Efficient Action Robust Reinforcement Learning with Probabilistic Policy Execution Uncertaintycited by 2
  17. 2024Model-Free Robust φ-Divergence Reinforcement Learning Using Both Offline and Online Datacited by 2
  18. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 2
  19. 2025Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learningcited by 2
  20. 2025Near-Optimal Sample Complexities of Divergence-based S-rectangular Distributionally Robust Reinforcement Learningcited by 1
  21. 2025Provably Efficient Sample Complexity for Robust CMDPcited by 1
  22. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 1
  23. 2023Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbationscited by 0
  24. 2024Learning Optimal Distributionally Robust Stochastic Control in Continuous State Spacescited by 0
  25. 2025Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximationcited by 0
  26. 2026Distributionally Robust Cooperative Multi-Agent Reinforcement Learning via Robust Value Factorizationcited by 0
  27. 2026Data-driven robust Markov decision processes on Borel spaces: performance guarantees via an axiomatic approachcited by 0
  28. 2026Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guaranteescited by 0
  29. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0
  30. 2026Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RLcited by 0
  31. 2026Stationary Robust Mean-Field Games under Model Mismatchescited by 0
  32. 2026Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processescited by 0