Learning in Multi-Memory Games Triggers Complex Dynamics Diverging from Nash Equilibrium

Yuma Fujimoto, Kaito Ariu, Kenshi Abe

Abstract

Repeated games consider a situation where multiple agents are motivated by their independent rewards throughout learning. In general, the dynamics of their learning become complex. Especially when their rewards compete with each other like zero-sum games, the dynamics often do not converge to their optimum, i.e., the Nash equilibrium. To tackle such complexity, many studies have understood various learning algorithms as dynamical systems and discovered qualitative insights among the algorithms. However, such studies have yet to handle multi-memory games (where agents can memorize actions they played in the past and choose their actions based on their memories), even though memorization plays a pivotal role in artificial intelligence and interpersonal relationship. This study extends two major learning algorithms in games, i.e., replicator dynamics and gradient ascent, into multi-memory games. Then, we prove their dynamics are identical. Furthermore, theoretically and experimentally, we clarify that the learning dynamics diverge from the Nash equilibrium in multi-memory zero-sum games and reach heteroclinic cycles (sojourn longer around the boundary of the strategy space), providing a fundamental advance in learning in games.

Introduction

In game theory, the Nash Equilibrium (NE) represents a state of stability where no player can improve their payoff by unilaterally changing their strategy. While learning dynamics in zero-memory games—where agents react only to the current state—are well-documented as often forming stable orbits around the NE, the impact of memory remains poorly understood. This paper investigates how the introduction of memory, a fundamental component of human and artificial intelligence, alters the stability of learning in repeated zero-sum games.

The Multi-Memory Framework

The researchers extend two foundational learning models to the multi-memory domain: Multi-Memory Replicator Dynamics (MMRD) and Multi-Memory Gradient Ascent (MMGA). In these models, agents maintain a memory of past actions, using this history to inform their current strategy.

Figure 1: Schematic representation of a multi-memory game where the state $s_i$ is determined by a sequence of past actions, influencing the strategy in the present round.

A significant theoretical finding of this work is the "Continuous-Time Equivalence." The authors prove that in the limit of infinitesimal learning steps, MMRD and MMGA are mathematically identical. This unification allows for a singular theoretical analysis of memory-based learning trajectories.

Divergence from Equilibrium

Contrary to zero-memory games where agents typically orbit the NE in stable loops, multi-memory agents exhibit fundamentally different behavior. The authors demonstrate that in zero-sum games, the distance to the NE (measured by Kullback-Leibler divergence) does not remain constant; instead, it increases over time.

Figure 5: Strategy trajectories ($x_i$) and distance from equilibrium over time. The spikes in the maximum eigenvalue indicate periods of high instability and sensitivity.

As shown in the simulations, the learning dynamics spiral outward, eventually reaching "heteroclinic cycles." In these cycles, agents spend prolonged periods at the boundaries of the strategy space—playing nearly pure strategies—before rapidly transitioning to another extreme. This behavior is characterized by extreme sensitivity to initial conditions, a hallmark of chaotic systems.

Key Findings and Implications

  • Mathematical Origin of Instability: Using Taylor expansions, the study identifies that second-order terms in the learning dynamics are the primary drivers of divergence from the NE.
  • Unchanged Equilibrium Points: Interestingly, the addition of memory does not create new Nash Equilibria in one-memory two-action zero-sum games; it merely destabilizes the path toward the existing one.
  • Algorithmic Equivalence: Theorem 3 formally unifies Replicator Dynamics and Gradient Ascent in the context of multi-memory games, bridging two previously separate research areas.

Conclusion and Future Directions

This research reveals that memory, while enhancing an agent's ability to recognize patterns, fundamentally destabilizes learning in competitive environments. The resulting chaotic divergence poses a significant challenge for multi-agent reinforcement learning. Future work must address the "curse of dimensionality" as memory length increases and seek new classes of algorithms capable of achieving convergence in high-dimensional, memory-rich strategy spaces.

Summary updated

Abstract

Repeated games consider a situation where multiple agents are motivated by their independent rewards throughout learning. In general, the dynamics of their learning become complex. Especially when their rewards compete with each other like zero-sum games, the dynamics often do not converge to their optimum, i.e., the Nash equilibrium. To tackle such complexity, many studies have understood various learning algorithms as dynamical systems and discovered qualitative insights among the algorithms. However, such studies have yet to handle multi-memory games (where agents can memorize actions they played in the past and choose their actions based on their memories), even though memorization plays a pivotal role in artificial intelligence and interpersonal relationship. This study extends two major learning algorithms in games, i.e., replicator dynamics and gradient ascent, into multi-memory games. Then, we prove their dynamics are identical. Furthermore, theoretically and experimentally, we clarify that the learning dynamics diverge from the Nash equilibrium in multi-memory zero-sum games and reach heteroclinic cycles (sojourn longer around the boundary of the strategy space), providing a fundamental advance in learning in games.
BibTeX
@inproceedings{fujimoto2023learning,
  author = {Yuma Fujimoto and Kaito Ariu and Kenshi Abe},
  title = {{Learning in Multi-Memory Games Triggers Complex Dynamics Diverging from Nash Equilibrium}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=W5DS82rfCyq},
}
Figure