# Robust Markov Decision Process: Beyond Rectangularity

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Nov 2018.

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

- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Bayesian Robust Optimization for Imitation Learning](https://mlsanity.com/paper/2007.12315/) (2020)
- [Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2301.00858/) (2023)
- [Efficient Policy Iteration for Robust Markov Decision Processes via Regularization](https://mlsanity.com/paper/2205.14327/) (2022)
- [Model-Free Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2305.10504/) (2023)
- [Robust Anytime Learning of Markov Decision Processes](https://mlsanity.com/paper/2205.15827/) (2022)
- [Robust Markov Decision Processes without Model Estimation](https://mlsanity.com/paper/2302.01248/) (2023)
- [Decision-Making Under Uncertainty: Beyond Probabilities](https://mlsanity.com/paper/2303.05848/) (2023)
- [Group Distributionally Robust Reinforcement Learning with Hierarchical Latent Variables](https://mlsanity.com/paper/2210.12262/) (2022)
- [Explicit Explore, Exploit, or Escape (E4): near-optimal safety-constrained reinforcement learning in polynomial time](https://mlsanity.com/paper/2111.07395/) (2021)
- [The Geometry of Robust Value Functions](https://mlsanity.com/paper/2201.12929/) (2022)
- [An Efficient Solution to s-Rectangular Robust Markov Decision Processes](https://mlsanity.com/paper/2301.13642/) (2023)
- [Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving](https://mlsanity.com/paper/2105.13203/) (2021)
- [Robustness and risk management via distributional dynamic programming](https://mlsanity.com/paper/2112.15430/) (2021)
- [Solving optimization problems with Blackwell approachability](https://mlsanity.com/paper/2202.12277/) (2022)
- [Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes](https://mlsanity.com/paper/2502.09432/) (2025)
- [Interpretable Machine Learning for Resource Allocation with Application to Ventilator Triage](https://mlsanity.com/paper/2110.10994/) (2021)
- [Time-Constrained Robust MDPs](https://mlsanity.com/paper/2406.08395/) (2024)
- [Robust Optimization for Mitigating Reward Hacking with Correlated Proxies](https://mlsanity.com/paper/2604.12086/) (2026)
- [Robust Phi-Divergence MDPs](https://mlsanity.com/paper/2205.14202/) (2022)
- [Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization](https://mlsanity.com/paper/2303.06654/) (2023)
- [On the Convergence of Modified Policy Iteration in Risk Sensitive Exponential Cost Markov Decision Processes](https://mlsanity.com/paper/2302.03811/) (2023)
- [Percentile Criterion Optimization in Offline Reinforcement Learning](https://mlsanity.com/paper/2404.05055/) (2024)

## Abstract (arXiv)

We consider a robust approach to address uncertainty in model parameters in Markov Decision Processes (MDPs), which are widely used to model dynamic optimization in many applications. Most prior works consider the case where the uncertainty on transitions related to different states is uncoupled and the adversary is allowed to select the worst possible realization for each state unrelated to others, potentially leading to highly conservative solutions. On the other hand, the case of general uncertainty sets is known to be intractable. We consider a factor model for probability transitions where the transition probability is a linear function of a factor matrix that is uncertain and belongs to a factor matrix uncertainty set. This is a fairly general model of uncertainty in probability transitions, allowing the decision maker to model dependence between probability transitions across different states and it is significantly less conservative than prior approaches. We show that under an underlying rectangularity assumption, we can efficiently compute an optimal robust policy under the factor matrix uncertainty model. Furthermore, we show that there is an optimal robust policy that is deterministic, which is of interest from an interpretability standpoint. We also introduce the robust counterpart of important structural results of classical MDPs, including the maximum principle and Blackwell optimality, and we provide a computational study to demonstrate the effectiveness of our approach in mitigating the conservativeness of robust policies.