Robust Markov Decision Processes: An Introduction Using Convex Optimization and Game Theory
Abstract
The goal of these notes is to provide a unified and rigorous introduction to robust sequential decision-making. We offer a self-contained introduction to the main results in the field. After a concise introduction to MDPs we introduce robust MDPs with general uncertainty sets, before focusing on rectangular models of uncertainty. We make a significant effort to show connections between robust MDPs and several other popular models for sequential decision-making: MDPs with uncertain rewards, Multi-Objective MDPs and Pareto optimality, MDPs with time-varying uncertain parameters, non-rectangular robust MDPs, stochastic games, distributionally robust MDPs, and risk-averse MDPs. Having all these results in one place, within a single unifying formalism, will hopefully be useful for researchers who want to start working on this topic. The exposition combines operator and fixed point approaches, convex optimization (more specifically, duality in saddle-point problems), and game-theoretic arguments. The latter identifies robust MDPs with a certain type of two-player game; this helps build useful intuition, especially when constructing counterexamples.
Related
- Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
- Worst-Case Bayesian CVaR Regret Bounds for Episodic Markov Decision Processes
- Dynamic Programming for Value-at-Risk Markov Decision Processes in Continuous Spaces
- Percolation Markov Decision Processes
- Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy
BibTeX
@misc{grandclement2026robust,
title = {{Robust Markov Decision Processes: An Introduction Using Convex Optimization and Game Theory}},
author = {Julien Grand-Clément},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06672},
eprint = {2611.06672},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06672},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Robust Markov Decision Processes: An Introduction Using Convex Optimization and Game Theory
AU - Julien Grand-Clément
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06672
UR - https://arxiv.org/abs/2611.06672
AB - The goal of these notes is to provide a unified and rigorous introduction to robust sequential decision-making. We offer a self-contained introduction to the main results in the field. After a concise introduction to MDPs we introduce robust MDPs with general uncertainty sets, before focusing on rectangular models of uncertainty. We make a significant effort to show connections between robust MDPs and several other popular models for sequential decision-making: MDPs with uncertain rewards, Multi-Objective MDPs and Pareto optimality, MDPs with time-varying uncertain parameters, non-rectangular robust MDPs, stochastic games, distributionally robust MDPs, and risk-averse MDPs. Having all these results in one place, within a single unifying formalism, will hopefully be useful for researchers who want to start working on this topic. The exposition combines operator and fixed point approaches, convex optimization (more specifically, duality in saddle-point problems), and game-theoretic arguments. The latter identifies robust MDPs with a certain type of two-player game; this helps build useful intuition, especially when constructing counterexamples.
ER -