On the Last-iterate Convergence in Time-varying Zero-sum Games: Extra Gradient Succeeds where Optimism Fails

Yi Feng, Hu Fu, Qun Hu, Ping Li, Ioannis Panageas, Bo Peng, Xiao Wang

Introduction

In the landscape of game theory and machine learning—particularly in the training of Generative Adversarial Networks (GANs)—the search for a Nash Equilibrium is a central challenge. Traditionally, optimization algorithms are evaluated in static environments where the payoff matrix remains constant. In these settings, two algorithms have emerged as the gold standard for achieving "last-iterate convergence": Extra Gradient (EG) and Optimistic Gradient Descent Ascent (OGDA).

However, real-world applications are rarely static. Environmental shifts, seasonal cycles, or decaying noise mean that the underlying game dynamics often evolve over time. This paper investigates a fundamental question: Do these algorithms maintain their convergence guarantees when the game itself is time-varying? The research reveals a surprising theoretical "divorce" between EG and OGDA, demonstrating that while they appear similar in static games, their behaviors diverge drastically in dynamic settings.

The Challenge of Time-Varying Games

The authors focus on two primary types of non-static environments:

  1. Periodic Games: Where the game's rules repeat in a cycle (e.g., representing seasonal effects or recurring system states).
  2. Convergent Perturbed Games: Where the game begins with external noise or influence that gradually vanishes, eventually stabilizing into a static state.

To analyze these, the study models the learning process as a non-autonomous linear difference system. Unlike static games, which are governed by a single fixed matrix, time-varying games involve a sequence of different matrices, requiring more sophisticated tools from dynamical systems theory, such as the Floquet theorem and Gronwall inequalities.

Methodology and Algorithms

The study evaluates three prominent gradient-based methods:

  • Extra Gradient (EG): This method utilizes a "look-ahead" step, calculating a gradient at a predicted future point before committing to the actual update.
  • Optimistic Gradient Descent Ascent (OGDA): This approach uses the gradient from the previous iteration as a "hint" or predictor for the current step's direction.
  • Negative Momentum (NM): An alternating method that incorporates past movement to stabilize current updates.

While these methods are often considered closely related "cousins" in optimization literature, this paper provides the first clear evidence that they are qualitatively different when the game's payoff matrix is not constant.

Key Insights: The Power of Normality

The core technical discovery of the paper lies in the mathematical structure of the algorithms' update rules. The authors identify that the iterative matrix for the Extra Gradient (EG) algorithm is "normal" (it commutes with its transpose). This property is crucial for stability; it allows EG to effectively "average out" the fluctuations in a periodic environment.

In contrast, OGDA and Momentum methods lack this inherent symmetry. In periodic environments, these algorithms can be "tricked" by the shifting payoff matrix, leading to a feedback loop where errors compound rather than cancel out. This lack of stability can result in exponential divergence from the equilibrium, even when the step size is infinitesimally small.

Theoretical and Experimental Results

The paper presents several landmark findings:

  • Periodic Convergence: Theorem 3.1 proves that EG converges at an exponential rate in periodic games, successfully navigating the cyclic changes to find the equilibrium.
  • The Failure of Optimism: Theorem 3.2 provides a concrete counter-example—a simple period-2 game—where OGDA and Momentum methods diverge exponentially. This proves that optimism is not robust to even the simplest periodic perturbations.
  • Resilience to Noise: In perturbed games (where noise eventually vanishes), EG is shown to be significantly more resilient. While OGDA and Momentum require the noise to vanish at a specific, rapid rate (the BAP assumption) to ensure convergence, EG converges as long as the noise eventually disappears.

These theoretical results were validated through synthetic numerical experiments. Using $2 \times 2$ payoff matrices, the authors demonstrated that the strategy distance ($\Delta_t$) for EG consistently drops to zero, while for OGDA, it explodes toward infinity under the same periodic conditions.

Limitations and Future Directions

While this research provides a significant leap in understanding dynamic game optimization, it focuses primarily on unconstrained bilinear games, where strategies are represented by any real number. Many real-world games involve constraints (such as strategies being limited to probability distributions). Extending these proofs to constrained settings remains a vital area for future work.

Additionally, the study is currently restricted to two-player zero-sum games. As machine learning moves toward multi-agent systems, exploring how these algorithms behave in multi-player or general-sum time-varying games will be essential for developing robust AI agents in changing environments.

Summary updated

BibTeX
@inproceedings{feng2023last,
  author = {Yi Feng and Hu Fu and Qun Hu and Ping Li and Ioannis Panageas and Bo Peng and Xiao Wang},
  title = {{On the Last-iterate Convergence in Time-varying Zero-sum Games: Extra Gradient Succeeds where Optimism Fails}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=3CJOaJugMG},
}
Figure