Comparison of Algorithms for Simple Stochastic Games (Full Version)

Abstract

Simple stochastic games are turn-based 2.5-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 PRISM-games 3.0, thereby providing the first implementation of quadratic programming for solving simple stochastic games.

References in corpus (5)

• PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games
• A reduction from parity games to simple stochastic games
• Of Cores: A Partial-Exploration Framework for Markov Decision Processes
• Approximating Values of Generalized-Reachability Stochastic Games
• Satisfiability Bounds for $\omega$-Regular Properties in Bounded-Parameter Markov Decision Processes

Cited by in corpus (2)

• Stochastic Games with Disjunctions of Multiple Objectives
• Stochastic Games with Disjunctions of Multiple Objectives (Technical Report)