Skip to Main content Skip to Navigation
Reports

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

Abstract : 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.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00506390
Contributor : Konstantin Avrachenkov Connect in order to contact the contributor
Submitted on : Tuesday, July 27, 2010 - 3:41:49 PM
Last modification on : Thursday, January 20, 2022 - 5:27:35 PM
Long-term archiving on: : Thursday, October 28, 2010 - 5:32:16 PM

File

RR-7355.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00506390, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

121

Files downloads

222