Comparison of Algorithms for Simple Stochastic Games

Simple stochastic games are turn-based 2. 5-player zero-sum games with a reachability objective. The problem is to compute the winning probability as well as the optimal strategies of both players. In this work, 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, thereby providing the first implementation of quadratic programming for solving simple stochastic games. This is joint work with Jan Kretinsky, Emanuel Ramneantu and Alexander Slivinskiy. It has been published at GandALF 2020 (https: //arxiv. org/abs/2009. 10882v1) and the respective presentation (https: //www. youtube. com/watch? v=kEvJg7xJOv4) won the best video award.

Authors

• Maximilian Weininger Ruhr-Universtät Bochum

Keywords

No keywords are indexed for this paper.