Proceedings

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

Fengming Zhu, Fangzhen Lin

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 490-498.

https://doi.org/10.24963/ijcai.2026/56

Keywords

  • Agent-based and Multi-agent Systems: Agent theories and models
  • Planning and Scheduling: Planning with Incomplete Information
  • Game Theory and Economic Paradigms: Noncooperative games
  • Machine Learning: Partially observable reinforcement learning and POMDPs

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 Iterated Prisoner's Dilemma, the Iterated Traveler's Dilemma, and the 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.

Fengming Zhu, and Fangzhen Lin. 2026. Constant-Memory Strategies in Stochastic Games: A Theoretical and Empirical Study. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 490–498. https://doi.org/10.24963/ijcai.2026/56
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards