Memory Asymmetry Creates Heteroclinic Orbits to Nash Equilibrium in Learning in Zero-Sum Games

Yuma Fujimoto, Kaito Ariu, Kenshi Abe

Abstract

Learning in games considers how multiple agents maximize their own rewards through repeated games. Memory, an ability that an agent changes his/her action depending on the history of actions in previous games, is often introduced into learning to explore more clever strategies and discuss the decision-making of real agents like humans. However, such games with memory are hard to analyze because they exhibit complex phenomena like chaotic dynamics or divergence from Nash equilibrium. In particular, how asymmetry in memory capacities between agents affects learning in games is still unclear. In response, this study formulates a gradient ascent algorithm in games with asymmetry memory capacities. To obtain theoretical insights into learning dynamics, we first consider a simple case of zero-sum games. We observe complex behavior, where learning dynamics draw a heteroclinic connection from unstable fixed points to stable ones. Despite this complexity, we analyze learning dynamics and prove local convergence to these stable fixed points, i.e., the Nash equilibria. We identify the mechanism driving this convergence: an agent with a longer memory learns to exploit the other, which in turn endows the other's utility function with strict concavity. We further numerically observe such convergence in various initial strategies, action numbers, and memory lengths. This study reveals a novel phenomenon due to memory asymmetry, providing fundamental strides in learning in games and new insights into computing equilibria.

Introduction

Learning in zero-sum games (like Rock-Paper-Scissors) is a classic "moving target" problem. Because one player’s gain is the other’s loss, agents using standard gradient-based learning often end up chasing each other in circles. In technical terms, the learning dynamics exhibit "cycling behavior" or "divergence."

Previous research showed that adding memory—allowing agents to choose actions based on previous rounds—often exacerbates this instability, leading to chaotic dynamics or faster divergence if both players have the same memory capacity. This paper, presented at AAAI-24, explores a counter-intuitive solution: What happens if the memory capacity is asymmetric? If Player X remembers more history than Player Y, does the "smarter" player stabilize the game or break it further?

Methods

The authors approach this through both rigorous mathematical proofs and numerical simulations. They model the game as a Markov Transition Process, where strategies are defined as the probability of taking an action given a specific history of previous actions.

The game is formulated as a Markov Transition Process where agents' strategies depend on the history of past rounds (memory).

They introduce Discretized Multi-Memory Gradient Ascent (MMGA), a variation of standard gradient ascent where agents update their strategies to maximize their "stationary state" payoff—the average reward they expect to receive over a long period. The theoretical analysis focuses on a two-action zero-sum game where Player X has a memory of one round ($n_X=1$) and Player Y has no memory ($n_Y=0$). By analyzing the Jacobian matrix of the learning dynamics, they identify "heteroclinic orbits"—trajectories in the strategy space that connect unstable fixed points to stable ones.

Key Insights: Exploitation as a Stabilizer

The most profound insight is why asymmetry leads to convergence. When Player X has a longer memory, they learn to exploit Player Y’s simpler, memoryless strategy. Mathematically, this exploitation "reshapes" Player Y’s utility function, making it strictly concave. In optimization, strict concavity is a powerful property that creates a clear peak for the gradient ascent to climb, effectively turning exploitation into a stabilizing force.

Furthermore, the authors show that the Nash Equilibrium of a standard game is divided into two regions when memory is added: one where fixed points are unstable (causing divergence) and one where they are stable. The dynamics follow specific heteroclinic orbits that "flee" from the unstable regions of the strategy space and "land" in the stable regions.

Key Results

The authors provide a formal proof (Theorem 4) that for any Nash Equilibrium satisfying a specific condition related to the exploitation of the opponent, the learning dynamics are locally asymptotically stable.

Comparison of learning dynamics in zero-sum games: without memory, agents cycle; with symmetric memory, they diverge; with asymmetric memory, they converge to the Nash equilibrium.

As shown in the figure above, simulations of Matching Pennies provide clear visual evidence of this phenomenon:

  • No memory: The agents cycle forever around the equilibrium.
  • Symmetric memory: The agents spiral away from the equilibrium (divergence).
  • Asymmetric memory: The agents spiral into the equilibrium (convergence).

These results were found to be scalable, holding true as the number of actions increased (up to 4) and for various memory lengths (e.g., a 2-memory agent vs. a 1-memory agent).

Limitations and Future Work

While the mathematical proof covers local stability, numerical simulations suggest global convergence (starting from anywhere in the strategy space), which remains an open challenge for formal proof. Additionally, while results for general memory lengths are promising, the rigorous theory currently focuses on the (1, 0) case. Finally, the computational cost of calculating the "stationary state" payoff gradient increases with memory length, potentially limiting applications to games with very long histories.

This research suggests a provocative new direction for AI safety and multi-agent systems: sometimes, to make a system stable, we shouldn't aim for perfect equality, but rather a strategic imbalance in agent capabilities.

Summary updated

Abstract

Learning in games considers how multiple agents maximize their own rewards through repeated games. Memory, an ability that an agent changes his/her action depending on the history of actions in previous games, is often introduced into learning to explore more clever strategies and discuss the decision-making of real agents like humans. However, such games with memory are hard to analyze because they exhibit complex phenomena like chaotic dynamics or divergence from Nash equilibrium. In particular, how asymmetry in memory capacities between agents affects learning in games is still unclear. In response, this study formulates a gradient ascent algorithm in games with asymmetry memory capacities. To obtain theoretical insights into learning dynamics, we first consider a simple case of zero-sum games. We observe complex behavior, where learning dynamics draw a heteroclinic connection from unstable fixed points to stable ones. Despite this complexity, we analyze learning dynamics and prove local convergence to these stable fixed points, i.e., the Nash equilibria. We identify the mechanism driving this convergence: an agent with a longer memory learns to exploit the other, which in turn endows the other's utility function with strict concavity. We further numerically observe such convergence in various initial strategies, action numbers, and memory lengths. This study reveals a novel phenomenon due to memory asymmetry, providing fundamental strides in learning in games and new insights into computing equilibria.
BibTeX
@inproceedings{fujimoto2024memory,
  author = {Yuma Fujimoto and Kaito Ariu and Kenshi Abe},
  title = {{Memory Asymmetry Creates Heteroclinic Orbits to Nash Equilibrium in Learning in Zero-Sum Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=0t62pZHksn},
}
Figure