PaperlayerView exact revision on arXiv

Source-linked AI summary

Constant regret in general games via higher-order optimism

Omar Abbadi, Rida Laraki, Panayotis Mertikopoulos

arXiv:2609.04113v1cs.LGcs.GT

TL;DR

The paper addresses whether uncoupled learning can achieve constant individual regret for every player in arbitrary finite games under full-information feedback. It proposes HOOD, combining higher-order optimism, discounting, and lifted entropic regularization, and proves an O(N^3 log^2 K) horizon-uniform regret bound. The guarantee is horizon-free, so regret remains finite over an entire trajectory and empirical play converges to coarse correlated equilibria at rate O(1/T).

  • Problem

    The paper asks whether all players following an uncoupled learning rule can achieve constant individual regret in all games.

  • Method

    HOOD is an uncoupled full-information OptFTRL variant using a discounted higher-order predictor and entropic regularization on a lifted strategy space.

  • Results

    HOOD guarantees each player O(N^3 log^2 K) regret uniformly over time in finite N-player games with up to K actions.

  • Takeaways & Limitations

    For fixed N and K, regret remains finite over possibly infinite play, and empirical play converges to coarse correlated equilibria at rate O(1/T).

  • Takeaways & Limitations

    The guarantee assumes deterministic full-information feedback, with each player receiving their mixed payoff vector and no further information.

Abstract

from arXiv · show

We introduce an uncoupled learning algorithm which, when employed by all players of an arbitrary $N$-player normal form game with up to $K$ actions per player, guarantees $O(N^3\log^2 K)$ individual regret, uniformly over the horizon of play. The proposed algorithm - which we call higher-order optimism with discounting (HOOD) is a variant of optimistic follow-the-regularized-leader (OptFTRL) that combines a discounted $(N+1)$-th order predictor with entropic regularization over a suitable "lifting" of the game's strategy space. This combination of ingredients is purposefully designed to dampen large oscillations of the induced sequence of play in a controlled manner, removing in this way a key stumbling block of previous attempts to achieve constant regret in general games. Our approach bears several striking similarities to the concurrent - and completely independent - work of Liu, Farina, and Ozdaglar (arXiv:2608.31166), who very recently derived an $O(N^{21}\log^{4} K)$ regret bound through the use of higher-order optimism and an exponential moving average estimator.

1. Introduction

The paper asks whether uncoupled learning can guarantee constant individual regret in arbitrary games and answers affirmatively under deterministic full-information feedback. HOOD combines higher-order optimism, discounting, and lifted entropic regularization to obtain horizon-uniform regret.

  • 1. Introduction: The result addresses the open question of constant individual regret for all players in arbitrary games while requiring uncoupled updates and deterministic full-information feedback.Each player receives their mixed payoff vector but no further information.
  • 1. Introduction: HOOD bounds each player’s regret by O(N^3 log^2 K) uniformly over time in finite N-player games with up to K actions.The informal bound is 45(N + 1)^3[16 + 4 log K + log^2 K].
  • 1. Introduction: For fixed N and K, horizon-free HOOD yields finite total regret and empirical play converges to coarse correlated equilibria at rate O(1/T).The algorithm does not require prior knowledge of the horizon.
  • 1. Introduction: HOOD combines a discounted higher-order predictor with lifted entropic regularization to stabilize prediction errors and control positive regret.The lifting prevents large positive regret from being offset by negative contributions from other players.
  • 1. Introduction: The approach uses a more direct algebraic expansion than concurrent higher-order-optimism work, obtaining O(N^3 log^2 K) versus O(N^21 log^4 K).Both approaches exploit the number of players, but differ in their proof constructions and regularization or estimator designs.

2. Preliminaries

The preliminaries formalize finite normal-form games, players’ mixed strategies and payoffs, full-information feedback, and external regret, linking uniform regret bounds to CCE convergence.

  • The game has N players with K actions each, and unequal action sets can be padded with duplicate actions without affecting regret guarantees.
  • Each player uses a mixed strategy from the probability simplex, while multilinear extension gives expected payoffs under the induced product distribution.
  • Payoffs may be assumed bounded in [-1,1], since positive affine transformations only rescale regret guarantees.
  • Under full-information feedback, each player observes a payoff vector after choosing a mixed strategy and centers it by the payoff obtained in expectation for updates.
  • External regret compares cumulative payoff against the best fixed action, and a uniform bound yields O(1/T) convergence of empirical play to coarse correlated equilibria.

3. Algorithm and main result

HOOD combines lifted entropic regularization with a discounted higher-order predictor to stabilize optimistic learning in uncoupled general games. With horizon-independent step sizes, it provides uniformly bounded regret and an O(1/T) coarse correlated equilibrium consequence.

  • 3.1. Lifted regularization.: HOOD uses a lifted simplex containing the origin, with entropic regularization inducing a lifted mirror map and a softmax choice map with mass-dependent temperature.Conditional on the optimizing mass, the remaining maximization over the mixed strategy is explicit, leaving only a one-dimensional optimization problem.
  • 3.2. The algorithm.: The algorithm forms a discounted higher-order predictor and applies optimistic FTRL updates to generate each player's mixed action.The discount factor is fixed by the number of players, and HOOD is defined through the resulting predictor and regularized update.
  • 3.2. The algorithm.: HOOD is uncoupled and horizon-free: each player uses only N, K, their own mixed action, and observed payoff vectors, without requiring T.The algorithm is run indefinitely and does not require prior knowledge of the horizon.
  • 3.3. Regret guarantee.: For every player, the main theorem gives Reg_i(T) ≤ 45(N + 1)^3[16 + 4 log K + log^2 K] under the stated step-size condition.The admissible step-size range is independent of the horizon, yielding the stated uniform-in-time regret bound.
  • 3.3. Regret guarantee.: The empirical distribution of play is a 3L/(ηT)-approximate coarse correlated equilibrium under the theorem's conditions.This follows from the uniform regret guarantee and the regret-to-CCE implication.
  • 3.3. Regret guarantee.: A switching rule extends robustness to adversarial payoff sequences by replacing HOOD with an adversarial-regret algorithm once its regret bound is exceeded.The paper presents this as a consequence of HOOD's bounded regret guarantee; the detailed rule is deferred to Appendix D.

4. Proof overview

The proof combines a lifted OptFTRL analysis with higher-order, geometrically discounted prediction errors. The resulting expansion terminates after introducing distinct player labels and yields a regret bound uniform over time.

  • 4.1. The lifted RVU inequality.: The lifted RVU inequality makes positive regret nonnegative, allowing Bregman movement to be bounded by prediction error.The lift uses a simplex containing the origin and identifies the lifted regret with the positive part of external regret.
  • 4.2. The prediction error and Bregman movement bounds.: HOOD builds N + 1 time differences directly into its predictor, rather than proving that ordinary high-order differences eventually become small.This connects payoff differences, strategy differences, and the learning map through the game's multilinearity.
  • 4.6. Closing the loop.: The proof closes by combining uniform prediction-error and Bregman-movement bounds, giving Reg_i(T) = O(N^3 log^2 K).The bound holds uniformly over T for the admissible step size η = 1/[60(N + 1)^3].
  • 4.3. Higher-order optimism with discounting.: Only terms introducing a fresh player label can continue in the expansion, so no continuation remains after all N player labels appear.Repeated appearances of an existing player are controlled by local Jacobian and Bregman bounds.
  • 4.3. Higher-order optimism with discounting.: Geometric discounting prevents successive differences from producing exponential dependence on the number of players.The predictor pairs the required N + 1 ordinary differences with geometric discounting.

5. Concluding remarks

The paper concludes that uncoupled full-information learning can achieve uniformly bounded regret in every finite game. It highlights the remaining dependence on game parameters and identifies directions for reducing those costs and broadening the guarantee.

  • 5. Concluding remarks: Uncoupled full-information learning achieves regret uniformly bounded in time in every finite game.For fixed N and K, each player incurs only a finite amount of regret over the entire trajectory.
  • 5. Concluding remarks: The result removes the prior O(N log^2 K log T) horizon dependence at the cost of an additional N^2 factor.The paper identifies reducing this player-count price and improving the log^2 K dependence as open questions.
  • 5. Concluding remarks: Future work includes bounded regret for broader game classes, stronger notions such as swap regret, and simpler dynamics.The paper specifically questions whether classical OptFTRL can retain good parameter-dependent bounds.

B.1. Discounted finite differences.

This section establishes the sequence identities and norm bounds underlying HOOD’s discounted higher-order differences. The discount operator and its inverse let the predictor encode repeated differences while controlling their growth.

  • B.1. Discounted finite differences.: The discount operator and w_t − δw_t−1 are inverses on zero-prehistory sequences.The same conclusion extends to bounded sequences by absolute convergence.
  • B.1. Discounted finite differences.: The predictor identity states that applying the first-order discounted-difference operator N + 1 times to prediction error yields the required higher-order structure.Applying the inverse operator repeatedly recovers the predictor representation.
  • B.1. Discounted finite differences.: The higher-order sequence bounds apply for orders 1 through N + 1 in both ℓ1 and ℓ∞ norms.These bounds control the discounted difference sequences used in the proof.

B.2. Payoff differences.

The payoff-difference analysis uses multilinearity to express changes in payoffs through strategy variations. The resulting coefficients have controlled structure, which supports the higher-order expansion.

  • B.2. Payoff differences.: The product rule expands a multilinear payoff difference by changing one strategy argument at a time.This one-at-a-time decomposition exposes the strategy variations needed by the higher-order argument.
  • B.2. Payoff differences.: A payoff difference is represented as linear maps applied to strategy variations of the players.The representation follows by applying the multilinear product rule to the payoff maps.
  • B.2. Payoff differences.: Each coefficient contains at most N − 1 strategy terms, with each player label appearing at most once.A fixed player label can occur at most twice across the two coefficient sums.

B.3. Differences control.

This section establishes bounds for initialization, score, strategy, and divergence-related difference terms under the stated conditions. These bounds are then used to prove the displayed auxiliary relations.

  • Initialization: The initialization conventions set the prehistory variables to zero or fixed baseline values, including y_i,t, m_i,t, e_i,t, z_i,t, x_i,t, P_i,t, and G_i,t.For t ≤ 0, the construction also sets r_i,t = 0 and J_i,t = ηJ(0).
  • Difference bounds: The lifted iterates are represented as x_i,t = Q(η(y_i,t−1 + m_i,t)) and x_i,t−1 = Q(η(y_i,t−1 − e_i,t−1)).These identities provide the two arguments used in the subsequent difference bounds.
  • Difference bounds: The proof applies the stated inequalities and the condition on η to bound the relevant expansion terms, including divergence expressions involving P_i,t and G_i,t−1.The displayed divergence identities are Dψ(z_i,t−1/2, z_i,t−1) = ηP_i,t and Dψ(z_i,t−3/2, z_i,t−1) = ηG_i,t−1.
  • Conclusions: The resulting estimates establish the auxiliary bounds (B.64)–(B.67), with (B.67) relying on 600000(N + 1)^2η^2 < 11 and e^1/480 < 480/479.The proof concludes explicitly that these inequalities establish (B.67).
  • Conclusions: The prehistory conventions ensure that the stated relation (B.63) holds for every integer time t.This extends the relation beyond the positive-time range used in the main argument.

Appendix C. Proof of the main theorem

The proof of the main theorem combines the results of Appendices A and B in sequence. It first invokes the RVU inequality, then the prediction error bound, and finally derives Theorem 1.

  • Proof structure: The proof combines the RVU inequality, the prediction error bound, and Theorem 1 in that order.The stated sequence is: first the RVU inequality, then the prediction error bound, and finally Theorem 1.

C.1. The RVU inequality.

This section proves an RVU inequality using lifted iterates, Bregman variation terms, and Fenchel-based regularizer identities. Summing the resulting bounds over players and rounds yields the section’s principal inequalities.

  • Setup: The lifted half-step and full-step iterates are defined through the score variables and the map Z, while the variation terms are expressed with Bregman divergences.The definitions include z_i,t−1/2 = Z(ηy_i,t−1/2), z_i,t = Z(ηy_i,t), and P_i,t and G_i,t as scaled divergences.
  • Setup: The section introduces cumulative quantities for the Bregman variation terms and recalls the range of the regularizer before proving the RVU inequality.The proof explicitly organizes the argument around P(T), G(T), and the regularizer range.
  • RVU inequality: The RVU inequality is stated as Proposition C.1 for every horizon T.This proposition is the central result of the section.
  • Potential identities: Fenchel equality identifies the regularized score potential with the lifted representation, yielding P_i,t = DΦ(y_i,t−1, y_i,t−1/2) and G_i,t = DΦ(y_i,t, y_i,t−1/2).The derivation uses ∇ψ(Z(ηp)) = ηp and the definition of Φ.
  • Bounding the terms: Fenchel–Young bounds the terminal score contribution, while strong convexity and integration control the remaining G_i,t terms.The proof combines these estimates with the previously established inequalities.
  • Conclusion: Summing the derived inequalities over players and rounds proves (C.5) and (C.6).This is the concluding step of the proposition’s proof.

C.2. Prediction error control.

This section controls prediction error by recursively expanding multilinear terms and exploiting the finite number of distinct player Jacobian labels. The resulting expansion bounds are combined to establish Proposition C.2 for every horizon.

  • Expansion framework: The prediction-error proof expands multilinear terms containing Jacobian, payoff, and strategy factors, with time offsets tracked explicitly.The expansion represents each term as M_t[(B_a); (v_a); (z_a)] after replacing these factors by arbitrary maps and vectors.
  • Recursive expansion: A strategy difference decomposes as Δx_j = r_j + J_jg_j − J_jΔe_j, with the first and last terms controlled directly and J_jg_j continuing only for fresh labels.Repeated player labels are handled separately, so continuing terms introduce fresh player labels.
  • One-step expansion: Lemma C.1 formalizes one-step expansion: a term with p distinct Jacobian labels splits into controlled terms and continuing terms satisfying corresponding structural conditions at the next order.The lemma covers terms with bounded payoff and strategy factors and time offsets in {0, ..., p}.
  • Recursive expansion: Continuing terms introduce fresh Jacobian labels, and no continuation is possible when p = N.The proof bounds the number of possible fresh labels and shows that the structural conditions persist at the next order.
  • Controlled contributions: The controlled contributions are bounded separately for Jacobian variations, initialization terms, remainders, error differences, and repeated-player terms.The argument applies the stated norm bounds, label-count bounds, and Cauchy–Schwarz estimates to each component before combining them.
  • Prediction error bound: Proposition C.2 states the resulting prediction error bound for every T ≥ 1, and the proof concludes by combining the component estimates.The final combination establishes (C.70).
  • Iteration: The continuing-family construction iterates the one-step expansion through orders up to N, while the weights at each order acquire a factor 2(N + 1)η.The induction starts from |F_1| = 1 and uses the condition (26) to control family sizes and weights.

C.3. Proof of the main theorem.

The proof of Theorem 1 combines preceding bounds to derive an expectation bound, then selects η to obtain the theorem’s stated conclusions.

  • Lemma C.2 establishes the regularizer range by noting that both terms in (18) are nonpositive, so max_K ψ = 0.
  • The numerical estimates use 13/6 < 3/2 and 26 · 45/19 < 62.
  • E(T) < 62^2(N + 1)^6L is obtained after substituting the preceding bounds into (C.70).
  • Taking η = 1/(60(N + 1)^3) gives (28), while (29) follows, completing the proof.

Appendix D. Adversarial robustness

Appendix D defines a switching rule that follows bounded-regret dynamics until a threshold violation, then permanently restarts an adversarially robust rule. When all players use it, no switch occurs.

  • The adversarial rule is assumed to provide bounded remaining regret for every payoff sequence in [−1, 1]^K; Hedge and exponential weights are examples.
  • The threshold is τi = inf{t ≥ 1 : Regi(t) > B}, with inf ∅ = ∞.
  • The rule runs Algorithm 1 until τi, then permanently switches to a restarted adversarial rule if the regret threshold is exceeded.
  • Proposition D.1 states that every player’s switching time is infinite when all players use the rule.
  • Before τi, regret remains at most B, and one round can increase external regret by at most 2 because |giα,t| ≤ 2.
Loading 2609.04113v1…