This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Bonet, B. Search for Related Content

On the Speed of Convergence of Value Iteration on Stochastic Shortest-Path Problems

Departamento de Computación, Universidad Simón Bolívar, Caracas 89000, Venezuela
bonet{at}ldc.usb.ve, http://www.ldc.usb.ve/bonet

We establish a bound on the convergence time of the value iteration algorithm on stochastic shortest-path problems. The bound, which applies for admissible initial vectors as, for example, J\equiv 0, implies a polynomial-time convergence of value iteration for all problems with polynomially bounded \Vert{J^*}\Vert/\underline{g}. This result gives a partial answer to the open problem of bounding the convergence time of value iteration on arbitrary initial vectors. The proof is obtained by analyzing a stochastic process associated with the shortest-path problem.

Key Words: Markov decision processes; stochastic shortest-path problems; value iteration
History: Received: October 3, 2005; revision received: August 28, 2006;

This article has been cited by other articles:

				A. Vladimirsky Label-Setting Methods for Multimode Stochastic Shortest Path Problems on Graphs Mathematics of Operations Research, November 1, 2008; 33(4): 821 - 838. [Abstract] [PDF]