Robust Markov Decision Processes: An Introduction Using Convex Optimization and Game Theory
math.OC
Submitted: 2026-11-04
Updated: 2026-11-04
Project page: https://joonkwon.github.io/rl-ups/reinforcement-learning-lecture-notes.pdf
License: http://creativecommons.org/licenses/by/4.0/
The gist: The goal of these notes is to provide a unified and rigorous introduction to robust sequential decision-making.
Terminology
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.
Sources
- Policy iteration for perfect information stochastic mean payoff games with bounded first return times is strongly polynomial
- Soft-Robust Algorithms for Batch Reinforcement Learning
- A tutorial on Zero-sum Stochastic Games
- Risk-averse formulations of Stochastic Optimal Control and Markov Decision Processes
- On the Foundation of Distributionally Robust Reinforcement Learning
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise