arXiv CS open access

Constant regret in general games via higher-order optimism

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 REGRET IN GENERAL GAMES VIA HIGHER-ORDER OPTIMISM

arXiv:2609.04113v1 [cs.LG] 3 Sep 2026

OMAR ABBADIc,∗,♯ , RIDA LARAKI∗ , AND PANAYOTIS MERTIKOPOULOS♯

Abstract. 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 log2 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 et al. [25], who very recently derived an O(N 21 log4 K) regret bound through the use of higher-order optimism and an exponential moving average estimator.

1. Introduction The standard model for learning in games typically unfolds as follows: at each instance of a repeated decision process (i) every player chooses an action; (ii) they receive any rewards and/or feedback generated from their chosen actions; (iii) they update their strategies, and the process repeats. In this general setting, the overarching objective of each player is to improve their individual payoff over time, ideally reaching a state where no further improvements are possible or, at the very least—and, perhaps, more pragmatically—not regretting their past choices. This last criterion leads to the seminal notion of (external) regret, first introduced in statistical decision-making by Wald [40] and Savage [33], and subsequently rediscovered in the context of games and approachability by Hannan [17] and Blackwell [6], respectively. At a high level, the individual regret of a player provides a natural “worst-case” performance benchmark, as it compares the player’s cumulative payoff over time to that of the best fixed action in hindsight. Accordingly, these early works also established the existence of no-regret learning procedures, i.e., update rules whose regret grows sublinearly with the horizon of play in any “game against Nature”—that is, against any possible behavior of the learner’s opponents, rational or otherwise. Nonetheless, since the behavior of no-regret learners in a normal form game is not arbitrary but shaped by the actions of all other players, an important question which has remained open since these early days of the field is whether all players following a no-regret learning rule can prevent individual regret from accumulating indefinitely over time. Somewhat more formally: Are there learning rules which, if followed by all players, guarantee constant individual regret to all players, in all games? c Corresponding author. ∗ Univ.

Mohammed VI Polytechnic, CMSIS, MCGT, 11103 Rabat, Morocco. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France. E-mail addresses: omar.abbadi@um6p.ma, rida.laraki@um6p.ma, panayotis.mertikopoulos@imag.fr. Key words and phrases. regret; learning in games; regularized methods; higher-order optimism. ♯ Univ.

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

An important caveat in the above is that any such rule should be uncoupled in the sense of Hart and Mas-Colell [18, 19], i.e., the strategy adjustment of any given player should not depend on the payoff functions of the other players (though it may of course depend on the payoff function of the focal player, and through it, the strategies of other players). An additional consideration is that the feedback available to the players must be sufficiently informative to allow them to leverage the (optimistically) mild evolution of their learned strategies over time. On that account, we work exclusively in the deterministic, full-information setting, where each players receives as feedback their mixed payoff vector at each stage of the process (but no further information); without this assumption, standard information-theoretic lower bounds would exclude the possibility of achieving constant regret, except in very special cases [8, 9]. Our contributions in the context of related work. Our main contribution is that, with these qualifications in mind, the driving question above can be answered in the affirmative. In more detail, we propose an uncoupled, full-information learning rule, which we call higher-order optimism with discounting (HOOD), and which enjoys the following universal guarantee: Main Theorem (Informal version). If all players of a finite N -player game with up to K actions per player follow HOOD, the individual regret of each player i = 1, . . . , N is bounded for all T as Regi (T ) ≤ 45(N + 1)3 [16 + 4 log K + log2 K] = O(N 3 log2 K) .

(1)

An additional appealing feature of the proposed algorithm is that it is horizon-free, i.e., it does not require prior knowledge of the horizon of play. As a result, for any fixed N and K, each player incurs only a finite amount of regret over the entire (possibly infinite) trajectory of play; equivalently, regret does not continue to accumulate as play unfolds. On that account, by standard results in the field, this also means that the empirical distribution of play converges to the game’s set of coarse correlated equilibria at a rate of O(1/T ). To provide the proper context for our contribution, it is instructive to begin with the so-called “adversarial” setting, in which a single learner is involved in a “game against Nature”—that is, they are facing an arbitrary sequence of payoff vectors, not necessarily coming from some underlying normal form game. In this case, the full-information version of the exponential weights algorithm—known √ √ in this context as Hedge [4, 5, 9, 14–16]—guarantees O( T log K) regret, compared to O( T K log K) regret in the bandit case, √ where the learner only has access to their realized payoff. In either case however, the O( T ) dependence is unavoidable without imposing further assumptions on how the sequence of payoff vectors is generated [8, 9]. This is where learning in games enters the stage. If every player follows an iterative learning algorithm, the players’ individual strategy adjustments are likely to be relatively small from one epoch to the next, so the induced sequence of payoff vectors faced by each player is likewise expected to be more predictable. This predictability can be leveraged by algorithms with an “extrapolation-based” structure, that is, where players attempt to anticipate their future payoff landscape in order to take a more informed update step at each iteration—like the original extra-gradient algorithm of Korpelevich [21], the single-query variant of Popov [28], and the like. In the context of regret minimization, the most relevant algorithmic scheme is the optimistic follow-the-regularized-leader (OptFTRL) method proposed by Rakhlin and Sridharan [29, 30] to take advantage of predictable payoff sequences, and which was shown to lead to O(1) regret in two-player zero-sum games under self-play. This constant regret result was subsequently expanded upon by Syrgkanis et al. [36], and Tsuchiya [38] recently obtained optimal bounds for the Optimistic Hedge algorithm in the same setting. Constant regret has also been achieved in several broader structured classes of

CONSTANT REGRET IN GENERAL GAMES

games, including variationally stable games [20], strategically zero-sum and potential games [3] and, more recently, harmonic games [24]. This array of results shows that attaining O(1) regret is possible in the context of game-theoretic learning, but they are all contingent on a certain, amenable “variational” structure. The case of arbitrary games is much more challenging due to the lack of such structure and lack of control over the iterates [1, 7, 23]. One of the key difficulties here is that the movement of one player can unpredictably amplify the movement of another over time; hence, for a long time, it was not known whether the√presence of an underlying game was sufficient to overcome the adversarial worst-case O( T ) regret bound. The first general breakthrough here was the stability analysis of Syrgkanis et al. [36] who showed that, for 1/4 arbitrary multiplayer normal form √ games, it is possible to achieve O(T ) individual regret, thus breaking the adversarial T barrier. Chen and Peng [10] later improved the exponent to 1/6 for two-player general-sum games. The next breakthrough in this thread came from the work of Daskalakis et al. [12] who showed that, somewhat surprisingly, the Optimistic Hedge algorithm actually inncurs only polylogarithmic regret in any games—the first “near-constant” result of its kind1. The proof of Daskalakis et al. [12] introduced in particular a higher-order smoothness analysis showing that the successive temporal differences of the generated sequence of play can be controlled to sufficiently high order. Subsequent work then simplified and strengthened this picture: Farina et al. [13] reduced the individual regret bound to O(log T ) in general convex games, Anagnostides et al. [2] obtained the same O(log T ) horizon dependence for the stronger notion of swap regret in finite games, and, more recently Soleymani et al. [34, 35] reduced the action dependence to polylogarithmic while keeping a O(log T ) dependence on the horizon. Following these developments, the question which naturally remains is whether we can make the ultimate step of descending from unbounded to constant regret in general games, or if there is a fundamental limitation that goes beyond the algorithms and approaches used so far. Our paper provides a bridge for this gap by showing that, under HOOD, the players’ regret can be bounded uniformly over time. In this sense, it completes the sequence of horizon improvements for uncoupled learning in arbitrary games under full information feedback: √ (2) O( T ) −→ O(T 1/4 ) −→ O(polylog(T )) −→ O(log T ) −→ O(1). We summarize this progression in Table 1, where we also describe the specific ex ante tuning required for each algorithm.2 Note also that, in addition to removing the horizon dependence of the bound, our update uses fixed, horizon-independent parameters. There is one concurrent paper that appears in Table 1 but which we did not discuss above, and which achieves constant regret in any game. Gvien its importance, we discuss it in detail in the end of this section. What goes on under the HOOD. The idea behind our algorithm is to make the optimistic prediction more stable, and therefore more predictable, through a carefully tuned combination of regularization, discounting, and past payoff information. In particular, we choose the optimistic predictor in a way that turns the induced prediction error into a geometrically discounted finite difference of order N + 1, compared to the classical optimistic predictor of [28–30], which uses only the previous payoff as its prediction, and leads to a first-order 1A somewhat related result is due to Piliouras et al. [27], who obtain bounded regret for an uncoupled learning dynamic along an O(log T )-sparse subsequence. 2We note here in passing that concurrent work has obtained related improvements for stronger or √ alternative notions of regret: Tsuchiya [39] obtained O(N K 2 log K log T ) swap regret in general games, while Tao and Zheng [37] achieved an optimal O(log K) alternating regret bound. However, because these concern a different measure of regret, we do not include them in Table 1.

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

Work Syrgkanis et al. [36] Daskalakis et al. [12] Farina et al. [13] Soleymani et al. [34] Liu et al. [25] This paper

Individual regret √ O( N log K T 1/4 ) O(N log K log4 T ) O(N K log T ) O(N log2 K log T ) O(N 21 log4 K), uniformly in T O(N 3 log2 K), uniformly in T

Tuning static, depends on N and T only static, depends on N and T only static, depends on N only adaptive, depends on N and K only static, depends on N and K only static, depends on N and K only

Table 1: Selected progression of individual regret bounds for arbitrary finite games.

difference in time. This higher-order structure provides enough regularity to control the prediction error via the method’s regularization mechanism, which is entropic in nature but defined on a lifted space, following a technique introduced by [13]. This lifting additionally allows us to control the positive part of the regret rather than the signed regret, so large positive regret accumulated by certain players cannot be offset in the aggregate by large negative regret contributions by others. The resulting control over the prediction error is then obtained through an expansion which continues only for terms that have not yet been controlled by either Bregman variation or prediction error terms that are proportional to the step size. The termination of this expansion follows from a somewhat surprising interaction between the geometry of the lifted regularization and the combinatorics of the higher-order extrapolation, whereby every term that remains uncontrolled must successively introduce a new player label, because terms associated with labels that have already appeared can already be controlled. Since there are only N players, no term in the expansion can remain uncontrolled beyond the (N + 1)st difference. Moreover, since the HOOD algorithm guarantees constant individual regret, it can easily be upgraded to an adversarially robust algorithm by adding a switching rule that further leverages the boundedness of the regret. The work of Liu et al. [25]. Three days before the submission of the current work, we were made aware of a concurrent paper by Liu et al. [25], who propose an algorithm achieving O(N 21 log4 K) individual external regret in any N -player finite game with up to K actions per player. Even though our two papers were developed completely independently, they exhibit certain striking similarities, which we explain below. First, the ECHO-OFTRL algorithm of Liu et al. [25] also employs a lifted regularization on the simplex in order to identify the players’ lifted regret with the positive part of their external regret, and also replaces the usual one-step prediction error by a geometrically stabilized high-order difference. The main differences with our approach here are in the way that these ingredients mesh together and the resulting analysis: On the one hand, the HOOD predictor encodes the required discounted differences directly in an (N + 1)-th order recurrence, and its analysis uses elementary bounds for this recurrence along with an explicit term-by-term expansion of players’ payoff functions, with the lifted regularizer supplying bounds that control each term once a player label is repeated in the expansion, so the argument terminates after finitely many steps. By contrast, the ECHO-OFTRL algorighm builds its predictor as an N -stage exponential moving average (EMA) cascade, motivated by signal processing and transfer function design, and analyzed via time-domain filter estimates, EMA kernels and weighted convolutions, together with a recursive weighted variation argument.

CONSTANT REGRET IN GENERAL GAMES

Thus, even though both proofs ultimately exploit the number of players present in the game, our approach does so through a more direct algebraic expansion rather than through a recursive weighted variation argument, and our predictor and lifted regularizer are both designed around this choice. This more direct construction ultimately leadso to a sharper bound in the case of HOOD—O(N 3 log2 K) regret for each player compared to O(N 21 log4 K) in the case of Liu et al. [25]. 2. Preliminaries 2.1. General notation. We write 1 for the vector of all ones, Rd+ and Rd++ for the nonnegative and positive orthants, respectively, ⟨u, v⟩ for the usual Euclidean pairing, and, for N ∈ N, [N ] = {1, . . . , N }. For p ∈ [1, ∞], ∥z∥p denotes the usual ℓp norm. If A : Ra → Rb is linear and p, q ∈ [1, ∞], we write the operator norm ∥A∥p→q = sup ∥Au∥q .

(3)

∥u∥p ≤1

We also write [r]+ = max{r, 0}, and A ≲ B (respectively A ≳ B) when A ≤ CB (respectively A ≥ CB) for a universal constant C > 0, where dependence on an additional parameter is indicated by a subscript, and we use the symbol ⊙ to denote coordinatewise multiplication. For probability vectors p, q on the same finite set, we write X pα DKL (p∥q) = pα log , (4) qα α:p >0 α

for the Kullback–Leibler divergence, and, for a differentiable convex function f , we write Df (z ′ , z) = f (z ′ ) − f (z) − ⟨∇f (z), z ′ − z⟩

(5)

for its Bregman divergence. Finally, for a set S, we denote its convex hull by conv(S). 2.2. Finite games. We consider a finite normal form game with player set N = [N ]. For notational simplicity, we assume throughout that every player has the same pure action set AK = [K], K ≥ 2, and we set A = AN K for the pure profile set; this entails no loss for our regret guarantees because unequal action sets may be padded with duplicate actions. Accordingly, player i’s mixed strategy space is the probability simplex XK = {x ∈ RK + : ⟨1, x⟩ = 1},

(6)

N and X = XK is the strategy space.

We moreover write x = (x1 , . . . , xN ) ∈ X for a mixed profile, x−i = (xj )j̸=i for the opponents’ component, and xiαi for the probability that player i plays pure action αi ∈ AK under x. As usual, we identify each pure action α ∈ AK with the corresponding vertex of XK . Player i’s payoff function is ui : A → [−1, 1], and we extend it multilinearly to X so that ui (x) is the expected payoff under the product distribution induced by x: X ui (x) = Eα∼x [ui (α)] = xα ui (α), (7) α∈A

where, for a pure profile α = (α1 , . . . , αN ) ∈ A, xα = gets played under the mixed profile x.

i∈N xiαi is the probability that α

Remark 1 (Payoff normalization). The restriction ui (A) ⊆ [−1, 1] is essentially without loss of generality. Since A is finite, every ui : A → R is bounded, and replacing ui by u bi = ai ui + bi with ai > 0 rescales regret as d i (T ) = ai Regi (T ). Reg (8) Thus the regret guarantees extend to arbitrary payoffs up to the corresponding rescaling factor. ✦

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

2.3. Feedback and regret. At every round t = 1, 2, . . ., player i chooses a mixed strategy xi,t ∈ XK , and we write xt = (x1,t , . . . , xN,t ) for the joint mixed profile. We assume full information feedback: after play, player i observes the payoff vector vi,t ∈ [−1, 1]K with coordinates viα,t = ui (α, x−i,t ), α ∈ AK . (9) By multilinearity, the payoff obtained at round t is therefore ui (xt ) = ⟨xi,t , vi,t ⟩.

(10)

Moreover, for the update and the subsequent analysis, it will be handy to center the payoff vector by the payoff actually obtained by the player in expectation. As such, we set gi,t = vi,t − ui (xt )1.

(11)

giα,t = ui (α, x−i,t ) − ui (xt ),

(12)

Coordinatewise, this gives and therefore ⟨xi,t , gi,t ⟩ = 0,

∥gi,t ∥∞ ≤ 2.

(13)

Finally, player i’s external regret is: Regi (T ) = max

α∈AK

T T X X ui (α, x−i,t ) − ui (xt ) = max giα,t . α∈AK

t=1

(14)

t=1

We recall that, if every player satisfies Regi (T ) ≤ ε(T ) after T rounds, the empirical distribution of play is an ε(T )/T -approximate coarse correlated equilibrium (CCE) [9, 31]. As a direct consequence, a regret guarantee that is uniform in T implies O(1/T ) convergence to the CCE set. 3. Algorithm and main result We shall now describe the learning rule at play. 3.1. Lifted regularization. We start with the regularization, which we define in a “lifted space” that contains the origin, in the spirit of [13]. Define the K-dimensional simplex K = {z ∈ RK + : ⟨1, z⟩ ≤ 1},

and K◦ = {z ∈ RK ++ : 0 < ⟨1, z⟩ < 1},

(15)

◦

so that K is the relative interior of K. Every nonzero z ∈ K has the unique representation z = λx, where λ = ⟨1, z⟩ ∈ (0, 1] and x ∈ XK . For x ∈ XK , let h be the negative entropy X h(x) = xα log xα , (16) α∈AK

with 0 log 0 = 0, and set 1 log2 K. 4 For a nonzero z = λx ∈ K, define the lifted entropic regularizer p √ ψ(0) = 0. ψ(z) = (λ + λ)h(x) − 3L λ(1 − λ), L = 4 + log K +

(17)

(18)

This regularizer induces the lifted mirror map Z(y) = arg max{⟨y, z⟩ − ψ(z)},

(19)

z∈K

and we call Q(y) =

Z(y) ⟨1, Z(y)⟩

(20)

CONSTANT REGRET IN GENERAL GAMES

the choice map. This corresponds to a lifted version of the usual regularized choice map from standard FTRL [22, 26]. Note also that, conditional on the optimal mass λ, the maximization over x is explicit. Indeed, the entropic nature of the regularizer implies that the choice map can be written as a softmax with a λ-dependent temperature: ! √ λ √ y . Q(y) = softmax (21) 1+ λ As such, the only additional optimization introduced by λ is an easy one-dimensional problem. 3.2. The algorithm. We denote the algorithm’s step size by η > 0. We shall now define the predictor : initialize gi,k = mi,k = 0 for −N ≤ k ≤ 0, then, at time t, form the prediction N +1 X N +1 mi,t = (−1)k+1 (1 − δ k )gi,t−k + δ k mi,t−k , (22) k k=1

where its discount factor δ is fixed by the number of players: N δ= . N +1 We moreover write ei,t = gi,t − mi,t

(23) (24)

for its prediction error. We then define the higher-order optimism with discounting (HOOD) algorithm as Algorithm 1. Algorithm 1 HOOD 1: yi,0 ← 0, gi,k , mi,k ← 0 for −N ≤ k ≤ 0 2: for t = 1, 2, . . . do 3: compute mi,t from (22), set yi,t−1/2 ← yi,t−1 + mi,t 4:

update xi,t ← Q(ηyi,t−1/2 ), play xi,t

5: observe vi,t , set gi,t ← vi,t − ui (xt )1 and yi,t ← yi,t−1 + gi,t 6: end for

The resulting rule is uncoupled, in the sense that player i only uses the game dimensions N, K, its own mixed action and its observed payoff vectors. Moreover, neither the update nor any of its parameters requires the horizon T . 3.3. Regret guarantee. We may now state our main result: Theorem 1. Let

1 log2 K. 4 Suppose every player uses Algorithm 1 with a step size satisfying 1 0<η≤ . 60(N + 1)3 L = 4 + log K +

(25)

(26)

Then, for every player i, sup Regi (T ) ≤

T ≥1

3L . η

(27)

In particular, for the largest choice η = 1/[60(N + 1)3 ], sup Regi (T ) ≤ 45(N + 1)3 [16 + 4 log K + log2 K].

T ≥1

(28)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

Consequently, sup Regi (T ) = O(N 3 log2 K).

(29)

T ≥1

Note that the admissible step size range in (26) is independent of the horizon T . By the earlier regret-to-CCE remark, we also have the following immediate consequence: PT N Corollary 1. Under the conditions of Theorem 1, let µT = T −1 t=1 i xi,t . Then µT is a 3L ηT -approximate coarse correlated equilibrium. Remark 2 (Adversarial robustness). In the previous theorem, all players are assumed to use Algorithm 1. We can nonetheless exploit the boundedness of its regret guarantee to obtain robustness against adversarial payoff sequences via a simple switching rule. The idea is for each player to follow Algorithm 1 until the regret bound is exceeded, and then switch permanently to a learning algorithm with adversarial regret guarantees. The details are given in Appendix D. ✦ 4. Proof overview In this section we overview the proof of Theorem 1, where the complete proofs are given in the appendices. The proof is based on the following four observations: (1) First, the usual regret bounded by variation in utilities (RVU) inequality for optimistic follow-the-regularized-leader (OptFTRL) suggests the two quantities that must be related. Writing xi,t−1/2 for the optimistic iterate and xi,t for the corresponding unoptimistic iterate, it gives Regi (T ) ≤

T Ω ηX 2 + ∥ei,t ∥∞ η 2 t=1

−

T 1 X Dh (xi,t−1/2 , xi,t−1 ) + Dh (xi,t , xi,t−1/2 ) , η t=1

(30)

(31)

where Ω is the range of the regularizer. The last two Bregman divergences measure the movement of the optimistic iterate to its two neighboring unoptimistic iterates. Thus, if the regret term on the left were nonnegative, (31) would bound this Bregman movement in terms of Ω and the prediction error. Bounded regret would then follow from a complementary bound controlling the prediction error by this movement, with sufficiently small coefficients to close the two inequalities. (2) Second, following the lifting idea of Farina et al. [13], the first issue can be resolved by performing the regularized update on the lifted simplex K introduced in Section 3. Since K contains the origin and the payoff vectors are centered as in (11), the regret term in the resulting RVU inequality becomes [Regi (T )]+ and is therefore nonnegative. (3) Third, the needed prediction error bound can be obtained using higher-order time differences. This part is inspired by the higher-order smoothness argument of Daskalakis et al. [12] where, as in their proof, successive payoff differences are related to strategy differences, which are then related back to payoff terms through the learning map. Here, instead of proving that sufficiently high finite differences of the resulting dynamics are small, we choose the predictor so that its prediction error already contains N + 1 time differences. Conditional on suitable local bounds for the learning map, every term that remains uncontrolled after one more difference must introduce a new player label. Since there are only N players, this expansion terminates after finitely many steps. The discounting in (22) then prevents these higher-order differences from introducing an exponential dependence on N .

CONSTANT REGRET IN GENERAL GAMES

(4) Fourth, this expansion requires local bounds that ordinary entropic OptFTRL satisfies on the simplex: the Jacobian of the choice map must be small (that is, proportional to the step size), Jacobian time differences and Taylor remainders must be controlled by Bregman movement, and a newly revealed variation of a player whose Jacobian already occurs in the expansion must also be controlled by Bregman movement. A naive lift does not preserve the last bound when the optimizing mass becomes small, so the particular regularizer (18) is designed precisely so that all of these controls remain valid after lifting. We now make these four observations more explicit. 4.1. The lifted RVU inequality. For each player i, recall from Algorithm 1 the optimistic score yi,t−1/2 = yi,t−1 + mi,t and the cumulative score yi,t = yi,t−1 + gi,t . Define the corresponding lifted iterates zi,t−1/2 = Z(ηyi,t−1/2 ), zi,t = Z(ηyi,t ), (32) and the Bregman movements Pi,t = Dψ/η (zi,t−1/2 , zi,t−1 ),

Gi,t = Dψ/η (zi,t−1/2 , zi,t ).

(33)

For a horizon T , set P (T ) =

N X T X

Pi,t ,

G(T ) =

i=1 t=1

N X T X

Gi,t ,

E(T ) =

i=1 t=1

N X T X 2 ∥ei,t ∥∞ ,

(34)

i=1 t=1

where ei,t is the prediction error from (24), and write Ω = max ψ(z) − min ψ(z). z∈K

(35)

z∈K

The usual OptFTRL analysis already contains a positive term measuring prediction error and a negative Bregman movement term, but the obstacle to rearranging this inequality is that external regret itself can be negative, so the role of the lift is then to remove this obstacle. Indeed, (13) gives ⟨xi,t , gi,t ⟩ = 0, while K = conv(0, e1 , . . . , eK ). Hence the comparator term in the lifted problem is ( ) T X max⟨z, yi,T ⟩ = max 0, max giα,t = [Regi (T )]+ . (36) z∈K

α∈AK

t=1

The lifted RVU inequality proved in Appendix C.1 therefore gives N X NΩ η + E(T ) − P (T ), [Regi (T )]+ ≤ η 2 i=1

G(T ) ≤

η E(T ). 2

(37)

which is the lifted analogue of the classical RVU inequality (31). Now, since the left-hand side is nonnegative, (37) immediately implies P (T ) + G(T ) ≤

NΩ + ηE(T ). η

(38)

It remains to prove the converse type of control, that is, the prediction error must itself be bounded by the Bregman movement. The bound proved in Proposition C.2 is p p √ 3p E(T ) ≤ 5 N (N + 1) + 2000(N + 1)5 η 3/2 P (T ) + G(T ) + E(T ). (39) 10 Combining (38) and (39) will give a bound on E(T ) which is uniform in T . Thus the main work is to prove (39).

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

4.2. The prediction error and Bregman movement bounds. We first state the bounds used in the higher-order argument, without yet explaining why the lifted regularizer satisfies them, which we postpone to Section 4.5. For a sequence w = (wt ), write (∆w)t = wt − wt−1

(40)

J (y) = DQ(y)

(41)

for its first time difference. Let be the Jacobian of the choice map, and define Ji,t = ηJ (ηyi,t−1 ).

(42)

To control ∆xi,t , note that both xi,t and xi,t−1 are perturbations of the same unoptimistic iterate Q(ηyi,t−1 ). Indeed, xi,t = Q(η(yi,t−1 + mi,t )) ,

xi,t−1 = Q(η(yi,t−1 − ei,t−1 )) .

(43)

Writing Ji,t = ηJ (ηyi,t−1 ), Taylor expansion around ηyi,t−1 gives ∆xi,t = Ji,t ∆yi,t−1/2 + ri,t ,

(44)

ri,t = xi,t − Q(ηyi,t−1 ) − Ji,t mi,t − xi,t−1 − Q(ηyi,t−1 ) + Ji,t ei,t−1 .

(45)

∆yi,t−1/2 = gi,t − ∆ei,t ,

(46)

∆xi,t = ri,t + Ji,t gi,t − Ji,t ∆ei,t .

(47)

where the remainder term is

Since we obtain There are then three bounds in Lemma B.4 that we will use repeatedly. First, ∥Ji,t ∥∞→1 ≤ η,

(48)

so that the terms containing Ji,t ∆ei,t can be controlled by the prediction error energy E(T ). Second, N X T X 2 ∥ri,t ∥1 ≲ (N + 1)2 η 3 P (T ) + G(T ) , (49) i=1 t=1

and N X T X

2 ∥Ji,t − Ji,t−1 ∥∞→1 ≲ η 3 P (T ) + G(T ) ,

(50)

i=1 t=1

so the Taylor remainders and Jacobian differences are controlled by the same Bregman movements appearing in (38). The third bound is used when the same player appears twice in the expansion. If |t − t′ | ≤ N + 1, Lemma B.4 gives 2 2 ∥Ji,t′ ∥∞→1 Ji,t ∆yi,t−1/2 1 ≲ η 3 Pi,t + Gi,t−1 . (51) We refer to (51) as the repeated player bound. The higher-order argument below will use only (48)–(51); afterward we explain how (18) is designed so that they remain valid despite the lifting.

CONSTANT REGRET IN GENERAL GAMES

4.3. Higher-order optimism with discounting. We next explain the prediction error expansion, where the starting point is multilinearity of the game, namely, that every payoff difference reveals strategy differences. Indeed, Lemma B.3 shows that, up to a finite initialization term, ∆gi is a sum of linear maps applied to strategy variations ∆xj , verifying the bounds in (B.55). Substituting (47), each revealed strategy variation has the form ∆xj =

rj |{z}

controlled by (49)

Jj gj |{z}

−

may continue

Jj ∆ej | {z }

(52)

controlled using (48)

so only the middle term may require another time difference. Indeed, applying the discrete product rule gives, suppressing time offsets, ∆(Jj gj ) = (∆Jj )gj + Jj ∆gj .

(53)

The first term is controlled by (50) and ∥gj ∥∞ ≤ 2 from (13). The second again reveals strategy variations through Lemma B.3, and (52) introduces another Jacobian. If the newly revealed variation belongs to a player whose Jacobian is already present in the term, (51) controls it. Thus a term can remain uncontrolled only if it introduces a player label that has not previously appeared in that term, and we will call such a label fresh. This is in particular where higher-order differences enter the argument, in that we build enough time differences directly into the prediction error. Indeed, since every continuing step introduces a fresh label and there are only N players, so N + 1 differences are sufficient to force every expansion branch to terminate. Nonetheless, using the ordinary higher-order difference ∆N +1 would introduce the bound ∆N +1 w ℓ ≤ 2N +1 ∥w∥ℓ2 , 2

(54)

P 2 where, for a vector-valued sequence, we recall that ∥w∥ℓ2 = ( t ∥wt ∥r )1/2 , with r = 1 or ∞ depending on context. This bound is notably exponential in the number of players, and the discounting in Algorithm 1 is chosen to avoid this loss. Indeed, for a sequence w = (wt )t∈Z , define the discounted sum ∞ X N , (55) (σw)t = δ k wt−k , δ= N +1 k=0

where the sequences arising below have their negative index terms set to 0 as specified in Algorithm 1. The predictor identity proved in Appendix B.1 states that ei = σ N +1 ∆N +1 gi .

(56)

Hence the prediction error contains the required N + 1 ordinary differences, paired with geometric discounting. To reveal these differences one at a time, define κp = σ N +1 ∆N +1−p ,

0 ≤ p ≤ N + 1,

(57)

0 ≤ p ≤ N.

(58)

∥κp w∥ℓ2 ≤ 4(N + 1)p+1 ∥w∥ℓ2 ,

(59)

so that κp = κp+1 ∆, The sequence bounds of Lemma B.2 give

where the estimate underlying this bound is ∥(σ∆)q w∥ℓ2 ≤ 2∥w∥ℓ2 ,

0 ≤ q ≤ N + 1,

(60)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

Mt [(J)1,...,p ; (g)1,...,s ; (x)1,...,h ] an obi Jac

stra

m ter

payoff term

∆J

∆g

controlled by η 3 (P + G)

initialization term + strategy variations

teg yt

erm

∆x

∆xj = rj + Jj gj − Jj ∆ej

rj controlled by η 3 (P + G)

Jj gj may continue

j repeated controlled by η 3 (P + G)

−Jj ∆ej controlled by η 2 E

j fresh continue with p + 1 labels

Figure 1: One-step expansion of a continuing term.

for scalar sequences w. Indeed, for vector-valued sequences equipped pointwise with the ℓ1 or ℓ∞ norm, the scalar bound proved in (B.37) gives ∥(σ∆)q w∥ℓ2 ≤ 4(N + 1)∥w∥ℓ2 ,

0 ≤ q ≤ N + 1,

(61)

and combining this with the bound for σ p yields (59), so the discounting prevents the successive differences from producing exponential dependance on the number of players. 4.4. One-step expansion. We may now formalize the recursive expansion. At order p, call a term continuing if it contains p Jacobians with distinct player labels and has not yet been controlled by (48)–(51). The precise conditions on its payoff and strategy factors are those in Lemma C.1—for which give an abbreviated version below—and they are importantly preserved whenever a branch continues. Lemma 1 (One-step expansion; abbreviated). Let M be a continuing term at order 1 ≤ p ≤ N . Then X ∆M = RM + M ′, (62) M ′ ∈C(M )

where RM collects terms controlled by P (T ) + G(T ), or E(T ), with the bound given in (C.42), the M ′ ∈ C(M ) terms are continuing terms at order p + 1, and |C(M )| ≤ 3p(N − p). In particular, C(M ) = ∅ when p = N .

(63)

CONSTANT REGRET IN GENERAL GAMES

We sketch the two facts in Lemma 1 that drive the argument. By (58), moving from order p to order p + 1 amounts to applying one ordinary difference. If this difference falls on a Jacobian, (50) controls the resulting term; if it falls on a payoff, Lemma B.3 produces strategy variations, up to the finite initialization term; if it falls on a strategy factor, such a variation appears directly. In either case, (52) shows that only Jj gj may continue. If j is already one of the existing Jacobian labels, (51) controls the resulting term, so every continuing branch introduces one fresh label. It remains then to count how many such branches are possible. Suppose the term contains s payoff factors, then, by Lemma B.3, each payoff factor can reveal a fixed player label at most twice, while the conditions in Lemma C.1 allow at most p strategy factors carrying any fixed label, so a fixed fresh label can produce at most 2s + p ≤ 3p continuing terms, and since N − p labels remain fresh, this gives (63). In particular, after all N labels have appeared, no branch can continue. Finally, the branching must be compensated by the small factor gained by each continuation. By (59), moving one level further costs one additional factor O(N +1), while every continuing branch gains a new Jacobian of norm at most 2η by Lemma B.4. Hence the total weighted continuation factor is at most 3 3p(N − p) 2η(N + 1) ≤ N 2 (N + 1)η, (64) 2 and this is in particular why the step size must be of order N −3 . Under (26), the continuing contribution contracts geometrically from one level to the next, while Lemma 1 guarantees that it terminates altogether after N levels. Iterating Lemma C.1, together with Lemmas B.2–B.4, gives Proposition C.2, i.e., (39). The three terms in that bound correspond respectively to the finite initialization cost, the terms stopped using Bregman movement, and the −Jj ∆ej terms in (52). 4.5. Why the lifted regularizer preserves the expansion bounds. We now return to (48)–(51) and explain why they hold for the lifted choice map. Recall from (18) that, for z = λx = ̸ 0, p √ 1 (65) ψ(λx) = (λ + λ)h(x) − 3L λ(1 − λ), L = 4 + log K + log2 K. 4 The two parts of (65) are chosen to preserve the local entropic bounds needed by the expansion while controlling the additional mass variable. Indeed, to see what must be preserved, first consider ordinary entropy on the original simplex. In that case the analogues of the strategy movement and Jacobian bounds are 2

∥∆xi,t ∥1 ≲ η(Pi,t + Gi,t−1 ),

∥Ji,t ∥∞→1 ≲ η 2 .

(66)

Thus an existing Jacobian paired with a newly revealed variation of the same player contributes η 2 · η(Pi,t + Gi,t−1 ) = η 3 (Pi,t + Gi,t−1 ), (67) which is the bound used in (51). The lifted regularizer is thus chosen so that this cancellation survives when the mass is allowed to vary. Indeed, consider first a naive lift ψ0 (λx) = λh(x) + φ(λ),

(68)

where φ depends only on λ. Conditional on the optimizing mass, the factor λ cancels from the strategy dependent part of the optimization, so its normalized choice map is still Q0 (y) = softmax(y), and its Jacobian therefore remains of constant order when λ becomes small. On the other hand, the strategy-dependent part λh(x) gives only 2

∥x′ − x∥1 ≲

1 Dψ (λ′ x′ , λx). λ 0

(69)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

The analogue of the repeated player bound would therefore contain η 3 /λ and become uncontrolled as λ → 0. As for the term λh(x) in (65), it retains this Bregman control, where Lemma A.5 gives 1 2 ∥x′ − x∥1 ≲ Dψ (λ′ x′ , λx) (70) λ √ for nearby scores. The additional term λh(x) then contributes by suppling the compensating factor in the Jacobian. Indeed, Lemma A.3 gives the choice map formula already stated in (21), ! √ λ √ y . Q(y) = softmax (71) 1+ λ If the optimizing mass were fixed, (71) would immediately make the Jacobian smaller by √ a factor of order λ. Nonetheless, the optimizing mass itself depends on the score, so we must p also control this dependence. This is the role of the single mass-dependent term −3L λ(1 − λ) and of the particular choice of L. Indeed, Lemma A.1 gives 1 (72) Varx (log x) ≤ log2 K + log K + 2 = L − 2. 4 Together with the mass-dependent term, this controls the interaction between mass and strategy variation in the Hessian, where Lemma A.2 and (A.32) then show in particular that the lifted regularizer is 1-strongly convex in ℓ1 , so that Lemma A.3 yields a unique smooth lifted mirror map and choice map. More importantly for the expansion, the same term also gives the lower bound (A.43) for the denominator arising when the optimality condition for the mass is differentiated. Equations (A.54) and (A.65) then give 1 |Dλ(y)[q]| ≲ λ3/2 ∥q∥∞ , |D log λ(y)[q]| ≤ ∥q∥∞ . (73) 4 The first bound √ ensures that the dependence of the optimizing mass on the score does not destroy the λ factor suggested by (71), where Lemma A.4 gives indeed √ (74) ∥J (y)∥∞→1 ≤ 2 λ. The second bound integrates to the mass comparison (A.66), which allows the masses corresponding to the nearby times in the N + 1-step expansion to be compared. Consequently, along the learning dynamics, Lemmas A.4 and A.5 give, for the nearby times appearing in the expansion, η 2 2 Pi,t + Gi,t−1 , ∥Ji,t′ ∥∞→1 ≲ η 2 λi,t−1 . (75) ∥∆xi,t ∥1 ≲ λi,t−1 The mass factors therefore cancel and give a bound as in (66): η 2 η λi,t−1 = η3 , λi,t−1

(76)

which gives the repeated player bound (51) through Lemma B.4. Finally, the lifted Bregman control also controls changes in the choice map. Indeed, Lemma A.7 allows us to bound Jacobian variation by lifted Bregman divergence and Lemma A.8 converts this into a Taylor remainder bound. Applied to the iterates, these bounds give (49) and (50) through Lemma B.4. Hence all the local bound assumed in the higher-order expansion are preserved after lifting, which was our goal. Note then that the dependence on the number of actions also enters through the regularizer, where, by Lemma C.2, 13 L = O(log2 K). (77) Ω≤ 6

CONSTANT REGRET IN GENERAL GAMES

4.6. Closing the loop. combine the two parts of the proof. Substituting (38) √ We can√now √ into (39) and using a + b ≤ a + b gives p √ √ E(T ) ≤ 5 N (N + 1) + 2000(N + 1)5 η N Ω (78) p 3 + 2000(N + 1)5 η 2 + E(T ). (79) 10 p The step-size condition (26) makes the coefficient multiplying E(T ) on the right-hand side small enough to absorb into the left-hand side. Together with (77), the calculation in Appendix C.3 gives E(T ) < 622 (N + 1)6 L, (80) uniformly in T . Finally, the player-specific version of the lifted RVU inequality gives Ω η [Regi (T )]+ ≤ + E(T ), (81) η 2 and, using Lemma C.2 and (80), [Regi (T )]+ <

3L , η

(82)

hence, since Regi (T ) ≤ [Regi (T )]+ , this proves Theorem 1. In particular, for the largest admissible step size η = 1/[60(N + 1)3 ], this gives sup Regi (T ) = O(N 3 log2 K).

(83)

T ≥1

5. Concluding remarks We have shown that uncoupled full information learning can achieve regret that is uniformly bounded in time in every finite game. Compared with the previous O(N log2 K log T ) perplayer bound [34], our result removes the remaining dependence on the horizon, at the cost of an additional N 2 factor in the number of players. Natural future research directions are whether this N 2 price can be reduced, whether the log2 K dependence can be improved, and whether bounded regret is possible in broader game classes, and for stronger notions of regret, such as swap regret. Another important question is whether we can obtain bounded regret from simpler dynamics—such as the classical OptFTRL update, for a suitable choice of regularizer and step size—and whether these dynamics retain good regret bounds in the game’s parameters. Acknowledgments Some design choices in the algorithm and its analysis were assisted by ChatGPT 5.6 Sol.

Appendix A. Lifted regularizer and choice map This section proves properties of the lifted regularizer used in Section 4. A.1. Hessian bounds. For x ∈ XK and values aα defined on the support of x, write  2 X X Varx (a) = xα aα − xβ aβ  . α:xα >0

(A.1)

β:xβ >0

For probability vectors p, q ∈ RK + , we use the following KL bounds [11, 32]: DKL (p∥q) ≥

1 2 ∥p − q∥1 , 2

√ √ 2 DKL (p∥q) ≥ ∥ p − q∥2 .

(A.2)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

For x ∈ XK , Gibbs’ inequality gives [11] log K + h(x) = DKL (x∥K −1 1) ≥ 0.

− log K ≤ h(x) ≤ 0,

(A.3)

◦ ◦ K Set XK = XK ∩ RK has the unique decomposition ++ . If z = λx ∈ K , every ξ ∈ R

b = ⟨1, ξ⟩,

ξ = bx + λw,

⟨1, w⟩ = 0.

(A.4)

Lemma A.1 (Logarithmic moment). For every x ∈ XK , Varx (log x) ≤

1 log2 K + log K + 2 = L − 2. 4

Proof. We first establish the auxiliary moment bounds, valid for every p ∈ RK + with 1: X pα | log pα |2 ≤ 4L,

(A.5) P

α pα ≤

(A.6)

α:pα >0

pα | log pα |4 ≤ 26L2 .

(A.7)

α:pα >0

For t ≥ 0, X

pα ≤ min{1, de−t },

(A.8)

α:− log pα ≥t

where the sum is over α with pα > 0. Hence, for every integer q ≥ 1, using aq+ = R ∞ q−1 q 0 u 1{a ≥ u} du and interchanging the finite sum with the integral gives Z ∞ X X pα (− log pα − log K)q+ = q uq−1 pα du (A.9) 0

α:pα >0

α:− log pα ≥log K+u

Z ∞ ≤q

uq−1 e−u du = q!.

(A.10)

≤ log K + (q!)1/q .

(A.11)

Minkowski’s inequality therefore yields !1/q X

pα | log pα |

α:pα >0

√ Since 2 L ≥ log K + 2, (A.11) with q = 2 gives (A.6). For q = 4, use 241/4 < 5/2 and √ L ≥ 2: √ 9√ 5 1 log K + 241/4 < log K + ≤ 2 L + ≤ L. (A.12) 2 2 4 Hence 4 X 9 pα | log pα |4 ≤ L2 < 26L2 , (A.13) 4 α which is (A.7). Now let p = x ∈ XK . Since variance is bounded by the second moment around any deterministic center, 2 X 1 Varx (log x) ≤ xα − log xα − log K . (A.14) 2 α:x >0 α

If − log xα ≤ log K, the squared term is at most (log K)2 /4; otherwise, 2 Z − log xα 1 (log K)2 1 − log xα − log K = + 2 t − log K dt. 2 4 2 log K

(A.15)

CONSTANT REGRET IN GENERAL GAMES

Using (A.8) and writing the square as an integral, 2 Z ∞ X 1 1 (log K)2 xα − log xα − log K 2 t − log K de−t dt ≤ + 2 4 2 log K α:x >0

(A.16)

1 log2 K + log K + 2 = L − 2. 4

(A.17)

This proves (A.5).

■

For nonzero z = λx ∈ K, define p √ φ(z) = λ h(x) − 3L λ(1 − λ),

φ(0) = 0.

(A.18)

Lemma A.2 (Hessian of the square-root terms). Let z = λx ∈ K◦ and let ξ = bx + λw satisfy (A.4). Then Lb2 D2 φ(z)[ξ, ξ] ≥ 3/2 ≥ 0. (A.19) 2λ Moreover, 1 √ X wα2 D2 φ(z)[ξ, ξ] ≥ λ + 3b2 . (A.20) 2 x α α Proof. For z(q) = z + qξ = λ(q)x(q), λ(q) = λ + qb,

x(q) = x +

qλ w, λ + qb

(A.21)

so x′ (0) = w and x′′ (0) = −2bw/λ. Since ⟨1, w⟩ = 0, Dh(x)[w] = ⟨w, log x⟩,

D2 h(x)[w, w] =

X w2

xα

(A.22)

Differentiating φ(z(q)) twice at q = 0 gives " # X w2 3L b2 α 2 −3/2 2 − h(x) . D φ(z)[ξ, ξ] = λ λ − λb⟨w, log x⟩ + xα 4 (1 − λ)3/2 α

(A.23)

Moreover, |⟨w, log x⟩| = |⟨w, log x − h(x)1⟩| ≤

Varx (log x)

X w2 α

Set S =

2 α wα /xα and V

!1/2

xα

(A.24)

= Varx (log x). Then

V b2 . 4 Using (A.3), (A.5), and (1 − λ)−3/2 ≥ 1, the bracket in (A.23) is therefore at least λ2 S − λb⟨w, log x⟩ ≥ −

b2 2L + 2 2 L (3L − V − h(x)) ≥ b ≥ b2 , 4 4 2 which proves (A.19). For the stronger bound, use instead 1 1 λ2 S − λb⟨w, log x⟩ ≥ λ2 S − V b2 . 2 2 √ Writing s = λ, (A.23), (A.5), and L ≥ 4 give 2 1√ 3L 2 −3/2 b D φ(z)[ξ, ξ] ≥ λS + λ − 2V − h(x) 2 4 (1 − λ)3/2

(A.25)

(A.26)

(A.27)

(A.28)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

≥

1√ λS + s−3 b2 2

3 − 1 . (1 − s2 )3/2

(A.29)

The function 3(1 − s2 )−3/2 − 1 − 3s3 is increasing on [0, 1), since its derivative is 9s[(1 − s2 )−5/2 − s] ≥ 0, and its value at s = 0 is 2. Thus the last coefficient is at least 3, proving (A.20). ■ Since φ is continuous on K and has positive semidefinite Hessian on K◦ by (A.19), it is convex on K. For z = λx ∈ K◦ , write ψ(z) = λh(x) + φ(z).

(A.30)

If ξ = bx + λw is as in (A.4), then D2 [λh(x)][ξ, ξ] = λ

X w2

xα

(A.31)

Together with (A.20), 1 √ X wα2 2 + 3b2 ≥ ∥ξ∥1 . (A.32) λ λ+ 2 x α α P 2 Indeed, Cauchy–Schwarz gives ∥w∥1 ≤ α wα2 /xα . If a = |b| and c = λ∥w∥1 , then λ ≤ 1 implies that the middle expression in (A.32) is at least 3a2 + 32 c2 ≥ (a+c)2 , while ∥ξ∥1 ≤ a+c. Integrating (A.32) along line segments in K◦ and approximating boundary points shows that ψ is 1-strongly convex with respect to the ℓ1 norm on K. In particular, D2 ψ(z) is positive definite on K◦ . D2 ψ(z)[ξ, ξ] ≥

A.2. Lifted mirror map and choice map. Lemma A.3 (Lifted mirror and choice map). For every y ∈ RK , Z(y) is unique and belongs to K◦ . If Z(y) = λx, then ! √ λ √ y . x = Q(y) = softmax (A.33) 1+ λ The maps Z and Q are C ∞ . Proof. Continuity follows from (18), (A.3), and r log r → 0 as r ↓ 0. By (A.32), ψ is strictly convex on K◦ . Approximating any two points of K by points of K◦ and passing to the limit shows that ψ is convex on K. Now, fix y. The objective in (19) is continuous on the compact set K, hence attains its maximum. For fixed 0 < λ ≤ 1, its x-dependent part is √ λ⟨y, x⟩ − (λ + λ)h(x). (A.34) The unique maximizer is (A.33). The maximized value at mass λ ∈ (0, 1) is !! √ K X p √ λ √ yα exp + 3L λ(1 − λ). Vy (λ) = (λ + λ) log 1+ λ α=1

(A.35)

This extends continuously to [0, 1] with Vy (0) = 0, and Vy (λ) lim √ = log K + 3L > 0. λ↓0 λ

(A.36)

Thus λ = 0 is not maximizing. For 0 < λ < 1, the maximizing x = x(λ) is unique and smooth by (A.33). Differentiating the unmaximized objective at (λ, x(λ)), the derivative through

CONSTANT REGRET IN GENERAL GAMES

x(λ) vanishes: its x-gradient is a scalar multiple of 1 at the maximizer, while ⟨1, x′ (λ)⟩ = 0. Hence 1 3L 1 − 2λ p Vy′ (λ) = ⟨y, x⟩ − 1 + √ h(x) + . (A.37) 2 2 λ λ(1 − λ) The last term tends to −∞ as λ ↑ 1, while all other terms remain bounded. Hence Vy′ < 0 on some interval (1 − ε, 1); integrating Vy′ on this interval shows Vy (1) < Vy (1 − ε), so λ = 1 is not maximizing. Every maximizer therefore lies in K◦ , where strict concavity of z 7→ ⟨y, z⟩ − ψ(z) gives uniqueness. Finally, at the maximizer, ∇ψ(Z(y)) = y,

(A.38)

and the Hessian of ψ is positive definite on K◦ by (A.32), so the implicit function theorem, applied to (A.38), gives Z ∈ C ∞ (RK ), and normalization gives Q ∈ C ∞ (RK ). ■ A.3. Local stability of the choice map. For y ∈ RK , write λ = λ(y) = ⟨1, Z(y)⟩,

Z(y) = λx,

x = Q(y).

(A.39)

Γx = Diag(x) − xx⊤ .

(A.40)

◦ For x ∈ XK , set

µx = x ⊙ (log x − h(x)1), Then Γx v = x ⊙ (v − ⟨x, v⟩1),

Γx log x = µx ,

∥µx ∥1 ≤

p √ Varx (log x) ≤ L − 2. (A.41)

◦ , define For λ ∈ (0, 1) and x ∈ XK

D(λ, x) =

3L 1 Varx (log x) √ − h(x) + . 4 4(1 − λ)3/2 1+ λ

(A.42)

L L+1 1 . + ≥ 2 2 2(1 − λ)3/2

(A.43)

By (A.3) and (A.5), D(λ, x) ≥

◦ Indeed, Varx (log x) ≤ L − 2 and (1 − λ)−3/2 ≥ 1. For λ ∈ (0, 1) and x ∈ XK , set µx √ . νλ,x = x + 2(1 + λ)

(A.44)

Lemma A.4 (Differential of the choice map). Let y ∈ RK and write Z(y) = λx. Then, for every q ∈ RK , ∥DQ(y)[q]∥1 ≤ ∥q∥∞ , √ ∥DQ(y)[q]∥1 ≤ 2 λ∥q∥∞ .

(A.45) (A.46)

Proof. The first-order condition (A.37) reads 1 3L 1 − 2λ p ⟨y, x⟩ = 1 + √ h(x) − . 2 2 λ λ(1 − λ)

(A.47)

From (A.33), 1 µx √ √ , ∂λ x = √ Γx y = 2 λ(1 + λ)2 2λ(1 + λ) √ √ where the second identity uses Γx y = (1 + λ)µx / λ. Hence ∂λ h(x) =

Varx (log x) √ , 2λ(1 + λ)

∂λ ⟨y, x⟩ =

Varx (log x) . 2λ3/2

(A.48)

(A.49)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

Differentiating (A.37) and collecting terms gives h(x) 3L ′′ −3/2 Varx (log x) √ Vy (λ) = λ + − 4 4(1 − λ)3/2 4(1 + λ)

(A.50)

= −λ−3/2 D(λ, x). (A.51) √ √ √ √ At fixed λ, (A.33) gives Dy x[q] = λΓx q/(1 + λ). Since Γx y = (1 + λ)µx / λ and ⟨1, Dy x[q]⟩ = 0, 1 ′ Dy Vy (λ)[q] = ⟨x, q⟩ + ⟨y, Dy x[q]⟩ − 1 + √ ⟨log x, Dy x[q]⟩ (A.52) 2 λ 1 √ ⟨µx , q⟩ = ⟨νλ,x , q⟩. (A.53) = ⟨x, q⟩ + 2(1 + λ) Differentiating Vy′ (λ(y)) = 0 and using (A.51) gives Dλ(y)[q] =

λ3/2 ⟨νλ,x , q⟩. D(λ, x)

(A.54)

Finally, differentiating (A.33) in y and λ gives √ λ Dλ(y)[q] √ Γx q + √ µx . DQ(y)[q] = 1+ λ 2λ(1 + λ)

(A.55)

Substituting (A.54) yields √ J (y) =

λ √

Γx +

1 ⊤ µx νλ,x . 2D(λ, x)

Assume ∥q∥∞ ≤ 1. By (A.41), ∥Γx q∥1 ≤

Varx (q) ≤ 1,

∥µx ∥1 ≤

(A.56) √

√

∥νλ,x ∥1 ≤ 1 +

L √ ≤ L. 2

(A.57)

Together with (A.43), this gives ∥µx ∥1 ∥νλ,x ∥1 L ≤ < 1. 2D(λ, x) L+1

(A.58)

Equation (A.56) now gives √

λ √ ∥q∥∞ . (A.59) 1+ λ √ √ √ √ √ Since λ/(1 +√ λ) ≤ 1/2 and λ/(1 + λ) ≤ λ, (A.45) and (A.46) follow. Next, (A.43) and ∥νλ,x ∥1 ≤ L give √ 2 L 3/2 |Dλ(y)[q]| ≤ λ ∥q∥∞ ≤ λ3/2 ∥q∥∞ . (A.60) L+1 √ √ √ √ √ For derivative, put s = λ. Since L − 2 ≤ L − 1/ L and, for L ≥ 2, √ the logarithmic √ 3 L/8 + 1/(2 L) ≥ 1, 1√ 7√ ∥νλ,x ∥1 ≤ 1 + L−2≤ L. (A.61) 2 8 Moreover, (A.3) and (A.5) give 3 1 4D(λ, x) ≥ L − . (A.62) 1+s (1 − s2 )3/2 ∥DQ(y)[q]∥1 ≤ 2

CONSTANT REGRET IN GENERAL GAMES

For 0 ≤ s < 1, 3 1 − ≥ 7s. (A.63) 2 3/2 1+s (1 − s ) Indeed, (1 − s2 )−1/2 ≥ 1 + s2 /2, so it is enough that 2 − 6s + 32 s2 + 7s3 ≥ 0. This is clear for s ≤ 1/6, while for s ≥ 1/6 the left-hand side equals 3s 1 (A.64) (s − 12 )2 (7s + 17 2 ) + 4 − 8 ≥ 0. √ Using (A.54) and L ≥ 2 therefore gives 1 |D log λ(y)[q]| ≤ ∥q∥∞ . (A.65) 4 ■ ′

′

′ ′

For y, y ∈ R , with Z(y) = λx and Z(y ) = λ x , integration of (A.65) gives 1 ′ λ′ 1 ′ ≤ exp ∥y − y∥∞ . exp − ∥y − y∥∞ ≤ 4 λ 4

(A.66)

By (A.30), Dψ (λ′ x′ , λx) = λ′ DKL (x′ ∥x) + Dφ (λ′ x′ , λx).

(A.67)

Lemma A.5 (Local Bregman coercivity). Let y, y ′ ∈ RK . Suppose Z(y) = λx, Z(y ′ ) = λ′ x′ , and ∥y ′ − y∥∞ ≤ M ≤ 1. Then " # √ √ ( λ′ − λ)2 ′ −M/4 ′ √ Dψ (Z(y ), Z(y)) ≥ e λDKL (x ∥x) + , (A.68) λ and 2

∥x′ − x∥1 ≤

2eM/4 Dψ (Z(y ′ ), Z(y)). λ

(A.69)

Proof. By (A.66), e−M/4 λ ≤ λ′ ≤ eM/4 λ.

(A.70)

Hence λ′ DKL (x′ ∥x) ≥ e−M/4 λDKL (x′ ∥x). (A.71) Let z(θ) = (1 − θ)Z(y) + θZ(y ′ ) and λ(θ) = ⟨1, z(θ)⟩. By (A.70), λ(θ) ≤ eM/4 λ. Therefore (A.19) gives Z 1 Dφ (Z(y ′ ), Z(y)) = (1 − θ)D2 φ(z(θ))[Z(y ′ ) − Z(y), Z(y ′ ) − Z(y)] dθ (A.72) 0

L (λ′ − λ)2 ≥ e−3M/8 (A.73) 3/2 4 √ λ√ 2 ( λ′ − λ) √ ≥ e−M/4 . (A.74) λ p For the last inequality, (A.70) gives λ′ /λ ≥ e−M/8 , while L ≥ 4 and e−M/8 ≥ 1−M/8 ≥ 7/8 imply 2 7 15 L −M/8 −M/8 2 e (1 + e ) ≥ > 1. (A.75) 4 8 8 Now (A.67) and (A.71) prove (A.68). Finally, (A.2) and (A.71) give 1 2 Dψ (Z(y ′ ), Z(y)) ≥ e−M/4 λ∥x′ − x∥1 , (A.76) 2 which is (A.69). ■

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

The next lemma proves the continuity bounds used in the Jacobian calculation. √ √ ◦ Lemma A.6 (Square-root stability). Let x, x′ ∈ XK and λ, λ′ ∈ (0, 1). Set ε = x′ − x . 2 Then √ |h(x′ ) − h(x)| ≤ 5 L ε, (A.77) √ (A.78) ∥µx′ − µx ∥1 ≤ 14 L ε, | Varx′ (log x′ ) − Varx (log x)| ≤ 31L ε,

(A.79)

∥Γx′ − Γx ∥∞→1 ≤ 3ε. Moreover, ∥νλ,x ∥1 ≤

(A.80)

√

L, (A.81) √ 1√ √ ′ √ ∥νλ′ ,x′ − νλ,x ∥1 ≤ 8 L ε + L | λ − λ|. (A.82) 2 Proof. For 0 ≤ θ ≤ 1, put √ √ a(θ) = (1 − θ) x + θ x′ , pα (θ) = aα (θ)2 . (A.83) √ P √ Since ∥a(θ)∥2 ≤ (1 − θ)∥ x∥2 + θ x′ = 1, we have α pα (θ) ≤ 1. For f1 (s) = s2 log s2 2

and f2 (s) = s2 (log s2 )2 , with the values and derivatives at s = 0 defined by continuity, |f1′ (s)|2 = 4s2 (1 + log s2 )2 ,

|f2′ (s)|2 = 4s2 (log s2 )2 (2 + log s2 )2 .

Since pα (θ) ≤ 1, log pα (θ) ≤ 0. Thus (A.6)–(A.7) give X X |f1′ (aα (θ))|2 ≤ 4 + 4 pα (θ)| log pα (θ)|2 ≤ 16L + 4, α

(A.84)

(A.85)

|f2′ (aα (θ))|2 ≤ 4

pα (θ)| log pα (θ)|4 + 16

pα (θ)| log pα (θ)|2

(A.86)

≤ 104L2 + 64L.

(A.87) 2

Since L ≥ 4, the right-hand sides are smaller than 25L and 121L , respectively. Integration and Cauchy–Schwarz therefore give X √ |x′α log x′α − xα log xα | ≤ 5 L ε, (A.88) α

|x′α (log x′α )2 − xα (log xα )2 | ≤ 11L ε.

(A.89)

Also, ∥x′ − x∥1 ≤

√

x′ −

√

√ x 2

x′ +

√

≤ 2ε.

(A.90)

Together with (A.88), √ this proves (A.77). Next, using µx = x ⊙ log x − h(x)x, (A.90), and |h(x)| ≤ log K ≤ 2 L, √ ∥µx′ − µx ∥1 ≤ 5 L ε + |h(x′ ) − h(x)| + |h(x)|∥x′ − x∥1 (A.91) √ ≤ 14 L ε. (A.92) This proves (A.78). Similarly, | Varx′ (log x′ ) − Varx (log x)| ≤ 11L ε + |h(x′ ) − h(x)| |h(x′ )| + |h(x)| ≤ 31L ε,

(A.93) (A.94)

CONSTANT REGRET IN GENERAL GAMES

which proves (A.79). For (A.80), note that √ √ √ √ Γx = Diag( x) I − x( x)⊤ Diag( x). Hence

√ √ √ √ √ Γx′ − Γx = Diag( x′ − x) I − x′ ( x′ )⊤ Diag( x′ ) √ √ √ √ √ √ + Diag( x) x( x)⊤ − x′ ( x′ )⊤ Diag( x′ ) √ √ √ √ √ + Diag( x) I − x( x)⊤ Diag( x′ − x).

(A.95) (A.96) (A.97) (A.98)

For vectors c, d and a matrix A, ∥Diag(c)A Diag(d)∥∞→1 ≤ ∥c∥2 ∥A∥2→2 ∥d∥2 . √

Since ∥ x∥2 =

√

x′

(A.99)

= 1, the first and third terms are at most ε. Moreover, 2

√ √ ⊤ √ ′ √ ′ ⊤ 2 x( x) − x ( x )

√ E2 x, x′ 2→2 D√ √ E ≤2 1− x, x′ =1−

√ =

D√

x′ −

√

= ε2 .

(A.100) (A.101) (A.102)

Thus the middle term is also at most ε, proving (A.80). Next, by (A.41) and L ≥ 4, √ 1 1√ ∥νλ,x ∥1 ≤ 1 + ∥µx ∥1 ≤ 1 + L − 2 ≤ L, (A.103) 2 2 which proves (A.81). the √ Finally, subtracting √ √ two√expressions in (A.44) and using (A.90), (A.78), and |(1 + λ′ )−1 − (1 + λ)−1 | ≤ | λ′ − λ| gives √ 1√ √ ′ √ L | λ − λ| (A.104) ∥νλ′ ,x′ − νλ,x ∥1 ≤ 2ε + 7 L ε + 2 √ 1√ √ ′ √ ≤ 8 Lε + L | λ − λ|, (A.105) 2 √ where L ≥ 2. This proves (A.82). ■ Lemma A.7 (Jacobian stability). Let y, y ′ ∈ RK . If ∥y ′ − y∥∞ ≤ M ≤ 1, then 2

∥J (y ′ ) − J (y)∥∞→1 ≤ 2000eM/4 Dψ (Z(y ′ ), Z(y)). (A.106) √ √ Proof. Write Z(y) = λx, Z(y ′ ) = λ′ x′ , and ε = x′ − x . Holding λ fixed, (A.77) and 2

(A.79) give |D(λ, x′ ) − D(λ, x)| ≤

1 √ (5 L + 31L)ε. 4

(A.107)

′

Using (A.43) at both x and x therefore gives |D(λ, x′ )−1 − D(λ, x)−1 | ≤ Indeed,

√

L ≤ L/2 and (A.43) give

35 ε. L

√ 5 L + 31L 35 < . 2 (L + 1) L

(A.108)

(A.109)

For fixed x, the function s 7→ D(s2 , x) satisfies d 9Ls Varx (log x) D(s2 , x) = + . ds 4(1 + s)2 4(1 − s2 )5/2

(A.110)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

Together with (A.43) and Varx (log x) ≤ L, for 0 < s < 1, d 9 p 1 (1 − s2 )3 (A.111) D(s2 , x)−1 ≤ s 1 − s2 + ds L L (1 + s)2 11 6 ≤ < . (A.112) 2L L √ Here s 1 − s2 ≤ 1/2. The mean value theorem therefore gives √ 6 √ |D(λ′ , x)−1 − D(λ, x)−1 | ≤ | λ′ − λ|. (A.113) L Set now ⊤ µx νλ,x . (A.114) B(λ, x) = Γx + 2D(λ, x) By (A.108)–(A.113), √ 6 √ 35 ε + | λ′ − λ|. (A.115) |D(λ′ , x′ )−1 − D(λ, x)−1 | ≤ L L Using this bound together with (A.80), (A.78), (A.81), (A.82), and 2D ≥ L + 1, we obtain √ √ √ √ ′− ∥B(λ′ , x′ ) − B(λ, x)∥∞→1 ≤ 3ε + 14ε + (8ε + 12 | λ′ − λ|) + ( 35 λ λ|) ε + 3| 2 (A.116) √ √ ≤ 43ε + 4| λ′ − λ|. (A.117) Moreover, by (A.41), (A.81), and (A.43), ∥µx ∥1 ∥νλ,x ∥1 L ≤ < 1. 2D(λ, x) L+1

∥Γx ∥∞→1 ≤ 1, Thus ∥B(λ, x)∥∞→1 ≤ 2. Since √ 1+

λ′ √

√ λ′

−

λ √

√ √ ≤ | λ′ − λ|,

(A.118)

(A.119)

(A.56) yields

√ √ √ ∥J (y ′ ) − J (y)∥∞→1 ≤ 43 λε + 6| λ′ − λ|. √ Hence, by Cauchy–Schwarz, (A.2), and 0 < λ ≤ 1, √ √ 2 ∥J (y ′ ) − J (y)∥∞→1 ≤ (432 + 62 )(λε2 + | λ′ − λ|2 ) " √ √ # | λ′ − λ|2 ′ √ < 1900 λDKL (x ∥x) + . λ

Now apply (A.68); enlarging 1900 to 2000 proves (A.106).

(A.120)

(A.121) (A.122) ■

Lemma A.8 (Taylor remainder bound). Let y, v ∈ RK . If ∥v∥∞ ≤ M ≤ 1, then 2

∥Q(y + v) − Q(y) − J (y)v∥1 ≤ 2000eM/4 ∥v∥2∞ Dψ (Z(y + v), Z(y)).

(A.123)

Proof. By integration, Z 1 Q(y + v) − Q(y) − J (y)v =

[J (y + θv) − J (y)]v dθ.

(A.124)

Also d Dψ (Z(y + θv), Z(y)) = ⟨θv, DZ(y + θv)[v]⟩ ≥ 0, dθ

(A.125)

CONSTANT REGRET IN GENERAL GAMES

because DZ = (D2 ψ)−1 is positive definite by (A.32). Hence the Bregman divergence along the segment is at most its value at θ = 1. Apply (A.106) inside the integral and then Cauchy–Schwarz to obtain (A.123). ■ Appendix B. Higher-order predictor and one-step expansions This section proves the predictor bounds used in Appendix C: first the discounted-difference bounds, then one payoff difference and one mirror-map difference. B.1. Discounted finite differences. For the analysis, extend gi,t = mi,t = ei,t = 0 to every t ≤ 0 and recall δ = N/(N + 1). For a sequence w = (wt )t∈Z , define (∆w)t = wt − wt−1 ,

(σw)t =

∞ X

δ k wt−k .

(B.1)

k=0

The sum defining σw converges absolutely whenever w is bounded. For the zero-prehistory sequences (that is, sequences whose nonpositive index terms vanish) used below, it is actually finite at every fixed time, so it is well defined without any boundedness assumption. Then, directly from the geometric sum, (σw)t − δ(σw)t−1 = wt .

(B.2)

Conversely, if wt = 0 for t ≤ 0, the sum below is finite at every fixed t and telescopes: ∞ X

δ k (wt−k − δwt−k−1 ) = wt .

(B.3)

k=0

Thus, on the space of sequences with zero prehistory, σ and the map w 7→ (wt − δwt−1 )t are inverse. The same conclusion holds for bounded sequences by absolute convergence. Moreover, σ∆ = ∆σ, (B.4) P because both sides at time t are equal to k≥0 δ k (wt−k − wt−k−1 ). We now begin with the central identity that justifies the predictor’s definition. Lemma B.1 (Predictor identity). For every player i, ei = σ N +1 ∆N +1 gi .

(B.5)

Proof. For t ≥ 1, Algorithm 1 and (24) give N +1 N +1 X X k N +1 k N +1 ei,t = (−1) gi,t−k − (−1) δ k ei,t−k . k k k=0

(B.6)

k=1

For t ≤ 0 both sides are zero. Equivalently, N +1 X k N +1 (−1) δ k ei,t−k = ∆N +1 gi,t , k

∀t ∈ Z.

(B.7)

k=0

The left-hand side of (B.7) is obtained by applying w 7→ (wt − δwt−1 )t successively N + 1 times to ei . Applying its inverse σ successively N + 1 times to (B.7) gives (B.5). ■ For 0 ≤ p ≤ N + 1, define κp = σ N +1 ∆N +1−p = σ p (σ∆)N +1−p ,

(B.8)

κp = κp+1 ∆.

(B.9)

then, for 0 ≤ p ≤ N

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

The next lemma collects important sequence bounds used in what will follow. Fix r ∈ {1, ∞} and, for a sequence wt ∈ RK , write !1/2 X 2 ∥w∥ℓ2 = ∥wt ∥r . (B.10) t∈Z

In particular, for scalar sequences, this is the usual ℓ2 norm. Lemma B.2 (Higher-order differences sequence bounds). For either r = 1 or r = ∞, every 1 ≤ p ≤ N + 1, and every sequence wt ∈ RK with ∥w∥ℓ2 < ∞, ∥κp w∥ℓ2 ≤ 4(N + 1)p+1 ∥w∥ℓ2 .

(B.11)

Proof. We first establish the required bounds for scalar sequences. For every finitely supported scalar sequence a, X 2 (at − δat−1 )2 − (1 + δ)2 ∥∆a∥ℓ2 (B.12) 4 t

= 2(1 − δ)2

X (a2t + at at−1 ) ≥ 0,

(B.13)

where the last inequality follows by summing 2at at−1 ≥ −a2t − a2t−1 over t. Moreover, Minkowski’s inequality gives X ∥σw∥ℓ2 ≤ δ k ∥(wt−k )t ∥ℓ2 = (N + 1)∥w∥ℓ2 , (B.14) k≥0

so (B.13) extends by density to every scalar ℓ2 sequence. Since (σw)t − δ(σw)t−1 = wt ,

∆σw = σ∆w,

(B.15)

applying (B.13) to σw yields ∥(σ∆)w∥ℓ2 ≤

2 ∥w∥ℓ2 . 1+δ

(B.16)

Set now

−1 1 2 = 1− . β= 1+δ 2(N + 1) then, iterating (B.16), for 0 ≤ q ≤ N + 1 we obtain

(B.17)

∥(σ∆)q w∥ℓ2 ≤ β q ∥w∥ℓ2 .

(B.18)

Furthermore, q

β ≤

1 1− 2(N + 1)

−(N +1)

≤ exp

N +1 2N + 1

≤ e2/3 < 2,

(B.19)

where we used − log(1 − u) ≤ u/(1 − u). Consequently, for 0 ≤ q ≤ N + 1, ∥(σ∆)q w∥ℓ2 ≤ 2∥w∥ℓ2 .

(B.20)

We next bound the scalar coefficients of (σ∆)q . Directly from the definition of σ, X ((σ∆)v)t = bk vt−k ,

(B.21)

k≥0

where b0 = 1,

bk = −(1 − δ)δ k−1 ,

k ≥ 1.

(B.22)

CONSTANT REGRET IN GENERAL GAMES (0)

(0)

Extend bk by 0 for k < 0. Define a0 = 1 and ak = 0 for k ̸= 0, and inductively set (q+1)

k X

(q)

k ≥ 0,

bℓ ak−ℓ ,

(B.23)

ℓ=0

P (q) where we also extend ak by 0 for k < 0. Since k≥0 |bk | = 2, induction shows that a(q) is absolutely summable and that X (q) ((σ∆)q v)t = ak vt−k . (B.24) k≥0

Applying the preceding scalar ℓ2 estimate to a sequence supported at time 0 gives  1/2 X (q)  |ak |2  ≤ βq .

(B.25)

k≥0

Set now 1/2

 sq = 

(q)

k 2 |ak |2 

(B.26)

k≥0

We shall bound sq by induction, where the same argument also proves that it is finite. Indeed, multiplying (B.23) by k and writing k = (k − ℓ) + ℓ gives (q+1)

kak

k X

(q)

bℓ (k − ℓ)ak−ℓ +

ℓ=0

k X

(q)

ℓbℓ ak−ℓ ,

(B.27)

ℓ=0

and, by (B.16) for the first sum, and by Minkowski’s inequality for the second, 1/2   X (q) X sq+1 ≤ βsq +  ℓ|bℓ |  |a |2  k

(B.28)

k≥0

ℓ≥0

≤ βsq + (N + 1)β q ,

(B.29)

because X ℓ≥0

ℓ|bℓ | = (1 − δ)

ℓδ ℓ−1 =

ℓ≥1

1 = N + 1, 1−δ

(B.30)

hence, since s0 = 0, induction yields, for 1 ≤ q ≤ N + 1, sq ≤ q(N + 1)β q−1 < 2q(N + 1). Combining (B.25), (B.31), and β q < 2, we obtain X (q) X (q) |ak |2 < 4, k 2 |ak |2 < 4q 2 (N + 1)2 . k≥0

(B.31)

(B.32)

k≥0

For 1 ≤ q ≤ N + 1, Cauchy–Schwarz gives  2   X (q) X 1   |ak | ≤  2 1 + (k/[q(N + 1)]) k≥0 k≥0   2 X (q) k . × |ak |2 1 + 2 q (N + 1)2 k≥0

(B.33)

(B.34)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

The first factor satisfies X k≥0

1 + (k/[q(N + 1)])

2 ≤1+

=1+

Z ∞

1 + (x/[q(N + 1)])

πq(N + 1) ≤ 2(N + 1)2 , 2

(B.35) (B.36)

where we used π < 7/2, q ≤ N + 1, and N + 1 ≥ 2, and the second factor is smaller than 8, hence for 1 ≤ q ≤ N + 1, X (q) |ak | < 4(N + 1). (B.37) k≥0

For q = 0, the same bound follows immediately from the definition of a(0) . Let now wt ∈ RK . Minkowski’s inequality and (B.37) give X (q) |ak |∥(wt−k )t ∥ℓ2 (B.38) ∥(σ∆)q w∥ℓ2 ≤ k≥0

≤ 4(N + 1)∥w∥ℓ2 .

(B.39)

Repeated application of the corresponding bound for σ also gives ∥σ p w∥ℓ2 ≤ (N + 1)p ∥w∥ℓ2 .

(B.40)

κp = σ p (σ∆)N +1−p ,

(B.41)

∥κp w∥ℓ2 ≤ 4(N + 1)p+1 ∥w∥ℓ2 ,

(B.42)

Since

we conclude that

which proves (B.11). If w is supported at time t0 with value v, then (N +1−p)

((σ∆)N +1−p w)t = at−t0

(B.43)

(σ∆)N +1−p w ℓ2 ≤ 2∥v∥r .

(B.44)

Therefore, (B.25) and β N +1−p < 2 imply

Combining this with the bound for σ p gives ∥κp w∥ℓ2 ≤ 2(N + 1)p ∥v∥r .

(B.45)

Finally, (B.37) with q = N + 1 gives sup ((σ∆)N +1 w)t r ≤ 4(N + 1) sup∥wt ∥r . t

(B.46)

■

Applying (B.5) and (B.46) to gi , and using (13), gives ∥ei,t ∥∞ ≤ 8(N + 1).

(B.47)

Since mi,t = gi,t − ei,t and N + 1 ≥ 2, ∥mi,t ∥∞ ≤ 9(N + 1).

(B.48)

CONSTANT REGRET IN GENERAL GAMES

B.2. Payoff differences. We call any strategy vector xk,t or xk,t−1 appearing as an argument of a multilinear payoff map a strategy term. Now, for t ≤ 0, set xi,t = Q(0) and xt = (x1,t , . . . , xN,t ) and for every t ∈ Z, define γi,t = ui ( · , x−i,t ) − ui (xt )1.

(B.49)

Since payoffs lie in [−1, 1], ∥γi,t ∥∞ ≤ 2, and, for t ≥ 1, γi,t = gi,t , whereas gi,t = 0 for t ≤ 0. Consequently, for t ∈ Z, ∆gi,t = 1{t=1} γi,0 + ∆γi,t .

(B.50) (B.51)

We shall also repeatedly use the following elementary product rule. If F is q-linear, then F (z1,t , . . . , zq,t ) − F (z1,t−1 , . . . , zq,t−1 ) =

q X

(B.52)

F (z1,t−1 , . . . , zk−1,t−1 , ∆zk,t , zk+1,t , . . . , zq,t ).

(B.53)

k=1

Lemma B.3 (One payoff difference). For every player i and every t ∈ Z, there are linear v u maps Cij,t (j ̸= i) and Cij,t (j ∈ N ) such that ∆γi,t =

v Cij,t ∆xj,t +

N X

u Cij,t ∆xj,t ,

(B.54)

j=1

j̸=i

with v Cij,t w ∞ ≤ ∥w∥1 ,

u Cij,t w ∞ ≤ ∥w∥1 .

(B.55)

Each coefficient contains at most N − 1 strategy terms, with each player label appearing at most once; consequently, each fixed label occurs at most twice in (B.54). Proof. Apply (B.53) to x−i 7→ ui ( · , x−i ) and x 7→ ui (x), and absorb the minus sign from u v (B.49) into Cij,t . More explicitly, Cij,t is obtained from x−i 7→ ui ( · , x−i ) by leaving player u j’s argument free and fixing every other argument at a strategy term; Cij,t is obtained v u analogously from x 7→ −ui (x)1, so that Cij,t w and Cij,t w are obtained by inserting w in that free argument. This gives (B.54) and shows that each coefficient contains at most N − 1 strategy terms, with each player label appearing at most once. A fixed j can occur once in each of the two sums in (B.54), hence at most twice overall. Finally, if |aβ | ≤ 1, then X β

aβ

q Y

zk,βk ≤

k=1

q Y

∥zk ∥1 .

(B.56)

k=1

Taking one zk = w and the others in XK proves (B.55).

■

B.3. Differences control. By (B.54), it remains to control ∆xi,t . For t ≥ 1, retain the notation yi,t−1/2 , zi,t−1/2 , zi,t , Pi,t , Gi,t introduced in Section 4. For t ≤ 0, set yi,t = mi,t = ei,t = yi,t−1/2 = 0,

zi,t = zi,t−1/2 = Z(0),

xi,t = Q(0),

Pi,t = Gi,t = 0. (B.57)

Set yi,t−1/2 = yi,t−1 + mi,t = yi,t − ei,t .

(B.58)

∆yi,t−1/2 = gi,t − ∆ei,t .

(B.59)

Then For t ≥ 1, set λi,t−1 = ⟨1, zi,t−1 ⟩,

Ji,t = ηJ (ηyi,t−1 ),

(B.60)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

and set Ji,t = ηJ (0) for t ≤ 0. The required bounds on ∆xi,t , ri,t , and ∆Ji,t are collected next. Lemma B.4 (Expansion terms bounds). Assume (26). Then, for every player i and every t ≥ 1, ∥Ji,t ∥∞→1 ≤ η, ∥Ji,t ∥∞→1 ≤ 2η

(B.61) p

λi,t−1 .

(B.62)

∆xi,t = Ji,t ∆yi,t−1/2 + ri,t ,

(B.63)

Moreover, if then, for every T ≥ 1, T X

∥ri,t ∥1 ≤ 300000(N + 1)2 η 3

(B.64)

t=1

t=1 T X

T X (Pi,t + Gi,t ),

∥Ji,t − Ji,t−1 ∥∞→1 ≤ 4100η 3

t=1

T X

(Pi,t + Gi,t ),

(B.65)

t=1

5η

∥∆xi,t ∥1 ≤

λi,t−1

(Pi,t + Gi,t−1 ).

(B.66)

Finally, if t′ ∈ Z and |t − t′ | ≤ N + 1, then 2

∥Ji,t′ ∥∞→1 Ji,t ∆yi,t−1/2 1 ≤ 90η 3 (Pi,t + Gi,t−1 ).

(B.67)

Proof. The bounds (B.61)–(B.62) follow from (A.45)–(A.46). Fix t ≥ 1. By (B.58), xi,t−1 = Q(η(yi,t−1 − ei,t−1 )) ,

xi,t = Q(η(yi,t−1 + mi,t )) ,

(B.68)

and ∆yi,t−1/2 = mi,t + ei,t−1 . Hence ri,t = xi,t − Q(ηyi,t−1 ) − Ji,t mi,t − xi,t−1 − Q(ηyi,t−1 ) + Ji,t ei,t−1 .

(B.69)

By (B.47)–(B.48) and (26), η∥mi,t ∥∞ <

1 , 16

η∥ei,t−1 ∥∞ <

1 . 16

(B.70)

Apply (A.123) to the two brackets. Since ea ≤ (1 − a)−1 for 0 ≤ a < 1, 2000e1/64 < 2050. Using Dψ (zi,t−1/2 , zi,t−1 ) = ηPi,t , Dψ (zi,t−3/2 , zi,t−1 ) = ηGi,t−1 , (B.71) we obtain

p 2 p 2 ∥ri,t ∥1 ≤ 2050(N + 1)2 η 3 9 Pi,t + 8 Gi,t−1 . 2

(B.72)

Since (9a + 8b) ≤ 145(a + b ), 2

∥ri,t ∥1 < 300000(N + 1)2 η 3 (Pi,t + Gi,t−1 ).

(B.73)

Summing in t proves (B.64). For (B.65), insert ηyi,t−3/2 between ηyi,t−1 and ηyi,t−2 . The two score differences have ℓ∞ norm smaller than 1/16. Thus 2

∥Ji,t − Ji,t−1 ∥∞→1 ≤ 2η 2 J (ηyi,t−1 ) − J (ηyi,t−3/2 ) ∞→1 + 2η

J (ηyi,t−3/2 ) − J (ηyi,t−2 )

≤ 4000e1/64 η 3 (Pi,t−1 + Gi,t−1 ) 3

< 4100η (Pi,t−1 + Gi,t−1 ),

2 ∞→1

(B.74) (B.75) (B.76) (B.77)

CONSTANT REGRET IN GENERAL GAMES

where (A.106) was applied with the orientation matching the definitions of Pi,t−1 and Gi,t−1 . Summing in t and shifting the indices gives (B.65). For (B.66), insert Q(ηyi,t−1 ) between xi,t and xi,t−1 . By (A.69), with ηyi,t−1 as the base score in both applications, 2

∥xi,t − Q(ηyi,t−1 )∥1 ≤

2e1/64 η Pi,t , λi,t−1

∥xi,t−1 − Q(ηyi,t−1 )∥1 ≤

2e1/64 η Gi,t−1 . λi,t−1

(B.78)

Therefore 4e1/64 η 5η (Pi,t + Gi,t−1 ) < (Pi,t + Gi,t−1 ). λi,t−1 λi,t−1 It remains to prove (B.67). If |t − t′ | ≤ N + 1, then 2

∥∆xi,t ∥1 ≤

1 . 120 Since Ji,t′ = ηJ (ηyi,t′ −1 ) also for t′ ≤ 0, (A.66) and (A.46) give η∥yi,t′ −1 − yi,t−1 ∥∞ ≤ 2η(N + 1) ≤

(B.79)

(B.80)

∥Ji,t′ ∥∞→1 ≤ 4e1/480 η 2 λi,t−1 .

(B.81)

Also, by (B.63), 2

Ji,t ∆yi,t−1/2 1 ≤ 2∥∆xi,t ∥1 + 2∥ri,t ∥1 .

(B.82)

Using (B.66) and (B.73), 2

∥Ji,t′ ∥∞→1 Ji,t ∆yi,t−1/2 1

(B.83)

≤ 4e1/480 η 3 10 + 600000(N + 1)2 η 2 (Pi,t + Gi,t−1 ) 3

< 90η (Pi,t + Gi,t−1 ),

(B.84) (B.85)

where 600000(N + 1)2 η 2 < 11 and e1/480 < 480/479. This proves (B.67).

■

For what follows, set ri,t = 0 for t ≤ 0. By (B.57), for t ≤ 0, ∆xi,t = ∆yi,t−1/2 = 0,

(B.86)

so (B.63) holds for every t ∈ Z. Appendix C. Proof of the main theorem We combine Appendices A and B: first the RVU inequality, then the prediction error bound, and finally Theorem 1. C.1. The RVU inequality. Recall from Section 4 the optimistic score and lifted iterates yi,t−1/2 = yi,t−1 + mi,t ,

zi,t−1/2 = Z(ηyi,t−1/2 ),

zi,t = Z(ηyi,t ),

(C.1)

the Bregman variation terms Pi,t = Dψ/η (zi,t−1/2 , zi,t−1 ),

Gi,t = Dψ/η (zi,t−1/2 , zi,t ),

(C.2)

and the cumulative quantities P (T ) =

N X T X

Pi,t ,

G(T ) =

i=1 t=1

N X T X

Gi,t ,

E(T ) =

i=1 t=1

N X T X 2 ∥ei,t ∥∞ .

(C.3)

i=1 t=1

Finally, recall the range of the regularizer, Ω = max ψ(z) − min ψ(z). z∈K

We now prove the RVU inequality.

z∈K

(C.4)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

Proposition C.1 (RVU inequality). For every T , N X

[Regi (T )]+ ≤

i=1

NΩ η + E(T ) − P (T ), η 2

and

(C.5)

η E(T ). 2

(C.6)

zi,t−1/2 , 1, zi,t−1/2

(C.7)

zi,t−1/2 , gi,t = 0.

(C.8)

G(T ) ≤ Proof. Fix i. Since xi,t = (13) gives Therefore, because K = conv({0, e1 , . . . , eK }), max u∈K

T X

u − zi,t−1/2 , gi,t = max⟨u, yi,T ⟩

(C.9)

u∈K

t=1

= max{0, max yiα,T } = [Regi (T )]+ . α

(C.10)

Let

∗ ψ + ιK , (C.11) η where ιK is 0 on K and +∞ outside K, and ∗ denotes convex conjugation. By Lemma A.3, the maximizer is unique and smooth, so, for a generic score y, 1 Φ(y) = ⟨y, Z(ηy)⟩ − ψ(Z(ηy)). (C.12) η

Φ=

Differentiating in a direction q and using ∇ψ(Z(ηy)) = ηy from (A.38) gives DΦ(y)[q] = ⟨q, Z(ηy)⟩ + η⟨y, DZ(ηy)[q]⟩ − ⟨∇ψ(Z(ηy)), DZ(ηy)[q]⟩ = ⟨q, Z(ηy)⟩. (C.13) Hence ∇Φ(y) = Z(ηy).

(C.14)

If p, q ∈ R , then ηp = ∇ψ(Z(ηp)) and ηq = ∇ψ(Z(ηq)) by (A.38). Fenchel equality therefore gives DΦ (p, q) = Dψ/η (Z(ηq), Z(ηp)). (C.15) Indeed, substituting Φ(r) = ⟨r, Z(ηr)⟩ − ψ(Z(ηr))/η in the left side yields the right side. Consequently, Pi,t = DΦ (yi,t−1 , yi,t−1/2 ),

Gi,t = DΦ (yi,t , yi,t−1/2 ).

(C.16)

Subtracting these two identities and using yi,t − yi,t−1 = gi,t gives Gi,t − Pi,t = Φ(yi,t ) − Φ(yi,t−1 ) − zi,t−1/2 , gi,t .

(C.17)

Hence, for every u ∈ K, T X

gi,t , u − zi,t−1/2 = ⟨yi,T , u⟩ − Φ(yi,T ) + Φ(0) +

t=1

T X (Gi,t − Pi,t )

(C.18)

t=1

≤

T T X ψ(u) − minz∈K ψ(z) X + Gi,t − Pi,t , η t=1 t=1

(C.19)

CONSTANT REGRET IN GENERAL GAMES

where we used the Fenchel–Young inequality, that is, ⟨yi,T , u⟩ − Φ(yi,T ) ≤ ψ(u)/η and Φ(0) = − minK ψ/η. Maximizing in u and using (C.10) proves [Regi (T )]+ ≤

T T X Ω X + Gi,t − Pi,t . η t=1 t=1

(C.20)

It remains to bound Gi,t . Let z ′ , z ∈ K◦ . By the 1-strong convexity in (A.32), Dψ/η (z ′ , z) ≥

1 ′ 2 ∥z − z∥1 . 2η

(C.21)

For arbitrary p, q ∈ RK , the first-order conditions imply ⟨p − q, Z(ηp) − Z(ηq)⟩ = Dψ/η (Z(ηp), Z(ηq)) + Dψ/η (Z(ηq), Z(ηp)) 1 2 ≥ ∥Z(ηp) − Z(ηq)∥1 . η

(C.22) (C.23)

By Hölder’s inequality, 1 2 ∥Z(ηp) − Z(ηq)∥1 ≤ ∥p − q∥∞ ∥Z(ηp) − Z(ηq)∥1 . η

(C.24)

If Z(ηp) = Z(ηq), the desired bound is immediate; otherwise, canceling one factor of ∥Z(ηp) − Z(ηq)∥1 proves ∥Z(ηp) − Z(ηq)∥1 ≤ η∥p − q∥∞ . (C.25) By (C.14) and integration, Z 1 ⟨Z(η(q + θ(p − q))) − Z(ηq), p − q⟩ dθ

DΦ (p, q) =

(C.26)

Z 1 ≤ 0

ηθ∥p − q∥∞ dθ =

η 2 ∥p − q∥∞ , 2

(C.27)

where the inequality uses (C.25). Thus η 2 ∥p − q∥∞ . 2 Since Gi,t = DΦ (yi,t , yi,t−1/2 ) and yi,t − yi,t−1/2 = ei,t , DΦ (p, q) ≤

η 2 ∥ei,t ∥∞ . 2 Summing (C.20) and (C.29) over players and rounds gives (C.5) and (C.6). Gi,t ≤

(C.28)

(C.29) ■

By (C.5)–(C.6), it remains to control E(T ) in terms of P (T ) + G(T ). We combine the bounds of Appendix B below. C.2. Prediction error control. Fix T , and let all ℓ2 norms below be taken over t = 1, . . . , T , with the underlying vector norm clear from context. By the zero prehistory conventions above, every sequence to which we apply κp vanishes for t ≤ 0. Moreover, (κp w)t depends only on the values ws with s ≤ t, so values of the sequence after time T do not affect (κp w)t for 1 ≤ t ≤ T . Hence the bounds of Lemma B.2 apply directly on the finite horizon 1, . . . , T , and we obtain ∥κp w∥ℓ2 ≤ 4(N + 1)p+1 ∥w∥ℓ2 , p

∥κp w∥ℓ2 ≤ 2(N + 1) ∥v∥

if wt = 1{t=t0 } v.

(C.30) (C.31)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

Summing Lemma B.4 over players yields N X

∥rj ∥ℓ2 ≤ 300000(N + 1)2 η 3 (P (T ) + G(T )),

(C.32)

j=1 N X 2 ∥∆Jj ∥ℓ2 ≤ 4100η 3 (P (T ) + G(T )),

(C.33)

j=1 N X

∥∆ej ∥ℓ2 ≤ 4E(T ).

(C.34)

j=1 2

2 ∥Jj,t−ℓ ∥∞→1

Jj,t−u ∆y

The third bound uses ∥∆ej,t ∥∞ ≤ 2∥ej,t ∥∞ + 2∥ej,t−1 ∥∞ and ej,0 = 0. Also, for 0 ≤ ℓ, u ≤ N + 1, (B.67) gives T X

2 j,t−u− 12

t=1

≤ 90η 1

T X

(Pj,k + Gj,k ).

(C.35)

k=1

For t − u > 0, this is (B.67) at time t − u, since |u − ℓ| ≤ N + 1; for t − u ≤ 0 the summand is zero. We will also use the following Cauchy–Schwarz consequence. If ∥wν ∥ℓ2 ≤ c ujν , |I| ≤ n0 , and each label occurs at most n1 times, then  1/2 N X X √ u2j  . (C.36) wν ≤ c n0 n1  ν∈I

j=1

ℓ2

Next, in the expansion below, we call Jj,t−q , gk,t−q , and xℓ,t−q a Jacobian term, payoff term, and strategy term, respectively, with q denoting the corresponding time offset, and each term in the expansion is multilinear in these factors. Accordingly, if its Jacobian, payoff, and strategy terms are replaced by arbitrary maps Ba : RK → RK and vectors va , za , we write the resulting expression as Mt [(Ba ); (va ); (za )]. The terms generated by the expansion satisfy Y Y Y ∥Mt [(Ba ); (va ); (za )]∥∞ ≤ ∥Ba ∥∞→1 ∥va ∥∞ ∥za ∥1 , (C.37) a

and the proof below shows that this bound is preserved whenever the expansion continues. The way the expansion continues becomes then simple. Indeed, whenever a strategy or payoff difference, after being expanded, reveals ∆xj , (B.63) and (B.59) give, suppressing time offsets, ∆xj = rj + Jj gj − Jj ∆ej . (C.38) The first and last terms are controlled directly, while Jj gj can continue only if the player label j is new; and if j has already appeared among the Jacobian terms, the resulting repeated player term is controlled by (C.35), so every continuing term must introduce a fresh player label. The next lemma makes this recursive structure precise. Lemma C.1 (One-step expansion). Fix 1 ≤ p ≤ N , and let M be a term containing p Jacobian terms with distinct player labels j1 , . . . , jp , together with s payoff terms and h strategy terms, where 1 ≤ s ≤ p and 0 ≤ h ≤ N p. Assume that all time offsets lie in {0, . . . , p}, that each player occurs at most p times among the strategy terms, and that M satisfies (C.37). Then X ∆M = RM + M ′, (C.39) M ′ ∈C(M )

where RM collects the controlled terms and satisfies ∥κp+1 RM ∥ℓ2 ≤ 2p(N + 1)p+1 (2η)p

(C.40)

CONSTANT REGRET IN GENERAL GAMES

p √ + 815p N (N + 1)p+2 (2η)p−1 η 3/2 P (T ) + G(T ) p √ + 12p N (N + 1)p+2 (2η)p+1 E(T ).

(C.41) (C.42)

Moreover, every M ′ ∈ C(M ) satisfies the same conditions as M with p replaced by p + 1, and |C(M )| ≤ 3p(N − p).

(C.43)

In particular, C(M ) = ∅ when p = N . Proof. Apply the discrete product rule (B.53) to M , so that exactly one Jacobian, payoff, or strategy term is differenced, while all the other terms remain present, possibly with their time offsets increased by one. We now need to determine which terms may continue. First, a differenced Jacobian is controlled directly; next if a payoff term is differenced, (B.51) separates an initialization term and Lemma B.3 expresses the remaining part as a sum of strategy variations ∆xj ; and differencing a strategy term produces such a variation directly. Since each of the s payoff terms produces at most 2N − 1 strategy variations, the total number of revealed variations is at most (2N − 1)s + h ≤ 3N p.

(C.44)

More importantly, for any fixed player j, Lemma B.3 can produce the label j at most twice from each payoff term, while by assumption j occurs at most p times among the strategy terms. Hence each label is revealed at most 2s + p ≤ 3p

(C.45)

times. For every revealed ∆xj , use (C.38): ∆xj = rj + Jj ∆yj,·−1/2 = rj + Jj gj − Jj ∆ej .

(C.46)

We know the remainder rj is already controlled. If j ∈ {j1 , . . . , jp }, an existing Jacobian with the same player label is already present, so the term Jj ∆yj,·−1/2 is controlled by (C.35). If instead j ∈ / {j1 , . . . , jp }, then −Jj ∆ej is controlled and Jj gj is the only term that may continue. Thus every continuing term introduces one fresh Jacobian label. There are N − p possible fresh labels, and by (C.45) each can arise at most 3p times. Therefore |C(M )| ≤ 3p(N − p),

(C.47)

which proves (C.43). In particular, no continuation is possible when p = N . We next check that a continuing term satisfies the same structural conditions at the next order. If ∆xj came from a strategy term, the continuing replacement is simply Jj gj , and ∥Jj gj ∥1 ≤ ∥Jj ∥∞→1 ∥gj ∥∞ .

(C.48)

If it came from a payoff term, Lemma B.3 produces an expression of the form Ckj Jj gj , and (B.55) gives Y ∥Ckj Jj gj ∥∞ ≤ ∥Jj ∥∞→1 ∥gj ∥∞ ∥za ∥1 . (C.49) a

Hence (C.37) is preserved in either case. Differencing a payoff term inserts at most N − 1 strategy terms, with each player appearing at most once, whereas differencing a strategy term inserts none. Consequently, a continuing term has at most N (p + 1) strategy terms, each player occurs at most p + 1 times among them, it has p + 1 distinct Jacobian labels and between 1 and p + 1 payoff terms, and every time offset lies in {0, . . . , p + 1}. It remains then to bound the controlled part. Write y J 0 r e RM = RM + RM + RM + RM + RM ,

(C.50)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

where the five pieces contain, respectively, a Jacobian variation, an initialization term, a remainder rj , a term −Jj ∆ej , and a repeated player term Jj ∆yj,·−1/2 . For brevity, set P = P (T ),

G = G(T ),

E = E(T ).

(C.51)

Since ∥xi,t ∥1 = 1, ∥Ji,t ∥∞→1 ≤ η by (B.61), and ∥gi,t ∥∞ ≤ 2 by (13), the product of the bounds for the p Jacobian terms, the s ≤ p payoff terms, and all strategy terms is at most η p 2s ≤ (2η)p .

(C.52)

J We use this bound after removing whichever factor is being controlled. For RM , one of the p Jacobian factors is replaced by ∆Jj . The remaining factors contribute at most 2(2η)p−1 .

Hence (C.30), Cauchy–Schwarz over the p distinct Jacobian labels, and (C.33) give  1/2 N X √ 2 J κp+1 RM ≤ 4(N + 1)p+2 2(2η)p−1 p  ∥∆Jj ∥ℓ2  (C.53) ℓ 2

j=1

√ √ √ ≤ 8 4100 p (N + 1)p+2 (2η)p−1 η 3/2 P + G √ √ ≤ 520 p (N + 1)p+2 (2η)p−1 η 3/2 P + G,

(C.54) (C.55)

√

0 where 8 4100 < 520. For RM , each initialization term is supported at one time and has norm at most 2 by (B.50). There are at most s ≤ p such terms, so (C.31) gives 0 κp+1 RM ≤ 2p(N + 1)p+1 (2η)p . ℓ2

(C.56)

r For RM , there are at most 3N p revealed variations, while each label occurs at most 3p times by (C.45). After singling out rj , the remaining factors contribute at most (2η)p . Applying (C.36) with n0 = 3N p, n1 = 3p, (C.57) and then (C.32) and (C.30), we obtain 1/2  N X p 2 r (C.58) ∥κp+1 RM ∥ℓ2 ≤ 4(N + 1)p+2 (2η)p (3N p)(3p)  ∥rj ∥ℓ2  j=1

√ √ √ ≤ 12 300000 p N (N + 1)p+3 (2η)p η 3/2 P + G √ √ ≤ 6600p N (N + 1)p+3 (2η)p η 3/2 P + G,

(C.59)

(C.60) √ e where 12 300000 < 6600. For RM , the revealed term is −Jj ∆ej . After singling out ∆ej , there are p + 1 Jacobian factors and at most p payoff factors, so the remaining product is at most 1 η p+1 2p = (2η)p+1 . (C.61) 2 Using again n0 = 3N p, n1 = 3p, together with (C.36), (C.34), and (C.30), gives  1/2 N X p 1 2 e ∥κp+1 RM ∥ℓ2 ≤ 4(N + 1)p+2 (2η)p+1 (3N p)(3p)  ∥∆ej ∥ℓ2  (C.62) 2 j=1 √ √ ≤ 12p N (N + 1)p+2 (2η)p+1 E. (C.63) y Finally, RM contains the repeated player terms Jj ∆yj,·−1/2 . We pair this factor with the existing Jacobian carrying the same player label and apply (C.35), and the remaining factors contribute at most 2(2η)p−1 . Thus (C.36), (C.35), and (C.30) give p √ √ y ∥κp+1 RM ∥ℓ2 ≤ 4(N + 1)p+2 2(2η)p−1 (3N p)(3p) 90 η 3/2 P + G (C.64)

CONSTANT REGRET IN GENERAL GAMES

√ √ ≤ 240p N (N + 1)p+2 (2η)p−1 η 3/2 P + G,

(C.65)

√

where 24 90 < 240. We now put the three P + G terms on the same scale. By (26), 2(N + 1)η ≤

1 , 120

(C.66)

r so the RM bound becomes

√ √ (C.67) 6600p N (N + 1)p+3 (2η)p η 3/2 P + G √ √ ≤ 55p N (N + 1)p+2 (2η)p−1 η 3/2 P + G. (C.68) √ √ Also, since 1 ≤ p ≤ N , p ≤ p N . Therefore the three coefficients of the common P + G factor are bounded by 520 + 55 + 240 = 815. (C.69) Adding the five pieces proves (C.42).

■

Proposition C.2 (Prediction error bound). If (26) holds, then, for every T ≥ 1, p p √ 3p E(T ) ≤ 5 N (N + 1) + 2000(N + 1)5 η 3/2 P (T ) + G(T ) + E(T ). (C.70) 10 Proof. We first iterate Lemma C.1. Every continuing term contains at least one payoff term and therefore vanishes for t ≤ 0. Let M satisfy the hypotheses of Lemma C.1 with p = 1, set F1 = {M }, and recursively define ] Fp+1 = C(M ′ ), (C.71) M ′ ∈Fp

so that Fp is the multiset of continuing terms containing p distinct Jacobian labels. Since κp = κp+1 ∆ by (B.9), iterating (C.39) and using C(M ′ ) = ∅ at p = N gives κ1 M =

N X X

κp+1 RM ′ .

(C.72)

p=1 M ′ ∈Fp

We next bound the size of the continuing families. By (C.43), |Fp+1 | ≤ 3p(N − p)|Fp |.

(C.73)

At the same time, passing from order p to p + 1 multiplies each of the weights appearing in (C.42) by 2(N + 1)η. Hence 3 2 N (N + 1)η (C.74) 2 1 ≤ , (C.75) 40 where the last inequality follows from (26). Starting from |F1 | = 1, induction therefore gives p−1 1 p+2 p−1 3 |Fp |(N + 1) (2η) ≤ (N + 1) , (C.76) 40 p−1 1 |Fp |(N + 1)p+1 (2η)p ≤ (N + 1)2 (2η) . (C.77) 40 6p(N − p)(N + 1)η ≤

Since X 1 p−1 40 2 11 = < , p 40 39 10 p≥1

(C.78)

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

summing (C.42) over all M ′ ∈ Fp and all p yields ∥κ1 M ∥ℓ2 ≤ 5(N + 1)2 η p √ + 900 N (N + 1)3 η 3/2 P (T ) + G(T ) p √ + 53 N (N + 1)3 η 2 E(T ). Indeed, the three numerical constants follow from 11 11 11 2·2· < 5, 815 · < 900, 12 · 4 · < 53. 10 10 10 We now apply this bound to the prediction error. Define bi,t = 1{t=1} γi,0 ,

Ari =

v Cij rj +

N X

u Cij rj ,

(C.79) (C.80) (C.81)

(C.82)

(C.83)

j=1

j̸=i

and Aei =

v Cij Jj ∆ej +

N X

u Cij Jj ∆ej ,

Agi =

j=1

j̸=i

v Cij Jj gj +

j̸=i

N X

u Cij Jj gj .

(C.84)

j=1

Then (B.9), (B.51), (B.54), (B.63), and (B.59) give ei = κ1 bi + κ1 (Ari − Aei + Agi ). We bound the four contributions in (C.85). First, (C.31) and (B.50) give !1/2 X √ 2 ≤ 4 N (N + 1). ∥κ1 bi ∥ℓ2

(C.85)

(C.86)

Next, each of Ari and Aei contains 2N − 1 terms, and by Lemma B.3 each fixed player label occurs at most twice. Thus (C.36) may be applied with n0 = 2N − 1,

n1 = 2.

Using (C.30) and (C.32), and then taking the ℓ2 norm over i, gives !1/2 X p p √ 2 ∥κ1 Ari ∥ℓ2 ≤ 4 300000 2N (2N − 1)(N + 1)3 η 3/2 P (T ) + G(T )

(C.87)

(C.88)

p p < 2200 2N (2N − 1)(N + 1)3 η 3/2 P (T ) + G(T ),

(C.89)

where 4 300000 < 2200. Similarly, using (B.61) and (C.34), !1/2 X p p e 2 ∥κ1 Ai ∥ℓ2 ≤ 4 · 2 2N (2N − 1)(N + 1)2 η E(T )

(C.90)

√

p p = 8 2N (2N − 1)(N + 1)2 η E(T ).

(C.91)

Finally, Agi is a sum of 2N − 1 terms satisfying the hypotheses of Lemma C.1 with p = 1. Applying (C.81) to each such term, summing them, and then taking the ℓ2 norm over i, gives the three contributions √ 5 N (2N − 1)(N + 1)2 η, (C.92) p 3 3/2 900N (2N − 1)(N + 1) η P (T ) + G(T ), (C.93) p 3 2 53N (2N − 1)(N + 1) η E(T ). (C.94)

CONSTANT REGRET IN GENERAL GAMES

It remains only to combine these bounds. For the initialization terms, (26) and 2N − 1 ≤ (N + 1)2 imply √ √ 4 N (N + 1) + 5 N (2N − 1)(N + 1)2 η (C.95) √ √ 1 N (N + 1) < 5 N (N + 1). (C.96) ≤ 4+ 12 p For the coefficient of P (T ) + G(T ), we use p 2N (2N − 1) ≤ 2N, 2N − 1 ≤ 2N. (C.97) Hence 2200

p 2N (2N − 1) + 900N (2N − 1)

(C.98)

≤ 4400N + 1800N 2

(C.99)

≤ 2000(N + 1) ,

(C.100)

because 2000(N + 1)2 − (1800N 2 + 4400N ) = 200(N 2 − 2N + 10) > 0.

(C.101)

3 3/2

After restoring the common factor (N + 1) η

5 3/2

, this gives p P (T ) + G(T ).

2000(N + 1) η p Finally, for the coefficient of E(T ), (26) gives p 4N 4 < , 8 2N (2N − 1)(N + 1)2 η ≤ 15(N + 1) 15 106N 2 53 1 53N (2N − 1)(N + 1)3 η 2 ≤ 2 ≤ < , 60 (N + 1)3 3600 60

(C.102)

(C.103) (C.104)

where we used N2 1 1 ≤ ≤ . 3 (N + 1) N +1 2

(C.105)

Since 4 1 17 3 + = < , (C.106) 15 60 60 10 p p 3 the total E(T ) contribution is at most 10 E(T ). Combining the three bounds proves (C.70). ■ C.3. Proof of the main theorem. We use the following bound on Ω. Lemma C.2 (Regularizer range). Ω = max ψ − min ψ ≤ K

13 L. 6

(C.107)

Proof. Both terms in (18) are nonpositive, so maxK ψ = 0. Since L − 3 log K =

1 (log K − 4)2 ≥ 0, 4

(C.108)

we have log K/L ≤ 1/3. Hence p √ −ψ(λx) log K 2 3 13 ≤ (λ + λ) + 3 λ(1 − λ) ≤ + = . L L 3 2 6 This proves (C.107).

(C.109) ■

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

Proof of Theorem 1. From (C.5), (C.6), and

i=1 [Regi (T )]+ ≥ 0,

NΩ + ηE(T ). (C.110) η √ √ √ Substituting this into (C.70) and using a + b ≤ a + b gives p p √ √ 3p E(T ) ≤ 5 N (N +1)+2000(N +1)5 η N Ω+2000(N +1)5 η 2 E(T )+ E(T ). (C.111) 10 By (C.107), L ≥ 4, and (N + 1)3 η ≤ 1/60, √ √ 5 (C.112) 5 N (N + 1) ≤ (N + 1)3 L, 8 r √ √ 100 13N L 2000(N + 1)5 η N Ω ≤ (N + 1)2 < 25(N + 1)3 L, (C.113) 3 6 5 . (C.114) 2000(N + 1)5 η 2 ≤ 18 p √ √ For the second inequality, N + 1 ≥ 2 N , so N /(N + 1) ≤ 1/2, and we used 13/6 < 3/2. Therefore p √ 26 p E(T ) < 26(N + 1)3 L + E(T ). (C.115) 45 Since 26 · 45/19 < 62, E(T ) < 622 (N + 1)6 L. (C.116) P (T ) + G(T ) ≤

Finally, (C.20), (C.29), and Pi,t ≥ 0 give [Regi (T )]+ ≤

Ω η + E(T ). η 2

Using (C.107), (C.116), and (N + 1)3 η ≤ 1/60, 13 5 L 49 L 3L + = < . [Regi (T )]+ < 6 9 η 18 η η This proves (27). Taking η = 1/(60(N + 1)3 ) gives (28), and (29) follows.

(C.117)

(C.118) ■

Appendix D. Adversarial robustness For the switching rule stated after Theorem 1, set 3 1 B= 4 + log K + log2 K . η 4

(D.1)

Fix any full information adversarial rule whose k-th strategy after a fresh start is qk and whose remaining regret satisfies, for every payoff sequence w1 , . . . , ws ∈ [−1, 1]K , max

α∈AK

s X

⟨α − qk , wk ⟩ ≤ H(s),

H(s) = o(s).

(D.2)

k=1

Standard examples of such rules include Hedge / exponential weights with well-chosen step sizes. Put Regi (0) = 0. Define τi = inf{t ≥ 1 : Regi (t) > B},

inf ∅ = ∞.

(D.3)

Run Algorithm 1 through round τi and, if τi < ∞, restart the adversarial rule from round τi + 1. The switching rule follows the bounded regret dynamics until the first bound violation and then makes a single permanent switch to the adversarially robust rule.

CONSTANT REGRET IN GENERAL GAMES

Proposition D.1 (Switching guarantee). If every player uses the above rule, then τi = ∞ for every player. Against arbitrary deviations of the other players, lim sup T →∞

Regi (T ) ≤ 0. T

(D.4)

Proof. By definition of τi , for 0 ≤ T < τi , Regi (T ) ≤ B. Moreover, one round can increase external regret by at most 2, because |giα,t | ≤ 2 for every action α. Hence, if τi < ∞, Regi (τi ) ≤ B + 2.

(D.5)

After round τi , the restarted adversarial rule is run on the payoff vectors vi,τi +1 , . . . , vi,T . Since ⟨α − xi,t , vi,t ⟩ = ui (α, x−i,t ) − ui (xt ), (D.6) its regret guarantee (D.2) gives, for T > τi , Regi (T ) ≤ Regi (τi ) + H(T − τi ) ≤ B + 2 + H(T − τi ),

(D.7)

so the switching rule satisfies the three bounds above for every realized play of the other players. Suppose now that every player uses the switching rule and that a switch occurs at some point for some player. Let τ = minj τj , then up to and including the round τ , no player has switched and so the realized play coincides with a trajectory on which all players use Algorithm 1. This means that the bound (27) implies Regj (τ ) ≤ B for every j, contradicting the fact that Regj (τ ) > B for any player with τj = τ , hence τi = ∞ for every player. Finally, against arbitrary opponents, if τi = ∞ then Regi (T ) ≤ B for all T , and if τi < ∞, then for T > τi , Regi (T ) B + 2 T − τi H(T − τi ) ≤ + . (D.8) T T T T − τi Both terms tend to zero because H(s) = o(s), proving (D.4). ■ References [1] O. Abbadi, R. Laraki, and P. Mertikopoulos. What preferences can—and cannot—predict in multi-agent online learning. In Proc. 43rd Internat. Conf. Machine Learning, 2026. [2] I. Anagnostides, G. Farina, C. Kroer, C.-W. Lee, H. Luo, and T. Sandholm. Uncoupled learning dynamics with O(log T ) swap regret in multiplayer games. In Advances in Neural Information Processing Systems 35, 2022. [3] I. Anagnostides, I. Panageas, G. Farina, and T. Sandholm. On last-iterate convergence beyond zero-sum games. In Proc. 39th Internat. Conf. Machine Learning, 2022. [4] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995. [5] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48–77, 2002. [6] D. Blackwell. Controlled random walks. In Proc. Internat. Congr. Math., volume 3, pages 336–338, 1954. [7] V. Boone and P. Mertikopoulos. The equivalence of dynamic and strategic stability under regularized learning in games. In Advances in Neural Information Processing Systems 36, pages 78533–78557, 2023. [8] S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Found. Trends Mach. Learn., 5(1):1–122, 2012. [9] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, Cambridge, 2006. [10] X. Chen and B. Peng. Hedging in games: Faster convergence of external and swap regrets. In Advances in Neural Information Processing Systems 33, pages 18990–18999, 2020. [11] T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, second edition, 2006.

O. ABBADI, R. LARAKI, AND P. MERTIKOPOULOS

[12] C. Daskalakis, M. Fishelson, and N. Golowich. Near-optimal no-regret learning in general games. In Advances in Neural Information Processing Systems 34, 2021. [13] G. Farina, I. Anagnostides, H. Luo, C.-W. Lee, C. Kroer, and T. Sandholm. Near-optimal no-regret learning dynamics for general convex games. In Advances in Neural Information Processing Systems 35, 2022. [14] D. P. Foster and R. Vohra. Regret in the on-line decision problem. Games Econom. Behav., 29(1–2): 7–35, 1999. [15] Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. System Sci., 55(1):119–139, 1997. [16] Y. Freund and R. E. Schapire. Adaptive game playing using multiplicative weights. Games Econom. Behav., 29(1–2):79–103, 1999. [17] J. Hannan. Approximation to Bayes risk in repeated play. In Contributions to the Theory of Games, Vol. III, pages 97–139. Princeton University Press, 1957. [18] S. Hart and A. Mas-Colell. Uncoupled dynamics do not lead to Nash equilibrium. American Economic Review, 93(5):1830–1836, 2003. [19] S. Hart and A. Mas-Colell. Stochastic uncoupled dynamics and Nash equilibrium. Games and Economic Behavior, 57:286–303, 2006. [20] Y.-G. Hsieh, K. Antonakopoulos, and P. Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. In Proc. 34th Conf. Learning Theory, 2021. [21] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Èkonom. i Mat. Metody, 12:747–756, 1976. [22] J. Kwon and P. Mertikopoulos. A continuous-time approach to online optimization. J. Dynam. Games, 4(2):125–148, 2017. [23] R. Laraki and P. Mertikopoulos. Higher order game dynamics. J. Econom. Theory, 148(6):2666–2695, 2013. [24] D. Legacci, P. Mertikopoulos, C. H. Papadimitriou, G. Piliouras, and B. S. R. Pradelski. No-regret learning in harmonic games: Extrapolation in the face of conflicting interests. In Advances in Neural Information Processing Systems 37, 2024. [25] M. Liu, G. Farina, and A. Ozdaglar. Constant Individual Regret in General Games. https://arxiv. org/abs/2608.31166, 2026. [26] P. Mertikopoulos and W. H. Sandholm. Learning in games via reinforcement and regularization. Math. Oper. Res., 41(4):1297–1324, 2016. [27] G. Piliouras, R. Sim, and S. Skoulakis. Beyond time-average convergence: Near-optimal uncoupled online learning via Clairvoyant Multiplicative Weights Update. In Advances in Neural Information Processing Systems 35, 2022. [28] L. D. Popov. A modification of the Arrow–Hurwicz method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5):845–848, 1980. [29] A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems 26, 2013. [30] A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In Proc. 26th Annual Conf. Learning Theory, pages 993–1019, 2013. [31] T. Roughgarden. Twenty Lectures on Algorithmic Game Theory. Cambridge University Press, Cambridge, 2016. [32] I. Sason and S. Verdú. f -divergence inequalities. IEEE Trans. Inform. Theory, 62(11):5973–6006, 2016. [33] L. J. Savage. The theory of statistical decision. Journal of the American Statistical Association, 46 (253):55–67, March 1951. [34] A. Soleymani, G. Piliouras, and G. Farina. Faster rates for no-regret learning in general games via cautious optimism. In Proc. 57th Annual ACM Symposium on Theory of Computing, 2025. [35] A. Soleymani, G. Piliouras, and G. Farina. Cautious optimism: A meta-algorithm for near-constant regret in general games, 2025. Extended abstract in Proc. 26th ACM Conf. Economics and Computation; arXiv:2506.05005. [36] V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems 28, 2015. [37] Y. Tao and W. Zheng. Optimal alternating regret for online learning and games. https://arxiv.org/ abs/2608.24731, 2026.

CONSTANT REGRET IN GENERAL GAMES

[38] T. Tsuchiya. Tight regret upper and lower bounds for Optimistic Hedge in two-player zero-sum games. In Proc. Internat. Conf. Artificial Intelligence and Statistics (AISTATS), 2026. [39] T. Tsuchiya. Sublogarithmic swap regret in multiplayer general-sum games via hybrid regularization. https://arxiv.org/abs/2608.04149, 2026. [40] A. Wald. Statistical Decision Functions. Wiley, 1950.

Constant regret in general games via higher-order optimism

Analyze & explore related research in Conceptio

Related documents