Title:Strategy Complexity of Büchi Objectives in Concurrent Stochastic Games

Abstract:We study 2-player concurrent stochastic Büchi games on countable graphs. Two players, Max and Min, seek respectively to maximize and minimize the probability of visiting a set of target states infinitely often. We show that there always exist $\varepsilon$-optimal Max strategies that use just a step counter plus 1 bit of public memory. This upper bound holds for all countable graphs, but it is a new result even for the special case of finite graphs. The upper bound is tight in the sense that Max strategies that use just a step counter, or just finite memory, are not sufficient even on finite game graphs.
The upper bound is a consequence of a slightly stronger new result: $\varepsilon$-optimal Max strategies for the combined Büchi and Transience objective require just 1 bit of public memory (but cannot be memoryless). Our proof techniques also yield a closely related result, that $\varepsilon$-optimal Max strategies for the Transience objective alone (which is only meaningful in infinite graphs) can be memoryless.