A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and Few Random Positions

Abstract

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph $G = (V,E)$, with local rewards $r : E \to \mathbb{Z}$, and three types of positions: black $V_B$, white $V_W$, and random $V_R$ forming a partition of $V$ . It is a longstanding open question whether a polynomial time algorithm for BWR-games exists, or not, even when $|V_R| = 0$. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper, we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with $|V_R| = O(1)$, a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in $|V_W| + |V_B|$, the maximum absolute local reward, and the common denominator of the transition probabilities.