Efficient Algorithms for Robust Markov Decision Processes with $s$-Rectangular Ambiguity Sets
Preprint
Abstract
Robust Markov decision processes (MDPs) have attracted significant interest due to their ability to protect MDPs from poor out-of-sample performance in the presence of ambiguity. In contrast to classical MDPs, which account for stochasticity by modeling the dynamics through a stochastic process with a known transition kernel, a robust MDP additionally accounts for ambiguity by optimizing against the most adverse transition kernel from an ambiguity set constructed via historical data. In this paper, we develop a unified solution framework for a broad class of robust MDPs with $s$-rectangular ambiguity sets, where the most adverse transition probabilities are considered independently for each state. Using our algorithms, we show that $s$-rectangular robust MDPs with $1$- and $2$-norm as well as $φ$-divergence ambiguity sets can be solved several orders of magnitude faster than with state-of-the-art commercial solvers, and often only a logarithmic factor slower than classical MDPs. We demonstrate the favorable scaling properties of our algorithms on a range of synthetically generated as well as standard benchmark instances.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Policy Gradient Algorithms for Robust MDP\(\text{s}\) with Nonrectangular Uncertainty SetsSIAM Journal on Optimization, 2026
- Distributionally robust Optimal Control and MDP modelingOperations Research Letters, 2021
- Distributionally robust optimization for sequential decision-makingOptimization, 2019
- A filtered bucket-clustering method for projection onto the simplex and the $\ell _1$ ballMathematical Programming, 2019
- Identifying effective scenarios in distributionally robust stochastic programs with total variation distanceMathematical Programming, 2018
- Robust Scheduling of EV Charging Load With Uncertain Wind Power IntegrationIEEE Transactions on Smart Grid, 2016
- Robust Power Control under Channel Uncertainty for Cognitive Radios with Sensing DelaysIEEE Transactions on Wireless Communications, 2013
- Risk-averse dynamic programming for Markov decision processesMathematical Programming, 2010
- An analysis of model-based Interval Estimation for Markov Decision ProcessesJournal of Computer and System Sciences, 2008
- A finite algorithm for finding the projection of a point onto the canonical simplex of ? nJournal of Optimization Theory and Applications, 1986