TY - JOUR
T1 - Comparison of algorithms for simple stochastic games
AU - Křetínský, Jan
AU - Ramneantu, Emanuel
AU - Slivinskiy, Alexander
AU - Weininger, Maximilian
N1 - Publisher Copyright:
© Křetínský, Ramneantu, Slivinskiy & Weininger.
PY - 2020/9/20
Y1 - 2020/9/20
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85092655625&partnerID=8YFLogxK
U2 - 10.4204/EPTCS.326.9
DO - 10.4204/EPTCS.326.9
M3 - Conference article
AN - SCOPUS:85092655625
SN - 2075-2180
VL - 326
SP - 131
EP - 148
JO - Electronic Proceedings in Theoretical Computer Science, EPTCS
JF - Electronic Proceedings in Theoretical Computer Science, EPTCS
T2 - 11th International Symposium on Games, Automata, Logics, and Formal Verification, G AND ALF 2020
Y2 - 21 September 2020 through 22 September 2020
ER -