Stochastic Limit-Average Games are in EXPTIME
Krishnendu Chatterjee, Rupak Majumdar, Thomas A. Henzinger · arXiv (Cornell University) · 2008
The value of a finite-state two-player zero-sum stochastic game with limit-average payoff can be approximated to within $ε$ in time exponential in a polynomial in the size of the game times polynomial in logarithmic in $\frac{1}ε$, for all $ε>0$.