Robust Markov Decision Process: Beyond Rectangularity

Markov decision processes (MDPs) are a common approach used to model dynamic optimization problems. MDPs are specified by a set of states, actions, transition probability kernel and the rewards associated with transitions. The goal is to find a policy that maximizes the expected cumulated reward. However, in most real world problems, the model parameters are estimated from noisy observations and are uncertain. The optimal policy for the nominal parameters might be highly sensitive to even small perturbations in the parameters, leading to significantly suboptimal outcomes. To address this issue, we consider a robust approach where the uncertainty in probability transitions is modeled as an adversarial selection from an uncertainty set. Most prior works consider the case where uncertainty on transitions related to different states is uncoupled. However, the case of general uncertainty sets is known to be intractable. We consider a factor model where the transition probability is a linear function of a factor matrix that is uncertain and belongs to a factor matrix uncertainty set. It allows to model dependence between probability transitions across different states and it is significantly less conservative than prior approaches. We show that under a certain assumption, we can efficiently compute an optimal robust policy under the factor matrix uncertainty model. We show that an optimal robust policy can be chosen deterministic and in particular is an optimal policy for some transition kernel in the uncertainty set. This implies strong min-max duality. We introduce the robust counterpart of important structural results of classical MDPs and we provide a computational study to demonstrate the usefulness of our approach, where we present two examples where robustness improves the worst-case and the empirical performances while maintaining a reasonable performance on the nominal parameters.