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

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.Nous nous intéressons aux relations entre l'algorithme d'itération de valeurs et la procédure de l'horizon roulant, pour résoudre les problèmes de contrôle optimal stochastique Markovien sous le critère du coût moyen, dans le cas d'espaces d'états et d'actions finis. Nous passons en revue des conditions issues de la littérature qui impliquent la convergence géométrique de l'itération de valeurs vers la valeur optimale. L'apériodicité du modèle est un pré-requis essentiel. Nous montrons que la convergence de l'itération de valeurs implique de façon générale celle de l'horizon roulant. Nous présentons également une procédure modifiée d'horizon roulant qui peut être appliquée sans avoir besoin d'analyser l'apériodicité, et nous étudions l'impact de cette transformation sur la convergence. Nous illustrons les différents résultats avec de nombreux exemples