  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.
