arXiv CS open access

Constant Individual Regret in General Games

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Constant Individual Regret in General Games Mingyang Liu1 , Gabriele Farina1 , Asuman Ozdaglar1 1 LIDS, EECS, Massachusetts Institute of Technology 1 {liumy19,gfarina,asuman}@mit.edu

arXiv:2608.31166v1 [cs.LG] 31 Aug 2026

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 followthe-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 mmax denotes the largest action-set size, then, simultaneously for every horizon T ≥ 1, it guarantees that each of the N players in the game incurs regret upper bounded by O(poly( N, log mmax )). Our algorithm leverages a new form of optimism inspired by modern filter design.

Introduction

Uncoupled no-regret dynamics model decentralized learning: each player updates from its own full payoff vector without knowing the other players’ objectives (Hart and Mas-Colell, 2000; Greenwald and Jafari, 2003). If every player has small external regret, empirical play approaches the set of coarse correlated equilibria (CCE) (Moulin and Vial, 1978; Cesa-Bianchi and Lugosi, 2006). Regret-minimization methods also underlie several landmark systems for solving large imperfect-information games (Bowling et al., 2015; Moravčík et al., 2017; Brown and Sandholm, 2018, 2019). Traditional online-learning analysis treats the payoff sequence as an arbitrary, possibly adver√ sarial, exogenous process. Against such a sequence, T regret can be easily shown to be unavoidable (Hazan, 2016). In self-play, however, the payoff sequences are coupled through a fixed game and the learners’ updates. While nonstationary, the smooth update of strategies makes the dynamic landscape faced by each player in the game slightly predictable. Optimistic methods seek to exploit this predictability to accelerate learning and convergence to equilibrium. Optimism has also been studied more broadly as a route to acceleration in optimization and game solving (Wang and Abernethy, 2018; Mertikopoulos et al., 2019; Farina et al., 2019; Piliouras et al., 2022a). Fast rates under robustness and nonparametric structure have also been studied (Foster et al., 2016; Daskalakis and Golowich, 2022). The quest for accelerated learning dynamics has driven a long progression of faster rates. 1

Predictable-sequence methods brought optimism to online learning (Chiang et al., 2012; Rakhlin and Sridharan, 2013). The RVU framework (Syrgkanis et al., 2015) then gave T 1/4 individual regret and, more crucially, exposed a key mechanism of analysis that has since been a key mainstay. Unfortunately, that analysis alone is capable of guaranteeing constant sum of regrets, but not constant individual regret, as negative regrets can hide another player’s large positive regret. Later, Chen and Peng (2020) leveraged the RVU bound, but was able to break through the T 1/4 barrier in the special case of two-player games. Breaking past the polynomial dependence in T, the high-order, discrete-time frequency analysis of Optimistic Hedge of Daskalakis, Fishelson, and Golowich (2021) reduced individual regret to O(log4 T ). This approach was subsequently extended to certain structured polyhedral games (Farina et al., 2022b). Lifted OFTRL then obtained O(log T ) regret over general convex games by turning ordinary regret into a nonnegative lifted regret (Farina et al., 2022a). Dynamic learning-rate control matched this logarithmic horizon dependence while improving the action dependence to polylogarithmic (Soleymani et al., 2025b). This mechanism proved extremely general and robust across different choices of the convex action set and regularizer (Soleymani et al., 2025a). Related work also obtains logarithmic swap regret in multiplayer games (Anagnostides et al., 2022). Finally, Clairvoyant MWU (Piliouras et al., 2022b) obtained a constant regret bound from a fixed-point update that evaluates payoff vectors at the strategy profile being computed. This guarantee is not directly comparable to those above: the method requires unrolling joint fixed-point computations, and its regret bound applies only to a sparse subsequence rather than the full history of play. We summarize the comparable results in Table 1, where N denotes the number of players and m := mmax denotes the largest number of actions of any player. All bounds are specialized to utilities in [0, 1]; the OFTRL/OOMD row uses entropy regularization. This history points to a natural question: Can uncoupled regularized learning keep every player’s positive regret uniformly bounded in time? We show that it can for full-information self-play in finite normal-form games, resolving the horizon-dependence question in this setting. We also remark that because our dynamics are based on a (lifted) version of Hedge, it is possible to kernelize them, making our method applicable beyond normal-form games to a number of important combinatorial settings, including extensiveform games (Farina et al., 2022b).

1.1

Contributions

The main contribution of the paper is to show the following. Theorem 1.1 (informal main theorem). For every N-player finite normal-form game with utilities in [0, 1] and full payoff-vector feedback, there exist deterministic, uncoupled learning dynamics such that,

Table 1: Progress toward horizon-independent individual regret via uncoupled learning dynamics. Method OFTRL/OOMD (Syrgkanis et al., 2015) Optimistic Hedge (Chen and Peng, 2020) Optimistic Hedge (Daskalakis et al., 2021) LRL-OFTRL (Farina et al., 2022a) DLRC-OMWU / Cautious Optimism (Soleymani et al., 2025b,a) ECHO-OFTRL (This paper)

Individual regret √ O N log m T 1/4

Main technique(s)

O log5/6 m T 1/6 (Two-players only) O N log m log4 T

Coupled strategy/payoff path-length bounds Analysis leverages high-order discrete differences Lifting, nonnegative RVU bounds, and log regularization Dynamic pacing, intrinsic Lipschitzness

O( Nm log T ) O N log2 m log T

O N 21 log4 m

One-step optimism and RVU bounds

Transfer-function-designed EMA residual and nonnegative RVU bound

when used by all players, the individual regret of the generic player i satisfies N

Regi ( T ) ≤ ∑ [Reg j ( T )]+ ≤ C ( N + 1)21 (1 + log(mmax + 1))

j =1

simultaneously for every horizon T ≥ 1, where C is a universal constant. The player dependence is explicitly polynomial and the bound is independent of T; we made no attempt to optimize either displayed exponent. Technique-wise, our main methodological contribution is a signal-processing construction of a new, stable high-order predictor. Standard optimistic learning uses the preceding payoff vector to predict the current one, so the prediction error is the one-step change in payoffs. Repeating this idea N times would give the raw difference ( I − L) N , where L is the one-round delay: for a payoff sequence g and every integer t, (Lg )(t) = g (t−1) . The coefficients of the raw difference have total absolute value 2 N , so this direct construction can amplify oscillations exponentially. We instead set 1 I−L ρ :=1 − , δ := , N I − ρL gb :=( I − δ N )g,

g − gb = δ N g.

The filter I − δ = (1 − ρ)L( I − ρL)−1 is a one-pole EMA of past values. This preconditioning reduces the worst-case frequency gain of the N-fold difference from 2 N to (2/(1 + ρ)) N ≤ e, while the time-domain filter bounds used in the proof remain polynomial in N. In short, high-order optimism lets us bound the cumulative prediction-error term by a horizonindependent constant plus strategy movement; the negative movement term absorbs the latter, yielding constant regret. 3

Preliminaries

For every positive integer n, let [n] := {1, . . . , n}. For a vector z ∈ Rn and a ∈ [n], write 1/p z( a) for its ath coordinate. For 1 ≤ p < ∞, define ∥z ∥ p := ∑na=1 |z( a)| p , and define : : ∥z ∥∞ = maxa∈[n] |z( a)|. For a scalar r ∈ R, define [r ]+ = max {r, 0}. The (n − 1)-dimensional probability simplex is ( ) ∆n :=

x ∈ [0, 1]n : ∑ x ( a) = 1 . a =1

We use ⟨·, ·⟩ for the standard inner product and 1 for the all-ones vector of the appropriate dimension. For a tuple x := (xi )i , write x−i := (x j ) j̸=i . Superscripts in parentheses index time, so z (t) denotes the value of a sequence z at round t. For a differentiable map Φ : E → F between finite-dimensional Euclidean spaces, x ∈ E, and ξ ∈ E, JΦ (x) : E → F denotes its Jacobian at x, d Φ(x + rξ ) and JΦ (x)[ξ ] := dr is its directional derivative along ξ. If E = ∏kj=1 Ej , then, for r =0

j ∈ [k ], write ∂ j Φ for the derivative with respect to the jth block. For scalar-valued f , ∇ f denotes its gradient, so J f (x)[ξ ] = ⟨∇ f (x), ξ ⟩, and ∇2 f denotes its Hessian.

2.1

Finite normal-form games and regret

There are N ≥ 2 players. Player i has action set [mi ], where mi ≥ 2, and chooses a mixed strategy xi ∈ ∆mi . Define the largest action-set size by mmax := max mi . i ∈[ N ]

mj Player i’s utility function Ui : ∏ N → [0, 1] is the multilinear extension of a pure-profile j =1 ∆ payoff function taking values in [0, 1]. Define the expected payoff vector by

Ui (x−i ) := ∇xi Ui (x) ∈ [0, 1]mi . It is multiaffine in the opponents’ strategies and does not depend on xi . mj For a horizon T ≥ 1, at every round t ∈ [ T ], the players choose x(t) ∈ ∏ N simultaneously j =1 ∆

(t)

and player i observes the full vector ui

(t)

:= Ui (x−i ). Its external regret is

i T h (t) Regi ( T ) := maxm ∑ Ui (xi , x−i ) − Ui (x(t) ) xi ∈ ∆ i t = 1

E T D (t) (t) = maxm ∑ ui , xi − xi . xi ∈ ∆ i t = 1

The equality follows from multilinearity in player i’s strategy.

Lifted optimistic dynamics

3.1

Lifted regret

Following Farina et al. (2022a), for every player i ∈ [ N ], define e i := {(λ, y ) : 0 ≤ λ ≤ 1, y ∈ λ∆mi } . ∆ e i with λ > 0, the point (λ, y ) plays x := y/λ. For every player For every i ∈ [ N ] and (λ, y ) ∈ ∆ i ∈ [ N ], define Gi by

Gi (x) := Ui (x−i ) − ⟨Ui (x−i ), xi ⟩ 1. (s) For every player i ∈ [ N ], define gi = gi by s ∈Z

( (s)

Gi (x(s) ), s ≥ 1,

s ∈ Z.

s ≤ 0,

For every i ∈ [ N ] and integer s ≥ 1, (s)

gi D

(s)

gi , xi

D E (s) (s) (s) = ui − ui , xi 1,

(s)

∞

≤ 1,

=0.

(t) (t) (t) e i for player i’s lifted strategy = λ i , λ i xi ∈∆ e i as b at round t. For every i ∈ [ N ] and T ≥ 1, write each comparator in ∆ λi , b λi x bi , where D E D E (t) (t) (t) (t) (t) (t) b λi ∈ [0, 1] and x bi ∈ ∆mi . Since gi , λi xi = λ i gi , xi = 0 for every t ≥ 1, (t)

For every i ∈ [ N ] and round t ≥ 1, write µi

E T D (t) (t) (t) max ∑ gi , b λi x b i − λ i xi = max b λi Regi ( T ) = [Regi ( T )]+ . b b e λ , λ x b ∈ ∆ 0≤ b λ i ≤1 ( i i i ) i t =1

3.2

(3.1)

The square-root entropy response

For every integer m > 0 and x ∈ ∆m , Γm bounds Vara∼x [− log x ( a)]. Formally, Γm := (log m)2 + 2 log m + 2,

Ξm := 104 (1 + Γm ).

For every integer m ≥ 2 and x ∈ ∆m , define ψm (x) := ∑m a=1 x ( a ) log x ( a ), where 0 log 0 := 0. For every integer m ≥ 2, define e m := {(λ, y ) : 0 ≤ λ ≤ 1, y ∈ λ∆m } . ∆ e m by em on ∆ For every integer m ≥ 2, define ψ √ √ em (λ, y ) := − 1 − λ + λ [ψm (y/λ) − 2Γm − 3] , ψ 5

λ > 0.

em (0, 0) := −1 for every integer m ≥ 2. For every integer m ≥ 2 and θ ∈ Rm , define Set ψ em (λ, y ) . Qm (θ ) := argmax ⟨θ , y ⟩ − ψ em (λ,y )∈∆

The next lemma establishes some basic properties of Qm (θ ). e m and strictly convex in em is finite and convex on ∆ Lemma 3.1. For every integer m ≥ 2, the function ψ m its relative interior. For every integer m ≥ 2 and θ ∈ R , the maximizer defining Qm (θ ) is unique and e m . More explicitly, for every integer m ≥ 2 and θ ∈ Rm , the function on (0, 1) given belongs to relint ∆ by √ √ m m ′ θ ( a) ′ θ ( a) 2Γ + 3 + log λ λ exp θ ( a ) exp ∑ ∑ m a =1 a =1 1 √ √ λ′ 7−→ √ − − ′ ′ 1−λ λ λ′ θ ( a) ∑m a=1 exp is strictly increasing, tends to −∞ at the left endpoint, and tends to +∞ at the right endpoint. Let λ ∈ (0, 1) denote its unique zero. Then √   λ θ ( a) λ exp a∈[m]   . √ Qm (θ ) = λ, m λ θ (b) ∑b=1 exp Moreover, for every integer m ≥ 2, em (µ) ≤ 2Γm + log m + 4. em (µ) − inf ψ sup ψ em µ∈ ∆

em µ∈ ∆

The proof is deferred to Section B. Remark 3.2. Fix an integer m ≥ 2 and θ ∈ Rm . By Lemma 3.1, binary search on the sign of the strictly increasing function in the lemma localizes its unique zero λ and the formula in the lemma determines Qm (θ ). For every integer m ≥ 2 and θ ∈ Rm , write

(λm (θ ), ym (θ )) := Qm (θ ),

xm (θ ) := ym (θ )/λm (θ ).

e m , define For every integer m ≥ 2 and µ, µ′ ∈ relint ∆ em (µ′ ) − ψ em (µ) − ∇ψ em (µ), µ′ − µ , Dψem (µ′ , µ) :=ψ sym

Dψe (µ′ , µ) := Dψem (µ′ , µ) + Dψem (µ, µ′ ). m

For every i ∈ [ N ], abbreviate ψi :=ψmi ,

ei := ψ emi , ψ

Γi :=Γmi ,

Ξi := Ξmi .

Qi := Qmi ,

Set Ξmax := maxi∈[ N ] Ξi . For every i ∈ [ N ] and θ ∈ Rmi , write Qi (θ ) = (λmi (θ ), λmi (θ )xmi (θ )). 6

3.3

ECHO-OFTRL

We call the algorithm below ECHO-OFTRL, where ECHO stands for EMA cascade for high-order optimism and EMA denotes exponential moving average. Fix a common learning rate η > 0. On every space of bounded bi-infinite sequences in a finite-dimensional normed space, let I be the identity operator and let L be the backward shift, defined for every sequence z in that space and integer t by (Lz )(t) := z (t−1) . Set ρ :=1 −

1 , N

δ :=AD =

∞

A := ( I − ρL)−1 = ∑ ρk Lk ,

D := I − L,

k =0

I−L . I − ρL

(3.2)

Since A and D commute, δ = DA. Thus, δ takes the one-step difference of the exponentially weighted sequence generated by A. For every sequence z that vanishes at nonpositive times and every integer t ≥ 1, ∞

(( I − δ)z )(t) = (1 − ρ) ∑ ρk−1 z (t−k) . k =1

For every i ∈ [ N ], define gbi :=( I − δ N )gi , ei :=gi − gbi = δ N gi .

(3.3)

Thus, for every i ∈ [ N ], the prediction error ei is the stable N th -order filtered difference δ N gi . (t) Since I − δ N = ( I − δ) ∑hN=1 δh−1 , the preceding formula for I − δ shows that gbi depends only on feedback from rounds before t. The following EMA cascade computes this predictor recursively. (t)

Every player i ∈ [ N ] maintains the sequences (emai,h )t≥1 in Rmi for h ∈ [ N ], initialized by (1)

emai,h := 0 for every h ∈ [ N ]. For every i ∈ [ N ] and integer t ≥ 1, define t −1

:= ∑ gi .

( t −1)

(s)

s =1

(t)

For every i ∈ [ N ] and round t ≥ 1, player i forms gbi (t)

gbi

(t)

µi

and plays

= ∑ emai,h , (t)

(3.4)

h =1

( t −1) (t) := Qi η Si + gbi , (t)

For every i ∈ [ N ] and t ≥ 1, after observing ui all N vectors simultaneously by ( t +1) (t) emai,h := ρemai,h + (1 − ρ)

(t)

µi

(t) (t) (t) = λ i , λ i xi .

(t)

(3.5)

(t)

= Ui (x−i ) and computing gi , player i updates (t) gi −

h −1

∑

ℓ=1

! (t) emai,ℓ

h ∈ [ N ].

(3.6)

(3.2) gives ( I − ρL)( I − δ) = (1 − ρ)L. Hence, for every bounded bi-infinite sequence z in a finite( t +1) dimensional normed space and every integer t ≥ 0, (( I − δ)z ) = ρ (( I − δ)z )(t) + (1 − ρ)z (t) . (t) (t) Fix i, h ∈ [ N ] and an integer t ≥ 1. If emai,ℓ = ( I − δ)δℓ−1 gi for every ℓ < h, then (t) gi −

h −1

∑

h −1

I − ( I − δ) ∑ δℓ−1

(t) emai,ℓ =

ℓ=1

!(t)

! gi

(t) = δ h − 1 gi ,

ℓ=1

where the last equality is the geometric-series identity. The zero initial states and (3.6) therefore (t) (t) imply, by induction over h ∈ [ N ], that emai,h = ( I − δ)δh−1 gi for every integer t ≥ 1. N h − 1 N Summing over h ∈ [ N ] and using ( I − δ) ∑h=1 δ = I − δ verifies (3.4). (t)

(t)

For every i ∈ [ N ], extend xi and λi by xi

:= λmi (0) for t ≤ 0, and write (t) (t) (t) xi := (xi )t∈Z and λi := (λi )t∈Z . Thus, for every i ∈ [ N ] and t ≥ 1, player i forms gbi from (t) (t) (t) (t) past feedback, computes and plays xi , observes ui , computes gi , evaluates ei , updates (t) ( t −1) (t) the cascade by (3.6), and sets Si := Si + gi . For every i ∈ [ N ], the cascade uses O( Nmi ) (t) memory and arithmetic per round. For every i ∈ [ N ] and t ≥ 1, Lemma 3.1 gives 0 < λi < 1, (t) so xi is well defined. (t)

For every i ∈ [ N ] and t ≥ 1, fixing λi a ∈ [ m i ],

:= xmi (0) and λi

in the lifted optimistic-FTRL objective gives, for every

q ( t ) ( t −1) (t) exp η λi [Si + gbi ]( a) (t) . q xi ( a ) = (t) ( t ) ( t −1) mi + gbi ](b) ∑b=1 exp η λi [Si (t)

Thus, for every i ∈ [ N ] and t ≥ 1, xi

is the Hedge strategy with learning rate η (t)

For every i ∈ [ N ] and t ≥ 1, Algorithm 1 computes ei

Require: Common learning rate η > 0 and ρ = 1 − 1/N (0) (1) 1: Initialize Si ← 0 and emai,h ← 0 for every h ∈ [ N ] 2: for t = 1, 2, . . . do (t) (t) 3: Set gbi ← ∑hN=1 emai,h 5: 6: 7: 8: 9:

(t)

Compute µi

(t)

and play xi

using (3.5) D

(t) (t) (t) Observe ui , compute gi ← ui −

(t)

for h = 1, . . . , N do ( t +1) (t) (t) Set emai,h ← ρemai,h + (1 − ρ)ei,h−1 (t)

(t)

Set ei,h ← ei,h−1 − emai,h (t)

Set ei

(t)

← ei,N and Si

( t −1)

← Si

(t)

ui , xi

(t)

+ gi

(t)

λi .

in (3.3) with one loop over h ∈ [ N ].

Algorithm 1 ECHO-OFTRL for player i

(t)

1, and set ei,0 ← gi

3.4

Main result

Theorem 3.3. In every N-player finite normal-form game with utilities in [0, 1], suppose every player i ∈ [ N ] runs ECHO-OFTRL as specified in Algorithm 1 with Qi and the constant learning rate 2−94 . N 20 Ξmax

η := Then, simultaneously for every horizon T ≥ 1, N

∑ [Regi (T )]+ ≤ 2112 N 21 (1 + log (mmax + 1))4 .

i =1

A proof sketch is in Section 4 and the formal proof is in Section A.

Proof sketch

The formal proof of Theorem 3.3 appears in Section A; the subsequent appendices prove its geometric and filter estimates. This section outlines the main steps of the argument; O (·) suppresses only universal numerical factors.

4.1

The optimistic-FTRL bound (0)

Fix a horizon T ≥ 1. For every player i ∈ [ N ], set µi T

Pi,T := ∑ Dψei (µi , µi (t)

( t −1)

:= Qi (0) and define N

t =1

PTΞ := ∑ Ξi Pi,T . i =1

The optimistic-FTRL calculation in (A.19), together with (3.3), gives N

∑ [Regi (T )]+ ≤

i =1

(t) 2 N T 1 N 4 N (t) 3/2 N δ g Γ + 80η Ξ λ − Pi,T . i i i ∑ ∑ ∑ i η i =1 2η i∑ ∞ i =1 t =1 =1

It therefore remains to prove the variation estimate N

∑∑

(t) 3/2

λi

δ N gi

(t) 2 ∞

i =1 t =1

≤ O N 16 1 + PTΞ .

The weights (ηΞi )i∈[ N ] are inserted only after this estimate, when the resulting sum is absorbed by − ∑i Pi,T /(2η ).

4.2

A recursive bound

For a positive weight sequence w =

w(t)

t≤ T

, a player i ∈ [ N ], and an integer 1 ≤ h ≤ N,

define T

Eih (w) := ∑ w(t)

δ h xi

(t) 2

t =1

By A.9, for every i ∈ [ N ], integer 1 ≤ h ≤ N, and positive weight sequence w = Lemma ( t ) w satisfying w(t) ≤ 1 for every t ∈ [ T ], t≤ T

∑ w(t)

δ h gi

t =1

(t) 2 ∞

N ≤ 8N ∑ E jh (w) + O N 13 + η 2 Ξ2max N 27 PTΞ . j =1

For every i ∈ [ N ], integer 1 ≤ h ≤ N, and positive weight sequence w = w(t) satisfying t≤ T q (t) w(t) ≤ λi for every t ∈ [ T ], Lemma A.7 gives Eih (w) ≤ O N 12 Ξi Pi,T .

(4.1)

For every r ∈ [ N ], S ⊆ [ N ] \ {r }, and t ∈ Z, set (t) (t) 3/2 (t) wr,S := λr ∏ λk .

(4.2)

k∈S

(t)

Fix r, j ∈ [ N ] and S ⊆ [ N ] \ {r }, and set h = N − |S|. If j ∈ S ∪ {r }, then wr,S ≤ t ∈ [ T ], so (4.1) applies. If j ∈ / S ∪ {r }, then h ≥ 2 and Aδh−1 ( I − Dδ N ) = A − δ N +1 δh−1 .

(t)

λ j for every

The proof of (A.29) verifies the hypothesis of Lemma A.3 for every weight in (4.2), in particular wr,S∪{ j} . Combining this with Lemmas A.5, A.8 and A.9 gives ! N N −| S ∪{ j }| N −|S| Ej (wr,S ) ≤ O N 13 η 2 Ξ2max ∑ Ek wr,S∪{ j} + N 12 1 + P TΞ . k =1

The constants are specified in (A.29).

4.3

Iterating the bound (t)

(t)

For every r ∈ [ N ], begin with S = ∅, for which wr,∅ = (λr )3/2 for every t ∈ Z. Consider N −|S|

a current term E j (wr,S ), where r, j ∈ [ N ] and S ⊆ [ N ] \ {r }. If j ∈ / S ∪ {r }, the preceding estimate replaces S by S ∪ { j} and lowers the order by one; otherwise, (4.1) applies. Thus at most N − 1 additions precede a term to which (4.1) applies. 10

Combining the resulting estimates gives N

∑∑

(t) 3/2

λi

δ N gi

(t) 2 ∞

i =1 t =1

≤ poly( N ) 1 + PTΞ .

For the learning rate in Theorem 3.3, the preceding estimate gives (t) 2 N T 1 N (t) 3/2 Pi,T ≤ poly( N ). 80η ∑ ∑ Ξi λi δ N gi − 2η i∑ ∞ =1 i =1 t =1

Acknowledgments Initial versions of the proofs were developed with the assistance of ChatGPT 5.5 and ChatGPT 5.6 Sol. The authors subsequently streamlined and revised the proofs substantially.

References Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with O(log T ) swap regret in multiplayer games. In Conference on Neural Information Processing Systems (NeurIPS), 2022. Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up Limit Hold’em poker is solved. Science, 347(6218):145–149, 2015. Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418–424, 2018. Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885–890, 2019. Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006. Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. In Conference on Neural Information Processing Systems (NeurIPS), 2020. Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory (COLT), 2012. Constantinos Daskalakis and Noah Golowich. Fast rates for nonparametric online learning: from realizability to learning in games. In Annual ACM Symposium on Theory of Computing (STOC), 2022.

Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. In Conference on Neural Information Processing Systems (NeurIPS), 2021. Gabriele Farina, Christian Kroer, Noam Brown, and Tuomas Sandholm. Stable-predictive optimistic counterfactual regret minimization. In International Conference on Machine Learning (ICML), 2019. Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning dynamics for general convex games. In Conference on Neural Information Processing Systems (NeurIPS), 2022a. Gabriele Farina, Chung-Wei Lee, Haipeng Luo, and Christian Kroer. Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games. In International Conference on Machine Learning, pages 6337–6357. PMLR, 2022b. Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Eva Tardos. Learning in games: Robustness of fast convergence. In Conference on Neural Information Processing Systems (NeurIPS), 2016. Amy Greenwald and Amir Jafari. A general class of no-regret learning algorithms and gametheoretic equilibria. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop (COLT/Kernel), 2003. Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127–1150, 2000. Elad Hazan. Introduction to online convex optimization. Foundations and Trends® in Optimization, 2(3-4):157–325, 2016. Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations (ICLR), 2019. Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. DeepStack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508–513, 2017. Hervé Moulin and J-P Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3-4):201–221, 1978. Georgios Piliouras, Lillian Ratliff, Ryann Sim, and Stratis Skoulakis. Fast convergence of optimistic gradient ascent in network zero-sum extensive form games. arXiv preprint arXiv:2207.08426, 2022a.

Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Beyond time-average convergence: Nearoptimal uncoupled online learning via clairvoyant multiplicative weights update. In Conference on Neural Information Processing Systems (NeurIPS), 2022b. Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Conference on Neural Information Processing Systems (NeurIPS), 2013. Ashkan Soleymani, Georgios Piliouras, and Gabriele Farina. Cautious optimism: A metaalgorithm for near-constant regret in general games. In ACM Conference on Economics and Computation (EC), 2025a. Ashkan Soleymani, Georgios Piliouras, and Gabriele Farina. Faster rates for no-regret learning in general games via cautious optimism. In Annual ACM Symposium on Theory of Computing (STOC), 2025b. Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. In Conference on Neural Information Processing Systems (NeurIPS), 2015. Jun-Kun Wang and Jacob D Abernethy. Acceleration through optimistic no-regret dynamics. In Conference on Neural Information Processing Systems (NeurIPS), 2018.

Proof of Theorem 3.3

Set γ := ηΞmax .

(A.1)

For every integer m ≥ 2 and θ ∈ Rm , write Jmx (θ ) := Jxm (θ ) whenever the response is differentiable. For every integer m ≥ 2 and linear map J : Rm → Rm , write

∥J ∥∞→1 := sup ∥J z ∥1 . ∥z ∥ ∞ ≤1

Lemma A.1. For every integer m ≥ 2 and θ ∈ Rm , the maximizer defining Qm (θ ) is unique and belongs e m . For every integer m ≥ 2, the map Qm is continuously differentiable and Jmx is differentiable. to relint ∆ For every integer m ≥ 2, score θ ∈ Rm , and direction ξ ∈ Rm , q (A.2) ∥Jmx (θ )∥∞→1 ≤4Ξm λm (θ ), s d d x θ θ ξ, J ( + rξ ) ym ( + rξ ) . (A.3) ≤Ξm dr m dr r =0 ∞ →1 r =0 For every integer m ≥ 2 and θ , e ∈ Rm , set θ ′ := θ + e, µ := Qm (θ ), µ′ := Qm (θ ′ ), and b λ := max {λm (θ ), λm (θ ′ )}. If Ξm ∥e∥∞ ≤ 1/100, then λm (θ ′ ) ≤ Ξ m ∥e∥ ∞ , λm (θ ) √ λ3/2 ∥e∥2∞ , e, ym (θ ′ ) − ym (θ ) ≤20 2Ξm b p n o √ 2 b λ xm (θ ′ ) − xm (θ ) 1 ≤16 2Ξm min Dψem (µ′ , µ), Dψem (µ, µ′ ) , n o sym Dψe (µ′ , µ) ≤4 min Dψem (µ′ , µ), Dψem (µ, µ′ ) . log

(A.4) (A.5) (A.6) (A.7)

The proof is deferred to Section B.2. For a filter K = ∑s≥0 k s Ls , write K( ς ) = ∑ k s ς s ,

ker(K) = (k s )s≥0 .

s ≥0

Lemma A.2. Set K⋆ := A − δ N +1 , and, for every integer 1 ≤ h ≤ N + 1, set Kh := Aδh−1 . For every integer 1 ≤ h ≤ N + 1, the filters in (3.2) satisfy δ =AD,

Kh D = δ h ,

(A.8)

Kh ( I − Dδ N ) =K⋆ δh−1 . (A.9) For every integer 1 ≤ h ≤ N + 1, K ∈ δh , Kh , K⋆ , and 0 ≤ ϵ ≤ 1/(8N ), if ker(K) = (k s )s≥0 , then

∑ eϵs/2 (s + 1)4 |ks | ≤ 228 N 6 .

s ≥0

(A.10)

For every integer 1 ≤ h ≤ N + 1 and K ∈ δh , Kh , K⋆ , the ℓ1 norm and the first four absolute moments of ker(K) are at most 228 N 6 . For every integer 1 ≤ h ≤ N + 1, the coefficients of δh satisfy ∑s≥0 ker(δh )s = 0. For every integer 1 ≤ h ≤ N + 1 and K ∈ δh , Kh , K⋆ , consider in any normed space two inputs to K that agree at positive times and are equal, respectively, to a fixed vector φ and 0 at every nonpositive time. If their output difference is τ , then ∞

∑ τ (t)

≤ 259 N 13 ∥φ∥2 .

(A.11)

t =1

Lemma A.3. Fix T ≥ 1 and ϵ ≥ 0. Let z take values in a normed space, with z (t) = 0 for t ≤ 0, and let K = ∑s≥0 k s Ls satisfy ∑s≥0 eϵs/2 |k s | < ∞. Suppose positive weights w(t) are defined for every integer t ≤ T and satisfy w(t) ≤ eϵs w(t−s)

( t ∈ [ T ], s ≥ 0).

Then T

∑w

(t)

(Kz )

(t) 2

∑e

≤

!2 ϵs/2

|k s |

s ≥0

t =1

∑ w(t) z (t)

t =1

Lemma A.4. For every player i ∈ [ N ] and time t ≥ 1, (t)

∞

≤ 3 · 228 N 6 ,

( I − Dδ N )gi

(t)

≤ 3 · 228 N 6 .

(A.12)

∞

If 3 · 228 γN 6 ≤ 1/100, then, for every player i ∈ [ N ] and time t ≥ 1, the two scores in (3.5) at times t and t + 1 satisfy the hypothesis of Lemma A.1, and ( t +1)

log

λi

≤ 3 · 228 γN 6 .

(t) λi

(A.13)

(t)

For every player i ∈ [ N ] and time t ≥ 1, define θ i , and for every player i ∈ [ N ], define di by (t) ( t −1) (t) θ i := η Si + gbi , di := ( I − Dδ N )gi . (t)

(1) (0) = 0. For every player i ∈ [ N ], both θ i − θ i (1) and di vanish. For every i ∈ [ N ] and integer t ≥ 2, (t) ( t −1) ( t −1) (t) ( t −1) (t) ( t −1) (t) θi − θi = η gi + gbi − gbi = η gbi + ei = ηdi .

For every player i ∈ [ N ] and integer t ≤ 0, set θ i

For every player i ∈ [ N ] and time t ≥ 1, define (t) J i := η

Z 1 0

( t −1) (t) Jmx i θ i + αηdi dα. 15

(t)

For every i ∈ [ N ] and integer t ≤ 0, set J i gives, for every i ∈ [ N ] and integer t,

= ηJmx i (0). The fundamental theorem of calculus (t) (t)

(Dxi )(t) = J i di . Lemma A.5. Suppose 3 · 228 γN 6 ≤ 1/100. For every i ∈ [ N ] and t ≥ 1, q √ √ q (t) (t) (t) ≤4 2ηΞi λi ≤ 4 2γ λi , Ji ∞ →1 q √ 2 (t) ( t −1) (t) , λi (Dxi )(t) ≤16 2Ξi Dψei µi , µi 1 q q √ √ (t) (t) (t) 30 6 30 6 ≤ 3 Dx 2 · 2 ηΞ N λ ≤ 3 2 · 2 γN λi . ( i) i i 1

(A.14)

(A.15) (A.16) (A.17)

For every i ∈ [ N ] and horizon T ≥ 1, T

∑

t =1

DJ i

(t) 2 ∞ →1

≤ 16η 2 Ξ2i Pi,T .

(A.18)

The proofs of these four lemmas are deferred to Section C.

A.1

The optimistic-FTRL path inequality

e i . Use Pi,T from Section 4 and suppress Fix T ≥ 1, i ∈ [ N ], and a comparator µ b i = (b λi , ybi ) ∈ ∆ ( 0 ) the player index i below. Set e := 0. For 0 ≤ t ≤ T, write µ(t) = (λ(t) , y (t) ) := Q η S (t) − e(t) , and set µ(T +1) = (λ(T +1) , y (T +1) ) := Q ηS (T ) . The increments of the scores defining µ(0) , . . . , µ(T +1) , divided by η, are g (t) − (e(t) − e(t−1) ) for t ∈ [ T ] and e(T ) for t = T + 1. Reindexing the terms involving e and applying the standard regularized-leader telescope give T

∑

t =1

E E D E T D g (t) , yb − y (t) = ∑ g (t) − e(t) − e(t−1) , yb − y (t) + e(T ) , yb − y (T +1) t =1

E T D + ∑ e( t ) , y ( t +1) − y ( t ) t =1

≤

E T D e(µ e(µ(0) ) 1 T +1 ψ b) − ψ − ∑ Dψe µ(t) , µ(t−1) + ∑ e(t) , y (t+1) − y (t) . η η t =1 t =1

Suppose 2ηΞi e(t) ≤ 1/100 for every t ∈ [ T ]. For each t ∈ [ T ], set µ e (t) = ( e λ(t) , ye(t) ) := ∞ √ Q η S (t) + e(t) . For every t ∈ [ T ], (A.4) and (A.5) and exp (3/200) ≤ 2 give sym Dψe µ(t) , µ e (t) ≤ Dψe µ e ( t ) , µ( t ) 16

D E = 2ηe(t) , ye(t) − y (t) √ 3/2 √ 2 (t) ≤20 2Ξi 2 λ (2η )2 e(t)

∞

=160η 2 Ξi λ(t)

3/2

e( t )

2 ∞

For every t ∈ [ T ], the Bregman three-point identity therefore gives D E e (t) e (t) − Dψe µ(t+1) , µ 2η e(t) , y (t+1) − y (t) = Dψe µ(t+1) , µ(t) + Dψe µ(t) , µ 3/2 2 e( t ) . ≤ Dψe µ(t+1) , µ(t) + 160η 2 Ξi λ(t) ∞

Summing over t ∈ [ T ] and using µ(1) = µ(0) = Q (0),

−

Pi,T 1 T +1 1 T 1 T +1 Dψe µ(t) , µ(t−1) ≤ − . Dψe µ(t) , µ(t−1) + Dψe µ(t+1) , µ(t) = − ∑ ∑ ∑ η t =1 2η t=1 2η t=2 2η

Using the preceding bounds and the range estimate 4Γi implied by Lemma 3.1, we maximize over the comparator, sum over players, and apply (3.1) to obtain N

4 N

(t) 3/2

∑ [Regi (T )]+ ≤ η ∑ Γi + 80η ∑ ∑ Ξi λi

i =1

A.2

i =1 t =1

i =1

(t) 2

∞

−

1 N Pi,T . 2η i∑ =1

(A.19)

Weighted variation bound

Proposition A.6. If γ≤

2−94 , N 20

(A.20)

then, for every T ≥ 1, N

∑∑

(t) 3/2 λi

δ gi

(t) 2 ∞

i =1 t =1

≤ 2204 N 16 1 + PTΞ . (t)

Proof. Use the extensions (gi , xi , λi )i∈[ N ] from Section 3, together with J i i ∈ [ N ] and t ≤ 0. For every integer 1 ≤ h ≤ N, (A.9) gives Kh I − Dδ N = K⋆ δh−1 . Fix r, j ∈ [ N ] and S ⊆ [ N ] \ {r }. Since |S| ≤ N − 1, 3 1 + |S| ≤ N + . 2 2

(A.21)

= ηJmx i (0) for every

Hence (A.13) and (A.20) and N ≥ 2 give, for every t ∈ [ T ], ( t +1)

log

wr,S

≤3 · 2

(t)

wr,S

3 + |S| γN 6 2

9 9 1 ≤ 228 γN 7 ≤ 2−66 N −13 ≤ . 2 2 8N The same rate condition also gives 1 , 100 1 3 · 228 γN 7 ≤3 · 2−66 N −13 ≤ , 4 −20 γ ≤N .

3 · 228 γN 6 ≤3 · 2−66 N −14 ≤

These inequalities verify the numerical hypotheses of Lemmas A.7 to A.9. For every i ∈ [ N ], (1) (0) (τ ) (0) λi = λmi (0) = λi . Telescoping the logarithmic bound and using λi = λi for every i ∈ [ N ] and integer τ ≤ 0 gives, for every t ∈ [ T ] and s ≥ 0, (t−s)

(t)

wr,S ≤ es/(8N ) wr,S . The kernel bound in (A.10) therefore verifies the remaining hypothesis of Lemma A.3 with w = wr,S and K ∈ {K⋆ , Kh } for every integer 1 ≤ h ≤ N. Lemma A.7. Suppose 3 · 228 γN 6 ≤ 1/100 and 3 · 228 γN 7 ≤ 1/4. For every j ∈ [ N ], integer 1 ≤ h ≤ N, and horizon T ≥ 1, r (t) 2 T √ (t) h ≤ 260 2 N 12 Ξ j P j,T . ∑ λ j δ xj 1

t =1

The proof is deferred to Section C.2. (t)

There are two cases. If j ∈ S ∪ {r }, then, for every t ∈ [ T ], wr,S ≤ N −|S|

(wr,S ) ≤ 261 N 12 PTΞ .

(t)

λ j , so Lemma A.7 gives (A.22)

For every player i ∈ [ N ], regard J i as pointwise multiplication on score sequences. For every i ∈ [ N ], integer 1 ≤ h ≤ N, and score sequence z, define

[Kh , J i ]z := Kh (J i z ) − J i (Kh z ). For every i ∈ [ N ] and integer 1 ≤ h ≤ N, define ci,h := [Kh , J i ]di .

Lemma A.8. Suppose 3 · 228 γN 6 ≤ 1/100. For every i ∈ [ N ], integer 1 ≤ h ≤ N, and time t ≥ 1,

δ h xi

(t)

= Ji

K ⋆ δ h − 1 gi

(t)

+ ci,h .

(A.23)

For every i ∈ [ N ], integer 1 ≤ h ≤ N, and horizon T ≥ 1, T

(t) 2

∑ ci,h 1 ≤ 9 · 2116 η 2 Ξ2i N 24 Pi,T ≤ 9 · 2116 γ2 N 24 Pi,T .

(A.24)

t =1

The proof is deferred to Section C.2. Suppose instead that j ∈ / S ∪ {r }, and set h = N − |S|. Then |S| ≤ N − 2, so h ≥ 2. By Lemma A.8 and (A.23), N −|S|

(t)

(wr,S ) ≤ 2 ∑ wr,S J j (t)

K⋆ δ h −1 g j

(t) 2 1

t =1

(t) 2

+ 2 ∑ wr,S c j,h (t)

t =1

(A.25)

Lemma A.9. Let n o √ Cmulti := 2 max 259 , 9 2 · 2121 . Suppose 3 · 228 γN 6 ≤ 1/100. For every i, j ∈ [ N ] and profile x ∈ ∏kN=1 ∆mk , sup m

ξ ∈R j , ∥ξ ∥1 ≤1

∂ j Gi (x)[ξ ] ∞ ≤ 2.

For every i ∈ [ N ] and integer 1 ≤ h ≤ N, there is a sequence χi,h such that, for every t ≥ 1,

δ h gi

(t)

(t) N (t) = ∑ ∂ j G i x( t ) δ h x j + χi,h .

(A.26)

j =1

For every i ∈ [ N ], integer 1 ≤ h ≤ N, and horizon T ≥ 1, T

(t) 2

∑

χi,h

t =1

∞

≤ Cmulti N 13 + γ2 N 27 PTΞ .

(A.27)

If γ ≤ N −20 , then, for every i ∈ [ N ], integer 1 ≤ h ≤ N, and horizon T ≥ 1, T

(t) 2

∑ χi,h ∞ ≤ Cmulti N 13 1 + PTΞ .

t =1

The proof is deferred to Section C.3. n o √ √ Since Cmulti = 2 max 259 , 9 2 · 2121 , 9 2 < 16, and 9 < 16, Cmulti < 2128 ,

9 · 2116 < 2120 . 19

(A.28)

(t) Jj

By Lemma A.5 and (A.15), integer t ≤ T,

∞ →1

≤ 8γ

(t) (t)

(t)

for every t ≥ 1. Since j ∈ / S ∪ {r }, for every

λj

(t)

wr,S λ j =wr,S∪{ j} , h − 1 = N − |S| − 1 = N − |S ∪ { j}| . The weight bound above, with S ∪ { j} in place of S, verifies the hypotheses of Lemma A.3 for w = wr,S∪{ j} . Applying that lemma with K = K⋆ , followed by (A.26) at order h − 1, gives T

(t)

∑ wr,S J j (t)

K⋆ δ h −1 g j

(t) 2 1

t =1

≤64 · 256 γ2 N 12 ∑ wr,S λ j ≤512 · 256 γ2 N

t =1 N 13

(t) (t)

δ h −1 g j

∑ Ek

N −|S∪{ j}|

(t) 2 ∞

wr,S∪{ j} + 128 · 256 Cmulti γ2 N 25 1 + P TΞ .

k =1

(t) (t)

Here (A.28) applies because wr,S λ j ≤ 1 for every t ∈ [ T ]. Moreover, (A.24) gives T

(t) 2

∑ wr,S cj,h 1 ≤ 9 · 2116 γ2 N 24 P j,T . (t)

t =1

Substituting the last two displays into (A.25) and using γ ≤ N −20 gives N −|S|

(wr,S ) ≤ 2200 N 13 γ2 ∑ Ek

N −|S∪{ j}|

wr,S∪{ j} + 2200 N 12 1 + P TΞ .

(A.29)

k =1

Since r, j, and S were arbitrary, the preceding two case bounds hold throughout their stated ranges. For every integer 0 ≤ s ≤ N − 1, define n o Ms := max EiN −s (wr,S ) : r, i ∈ [ N ], S ⊆ [ N ] \ {r } , |S| = s . (A.30) When s = N − 1, every feasible pair (r, S) in (A.30) satisfies S = [ N ] \ {r }. Hence j ∈ S ∪ {r } for every j ∈ [ N ], and (A.22) applies at order one. For every integer 0 ≤ s < N − 1, (A.22) and (A.29) give n o Ms ≤ max 2200 N 12 P TΞ , 2200 N 14 γ2 Ms+1 + 2200 N 12 1 + P TΞ . Moreover, 2200 N 14 γ2 ≤ 212 N −26 ≤ 2−14 ≤

1 . 2

Backward induction thus proves, for every integer 0 ≤ s ≤ N − 1, Ms ≤ 2201 N 12 1 + P TΞ . 20

(A.31)

Finally, apply (A.26) at order N and use (A.31) with s = 0. For every r ∈ [ N ], T

∑

(t) 3/2

λr

δ N gr

(t) 2 ∞

t =1

N ≤ 8N ∑ E jN (wr,∅ ) + 2Cmulti N 13 1 + PTΞ . j =1

Summing over r, using Cmulti < 2128 , and applying (A.31) prove N

∑∑

(t) 3/2

λr

δ N gr

r =1 t =1

(t) 2 ∞

≤ 2204 N 15 + 2129 N 14 1 + PTΞ ≤2204 N 16 1 + PTΞ ,

as claimed. Proof of Theorem 3.3. Fix T ≥ 1 and set η = 2−94 /( N 20 Ξmax ). Then (A.20) holds, and 6 · 228 ηΞmax N 6 = 6 · 2−66 N −14 ≤

1 . 100

(t)

≤ 1/100 for every i ∈ [ N ] and t ∈ [ T ], as required in the derivation of (A.19). By (A.21) and (3.3),

Thus, by Lemma A.4, 2ηΞi ei

∞

N T (t) 3/2 (t) 2 80η ∑ ∑ Ξi λi ei ≤80 · 2110 N −4 1 + PTΞ , ∞

i =1 t =1

1 N Pi,T ≥293 N 20 PTΞ . 2η i∑ =1 Since 80 · 217 ≤ 224 ≤ N 24 , the coefficient of P TΞ after substitution into (A.19) is nonpositive. Hence N

i =1

∑ [Regi (T )]+ ≤ 4 · 294 N 20 Ξmax ∑ Γi + 80 · 2110 N −4 .

The definitions of Γi , Ξi , and mmax give N

Ξmax ∑ Γi ≤ 4 · 104 N (1 + log (mmax + 1))4 . i =1

Consequently, N

∑ [Regi (T )]+ ≤5 · 2109 N 21 (1 + log (mmax + 1))4 + 80 · 2110 N −4

i =1

≤7 · 2109 N 21 (1 + log (mmax + 1))4 ≤2112 N 21 (1 + log (mmax + 1))4 .

Geometry of Qm

Fix an integer m ≥ 2. Recall ψm and Γm from Section 3: m

ψm (x) = ∑ x ( a) log x ( a),

Γm = (log m)2 + 2 log m + 2.

a =1

Throughout this section, every dummy action index ranges over [m]; in particular, ∑ a := ∑ a∈[m] .

B.1

em Convexity of ψ

For an interior x ∈ ∆m , define Wm (x) := ∑ x ( a) (log x ( a) − ψm (x)) . 2

Let a ∼ x and set ε := − log x ( a). For every t ≥ 0, Pr(ε ≥ t) =

∑ − x(a) ≤ min 1, me−t ,

a:x ( a)≤e t

so the tail-integral formula gives E ε2 ≤(log m)2 + 2 log m + 2 = Γm , h i E ε4 ≤(log m)4 + 4(log m)3 + 12(log m)2 + 24 log m + 24 ≤ 4Γ2m . The last inequality follows by expansion and holds for m ≥ 2. Thus Wm (x) = Var(ε) ≤ Γm , h i h i 4 4 4 4 x ( a ) log x ( a ) − ψ ( x )| = E ε − E ε ≤ 8 E ε + E ε ≤ 64Γ2m . [ ]| ( [ ]) | | m ∑

(B.1) (B.2)

For every z ∈ Rm satisfying 1⊤ z = 0,

⟨∇ψm (x), z ⟩ = ∑ (log x ( a) − ψm (x)) z( a). a

z ( a )2 . a x ( a)

⟨∇ψm (x), z ⟩2 ≤Γm ∑

The last inequality follows from weighted Cauchy–Schwarz and (B.1). em from Section 3: For λ > 0 and y = λx, recall ψ √ √ em (λ, y ) = − 1 − λ + λ [ψm (y/λ) − 2Γm − 3] ψ e m , with ψ em (0, 0) = −1. on ∆

(B.3)

e m and strictly convex in em is finite and convex on ∆ Lemma 3.1. For every integer m ≥ 2, the function ψ m its relative interior. For every integer m ≥ 2 and θ ∈ R , the maximizer defining Qm (θ ) is unique and e m . More explicitly, for every integer m ≥ 2 and θ ∈ Rm , the function on (0, 1) given belongs to relint ∆ by √ √ m m ′ θ ( a) ′ θ ( a) 2Γ + 3 + log exp λ λ θ ( a ) exp ∑ ∑ m a = 1 a = 1 1 √ √ − λ′ 7−→ √ − m ′ 1 − λ′ λ′ λ θ ( a ) exp ∑ a =1 is strictly increasing, tends to −∞ at the left endpoint, and tends to +∞ at the right endpoint. Let λ ∈ (0, 1) denote its unique zero. Then √   λ exp λ θ ( a) a∈[m]   . √ Qm (θ ) = λ, m λ θ ( b ) exp ∑ b =1 Moreover, for every integer m ≥ 2, em (µ) − inf ψ em (µ) ≤ 2Γm + log m + 4. sup ψ em µ∈ ∆

em µ∈ ∆

Proof. Fix an interior point µ = (λ, λx) and write a tangent vector as (s, sx + λz ), where s ∈ R and 1⊤ z = 0. Define v := ( x ( a) (log x ( a) − ψm (x))) a∈[m] , β :=2Γm + 3 − ψm (x) − Wm (x),

ωλ :=

λ 1−λ

3/2 .

Since 1⊤ z = 0, v( a)z( a) , x ( a) a

⟨∇ψm (x), z ⟩ = ∑

v ( a )2 . a x ( a)

Wm (x) = ∑

Direct differentiation gives

(s, sx + λz )⊤ ∇2 ψem (µ) (s, sx + λz ) √ z ( a )2 v( a)z( a) 2Γm + 3 − ψm (x) + ωλ 2 = λ∑ − λ−1/2 s ∑ + s x ( a ) x ( a) 4λ3/2 a a √ [z( a) − (s/(2λ))v( a)]2 2Γm + 3 − ψm (x) − Wm (x) + ωλ 2 = λ∑ + s . x ( a) 4λ3/2 a √ By (B.1) and the bounds ψm (x) ≤ 0 and −ψm (x) ≤ log m ≤ Γm , Γ m + 3 ≤ β ≤ 3(1 + Γ m ). By (B.3) and Young’s inequality, v( a)z( a) 1√ z ( a )2 Γm λ∑ + 3/2 s2 . ≤ x ( a ) 2 x ( a ) 2λ a a

λ−1/2 |s| ∑

(B.4)

(B.5)

Substitution gives

(s, sx + λz )⊤ ∇2 ψem (µ) (s, sx + λz ) ≥

z ( a )2 s2 3s2 1√ λ∑ . + 3/2 + 2 4λ 4(1 − λ)3/2 a x ( a)

(B.6)

Continuity at λ = 0, convexity on the closed domain, and the range bound follow from − log m ≤ ψm (x) ≤ 0. The one-sided λ-derivatives of ψem diverge at λ ∈ {0, 1}, while ∂ a ψm (x) = 1 + log x ( a) → −∞ as x ( a) ↓ 0. Hence Qm (θ ) is interior for every θ ∈ Rm ; strict convexity gives uniqueness. Fix θ ∈ Rm and λ′ ∈ (0, 1). Entropy conjugacy gives ! o √ √ n √ ′ maxm λ ⟨θ , x⟩ − λ′ ψm (x) = λ′ log ∑ exp λ′ θ ( a) , x∈ ∆

and its unique maximizer is

√

λ′ θ ( a) a∈[m] √ . ′ λ θ ( a) ∑ a exp

exp

Thus, after optimizing over x, the objective defining Qm (θ ) as a function of λ′ is " !# √ √ √ 1 − λ′ + λ′ 2Γm + 3 + log ∑ exp λ′ θ ( a) . a

Its derivative is √ √ ′ θ ( a) ′ θ ( a) λ θ ( a ) exp λ 2Γ + 3 + log exp ∑ ∑ m a 1 a 1 √ . √ + + − √ 2 ∑ exp ′ θ ( a) 2 1 − λ′ 2 λ′ λ a em (λ j , y ). For Fix distinct λ0 , λ1 ∈ (0, 1). For every j ∈ {0, 1}, let y j ∈ λ j ∆m maximize ⟨θ , y ⟩ − ψ every t ∈ (0, 1),

(1 − t)y0 + ty1 ∈ ((1 − t)λ0 + tλ1 ) ∆m . Strict concavity of the lifted objective therefore implies strict concavity of the scalar objective, so its derivative is strictly decreasing. The function in the lemma is −2 times this derivative and is therefore strictly increasing. The derivative tends to +∞ as λ′ ↓ 0 and to −∞ as λ′ ↑ 1, which gives the two limits in the lemma. Its unique zero and the conditional maximizer give the formula for Qm (θ ).

B.2

Bounds for Qm

d x ≤Ξm J (θ + rξ ) dr m r =0 ∞ →1

d . ym (θ + rξ ) ξ, dr r =0

(A.3)

For every integer m ≥ 2 and θ , e ∈ Rm , set θ ′ := θ + e, µ := Qm (θ ), µ′ := Qm (θ ′ ), and b λ := max {λm (θ ), λm (θ ′ )}. If Ξm ∥e∥∞ ≤ 1/100, then λm (θ ′ ) ≤ Ξ m ∥e∥ ∞ , λm (θ ) √ e, ym (θ ′ ) − ym (θ ) ≤20 2Ξm b λ3/2 ∥e∥2∞ , p n o √ 2 b λ xm (θ ′ ) − xm (θ ) 1 ≤16 2Ξm min Dψem (µ′ , µ), Dψem (µ, µ′ ) , n o sym Dψe (µ′ , µ) ≤4 min Dψem (µ′ , µ), Dψem (µ, µ′ ) . log

(A.4) (A.5) (A.6) (A.7)

Proof. Fix an integer m ≥ 2 and θ ∈ Rm , and write Qm (θ ) = (λ, λx). e m . The Hessian By Lemma 3.1, the maximizer defining Qm (θ ) is unique and belongs to relint ∆ in (B.4) is positive definite, so the implicit-function theorem makes Qm and xm smooth.

B :=diag(x) − xx⊤ ,

ι := (log x ( a) − ψm (x)) a∈[m] ,

v := ( x ( a)ι( a)) a∈[m] ,

1 w := x + v, 2

β :=2Γm + 3 − ψm (x) − Wm (x), d For e ∈ Rm , write dr Qm (θ + re)

r =0

ωλ :=

λ 1−λ

3/2 .

= (s, sx + λz ). The linearized first-order condition gives,

for every ξ ∈ Rm satisfying 1⊤ ξ = 0,

√

[z( a) − (s/(2λ))v( a)]ξ ( a) =λ ⟨e, ξ ⟩ , x ( a) a β + ωλ s = ⟨e, w ⟩ . 4λ3/2

λ∑

Therefore, s=

4λ3/2 ⟨e, w ⟩ , β + ωλ

√

λBe +

s v. 2λ

Consequently, Jmx (θ ) and Jym (θ ) are √ 2 ⊤ λ B+ vw , β + ωλ 4 Jym (θ ) =λ3/2 B + ww ⊤ . β + ωλ Jmx (θ ) =

(B.7)

By (B.1) and (B.5),

∥v ∥1 ≤

√

Γm ,

∥w ∥1 ≤ 1 +

1√ Γm , 2

∥B ∥∞→1 ≤ 2.

Consequently,

√ ∥Jmx (θ )∥∞→1 ≤5 λ,

(B.8)

e⊤ Jym (θ )e ≤10λ3/2 ∥e∥2∞ ,

(B.9)

|s| ≤6 ∥e∥ ∞ . λ

(B.10)

(B.8) proves (A.2); integrating (B.10) along θ + te, t ∈ [0, 1], proves (A.4). Let ϑ : [0, 1] → Rm be differentiable and set µ(r ) := Qm (ϑ(r )) = (λ(r ), λ(r )x(r )). Fix r ∈ [0, 1], suppress the argument r, and set s :=λ̇,

τ := s/λ,

ẋ ( a)2 , a x ( a)

E := ∑

H :=µ̇⊤ ∇2 ψem (µ)µ̇. Differentiating B, ψm , v, Wm , and β with respect to r gives Ḃ =diag(ẋ) − ẋx⊤ − xẋ⊤ , ψ̇m = ∑ ι( a) ẋ ( a), a

v̇( a) = ẋ ( a)(1 + ι( a)) − x ( a)ψ̇m , Ẇm = ∑ ẋ ( a)(ι( a)2 + 2ι( a)),

a ∈ [ m ], β̇ = −ψ̇m − Ẇm .

Weighted Cauchy–Schwarz and (B.1) and (B.2) yield √ √ p Ḃ ∞→1 ≤ 3 E , ∥v̇ ∥1 + ∥ẇ ∥1 ≤ 6 1 + Γm E ,

√ β̇ ≤ 13(1 + Γm ) E .

The two scalar estimates √ q λ ω λ ( λ −1 + (1 − λ ) −1 ) ≤ 3 λ−3/2 + (1 − λ)−3/2 , ( β + ω λ )2 λ3/2 ωλ (λ−1 + (1 − λ)−1 ) √ ≤ 2 ( β + ω λ )2 follow by splitting at λ = 1/2. The derivative of (B.7) is 1 J˙mx = τJmx + 2

√ 2(v̇w ⊤ + v ẇ ⊤ ) 2vw ⊤ ( β̇ + ω̇λ ) λ Ḃ + − , β + ωλ ( β + ω λ )2 26

(B.11)

(B.12) (B.13)

3 ω̇λ = ωλ s λ−1 + (1 − λ)−1 . 2 Substituting (B.8), (B.11) and (B.12) and the bounds on v, w, β gives √ √ q √ x λ E + λ |τ | + |s| λ−3/2 + (1 − λ)−3/2 . J˙m ∞→1 ≤ 200(1 + Γm ) By (B.6),

√ √ √ √ λ E ≤ 2 H,

√

2 √ λ |τ | ≤ √ H, 3

|s|

√ λ−3/2 + (1 − λ)−3/2 ≤ 2 H.

Hence

√ √ J˙mx ∞→1 ≤ 103 (1 + Γm ) H ≤ Ξm H.

(B.14)

For an arbitrary e ∈ Rm , specialize the preceding path to ϑ(r ) = θ + re, r ∈ [0, 1]. At r = 0, the linearized response optimality condition gives d H = e, ym (θ + re) . dr r =0 Applying (B.14) at r = 0 proves (A.3). Fix e ∈ Rm . Along Qm (θ + te), t ∈ [0, 1], let overdots denote derivatives with respect to t, set s := λ̇ and τ := s/λ, and use λ, x, B, ι, v, w, β, and ωλ for their values at t. Define e◦ :=e − ⟨e, x⟩ 1, κ :=

4λ3/2 , β + ωλ

ϖ := ⟨e, w ⟩ ,

T := λ3/2 ∑ x ( a)e◦ ( a)2 , a

S :=κϖ . Applying the formulas for s and z above with z = ẋ at Qm (θ + te) gives, for every a ∈ [m],

√ 1 ẋ ( a) = λe◦ ( a) + τι( a), x ( a) 2

s = κϖ,

e⊤ Jym (θ + te)e = T + S .

Differentiating T , β, ϖ, κ, and S with respect to t gives 3 1 Ṫ = τ T + λ2 ∑ x ( a)e◦ ( a)3 + τλ3/2 ∑ x ( a)e◦ ( a)2 ι( a), (B.15) 2 2 a a √ 1 2 ◦ β̇ = − ∑ x ( a)(ι( a) + 3ι( a)) λe ( a) + τι( a) , 2 a √ √ 1 3 1 1 ◦ ◦ ◦ ◦ ϖ̇ = ∑ x ( a)e ( a) λe ( a) + τι( a) + ∑ x ( a)e ( a)ι( a) λe ( a) + τι( a) , 2 a 2 2 a 2 κ̇ 3 β̇ + ω̇λ = τ− , κ 2 β + ωλ

Ṡ =

κ̇ S + 2κϖ ϖ̇. κ

(B.16)

Using |e◦ ( a)| ≤ 2 ∥e∥∞ for every a ∈ [m], (B.1), (B.2) and (B.13), and weighted Cauchy–Schwarz gives p |κ̇ | ≤ 130 1 + Γm ∥e∥∞ , | τ | ≤6 ∥e∥ ∞ , √ κ √ √ κ |ϖ̇ | ≤8 ∥e∥∞ T + S . Substitution in (B.15) and (B.16) gives

Ṫ ≤12 ∥e∥∞ (T + S), Ṡ ≤160(1 + Γm ) ∥e∥∞ (T + S). Therefore, whenever T + S > 0, d log(T + S) ≤ 200(1 + Γm ) ∥e∥∞ ≤ Ξm ∥e∥∞ . dt

(B.17)

Suppose Ξm ∥e∥∞ ≤ 1/100, and set µt := Qm (θ + te),

t ∈ [0, 1],

H(t) := e⊤ Jym (θ + te)e.

If e ̸= 0, positive definiteness and (B.17) imply maxt∈[0,1] H(t) ≤ 2 mint∈[0,1] H(t). Fenchel duality and Taylor’s integral formula give Dψem (µ1 , µ0 ) = sym

Dψe (µ1 , µ0 ) =

Z 1 0

Z 1

tH(t) dt,

Dψem (µ0 , µ1 ) =

Z 1 0

(1 − t)H(t) dt,

H(t) dt.

Thus each directed divergence is at least one quarter of the symmetric divergence, proving (A.7). By (B.10), λm (θ + te) ≤ 2λm (θ + t′ e) for every t, t′ ∈ [0, 1]. Integrating (B.9) therefore gives √ 3/2 λ ∥e∥2∞ , ⟨e, ym (θ + e) − ym (θ )⟩ ≤ 20 2 b which is stronger than (A.5). Finally, write µℓ = (λℓ , λℓ xℓ ) for ℓ ∈ {0, 1}. Direct differentiation gives ν (t) = (1 − t)µ0 + tµ1 = (λ(t), λ(t)x(t)),

t ∈ [0, 1],

ẋ(t) =

λ0 λ1 (x1 − x0 ) . λ ( t )2

Since λℓ ≤ 2λ1−ℓ for ℓ ∈ {0, 1}, λ(t) ≥ b λ/2 and λ0 λ1 /λ(t)2 ≥ 1/2. Hence (B.6) and weighted Cauchy–Schwarz give 1 pb em (ν (t))ν̇ (t) ≥ √ ν̇ (t)⊤ ∇2 ψ λ ∥x1 − x0 ∥21 . 8 2 Taylor’s integral formula in both orientations yields n o min Dψem (µ1 , µ0 ), Dψem (µ0 , µ1 ) ≥ Since Ξm ≥ 1, this proves (A.6). 28

1 pb √ λ ∥x1 − x0 ∥21 . 16 2

EMA estimates for multilinear games

Use ρ and γ from (A.1) and (3.2).

C.1

EMA kernels and weighted convolution

Lemma A.2. Set K⋆ := A − δ N +1 , and, for every integer 1 ≤ h ≤ N + 1, set Kh := Aδh−1 . For every integer 1 ≤ h ≤ N + 1, the filters in (3.2) satisfy δ =AD,

Kh D = δ h ,

(A.8)

Kh ( I − Dδ N ) =K⋆ δh−1 . (A.9) For every integer 1 ≤ h ≤ N + 1, K ∈ δh , Kh , K⋆ , and 0 ≤ ϵ ≤ 1/(8N ), if ker(K) = (k s )s≥0 , then

∑ eϵs/2 (s + 1)4 |ks | ≤ 228 N 6 .

(A.10)

s ≥0

∑ τ (t)

≤ 259 N 13 ∥φ∥2 .

(A.11)

t =1

Proof. The transfer functions are A( ς ) =

1 , 1 − ρς

δ(ς) =

1−ς , 1 − ρς

Kh ( ς ) =

(1 − ς ) h −1 . (1 − ρς)h

Thus δ = AD and Kh D = δh . Since these operators commute, Kh ( I − Dδ N ) = Aδh−1 − δ N +h = A − δ N +1 δh−1 = K⋆ δh−1 . Set R = 1 + 1/(4N ). Then ρR < 1 and ρR2 = 1 −

1 7 1 − − < 1. 2 2N 16N 16N 3

For ϑ ∈ R and ς = Reiϑ ,

|δ(ς)|2 =

1 + R2 − 2R cos ϑ , 1 + ρ2 R2 − 2ρR cos ϑ

2R(1 − ρ)(ρR2 − 1) d ≤ 0. |δ(ς)|2 = d(cos ϑ ) (1 + ρ2 R2 − 2ρR cos ϑ)2 The maximum on |ς| = R is therefore attained at ς = − R. Since R(4 − 3ρ) ≤ 3 for N ≥ 2, sup |δ(ς)| = |ς|= R

1+R (1 − ρ ) R 3 = 1+ ≤ 1+ . 1 + ρR 1 + ρR 4N

For h ≤ N + 1 ≤ 3N/2, this gives h

sup |δ(ς)| ≤ e9/8 < 4. |ς|= R

Moreover, 1 − ρR ≥ 3/(4N ), and hence sup |Kh (ς)| ≤ |ς|= R

sup |K⋆ (ς)| ≤ |ς|= R

4 ≤ 6N, 1 − ρR 1 + 4 ≤ 6N. 1 − ρR

The same upper bound 6N applies to δh . Cauchy’s coefficient estimate therefore gives

|k s | ≤ 6NR−s ,

s ≥ 0.

Fix 0 ≤ ϵ ≤ 1/(8N ). The inequality log(1 + y) ≥ y/(1 + y) for y ≥ 0 gives log R −

ϵ 1 1 1 ≥ − ≥ . 2 4N + 1 16N 8N

Thus eϵ/2 /R ≤ e−1/(8N ) . Since 1 − e−y ≥ y/2 for 0 ≤ y ≤ 1, we have 1 − eϵ/2 /R ≥ 1/(16N ). Consequently,

∑e

s ≥0

ϵs/2

ϵ/2 s e (s + 1) |k s | ≤6N ∑ (s + 1) R s ≥0 4

≤

144N 5 (1 − eϵ/2 /R)

≤ 144 · 165 N 6 ≤ 228 N 6 ,

where, for every q ∈ [0, 1), ∑s≥0 (s + 1)4 qs = (1 + 11q + 11q2 + q3 )/(1 − q)5 . The absolute convergence permits evaluation at ς = 1, so the coefficients of δh sum to δ(1)h = 0. For the last claim, the output difference at time t ≥ 1 is τ (t) = φ ∑ k s . s≥t

Apply (A.10) with ϵ = 1/(8N ). For every t ≥ 1, τ (t) ≤ e−t/(16N ) ∥φ∥ ∑ es/(16N ) |k s | ≤ 228 N 6 e−t/(16N ) ∥φ∥ . s ≥0

Since e1/(8N ) − 1 ≥ 1/(8N ), summing the squares gives ∞

∑

τ (t)

≤

t =1

256 N 12 ∥φ∥2 ≤ 259 N 13 ∥φ∥2 . e1/(8N ) − 1

( t ∈ [ T ], s ≥ 0).

Then T

∑w

(t)

(Kz )

(t) 2

∑e

≤

!2 ϵs/2

s ≥0

t =1

|k s |

∑ w(t) z (t)

t =1

Proof. The hypothesis on w gives p p w(t) (Kz )(t) ≤ ∑ eϵs/2 |k s | w(t−s) z (t−s) . s ≥0

Extend the scalar sequence on the right by zero outside [ T ]. The ℓ1 ∗ ℓ2 → ℓ2 Young inequality gives the conclusion.

C.2

Score and response movement

Lemma A.4. For every player i ∈ [ N ] and time t ≥ 1, (t) (t) ei ≤ 3 · 228 N 6 , ( I − Dδ N )gi ∞

≤ 3 · 228 N 6 .

(A.12)

∞

If 3 · 228 γN 6 ≤ 1/100, then, for every player i ∈ [ N ] and time t ≥ 1, the two scores in (3.5) at times t and t + 1 satisfy the hypothesis of Lemma A.1, and ( t +1)

log

λi

≤ 3 · 228 γN 6 .

(t) λi (t)

Proof. For every i ∈ [ N ] and t ≥ 1, gi

(s)

∞

≤ 1, and gi

(A.13)

= 0 for every integer s ≤ 0. Since

ei = δ N gi , Lemma A.2 gives the first bound. Moreover, (t) (t) ( t −1) ( I − Dδ N )gi = gbi + ei ≤ 1 + 229 N 6 ≤ 3 · 228 N 6 . ∞

∞

Fix i ∈ [ N ] and t ≥ 1. Then t t −1 ( t +1) (t) (s) ( t +1) (s) (t) η −1 θ i − θi = ∑ gi + gbi − ∑ gi − gbi s =1

s =1

( t +1) = ( I − Dδ N )gi ( t +1)

=gbi

(t)

+ ei .

Applying the preceding bound at time t + 1 and multiplying by ηΞi verifies the hypothesis of Lemma A.1. Applying (A.4) proves (A.13). Lemma A.5. Suppose 3 · 228 γN 6 ≤ 1/100. For every i ∈ [ N ] and t ≥ 1, q √ √ q (t) (t) (t) ≤4 2ηΞi λi ≤ 4 2γ λi , Ji ∞ →1 q √ 2 (t) ( t −1) (t) , λi (Dxi )(t) ≤16 2Ξi Dψei µi , µi 1 q q √ √ (t) (t) (Dxi )(t) ≤3 2 · 230 ηΞi N 6 λi ≤ 3 2 · 230 γN 6 λi . 1

(A.15) (A.16) (A.17)

For every i ∈ [ N ] and horizon T ≥ 1, T

∑

DJ i

(t) 2 ∞ →1

t =1

≤ 16η 2 Ξ2i Pi,T .

(A.18)

Proof. Fix i ∈ [ N ] and t ≥ 1. For every α ∈ [0, 1], ( t −1)

θi

(t)

+ αηdi − θ i = −(1 − α)ηdi ,

and (A.1) and (A.12) give (t)

Ξi (1 − α)ηdi

∞

≤ (1 − α) 3 · 228 γN 6 ≤

1 . 100

Therefore, Lemma A.1 and (A.4) gives, for every α ∈ [0, 1], (t) (t) (t) ( t −1) ≤ e1/100 λi ≤ 2λi . λ mi θ i + αηdi Integrating (A.2) over α ∈ [0, 1] and using ηΞi ≤ γ proves (A.15). (t)

( t −1)

Since θ i − θ i

(t)

= ηdi , (A.6) gives q √ 2 (t) (t) ( t −1) λi (Dxi )(t) ≤ 16 2Ξi Dψei µi , µi . 1

This is (A.16). The identity in (A.14), (A.15), and (A.12) give q √ (t) (t) 30 6 ≤ 3 2 · 2 ηΞi N λi , (Dxi ) 1

which proves (A.17). Since t was arbitrary, this proves the first three assertions. It remains to prove (A.18). Fix t ≥ 1. The fundamental theorem of calculus gives (t) J i − ηJmx i

Z 1 d ( t −1) ( t −1) (t) θi =η (1 − α) Jmx i θ i + αηdi dα, dα 0

Z 1 d (t) ( t −1) (t) (t) + αηdi dα. ηJmx i θ i − J i =η α Jmx i θ i dα 0

By (A.3), the Cauchy–Schwarz inequality, and (A.7), 2 2 (t) (t) ( t −1) (t) , J i − ηJmx i θ i max J i − ηJmx i θ i ∞ →1

∞ →1

sym

≤η 2 Ξ2i Dψe

(t)

( t −1)

µi , µi

(t) ( t −1) ≤4η 2 Ξ2i Dψei µi , µi . (1)

Since t was arbitrary, the preceding bound holds for every t ≥ 1. Since J i for every t ≥ 2 the preceding bound gives DJ i

(t) 2

(0)

= Ji

= ηJmx i (0),

i h ( t −1) ( t −2) (t) ( t −1) , µi . ≤ 8η 2 Ξ2i Dψei µi , µi + Dψei µi

∞ →1

Fix T ≥ 1. Summing over t ∈ [ T ] proves (A.18). Lemma A.7. Suppose 3 · 228 γN 6 ≤ 1/100 and 3 · 228 γN 7 ≤ 1/4. For every j ∈ [ N ], integer 1 ≤ h ≤ N, and horizon T ≥ 1, r (t) 2 T √ (t) h λ δ x ≤ 260 2 N 12 Ξ j P j,T . j ∑ j 1

t =1

Proof. Extend λ j constantly to all nonpositive integer times. By (A.13), for t ∈ [ T ] and s ≥ 0, q log q

(t)

λj

≤ 3 · 227 γN 6 s.

(t−s) λj

The rate condition gives 3 · 227 γN 6 s ≤ s/(8N ). Since δh = Kh D and Dx j vanishes at every nonpositive integer time, Lemmas A.2 and A.3 gives T

∑

(t) λj

δ xj

(t) 2

≤2 N

t =1

≤2

√ 60

∑

(t)

λj

Dx j

t =1 12

(t) 2 1

2 N Ξ j P j,T ,

where the last inequality follows by summing (A.16) over t ∈ [ T ]. Lemma A.8. Suppose 3 · 228 γN 6 ≤ 1/100. For every i ∈ [ N ], integer 1 ≤ h ≤ N, and time t ≥ 1,

δ h xi

(t)

= Ji

K ⋆ δ h − 1 gi

(t)

+ ci,h .

(A.23)

For every i ∈ [ N ], integer 1 ≤ h ≤ N, and horizon T ≥ 1, T

(t) 2

∑ ci,h 1 ≤ 9 · 2116 η 2 Ξ2i N 24 Pi,T ≤ 9 · 2116 γ2 N 24 Pi,T .

t =1

(A.24)

Proof. Apply Kh to (A.14), commute it past J i , and use (A.8) and (A.9) to obtain (A.23). Write k s = ker(Kh )s . By the definition of ci,h , for every t ≥ 1, (t−s) (t) (t−s) (t) − J i di ci,h = ∑ k s J i s ≥1

s −1

= − ∑ k s ∑ DJ i s ≥1

( t −r )

r =0

(t−s)

For every t ∈ [ T ], s ≥ 1, and integer 0 ≤ r < s, (A.12) gives DJ i

( t −r )

(t−s)

≤ 3 · 228 N 6

DJ i

( t −r ) ∞ →1

Weighted Cauchy–Schwarz over the pairs (s, r ), followed by the time shifts α = t − r, gives ! T s −1 T ( t −r ) 2 (t) 2 ∑ ci,h ≤9 · 256 N 12 ∑ s |ks | ∑ |ks | ∑ ∑ DJ i t =1

s ≥1

≤9 · 256 N 12

s ≥1

∑ s |k s |

s ≥1 116 2 2 24 ≤9 · 2 η Ξi N Pi,T .

∑

∞ →1

r =0 t =1

DJ i

(α) 2

α =1

∞ →1

(τ )

The second inequality uses J i = ηJmx i (0) for every integer τ ≤ 0, and the last uses (A.10) and (A.18). By the definition of ci,h , the preceding display proves the first inequality in (A.24). The inequality ηΞi ≤ γ gives T

(t) 2

∑ ci,h 1 ≤ 9 · 2116 γ2 N 24 Pi,T .

t =1

This proves the second inequality.

C.3

Filtered action and payoff differences

Lemma A.9. Let n o √ Cmulti := 2 max 259 , 9 2 · 2121 . Suppose 3 · 228 γN 6 ≤ 1/100. For every i, j ∈ [ N ] and profile x ∈ ∏kN=1 ∆mk , sup m

ξ ∈R j , ∥ξ ∥1 ≤1

∂ j Gi (x)[ξ ] ∞ ≤ 2.

For every i ∈ [ N ] and integer 1 ≤ h ≤ N, there is a sequence χi,h such that, for every t ≥ 1,

δ h gi

(t)

(t) N (t) = ∑ ∂ j G i x( t ) δ h x j + χi,h . j =1

(A.26)

For every i ∈ [ N ], integer 1 ≤ h ≤ N, and horizon T ≥ 1, T

(t) 2

∑

χi,h

t =1

∞

≤ Cmulti N 13 + γ2 N 27 PTΞ .

(A.27)

If γ ≤ N −20 , then, for every i ∈ [ N ], integer 1 ≤ h ≤ N, and horizon T ≥ 1, T

∑

t =1

(t) 2

χi,h

∞

≤ Cmulti N 13 1 + PTΞ .

(A.28)

Proof. For every i ∈ [ N ], integer 1 ≤ q ≤ N, pairwise distinct j1 , . . . , jq ∈ [ N ], profile x ∈ m ∏kN=1 ∆mk , and directions z jℓ ∈ R jℓ , ℓ ∈ [q], multilinearity and the payoff range [0, 1] give q

∂ j1 · · · ∂ jq Gi (x)[z j1 , . . . , z jq ]

∞

≤ 2 ∏ z jℓ 1 . ℓ=1

Indeed, for every output coordinate, expanding Ui over pure profiles bounds the absolute value of the mixed directional derivative of each term in Gi (x) = Ui (x−i ) − ⟨Ui (x−i ), xi ⟩ 1 by q ∏ℓ=1 z jℓ 1 . This proves the first inequality in the statement by taking q = 1. Fix i ∈ [ N ] and an integer 1 ≤ h ≤ N. Use (x j ) j∈[ N ] with the extension from Section 3, and set (t)

gei = Gi (x(t) ) for every integer t. Write k h,s = ker(δh )s for s ≥ 0. Since ∑s≥0 k h,s = 0, for every integer t and s ≥ 0 define the Taylor remainder by N Tay (t−s) (t) χi,t,s := Gi x(t−s) − Gi x(t) − ∑ ∂ j Gi x(t) x j − xj . j =1

Taylor’s formula gives

δh gei

(t)

(t) N Tay = ∑ ∂ j G i x( t ) δ h x j + ∑ k h,s χi,t,s . s ≥0

j =1

(t) For every integer t, nonnegative integer s, distinct j, k ∈ [ N ], and α ∈ [0, 1], the profile x + N mℓ α x(t−s) − x(t) belongs to ∏ℓ= 1 ∆ . The bound with q = 2 gives

h i (t−s) (t) (t−s) (t) ∂ j ∂ k G i x( t ) + α x( t − s ) − x( t ) xj − x j , xk − xk

≤2

(t−s) (t) xj − xj 1

(t−s) (t) xk − xk . 1

Since ∂2j Gi = 0, the integral Taylor remainder and Tay ≤ χi,t,s ∞

R1 0

2(1 − α)dα = 1 yield !2

∑

(t−s) (t) xj − xj 1 j =1

∞

(s)

Since gi

= 0 for every integer s ≤ 0, for every t ≥ 1,

δ h gi

(t) − Gi x(0) ∑ k h,s . = δh gei

(t)

s≥t

Therefore, for every t ≥ 1, set Tay (t) χi,h := ∑ k h,s χi,t,s − Gi x(0) ∑ k h,s . s≥t

s ≥0

Fix T ≥ 1. Weighted Cauchy–Schwarz and Hölder’s inequality give 2

∑ ∑

t =1

s ≥0

Tay k h,s χi,t,s

∑ |kh,s | ∑ |kh,s | ∑ ∑ xj

≤ N3

s ≥0

∞

(t−s)

(t) 4

− xj

j =1 t =1

For every j ∈ [ N ], integer t, and integer s ≥ 1, telescoping and Hölder’s inequality yield s −1

(t) 4

(t−s)

− xj

≤ s3 ∑

Dx j

( t −r ) 4 1

r =0

For every j ∈ [ N ] and integer s ≥ 1, the extension of x j from Section 3 gives T s −1

∑∑

Dx j

( t −r ) 4 1

t =1 r =0

≤s∑

Dx j

(t) 4

t =1

Substitution and (A.10) give 2

∑ ∑

Tay k h,s χi,t,s

(t) 4

t =1

s ≥0

∞

≤ 256 N 15 ∑ ∑

Dx j

(t) 4 1

j =1 t =1

By (A.16) and (A.17), N

∑∑

Dx j

j =1 t =1

≤9 · 261 γ2 N 12 ∑ ∑ λ j

(t)

Dx j

j =1 t =1

√

(t) 2 1

≤9 2 · 265 γ2 N 12 PTΞ . (t)

The second inequality uses λ j ≤

∑ ∑

t =1

Since Gi (x(0) )

∞

(t)

λ j , followed by (A.16). Substitution gives

s ≥0

√ ≤ 9 2 · 2121 γ2 N 27 PTΞ .

Tay k h,s χi,t,s ∞

≤ 1, (A.11) gives T

∑ Gi x

t =1

(0)

∑ kh,s

s≥t

≤ 259 N 13 . ∞

(t)

By the definition of χi,h , for every t ≥ 1, 2 Tay (t) 2 χi,h ≤2 k h,s χi,t,s +2 ∞ s ≥0 ∞

∑

Gi x

(0)

∑ kh,s

s≥t

. ∞

Summing this inequality and using the preceding two estimates proves (A.27). Finally, γ ≤ N −20 implies γ2 N 27 ≤ N −13 ≤ N 13 , which proves (A.28).

Constant Individual Regret in General Games

Analyze & explore related research in Conceptio

Related documents