# Efficient Policy Iteration for Robust Markov Decision Processes via Regularization

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 31 references that are in the map.
- First posted on arXiv 28 May 2022.

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

- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Maximum Entropy RL (Provably) Solves Some Robust RL Problems](https://mlsanity.com/paper/2103.06257/) (2021)
- [Equivalence Between Policy Gradients and Soft Q-Learning](https://mlsanity.com/paper/1704.06440/) (2017)
- [Assessing Generalization in Deep Reinforcement Learning](https://mlsanity.com/paper/1810.12282/) (2018)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [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)
- [Distributional Robustness and Regularization in Reinforcement Learning](https://mlsanity.com/paper/2003.02894/) (2020)
- [Regularized Policies are Reward Robust](https://mlsanity.com/paper/2101.07012/) (2021)
- [Robust Markov Decision Process: Beyond Rectangularity](https://mlsanity.com/paper/1811.00215/) (2018)
- [Model-Based Reinforcement Learning Exploiting State-Action Equivalence](https://mlsanity.com/paper/1910.04077/) (2019)
- [k*-Nearest Neighbors: From Global to Local](https://mlsanity.com/paper/1701.07266/) (2017)
- [Robust Entropy-regularized Markov Decision Processes](https://mlsanity.com/paper/2112.15364/) (2021)

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

- [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)
- [Policy Gradient for Rectangular Robust Markov Decision Processes](https://mlsanity.com/paper/2301.13589/) (2023)
- [Towards Minimax Optimality of Model-based Robust Reinforcement Learning](https://mlsanity.com/paper/2302.05372/) (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)
- [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)
- [Solving Non-Rectangular Reward-Robust MDPs via Frequency Regularization](https://mlsanity.com/paper/2309.01107/) (2023)
- [Roping in Uncertainty: Robustness and Regularization in Markov Games](https://mlsanity.com/paper/2406.08847/) (2024)
- [Adversarial Diffusion for Robust Reinforcement Learning](https://mlsanity.com/paper/2509.23846/) (2025)
- [Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes](https://mlsanity.com/paper/2404.00099/) (2024)
- [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)
- [Session-Level Dynamic Ad Load Optimization using Offline Robust Reinforcement Learning](https://mlsanity.com/paper/2501.05591/) (2025)
- [Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization](https://mlsanity.com/paper/2303.06654/) (2023)
- [Bootstrapping Expectiles in Reinforcement Learning](https://mlsanity.com/paper/2406.04081/) (2024)
- [Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization](https://mlsanity.com/paper/2602.11387/) (2026)
- [ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertainty](https://mlsanity.com/paper/2510.11899/) (2025)

## Abstract (arXiv)

Robust Markov decision processes (MDPs) provide a general framework to model decision problems where the system dynamics are changing or only partially known. Efficient methods for some textttsa-rectangular robust MDPs exist, using its equivalence with reward regularized MDPs, generalizable to online settings. In comparison to textttsa-rectangular robust MDPs, texttts-rectangular robust MDPs are less restrictive but much more difficult to deal with. Interestingly, recent works have established the equivalence between texttts-rectangular robust MDPs and policy regularized MDPs. But we don't have a clear understanding to exploit this equivalence, to do policy improvement steps to get the optimal value function or policy. We don't have a clear understanding of greedy/optimal policy except it can be stochastic. There exist no methods that can naturally be generalized to model-free settings. We show a clear and explicit equivalence between texttts-rectangular Lp robust MDPs and policy regularized MDPs that resemble very much policy entropy regularized MDPs widely used in practice. Further, we dig into the policy improvement step and concretely derive optimal robust Bellman operators for texttts-rectangular Lp robust MDPs. We find that the greedy/optimal policies in texttts-rectangular Lp robust MDPs are threshold policies that play top k actions whose Q value is greater than some threshold (value), proportional to the (p-1)th power of its advantage. In addition, we show time complexity of (textttsa and texttts-rectangular) Lp robust MDPs is the same as non-robust MDPs up to some log factors. Our work greatly extends the existing understanding of texttts-rectangular robust MDPs and naturally generalizable to online settings.