Constant regret in general games via higher-order optimism

TL;DR: A decades-old question in game theory asks whether players can learn in any finite game such that their regret stays bounded forever—not growing like \sqrt{T}, not even like \log T, but genuinely constant in the horizon T. This paper answers yes, with an explicit algorithm (HOOD) guaranteeing each of N players at most O(N^3 \log^2 K) regret over an infinite trajectory of play, where K is the number of actions. The mechanism—an (N+1)-th order discounted optimistic predictor combined with a carefully engineered "lifted" entropy regularizer—is new, and a concurrent independent paper (Liu, Farina, Ozdaglar) reached the same qualitative conclusion with a much worse constant (N^{21} \log^4 K), which strongly suggests this is a real resolution, not a fluke.

The question that stayed open

Picture N players repeatedly playing a finite game. Each round, every player picks a mixed strategy, then observes their full payoff vector (their expected payoff against each of their own actions, given what everyone else did). The player's external regret after T rounds is

i.e., how much better the single best fixed action would have done in hindsight against the actual sequence of opponents' play.

Against a fully adversarial payoff sequence, \Theta(\sqrt{T}) regret is information-theoretically unavoidable—Hedge achieves it and nothing beats it. But when all players run a learning algorithm, the payoff stream each player sees isn't adversarial: it's generated by other learners, whose strategies drift slowly. This predictability is exploitable. Optimistic algorithms (OFTRL, which biases each update with a prediction of the next payoff vector) turned this into a striking cascade of improvements in general games:

Constant regret was already known in structured games—two-player zero-sum, potential games, harmonic games—where a variational structure tames the dynamics. In arbitrary games no such structure exists; one player's movement can amplify another's, and the best known bounds stalled at O(\log T). The open question was whether that residual \log T was fundamental. This paper (and its concurrent twin) says it is not.

Theorem (informal). If every player of an N-player game with \le K actions runs HOOD with step size \eta = 1/[60(N+1)^3], then for every player and every T,

The algorithm is uncoupled (each player uses only their own feedback plus the numbers N, K), horizon-free (no T in any parameter), and the bound holds uniformly over all T—so total lifetime regret is finite. A standard consequence: the empirical distribution of play converges to the game's coarse correlated equilibria at rate O(1/T), the fastest possible.

Why optimism alone gets stuck

The engine of all these results is the RVU (Regret bounded by Variation in Utilities) inequality for OFTRL. Writing e_{i,t} = g_{i,t} - m_{i,t} for the prediction error (actual payoff vector minus predicted), it says roughly

where \Omega is the regularizer's range and \eta the step size. The dream is a bootstrap: if regret were nonnegative, this inequality would bound the movement of play by the prediction error; if you could conversely bound the prediction error by the movement, the two inequalities close into a constant. Two things break the dream:

1. Regret can be negative. Then the left-hand side gives no leverage—one player's large positive regret can hide behind another's large negative regret in the aggregate, and the movement isn't actually controlled.
2. First-order prediction is too weak. The classical optimistic predictor m_t = g_{t-1} makes the error a first time-difference of payoffs, and in a general game one difference of payoffs is not small enough to feed back into the movement bound with room to spare.

HOOD fixes each with a dedicated ingredient.

Ingredient one: lift the simplex so regret can't hide below zero

Following Farina et al., the update is run not on the probability simplex \mathcal{X}_K but on the "corner" simplex \mathcal{K} = \{z \ge 0 : \langle \mathbf{1}, z\rangle \le 1\}, which contains the origin. Every nonzero point factors as z = \lambda x with mass \lambda \in (0,1] and a genuine mixed strategy x. Because payoffs are centered so that \langle x_{i,t}, g_{i,t}\rangle = 0, the comparator in the lifted problem becomes

the positive part of regret—the origin acts as a floor. Now the RVU left-hand side is nonnegative by construction, and the movement bound P(T) + G(T) \le N\Omega/\eta + \eta E(T) (movement \lesssim prediction-error energy) holds unconditionally.

The subtlety—and the paper's most delicate engineering—is that a naive lift breaks the other half of the argument when the mass \lambda gets small. HOOD's regularizer,

is tuned so that the choice map is a \lambda-tempered softmax, Q(y) = \mathrm{softmax}\!\big(\tfrac{\sqrt\lambda}{1+\sqrt\lambda}y\big), whose Jacobian shrinks like \sqrt\lambda—exactly cancelling the 1/\lambda blow-up in the Bregman coercivity bound. The product works out to \eta^2\lambda \cdot \eta/\lambda = \eta^3, mass-free. This cancellation ("the repeated player bound") is what the whole proof leans on.

Ingredient two: make the prediction error an (N+1)-th derivative

Here is the aha. Daskalakis–Fishelson–Golowich proved polylog regret by showing that under Optimistic Hedge, high-order finite differences of the trajectory are small. HOOD inverts the logic: instead of proving the dynamics are high-order smooth, choose the predictor so that its error is, by algebraic identity, an (N+1)-th order difference of the payoff stream:

where \Delta is the first time-difference and \sigma is a geometric discount with factor \delta = N/(N+1). The predictor achieving this is a fixed recurrence over the last N+1 payoffs and predictions (Eq. 22 in the paper)—computationally trivial. Think of it as an order-(N+1) high-pass filter: the error only "sees" the (N+1)-th derivative of play. The discounting matters because a raw (N+1)-th difference costs a factor 2^{N+1} (\|\Delta^{N+1}w\| \le 2^{N+1}\|w\|)—exponential in N; the discounted operators satisfy \|\sigma^{N+1}\Delta^{N+1-p}w\| \le 4(N+1)^{p+1}\|w\|, polynomial in N.

Why is N+1 the magic order? Because of a pigeonhole argument on player labels. Each time you difference a payoff term, multilinearity of the game converts it into strategy variations \Delta x_j of individual players, and each such variation expands as

Only the middle term can survive—and only if player j's Jacobian hasn't already appeared in the term: if j is a repeat, the \eta^3 cancellation above kills it. So every surviving branch of the expansion must introduce a fresh player label. There are only N players. After N+1 differences, every branch has terminated.

There is a cost: each expansion level multiplies the number of branches by up to 3p(N-p) \le \tfrac34 N^2 and picks up a factor O((N+1)\eta) per new Jacobian. For the branching to contract geometrically you need N^2(N+1)\eta \lesssim 1—this is precisely why the step size must be \eta = O(N^{-3}), and where the N^3 in the regret bound comes from. Closing the loop, the two inequalities (E \lesssim P + G from the expansion, P + G \lesssim \Omega/\eta + \eta E from lifted RVU) yield E(T) < 62^2(N+1)^6 L uniformly in T, hence \mathrm{reg}_i(T) \le 3L/\eta forever.

The concurrent result, and how the bounds compare

Liu, Farina, and Ozdaglar independently proved constant regret three days earlier (ECHO-OFTRL), also using a lifted regularizer and a stabilized high-order predictor—but built as an N-stage exponential-moving-average cascade analyzed with signal-processing tools (filter kernels, weighted convolutions). Both proofs pivot on the same phenomenon—the number of players bounds the order of differencing needed—but HOOD's direct algebraic expansion yields a dramatically sharper constant:

That N^3 vs. N^{21} gap is the difference between a bound that is merely large and one that is astronomically vacuous for any realistic N. Two independent teams converging on the same architecture within days is also the strongest kind of evidence that higher-order optimism plus lifting is the mechanism here, not an artifact of one proof style.

What to make of it—and what to be skeptical about

What changes if this holds. A question open in spirit since Hannan and Blackwell is settled: in the full-information self-play regime, the presence of an underlying game is enough to eliminate regret growth entirely, in every finite game, with no structural assumptions. It also gives O(1/T) convergence of empirical play to coarse correlated equilibria, matching the trivial lower bound. And the paper's bootstrap template—design the predictor so its error is a high-order derivative, design the regularizer so the geometry cancels exactly where the combinatorics needs it—is a genuinely reusable idea.

Caveats, plainly. The result requires deterministic full-information feedback (each player sees their entire mixed payoff vector) and all players running HOOD; both are essential, and the authors are upfront that bandit feedback provably rules out constant regret. The constants are enormous in practice: for N=2, K=2 the explicit bound is \approx 2.3 \times 10^4, and the mandated step size \eta \le 1/[60(N+1)^3] means the dynamics move glacially—for equilibrium computation at moderate T, a \log T method with better constants will beat this. There are no experiments; this is a pure theory paper (which is fine—the claim is a worst-case guarantee—but we learn nothing about typical-case behavior or whether simpler dynamics like vanilla Optimistic Hedge might secretly also achieve O(1), a question the authors explicitly leave open). Robustness against non-HOOD opponents is handled only by a bolt-on switching rule (Appendix D) that permanently defects to Hedge if the bound is ever violated. One eyebrow-raiser: the acknowledgments credit ChatGPT with assisting some design choices in the algorithm and analysis—the proofs are fully written out and checkable, but careful verification by the community is warranted for a result of this significance, doubly so given the density of explicit constants throughout the appendices.

Where to spend your time. Section 4 ("Proof overview") is excellent and self-contained: the four-observation structure (lifted RVU → positivity → higher-order expansion → why the lifted regularizer preserves the local bounds) gives you the entire argument's skeleton in a few pages. Section 4.5, on why the naive lift fails and how the \sqrt\lambda terms in the regularizer are reverse-engineered from the needed cancellation, is the part you won't find anywhere else.