# Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning

arXiv: https://arxiv.org/abs/2303.02783 · HTML: https://mlsanity.com/paper/2303.02783/

## Key facts

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

## Builds on (most cited first, 26 of 26)

- [Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World](https://mlsanity.com/paper/1703.06907/) (2017)
- [Sim-to-Real Transfer of Robotic Control with Dynamics Randomization](https://mlsanity.com/paper/1710.06537/) (2017)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [Robust Reinforcement Learning on State Observations with Learned Optimal Adversary](https://mlsanity.com/paper/2101.08452/) (2021)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [The Limits and Potentials of Deep Learning for Robotics](https://mlsanity.com/paper/1804.06557/) (2018)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [Robust Reinforcement Learning for Continuous Control with Model Misspecification](https://mlsanity.com/paper/1906.07516/) (2019)
- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [Robust Reinforcement Learning using Adversarial Populations](https://mlsanity.com/paper/2008.01825/) (2020)
- [Reinforcement Learning under Model Mismatch](https://mlsanity.com/paper/1706.04711/) (2017)
- [Distributionally Robust Learning](https://mlsanity.com/paper/2108.08993/) (2021)
- [Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs](https://mlsanity.com/paper/1902.07605/) (2019)
- [Soft-Robust Actor-Critic Policy-Gradient](https://mlsanity.com/paper/1803.04848/) (2018)
- [A Bayesian Approach to Robust Reinforcement Learning](https://mlsanity.com/paper/1905.08188/) (2019)
- [Distributionally Robust Counterpart in Markov Decision Processes](https://mlsanity.com/paper/1501.07418/) (2015)
- [Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics](https://mlsanity.com/paper/2105.03863/) (2021)
- [Empirical Q-Value Iteration](https://mlsanity.com/paper/1412.0180/) (2014)
- [Empirical Dynamic Programming](https://mlsanity.com/paper/1311.5918/) (2013)

## Built on by (most cited first, 30 of 44)

- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [Natural Actor-Critic for Robust Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2307.08875/) (2023)
- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024)
- [Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlation](https://mlsanity.com/paper/2307.07907/) (2023)
- [Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximation](https://mlsanity.com/paper/2402.15399/) (2024)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [On the Foundation of Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2311.09018/) (2023)
- [Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2403.09621/) (2024)
- [Robust LLM Alignment via Distributionally Robust Direct Preference Optimization](https://mlsanity.com/paper/2502.01930/) (2025)
- [Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity](https://mlsanity.com/paper/2306.11626/) (2023)
- [Distributionally Robust Model-based Reinforcement Learning with Large State Spaces](https://mlsanity.com/paper/2309.02236/) (2023)
- [Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning](https://mlsanity.com/paper/2409.20521/) (2024)
- [Distributionally Robust Constrained Reinforcement Learning under Strong Duality](https://mlsanity.com/paper/2406.15788/) (2024)
- [Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes](https://mlsanity.com/paper/2403.12946/) (2024)
- [Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage](https://mlsanity.com/paper/2310.18434/) (2023)
- [Wasserstein Distributionally Robust Policy Evaluation and Learning for Contextual Bandits](https://mlsanity.com/paper/2309.08748/) (2023)
- [Bring Your Own (Non-Robust) Algorithm to Solve Robust MDPs by Estimating The Worst Kernel](https://mlsanity.com/paper/2306.05859/) (2023)
- [Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization](https://mlsanity.com/paper/2411.18612/) (2024)
- [Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees](https://mlsanity.com/paper/2505.19238/) (2025)
- [ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2508.03768/) (2025)
- [Linear Mixture Distributionally Robust Markov Decision Processes](https://mlsanity.com/paper/2505.18044/) (2025)
- [Model-Free Robust φ-Divergence Reinforcement Learning Using Both Offline and Online Data](https://mlsanity.com/paper/2405.05468/) (2024)
- [Tractable Equilibrium Computation in Markov Games through Risk Aversion](https://mlsanity.com/paper/2406.14156/) (2024)
- [Tail-Risk-Safe Monte Carlo Tree Search under PAC-Level Guarantees](https://mlsanity.com/paper/2508.05441/) (2025)
- [Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach](https://mlsanity.com/paper/2305.13289/) (2023)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Hybrid Cross-domain Robust Reinforcement Learning](https://mlsanity.com/paper/2505.23003/) (2025)
- [DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertainty](https://mlsanity.com/paper/2506.12622/) (2025)
- [Efficient Action Robust Reinforcement Learning with Probabilistic Policy Execution Uncertainty](https://mlsanity.com/paper/2307.07666/) (2023)

## 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.