Tractable Robust Markov Decision Processes
Preprint
Abstract
In this paper we investigate the tractability of robust Markov Decision Processes (RMDPs) under various structural assumptions on the uncertainty set. Surprisingly, we show that in all generality (i.e. without any assumption on the instantaneous rewards), s-rectangular and sa-rectangular uncertainty sets are the only models of uncertainty that are tractable. Our analysis also shows that existing non-rectangular models, including r-rectangular uncertainty and new generalizations, are only weakly tractable in that they require an additional structural assumption that the instantaneous rewards do not depend on the next state, and in this case they are equivalent to rectangular models, which severely undermines their significance and usefulness. Interestingly, our proof techniques rely on identifying a novel simultaneous solvability property, which we show is at the heart of several important properties of RMDPs, including the existence of stationary optimal policies and dynamic programming-based formulations. The simultaneous solvability property enables a unified approach to studying the tractability of all existing models of uncertainty, rectangular and non-rectangular alike.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Robust Markov Decision Processes: Beyond RectangularityMathematics of Operations Research, 2023
- Robust Markov Decision Processes with Data-Driven, Distance-Based Ambiguity SetsSIAM Journal on Optimization, 2022
- Robust MDPs with k-Rectangular UncertaintyMathematics of Operations Research, 2016
- Percentile Optimization for Markov Decision Processes with Parameter UncertaintyOperations Research, 2010
- Robust Control of Markov Decision Processes with Uncertain Transition MatricesOperations Research, 2005
- Robust Dynamic ProgrammingMathematics of Operations Research, 2005
- Über exponierte Punkte abgeschlossener PunktmengenFundamenta Mathematicae, 1935