Artículo
Illustrated review of convergence conditions of the value iteration algorithm and the rolling horizon procedure for average-cost MDPs
Fecha de publicación:
02/2012
Editorial:
Springer
Revista:
Annals Of Operations Research
ISSN:
0254-5330
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
This paper is concerned with the links between the Value Iteration algorithm and the Rolling Horizon procedure, for solving problems of stochastic optimal control under the long-run average criterion, in Markov Decision Processes with finite state and action spaces. We review conditions of the literature which imply the geometric convergence of Value Iteration to the optimal value. Aperiodicity is an essential prerequisite for convergence. We prove that the convergence of Value Iteration generally implies that of Rolling Horizon. We also present a modified Rolling Horizon procedure that can be applied to models without analyzing periodicity, and discuss the impact of this transformation on convergence. We illustrate with numerous examples the different results. Finally, we discuss rules for stopping Value Iteration or finding the length of a Rolling Horizon. We provide an example which demonstrates the difficulty of the question, disproving in particular a conjectured rule proposed by Puterman.
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - ROSARIO)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Citación
Della Vecchia, Eugenio Martín; Di Marco, Silvia Cristina; Jean-marie, Alain; Illustrated review of convergence conditions of the value iteration algorithm and the rolling horizon procedure for average-cost MDPs; Springer; Annals Of Operations Research; 199; 1; 2-2012; 193-214
Compartir
Altmétricas