Another Sub‐exponential Algorithm for the Simple Stochastic Game

We study the problem of solving simple stochastic games, and give both an interesting new algorithm and a hardness result. We show a reduction from fine approximation of simple stochastic games to coarse approximation of a polynomial sized game, which can be viewed as an evidence showing the hardness to approximate the value of simple stochastic games. We also present a randomized algorithm that runs in $Õ(\sqrt{\mid V_{\mathrm{R}}\mid !})$ time, where |V R| is the number of RANDOM vertices and $Õ$ ignores polynomial terms. This algorithm is the fastest known algorithm when |V R|=ω(log n) and $\mid V_{\mathrm{R}}\mid =o(\sqrt{\min \mid V_{\min }\mid ,\mid V_{\max }\mid })$ and it works for general (non‐stopping) simple stochastic games.