Convergence of Multi-Agent Learning with a Finite Step Size in General-Sum Games

Xinliang Song, Tonghan Wang, Chongjie Zhang

Introduction

In the field of multi-agent learning (MAL), agents face a "moving target" problem: as each agent adapts its strategy to maximize rewards, the environment becomes non-stationary. Standard gradient ascent often fails in these settings, resulting in perpetual oscillations—most famously seen in games like Rock-Paper-Scissors—or outright divergence. While existing algorithms like Infinitesimal Gradient Ascent (IGA) offer theoretical convergence, they typically rely on the impractical assumption of an infinitesimal learning rate.

This paper introduces Gradient Ascent with Shrinking Policy Prediction (GA-SPP), a novel algorithm designed to achieve Nash convergence in general-sum games using a practical, finite step size. By allowing agents to "look ahead" and adjust their strategies based on a forecast of their opponent's next move, GA-SPP provides stronger theoretical guarantees and better empirical performance than previous gradient-based methods.

The GA-SPP Algorithm

GA-SPP improves upon previous methods by incorporating a "look-ahead" mechanism. The algorithm proceeds through three distinct phases:

  1. Forecast: Each agent predicts the opponent's next move by taking a small step along the opponent's current gradient. This forecast is projected back into the valid probability simplex to ensure strategy validity.
  2. Update: Instead of reacting to the opponent's current strategy, the agent updates its own strategy based on the forecasted move.
  3. Shrink: To ensure convergence to a true Nash Equilibrium, the algorithm dynamically "shrinks" the prediction length ((\gamma)) if it detects a lack of convergence.

This combination of projection and a flexible, shrinking prediction length allows GA-SPP to maintain stability even with a non-zero learning rate ((\eta)).

Theoretical Foundations and Dynamics

A core insight of this work is that anticipation acts as a damping force. By reacting to an opponent's trajectory rather than their current state, agents introduce a form of "friction" into the learning dynamics, preventing the circular cycles typical of zero-sum-like interactions.

Vector field dynamics illustrating the difference between real and plural eigenvalues in the strategy space. Plural eigenvalues (b) typically lead to the oscillations that GA-SPP aims to dampen.

The authors utilize the concept of Positive Semi-Definite (PSD) games to bridge the gap between zero-sum and general-sum games. They provide formal proofs of convergence for (m \times n) PSD games, a subclass of (2 \times n) general-sum games, and all (2 \times 2) general-sum games. Crucially, these guarantees hold for fixed, finite step sizes.

Empirical Performance

The algorithm was evaluated against standard benchmark matrix games, including the Prisoners’ Dilemma, Chicken, Battle of the Sexes, and Rock-Paper-Scissors.

Convergence of row player strategies over iteration steps across four benchmark games. Note the damped oscillations in Rock-Paper-Scissors leading to a stable equilibrium.

Beyond simple (2 \times 2) games, GA-SPP demonstrated superior robustness in more complex scenarios like Shapley’s Game ((3 \times 3)) and (2 \times 3) general-sum games. While benchmark algorithms like GIGA-WoLF continued to oscillate in Shapley’s Game, GA-SPP successfully converged to the Nash Equilibrium. Furthermore, GA-SPP showed less sensitivity to hyperparameter selection compared to its predecessor, IGA-PP.

Limitations and Future Outlook

Despite its strengths, GA-SPP currently requires agents to have full knowledge of the opponent's strategy and gradient, which may not be available in "black box" environments. Additionally, the algorithm struggles with the chaotic, non-linear dynamics of games involving three or more players, as seen in the Three-player Matching Pennies case. Future research will focus on extending these principles to stochastic settings and reinforcement learning, where payoffs are sampled rather than known a priori.

Summary updated

BibTeX
@inproceedings{song2019convergence,
  author = {Xinliang Song and Tonghan Wang and Chongjie Zhang},
  title = {{Convergence of Multi-Agent Learning with a Finite Step Size in General-Sum Games}},
  booktitle = {AAMAS},
  year = {2019},
  url = {https://openreview.net/forum?id=KIakVTdzkd},
}
Figure