Serial and parallel value iteration algorithms for discounted Markov decision processes

DOI10.1016/0377-2217(93)90061-QMaRDI QIDQ2367364zbMATH OpenFDO

Authors T. Archibald, K. I. M. McKinnon, Lyn C. Thomas

Publication date 13 July 1994

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(93)90061-Q

zbMATH Keywords

discounted Markov decision processesparallel implementationserial value iteration schemesstate space partitiontransputers

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Markov and semi-Markov decision processes (90C40)

Review text

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.

Recommendations

• Performance Issues for the Iterative Solution of Markov Decision Processes on Parallel Computers
• Monotone value iteration for discounted finite Markov decision processes
• The convergence of value iteration in discounted Markov decision processes
• On iterative optimization ol structured Markov decision processes with discounted rewards
• A K-step look-ahead analysis of value iteration algorithms for Markov decision processes

Cites work

• Computational comparison of value iteration algorithms for discounted Markov decision processes
• Computing the discounted return in markov and semi-markov chains
• Discounting, Ergodicity and Convergence for Markov Decision Processes
• scientific article; zbMATH DE number 3148886 (Why is no real title available?)
• scientific article; zbMATH DE number 4061056 (Why is no real title available?)
• Improved iterative computation of the expected discounted return in Markov and semi-Markov chains
• Letter to the Editor—A Test for Suboptimal Actions in Markovian Decision Problems
• On iterative optimization ol structured Markov decision processes with discounted rewards
• On the Generation of Markov Decision Processes
• Some Bounds for Discounted Sequential Decision Processes

Cited in

(9)

• A K-step look-ahead analysis of value iteration algorithms for Markov decision processes
• Block-scaling of value-iteration for discounted Markov renewal programming
• Evaluating Strategies for Markov Decision Processes in Parallel
• On iterative optimization ol structured Markov decision processes with discounted rewards
• Parallel Markov decision processes
• Optimizing Long‐term Hydro‐power Production Using Markov Decision Processes
• scientific article; zbMATH DE number 2030016 (Why is no real title available?)
• Performance Issues for the Iterative Solution of Markov Decision Processes on Parallel Computers
• A new parallelized of hierarchical value iteration algorithm for discounted Markov decision processes

This page was built for publication: Serial and parallel value iteration algorithms for discounted Markov decision processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2367364)