Strategy Complexity of Büchi and Transience Objectives in Concurrent Stochastic Games

We study two-player stochastic games on countable graphs. Players Max and Min seek, respectively, to maximize and minimize the probability of satisfying the game objective. The Büchi objective is to visit a given set of states infinitely often. The Transience objective is to visit no state infinitely often. In Büchi games, there exist $\epsilon$-optimal Max strategies that use just a step counter plus 1 bit of public memory. This upper bound holds for all countable graphs, but is a new result even for finite graphs. It is tight, because Max strategies that use just a step counter, or just finite memory, are not sufficient, even on finite game graphs. This upper bound follows from a slightly stronger new result: $\epsilon$-optimal Max strategies for the combined Büchi and Transience objective require exactly 1 bit of public memory. Moreover, $\epsilon$-optimal Max strategies for the Transience objective alone can be chosen as memoryless.

Funding: Financial support from Agence Nationale de la Recherche [Grant ANR-22-CE48-0005] and the Engineering and Physical Sciences Research Council [Grant EP/X042596/1] is gratefully acknowledged.