---
title: "Constant-Memory Strategies in Stochastic Games: A Theoretical and Empirical Study"
authors:
  - "Fengming Zhu"
  - "Fangzhen Lin"
doi: "10.24963/ijcai.2026/56"
url: "https://ijcai.org/proceedings/2026/56"
pdf: "https://ijcai.org/proceedings/2026/0056.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "490-498"
track: "Main Track"
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"
---

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

Fengming Zhu, Fangzhen Lin

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 490-498. DOI: [10.24963/ijcai.2026/56](https://doi.org/10.24963/ijcai.2026/56)

## 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.