Policy iteration algorithm for zero-sum multichain stochastic games with mean payoff and perfect information

Marianne Akian 1, 2 Jean Cochet-Terrasson Sylvie Detournay 1, 2 Stéphane Gaubert 1, 2
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : We consider zero-sum stochastic games with finite state and action spaces, perfect information, mean payoff criteria, without any irreducibility assumption on the Markov chains associated to strategies (multichain games). The value of such a game can be characterized by a system of nonlinear equations, involving the mean payoff vector and an auxiliary vector (relative value or bias). We develop here a policy iteration algorithm for zero-sum stochastic games with mean payoff, following an idea of two of the authors (Cochet-Terrasson and Gaubert, C. R. Math. Acad. Sci. Paris, 2006). The algorithm relies on a notion of nonlinear spectral projection (Akian and Gaubert, Nonlinear Analysis TMA, 2003), which is analogous to the notion of reduction of super-harmonic functions in linear potential theory. To avoid cycling, at each degenerate iteration (in which the mean payoff vector is not improved), the new relative value is obtained by reducing the earlier one. We show that the sequence of values and relative values satisfies a lexicographical monotonicity property, which implies that the algorithm does terminate. We illustrate the algorithm by a mean-payoff version of Richman games (stochastic tug-of-war or discrete infinity Laplacian type equation), in which degenerate iterations are frequent. We report numerical experiments on large scale instances, arising from the latter games, as well as from monotone discretizations of a mean-payoff pursuit-evasion deterministic differential game.
Type de document :
Pré-publication, Document de travail
Preprint arXiv:1208.0446, 34pages. 2012
Liste complète des métadonnées

Contributeur : Marianne Akian <>
Soumis le : vendredi 11 janvier 2013 - 15:40:40
Dernière modification le : jeudi 11 janvier 2018 - 06:22:34


  • HAL Id : hal-00773080, version 1
  • ARXIV : 1208.0446



Marianne Akian, Jean Cochet-Terrasson, Sylvie Detournay, Stéphane Gaubert. Policy iteration algorithm for zero-sum multichain stochastic games with mean payoff and perfect information. Preprint arXiv:1208.0446, 34pages. 2012. 〈hal-00773080〉



Consultations de la notice