In classical game theory and reinforcement learning, we almost always assume agents have perfect recall. This means an agent never forgets a past observation, a previous action, or a piece of information it once knew. While this assumption makes the math elegant, it is the "frictionless plane" of decision theory—a useful simplification that rarely holds in the real world.
Yoav Shoham noted as early as 1989 in Time for Action: On the Relation Between Time, Knowledge and Action that models assuming perfect memory fail to account for agents that must revise their understanding of the past or operate under hardware constraints. Research into imperfect recall explores what happens when agents have finite memory, intentionally forget information for privacy, or operate in decentralized teams where "collective memory" is fragmented.
The Complexity of Forgetting
The transition from perfect to imperfect recall isn't just a minor tweak; it fundamentally changes the computational landscape. In games with perfect recall, we can often use dynamic programming or efficient regret-minimization algorithms. However, as Emanuel Tewolde, Vincent Conitzer, and Paul W. Goldberg demonstrate in The Computational Complexity of Single-Player Imperfect-Recall Games, finding optimal strategies when an agent can forget its own past actions ranges from NP-hard to CLS-complete.
The difficulty arises because an agent with imperfect recall may find itself in a state where it cannot distinguish between different points in its own history. This creates a "non-linear" decision sequence. As Axel Parmentier and colleagues point out in Integer programming on the junction tree polytope for influence diagrams, these constraints prevent the use of standard dynamic programming, forcing researchers to turn to combinatorial optimization and mixed-integer programming.
Modeling Limited Memory
To handle these challenges, researchers use specialized frameworks like Limited Memory Influence Diagrams (LIMIDs). Unlike traditional influence diagrams that assume an agent remembers all previous nodes, LIMIDs explicitly define which past information is available at each decision point.
Denis Mauá and Cassio de Campos have developed algorithms like Labeled Variable Elimination (LVE) and Multiple Policy Updating (MPU) to solve these problems. Their work, such as Solving Limited Memory Influence Diagrams, uses dominance-based pruning to discard suboptimal strategies early, allowing them to solve problems with massive strategy spaces ($10^{64}$) that were previously unreachable.
Another approach, championed by Joseph Halpern and Yoram Moses, shifts the focus from game trees to knowledge-based programs. In Characterizing Solution Concepts in Games Using Knowledge-Based Programs, they show that "rationality" can be viewed as a consistent logic that produces different outcomes based on the agent's internal state. Imperfect recall is modeled endogenously: an agent's "information set" is simply what its current computational state allows it to know.
Strategic Forgetting as an Advantage
While limited memory is often seen as a constraint, it can also be a powerful tool for abstraction. In massive games like Poker, the game tree is too large to store. Jiri Cermak, Viliam Lisý, and Branislav Bošanský explore this in Automated Construction of Bounded-Loss Imperfect-Recall Abstractions in Extensive-Form Games. By teaching an AI to strategically "forget" irrelevant details, they can find near-optimal strategies using less than 1% of the memory required by traditional methods.
Fragmented Memory in Teams
Imperfect recall is also a natural feature of decentralized teams. Even if every individual has perfect recall, the team as a whole has imperfect recall because information known by one member might not be known by another. Luca Carminati and Nicola Gatti address this in A Marriage between Adversarial Team Games and 2-player Games. They model the team as a single coordinator who issues "prescriptions" to members, effectively bridging the gap between fragmented team memory and powerful 2-player game-solving tools.
New Frontiers in Optimization
Recent work has moved toward more robust optimization techniques for these NP-hard scenarios. Rui Zheng and Antonios Varvitsiotis introduced a framework using Sum-of-Squares (SOS) hierarchies in Solving Imperfect-Recall Games via Sum-of-Squares Optimization, providing finite convergence guarantees for finding equilibria in games where players forget their past.
Simultaneously, Brian Hu Zhang and Tuomas Sandholm discovered that Regret Matching (RM) algorithms—originally designed for two-player zero-sum games—are surprisingly effective optimizers for imperfect-recall decision problems, often outperforming standard gradient descent by orders of magnitude (Decision Making under Imperfect Recall: Algorithms and Benchmarks).
By relaxing the assumption of perfect recall, this research direction moves AI closer to the reality of physical hardware, biological constraints, and the strategic necessity of forgetting.