Sequential decision-making under uncertainty: a robust MDPs review

Wenfan Ou () and Sheng Bi ()
Additional contact information
Wenfan Ou: Shanghai University of Finance and Economics
Sheng Bi: Shanghai University of Finance and Economics

Annals of Operations Research, 2025, vol. 353, issue 3, No 13, 1239-1285

Abstract: Abstract 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.

Keywords: Robust Markov decision processes; Ambiguity sets modeling; Reinforcement learning; Rectangularity (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-025-06738-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:353:y:2025:i:3:d:10.1007_s10479-025-06738-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-025-06738-x

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().