Ecole d'ingénieur et centre de recherche en télécommunications

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

Mots Clés:Stochastic games; Perfect information; Uniform optimal strategies; Computation
Type:Rapport
Langue:English
Ville:
Date:
Département:Communications Mobiles
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},, }
Voir aussi: