# Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 67 references that are in the map.
- First posted on arXiv 30 May 2023.

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

- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application](https://mlsanity.com/paper/1309.1541/) (2013)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [Robust Inverse Reinforcement Learning under Transition Dynamics Mismatch](https://mlsanity.com/paper/2007.01174/) (2020)
- [Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning](https://mlsanity.com/paper/2012.12137/) (2020)
- [First-order Policy Optimization for Robust Markov Decision Process](https://mlsanity.com/paper/2209.10579/) (2022)
- [Robust Imitation Learning against Variations in Environment Dynamics](https://mlsanity.com/paper/2206.09314/) (2022)
- [Reinforcement Learning for Quantitative Trading](https://mlsanity.com/paper/2109.13851/) (2021)
- [On the convex formulations of robust Markov decision processes](https://mlsanity.com/paper/2209.10187/) (2022)
- [Robust Learning from Observation with Model Misspecification](https://mlsanity.com/paper/2202.06003/) (2022)
- [Concentration of the Langevin Algorithm's Stationary Distribution](https://mlsanity.com/paper/2212.12629/) (2022)
- [Distributionally Robust Optimization with Markovian Data](https://mlsanity.com/paper/2106.06741/) (2021)
- [Fast Projection Onto Convex Smooth Constraints](https://mlsanity.com/paper/2109.09835/) (2021)
- [Topological Linear System Identification via Moderate Deviations Theory](https://mlsanity.com/paper/2103.03805/) (2021)

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

- [Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity](https://mlsanity.com/paper/2306.11626/) (2023)
- [Linear Mixture Distributionally Robust Markov Decision Processes](https://mlsanity.com/paper/2505.18044/) (2025)
- [A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes](https://mlsanity.com/paper/2406.00274/) (2024)
- [Policy Gradient for Robust Markov Decision Processes](https://mlsanity.com/paper/2410.22114/) (2024)
- [Time-Constrained Robust MDPs](https://mlsanity.com/paper/2406.08395/) (2024)
- [Towards Optimal Offline Reinforcement Learning](https://mlsanity.com/paper/2503.12283/) (2025)
- [Direct Preference Optimization with Rating Information: Practical Algorithms and Provable Gains](https://mlsanity.com/paper/2602.00603/) (2026)
- [Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values](https://mlsanity.com/paper/2603.00945/) (2026)
- [Bootstrapping Expectiles in Reinforcement Learning](https://mlsanity.com/paper/2406.04081/) (2024)
- [Distributionally Robust Deep Q-Learning](https://mlsanity.com/paper/2505.19058/) (2025)
- [Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization](https://mlsanity.com/paper/2602.11387/) (2026)
- [Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RL](https://mlsanity.com/paper/2605.08417/) (2026)
- [Policy Gradient for Continuous-Time Robust Markov Decision Processes](https://mlsanity.com/paper/2606.04335/) (2026)
- [Robust Q-learning for mean-field control under Wasserstein uncertainty in common noise](https://mlsanity.com/paper/2606.20356/) (2026)
- [Entropy Regularization Improves Policy Robustness in Continuous-Time Reinforcement Learning](https://mlsanity.com/paper/2607.03168/) (2026)
- [Bellman-Certified Rounding for Sparse Policy Deployment in MDPs](https://mlsanity.com/paper/2610.00325/) (2026)

## Abstract (arXiv)

We propose policy gradient algorithms for robust infinite-horizon Markov decision processes (MDPs) with non-rectangular uncertainty sets, thereby addressing an open challenge in the robust MDP literature. Indeed, uncertainty sets that display statistical optimality properties and make optimal use of limited data often fail to be rectangular. Unfortunately, the corresponding robust MDPs cannot be solved with dynamic programming techniques and are in fact provably intractable. We first present a randomized projected Langevin dynamics algorithm that solves the robust policy evaluation problem to global optimality but is inefficient. We also propose a deterministic policy gradient method that is efficient but solves the robust policy evaluation problem only approximately, and we prove that the approximation error scales with a new measure of non-rectangularity of the uncertainty set. Finally, we describe an actor-critic algorithm that finds an ε-optimal solution for the robust policy improvement problem in O(1/ε4) iterations. We thus present the first complete solution scheme for robust MDPs with non-rectangular uncertainty sets offering global optimality guarantees. Numerical experiments show that our algorithms compare favorably against state-of-the-art methods.