Solving Uncertain Markov Decision Problems: An Interval-Based Method.

Stochastic Shortest Path problems (SSPs), a subclass of Markov Decision Problems (MDPs), can be efficiently dealt with VI, PI, RTDP, LAO* and so on. However, in many practical problems the estimation of the probabilities is far from accurate. In this paper, we present uncertain transition probabilities as close real intervals. Also, we describe a general algorithm, called gLAO*, that can solve uncertain MDPs efficiently. We demonstrate that Buffet and Aberdeen's approach, searching for the best policy under the worst model, is a special case of our approaches. Experiments show that gLAO* inherits excellent performance of LAO* for solving uncertain MDPs. [ABSTRACT FROM AUTHOR]