Sequential decision-making under uncertainty: a robust MDPs review

Fueled by advances in both robust optimization theory and reinforcement learning (RL), robust Markov Decision Processes (RMDPs) have garnered increasing attention due to their powerful capability for sequential decision-making under uncertainty. In this paper, we provide a comprehensive overview of the theoretical foundations and recent developments in RMDPs, with a particular emphasis on ambiguity modeling. We examine the "rectangular assumption", a key condition ensuring computational tractability in RMDPs but often resulting in overly conservative policies. Three widely used rectangular forms are summarized, and a novel proof is provided for the NP-hardness of non-rectangular RMDPs. We categorize RMDP formulation approaches into parametric, moment-based, and discrepancy-based models, analyzing the trade-offs associated with each representation. Beyond the traditional scope of RMDPs, we also explore recent efforts to relax rectangular assumptions and highlight emerging trends within the RMDP research community. These developments contribute to more practical and flexible modeling frameworks, complementing the classical RMDP results. Relaxing rectangular assumptions tailored to operations management is a promising area for future research, and there are also opportunities for further advances in developing fast algorithms and provably robust RL algorithms.