Open Collections

Robust Markov Decision Processes: Beyond Rectangularity

Banff International Research Station for Mathematical Innovation and Discovery

Markov decision processes (MDPs) are a common approach to model dynamic optimization problems in many applications. However, in most real world problems, the model parameters that are estimated from noisy observations are uncertain, and the optimal policy for the nominal parameter values might be highly sensitive to even small perturbations in the parameters leading to significantly suboptimal outcomes. We consider a robust approach where the uncertainty in probability transitions is modeled as an adversarial selection from an uncertainty set. Most prior work considers the case where uncertainty on parameters related to different states is unrelated and the adversary is allowed to select 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 a significantly less conservative approach to modeling uncertainty in probability transitions while allowing to model dependence between probability transitions across different states. We show that under a certain rectangularity assumption, we can efficiently compute the optimal robust policy under the factor matrix uncertainty model. We also present a computational study to demonstrate the usefulness of our approach.

Mathematics; Operations research, mathematical programming; Computer science; Applied computer science

video/mp4

Author affiliation: Columbia University

2019-07-18

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/71046

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/