Speeding up the convergence of value iteration in partially observable Markov decision processes

Partially observable Markov decision processes (POMDPs) have recently become pop-ular among many AI researchers because they serve as a natural model for planning under uncertainty. Value iteration is a well-known algorithm for nding optimal policies for POMDPs. It typically takes a large number of iterations to converge. This paper proposes a method for accelerating the convergence of value iteration. The method has been eval-uated on an array of benchmark problems and was found to be very eective: It enabled value iteration to converge after only a few iterations on all the test problems. 1