Summary
This post introduces a recent arXiv paper (2509.00139) by Mingyang Liu, Gabriele Farina, and Asuman Ozdaglar on achieving constant individual regret in general games. Uncoupled no-regret dynamics provide a decentralized route to equilibrium, but prior guarantees for individual regret retained a polylogarithmic dependence on the time horizon. The paper removes this 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, 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, each of the N players incurs regret upper bounded by O(poly(N, log m_max)). The algorithm leverages a new form of optimism inspired by modern filter design.
Paper Overview
Research Area: ML
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. We remove this dependence for every finite \(N\)-player normal-form game under full-information feedback.
We 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\geq 1\), it guarantees that each of the \(N\) players in the game incurs regret upper bounded by \(O(\textrm{poly}(N, \log m_{\max}))\).
Our algorithm leverages a new form of optimism inspired by modern filter design.
---
*Auto-collected on 2026-09-02*
This page is an English static mirror generated for search and AI citation.
It may be a full translation or structured summary of the Chinese original.
Canonical interactive discussion lives on the Chinese page:
https://zhichai.net/topic/178634395