On the Existence of Easy Initial States for Undiscounted Stochastic Games

This paper deals with undiscounted infinite stage two-person zero-sum stochastic games with finite state and action spaces. It was recently shown that such games possess a value. But in general there are no optimal strategies. We prove that for each player there exists a nonempty set of easy initial states, i.e., starting states for which the player possesses an optimal stationary strategy. This result is proved with the aid of facts derived by Bewley and Kohlberg for the limit discount equation for stochastic games.