A Recursive Algorithm for Solving Simple Stochastic Games

2021/10/03 by Xavier Badin de Montjoye, de Montjoye, Xavier Badin
Computer Science · Economics, Econometrics and Finance · Engineering · #Artificial Intelligence in Games #Sports Analytics and Performance #Autonomous Vehicle Technology and Safety

paper · pdf · doi:10.48550/arxiv.2110.01030

Abstract

We present two recursive strategy improvement algorithms for solving simple stochastic games. First we present an algorithm for solving SSGs of degree d that uses at most O(\lfloor(d+1)²/2\rfloor^n/2) iterations, with n the number of MAX vertices. Then, we focus on binary SSG and propose an algorithm that has complexity O(φⁿPoly(N)) where φ= (1 + √(5))/2 is the golden ratio. To the best of our knowledge, this is the first deterministic strategy improvement algorithm that visits 2^cn strategies with c < 1.

Citations

• Strategy improvement for concurrent reachability and turn-based stochastic safety games

Related

• A Generic Strategy Improvement Method for Simple Stochastic Games
• Solving Simple Stochastic Games with few Random Nodes faster using Bland's Rule
• Solving simple stochastic games with few coin toss positions
• Exact Algorithms for Solving Stochastic Games
• The Complexity of Simple Stochastic Games