TY - ELEC
AU - Grand Clement, Julien
PY - 2019
TI - Robust Markov Decision Processes: Beyond Rectangularity
LA - eng
M3 - Moving Image
AB - 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.
N2 - 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.
UR - https://open.library.ubc.ca/collections/48630/items/1.0379915
ER - End of Reference