Robust Control of Markov Decision Processes with Uncertain Transition
Matrices
Operations Research, (2005)Abstract
Optimal solutions to Markov decision problems may be very sensitive
with respect to the state transition probabilities. In many practical
problems, the estimation of these probabilities is far from accurate.
Hence, estimation errors are limiting factors in applying Markov
decision processes to real-world problems. We consider a robust control
problem for a finite-state, finite-action Markov decision process,
where uncertainty on the transition matrices is described in terms
of possibly nonconvex sets. We show that perfect duality holds for
this problem, and that as a consequence, it can be solved with a
variant of the classical dynamic programming algorithm, the "robust
dynamic programming" algorithm. We show that a particular choice
of the uncertainty sets, involving likelihood regions or entropy
bounds, leads to both a statistically accurate representation of
uncertainty, and a complexity of the robust recursion that is almost
the same as that of the classical recursion. Hence, robustness can
be added at practically no extra computing cost. We derive similar
results for other uncertainty sets, including one with a finite number
of possible values for the transition matrices. We describe in a
practical path planning example the benefits of using a robust strategy
instead of the classical optimal strategy; even if the uncertainty
level is only crudely guessed, the robust strategy yields a much
better worst-case expected travel time.
Description
diverse cognitive systems bib
