Robust planning with (L)RTDP
Olivier Buffet, Douglas Aberdeen · 2005
Stochastic Shortest Path problems (SSPs), a sub-class of Markov Decision Problems (MDPs), can be efficiently dealt with using Real-Time Dynamic Programming (RTDP). Yet, MDP models are often uncertain (obtained through statistics or guessing). The usual approach is robust planning: searching for the best policy under the worst model. This paper shows how RTDP can be made robust in the common case where transition probabilities are known to lie in a given interval. 1