A policy iteration algorithm for zero-sum stochastic games with mean payoff

We give a policy iteration algorithm to solve zero-sum stochastic games with finite state and action spaces and perfect information, when the value is defined in terms of the mean payoff per turn. This algorithm does not require any irreducibility assumption on the Markov chains determined by the strategies of the players. It is based on a discrete nonlinear analogue of the notion of reduction of a super-harmonic function. To cite this article: J. Cochet-Terrasson, S. Gaubert, C. R. Acad. Sci. Paris, Ser. I 343 (2006).

RésuméNous donnons un algorithme d'itération sur les politiques pour résoudre les jeux stochastiques à somme nulle, avec espaces d'état et d'action finis, en information parfaite, lorsque la valeur du jeu est définie en termes de gain moyen par tour. Cet algorithme ne demande pas que les chaînes de Markov déterminées par les stratégies des deux joueurs soient irréductibles. Il repose sur un analogue discret non-linéaire de la notion de réduite d'une fonction surharmonique. Pour citer cet article : J. Cochet-Terrasson, S. Gaubert, C. R. Acad. Sci. Paris, Ser. I 343 (2006).