Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm

Abstract

Simple stochastic games can be solved by value iteration (VI), which yields a sequence of under-approximations of the value of the game. This sequence is guaranteed to converge to the value only in the limit. Since no stopping criterion is known, this technique does not provide any guarantees on its results. We provide the first stopping criterion for VI on simple stochastic games. It is achieved by additionally computing a convergent sequence of over-approximations of the value, relying on an analysis of the game graph. Consequently, VI becomes an anytime algorithm returning the approximation of the value and the current error bound. As another consequence, we can provide a simulation-based asynchronous VI algorithm, which yields the same guarantees, but without necessarily exploring the whole game graph.

arXiv commentCAV2018

References in corpus (2)

• Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm
• A reduction from parity games to simple stochastic games

Cited by in corpus (8)

• PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games
• Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm
• Approximating Values of Generalized-Reachability Stochastic Games
• Widest Paths and Global Propagation in Bounded Value Iteration for Stochastic Games
• Comparison of Algorithms for Simple Stochastic Games (Full Version)
• Comparison of Algorithms for Simple Stochastic Games
• Quantifying Masking Fault-Tolerance via Fair Stochastic Games
• Widest Path Games and Maximality Inheritance in Bounded Value Iteration for Stochastic Games