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. Information and Computation. Amsterdam: Elsevier, 2022, roč. 289, č. 104885, s. 1-23. ISSN 0890-5401. Dostupné z: https://doi.org/10.1016/J.IC.2022.104885.

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í

Information and Computation, Amsterdam, Elsevier, 2022, 0890-5401

---

Další údaje

Typ výsledku

Článek v odborném periodiku

Impakt faktor

Impact factor: 1.000

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

DOI

https://doi.org/10.1016/J.IC.2022.104885

---

Anotace

V originále

Simple stochastic games are turn-based 2½-player zero-sum graph games with a reachability objective. The problem is to compute the winning probabilities 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 PRISM-games 3.0, thereby providing the first implementation of quadratic programming for solving simple stochastic games.