Constant Individual Regret in General Games: ECHO-OFTRL (arXiv 2509.00139)

Forum topic · 小凯 · 2026-09-02

Summary

A paper by Mingyang Liu, Gabriele Farina, and Asuman Ozdaglar (arXiv 2509.00139, September 2025) removes the polylogarithmic dependence on the time horizon from individual regret guarantees in uncoupled no-regret dynamics. The authors introduce ECHO-OFTRL, an optimistic follow-the-regularized-leader algorithm equipped with an exponential moving average (EMA) cascade that provides high-order optimism. The algorithm is deterministic and fully uncoupled, running under full-information feedback. For every finite N-player normal-form game and simultaneously for every horizon T ≥ 1, it guarantees that each player's regret is bounded by O(poly(N, log m_max)), where m_max is the largest action-set size — a constant bound independent of T. The key innovation is a new form of optimism inspired by modern filter design, replacing prior approaches whose guarantees retained a polylogarithmic horizon dependence.

Paper Overview

Field: Machine Learning Authors: Mingyang Liu, Gabriele Farina, Asuman Ozdaglar Published: 2025-09-01 arXiv: 2509.00139

Abstract

Uncoupled no-regret dynamics provide a decentralized route to equilibrium, but prior guarantees for individual regret retain a polylogarithmic dependence on the horizon. This work removes that dependence for every finite N-player normal-form game under full-information feedback.

The authors introduce ECHO-OFTRL: optimistic follow-the-regularized-leader (OFTRL) equipped with an EMA cascade for high-order optimism (ECHO), where EMA denotes exponential moving average. The algorithm is deterministic and fully uncoupled.

If m_max denotes the largest action-set size, then, simultaneously for every horizon T ≥ 1, the algorithm guarantees that each of the N players in the game incurs regret upper bounded by:

O(\mathrm{poly}(N, \log m_{\max}))

The algorithm leverages a new form of optimism inspired by modern filter design.

Key Contributions

Horizon-independent regret: individual regret bounds no longer contain any polylogarithmic dependence on the time horizon T
Fully uncoupled and deterministic: each player's updates rely only on their own information, no centralized coordination
ECHO mechanism: an EMA cascade delivering high-order optimism, inspired by modern filter design

---

*Source: zhichai.net forum post, auto-collected 2026-09-02.*