Dynamic Programming-Compatible Uncertainty Sets in Robust Markov Decision Processes

In this paper, we investigate the compatibility of robust Markov decision processes (RMDPs) with dynamic programming under various assumptions on the uncertainty set (i.e., we investigate when one can solve an RMDP by solving a fixed-point equation. We show that in all generality, s-rectangular and sa-rectangular uncertainty sets are the only models of uncertainty that are compatible with dynamic programming. Our analysis shows that existing nonrectangular models, including r-rectangularity, are only weakly compatible with dynamic programming as they require the assumption that rewards do not depend on the next state. In this case, our results imply that one can always construct a rectangular uncertainty set that is equivalent for both policy evaluation and optimization to the dynamic programming-compatible nonrectangular model. This highlights a key limitation; dynamic-programming-compatible nonrectangular uncertainty sets, although practically relevant for uncertainty quantification, do not provide a genuinely distinct assessment of policy performance. Interestingly, our proof techniques rely on identifying a novel simultaneous solvability property, which we show is central to 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 all existing models of uncertainty, rectangular and nonrectangular alike.

Funding: The work described in this paper was partially supported by the Research Grants Council, University Grants Committee [Grant HKUST603/25] and the Agence Nationale de la Recherche [Grant HKUST603/25]. J. Grand-Clément was also supported by the Labex Ecodec [Grant ANR-11-LABEX-0047].