Complexity of Good Strategies in Stochastic Games

Abstract. The talk will attempt to characterize good strategies for some special cases of stochastic games. For instance, the talk will argue that there might always be a good strategy with a certain property for all games in a special case of stochastic games or that no good strategy exists that have some property for some game. Concretely,
1) For the stochastic game the Big Match, no good strategy (for lim inf) exists that only depends on how long the game has been playing and a finite amount of extra memory (when the extra memory is updated deterministically).
2) For the Big Match there is a good strategy that uses only a single coin flip per round and exponential less space when previous known good strategies.
3) Let x be the greatest reward in a stochastic game. The talk will next give a simple characterization of the states of value equal to x for which there exists either (a) an optimal strategy; (b) for each ϵ > 0, an stationary ϵ-optimal strategy; or (c) for each ϵ > 0, a finite-memory ϵ-optimal strategy (when the memory is updated deterministically) . The characterization also gives the corresponding strategy.
4) The talk will then consider stochastic games where there exists ϵ-optimal stationary strategies for all ϵ > 0. It will argue that the smallest positive probability in a stationary ϵ-optimal strategy must be at least double exponential small for some sub-classes of stochastic games, while for other classes exponential small probabilities suffices.
Points 1) and 2) are based on “The Big Match in Small Space”, 3) is based on “The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games”, and 4) is based on “Strategy Complexity of Concurrent Stochastic Games with Safety and Reachability Objectives” and “The complexity of ergodic mean-payoff games”. All papers can be found in http://Rasmus.Ibsen-Jensen.com.