Bounded-Memory Strategies in Partial-Information Games
Sougata Bose, Rasmus Ibsen-Jensen, Patrick Totzke · 2024
We study the computational complexity of solving stochastic games with mean-payoff objectives. Instead of identifying special classes in which simple strategies are sufficient to play ∈-optimally, or form ∈-Nash equilibria, we consider general partial-information multiplayer games and ask what can be achieved with (and against) finite-memory strategies up to a given bound on the memory.