# Sequential Decision-Making under Uncertainty: A Robust MDPs review

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 49 of its 164 references that are in the map.
- First posted on arXiv 1 Apr 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Offline Reinforcement Learning with Fisher Divergence Critic Regularization](https://mlsanity.com/paper/2103.08050/) (2021)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [A Study on Overfitting in Deep Reinforcement Learning](https://mlsanity.com/paper/1804.06893/) (2018)
- [Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach](https://mlsanity.com/paper/1506.02188/) (2015)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [Safe Policy Improvement with Baseline Bootstrapping](https://mlsanity.com/paper/1712.06924/) (2017)
- [Safe Reinforcement Learning in Constrained Markov Decision Processes](https://mlsanity.com/paper/2008.06626/) (2020)
- [The Uncertainty Bellman Equation and Exploration](https://mlsanity.com/paper/1709.05380/) (2017)
- [Regularization via Mass Transportation](https://mlsanity.com/paper/1710.10016/) (2017)
- [Wasserstein Robust Reinforcement Learning](https://mlsanity.com/paper/1907.13196/) (2019)
- [Safe Policy Improvement by Minimizing Robust Baseline Regret](https://mlsanity.com/paper/1607.03842/) (2016)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [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)
- [Distributional Robustness and Regularization in Reinforcement Learning](https://mlsanity.com/paper/2003.02894/) (2020)
- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)
- [A Bayesian Approach to Robust Reinforcement Learning](https://mlsanity.com/paper/1905.08188/) (2019)
- [Distributionally Robust Counterpart in Markov Decision Processes](https://mlsanity.com/paper/1501.07418/) (2015)
- [Policy Gradient for Rectangular Robust Markov Decision Processes](https://mlsanity.com/paper/2301.13589/) (2023)
- [Wasserstein Distributionally Robust Stochastic Control: A Data-Driven Approach](https://mlsanity.com/paper/1812.09808/) (2018)
- [Hindsight Learning for MDPs with Exogenous Inputs](https://mlsanity.com/paper/2207.06272/) (2022)
- [Scalable First-Order Methods for Robust MDPs](https://mlsanity.com/paper/2005.05434/) (2020)
- [Robust Reinforcement Learning with Wasserstein Constraint](https://mlsanity.com/paper/2006.00945/) (2020)
- [On the Convergence and Optimality of Policy Gradient for Markov Coherent Risk](https://mlsanity.com/paper/2103.02827/) (2021)
- [Efficient Policy Iteration for Robust Markov Decision Processes via Regularization](https://mlsanity.com/paper/2205.14327/) (2022)
- [Unbiased Multilevel Monte Carlo: Stochastic Optimization, Steady-state Simulation, Quantiles, and Other Applications](https://mlsanity.com/paper/1904.09929/) (2019)

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

- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Robustness Analysis of POMDP Policies to Observation Perturbations](https://mlsanity.com/paper/2604.21256/) (2026)

## Abstract (arXiv)

Fueled by advances in both robust optimization theory and reinforcement learning (RL), robust Markov Decision Processes (RMDPs) have garnered increasing attention due to their powerful capability for sequential decision-making under uncertainty. In this paper, we provide a comprehensive overview of the theoretical foundations and recent developments in RMDPs, with a particular emphasis on ambiguity modeling. We examine the ``rectangular assumption", a key condition ensuring computational tractability in RMDPs but often resulting in overly conservative policies. Three widely used rectangular forms are summarized, and a novel proof is provided for the NP-hardness of non-rectangular RMDPs. We categorize RMDP formulation approaches into parametric, moment-based, and discrepancy-based models, analyzing the trade-offs associated with each representation. Beyond the traditional scope of RMDPs, we also explore recent efforts to relax rectangular assumptions and highlight emerging trends within the RMDP research community. These developments contribute to more practical and flexible modeling frameworks, complementing the classical RMDP results. Relaxing rectangular assumptions tailored to operations management is a promising area for future research, and there are also opportunities for further advances in developing fast algorithms and provably robust RL algorithms.