Strategy complexity in infinite-state MDPs and two-player games

Abstract

Markov decision processes (MDPs) are a standard model for dynamic systems that exhibit both stochastic and nondeterministic behavior. For MDPs with finite state space it is known that for a wide range of objectives there exist optimal strategies that are memoryless and deterministic. In contrast, if the state space is infinite, optimal strategies may not exist, and optimal or epsilon-optimal strategies may require (possibly infinite) memory. In this talk we consider various qualitative objectives: reachability, safety, (co-)Büchi, and other parity objectives. We aim at giving an introduction to a collection of techniques that allow for the construction of strategies with little or no memory in countably infinite MDPs. We also report on recent extensions of our work on strategy complexity. On the one hand, we admit a second player, leading to two-player stochastic zero-sum games. On the other hand, we consider also quantitative objectives, in particular the expected limsup of the daily reward.