Comparison of Algorithms for Simple Stochastic Games

KŘETÍNSKÝ, Jan; Emanuel RAMNEANTU; Alexander SLIVINSKIY a Maximilian WEININGER. Comparison of Algorithms for Simple Stochastic Games. In Proceedings 11th International Symposium on Games, Automata, Logics, and Formal Verification, GandALF 2020, Brussels, Belgium, September 21-22, 2020. 2020, s. 131-148. ISSN 20752180. Dostupné z: https://doi.org/10.4204/EPTCS.326.9.

Základní údaje

Originální název

Comparison of Algorithms for Simple Stochastic Games

Autoři

KŘETÍNSKÝ, Jan; Emanuel RAMNEANTU; Alexander SLIVINSKIY a Maximilian WEININGER

Vydání

Proceedings 11th International Symposium on Games, Automata, Logics, and Formal Verification, GandALF 2020, Brussels, Belgium, September 21-22, 2020. od s. 131-148, 18 s. 2020

---

Další údaje

Typ výsledku

Stať ve sborníku

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

ISSN

DOI

https://doi.org/10.4204/EPTCS.326.9

---

Anotace

V originále

Simple stochastic games are turn-based 21/2-player zero-sum graph games with a reachability objective. The problem is to compute the winning probability as well as the optimal strategies of both players. In this paper, we compare the three known classes of algorithms - value iteration, strategy iteration and quadratic programming - both theoretically and practically. Further, we suggest several improvements for all algorithms, including the first approach based on quadratic programming that avoids transforming the stochastic game to a stopping one. Our extensive experiments show that these improvements can lead to significant speed-ups. We implemented all algorithms in PRISMgames 3.0, thereby providing the first implementation of quadratic programming for solving simple stochastic games.