Skip to Main content Skip to Navigation
Reports

Illustrated review of convergence conditions of the value iteration algorithm and the rolling horizon procedure for average-cost MDPs

Eugenio Della Vecchia 1 Silvia C. Di Marco 1 Alain Jean-Marie 2, 3, *
* Corresponding author
2 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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 convergence results.
Document type :
Reports
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00617271
Contributor : Alain Jean-Marie <>
Submitted on : Friday, August 26, 2011 - 5:13:42 PM
Last modification on : Tuesday, November 13, 2018 - 2:38:01 AM
Long-term archiving on: : Sunday, November 27, 2011 - 2:26:23 AM

File

RR-7710.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00617271, version 1

Citation

Eugenio Della Vecchia, Silvia C. Di Marco, Alain Jean-Marie. Illustrated review of convergence conditions of the value iteration algorithm and the rolling horizon procedure for average-cost MDPs. [Research Report] RR-7710, LIRMM; INRIA. 2011. ⟨inria-00617271⟩

Share

Metrics

Record views

662

Files downloads

1084