Serial and parallel value iteration algorithms for discounted Markov decision processes (Q2367364)

This paper extends the work of \textit{L. C. Thomas}, \textit{R. Hartley} and \textit{A. C. Lavercombe} [Oper. Res. Lett. 2, 72-76 (1983; Zbl 0511.90094)], where a number of serial value iteration schemes for the solution of discounted Markov decision processes were appraised. Several of the schemes are re-assessed using carefully chosen test problems. Parallel implementation of the algorithms, based on state space partition, is then discussed. Detailed performance data are given which demonstrate considerable efficiency gains over the serial approach. Throughout, the influence of problem structure is stressed.