Reduction of temporal complexity in Markov decision processes

In this paper we propose a new algorithm in order to reduce temporal complexity in Markov decision processes. Value iteration is a classical algorithm for solving them, but this algorithm and its variants are quite slow for discount factors close to one and their convergence properties depend to a great extent on a good state update order. It has been shown that improved topological value iteration presents a good convergence speed thanks to the use of an improved topological ordering. Nevertheless, its drawback is due to high memory requirements. So, our algorithm obtains the optimal state backup order with less memory requirements. Experimental results on stochastic shortest-path problems (highly cyclic) are presented. Our approach obtained a considerable reduction in temporal complexity with respect to other variants of value iteration. For instance, the experiments showed in one test a reduction of six times with respect to asynchronous value iteration.