Multi-Agent Decision Making with Bounded Memory

203 concepts146 papers1 proposal

In game theory and multi-agent systems, researchers traditionally evaluate agent behavior through two extreme lenses: perfect recall and memoryless semantics.

An agent with perfect recall remembers every action it has ever taken and every observation it has ever made. As noted by Ronen Brafman et al. in Towards Action Prediction Using a Mental-Level Model, theoretical guarantees for predicting an agent's future actions heavily rely on this assumption. However, perfect recall causes an exponential explosion in the size of the game tree, making computation and formal verification notoriously intractable.

To escape this complexity, researchers often enforce a memoryless constraint, assuming agents act purely on the immediate state of the environment. For instance, Petr Cermák et al. demonstrate in MCMAS-SLK: A Model Checker for the Verification of Strategy Logic Specifications that restricting agents to memoryless strategies keeps the model-checking problem within the decidable PSPACE complexity class.

Yet, real-world agents—whether biological organisms or deep reinforcement learning models—operate in the messy middle. They possess finite memory capacities that prevent perfect recall, but they are rarely entirely memoryless. Investigating how bounded memory alters strategic interaction, learning stability, and computational verification defines this research direction.

The Strategic Cost of Forgetting and Remembering

Why does memory depth matter so fundamentally for multi-agent coordination? When agents are completely stateless, they cannot utilize historical data to establish coordinated equilibria, such as reciprocity or reputation-based cooperation.

Conversely, adding memory does not simply make games easier to solve; it fundamentally alters system dynamics. Yuma Fujimoto et al. discovered in Learning in Multi-Memory Games Triggers Complex Dynamics Diverging from Nash Equilibrium that when agents transition from memoryless to multi-memory strategies in zero-sum games, their learning dynamics destabilize. Instead of orbiting a stable Nash equilibrium, multi-memory agents spiral outward into chaotic, unpredictable behaviors.

Interestingly, this instability can be tamed by introducing memory asymmetry. In Global Behavior of Learning Dynamics in Zero-Sum Games with Memory Asymmetry, Yuma Fujimoto et al. proved that if one player retains historical memory while the opponent remains reactive, the chaotic cycles break, forcing the entire system to converge globally to the Nash equilibrium.

Engineering Imperfect Recall through Strategic Abstraction

If perfect recall is computationally impossible for complex games and memoryless behavior is strategically crippled, how do we design practical AI systems? The solution lies in imperfect recall abstractions—mathematical frameworks that teach agents to strategically forget irrelevant details.

In Automated Construction of Bounded-Loss Imperfect-Recall Abstractions in Extensive-Form Games (Extended Abstract), Jiri Cermak et al. introduced algorithms that automatically compress massive game trees by merging historical states that do not significantly impact the final payoff. In follow-up work, Jiří Čermák et al. demonstrated in Automated construction of bounded-loss imperfect-recall abstractions in extensive-form games that these abstractions allow algorithms to compute near-optimal strategies using less than 1% of the memory required by traditional perfect-recall models.

This trade-off is highly visible in cooperative AI benchmarks. For example, Rodrigo Canaan et al. evaluated deep reinforcement learning models in the card game Hanabi in Behavioral Evaluation of Hanabi Rainbow DQN Agents and Rule-Based Agents. They showed that feed-forward architectures without recurrent memory connections fail to generalize to new partners because they cannot maintain a history of interactions, leaving them unable to identify a teammate's strategy mid-game. To handle these information gaps mathematically, frameworks like the one proposed in No-Regret Learning in Extensive-Form Games with Imperfect Recall provide formal regret bounds, proving that strategic forgetting can be bounded so it does not lead to catastrophic performance loss.

Formalizing Knowledge and Strategic Know-How

To verify that a multi-agent system will behave safely and correctly, computer scientists must formally reason about what an agent knows relative to what it remembers. This requires distinguishing between an agent knowing that a winning strategy exists versus knowing how to execute it when its memory is constrained.

Francesco Belardinelli formalized this distinction in Reasoning about Knowledge and Strategies: Epistemic Strategy Logic, demonstrating how variations in an agent's memory model fundamentally alter the validity of its strategic claims. When agents suffer from imperfect recall, they cannot rely on past observations to resolve current environmental uncertainties. As Pavel Naumov argues in Together We Know How to Achieve: An Epistemic Logic of Know-How (Extended Abstract), this constraint necessitates a more rigorous definition of "know-how" that depends entirely on information available in the present moment.

Conversely, when full cooperation can be paired with perfect memory, the interplay simplifies. In Strategic Coalitions with Perfect Recall, Pavel Naumov proved that the complex relationship between a group's distributed knowledge and its long-term strategic capability can be captured by a single, elegant logical axiom.

Ultimately, mapping this spectrum between perfect recall and memoryless execution allows researchers to build multi-agent systems that are both strategically capable and computationally viable.

Key Foundational Work

Towards Action Prediction Using a Mental-Level Model (1995) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 155 papers
  2. Version 1 · 2026-10-04 · 88 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_perfect_recall_assumption_7c775e84,
  title = {perfect recall assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/perfect-recall-assumption/rdr_7c775e84ab6449578a641290e7ee0fe9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_perfect_recall_assumption_7c775e84_v2,
  title = {perfect recall assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/perfect-recall-assumption/rdr_7c775e84ab6449578a641290e7ee0fe9/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake