# Twice regularized MDPs and the equivalence between robustness and regularization

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 55 references that are in the map.
- First posted on arXiv 12 Oct 2021.

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

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Maximum Entropy RL (Provably) Solves Some Robust RL Problems](https://mlsanity.com/paper/2103.06257/) (2021)
- [Action Robust Reinforcement Learning and Applications in Continuous Control](https://mlsanity.com/paper/1901.09184/) (2019)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Reinforcement Learning via Fenchel-Rockafellar Duality](https://mlsanity.com/paper/2001.01866/) (2020)
- [Differentiable Dynamic Programming for Structured Prediction and Attention](https://mlsanity.com/paper/1802.03676/) (2018)
- [Reinforcement Learning under Model Mismatch](https://mlsanity.com/paper/1706.04711/) (2017)
- [Distributional Robustness and Regularization in Reinforcement Learning](https://mlsanity.com/paper/2003.02894/) (2020)
- [Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learning](https://mlsanity.com/paper/1709.06293/) (2017)
- [Soft-Robust Actor-Critic Policy-Gradient](https://mlsanity.com/paper/1803.04848/) (2018)
- [Regularized Policies are Reward Robust](https://mlsanity.com/paper/2101.07012/) (2021)
- [Scalable First-Order Methods for Robust MDPs](https://mlsanity.com/paper/2005.05434/) (2020)
- [Learning Robust Options](https://mlsanity.com/paper/1802.03236/) (2018)

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

- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Correlated Proxies: A New Definition and Improved Mitigation for Reward Hacking](https://mlsanity.com/paper/2403.03185/) (2024)
- [Evaluation of Best-of-N Sampling Strategies for Language Model Alignment](https://mlsanity.com/paper/2502.12668/) (2025)
- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [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)
- [Maximum entropy GFlowNets with soft Q-learning](https://mlsanity.com/paper/2312.14331/) (2023)
- [Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2301.00858/) (2023)
- [Towards Minimax Optimality of Model-based Robust Reinforcement Learning](https://mlsanity.com/paper/2302.05372/) (2023)
- [Your Policy Regularizer is Secretly an Adversary](https://mlsanity.com/paper/2203.12592/) (2022)
- [Efficient Policy Iteration for Robust Markov Decision Processes via Regularization](https://mlsanity.com/paper/2205.14327/) (2022)
- [Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity](https://mlsanity.com/paper/2306.11626/) (2023)
- [Distributionally Robust Constrained Reinforcement Learning under Strong Duality](https://mlsanity.com/paper/2406.15788/) (2024)
- [Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity](https://mlsanity.com/paper/2201.09457/) (2022)
- [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)
- [Robust Reinforcement Learning in Continuous Control Tasks with Uncertainty Set Regularization](https://mlsanity.com/paper/2207.02016/) (2022)
- [Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies](https://mlsanity.com/paper/2410.03968/) (2024)
- [An Efficient Solution to s-Rectangular Robust Markov Decision Processes](https://mlsanity.com/paper/2301.13642/) (2023)
- [Robust Multi-Agent Reinforcement Learning by Mutual Information Regularization](https://mlsanity.com/paper/2310.09833/) (2023)
- [State Entropy Regularization for Robust Reinforcement Learning](https://mlsanity.com/paper/2506.07085/) (2025)
- [Roping in Uncertainty: Robustness and Regularization in Markov Games](https://mlsanity.com/paper/2406.08847/) (2024)
- [RASR: Risk-Averse Soft-Robust MDPs with EVaR and Entropic Risk](https://mlsanity.com/paper/2209.04067/) (2022)
- [Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality](https://mlsanity.com/paper/2508.17448/) (2025)
- [Adversarial Diffusion for Robust Reinforcement Learning](https://mlsanity.com/paper/2509.23846/) (2025)
- [Evidence on the Regularisation Properties of Maximum-Entropy Reinforcement Learning](https://mlsanity.com/paper/2501.17115/) (2025)
- [Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes](https://mlsanity.com/paper/2502.09432/) (2025)

## Abstract (arXiv)

Robust Markov decision processes (MDPs) aim to handle changing or partially known system dynamics. To solve them, one typically resorts to robust optimization methods. However, this significantly increases computational complexity and limits scalability in both learning and planning. On the other hand, regularized MDPs show more stability in policy learning without impairing time complexity. Yet, they generally do not encompass uncertainty in the model dynamics. In this work, we aim to learn robust MDPs using regularization. We first show that regularized MDPs are a particular instance of robust MDPs with uncertain reward. We thus establish that policy iteration on reward-robust MDPs can have the same time complexity as on regularized MDPs. We further extend this relationship to MDPs with uncertain transitions: this leads to a regularization term with an additional dependence on the value function. We finally generalize regularized MDPs to twice regularized MDPs (R2 MDPs), i.e., MDPs with textitboth value and policy regularization. The corresponding Bellman operators enable developing policy iteration schemes with convergence and robustness guarantees. It also reduces planning and learning in robust MDPs to regularized MDPs.