Markov strategies are better than stationary strategies

We examine the use of stationary and Markov strategies in zero-sum stochastic games with finite state and action spaces. It is natural to evaluate a strategy for the maximising player, player???1, by the highest reward guaranteed to him against any strategy of the opponent. The highest rewards guaranteed by stationary strategies or by Markov strategies are called the stationary utility or the Markov utility, respectively. Since all stationary strategies are Markov strategies, the Markov utility is always larger or equal to the stationary utility. However, in all presently known subclasses of stochastic games, these utilities turn out to be equal. In this paper, we provide a colourful example in which the Markov utility is strictly larger than the stationary utility and we present several conditions under which the utilities are equal. We also show that each stochastic game has at least one initial state for which the two utilities are equal. Several examples clarify these issues