Linear Last-Iterate Convergence Rates for Optimistic Learning in Harmonic Games

John Lazarsfeld, Anas Barakat, Jacob Abernethy, Vidya Muthukumar, Georgios Piliouras, Andre Wibisono, Juba ZianiarXiv 2026 · arXiv

TL;DR

This paper provides the first global, linear last-iterate convergence rates for optimistic learning algorithms (OFTRL and EGFTRL) in multiplayer harmonic games. By using a dual perspective, the authors demonstrate that "optimism" acts as a dissipative force that stabilizes learning, pulling agents toward a Nash equilibrium even in complex, non-constant-sum environments where standard algorithms typically fail.

What Problem Does This Paper Address?

In multi-agent reinforcement learning and game theory, we often distinguish between time-average and last-iterate convergence. While many "no-regret" algorithms are guaranteed to converge on average, their actual strategies (the last iterate) often fail to stabilize. In competitive settings, standard algorithms like Multiplicative Weights Update (MWU) frequently spiral outward, away from equilibrium, toward the boundaries of the strategy space.

While recent research has shown that "optimistic" variants of these algorithms can fix this spiraling behavior in two-player zero-sum games, the broader landscape of multiplayer, general-sum games remained a "Wild West." The authors tackle this by focusing on harmonic games—a broad class of games that capture strategic interactions with conflicting interests. Until now, it was known that optimistic methods converged eventually in these games, but how fast they converged (and why) remained an open question.

Methods

The authors analyze two primary algorithms:

  1. Optimistic Follow-The-Regularized-Leader (OFTRL): A framework that uses a "hint" of the next gradient to stabilize updates.
  2. Extragradient FTRL (EGFTRL): A related two-step update method.

Their "secret sauce" is a dual perspective. Instead of looking only at the strategies (primal space), they look at the "energy" of the system in the dual space.

Key technical components include:

  • Weighted Minty Variational Equality: They leverage a unique structural property of harmonic games where the game's loss operators satisfy a specific global balance condition.
  • Energy Dissipation: They prove that while the continuous-time "flow" of these games conserves energy (meaning it orbits the equilibrium forever), the discrete-time optimistic updates actually dissipate energy.
  • Implicit Coupling: The analysis works by "coupling" the optimistic updates to an idealized (but unimplementable) implicit update, showing that the optimistic version is a close enough approximation to inherit its stability.

Datasets

As a theoretical paper, no real-world datasets were used. Instead, the authors evaluated their findings using:

  • Synthetic Harmonic Games: Specifically, a 3-player polymatrix harmonic game and a non-linear harmonic game designed to test the limits of the theory.
  • Regularizers: The results were verified across a family of regularizers, including Shannon entropy (which yields the popular OMWU algorithm), Tsallis entropy, and log-barrier functions.

Key Insights and Ideas

  • Optimism as Friction: In physics terms, if a standard game is a frictionless pendulum swinging forever, "optimism" introduces a form of friction (dissipation) that causes the pendulum to settle at the bottom (the equilibrium).
  • Beyond Zero-Sum: The results prove that the benefits of optimistic learning aren't limited to zero-sum games. The "harmonic" structure is the true requirement for this type of stability.
  • Equilibrium Selection: The paper doesn't just say that the algorithm converges; it characterizes which equilibrium it will find based on the starting point and the choice of regularizer.
  • The "Gap" vs. Divergence: The authors establish a quantitative "separation." They prove that while optimistic methods converge linearly, vanilla (non-optimistic) FTRL actually diverges at a geometric rate in these same games.
Figure 1: Variants of FTRL (with entropy regularizer) on the 3-player harmonic game in A.4.1. Left: two trajectories of OFTRL converging to their distinct analytic limits (in green) from Theorem 4.1 (i). Right: Bregman divergence from NE for the t-th iterate of OFTRL, EGFTRL, and FTRL from a fixed initialization. OFTRL and EGFTRL converge linearly (Theorem 4.1(ii)), while FTRL diverges at a geometric rate (Theorem 4.5).

Key Results

  • Linear Convergence Rate: The authors prove that the Bregman divergence from the equilibrium decreases at a rate of $O(\exp(-\gamma \eta^2 t))$, where $t$ is the number of iterations. This is a "fast" rate of convergence.
  • Generality: The proof holds for any "relatively Legendre" regularizer, meaning it applies to a wide variety of common machine learning setups.
  • Polymatrix Games: For the specific case of linear (polymatrix) harmonic games, they show that the regularity conditions required for their proof are always satisfied.

Limitations and Future Work

  • Stepsize Constraints: The current proof requires a sufficiently small constant stepsize ($\eta$). In practice, finding this optimal stepsize can be difficult. The authors suggest that adaptive stepsize variants are a promising next step.
  • Instance Dependence: The convergence constant ($\gamma$) depends on the specific geometry of the game and the regularizer. A deeper understanding of how this constant scales with the number of players or actions is still needed.
  • General Games: Most games are not perfectly harmonic. However, any game can be decomposed into "potential" and "harmonic" parts. The authors hope their techniques can eventually be combined with potential game theory to provide a complete picture of learning in all finite games.

Summary updated

Abstract

We prove that the last iterate of Optimistic Follow-The-Regularized-Leader (OFTRL) converges at a linear rate to a Nash equilibrium in multiplayer harmonic games. Our result holds under a mild game-regularity condition and for a large family of regularizers, including entropy, Tsallis, and log-barrier. Our analysis is based on a dual perspective of OFTRL: we prove that the interaction between optimism and the global structure of harmonic games leads to the dissipation of an energy function along the dual iterates, for which we establish tight quantitative bounds. Our result also holds for the Extragradient FTRL variant.
BibTeX
@misc{lazarsfeld2026linear,
  author = {John Lazarsfeld and Anas Barakat and Jacob Abernethy and Vidya Muthukumar and Georgios Piliouras and Andre Wibisono and Juba Ziani},
  title = {{Linear Last-Iterate Convergence Rates for Optimistic Learning in Harmonic Games}},
  year = {2026},
  eprint = {2610.18560},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.18560},
}

Loading related content...

Figure