Source-linked AI summary
Constant Individual Regret in General Games
Mingyang Liu, Gabriele Farina, Asuman Ozdaglar
TL;DR
The paper asks whether uncoupled regularized learning can eliminate the horizon dependence in individual regret for finite normal-form games. It introduces deterministic, fully uncoupled ECHO-OFTRL, which adds an EMA cascade for high-order optimism. The resulting guarantee holds simultaneously for every horizon, with regret bounded polynomially in N and logarithmically in m_max.
Problem
Prior individual-regret guarantees for uncoupled no-regret dynamics retain polylogarithmic dependence on the horizon, motivating the question of whether positive regret can remain uniformly bounded in time.
Method
ECHO-OFTRL equips optimistic follow-the-regularized-leader with an EMA-based signal-processing cascade that provides stable high-order prediction.
Results
The deterministic uncoupled dynamics guarantee each player regret at most 2^112 N^21 (1 + log(m_max + 1))^4 simultaneously for every horizon T ≥ 1.
Takeaways & Limitations
The horizon-dependence question is resolved affirmatively for full-information self-play in every finite normal-form game.
Takeaways & Limitations
The result is stated for finite normal-form games with utilities in [0, 1] and full payoff-vector feedback.
Abstract
from arXiv · showhide
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 \emph{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\geq1$, 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.
1 Introduction
The paper resolves whether uncoupled regularized learning can keep every player’s positive regret uniformly bounded in time, proving horizon-independent individual regret in finite full-information normal-form games. Its ECHO-OFTRL method combines high-order optimism with EMA-based filter design to stabilize prediction errors.
- 1 Introduction: Self-play creates payoff predictability because players’ smooth updates couple the payoff sequences through a fixed game.Optimistic methods exploit this predictability to accelerate learning and convergence to equilibrium.
- 1 Introduction: Prior uncoupled dynamics approached coarse correlated equilibria with small external regret, but individual-regret guarantees retained horizon dependence.Earlier methods progressed from T^1/4 to O(log^4 T) and O(log T) bounds, without removing the dependence generally.
- 1.1 Contributions: For every finite N-player normal-form game with utilities in [0, 1] and full payoff-vector feedback, deterministic uncoupled dynamics achieve a horizon-independent individual-regret bound.The paper states the bound simultaneously for every horizon T ≥ 1, with explicit polynomial dependence on players and logarithmic dependence on the largest action set.
- 1.1 Contributions: ECHO-OFTRL uses a stable high-order predictor built from signal-processing ideas rather than repeatedly applying an unstable raw difference.The raw N-fold difference has coefficient mass 2^N and can exponentially amplify oscillations.
- 1.1 Contributions: EMA preconditioning reduces the worst-case frequency gain of the N-fold difference from 2^N to (2/(1 + ρ))^N ≤ e while keeping proof bounds polynomial in N.The filter I − δ = (1 − ρ)L(I − ρL)^−1 is a one-pole exponential moving average of past values.
2 Preliminaries
The preliminaries define finite normal-form games, mixed strategies, payoff vectors, and the full-information interaction protocol used for regret analysis.
- Players choose mixed strategies from finite simplices, with player i having action set [m_i].
- Each player’s utility is the multilinear extension of a pure-profile payoff function taking values in [0, 1].
- The expected payoff function is multiaffine in opponents’ strategies and independent of player i’s own strategy.
- At each round, players jointly choose a strategy profile and player i observes its full payoff vector.
3 Lifted optimistic dynamics
This section constructs ECHO-OFTRL by lifting optimistic regularized learning and replacing unstable repeated differences with a stable EMA-based high-order predictor.
- ECHO-OFTRL uses lifted optimistic-FTRL objectives and response maps Q_i to update each player’s mixed strategy.
- The regularizer uses Γ_m := (log m)^2 + 2 log m + 2 and Ξ_m := 104(1 + Γ_m).
- ECHO denotes an EMA cascade for high-order optimism, with EMA meaning exponential moving average.
- The predictor replaces the raw Nth difference (I − L)^N, whose coefficients have total absolute value 2^N, with a stable filtered construction.
- Theorem 3.3 guarantees that, in finite N-player games with utilities in [0, 1], every player’s positive regret is bounded by 2112N^21(1 + log(m_max + 1))^4.
4 Proof sketch
The proof sketch combines optimistic-FTRL regret inequalities with a weighted variation estimate, then absorbs the resulting terms using the learning-rate choice.
- The argument begins with the optimistic-FTRL calculation and the variation relation in (3.3).
- A weighted variation estimate remains the central intermediate bound to prove.
- After the estimate, weights ηΞ_i are inserted so the resulting sum can be absorbed by −∑_i P_i,T/(2η).
- The learning-rate specialization yields the theorem’s final regret estimate.
A Proof of Theorem 3.3
The formal proof establishes smooth response-map properties, filter bounds, and weighted variation control under the theorem’s smallness condition.
- The response map Q_m has a unique interior maximizer and is continuously differentiable.
- The filter lemmas bound the ℓ1 norm and first four absolute moments of ker(K) by 2^28N^6, while δ^h has zero coefficient sum.
- The remaining proof applies weighted-sequence estimates to control the variation terms used in Theorem 3.3.
- Under 3 · 2^28γN^6 ≤ 1/100, the score dynamics satisfy the regularity hypothesis needed for the subsequent estimates.
A.1 The optimistic-FTRL path inequality
The optimistic-FTRL analysis compares the algorithm’s regularized path with a comparator by tracking prediction-error increments and applying a Bregman three-point identity. These steps yield a regret inequality after maximizing over comparators and summing over players.
- A.1 The optimistic-FTRL path inequality: The path analysis is set up for a fixed horizon, player, and comparator, with prediction-error initialization e(0) := 0.
- A.1 The optimistic-FTRL path inequality: The proof encodes score increments as g(t) − (e(t) − e(t−1)) through the optimistic-FTRL path.The terminal increment is e(T+1) = e(T), and the regularized-leader telescope reorganizes the error terms.
- A.1 The optimistic-FTRL path inequality: The Bregman three-point identity supplies the central comparison step for every time t.
- A.1 The optimistic-FTRL path inequality: The resulting bounds are combined with the range estimate 4Γi, maximized over comparators, and summed over players.
A.2 Weighted variation bound
The weighted-variation analysis controls the high-order filter terms under explicit numerical conditions on γ and N. With η chosen as a function of N and Ξmax, these bounds produce a horizon-uniform individual-regret guarantee scaling polynomially in N and logarithmically in mmax.
- A.2 Weighted variation bound: The parameter conditions ensure the numerical hypotheses of Lemmas A.7–A.9 and make the horizon-dependent term nonpositive.
- A.2 Weighted variation bound: The auxiliary estimates rely on assumptions such as 3 · 228γN6 ≤ 1/100 and γ ≤ N−20.
- A.2 Weighted variation bound: The weighted variation proof separates cases according to whether j belongs to S ∪ {r}, applying Lemmas A.7 and A.8 accordingly.
- A.2 Weighted variation bound: The construction bounds commutator terms ci,h := [Kh, Ji]di and verifies kernel hypotheses for the relevant filters.
- A.2 Weighted variation bound: η = 2−94/(N20Ξmax) is selected so that the key hypothesis holds for every T ≥ 1.The proof also verifies 6 · 228ηΞmaxN6 ≤ 1/100.
- A.2 Weighted variation bound: 2112N21 (1 + log (mmax + 1))4 bounds each player’s positive regret uniformly over the horizon.The preceding inequality gives [Regi(T)]+ ≤ 5 · 2109N21 (1 + log (mmax + 1))4 + 80 · 2110N−4 before simplification.
B.1 Convexity of eψm
The paper establishes convexity and interior uniqueness for the lifted regularizer eψm and its conjugate optimizer Qm. The scalar optimization has a unique solution characterized by a strictly monotone derivative.
- B.1 Convexity of eψm: eψm is finite and convex on e∆m, strictly convex in its relative interior, and induces a unique interior maximizer Qm(θ).
- B.1 Convexity of eψm: The convexity proof uses differentiation and Young’s inequality to control the relevant terms.
- B.1 Convexity of eψm: The optimizer remains interior because one-sided derivatives diverge at λ ∈ {0, 1} and action-coordinate derivatives diverge at the simplex boundary.
- B.1 Convexity of eψm: For m ≥ 2, the regularizer’s range is controlled by −log m ≤ ψm(x) ≤ 0.
- B.1 Convexity of eψm: The scalar objective’s derivative is strictly decreasing, so the associated function is strictly increasing with a unique zero.
B.2 Bounds for Qm
The bounds for Qm establish smoothness, uniqueness, stability, and divergence comparisons for the regularized optimizer. These properties follow from positive-definite Hessians, pathwise differentiation, and Taylor-integral arguments.
- B.2 Bounds for Qm: Qm(θ) is unique, interior, and continuously differentiable for every m ≥ 2 and θ ∈ Rm.
- B.2 Bounds for Qm: If Ξm ∥e∥∞ ≤ 1/100, the optimizer’s local perturbation is controlled for θ′ = θ + e.
- B.2 Bounds for Qm: Positive definiteness of the Hessian and the implicit-function theorem make Qm and xm smooth along perturbation paths.
- B.2 Bounds for Qm: The pathwise derivative analysis bounds H(t) across the interval and yields the stated regularizer estimates.
- B.2 Bounds for Qm: Each directed divergence is at least one quarter of the corresponding symmetric divergence.
- B.2 Bounds for Qm: Along the interpolation path, λ(t) is bounded below by bλ/2, enabling weighted Cauchy–Schwarz estimates.
C.1 EMA kernels and weighted convolution
The section establishes quantitative bounds and cancellation properties for the EMA-derived filters, then develops weighted convolution tools used to control their outputs and derivatives.
- The ℓ1 norm and first four absolute moments of ker(K) are at most 228N^6.
- For each 1 ≤ h ≤ N, the coefficients of δ^h sum to zero, yielding cancellation for the corresponding filter kernels.
- The filter K⋆ has transfer-function bound |K⋆(ς)| ≤ 6N.
- Lemma A.3 applies weighted convolution bounds when the kernel has exponentially weighted absolutely summable coefficients and the input sequence is supported through time T.
- Under conditions such as 3 · 228γN^6 ≤ 1/100, the filter estimates verify hypotheses needed for subsequent score and output bounds.