# Policy Gradient in Robust MDPs with Global Convergence Guarantee

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 79 references that are in the map.
- First posted on arXiv 20 Dec 2022.

## Builds on (most cited first, 30 of 33)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [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)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [Safe Policy Improvement by Minimizing Robust Baseline Regret](https://mlsanity.com/paper/1607.03842/) (2016)
- [Reinforcement Learning under Model Mismatch](https://mlsanity.com/paper/1706.04711/) (2017)
- [On Linear Convergence of Policy Gradient Methods for Finite MDPs](https://mlsanity.com/paper/2007.11120/) (2020)
- [Partial Policy Iteration for L1-Robust Markov Decision Processes](https://mlsanity.com/paper/2006.09484/) (2020)
- [Twice regularized MDPs and the equivalence between robustness and regularization](https://mlsanity.com/paper/2110.06267/) (2021)
- [Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs](https://mlsanity.com/paper/1902.07605/) (2019)
- [Approximate Policy Iteration Schemes: A Comparison](https://mlsanity.com/paper/1405.2878/) (2014)
- [Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances](https://mlsanity.com/paper/2006.08141/) (2020)
- [Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization](https://mlsanity.com/paper/2002.05466/) (2020)
- [First-order Policy Optimization for Robust Markov Decision Process](https://mlsanity.com/paper/2209.10579/) (2022)
- [Scalable First-Order Methods for Robust MDPs](https://mlsanity.com/paper/2005.05434/) (2020)
- [Robust Constrained-MDPs: Soft-Constrained Robust Policy Optimization under Model Uncertainty](https://mlsanity.com/paper/2010.04870/) (2020)

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

- [Policy Gradient for Rectangular Robust Markov Decision Processes](https://mlsanity.com/paper/2301.13589/) (2023)
- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024)
- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity](https://mlsanity.com/paper/2306.11626/) (2023)
- [Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets](https://mlsanity.com/paper/2305.19004/) (2023)
- [Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage](https://mlsanity.com/paper/2310.18434/) (2023)
- [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)
- [Solving Non-Rectangular Reward-Robust MDPs via Frequency Regularization](https://mlsanity.com/paper/2309.01107/) (2023)
- [Constrained Reinforcement Learning Under Model Mismatch](https://mlsanity.com/paper/2405.01327/) (2024)
- [Imprecise Probabilities Meet Partial Observability: Game Semantics for Robust POMDPs](https://mlsanity.com/paper/2405.04941/) (2024)
- [Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees](https://mlsanity.com/paper/2505.19238/) (2025)
- [Roping in Uncertainty: Robustness and Regularization in Markov Games](https://mlsanity.com/paper/2406.08847/) (2024)
- [Robust Finite-Memory Policy Gradients for Hidden-Model POMDPs](https://mlsanity.com/paper/2505.09518/) (2025)
- [A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes](https://mlsanity.com/paper/2406.00274/) (2024)
- [Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality](https://mlsanity.com/paper/2508.17448/) (2025)
- [Stochastic Weakly Convex Optimization Beyond Lipschitz Continuity](https://mlsanity.com/paper/2401.13971/) (2024)
- [Robust Reinforcement Learning with Dynamic Distortion Risk Measures](https://mlsanity.com/paper/2409.10096/) (2024)
- [Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes](https://mlsanity.com/paper/2502.09432/) (2025)
- [Sequential Decision-Making under Uncertainty: A Robust MDPs review](https://mlsanity.com/paper/2404.00940/) (2024)
- [Solving robust MDPs as a sequence of static RL problems](https://mlsanity.com/paper/2410.06212/) (2024)
- [Qualitative Analysis of ω-Regular Objectives on Robust MDPs](https://mlsanity.com/paper/2505.04539/) (2025)
- [Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learning](https://mlsanity.com/paper/2505.18447/) (2025)
- [Achieve Performatively Optimal Policy for Performative Reinforcement Learning](https://mlsanity.com/paper/2510.04430/) (2025)
- [Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluation](https://mlsanity.com/paper/2608.24146/) (2026)
- [Microservice Deployment in Space Computing Power Networks via Robust Reinforcement Learning](https://mlsanity.com/paper/2501.06244/) (2025)
- [Distributionally Robust Deep Q-Learning](https://mlsanity.com/paper/2505.19058/) (2025)
- [Distributionally Robust Self Paced Curriculum Reinforcement Learning](https://mlsanity.com/paper/2511.05694/) (2025)
- [Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs](https://mlsanity.com/paper/2511.05758/) (2025)
- [Provably Efficient Sample Complexity for Robust CMDP](https://mlsanity.com/paper/2511.07486/) (2025)

## Abstract (arXiv)

Robust Markov decision processes (RMDPs) provide a promising framework for computing reliable policies in the face of model errors. Many successful reinforcement learning algorithms build on variations of policy-gradient methods, but adapting these methods to RMDPs has been challenging. As a result, the applicability of RMDPs to large, practical domains remains limited. This paper proposes a new Double-Loop Robust Policy Gradient (DRPG), the first generic policy gradient method for RMDPs. In contrast with prior robust policy gradient algorithms, DRPG monotonically reduces approximation errors to guarantee convergence to a globally optimal policy in tabular RMDPs. We introduce a novel parametric transition kernel and solve the inner loop robust policy via a gradient-based method. Finally, our numerical results demonstrate the utility of our new algorithm and confirm its global convergence properties.