Constant Regret in Repeated Games: Why the Best Players Never Regret

> *"In the river of time, the true winners are not those who win every round, but those who look back and find every step taken without regret."*

This is an accessible walkthrough of a recent game theory paper showing that constant individual regret is achievable in general games—eliminating dependence on the time horizon entirely.

What Is "Regret"?

In game theory, regret is defined precisely:

> Regret = your actual cumulative payoff − the cumulative payoff of the best fixed strategy in hindsight.

A strategy is *no-regret* if average regret R(T)/T → 0 as the game runs for T rounds. Classic algorithms guarantee R(T) ≤ O(log T): average regret vanishes, but cumulative regret keeps growing—like a walker whose gait gets steadier yet drifts ever further from the start.

From Logarithmic to Constant Regret

The paper (Liu, Farina, Ozdaglar, *Constant Individual Regret in General Games*, arXiv:2608.31166) proposes a new algorithm, ECHO-OFTRL (Exponential Moving Average Cascade for High-Order Optimism, Optimistic Follow-The-Regularized-Leader), guaranteeing:

> Regret ≤ O(poly(N, log m_max))

where N is the number of players and m_max the largest action-set size—T disappears completely. No matter how long the game runs, total regret stays bounded by a constant.

The Name, Unpacked

• EMA (Exponential Moving Average): weight recent data more, like a sea captain trusting recent observations of currents without discarding history.
• Cascade: information flows layer by layer, like a waterfall.
• ECHO: signals reverberating and being refined through the cascade.
• OFTRL (Optimistic Follow-The-Regularized-Leader): predict the next round's payoffs before optimizing, like a chess player anticipating the opponent's reply.

Why "High-Order"?

Traditional methods use only first-order information (what happened). ECHO-OFTRL captures higher-order dynamics—the *rate of change* of payoffs and beyond, like a driver knowing not just speed but acceleration and its rate of change. This lets the algorithm sense when a trend's momentum is fading, not just that a trend exists. The authors note their optimism formulation was inspired by modern filter design: extracting signal from noisy game history.

Connection to Equilibrium

Nash proved equilibria *exist*, but not how decentralized agents reach them. A classical result: if every player runs a no-regret strategy, play converges to equilibrium with no central coordination and only private payoffs. Constant regret strengthens this guarantee dramatically.

Why It Matters

• Auction design: bidders using no-regret strategies drive spectrum auctions toward reasonable equilibria.
• Traffic routing: drivers learning without regret yield stable (though not necessarily optimal) flows.
• Financial markets: prices converge toward efficient states with no persistently ignored arbitrage.
• Decentralized systems: blockchains, P2P networks, and DAOs face the core problem of cooperation without central authority—no-regret learning provides a theoretical framework.
• Machine learning: gradient descent can be viewed as a no-regret algorithm; bandits and reinforcement learning share these ideas, so constant-regret tools may transfer broadly.

Closing Thought

Feynman: *"Knowing the name of something and understanding it are two very different things."* True understanding here means being able to make choices you won't regret under uncertainty—not winning every round, but always deciding with the best available information. Not just a theorem—a philosophy.

Reference

• Liu, M., Farina, G., Ozdaglar, A. (2026). *Constant Individual Regret in General Games*. arXiv:2608.31166.