Graduate School and Research Center In communication systems

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

Avrachenkov, Konstantin; Cottatellucci, Laura; Maggi, Lorenzo

Research Report N°7355, July 2010

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.

Document Hal Bibtex

Keywords:Stochastic games; Perfect information; Uniform optimal strategies; Computation
Type:Report
Language:English
City:
Date:
Department:Mobile Communications
Eurecom ref:3191
Copyright: © INRIA. Personal use of this material is permitted. The definitive version of this paper was published in Research Report N°7355, July 2010 and is available at :
Bibtex: @techreport{EURECOM+3191, year = {2010}, title = {{A}lgorithms for uniform optimal strategies in two-player zero-sum stochastic games with perfect information}, author = {{A}vrachenkov, {K}onstantin and {C}ottatellucci, {L}aura and {M}aggi, {L}orenzo }, number = {EURECOM+3191}, month = {07}, institution = {Eurecom}, url = {http://www.eurecom.fr/publication/3191},, }
See also: