Comparison of algorithms for simple stochastic games

Jan Křetínský, Emanuel Ramneantu, Alexander Slivinskiy, Maximilian Weininger

Research output: Contribution to journalConference articlepeer-review

5 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)131-148
Number of pages18
JournalElectronic Proceedings in Theoretical Computer Science, EPTCS
Volume326
DOIs
StatePublished - 20 Sep 2020
Event11th International Symposium on Games, Automata, Logics, and Formal Verification, G AND ALF 2020 - Virtual, Brussels, Belgium
Duration: 21 Sep 202022 Sep 2020

Fingerprint

Dive into the research topics of 'Comparison of algorithms for simple stochastic games'. Together they form a unique fingerprint.

Cite this