Mixed Acceleration Techniques for Solving Quickly Stochastic Shortest-Path Markov Decision Processes

In this paper we propose the combination of accelerated variants of value iteration mixed with improved prioritizedsweeping for the fast solution of stochastic shortest-path Markov decision processes. Value iteration is a classicalalgorithm for solving Markov decision processes, but this algorithm and its variants are quite slow for solvingconsiderably large problems. In order to improve the solution time, acceleration techniques such as asynchronousupdates, prioritization and prioritized sweeping have been explored in this paper. A topological reordering algorithmwas also compared with static reordering. Experimental results obtained on finite state and action-space stochasticshortest-path problems show that our approach achieves a considerable reduction in the solution time with respect tothe tested variants of value iteration. For instance, the experiments showed in one test a reduction of 5.7 times withrespect to value iteration with asynchronous updates.