Strategy Complexity of Reachability in Countable Stochastic 2-Player Games

Area of Science:

• Theoretical Computer Science
• Game Theory
• Stochastic Processes

Background:

• Stochastic 2-player games with reachability objectives are fundamental in decision-making under uncertainty.
• Understanding strategy memory requirements is crucial for computational complexity and algorithm design.

Purpose of the Study:

• To fully characterize the memory needs of epsilon-optimal and optimal strategies in infinite stochastic games.
• To investigate the impact of action set sizes and uniformity on memory requirements.

Main Methods:

• Analysis of memory bounds for epsilon-optimal and optimal strategies.
• Consideration of uniform strategies (independent of the start state).
• Examination of specific cases like infinitely branching turn-based games.

Main Results:

• Epsilon-optimal Maximizer strategies necessitate infinite memory if the Minimizer has infinite action sets.
• Even with guaranteed winning strategies, finite memory (step counter plus private memory) is insufficient in some infinite games.
• Memoryless uniform epsilon-optimal Maximizer strategies may not exist, even with finite action sets or finitely branching games.

Conclusions:

• The memory complexity of strategies in infinite stochastic games is highly sensitive to player action sets and uniformity requirements.
• A single bit of public memory suffices for uniform epsilon-optimal Maximizer strategies in games with finite action sets.