Playing Against a Stationary Opponent

This paper investigates properties of Blackwell [Formula: see text]-optimal strategies in zero-sum stochastic games when the adversary is restricted to stationary strategies, motivated by applications to robust Markov decision processes. For a class of absorbing games (including generalized Big Match games), we show that Markovian Blackwell [Formula: see text]-optimal strategies may fail to exist, yet we prove the existence of Blackwell [Formula: see text]-optimal strategies that can be implemented by a two-state automaton whose internal transitions are independent of actions. For more general absorbing games, however, there need not exist Blackwell [Formula: see text]-optimal strategies that are independent of the adversary’s decisions. Our findings provide new insights into the properties of optimal policies for robust Markov decision processes.