Constant Individual Regret in General Games

Paper: 2608.31166 Authors: Mingyang Liu, Gabriele Farina, Asuman Ozdaglar Categories: cs.LG, cs.GT

The Gap

Uncoupled no-regret dynamics are the standard decentralized story for reaching equilibrium: each player runs their own learning algorithm, observes only their own payoffs, and the joint behaviour converges. The appeal is that nothing is coordinated — no shared clock, no central authority, no communication.

The guarantee has been about individual regret: how much a player loses relative to the best fixed action in hindsight. And it always carried a polylogarithmic dependence on the horizon — the bound grows, slowly but without limit, as the game runs longer. So the promise is asymptotic. A player cannot say “after this many rounds my regret is at most some constant”; they can only say it grows slower than the horizon.

The distinction is not pedantic. A bound that grows with time means the worst-case gap between a player’s play and the best fixed action never closes. For a decentralized protocol to give a meaningful guarantee — one you could state as a number rather than as a rate — the horizon has to leave the bound.

   UNCOUPLED NO-REGRET DYNAMICS

   each player runs their OWN learning algorithm
     observes only their OWN payoffs
     no shared clock, no central authority, no communication
        |
        v
   guarantee: INDIVIDUAL REGRET
     = loss relative to the best fixed action in hindsight
        |
        v
   PRIOR STATE: polylogarithmic dependence on the horizon
     -> the bound GROWS with time, slowly but without limit
     -> the promise is ASYMPTOTIC
     -> a player cannot say "my regret is at most C"
        only "it grows slower than T"
        |
        v
   [GAP] a bound that grows with time means the worst-case
         gap never closes -> no guarantee statable as a NUMBER

The Increment

One sentence: Before this paper, individual regret in general games grew polylogarithmically with the horizon; after it, ECHO-OFTRL bounds it by a quantity depending only on the number of players and the sizes of their action sets — for every horizon simultaneously.

Core Mechanism

The algorithm is ECHO-OFTRL: optimistic follow-the-regularized-leader, equipped with an EMA cascade for high-order optimism. The acronyms decompose cleanly: OFTRL is the well-established optimistic variant of follow-the-regularized-leader, and ECHO is the new part — an exponential moving average cascade that supplies high-order optimism. Where ordinary optimism predicts the next gradient from the most recent one, a cascade of exponential moving averages builds a prediction from a hierarchy of timescales, which is what makes higher-order prediction possible.

Two properties keep it usable as a decentralized protocol. It is deterministic — no randomness to coordinate or to argue about, which matters for reproducibility in a distributed setting. And it is fully uncoupled — each player’s update depends only on their own observations, so the decentralization claim survives intact. An algorithm that reached a constant regret bound but required shared state would have solved a different problem.

The guarantee is stated precisely, and the quantifiers are the substance. Let m_max be the largest action-set size. Then, simultaneously for every horizon T at least 1, each of the N players incurs regret bounded above by O(poly(N, log m_max)).

Every part of that sentence is doing work. Simultaneously for every horizon is the result: not a bound that holds at each T with a T-dependent constant, but one expression valid at all horizons at once. poly(N, log m_max) contains no T at all, which is the constant-regret claim — regret that does not grow with how long the game runs. And log m_max means the bound is essentially insensitive to how many actions are available, which is the practically important dependence: a player facing a huge action set pays logarithmically, not linearly.

The mechanism behind the improvement is described as a new form of optimism inspired by modern filter design. That framing is worth noting on its own, because it is the source of the technique rather than an analogy applied afterwards: the exponential moving average cascade is a filter, the horizon-independence follows from choosing the right filter order, and the problem was that nobody had imported the right design principle from that literature.

   ECHO-OFTRL

   optimistic follow-the-regularized-leader (OFTRL)   [known]
        +
   EMA CASCADE for HIGH-ORDER optimism (ECHO)          [new]
     ordinary optimism: predict next gradient from the
                        most recent one
     cascade: build the prediction from a HIERARCHY of
              timescales -> higher-order prediction
        |
        v
   PROPERTIES
     DETERMINISTIC   (nothing to coordinate or argue about)
     FULLY UNCOUPLED (depends only on own observations)
        -> the decentralization claim survives

   GUARANTEE (m_max = largest action-set size)
     simultaneously for EVERY horizon T >= 1:
       each of the N players' regret
         <= O( poly(N, log m_max) )
        -> NO T in the bound: the constant-regret claim
        -> log m_max: essentially insensitive to action count

   SOURCE OF THE TECHNIQUE
     a new form of optimism INSPIRED BY MODERN FILTER DESIGN
     the EMA cascade IS a filter; horizon-independence follows
     from choosing the right filter ORDER

Think of it as tuning a control system so its error settles to a fixed band rather than drifting with the length of the run. A controller whose error grows slowly with time is better than one whose error grows quickly, and both are different from a controller whose error is bounded by a constant you can state up front. What gets you there is not a bigger correction term but a better predictor: a controller that only looks at the last measurement lags, and one that averages over several timescales anticipates. That is the cascade — the same idea as a well-designed filter that separates a trend from the noise riding on it. And the property that makes it a decentralized result rather than a control-theoretic curiosity is that each player builds their own predictor from their own history, with nothing shared.

Key Concepts

• Individual regret as the guarantee: the loss relative to the best fixed action in hindsight, measured per player. It is the weaker and more natural notion for uncoupled dynamics, and it is where the horizon dependence lived.
• Constant regret: a bound containing no horizon term, holding at all horizons simultaneously. It converts an asymptotic promise into a number, which is what makes the guarantee usable in a protocol rather than as a statement about limits.
• High-order optimism via an EMA cascade: predicting the next gradient from a hierarchy of timescales rather than the most recent observation. It is the mechanism delivering horizon-independence, and it is imported from filter design rather than derived within the usual regret-analysis toolkit.
• Logarithmic dependence on action-set size: log m_max where a naive bound would be linear. It is the practical dependence, since action spaces in real games are large and a linear penalty would make the guarantee vacuous.
• Deterministic and fully uncoupled: the properties that keep it a decentralized algorithm. A constant bound requiring shared state would not answer the question that was asked.

Framework Shift

Before (asymptotic, horizon-dependent):
  uncoupled players, individual regret
  bound carries polylog(T)
  -> regret grows without limit, slowly
  -> guarantee stated as a RATE
  -> worst-case gap to best fixed action never closes

After (horizon-free):
  ECHO-OFTRL = OFTRL + EMA cascade for high-order optimism
  deterministic, fully uncoupled
  simultaneously for every T >= 1:
    regret <= O(poly(N, log m_max))
  -> guarantee stated as a NUMBER
  -> technique imported from filter design

From a guarantee that regret grows more slowly than the horizon, to a guarantee that regret is bounded by a constant depending only on the game’s size, the core shift is that the horizon can be removed from the bound rather than merely suppressed in it.

Expert Assessment

Problem choice: Strong, and it targets the gap between an asymptotic story and a usable guarantee. No-regret dynamics are the foundation of decentralized learning, and a bound that grows with time is exactly the part that prevents the theory from being cashed out as a protocol guarantee.

Method maturity: The result is clean and the algorithm is stated with its properties attached — deterministic, uncoupled, with quantifiers that hold for all horizons at once. The most interesting aspect is the provenance of the technique: importing high-order optimism from filter design, rather than searching within the standard regret-analysis repertoire, is what produced the improvement, and it suggests the analogy had been available to anyone who looked. The bound’s dependence structure is also right: poly(N, log m_max) is a dependence on the game’s size rather than on its duration, which is what one wants.

Experimental integrity: These are theorem statements, so the scrutiny is on the assumptions. Full-information feedback is the substantive one — each player observes their own full payoff vector after each round — and it is the strongest of the standard feedback models. Whether the horizon-free guarantee survives under bandit feedback, where a player learns only the payoff of the action taken, is a genuinely open question the paper does not claim to settle, and it is the direction a practitioner would immediately ask about.

Writing quality: The abstract is unusually well-constructed for a theory paper: it names the prior limitation, states the algorithm, gives the bound with explicit quantifiers, and identifies the source of the idea. Because the contribution is a removal of a dependence, stating what remains in the bound — poly(N, log m_max) — is exactly the right way to communicate it.

Verdict: strong accept — a sharp improvement to a foundational guarantee, with a technique whose provenance suggests a broader transfer between filter design and regret analysis.

Takeaways

• Prefer bounds without the horizon in them. A guarantee that contains no time term can be stated as a number; one that does cannot be cashed out as a protocol guarantee.
• Check what a bound depends on, not just its order. log m_max versus a linear action-set dependence is the difference between a usable guarantee and a vacuous one.
• Look outside a field’s usual toolkit for structural improvements. High-order optimism here came from filter design, and horizon-independence followed from choosing the right filter order.
• Note which feedback model a result assumes. Full-information feedback is the strongest standard setting, and it is worth knowing whether a guarantee carries over to bandit feedback before relying on it.