Constant-Memory Strategies in Stochastic Games: A Theoretical and Empirical Study

Fengming Zhu; Fangzhen Lin

IJCAI 20260 citations

Constant-Memory Strategies in Stochastic Games: A Theoretical and Empirical Study

Abstract

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 a discussion on the computational hardness of best responding to mixed constant-memory strategies. Those theoretic insights are later verified on several sequential decision-making testbeds, including the \textit{Iterated Prisoner's Dilemma}, the \textit{Iterated Traveler's Dilemma}, and the \textit{Pursuit} domain. This work aims to enhance the understanding of theoretical issues in single-agent planning under multi-agent systems, and uncover the connection between decision models in single-agent and multi-agent contexts. The codebase and the full version of this paper is available at github.com/Fernadoo/Const-Mem.

Agent-based and Multi-agent Systems: Agent theories and modelsGame Theory and Economic Paradigms: Noncooperative gamesMachine Learning: Partially observable reinforcement learning and POMDPsPlanning and Scheduling: Planning with Incomplete Information

BibTeX

@inproceedings{ijcai2026_constantmemoryst,
  title = {Constant-Memory Strategies in Stochastic Games: A Theoretical and Empirical Study},
  author = {Fengming Zhu and Fangzhen Lin},
  booktitle = {IJCAI 2026},
  year = {2026}
}