# First-Order Methods for Wasserstein Distributionally Robust MDP

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Sep 2020.

## Built on by (most cited first, 17 of 17)

- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [Robust Reinforcement Learning with Distributional Risk-averse formulation](https://mlsanity.com/paper/2206.06841/) (2022)
- [Group Distributionally Robust Reinforcement Learning with Hierarchical Latent Variables](https://mlsanity.com/paper/2210.12262/) (2022)
- [Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning](https://mlsanity.com/paper/2502.16816/) (2025)
- [Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving](https://mlsanity.com/paper/2105.13203/) (2021)
- [Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gain](https://mlsanity.com/paper/2509.14203/) (2025)
- [Solving optimization problems with Blackwell approachability](https://mlsanity.com/paper/2202.12277/) (2022)
- [RASR: Risk-Averse Soft-Robust MDPs with EVaR and Entropic Risk](https://mlsanity.com/paper/2209.04067/) (2022)
- [Relative Translation Invariant Wasserstein Distance](https://mlsanity.com/paper/2409.02416/) (2024)
- [Robust Phi-Divergence MDPs](https://mlsanity.com/paper/2205.14202/) (2022)
- [User-Oriented Robust Reinforcement Learning](https://mlsanity.com/paper/2202.07301/) (2022)
- [Risk-Averse MDPs under Reward Ambiguity](https://mlsanity.com/paper/2301.01045/) (2023)
- [On the Convergence of Modified Policy Iteration in Risk Sensitive Exponential Cost Markov Decision Processes](https://mlsanity.com/paper/2302.03811/) (2023)
- [Solving Robust MDPs through No-Regret Dynamics](https://mlsanity.com/paper/2305.19035/) (2023)
- [Percentile Criterion Optimization in Offline Reinforcement Learning](https://mlsanity.com/paper/2404.05055/) (2024)
- [A Distributionally Robust Reinforcement Learning Framework for Constrained Urban EV Dispatch](https://mlsanity.com/paper/2604.25848/) (2026)
- [Policy Gradient Learning for Distributionally Robust Markov Decision Processes under Wasserstein Ambiguity](https://mlsanity.com/paper/2606.27610/) (2026)

## Abstract (arXiv)

Markov decision processes (MDPs) are known to be sensitive to parameter specification. Distributionally robust MDPs alleviate this issue by allowing for ambiguity sets which give a set of possible distributions over parameter sets. The goal is to find an optimal policy with respect to the worst-case parameter distribution. We propose a framework for solving Distributionally robust MDPs via first-order methods, and instantiate it for several types of Wasserstein ambiguity sets. By developing efficient proximal updates, our algorithms achieve a convergence rate of Oleft(NA2.5S3.5log(S)log(ε-1)ε-1.5 right) for the number of kernels N in the support of the nominal distribution, states S, and actions A; this rate varies slightly based on the Wasserstein setup. Our dependence on N,A and S is significantly better than existing methods, which have a complexity of Oleft(N3.5A3.5S4.5log2(ε-1) right). Numerical experiments show that our algorithm is significantly more scalable than state-of-the-art approaches across several domains.