Strategy Complexity of B\"uchi Objectives in Concurrent Stochastic Games

We study 2-player concurrent stochastic B\"uchi 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 ε-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: ε-optimal Max strategies for the combined B\"uchi and Transience objective require just 1 bit of public memory (but cannot be memoryless). Our proof techniques also yield a closely related result, that ε-optimal Max strategies for the Transience objective alone (which is only meaningful in infinite graphs) can be memoryless.