Robust Markov Decision Processes: Beyond Rectangularity

Vineet Goyal () and Julien Grand-Clément ()
Additional contact information
Vineet Goyal: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Julien Grand-Clément: Department of Information Systems and Operations Management, Ecole des Hautes Études Commerciales (HEC) de Paris, 78350 Jouy-en-Josas, France

Mathematics of Operations Research, 2023, vol. 48, issue 1, 203-226

Abstract: We consider a robust approach to address uncertainty in model parameters in Markov decision processes (MDPs), which are widely used to model dynamic optimization in many applications. Most prior works consider the case in which the uncertainty on transitions related to different states is uncoupled and the adversary is allowed to select the worst possible realization for each state unrelated to others, potentially leading to highly conservative solutions. On the other hand, the case of general uncertainty sets is known to be intractable. We consider a factor model for probability transitions in which the transition probability is a linear function of a factor matrix that is uncertain and belongs to a factor matrix uncertainty set . This is a fairly general model of uncertainty in probability transitions, allowing the decision maker to model dependence between probability transitions across different states, and it is significantly less conservative than prior approaches. We show that under an underlying rectangularity assumption, we can efficiently compute an optimal robust policy under the factor matrix uncertainty model. Furthermore, we show that there is an optimal robust policy that is deterministic, which is of interest from an interpretability standpoint. We also introduce the robust counterpart of important structural results of classical MDPs, including the maximum principle and Blackwell optimality, and we provide a computational study to demonstrate the effectiveness of our approach in mitigating the conservativeness of robust policies.

Keywords: Primary: 90C40; secondary: 90C17; Markov decision processes; robust optimization; rectangularity (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1259 (application/pdf)

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:inm:ormoor:v:48:y:2023:i:1:p:203-226

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().