Algorithms for uniform optimal strategies in two-player zero-sum stochastic games with perfect information

Konstantin Avrachenkov (1) , Laura Cottatellucci (2) , Lorenzo Maggi (2)

1 MAESTRO - Models for the performance analysis and the control of networks
2 Eurecom [Sophia Antipolis]

In stochastic games with perfect information, in each state at most one player has more than one action available. We propose two algorithms which find the uniform optimal strategies for zero-sum two-player stochastic games with perfect information. Such strategies are optimal for the long term average criterion as well. We prove the convergence for one algorithm, which presents a higher complexity than the other one, for which we provide numerical analysis.

Dans les jeux stochastiques à information parfaite, dans chaque etat, au plus, un joueur a plus d'une action disponibles. Nous proposons deux algorithmes qui trouvent les stratégies uniformément optimales pour les jeux stochastiques à somme nulle avec deux joueurs et information parfaite. Ces stratégies sont aussi optimales pour le critère de la moyenne à long terme. Nous prouvons la convergence pour un algorithme, qui a une plus grande complexité que l'autre, pour lequel nous offrons une analyse numérique.

Mots clés: Stochastic games; Perfect information; Uniform optimal strategies; Computation

Domaines: Réseaux et télécommunications [cs.NI]

Konstantin Avrachenkov, Laura Cottatellucci, Lorenzo Maggi. Algorithms for uniform optimal strategies in two-player zero-sum stochastic games with perfect information. [Research Report] RR-7355, INRIA. 2010. ⟨inria-00506390⟩