Strategy Complexity of B\"uchi Objectives in Concurrent Stochastic Games
<|reference_start|>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 $\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\"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 $\varepsilon$-optimal Max strategies for the Transience objective alone (which is only meaningful in infinite graphs) can be memoryless.<|reference_end|>
@article{kiefer2024strategy,
    title={Strategy Complexity of B\"uchi Objectives in Concurrent Stochastic Games},
    author={Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke},
    journal={arXiv preprint arXiv:2404.15483},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.15483},
    primaryClass={cs.GT math.PR}
}