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:
© 2022 The Authors
PY - 2022/11
Y1 - 2022/11
N2 - 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.
AB - 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.
KW - Algorithms
KW - Formal methods
KW - Probabilistic verification
KW - Quadratic programming
KW - Stochastic games
KW - Strategy iteration
KW - Value iteration
UR - http://www.scopus.com/inward/record.url?scp=85126553789&partnerID=8YFLogxK
U2 - 10.1016/j.ic.2022.104885
DO - 10.1016/j.ic.2022.104885
M3 - Article
AN - SCOPUS:85126553789
SN - 0890-5401
VL - 289
JO - Information and Computation
JF - Information and Computation
M1 - 104885
ER -