# Scalable First-Order Methods for Robust MDPs

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

## Key facts

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

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

- [Twice regularized MDPs and the equivalence between robustness and regularization](https://mlsanity.com/paper/2110.06267/) (2021)
- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [Natural Actor-Critic for Robust Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2307.08875/) (2023)
- [First-order Policy Optimization for Robust Markov Decision Process](https://mlsanity.com/paper/2209.10579/) (2022)
- [Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage](https://mlsanity.com/paper/2310.18434/) (2023)
- [Robust Reinforcement Learning with Distributional Risk-averse formulation](https://mlsanity.com/paper/2206.06841/) (2022)
- [On the convex formulations of robust Markov decision processes](https://mlsanity.com/paper/2209.10187/) (2022)
- [Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form](https://mlsanity.com/paper/2408.16286/) (2024)
- [Bring Your Own (Non-Robust) Algorithm to Solve Robust MDPs by Estimating The Worst Kernel](https://mlsanity.com/paper/2306.05859/) (2023)
- [Robust Reinforcement Learning in Continuous Control Tasks with Uncertainty Set Regularization](https://mlsanity.com/paper/2207.02016/) (2022)
- [Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving](https://mlsanity.com/paper/2105.13203/) (2021)
- [Robust Finite-Memory Policy Gradients for Hidden-Model POMDPs](https://mlsanity.com/paper/2505.09518/) (2025)
- [Solving optimization problems with Blackwell approachability](https://mlsanity.com/paper/2202.12277/) (2022)
- [A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes](https://mlsanity.com/paper/2406.00274/) (2024)
- [Operator Splitting for Convex Constrained Markov Decision Processes](https://mlsanity.com/paper/2412.14002/) (2024)
- [Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality](https://mlsanity.com/paper/2508.17448/) (2025)
- [Sequential Decision-Making under Uncertainty: A Robust MDPs review](https://mlsanity.com/paper/2404.00940/) (2024)
- [RRLS : Robust Reinforcement Learning Suite](https://mlsanity.com/paper/2406.08406/) (2024)
- [Solving robust MDPs as a sequence of static RL problems](https://mlsanity.com/paper/2410.06212/) (2024)
- [Robust Phi-Divergence MDPs](https://mlsanity.com/paper/2205.14202/) (2022)
- [Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization](https://mlsanity.com/paper/2303.06654/) (2023)
- [Robust General Utility for Reinforcement Learning](https://mlsanity.com/paper/2608.03562/) (2026)
- [ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertainty](https://mlsanity.com/paper/2510.11899/) (2025)
- [A Theoretical Analysis of State Similarity Between Markov Decision Processes](https://mlsanity.com/paper/2512.17265/) (2025)
- [Entropy Regularization Improves Policy Robustness in Continuous-Time Reinforcement Learning](https://mlsanity.com/paper/2607.03168/) (2026)

## Abstract (arXiv)

Robust Markov Decision Processes (MDPs) are a powerful framework for modeling sequential decision-making problems with model uncertainty. This paper proposes the first first-order framework for solving robust MDPs. Our algorithm interleaves primal-dual first-order updates with approximate Value Iteration updates. By carefully controlling the tradeoff between the accuracy and cost of Value Iteration updates, we achieve an ergodic convergence rate of O left( A2 S3log(S)log(ε-1) ε-1 right) for the best choice of parameters on ellipsoidal and Kullback-Leibler s-rectangular uncertainty sets, where S and A is the number of states and actions, respectively. Our dependence on the number of states and actions is significantly better (by a factor of O(A1.5S1.5)) than that of pure Value Iteration algorithms. In numerical experiments on ellipsoidal uncertainty sets we show that our algorithm is significantly more scalable than state-of-the-art approaches. Our framework is also the first one to solve robust MDPs with s-rectangular KL uncertainty sets.