Constant-Memory Strategies in Stochastic Games: Best Responses and Equilibria

Stochastic games have become a prevalent framework for studying long-term multi-agent interactions, especially in the context of multi-agent reinforcement learning. In this work, we comprehensively investigate the concept of constant-memory strategies in stochastic games. We first establish some results on best responses and Nash equilibria for behavioral constant-memory strategies, followed by some discussion on the computational hardness of best responding to mixed constant-memory strategies. The full version can be found at https://arxiv.org/abs/2505.07008.