Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation

Yuval Dagan, Nadav Eisen, Liad Erez, Tomer KorenarXiv 2026 · arXiv

This paper, titled "Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation," provides a definitive answer to a long-standing question in algorithmic game theory: How well does the "Optimistic Hedge" algorithm actually perform when multiple players are competing in a general-sum game?

TL;DR

The researchers show that the number of players fundamentally changes the efficiency of Optimistic Hedge. While two-player games allow for "constant" regret (independent of time and polynomial in game size), adding just one more player can trigger an exponential barrier, causing regret to explode or even grow linearly over time.

What Problem Does This Paper Address?

In the world of "no-regret learning," an agent tries to perform as well as the best fixed action in hindsight. The classic Hedge (or Multiplicative Weights) algorithm is a staple, but it typically suffers regret that grows with the square root of time ($O(\sqrt{T})$).

Optimistic Hedge (OH) is a "smarter" version that uses the most recent loss as a prediction for the next one. In certain settings, like zero-sum games, OH is incredibly efficient, leading to much smaller regret. However, its performance in general-sum games (where players' interests aren't perfectly opposed) has been a mystery. Recent work suggested OH might achieve "constant regret"—meaning the total regret doesn't grow with time at all—but it wasn't clear if this bound would scale reasonably with the number of actions ($n$) or players ($m$).

The authors set out to determine if OH guarantees regret that is polynomial in the game's size and independent of the time horizon.

Methods

The authors introduce a new Temporal Approximation Framework to analyze the dynamics of the algorithm.

  1. Upper Bounds (The "Good" News): They break the timeline into short "windows." Within these windows, they approximate the players' losses using simple functions.
  2. For $m$ players, they use polynomials.
  3. For 2 players, they use sums of exponentials. By proving that these approximating functions satisfy a "variation-variance inequality" (meaning their movement is bounded by their stability), they can sum up the regret across the entire timeline.

  4. Lower Bounds (The "Bad" News): To prove OH can fail, they construct a specific three-player game. They use a "cascade of blocks" mechanism. Each block of actions is designed to oscillate twice as fast as the previous one. This "frequency doubling" allows them to create very high-frequency oscillations even with a small learning rate.

Datasets

Not discussed in the paper. This is a theoretical work based on mathematical proofs and synthetic game constructions rather than empirical datasets.

Key Insights and Ideas

  • The Two-Player Feedback Loop: The paper reveals that two-player games have a special "closed-loop" property. Player 1’s losses only change if Player 2 moves, and Player 2 only moves if Player 1’s losses vary. This mutual dependence keeps the system stable, allowing for a constant regret bound of $O(n \log n)$.
  • The Third Player as a "Spoiler": Adding a third player breaks this loop. The co-dynamics of Players 2 and 3 can create "drift" in Player 1's losses that isn't tied to Player 1's own movement. This decoupling is the root of the exponential regret.
  • Optimism Can Backfire: Optimism works by betting that the next round will look like the last. If the game oscillates too quickly (specifically, with a period of 4 rounds), the "optimistic" prediction becomes perfectly out of phase—it predicts a high loss exactly when the loss is low, and vice versa. This turns the algorithm's strength into a weakness, leading to linear regret.
  • Frequency Doubling: The authors show that you can "squeeze" high-frequency signals out of a slow-moving algorithm by using many actions. This is how they prove that the exponential barrier is tied to the number of actions $n$.

Key Results

  • Two Players: Proved a constant regret bound of $O(n \log n)$, which is independent of the time horizon $T$ and polynomial in the number of actions.
  • Three or More Players: Proved an exponential barrier. There exist games where at least one player suffers regret of $2^{\Omega(n)}$ (or $2^{\Omega(mn)}$ for $m$ players).
  • Linear Regret: If the learning rate is above a certain threshold ($2^{-\Omega(mn)}$), the regret can actually grow linearly with $T$, meaning the algorithm fails to learn the game effectively.
  • Simplified Analysis: Their framework provides a much simpler proof for the known logarithmic regret bound of $O(\sqrt{m} \log n \log T)$ for general $m$-player games.

Limitations and Future Work

The lower bound relies on a very specific, carefully engineered "cascade" game. A natural question is whether these "pathological" oscillations occur in more common or "natural" games.

Additionally, the study focuses on a fixed learning rate. While the paper shows that no fixed learning rate can save OH from the exponential barrier in three-player games, it leaves open the possibility that adaptive learning rates or more complex "higher-order" optimistic algorithms (which track more than just the last step) might perform better. Indeed, the authors note that more elaborate dynamics have recently been shown to bypass these limits.

Summary updated

Abstract

Optimistic Hedge, a multiplicative weight update with one step of extrapolation, is one of the most natural regret-minimizing dynamics for games, and characterizing its regret has been a longstanding open question. Daskalakis, Fishelson and Golowich proved that if all $m$ players in a finite general-sum game follow Optimistic Hedge with a fixed learning rate, each player's regret is polylogarithmic in the horizon $T$. Subsequently, Ha showed that an appropriate choice of learning rate makes each player's regret bounded independently of $T$. This bound, however, is non-constructive and its dependence on the number of actions $n$ is not explicit, leaving open whether Optimistic Hedge can achieve a constant regret bound which is polynomial in the size of the game. We show that the answer hinges on the number of players. In two-player games, there is a learning rate for which Optimistic Hedge guarantees $O(n\log n)$ regret independent of the horizon. In three-player games, however, no such bound is possible: for any learning rate up to an absolute constant and for sufficiently large horizon $T$, there is a game with $n$ actions per player in which some player's regret is $2^{Ω(n)}$, and more generally, for every $m\ge3$ we construct $m$-player games in which some player's regret is $2^{Ω(mn)}$; for learning rates above $2^{-Ω(mn)}$, that player's regret even grows linearly in $T$. Our upper bound is based on a temporal approximation framework for the analysis of Optimistic Hedge. Starting from the variance-based RVU bound of Daskalakis et al., we approximate the losses over time-localized windows by well-behaved functions, whose total variation is a small fraction of their cumulative variance. In $m$-player games, the same framework gives a significantly simplified proof of the recent $O(\sqrt{m}\log n\log T)$ regret bound due to Ha.
BibTeX
@misc{dagan2026optimistic,
  author = {Yuval Dagan and Nadav Eisen and Liad Erez and Tomer Koren},
  title = {{Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation}},
  year = {2026},
  eprint = {2611.07078},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.07078},
}
Figure