Robust Markov Decision Processes: Beyond Rectangularity
Mathematics of Operations Research · 2023-02 · 48 (1) · 203-226
DOI: 10.1287/moor.2022.1259 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics of Operations Research, 2023-02. Verfasst von Vineet Goyal und 1 weiteren Autor:innen. Die Arbeit wurde bisher 54-mal zitiert (Crossref) und nennt 25 Literaturangaben.
Abstract (Originalsprache)
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. Funding: V. Goyal’s research was supported in part by the National Science Foundation Division of Civil, Mechanical and Manufacturing Innovation [Grants 1351838 and 1636046] and DARPA Lagrange grants. J. Grand-Clément is supported by a grant of the French National Research Agency (ANR), “Investissements d’Avenir” (LabEx Ecodec/ANR-11-LABX-0047) and by Hi! Paris.
Zitieren
APA
Goyal, V., & Grand-Clément, J. (2023). Robust Markov Decision Processes: Beyond Rectangularity. Mathematics of Operations Research, 48(1), 203-226. https://doi.org/10.1287/moor.2022.1259
Vancouver
Goyal V, Grand-Clément J. Robust Markov Decision Processes: Beyond Rectangularity. Mathematics of Operations Research. 2023;48(1):203-226. doi:10.1287/moor.2022.1259
BibTeX
@article{Goyal2023,
author = {Goyal, Vineet and Grand-Clément, Julien},
title = {Robust Markov Decision Processes: Beyond Rectangularity},
journal = {Mathematics of Operations Research},
year = {2023},
volume = {48},
number = {1},
pages = {203--226},
doi = {10.1287/moor.2022.1259}
}
EUVIMED