Simplifying optimal strategies in stochastic games

We deal with zero-sum limiting average stochastic games. We show that the existence of arbitrary optimal strategies implies the existence of stationary ε-optimal strategies, for all ε>0, and the existence of Markov optimal strategies. We present such a construction for which we do not even need to know these optimal strategies. Furthermore, an example demonstrates that the existence of stationary optimal strategies is not implied by the existence of optimal strategies, so the result is sharp. More generally, one can evaluate a strategy π for the maximizing player, player 1, by the reward φ(s)(π) that π guarantees to him when starting in state s. A strategy π is called nonimproving if φ(s)(π) greater than or equal to φ(s)(π[h]) for all s and for all finite histories h with final state s, where π[h] is the strategy π conditional on the history h. Using the evaluation φ, we may define the relation ‘ε-better’ between strategies. A strategy π(1) is called epsilon-better than π(2) if φ(s)(π(1))≥φ(s)(π(2)) − ε for all s. We show that for any nonimproving strategy π, for all ε>0, there exists an ε-better stationary strategy and a (0)-better Markov strategy as well. Since all optimal strategies are nonimproving, this result can be regarded as a generalization of the above result for optimal strategies. Finally, we briefly discuss some other extensions. Among others, we indicate possible simplifications of strategies that are only optimal for particular initial states by ‘almost stationary’ ε-optimal strategies, for all ε>0, and by ‘almost Markov’ optimal strategies. We also discuss the validity of the above results for other reward functions. Several examples clarify these issues.