Solving simple stochastic games with few coin toss positions

2011/12/22 by Rasmus Ibsen-Jensen, Ibsen-Jensen, Rasmus, Peter Bro Miltersen +1
Computer Science · Economics, Econometrics and Finance · #AI-based Problem Solving and Planning #Artificial Intelligence in Games #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Sports Analytics and Performance #cs.GT

paper · pdf · doi:10.48550/arxiv.1112.5255

openalex publication_date 2011/12/22 · arxiv created 2012/03/20 · arxiv updated 2012/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Gimbert and Horn gave an algorithm for solving simple stochastic games with running time O(r! n) where n is the number of positions of the simple stochastic game and r is the number of its coin toss positions. Chatterjee et al. pointed out that a variant of strategy iteration can be implemented to solve this problem in time 4^r r^O(1) n^O(1). In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2^r (r log r + n)), thus improving both time bounds. While the algorithm is simple, the analysis leading to this time bound is involved, using techniques of extremal combinatorics to identify worst case instances for the algorithm.

Citations

• On cliques in graphs
• Stochastic Games

Related

• Solving Simple Stochastic Games with few Random Nodes faster using Bland's Rule
• A Generic Strategy Improvement Method for Simple Stochastic Games
• A Recursive Algorithm for Solving Simple Stochastic Games
• New algorithms for solving stochastic games
• The Complexity of Simple Stochastic Games