Robust Markov Decision Processes: Beyond Rectangularity

DOI10.1287/MOOR.2022.1259arXiv1811.00215OpenAlexW4224230876MaRDI QIDQ6199239FDOQ6199239

Authors: Vineet Goyal, Julien Grand-Clément 

Publication date: 23 February 2024

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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 where 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 where 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.

Full work available at URL: https://arxiv.org/abs/1811.00215

Recommendations

• Robust MDPs with \(k\)-rectangular uncertainty
• Robust Markov Decision Processes
• Robust Control of Markov Decision Processes with Uncertain Transition Matrices
• Reinforcement learning in robust Markov decision processes
• Distributionally robust Markov decision processes

zbMATH Keywords

Markov decision processrobust optimizationrectangularity

Mathematics Subject Classification ID

Markov and semi-Markov decision processes (90C40) Robustness in mathematical programming (90C17)

Cited In (4)

• A dynamical neural network approach for distributionally robust chance-constrained Markov decision process
• Markov decision processes under model uncertainty
• Robust \(Q\)-learning algorithm for Markov decision processes under Wasserstein uncertainty
• A family of \(s\)-rectangular robust MDPs: relative conservativeness, asymptotic analyses, and finite-sample properties

This page was built for publication: Robust Markov Decision Processes: Beyond Rectangularity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199239)