# Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 53 of its 121 references that are in the map.
- First posted on arXiv 18 Nov 2024.

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

- [Aleatoric and Epistemic Uncertainty in Machine Learning: An Introduction to Concepts and Methods](https://mlsanity.com/paper/1910.09457/) (2019)
- [The Probabilistic Model Checker Storm](https://mlsanity.com/paper/2002.07080/) (2020)
- [Safe Policy Improvement by Minimizing Robust Baseline Regret](https://mlsanity.com/paper/1607.03842/) (2016)
- [Partial Policy Iteration for L1-Robust Markov Decision Processes](https://mlsanity.com/paper/2006.09484/) (2020)
- [Verification of Markov Decision Processes using Learning Algorithms](https://mlsanity.com/paper/1402.2967/) (2014)
- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games](https://mlsanity.com/paper/1905.04403/) (2019)
- [Policy Gradient for Rectangular Robust Markov Decision Processes](https://mlsanity.com/paper/2301.13589/) (2023)
- [Risk-Averse Bayes-Adaptive Reinforcement Learning](https://mlsanity.com/paper/2102.05762/) (2021)
- [Robust Finite-State Controllers for Uncertain POMDPs](https://mlsanity.com/paper/2009.11459/) (2020)
- [Automated Verification and Synthesis of Stochastic Hybrid Systems: A Survey](https://mlsanity.com/paper/2101.07491/) (2021)
- [On the (In)Tractability of Reinforcement Learning for LTL Objectives](https://mlsanity.com/paper/2111.12679/) (2021)
- [Robust Anytime Learning of Markov Decision Processes](https://mlsanity.com/paper/2205.15827/) (2022)
- [Robust Control for Dynamical Systems With Non-Gaussian Noise via Formal Abstractions](https://mlsanity.com/paper/2301.01526/) (2023)
- [Distributionally Robust Partially Observable Markov Decision Process with Moment-based Ambiguity](https://mlsanity.com/paper/1906.05988/) (2019)
- [Parameter Synthesis for Markov Models: Covering the Parameter Space](https://mlsanity.com/paper/1903.07993/) (2019)
- [Multiple-Environment Markov Decision Processes](https://mlsanity.com/paper/1405.4733/) (2014)
- [StocHy: automated verification and synthesis of stochastic processes](https://mlsanity.com/paper/1901.10287/) (2019)
- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (2023)
- [Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimality](https://mlsanity.com/paper/2312.03618/) (2023)
- [Parameter Synthesis for Markov Models: Faster Than Ever](https://mlsanity.com/paper/1602.05113/) (2016)
- [Safe Policy Improvement for POMDPs via Finite-State Controllers](https://mlsanity.com/paper/2301.04939/) (2023)
- [Probabilities Are Not Enough: Formal Controller Synthesis for Stochastic Dynamical Models with Epistemic Uncertainty](https://mlsanity.com/paper/2210.05989/) (2022)
- [Synthesis in pMDPs: A Tale of 1001 Parameters](https://mlsanity.com/paper/1803.02884/) (2018)
- [The Complexity of Reachability in Parametric Markov Decision Processes](https://mlsanity.com/paper/2009.13128/) (2020)
- [Minimax Regret Optimisation for Robust Planning in Uncertain Markov Decision Processes](https://mlsanity.com/paper/2012.04626/) (2020)
- [Parameter Synthesis in Markov Models: A Gentle Survey](https://mlsanity.com/paper/2207.06801/) (2022)
- [A Practitioner's Guide to MDP Model Checking Algorithms](https://mlsanity.com/paper/2301.10197/) (2023)
- [Solving Long-run Average Reward Robust MDPs via Stochastic Games](https://mlsanity.com/paper/2312.13912/) (2023)
- [Faster Statistical Model Checking for Unbounded Temporal Properties](https://mlsanity.com/paper/1504.05739/) (2015)

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

- [Strongly Polynomial Time Complexity of Policy Iteration for L_∞ Robust MDPs](https://mlsanity.com/paper/2601.23229/) (2026)
- [Deep SPI: Safe Policy Improvement via World Models](https://mlsanity.com/paper/2510.12312/) (2025)
- [Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability](https://mlsanity.com/paper/2510.23744/) (2025)
- [A Theoretical Framework for Graph-based Digital Twins for Supply Chain Management and Optimization](https://mlsanity.com/paper/2504.03692/) (2025)
- [Qualitative Analysis of ω-Regular Objectives on Robust MDPs](https://mlsanity.com/paper/2505.04539/) (2025)
- [Data-Efficient Safe Policy Improvement Using Parametric Structure](https://mlsanity.com/paper/2507.15532/) (2025)
- [Supporting Dynamic Agentic Workloads: How Data and Agents Interact](https://mlsanity.com/paper/2512.09548/) (2025)
- [Robust Shielding for Safe Reinforcement Learning](https://mlsanity.com/paper/2606.00270/) (2026)
- [Best-Effort Policies for Robust Markov Decision Processes](https://mlsanity.com/paper/2508.07790/) (2025)
- [Bayesian Ambiguity Contraction-based Adaptive Robust Markov Decision Processes for Adversarial Surveillance Missions](https://mlsanity.com/paper/2512.01660/) (2025)
- [Robust Parameter Learning for Uncertain MDPs](https://mlsanity.com/paper/2605.01339/) (2026)
- [AI Agents and Hard Choices](https://mlsanity.com/paper/2504.15304/) (2025)
- [Safety Certification is Classification](https://mlsanity.com/paper/2605.06087/) (2026)
- [Property-driven Causal Abstractions for Markov Decision Processes](https://mlsanity.com/paper/2607.26787/) (2026)
- [Adaptive Probabilistic Shielding by Learning MDPs for Safe Reinforcement Learning](https://mlsanity.com/paper/2608.19836/) (2026)
- [Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games](https://mlsanity.com/paper/2608.24986/) (2026)
- [Robust PAC Learning of Concurrent Stochastic Games](https://mlsanity.com/paper/2609.04189/) (2026)
- [Bellman-Certified Rounding for Sparse Policy Deployment in MDPs](https://mlsanity.com/paper/2610.00325/) (2026)

## Abstract (arXiv)

Markov decision processes (MDPs) are a standard model for sequential decision-making problems and are widely used across many scientific areas, including formal methods and artificial intelligence (AI). MDPs do, however, come with the restrictive assumption that the transition probabilities need to be precisely known. Robust MDPs (RMDPs) overcome this assumption by instead defining the transition probabilities to belong to some uncertainty set. We present a gentle survey on RMDPs, providing a tutorial covering their fundamentals. In particular, we discuss RMDP semantics and how to solve them by extending standard MDP methods such as value iteration and policy iteration. We also discuss how RMDPs relate to other models and how they are used in several contexts, including reinforcement learning and abstraction techniques. We conclude with some challenges for future work on RMDPs.