Multiplicative Optimism for Constant Regret in Games
arXiv:2609.21976v1 [cs.GT] 18 Sep 2026
Ashkan Soleymani MIT [email protected]
Georgios Piliouras Google Deepmind [email protected]
Abstract We introduce Multiplicatively Optimistic Regret Matching (MORM), an uncoupled learning rule for finite general-sum √ games. Under simultaneous full-information self-play, every player achieves external regret O( n log d) uniformly over all horizons, using only one-step optimism. The analysis combines a potential-based regret-matching argument with multiplicative stability and √ Hellinger control of strategy movement. A learning-rate safeguard additionally gives O( T log d) regret in the face of adversarial utilities.
1
Contents 1 Introduction
3
2 Multiplicatively Optimistic Regret Matching and Its Guarantees 2.1 Finite Games and Uncoupled Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The Uncoupled Learning Update of MORM . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Regret and Equilibrium Guarantees . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9 9 10 11
3 Proof Overview 12 3.1 The Classical Regret-matching Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 The Multiplicative Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 Measuring Strategy Movement with Hellinger Distance . . . . . . . . . . . . . . . . . 16 3.4 Choosing the Potential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.5 Bounding Regret in Self-play . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 Analysis of MORM 25 4.1 Potential Geometry and Multiplicative Stability . . . . . . . . . . . . . . . . . . . . . 26 4.2 One-round and Cumulative Potential Bounds . . . . . . . . . . . . . . . . . . . . . . 28 4.3 From Weighted Squares to Strategy Movement . . . . . . . . . . . . . . . . . . . . . 29 4.4 The Potential-level RVU Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.5 Prediction Error under Self-play in a Fixed Game . . . . . . . . . . . . . . . . . . . . 30 4.6 Uniform Movement and Regret under Self-play . . . . . . . . . . . . . . . . . . . . . 32 4.7 The Equilibrium Guarantee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5 Conclusion
34
A Related Work
39
B Potential Geometry and the Taylor Bound 41 B.1 Scalar Properties, Derivatives, and Curvature . . . . . . . . . . . . . . . . . . . . . . 42 B.2 Multiplicative Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 B.3 The Finite-step Taylor Estimate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 C Stability of the Normalized Response 47 C.1 Compensation for Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 C.2 Normalized Paths and Square-root Movement . . . . . . . . . . . . . . . . . . . . . . 49 C.3 Changing the Optimistic Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 C.4 Changing the Cumulative Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 C.5 Combining the Correction and Input Changes . . . . . . . . . . . . . . . . . . . . . . 53 D Hellinger Distance and Prediction Error 54 D.1 Hellinger Distance and Differences of Expectations . . . . . . . . . . . . . . . . . . . 54 D.2 Hellinger Distance between Product Distributions . . . . . . . . . . . . . . . . . . . . 55 E Adversarial Regret with a Learning-Rate Safeguard 56 E.1 The Safeguarded Update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 E.2 The Adversarial Regret Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 E.3 The Safeguard under Self-play . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 E.4 Completing the Main Guarantee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2
1
Introduction
A central question in game theory is whether meaningful strategic behavior can emerge from the independent decisions of learning agents whose interests need not align. Equilibrium provides a static description of such behavior, but it does not by itself specify how agents can reach it through repeated interaction. A learning rule must therefore serve two purposes. Each player should perform well according to its own objective, while the joint behavior of the players should satisfy useful equilibrium guarantees [Fudenberg and Levine, 1998, Shoham and Leyton-Brown, 2008]. We study how quickly these two goals can be achieved by decentralized learning. The classical benchmark for stable behavior is Nash equilibrium. At a Nash equilibrium, no player can improve its expected utility by unilaterally changing its strategy, and every finite game admits such an equilibrium [Nash, 1950]. For a learner, however, existence is only part of the problem. A player may not know which equilibrium to target, how the other players will adapt, or even their utility functions. This motivates uncoupled learning, in which a player’s update does not require access to the objectives of the other players [Hart and Mas-Colell, 2003]. Learning in this setting is inherently nonstationary. Even when the underlying game is fixed, each player’s utility vector changes as the other players change their strategies. These changes in turn affect the players’ future updates, so the environment faced by each learner is generated by the learning process itself. This feedback is also present in modern multiagent systems, including self-play and population-based learning [Silver et al., 2017, Lanctot et al., 2017]. Finite games with exact utility observations remove many statistical and computational complications of these applications and isolate this strategic source of nonstationarity. Regret minimization provides a natural individual performance criterion for such interactions. A player’s external regret compares its cumulative utility with that of the best fixed action in hindsight, evaluated against the same sequence of play by the other players. Sublinear regret means that no fixed action retains a positive per-round advantage in the long run. Importantly, classical no-regret algorithms provide this guarantee against arbitrary utility sequences, without assuming a model of the opponents or that they follow a prescribed learning rule [Hannan, 1957, Blackwell, 1956, Cesa-Bianchi and Lugosi, 2006]. The guarantee therefore belongs to each learner individually rather than only to a coordinated collection of players. In two-player zero-sum games, this individual guarantee also gives a direct route to equilibrium. If both players have sublinear external regret, the saddle-point gap of their average strategies is bounded by the sum of their average regrets, and the averages approach the set of Nash equilibria [Freund and Schapire, 1999]. This connection underlies a long line of learning-based methods for solving games, from fictitious play [Robinson, 1951] to counterfactual regret minimization and its resulting breakthroughs in large imperfect-information games [Zinkevich et al., 2007, Bowling et al., 2015, Brown and Sandholm, 2018, Moravčík et al., 2017, Brown and Sandholm, 2019b]. The situation is different in general-sum and multiplayer games. Computing a Nash equilibrium is PPAD-complete already in two-player general-sum games [Chen and Deng, 2006, Daskalakis et al., 2009], and multi-agent learning faces additional obstacles [Hart and Mas-Colell, 2003, Milionis et al., 2023]. More directly for our purposes, small external regret does not generally imply that the players’ average strategies form an approximate Nash equilibrium. The natural equilibrium consequence of external regret is instead a coarse correlated equilibrium. A coarse correlated equilibrium is a distribution over joint play in which no player can gain by committing in advance to a fixed action [Aumann, 1974, Moulin and Vial, 1978, Blum and Mansour, 2007]. This matches external regret exactly. A correlated equilibrium imposes a stronger condition. After observing its recommended action, a player should still not benefit from replacing that recommendation according to a fixed rule. Thus, CCE corresponds to fixed deviations chosen before 3
the recommendation is known, whereas CE allows deviations that depend on the recommendation. Stronger notions such as internal or swap regret lead to correlated-equilibrium guarantees [Hart and Mas-Colell, 2000, Blum and Mansour, 2007]. This connection is important because it turns an individual learning guarantee into a statement about the joint behavior of all players. Although players randomize independently within each round, averaging the product distributions generated over time need not produce another product distribution. This average can therefore satisfy a CCE guarantee even if the current strategy profile itself does not converge. The regret rate translates directly into the rate of√convergence to CCE. With at most d actions and full-information observations, Hedge guarantees O( T log d) regret against an arbitrary, potentially adversarial utility sequence [Freund and Averaging p Schapire, 1997, Cesa-Bianchi and Lugosi, 2006]. 2 T rounds therefore gives CCE error O( log d/T ), so reaching error ε requires O(log d/ε ) rounds. If cumulative regret can instead be bounded uniformly in T , the CCE error decreases as O(1/T ), and an ε-CCE can be reached in O(1/ε) rounds up to the dependence on the game size. Achieving this faster rate under self-play has been a longstanding goal in the study of no-regret learning in games. Why might such a faster rate be possible in self-play? Against an arbitrary sequence of utility vectors, a learner cannot expect one round to be informative about the next. In a fixed game, however, the utility sequence is generated by the players’ own strategy changes. An action’s expected utility changes only when the opponents change their mixed strategies. If those strategies move gradually, the utility sequence becomes predictable from recent observations. Gradual variation and optimistic online learning formalize this idea by making regret depend on how accurately the next utility vector can be predicted from the past [Chiang et al., 2012, Rakhlin and Sridharan, 2013a]. The simplest predictor is the preceding utility vector [Rakhlin and Sridharan, 2013b]. In self-play, however, predictability is endogenous. A player’s prediction is accurate when the other players move slowly, while their movement is itself determined by their learning rules. A fast self-play guarantee must therefore make these two effects reinforce each other. Small strategy movement keeps the utility vectors predictable, and the optimistic regret bound must in turn provide enough control on movement to keep the prediction errors small. Syrgkanis et al. [2015] made this feedback between predictability and movement precise through regret-bounded-by-variation-in-utilities (RVU) inequalities. For each player, the regret bound contains a positive term that depends on changes in the observed utility vectors and a negative term that depends on changes in the player’s own strategy. In a fixed game, these two quantities are linked because changes in one player’s utilities are caused by movement of the other players. After the playerwise inequalities are combined, the negative movement terms can therefore offset part of the positive variation terms. This yields individual regret of order T 1/4 in general games and establishes the basic mechanism behind fast learning in self-play. This was a major improvement over treating every player’s utility sequence as fully adversarial. Subsequent work pushed this frontier much further. Daskalakis et al. [2021] showed that the same one-step Optimistic Hedge algorithm achieves O(n log d log4 T ) individual regret in multiplayer general-sum games. The algorithm itself remains simple; the main advance is in the analysis, which shows that self-play generates considerable higher-order regularity in the utility and strategy sequences. By controlling higher-order finite differences of these sequences, they reduce the polynomial dependence on T to a polylogarithmic one. A different route was developed by Farina et al. [2022]. Their Log-Regularized Lifted Optimistic FTRL (LRL-OFTRL) operates in a lifted space in which the relevant regret quantity is nonnegative. This is useful because external regret itself can be negative, so strong bounds on the sum of the players’ regrets need not translate into comparable bounds for every player. The lifting avoids this cancellation, while logarithmic regularization provides the multiplicative stability needed to control 4
the learning trajectory. The resulting algorithm achieves O(nd log T ) individual regret and extends beyond finite normal-form games to general convex games. A later line of work addressed negative regret more directly. Soleymani et al. [2025b] introduced Cautious Optimism, which equips Optimistic Multiplicative Weights Update (OMWU) with an adaptive, non-monotone learning rate. When a player’s regret becomes too negative, the learning rate is reduced, this pacing mechanism limits how much negative regret can offset positive regret elsewhere in the analysis. This yields O(n log2 d log T ) individual regret, improving the dependence on d of LRL-OFTRL and the dependence on T of Optimistic Hedge. Soleymani et al. [2025a] extended this idea to a general √ framework for optimistic FTRL, allowing different regularizers across players while retaining an O( T ) adversarial regret guarantee. Together, these works show that fast individual regret requires not only predictable utilities, but also a mechanism that prevents large negative regret from undermining playerwise guarantees. Two recent works, developed independently and concurrently with ours, removed the remaining dependence on the horizon through high-order optimism [Liu et al., 2026, Abbadi et al., 2026]. Despite being developed independently, the two algorithms have a closely related structure. Both use optimistic FTRL on a lifted simplex, where an additional mass variable turns external regret into a nonnegative lifted regret. Their entropic regularizers also make this mass affect the sensitivity of the played strategy, effectively pacing the response even though the nominal learning rate is fixed. The main difference lies in how high-order optimism is implemented. ECHO-OFTRL uses a cascade of exponential moving averages to produce a geometrically stabilized nth-order prediction error, while HOOD uses a discounted (n + 1)st-order recurrence. These constructions yield horizon-independent individual regret of O(n21 log4 d) and O(n3 log2 d), respectively. The results establish that constant individual regret is possible in general finite games, but they rely on high-order predictors whose order grows with the number of players together with a complicated lifted response that adaptively moderates the sensitivity of the strategy. This leaves open whether the same horizon independence can be obtained from a substantially simpler form of optimism. The two horizon-independent results change the nature of the question. They show that constant individual regret is possible in general finite-game self-play, but they obtain it through high-order optimism, lifted dynamics, and fairly large polynomial dependence on the number of players. This suggests looking more closely at what is actually needed for fast no-regret learning. A particularly appealing target would retain the simplicity of the earlier optimistic algorithms. The prediction should use only the previous utility vector, rather than an order that grows with the number of players, and the update itself should remain easy to implement. At the same time, removing the dependence on T is only one part of the rate. The dependence on the size of the game also matters. Logarithmic dependence on the number of actions is natural from classical √ multiplicative-weights guarantees, while the n dependence already appearing in the RVU analysis of Syrgkanis et al. [2015] suggests that a linear dependence on the number of players should not be necessary. A separate issue is robustness to adversarial utility sequences. Ideally, protection against arbitrary utility sequences should not require replacing the self-play algorithm by a different procedure. The adaptive construction of Daskalakis et al. [2021], which modifies only the learning rate, suggests that such protection can be added with a minimal change to the underlying dynamics. More generally, one would like the resulting guarantee to have explicit, moderate constants and to come from a proof whose main mechanism is easy to identify. These considerations lead to the following question.
5
Method
Regret in Games Iteration Cost Adversarial Regret
Hedge
√
Optimism Order
O(d)
√ O( T log d)
0
√ O( n log d T 1/4 )
Reg. dep.
√ O( T log d)
1
O(n log5/6 d T 1/6 )†
O(d)
√ O( T log d)
1
O(n log d log4 T )
O(d)
√ O( T log d)
1
O(n log d)‡
O(d)
No guarantee
−
O(nd log T )
O(d log log T )
√ O( T log d)
1
O(n log2 d log T )
O(d log log T )
√ O( T log d)
1
O(n21 log4 d)
Unknown
No guarantee
n
[Abbadi et al., 2026]
O(n3 log2 d)
Unknown
√ O( T log d)
n+1
MORM
√ O( n log d)
O(d)
√ O( T log d)§
1
[Cesa-Bianchi and Lugosi, 2006] O( T log d)
Optimistic FTRL / OMD [Syrgkanis et al., 2015]
Optimistic Hedge [Chen and Peng, 2020]
Optimistic Hedge [Daskalakis et al., 2021]
Clairvoyant MWU [Piliouras et al., 2022]
LRL-OFTRL [Farina et al., 2022]
Cautious Optimism [Soleymani et al., 2025b,a]
ECHO-OFTRL [Liu et al., 2026]
HOOD
[This work]
Table 1: Comparison of no-regret learning algorithms in finite general-sum games. Here n is the number of players, T the number of rounds, and d the maximum number of actions. Universal constants are suppressed. Computational cost is the per-player cost of one learning update after the utility vector is available and does not include the cost of computing that vector. Optimism order 0 denotes a non-optimistic method, while order 1 uses one-step prediction. † applies only to two-player games. ‡ Clairvoyant MWU gives the stated bound only on a selected subsequence of iterates. § The adversarial guarantee for Multiplicatively Optimistic Regret Matching (MORM) uses the learning-rate safeguard in Section E, which leaves the self-play run unchanged. Can a simple one-step optimistic learner achieve horizon-independent individual regret, logarithmic dependence on the number of actions d, and sublinear dependence on the number of players n, while retaining adversarial protection through only a learning-rate safeguard? We answer this question affirmatively. We introduce Multiplicatively Optimistic Regret Matching (MORM), a deterministic uncoupled rule satisfying (T )
Regi
√ ≤ 96 n (2 + log d)
for every player i and every T ≥ 1.
The guarantee holds in any fixed n-player finite game with utilities in [0, 1] and at most d ≥ 2 actions per player, when players choose mixed strategies simultaneously and observe their own √ exact expected-utility vectors after play. The rule uses the fixed learning rate η = 1/(32 n) and predicts the current centered utility using only its value from the preceding round. It requires neither knowledge of the horizon nor high-order prediction. To our knowledge, this is the first uncoupled 6
√ algorithm in this setting with O( n log d) individual external regret. For adversarial protection, we use a safeguard that adapts only the learning rate to the observed dynamics. The response itself, the cumulative state, and the update rule remain unchanged. Against arbitrary, possibly adaptive, full-information utility sequences, the safeguarded rule satisfies p √ (T ) Regi ≤ 96 n (2 + log d) + 21 T (2 + log d). Under self-play, the safeguard never changes the learning rate, so the trajectory is exactly the same as for the fixed-rate algorithm. Theorems 4.10 and E.1, together with Proposition E.2, give the precise statements. Table 1 summarizes the progression of finite-game regret bounds. Compared with the O(n log2 d log T ) guarantee of Soleymani et al. [2025b], our bound removes the dependence on the horizon, improves the action dependence to log d, and reduces the player dependence from n to √ n. Compared with the recent horizon-independent results [Liu et al., 2026, Abbadi et al., 2026], it achieves substantially smaller dependence on both n and d while using only one-step optimism. √ The regret bound immediately gives an O( n log d/T ) CCE guarantee for the average distribution √ of play. Hence, O( n log d/ε) rounds suffice to reach CCE error at most ε. Our starting point is regret matching. Each action is tracked through its cumulative advantage over the mixed strategy actually played, and the response is formed from these cumulative advantages [Hart and Mas-Colell, 2001, Cesa-Bianchi and Lugosi, 2003]. A potential on this vector is chosen so that controlling the potential also controls the largest cumulative advantage, and hence the player’s external regret. This potential-based viewpoint gives us room to redesign both the response and the analysis. Classical regret matching uses the centering identity to cancel the first-order change of the potential. We keep this basic structure, but modify the response so that recent information enters the cancellation in a more useful way. The potential is then constructed to support the additional stability and curvature properties needed by that modified update. Optimism has previously been incorporated into regret matching through an additive prediction. Predictive regret matching forms its response from cumulative regret plus a prediction of the next regret vector before the positive-part operation and normalization [Farina et al., 2021]. Our first change is to place the prediction somewhere else. In MORM, the cumulative state remains untouched, and the preceding centered utility instead multiplies the positive weight assigned to each action. We refer to this as multiplicative optimism. The distinction is small at the level of the update, but it changes the potential calculation in an important way. The optimistic correction produces a negative weighted term whose weights are exactly the derivatives of the potential. Those same weights can then be used to pay for both the curvature of the potential and the movement of the strategy. This viewpoint also changes how the dependence on the number of players enters the proof. In the standard RVU arguments, including the ℓ1 path-length analysis used in Cautious Optimism, the change in a player’s utility is controlled by the sum of the opponents’ strategy movements. Squaring that sum introduces one factor of n, and summing the playerwise inequalities introduces another. The resulting closure requires a learning rate of order 1/n, which is reflected in the linear player dependence of the final regret bound [Farina et al., 2022, Soleymani et al., 2025b,a]. This dependence might therefore appear to be an unavoidable price of multiplayer interaction. The second idea is to measure strategy movement in square-root coordinates (Hellinger distance) instead. Squared Hellinger distance behaves particularly well for product distributions. The distance between two product distributions is controlled by the sum of the squared distances between their factors. Applying this comparison before separating the opponents removes the first player factor in the usual ℓ1 argument. After summing over players, only one factor of n remains. This is what √ √ makes a learning rate of order 1/ n possible and ultimately gives the n dependence in the regret 7
bound. The improvement comes from matching the geometry used to measure strategy movement with the product structure of the game. These two ideas impose concrete requirements on the potential. Its partial derivatives must stay positive and change in a controlled multiplicative way, because the response is obtained by normalizing those derivatives after the optimistic correction. Its curvature must be controlled by the same derivative weights that appear in the regret-matching cancellation. Finally, those weights must control square-root movement even when their total mass becomes very small. These requirements are stronger than ordinary smoothness, and they are the reason we do not start from a standard potential and then try to adapt the analysis around it. Instead, we construct the potential step by step from the properties needed by the proof. The scalar building block is linear on positive inputs, which preserves the regret certificate, and reciprocal on negative inputs, which keeps small positive weights multiplicatively stable. A power-norm aggregation then combines the coordinates while keeping the initial potential logarithmic in the number of actions. This is where the log d dependence enters. The same construction also supplies the weighted curvature and normalization properties needed for the Hellinger movement bound. The proof overview in Section 3 develops this construction in the same order in which the requirements arise. The resulting analysis remains potential based throughout. The one-round inequality has the familiar variation-versus-movement shape of an RVU bound, but the nonnegative quantity carried across rounds is the potential itself. We therefore do not need to make the players’ ordinary regrets nonnegative or lift the decision space for that purpose. Under self-play, Hellinger movement controls prediction error, while the potential controls that same movement. Combining the two closes the argument and bounds each player’s terminal potential, which then converts directly into regret. The potential also makes the adversarial safeguard simple. We monitor the same potential bound that is guaranteed under self-play and reduce only the learning rate when that bound is violated, following the monitoring principle of Daskalakis et al. [2021, Appendix D]. The cumulative state is never reset and the algorithm keeps the same form. Under self-play the threshold is never crossed, so the safeguard is inactive. Against arbitrary utility sequences, the rate adjustment keeps the potential √ under control and recovers the usual T -type adversarial dependence. Although the potential is designed around the proof, the resulting algorithm is simple to implement. In each iteration, the learner computes one scalar weight for each action from its cumulative centered utility, multiplies it by the one-step optimistic correction, and normalizes the resulting vector to obtain the next mixed strategy. Thus, for a player with at most d actions, each iteration requires O(d) arithmetic operations and O(d) memory. The stored state consists of two real numbers per action, namely the cumulative centered utility and the centered utility from the previous round, i.e., the optimistic prediction. The adversarial safeguard, if used, adds only one scalar learning rate. These ingredients play separate roles in the analysis. The multiplicative correction uses only the previous observation. The potential gives the stability needed to control Hellinger movement √ and obtain the n dependence, while its initial value yields the logarithmic dependence on d. The safeguard changes only the learning rate and leaves the rest of the update unchanged. The organization of the paper is as follows. Section A places our result within the literature on regret matching, optimistic learning, fast self-play, and stronger notions of regret. Section 2 introduces the learning model, MORM, and its formal guarantees. Section 3 explains how multiplicative optimism and the potential are constructed from the curvature, stability, and movement properties needed in the proof. Section 4 proves the self-play regret and CCE guarantees, and Section E establishes the adversarial extension. Throughout the self-play analysis, players receive exact utility vectors in a fixed finite game. 8
2
Multiplicatively Optimistic Regret Matching and Its Guarantees
We first describe the uncoupled learning setting of learning dynamics and the information available to each player, then introduce the Multiplicatively Optimistic Regret Matching (MORM) update and its explicit implementation. We conclude the section by stating its individual-regret and equilibrium guarantees.
2.1
Finite Games and Uncoupled Learning
Consider a finite n-player game. Each player i ∈ [n] has a nonempty Q finite action set Ai and mixedstrategy space Xi = ∆(Ai ). The utility function of player i is Ui : nj=1 Aj → [0, 1]. We assume that there is a public bound d ≥ 2 such that |Ai | ≤ d for every player i. We write x = (x1 , . . . , xn ) for a mixed-strategy profile and xi [a] for the probability that player i assigns to action a ∈ Ai . All logarithms are natural. We study repeated self-play in this fixed game. At each round t, all players simultaneously choose (t) their mixed strategies xi . After the strategies are chosen, player i observes its expected-utility (t) vector νi . For every action a ∈ Ai , (t)
νi [a] = Es
−i ∼
(t) j̸=i xj
N
[Ui (a, s−i )],
a ∈ Ai .
(2.1)
(t)
Thus, νi [a] is the expected utility that player i would obtain by playing action a against the opponents’ current mixed strategies. We assume exact full-information observations, so player i (t) observes the entire vector νi rather than a single sampled payoff. (t) The learning dynamics are uncoupled. When choosing xi , player i may use its own past observations, its action set, and the public parameters. It does not need to know the other players’ utility functions, current mixed strategies, or internal learning states. We define the centered utility vector D E (t) (t) (t) (t) (0) ui = νi − xi , νi 1, ui = 0. (2.2) (t)
The coordinate ui [a] ∈ [−1, 1] measures the instantaneous advantage of action a over the mixed (t) (t) strategy xi played on round t. In particular, ui [a] > 0 means that action a would have yielded a (t) higher expected utility than xi against the opponents’ round-t mixed strategies. We accumulate these advantages over time. The cumulative centered utility available before round t is t−1 X (t) (s) (1) (t+1) (t) (t) Ui = ui , Ui = 0, Ui = Ui + ui . (2.3) s=1 (t)
Thus, Ui depends only on observations from rounds 1, . . . , t − 1 and is available when player i (t) (T +1) chooses xi . After round T , the vector Ui contains exactly the centered utilities accumulated through round T . By construction, the centered utility has zero expectation under the played strategy. Moreover, player i’s external regret after T rounds is the largest cumulative centered utility, D E (t) (T ) (T +1) (t) [a]. (2.4) xi , ui = 0, Regi = max Ui a∈Ai
Allowing the comparator to be any fixed mixed strategy gives the same regret, since its cumulative (T ) utility is a convex combination of the cumulative utilities of the pure actions. Notice that Regi need not be nonnegative. 9
2.2
The Uncoupled Learning Update of MORM
We now define the learning rule of MORM. Set c := 2 + log d,
η :=
For each player i, define the potential 1/(c−1) X U [a] c−1 Ψi (U ) = c , f c a∈Ai
1 √ . 32 n
(2.5)
( (1 − z)−1 , z ≤ 0, f (z) = 1 + z, z ≥ 0.
(2.6)
The potential is defined on vectors of cumulative centered utilities. We write ∂a Ψi for the derivative of Ψi with respect to coordinate a. Every coordinate of ∇Ψi (U ) is strictly positive. At the beginning of round t, player i evaluates the gradient at the scaled cumulative centered (t) utility ηUi . The gradient provides a positive weight for each action. MORM then adjusts these (t−1) weights using the preceding centered utility ui and normalizes them to obtain the next mixed strategy, (t) (t) (t−1) xi ∝ ∇Ψi (ηUi ) ⊙ 1 + 4ηui . Here, ⊙ denotes coordinatewise multiplication, while ∝ means that the resulting positive vector is normalized to sum to one. Algorithm 1 MORM for player i Require: learning rate η from (2.5) and potential Ψi from (2.6). (1) (0) 1: Ui ← 0, ui ← 0. 2: for t = 1, 2, . . . do (t) (t) (t−1) 3: xi ∝ ∇Ψi (ηUi ) ⊙ 1 + 4ηui . 4: 5:
(t)
(t+1)
Ui 7: end for 6:
(t)
Play xi and Dobserve νE i . (t) (t) (t) (t) ui ← νi − xi , νi 1. (t)
← Ui
(t)
+ ui .
Remark 2.1 (Connection to Optimistic MWU). Multiplicative optimism is not specific to the potential used by MORM. With the log-sum-exp potential associated with negative entropy, the same construction gives (t) (t) (t−1) xi [a] ∝ exp ηUi [a] 1 + 4ηui [a] . Thus, the underlying response is MWU, with the previous utility entering as a multiplicative optimistic correction. Standard Optimistic MWU, or Optimistic Hedge, instead uses an exponential correction [Rakhlin and Sridharan, 2013b, Daskalakis et al., 2021]. In our notation, its update can be written as (t) (t) (t−1) xi [a] ∝ exp ηUi [a] exp ηui [a] . Since exp(z) = 1 + z + O(z 2 ), the correction used by MORM is a first-order analogue of the standard optimistic correction. The potential in this paper is chosen differently in order to obtain the curvature and stability properties needed for our analysis. 10
Explicit implementation. The gradient of Ψi has a closed form, so the update does not require differentiation at runtime. Define the scalar weight function ( (1 − z/c)−c , z ≤ 0, ac (z) = (2.7) (1 + z/c)c−2 , z ≥ 0. Differentiating (2.6) gives ∂a Ψi (U ) =
Ψi (U ) c
2−c ac (U [a]).
(2.8)
The factor (Ψi (U )/c)2−c is the same for every action and therefore disappears when the weights are normalized. Consequently, the update can be implemented directly as (t) (t) (t−1) xi [a] ∝ ac ηUi [a] 1 + 4ηui [a] ,
a ∈ Ai .
(2.9)
(t)
Thus, each action xi [a] receives a weight determined by two quantities. The first depends on its (t) cumulative centered utility Ui [a], while the second depends on its centered utility in the preceding (t−1) round ui [a]. Computing the strategy requires only coordinatewise powers, multiplication, and a single normalization. So, a round costs O(|Ai |) time and O(|Ai |) memory since the learner stores (t) (t−1) Ui , ui , and one scalar learning rate. In particular, a player implementing the rule of MORM for self-play never has to evaluate Ψi itself. √ (t−1) Remark 2.2. Since ui [a] ∈ [−1, 1] and 4η = 1/(8 n) ≤ 1/8, every optimistic correction satisfies (t−1) 1 + 4ηui [a] ∈ [7/8, 9/8]. Together with the strict positivity of every coordinate of ∇Ψi , this ensures (t) that the normalization in (2.9) is well defined on every round and that xi has full support. On the (1) (0) (1) first round, Ui = 0 and ui = 0. Since ac (0) = 1, all actions receive the same weight, so xi is uniform. The same conclusions hold under the learning-rate safeguard, since the safeguard can only decrease the learning rate. (t)
Remark 2.3. The factor ac (ηUi [a]) captures the cumulative performance of action a. It is (t) increasing in Ui [a], so actions with larger cumulative advantage receive larger weight. For actions with large negative cumulative advantage, this weight approaches zero, but it remains strictly positive (t−1) at every finite input. The second factor, 1+4ηui [a], provides the optimistic correction. It increases the weight of an action that performed better than the player’s mixed strategy in the preceding round and decreases the weight of an action that performed worse. Thus, the first factor summarizes past performance over all previous rounds, while the second reacts to the most recent observation.
2.3
Regret and Equilibrium Guarantees
We now state the main guarantees of MORM. Under self-play, every player has external regret bounded √ independently of the time horizon. The bound grows sublinearly with the number of players, as n, and only logarithmically with the maximum number of actions, as log d. A learning-rate safeguard, which only decreases the learning rate adaptively (and keeps the update rule the same), also gives the optimal adversarial guarantee in the face of adversarial utilities. We first summarize the two results.
11
Theorem 2.4 (Regret bounds for MORM). Consider a fixed n-player finite game with at most d ≥ 2 actions per player and utilities in [0, 1]. If all players i ∈ [n] follow MORM (Algorithm 1) with √ c = 2 + log d and learning rate η = 1/(32 n), observing their exact expected-utility vectors after each round, then every player i ∈ [n] has external regret (T )
Regi
√ ≤ O( n log d).
Moreover, MORM is adaptive to adversarial utilities through the learning-rate safeguard in Section E, which only decreases the learning rate adaptively and leaves the rest of the update unchanged. The safeguarded rule for any individual player i guarantees p √ (T ) Regi ≤ O( n log d + T log d) (t)
against arbitrary, possibly adaptive, utility vectors νi all T ≥ 1.
∈ [0, 1]|Ai | . Both bounds hold uniformly over
The precise self-play and adversarial bounds are proved in Theorem 4.10 and Theorem E.1, respectively. Together, these results establish Theorem 2.4. The self-play bound also yields convergence of the time-average of the played distributions to the set of coarse correlated equilibria (CCE). Corollary 2.5 (CCE). Under the assumptions of Theorem 4.10, the distribution T
σ
(T )
n
1 X O (t) = xj T
(2.10)
t=1 j=1
√ is a 96 n (2 + log d)/T -coarse correlated equilibrium. Hence, no player can improve its expected √ utility by more than 96 n (2 + log d)/T by committing instead to any fixed action. Section 3 explains the main ideas behind the construction and analysis of MORM. Section 4 proves the self-play regret bound and the equilibrium guarantee. Section E defines the learning-rate safeguard and proves the adversarial guarantee.
3
Proof Overview
The construction of MORM starts from the standard regret-matching argument [Hart and Mas-Colell, 2001, Cesa-Bianchi and Lugosi, 2003]. Regret matching chooses the strategy so that the linear change of its potential cancels exactly, but it still pays a positive quadratic remainder on every round. Our first step is to modify the response so that this linear term becomes negative when the current centered utility is predictable from the previous round. Before choosing the potential, we compare the usual ℓ1 movement argument with a squared Hellinger comparison of the players’ product distributions. The latter avoids an extra player factor in the prediction-error bound. We then construct Ψi so that its negative weighted square controls this same squared Hellinger movement. Combining the potential and prediction-error estimates gives the self-play regret bound. Fix a player i. Throughout the single-player calculations below, we omit the player index from vectors and potentials, and all sums over actions are over Ai . A vector U without a round superscript denotes an arbitrary input to the potential. Along the learning trajectory, the input to Ψ is ηU (t) .
12
3.1
The Classical Regret-matching Analysis
The external-regret version of regret matching chooses h i [z]+ = max{z, 0}, x(t) [a] ∝ U (t) [a] , +
using any distribution if all weights are zero. Consider its quadratic potential Φ(U ) =
1X [U [a]]2+ . 2 a
Since ∂a Φ(U ) = [U [a]]+ , regret matching obtains x(t) by normalizing ∇Φ(U (t) ). The centering identity in (2.4) gives D E (t) (t) ∇Φ(U ), u = 0. This identity holds for every utility vector ν (t) observed after play. When ∇Φ(U (t) ) = 0, it holds regardless of the chosen strategy x(t) . The derivative of [z]2+ /2 is 1-Lipschitz, so [z + h]2+ /2 ≤ [z]2+ /2 + [z]+ h + h2 /2. Summing over actions gives D E 1X d Φ(U (t+1) ) − Φ(U (t) ) ≤ ∇Φ(U (t) ), u(t) + u(t) [a]2 ≤ . 2 a 2 √ Telescoping from U (1) = 0 yields [Reg(T ) ]2+ /2 ≤ Φ(U (T +1) ) ≤ dT /2, and therefore Reg(T ) ≤ dT [Hart and Mas-Colell,P2001, Cesa-Bianchi and Lugosi, 2003]. The linear term cancels exactly, but the curvature term 12 a u(t) [a]2 still costs up to d/2 on each round. We seek a response that makes the linear term negative enough to offset this cost when the centered utility u(t) is predictable.
3.2
The Multiplicative Correction
We now ask how to modify the regret-matching response so that the first-order change of the potential can offset its second-order remainder. For the moment, leave the potential Ψ unspecified, except that its partial derivatives are strictly positive. Recall that U (t+1) = U (t) + u(t) . Hence, over one round, the input to the potential moves from (t) ηU to ηU (t) + ηu(t) . Taylor’s theorem gives D E Ψ(ηU (t+1) ) − Ψ(ηU (t) ) = η ∇Ψ(ηU (t) ), u(t) + second-order remainder. The first term describes the linear change of the potential and, as in regret matching, depends directly on the response chosen by the player. Our goal is to choose the response so that this term becomes negative enough to compensate for the second-order remainder. To make this possible, we construct Ψ so that its curvature is controlled by its own gradient coordinates. This is related in spirit to the intrinsic Lipschitz viewpoint of Soleymani et al. [2025a], where local variation is controlled using the underlying geometry. Here, the property we need is a direct comparison between the Hessian and the gradient weights. In particular, along the update segment we establish X ⊤ u(t) ∇2 Ψ(V )u(t) ≤ ∂a Ψ(V )u(t) [a]2 . a
13
We also show that the gradient coordinates change only multiplicatively as V moves from ηU (t) to ηU (t) + ηu(t) . Combining these two properties with the integral form of the Taylor remainder gives D E 2η 2 X Ψ(ηU (t+1) ) − Ψ(ηU (t) ) ≤ η ∇Ψ(ηU (t) ), u(t) + ∂a Ψ(ηU (t) )u(t) [a]2 . 3 a
(3.1)
We prove this estimate formally in Lemma 4.3. The key feature of (3.1) is that the second-order 2 term is not bounded simply by a constant multiple of u(t) 2 . Instead, each u(t) [a]2 is weighted by ∂a Ψ(ηU (t) ). These are precisely the gradient weights that we will use to construct the mixed strategy. We can therefore try to make the first-order term η⟨∇Ψ(ηU (t) ), u(t) ⟩ produce a negative square with the same weights. The quadratic regret-matching potential Φ from Section 3.1 does not have this gradient-weighted curvature property. At U = 0, we have ∇Φ(0) = 0, so a bound of the desired form would force the second-order remainder to vanish. Nevertheless, increasing any coordinate from zero in a positive direction increases Φ quadratically. Thus, the curvature of Φ does not decrease together with its gradient weights. We therefore need a potential whose curvature can be controlled by the same weights that define the strategy as in (3.1). 3.2.1
An Ideal Multiplicative Correction
The form of (3.1) suggests how the response should be chosen. Suppose temporarily that the current centered utility u(t) were known before the player chooses x(t) . Consider the response x(t) [a] ∝ ∂a Ψ(ηU (t) ) 1 + 4ηu(t) [a] . Thus, we start from the gradient weight ∂a Ψ(ηU (t) ) and multiply it by a correction that depends on the current advantage u(t) [a]. P Let Z = b ∂b Ψ(ηU (t) ) 1 + 4ηu(t) [b] be the normalizing constant. Then ∂a Ψ(ηU (t) ) 1 + 4ηu(t) [a] (t) x [a] = . Z Since the centered utility satisfies x(t) , u(t) = 0, we have 0=
X a
x(t) [a]u(t) [a] =
1 X ∂a Ψ(ηU (t) ) 1 + 4ηu(t) [a] u(t) [a]. Z a
Multiplying by Z, expanding, and rearranging gives X X ∂a Ψ(ηU (t) )u(t) [a] = −4η ∂a Ψ(ηU (t) )u(t) [a]2 . a
a
Therefore, the first-order term in (3.1) becomes D E X η ∇Ψ(ηU (t) ), u(t) = −4η 2 ∂a Ψ(ηU (t) )u(t) [a]2 . a
This is the key observation. The negative first-order term uses exactly the same weights ∂a Ψ(ηU (t) ) as the positive second-order term in (3.1), but with a larger coefficient. Thus, if the current centered utility were known in advance, the first-order decrease would more than compensate for the Taylor remainder. 14
Of course, this response cannot be implemented because u(t) is only known after x(t) is chosen. Moreover, u(t) depends on x(t) through the centering term x(t) , ν (t) 1, while ν (t) depends on the opponents’ current mixed strategies. We therefore use this calculation only to identify the ideal multiplicative correction 1 + 4ηu(t) [a]. The executable algorithm replaces the unavailable u(t) by the preceding centered utility u(t−1) , which is known before round t. The next step shows that this replacement preserves the useful negative weighted square up to an error controlled by u(t) − u(t−1) . 3.2.2
From the Ideal Correction to an Optimistic Update
The ideal correction derived above depends on the current centered utility u(t) , which is not available when the player chooses x(t) . We therefore predict u(t) using the preceding centered utility u(t−1) . This use of a prediction for the current utility is the optimistic step in the update. Substituting this prediction into the ideal correction gives x(t) [a] ∝ ∂a Ψ(ηU (t) ) 1 + 4ηu(t−1) [a] . (3.2) This is precisely the update used by MORM. It has the same form as the ideal response, but replaces the unavailable current advantage u(t) [a] by the optimistic prediction u(t−1) [a]. The same normalization argument as before now produces a cross term between the predicted and realized centered utilities. In particular, using x(t) , u(t) = 0 gives D E X η ∇Ψ(ηU (t) ), u(t) = −4η 2 ∂a Ψ(ηU (t) )u(t−1) [a]u(t) [a]. a
For the ideal correction, the corresponding product was u(t) [a]2 . The price of using the prediction u(t−1) [a] is therefore determined by how close it is to u(t) [a]. To make this precise, for every action a, 2 −4u(t−1) [a]u(t) [a] ≤ 2 u(t) [a] − u(t−1) [a] − 2u(t) [a]2 . Indeed, the difference between the right-hand side and the left-hand side is 2u(t−1) [a]2 ≥ 0. Thus, the cross term decomposes into two useful pieces. The first is a positive squared prediction error, while the second retains a negative multiple of u(t) [a]2 . Substituting this inequality into (3.1) gives 2 4η 2 X ∂a Ψ(ηU (t) ) u(t) [a] − u(t−1) [a] − ∂a Ψ(ηU (t) )u(t) [a]2 3 a a X X 2 2 (t) (t) (t−1) 2 ≤ 2η ∂a Ψ(ηU ) u [a] − u [a] − η ∂a Ψ(ηU (t) )u(t) [a]2 . (3.3)
Ψ(ηU (t+1) ) − Ψ(ηU (t) ) ≤ 2η 2
X
a
a
Inequality (3.3) captures the role of optimism in the update. When the prediction is accurate, the positive term involving u(t) − u(t−1) is small, while the negative weighted square remains. Under perfect prediction, u(t) = u(t−1) , the prediction-error term vanishes and the potential decreases unless u(t) = 0. More generally, the potential can increase only through the squared prediction error, while the same gradient weights continue to multiply the negative term involving u(t) [a]2 . This matching of weights is the reason for introducing the prediction multiplicatively through 1 + 4ηu(t−1) . The coefficient 4 leaves enough slack for a negative weighted square to remain after accounting for the Taylor remainder. 15
3.3
Measuring Strategy Movement with Hellinger Distance (t)
(t−1)
The positive term in (3.3) is driven by the prediction error ui − ui . In a fixed game, this error is caused by changes in the players’ mixed strategies. We therefore need to control one-round strategy movement, measured by a squared distance such as (t−1) 2
(t)
xi − xi
q q 2 (t) (t−1) . xi − xi
or
1
2
As we show next, the choice of distance matters for the dependence on the number of players. The usual ℓ1 comparison loses an extra player factor, while squared Hellinger distance avoids this loss. 3.3.1
Standard ℓ1 Comparison Loses a Player Factor (t)
To see the issue, first consider the uncentered utility vector νi . By multilinearity of expected (t) utility in a normal-form game, νi [a] is the expectation of the fixed payoff function Ui (a, ·) under the opponents’ product distribution. Since Ui (a, ·) ∈ [0, 1], (t)
(t−1)
νi − ν i
∞
≤
O
(t)
xj −
j̸=i
O
(t−1)
xj
j̸=i
. 1
A telescoping comparison of the two product distributions then gives O
(t)
xj −
j̸=i
O
(t−1)
j̸=i
(t)
X
≤
xj
(t−1)
xj − xj
j̸=i
1
1
.
Because the prediction-error term is squared, by Cauchy–Schwarz, this gives (t)
(t−1) 2
νi − νi
∞
≤ (n − 1)
(t)
X
(t−1) 2
xj − x j
j̸=i
1
.
(3.4)
This is the key game-level step in the RVU analysis. Under self-play, predictability of the utility vectors is controlled by the players’ strategy movement, thereby connecting utility variation to the individual regret bounds through the accumulated squared path length. The first factor of order n above comes from converting the square of a sum into a sum of squares. Summing the prediction-error bounds over players introduces another factor of order n, since each player’s movement affects the utilities of every other player. These two factors force the learning rate to scale as O(1/n) in standard RVU-based analyses of regularized learning in games [Syrgkanis et al., 2015, Farina et al., 2022, Anagnostides et al., 2022b,a, Soleymani et al., 2025b,a]. Our goal is to avoid the first of these two n factors. 3.3.2
Squared Hellinger Movement
We instead measure movement using √
x′ −
√
2
x
2
,
where square roots are taken coordinatewise. Up to a conventional factor of 1/2, this is squared Hellinger distance. 16
The key property is that squared Hellinger distance behaves additively across product distributions. In particular, 2
sO
(t)
xj −
sO
j̸=i
(t−1)
≤
xj
j̸=i
X q (t) q (t−1) 2 xj − xj . 2
j̸=i
2
The crucial difference from the ℓ1 comparison is that the right-hand side is already a sum of squared movements. No additional Cauchy–Schwarz step, and hence no additional factor of n as in (3.4), is needed. By standard properties of Hellinger distance, changes in the expectation of a [0, 1]-valued function are controlled by the square-root distance between the underlying distributions. Applying this to Ui (a, ·) under the opponents’ product distributions on rounds t and t − 1 gives, for every a ∈ Ai , (t) (t−1) νi [a] − νi [a]
sO
≤
(t) xj −
sO
j̸=i
(t−1)
xj
j̸=i
. 2
Taking the maximum over actions, squaring, and using the product comparison above yields X q (t) q (t−1) 2 (t) (t−1) 2 xj − xj . νi − ν i ≤ ∞
2
j̸=i
These properties of Hellinger distance are proved in Section D. (t) (t) Our analysis uses centered utilities ui rather than the uncentered vectors νi . Centering introduces an additional dependence on player i’s own strategy, but only changes the constant in the prediction-error bound. Combining the opponents’ product-distribution comparison with the centering term gives q q n 2 X (t) (t−1) 2 (t) (t−1) ui − ui ≤5 xj − xj , t ≥ 2. (3.5) ∞
2
j=1
Lemma 4.8 proves this bound in detail. The important point is that the prediction error is controlled by a sum of squared strategy movements without an additional player factor inside the inequality. Summing (3.5) over players therefore introduces only one factor of n. 3.3.3
What the Potential Must Control
The argument above for efficient regret bounds in the self-play identifies the movement measure we need. To close the self-play analysis, the negative gradient-weighted square in (3.3) must control q q 2 (t+1) (t) xi − xi . 2 (t−1)
As discussed after (3.3), using the preceding centered utility ui (t)
(t−1) 2
(t)
in place of the unavailable ui
introduces the squared prediction-error term ui − ui . We therefore seek a movement bound ∞ involving these same two quantities. This requirement guides the potential construction. In MORM, the positive coordinates ∂a Ψ(ηU (t) ) serve as the base weights assigned to the actions before normalization. Since square-root movement depends on relative changes in these weights, we need their ratios across consecutive rounds to remain controlled even when the weights themselves become very small. In other words, these coordinates must be multiplicatively stable. The next subsection constructs Ψ to ensure this property. 17
3.4
Choosing the Potential
We now construct the potential Ψ used by MORM. The preceding discussion identifies three properties that the potential must satisfy. First, Ψ should dominate the largest cumulative advantage maxa U [a] while having initial value only O(log d), so that a bound on the potential yields a regret bound with logarithmic dependence on the number of actions. Second, the curvature of Ψ should be controlled by its coordinates ∂a Ψ(U ), as required for the weighted Taylor estimate (3.1). Third, these same coordinates must remain sufficiently stable under normalization (multiplicatively stable) so that the negative weighted square in (3.3) can control the squared Hellinger movement from Section 3.3. We construct Ψ step by step to satisfy these three requirements. 3.4.1
The Scalar Function
We begin by designing a one-dimensional function f that will underlie the potential and its action weights. To convert a potential bound into a regret bound, we need f (z) ≥ 1 + z. On the nonnegative half-line, the simplest choice is therefore f (z) = 1 + z,
z ≥ 0.
This gives the desired linear control of positive cumulative advantages and has constant derivative f ′ (z) = 1. The negative half-line requires more care. Extending the linear branch as [1 + z]+ would make the derivative vanish for z < −1, so actions with sufficiently negative cumulative advantage would receive zero weight. More importantly, we need the resulting positive weights to remain stable after normalization. As discussed in Section 3.3, the negative weighted square in (3.3) must ultimately control squared Hellinger movement, which in turn controls the prediction error in a fixed game. Absolute stability is not enough after normalization. For example, the positive vectors (ε, ε) and (2ε, ε) become arbitrarily close as ε → 0, while their normalizations remain (1/2, 1/2) and (2/3, 1/3). Thus, when weights become small, their relative changes must become small as well. This type of multiplicative stability also appears in the analysis of log-regularized FTRL and Cautious Optimism [Farina et al., 2022, Soleymani et al., 2025b,a]. We therefore seek a positive, convex, continuously differentiable function f that agrees with 1 + z for z ≥ 0, satisfies f ′ (z) > 0 at every finite input, approaches zero as z → −∞, and becomes increasingly stable in relative terms as f ′ (z) becomes small. To identify a sufficient condition for the last property, consider a scalar prototype. For an input vector z, normalize the derivative weights according to f ′ (z[a]) x[a] = P ′ . b f (z[b]) If the input changes by a small vector h, then the relative change of the weight of action a is, to first order, f ′ (z[a] + h[a]) − f ′ (z[a]) f ′′ (z[a]) ≈ ′ h[a]. ′ f (z[a]) f (z[a]) Hence, f ′′ (z)/f ′ (z) measures the local relative sensitivity of the derivative weight.
18
Let x′ denote the normalized weights after the perturbation and set X S= f ′ (z[b]). b
The local normalization calculation underlying squared Hellinger movement gives ′′ √ √ 2 1X ′ f (z[a]) 2 ′ x − x ≲ f (z[a]) h[a]2 . S a f ′ (z[a]) 2 TheP important feature is the factor 1/S created by normalization. We want to control this expression by a f ′ (z[a])h[a]2 , which is the scalar analogue of the gradient-weighted square retained in (3.3). A convenient sufficient condition is ′′ 2 f (z) ≲ f ′ (z). (3.6) f ′ (z) Indeed, under (3.6), 1X ′ f (z[a]) S a
f ′′ (z[a]) f ′ (z[a])
2
h[a]2 ≲
X 1X ′ f (z[a])2 h[a]2 ≤ f ′ (z[a])h[a]2 , S a a
where the last inequality uses f ′ (z[a]) ≤ S. Thus, the extra factor of f ′ (z) in (3.6) compensates for the normalizing denominator. This calculation only motivates the scalar design. After aggregation, (3.10) provides the corresponding bound for the actual gradient weights of Ψ. We now choose the negative branch to satisfy (3.6). A particularly simple choice is f ′ (z) = f (z)2 ,
f (0) = 1,
z ≤ 0.
Indeed, f ′′ (z) = 2f ′ (z)f (z) = 2f (z)3 , so
f ′′ (z) f ′ (z)
2
= 4f (z)2 = 4f ′ (z).
Thus, the squared relative sensitivity decreases at exactly the same rate as the derivative weight. The differential equation satisfies d 1 = −1, dz f (z) and the condition f (0) = 1 therefore gives f (z) =
1 , 1−z
z ≤ 0.
Joining the reciprocal negative branch with the linear positive branch yields ( (1 − z)−1 , z ≤ 0, f (z) = 1 + z, z ≥ 0. The two branches agree in value and first derivative at zero, so f is positive, convex, and continuously differentiable, with f ′ (z) = min{f (z)2 , 1}. 19
Finally, the reciprocal branch preserves the lower bound needed for regret. For z ≤ 0, f (z) − (1 + z) =
z2 ≥ 0, 1−z
while equality holds for z ≥ 0. Hence, f (z) ≥ 1 + z everywhere. The reciprocal tail therefore provides both ingredients we need from the scalar construction. It preserves the linear lower bound used to control regret, while making small derivative weights sufficiently stable under normalization. The next step aggregates these scalar values across actions while retaining these properties and keeping the initial potential only logarithmic in d. 3.4.2
Aggregation and Scaling
We now aggregate the scalar values f (U [a]/c) across actions. The aggregation must preserve the lower bound on the largest cumulative advantage while keeping the initial potential small. A direct sum would not achieve the latter, since f (0) = 1 gives X f (0) = |Ai |, a∈Ai
which can be of order d. Instead, we use an ℓc−1 norm. This follows the classical p-norm idea of choosing the norm order logarithmic in the dimension, so that a high-order norm approximates the maximum while having only logarithmic dimension dependence [Gentile, 2003, Shalev-Shwartz, 2012]. For any nonnegative vector, max f a
U [a] c
1/(c−1) X U [a] c−1 U [a] 1/(c−1) ≤ f ≤ |Ai | max f . a c c
a∈Ai
With c = 2 + log d, we have c − 1 = 1 + log d, and therefore |Ai |1/(c−1) ≤ d1/(1+log d) < e < 3. Thus, the ℓc−1 norm approximates the largest scalar value within a constant factor. In particular, at the origin its value is less than three. This is the reason for choosing an aggregation exponent of order log d. We also divide the scalar inputs by c and multiply the resulting norm by c. These two scalings are chosen so that differentiation does not introduce an additional factor depending on c. Indeed, the factor 1/c from differentiating f (U [a]/c) is canceled by the outer multiplier c, while the factors c − 1 from the inner and outer powers cancel each other. This leads to 1/(c−1) X U [a] c−1 , Ψi (U ) = c f c
a∈Ai
which is the potential defined in (2.6). The construction now gives the two properties needed for the regret analysis. First, since f (0) = 1, Ψi (0) = c|Ai |1/(c−1) < 3c. 20
Second, the ℓc−1 norm dominates each coordinate and f (z) ≥ 1 + z, so for every action a, U [a] Ψi (U ) ≥ cf ≥ c + U [a]. c Hence, 0 < Ψi (U ),
Ψi (U ) ≥ c + max U [a].
Ψi (0) < 3c,
a
(T +1)
The last inequality is the regret certificate. If Ψi (ηUi (T )
η Regi
(T +1)
= η max Ui a
) ≤ 4c, then
(T +1)
[a] ≤ Ψi (ηUi
(3.7)
) − c ≤ 3c,
where we used (2.4). Therefore, (T )
Regi
≤
3c . η
Since c = 2 + log d, the initial potential is only O(log d). Thus, the power-norm aggregation is what ultimately gives the logarithmic dependence on the number of actions. 3.4.3
Recovering the Power Weights
The potential construction also explains the explicit power weights used by MORM. Differentiating Ψi with respect to coordinate a gives U [a] c−2 ′ U [a] Ψi (U ) 2−c f f . ∂a Ψi (U ) = c c c The first factor is common to all actions. The action-specific part is determined entirely by the two branches of f . On the negative branch, f ′ = f 2 , while on the positive branch, f ′ = 1. Therefore, c−2 1 − U [a] −c , U [a] ≤ 0, U [a] U [a] c f f′ = 1 + U [a] c−2 , U [a] ≥ 0. c c c This is exactly the weight function ac defined in (2.7). Hence, we recover Ψi (U ) 2−c ∂a Ψi (U ) = ac (U [a]), c which is (2.8). The prefactor (Ψi (U )/c)2−c is independent of the action, so it disappears when the weights are normalized. Substituting (2.8) into the gradient response (3.2) therefore gives (t) (t) (t−1) xi [a] ∝ ac ηUi [a] 1 + 4ηui [a] , which is precisely the explicit update in (2.9). Thus, the two powers appearing in ac arise directly from the scalar construction. The reciprocal branch f ′ = f 2 produces the exponent c for negative cumulative advantages, while the linear branch f ′ = 1 produces the exponent c − 2 for positive cumulative advantages. 21
3.4.4
Weighted Curvature and Stability
We now verify the geometric properties of Ψi needed in the analysis. The first is a weighted curvature bound, which gives the Taylor estimate (3.1). The second is multiplicative stability of the coordinates ∂a Ψi , which allows us to compare these weights along a finite update. We also record a uniform bound on their total mass, which will later be used to control prediction-error terms. Recall the scalar weight ac from (2.7). Away from zero, its logarithmic derivative is ( (1 − z/c)−1 , z < 0, a′c (z) = (3.8) ac (z) (c − 2)/(c + z), z > 0. Both branches lie in [0, 1], independently of d. Thus, the relative sensitivity of each scalar weight is uniformly bounded. This bound also controls the curvature of the aggregated potential. Differentiating (2.8) at points with no zero coordinates gives a′c (U [a]) c−2 2 ∇ Ψi (U ) = diag ∂a Ψi (U ) ∇Ψi (U )∇Ψi (U )⊤ . − ac (U [a]) Ψi (U ) The rank-one matrix in the second term is positive semidefinite, so subtracting it can only decrease the Hessian in the positive semidefinite order. Using (3.8), the diagonal term is bounded above by diag(∂a Ψi (U )). Since Ψi is convex, its Hessian is positive semidefinite wherever it exists. Hence, 0 ⪯ ∇2 Ψi (U ) ⪯ diag ∂a Ψi (U ) . Equivalently, for every vector v, v ⊤ ∇2 Ψi (U )v ≤
X
∂a Ψi (U )v[a]2 .
a
This is exactly the gradient-weighted curvature property motivated in Section 3.2. We will also use that the gradient has uniformly bounded total mass. Applying Hölder’s inequality to the derivative formula gives X ∂a Ψi (U ) ≤ 3. a
We record the two bounds together as X ∂a Ψi (U ) ≤ 3, 0 ⪯ ∇2 Ψi (U ) ⪯ diag ∂a Ψi (U ) where the Hessian exists.
(3.9)
a
The Hessian bound controls the Taylor remainder, while the total-mass bound will later convert gradient-weighted prediction errors into ℓ∞ prediction errors. The remaining ingredient is multiplicative stability. By Lemma 4.2, moving the potential input (t) (t) from ηUi in the direction ηui changes each gradient coordinate only multiplicatively. In particular, for 0 ≤ θ ≤ 1, (t)
∂a Ψi ηUi (t)
Since ui
∞
(t)
+ θηui
(t)
2θη ui
≤e
≤ 1 and η ≤ 1/8, 4 e2θη ≤ e2η < . 3 22
∞
(t)
∂a Ψi (ηUi ).
Thus, every gradient coordinate along the update segment is at most 4/3 times its value at the beginning of the round. Combining this multiplicative stability with (3.9) gives the desired Taylor estimate. Indeed, the integral remainder is at most Z 1 X (t) (t) (t) 2 η (1 − θ) ∂a Ψi ηUi + θηui ui [a]2 dθ, 0
a
which is bounded by Z X 2η 2 X 4η 2 1 (t) (t) (t) (t) ∂a Ψi (ηUi )ui [a]2 = (1 − θ) dθ ∂a Ψi (ηUi )ui [a]2 . 3 0 3 a a Adding the first-order term gives (3.1). Section B proves these properties formally, including the regularity needed when a coordinate crosses zero. 3.4.5
Stability After Normalization
We now lift the scalar stability condition from Section 3.4.1 to the gradient weights P of the aggregated potential. The main difficulty is normalization. When the total derivative mass a ∂a Ψi (U ) becomes small, controlling only the absolute or multiplicative change of each weight is not enough. We need the sensitivity of the weights to decrease at the same time. The role of the reciprocal negative branch is especially transparent when every coordinate of the input equals cz with z < 0. In this case, ′ X ac (cz) 2 1/(c−1) 2 ∂a Ψi (cz1) = |Ai | f (z) , = f (z)2 . a (cz) c a Thus, the total derivative mass and the squared logarithmic sensitivity vanish at the same rate. For arbitrary inputs, the corresponding bound is 2 a′c (U [a])/ac (U [a]) P ≤ 3 where the derivatives exist. (3.10) b ∂b Ψi (U ) This is the aggregated analogue of the scalar condition developed in Section 3.4.1. Importantly, it does not require the total derivative mass to be bounded away from zero. Instead, the numerator shrinks whenever the denominator does. Section C proves (3.10). To see why this is exactly the normalization bound we need, first ignore the optimistic correction. By (2.8), normalizing the power weights ac (U [a]) is equivalent to normalizing the gradient coordinates, ac (U [a]) ∂a Ψi (U ) x[a] = P =P . b ac (U [b]) b ∂b Ψi (U ) For a small input change in direction v, the square-root movement is controlled locally by ′ 1 X ∂a Ψi (U ) ac (U [a]) 2 P v[a]2 . 4 a ∂ Ψ (U ) a (U [a]) c b b i Applying (3.10) removes the normalizing denominator and gives 3X ∂a Ψi (U )v[a]2 . 4 a 23
Thus, after normalization, strategy movement is controlled by the same gradient-weighted square that appears in (3.3). (t) Along the learning trajectory, the cumulative input changes in direction ηui . Integrating the preceding local estimate and using the multiplicative stability established in Section 3.4.4 gives a finite-step bound in terms of X (t) (t) η2 ∂a Ψi (ηUi )ui [a]2 . a (t−1)
The optimistic correction also changes between rounds, from 1 + 4ηui
(t)
to 1 + 4ηui . As discussed (t)
(t−1) 2
after (3.3), this second change is controlled by the squared prediction error ui − ui . ∞ Consequently, the movement between consecutive strategies is controlled by exactly the two quantities already present in the optimistic potential inequality. Lemma 4.6 makes this statement precise.
3.5
Bounding Regret in Self-play
We now combine the potential inequality with the strategy-movement and prediction-error bounds developed above. The key point is that the negative gradient-weighted square in (3.3) controls the same squared Hellinger movement that, in a fixed game, controls the prediction error. By Lemma 4.6, consecutive strategies satisfy q q 2 X (t+1) (t) (t) (t) (t) (t−1) 2 xi − xi ≤ 4η 2 ∂a Ψi (ηUi )ui [a]2 + 16η 2 ui − ui . 2
∞
a
The first term is exactly the gradient-weighted square that appears with a negative sign in (3.3), while the second is the same squared prediction error that appears on its positive side. Summing the movement estimate over rounds and combining it with the telescoped version of (3.3) gives q q T T 2 X 1X (t) (t−1) (T +1) (t) (t−1) 2 xi − xi . (3.11) Ψi (ηUi ) ≤ 3c + 10η 2 ui − ui − 4 ∞ 2 t=1
t=2
We refer to (3.11) as a potential-level RVU inequality. It is derived directly from the potential argument and holds for arbitrary bounded utility vectors. The left-hand side contains both the terminal potential and accumulated squared Hellinger movement, while the right-hand side contains the initial-potential bound and accumulated squared prediction error. No self-play in games assumption has been used yet. We now use self-play in a fixed game. By (3.5), for every t ≥ 2, q q n 2 X (t) (t−1) 2 (t) (t−1) ui − ui ≤5 xj − xj . ∞
j=1
2
Thus, the prediction error on the right-hand side of (3.11) is controlled by exactly the same movement (0) (1) quantity that appears on its left-hand side. For the first round, ui = 0 and ui ≤ 1. ∞
Substituting (3.5) into (3.11), summing over players, and discarding the nonnegative terminal potentials gives X q q n X T 2 1 (t) (t−1) 2 − 50nη xj − xj ≤ 3nc + 10nη 2 . 4 2 j=1 t=2
24
Only one factor of n appears in the movement coefficient because summing the prediction-error bounds contributes one factor of n. The Hellinger product comparison in Section 3.3 avoids the additional player factor that arises in the corresponding ℓ1 argument. √ With η = 1/(32 n), nη 2 =
1 , 1024
1 103 1 − 50nη 2 = > . 4 512 5
The movement term can therefore be absorbed onto the left-hand side, yielding q q n X T 2 X (t) (t−1) ≤ 16nc. xj − xj 2
j=1 t=2
In particular, the accumulated squared movement is bounded uniformly over the horizon. We can now return to the potential of a single player. Substituting the movement bound into (3.11) and using (3.5) gives (T +1)
Ψi (ηUi
) ≤ 4c.
Finally, the certificate (3.7) and the regret identity (2.4) imply (T )
η Regi
(T +1)
≤ Ψi (ηUi
) − c ≤ 3c.
Hence, (T )
Regi
≤
√ 3c = 96 n (2 + log d). η
√ The dependence on d comes from the initial potential c = 2 + log d, while the n dependence comes from choosing η so that nη 2 remains a sufficiently small constant. The argument applies to every finite horizon and bounds accumulated squared strategy movement.
4
Analysis of MORM
We now make the proof overview rigorous. We first establish the geometric properties of the potential needed for the weighted Taylor bound and for stability after normalization. These properties yield a one-round potential inequality with a negative gradient-weighted square. We then show that the same weighted square controls strategy movement. Combining the resulting potential and movement bounds gives a potential-level inequality in terms of the squared prediction errors. Finally, in a fixed game, we bound these prediction errors by the players’ squared Hellinger movement and close the argument to obtain a uniform bound on the potential and regret. Until the self-play analysis in Section 4.5, we fix a player i and allow the observed utility vectors (t) νi to be an arbitrary sequence in [0, 1]|Ai | . Throughout this part, we set c = 2 + log d and use a √ fixed learning rate 0 < η ≤ 1/16. We specialize to self-play in a fixed game and set η = 1/(32 n) only in the final part of the analysis. Recall from (2.2) and (2.3) that D E (t) (t) (t) (t) (t+1) (t) (t) ui = νi − xi , νi 1, Ui = Ui + ui .
25
Hence, (t)
ui
∞
≤ 1,
D
(t)
(t)
xi , ui
E
= 0,
(1)
Ui
(0)
= ui
= 0.
All sums over actions in a single-player calculation are over Ai , and every horizon considered below is finite. The basic calculus properties of the potential, including its weighted curvature and multiplicative stability, are proved in Section B. The corresponding stability bounds for the normalized response are proved in Section C. The elementary square-root-distance identities used to compare expectations and product distributions (properties of Hellinger distance) are collected in Section D. We state the results we need below before applying them. The adversarial guarantee is treated separately in Section E. The safeguard leaves the MORM update unchanged and only decreases the learning rate when necessary under adversarial utilities.
4.1
Potential Geometry and Multiplicative Stability
We now make precise the potential properties motivated in the proof overview in Section 3.4. In Section 3.2, we required the curvature of Ψi to be controlled by its partial derivatives ∂a Ψi , so that the Taylor remainder carries the same weights as the optimistic potential decrease. In Section 3.4.5, we saw that these weights must also remain stable under finite changes of the potential input. We establish these properties below and then combine them to obtain the finite-step Taylor bound. We begin with the basic geometry of the potential, collecting its convexity, positivity of the derivatives, and weighted curvature bound. Lemma 4.1. Fix a player i and let c = 2 + log d. The potential Ψi is convex and continuously differentiable on R|Ai | , with locally Lipschitz gradient. For every U , Ψi (U ) > 0,
Ψi (0) = c|Ai |1/(c−1) < 3c,
Ψi (U ) ≥ c + max U [a]. a
Moreover, ∂a Ψi (U ) =
Ψi (U ) c
2−c ac (U [a]) > 0,
X
∂a Ψi (U ) ≤ 3.
a
Where the Hessian exists, 0 ⪯ ∇2 Ψi (U ) ⪯ diag ∂a Ψi (U ) . The same directional second-derivative bound holds almost everywhere along every line segment. The bounds Ψi (0) < 3c and Ψi (U ) ≥ c + maxa U [a] give the regret certificate from (3.7). In particular, controlling the terminal potential will directly control the largest cumulative regret. The remaining bounds P describe the geometry needed for the potential analysis. The total derivative mass satisfies a ∂a Ψi (U ) ≤ 3, which will allow us to bound gradient-weighted prediction errors by their ℓ∞ counterparts. More importantly, the Hessian bound gives, for every vector v, X v ⊤ ∇2 Ψi (U )v ≤ ∂a Ψi (U )v[a]2 . a
Thus, the curvature of Ψi is controlled by the same coordinates ∂a Ψi (U ) that determine the action weights in MORM. This is precisely the weighted-curvature property motivated in Section 3.2. Section B proves Lemma 4.1 directly from the scalar function f and the power-norm construction of Ψi . 26
The Hessian bound is pointwise, whereas a finite update moves through an entire segment of potential inputs. To control the Taylor remainder using the gradient at the beginning of the update, we therefore need to compare ∂a Ψi at different points along this segment. This is the role of multiplicative stability. Lemma 4.2 (Multiplicative stability). For every U , u ∈ R|Ai | , every η > 0, and every action a ∈ Ai , log
∂a Ψi (U + ηu) ≤ 2η ∥u∥∞ . ∂a Ψi (U )
(4.1)
For MORM with a fixed rate 0 < η ≤ 1/16 and any sequence of utility vectors in [0, 1]|Ai | observed after play, (t+1)
log
xi
[a]
(t) xi [a]
(t)
≤ 2η ui
(t+1)
In particular, if η ≤ 1/32, then xi
∞
+
8η (t) (t−1) . ui − u i 1 − 4η ∞
(4.2)
(t)
[a]/xi [a] ∈ [1/2, 2] for every action a.
The first inequality gives multiplicative stability of the potential weights ∂a Ψi . The second shows that the played probabilities inherit a corresponding stability bound, accounting for both the cumulative-utility update and the optimistic correction. For the Taylor argument, we only need (4.1); the probability-ratio bound will be used later in the movement analysis. Both statements are proved in Section B. Combining the pointwise curvature bound from Lemma 4.1 with the multiplicative stability of the gradient coordinates from Lemma 4.2 gives the finite-step Taylor estimate used throughout the analysis. Lemma 4.3 (One-step Taylor bound). For every U , u ∈ R|Ai | with ∥u∥∞ ≤ 1 and every 0 < η ≤ 1/8, Ψi (U + ηu) − Ψi (U ) ≤ η ⟨∇Ψi (U ), u⟩ +
2η 2 X ∂a Ψi (U )u[a]2 . 3 a
The coefficient 2/3 comes from combining the weighted curvature bound with multiplicative stability along the update segment. By (4.1), 4 ∂a Ψi (U + θηu) ≤ ∂a Ψi (U ), 3
0 ≤ θ ≤ 1,
when ∥u∥∞ ≤ 1 and η ≤ 1/8. Hence, the integral Taylor remainder is at most 4η 2 3
Z 1 (1 − θ) dθ 0
X
∂a Ψi (U )u[a]2 =
a
2η 2 X ∂a Ψi (U )u[a]2 . 3 a (t)
(t)
Adding the first-order term proves Lemma 4.3. Taking U = ηUi and u = ui recovers (3.1). The full argument, including the regularity needed when a coordinate crosses zero, is given in Section B.
27
4.2
One-round and Cumulative Potential Bounds
We now make the cancellation from Section 3.2 rigorous. We first derive a one-round potential inequality. This argument is local to a single round and therefore remains valid when the safeguard changes the learning rate between rounds. We then specialize to a fixed learning rate and telescope the one-round inequalities to obtain the cumulative potential bound used in the self-play analysis. Lemma 4.4 (One-round potential change). Fix a player i and a round t. Suppose that on this round (t) the player uses the MORM response (3.2) with some 0 < η ≤ 1/16. After observing νi ∈ [0, 1]|Ai | and updating according to (2.2) and (2.3), X X 2 (t+1) (t) (t) (t) (t−1) (t) (t) Ψi (ηUi ) − Ψi (ηUi ) ≤ 2η 2 ∂a Ψi (ηUi ) ui [a] − ui [a] − η 2 ∂a Ψi (ηUi )ui [a]2 . a
a
The bound is local to round t and remains valid even if the learning rate changes across rounds. (t−1)
Proof. Since ui ≤ 1 and η ≤ 1/16, every optimistic correction factor is at least 3/4. Together ∞ with the positivity of ∂a Ψi from Lemma D 4.1, thisEensures that the response is well defined. (t) (t) By the centering identity in (2.4), xi , ui = 0. Substituting the normalized response and clearing its positive normalizing denominator gives X X (t) (t) (t) (t−1) (t) 0= ∂a Ψi (ηUi )ui [a] + 4η ∂a Ψi (ηUi )ui [a]ui [a]. a
a
Hence, the first-order term in Lemma 4.3 satisfies D E X (t) (t) (t) (t−1) (t) η ∇Ψi (ηUi ), ui = −4η 2 ∂a Ψi (ηUi )ui [a]ui [a]. a
For every action a, (t−1)
−4ui
(t)
(t)
(t−1)
[a]ui [a] = 2 ui [a] − ui
2 (t) (t−1) [a] − 2ui [a]2 − 2ui [a]2 . (t)
Dropping the last, nonpositive contribution and applying Lemma 4.3 with input ηUi (t) ui gives (t+1)
Ψi (ηUi
(t)
) − Ψi (ηUi ) ≤ 2η 2
X
(t)
(t)
(t−1)
∂a Ψi (ηUi ) ui [a] − ui
a
and direction
2 4η 2 X (t) (t) [a] − ∂a Ψi (ηUi )ui [a]2 . 3 a
Only the learning rate used on round t enters the argument. This is the rigorous version of the one-round estimate (3.3) from the proof overview. We now fix the learning rate so that the potential differences telescope across rounds. Lemma 4.5 (Potential telescope bound). For any fixed 0 < η ≤ 1/16, any sequence of utility vectors in [0, 1]|Ai | observed after play, and every T ≥ 1, (T +1)
Ψi (ηUi
) + η2
T X X t=1
(t)
(t)
∂a Ψi (ηUi )ui [a]2 ≤ 3c + 6η 2
a
T X t=1
28
(t)
(t−1) 2
ui − ui
∞
.
(4.3)
Proof. Apply Lemma 4.4 on each round and move the negative weighted square to the left. By the total derivative-mass bound in Lemma 4.1, X
(t)
(t)
(t−1)
∂a Ψi (ηUi ) ui [a] − ui
2 (t) (t−1) 2 [a] ≤ 3 ui − ui . ∞
a
Therefore, (t+1)
Ψi (ηUi
(t)
) − Ψi (ηUi ) + η 2
X
(t)
(t)
(t)
(t−1) 2
∂a Ψi (ηUi )ui [a]2 ≤ 6η 2 ui − ui
a
∞
.
Because the learning rate is fixed, summing over t = 1, . . . , T telescopes the potential terms, T X
(t+1)
Ψi (ηUi
(t) (T +1) ) − Ψi (ηUi ) = Ψi (ηUi ) − Ψi (0).
t=1
Using Ψi (0) < 3c from Lemma 4.1 proves (4.3). Both terms on the left of (4.3) are nonnegative. In the next step, the gradient-weighted square provides the control on strategy movement needed for the self-play analysis.
4.3
From Weighted Squares to Strategy Movement
We now show that the gradient-weighted square in (4.3) controls the movement of the player’s strategy. Since MORM may assign very small probability to some actions, we work in square-root coordinates √ 2 √ and measure movement by x − x′ . As motivated in Section 3.4.5, the stability built into the 2 potential is precisely what allows the gradient-weighted square to control this movement. Lemma 4.6. Suppose player i uses MORM with a fixed rate 0 < η ≤ 1/16 and receives any sequence of utility vectors in [0, 1]|Ai | after play. For every t ≥ 1, q
(t+1)
xi
−
q 2 X (t) (t) (t) (t) (t−1) 2 xi ≤ 4η 2 ∂a Ψi (ηUi )ui [a]2 + 16η 2 ui − ui . 2 (t)
∞
a
(4.4)
(t+1)
Proof. Fix t. Between xi and xi , both the cumulative input and the optimistic correction change. We separate these two effects using the intermediate distribution (t)
(t)
ac (ηUi [a])(1 + 4ηui [a]) . P (t) (t) a (ηU [b])(1 + 4ηu [b]) c b i i (t)
(t)
This distribution keeps the old cumulative input ηUi but uses the new correction ui . By Lemma C.3, changing only the correction contributes at most (t−1) 2
(t)
8η 2 ui − ui
∞
to the squared distance between the square-root vectors. By Lemma C.4, changing the cumulative (t) (t+1) input from ηUi to ηUi while keeping the correction fixed contributes at most X (t) (t) 2η 2 ∂a Ψi (ηUi )ui [a]2 . a
29
Both estimates are proved in Section C by differentiating normalized paths and integrating their square-root speeds. Applying the triangle inequality to the square-root vectors and then (x + y)2 ≤ 2x2 + 2y 2 gives q
(t+1) xi −
q 2 X (t) (t) (t) (t−1) 2 (t) . ≤ 4η 2 ∂a Ψi (ηUi )ui [a]2 + 16η 2 ui − ui xi 2
∞
a
This proves (4.4). In particular, the same gradient-weighted square that appears in the potential bound (4.3) controls strategy movement.
4.4
The Potential-level RVU Inequality
We now combine the cumulative potential bound (4.3) with the movement estimate (4.4). The gradient-weighted square in (4.3) provides exactly the budget needed to control accumulated squared strategy movement. Proposition 4.7 (Potential-level RVU inequality). For a fixed rate 0 < η ≤ 1/16, any sequence of utility vectors in [0, 1]|Ai | observed after play, and every integer T ≥ 1, (T +1) Ψi (ηUi ) ≤ 3c + 10η 2
T X t=1
T 1X (t) (t−1) 2 ui − ui − 4 ∞ t=2
q q 2 (t) (t−1) xi − xi . 2
Proof. Suppose first that T ≥ 2. Summing (4.4) over t = 1, . . . , T − 1, dividing by four, and extending the two nonnegative sums on the right through round T gives T
1X 4
q q T X T 2 X X (t) (t−1) (t) (t) (t) (t−1) 2 xi − xi ≤ η2 ∂a Ψi (ηUi )ui [a]2 + 4η 2 ui − ui . 2
t=2
(T +1)
Adding Ψi (ηUi
t=1
a
∞
t=1
) and applying (4.3) to the potential and weighted-square terms yields
1 (T +1) Ψi (ηUi )+ 4
q q T T 2 X X (t) (t−1) (t) (t−1) 2 xi − xi ≤ 3c + 10η 2 ui − u i . 2
t=2
t=1
∞
For T = 1, the movement sum is empty, and the same conclusion follows directly from (4.3). This is the potential-level RVU inequality previewed in (3.11). Its right-hand side depends only on the accumulated squared prediction errors, while its left-hand side controls both the terminal potential and accumulated squared strategy movement. The prediction error is expressed in terms (t) (t) of the centered utilities it captures both changes in the utility vector νi and changes in D ui . Thus, E (t)
(t)
the centering term xi , νi . No self-play assumption has been used so far. In the next subsection, we specialize to self-play in a fixed game and use the Hellinger prediction-error bound to close the argument.
4.5
Prediction Error under Self-play in a Fixed Game
We now specialize to self-play in a fixed game. This is the first point where the game structure enters the analysis. As discussed in Section 3, changes in the opponents’ strategies change the player’s action-utility vector, while movement of the player’s own strategy changes the centering term. The following lemma controls both effects by the players’ squared Hellinger movement. 30
Lemma 4.8. In the model of Section 2.1, for every player i and every t ≥ 2, (t−1) 2
(t)
ui − ui
∞
≤5
q q n 2 X (t) (t−1) . xj − xj 2
j=1
Proof. Fix i and t ≥ 2. We first control the change in action utilities caused by the opponents. For any a, b ∈ Ai , the function Ui (a, s−i ) − Ui (b, s−i ) takes values in [−1, 1]. Applying the expectation comparison from Lemma D.1 to the opponents’ current and previous product distributions gives (t) (t) (t−1) (t−1) (νi [a] − νi [b]) − (νi [a] − νi [b])
≤2
sO
(t) xj −
sO
j̸=i
(t−1)
xj
j̸=i
. 2
Since the same payoff function is evaluated on both rounds, the fixed-game assumption applies. Using the product comparison from Lemma D.2, 1/2 q q 2 X (t) (t−1) (t) (t) (t−1) (t−1) xj − xj . (νi [a] − νi [b]) − (νi [a] − νi [b]) ≤ 2 2
j̸=i
D E (t) (t−1) We next account for centering. Adding and subtracting xi , νi gives (t)
(t−1)
ui [a] − ui
(t)
(t−1)
[a] = νi [a] − νi
D E D E (t) (t) (t−1) (t) (t−1) (t−1) [a] − xi , νi − νi − xi − xi , νi .
The first three terms can be written as i X (t) h (t) (t) (t−1) (t−1) xi [b] (νi [a] − νi [b]) − (νi [a] − νi [b]) , b
so their absolute value is bounded by the estimate. D preceding opponent-movement E (t) (t−1) For the remaining centering term, xi − xi , 1 = 0, so D
(t)
(t−1)
xi − x i
(t−1)
, νi
E
≤
1 (t) (t−1) x − xi ≤ 2 i 1
q q (t) (t−1) xi − xi
. 2
Combining the two contributions and maximizing over a yields 1/2 q q X q (t) q (t−1) 2 (t) (t−1) + ≤ 2 xj − xj xi − xi
(t)
(t−1)
ui − u i
∞
2
j̸=i
Applying Cauchy–Schwarz to the two terms, with coefficients 2 and 1, gives n X (t) (t−1) 2 ui − ui ≤5 ∞ j=1
31
. 2
q q 2 (t) (t−1) xj − xj . 2
(0)
On the first round, ui T X
(1)
= 0 and ui (t−1) 2
(t)
ui − ui
∞
t=1
∞
≤ 1. Therefore,
≤1+5
q q n X T 2 X (t) (t−1) xj − xj . 2
j=1 t=2
Substituting this bound into Proposition 4.7 gives T
(T +1)
Ψi (ηUi
)+
1X 4
q
(t)
xi −
q q q n X T 2 2 X (t−1) (t) (t−1) ≤ 3c + 10η 2 + 50η 2 . (4.5) xi xj − xj 2
t=2
j=1 t=2
2
The product-distribution comparison is the key game-level step. It controls the prediction error by a sum of squared strategy movements, without an additional factor of n inside the inequality. Thus, after summing (4.5) over players, only one factor of n appears. This is what permits the √ learning rate to scale as η = O(1/ n).
4.6
Uniform Movement and Regret under Self-play
√ We now complete the self-play argument with η = 1/(32 n). The final step has the same absorption structure as in standard RVU analyses: after summing the playerwise inequalities, the prediction-error term is controlled by the same accumulated movement that appears on the left. Here, however, this movement is measured by the squared Hellinger path length, q q n X T 2 X (t) (t−1) xj − xj . 2
j=1 t=2
Our choice of learning rate leaves a positive coefficient on this term, yielding a uniform bound on the accumulated squared movement. Feeding this bound back into the playerwise inequality then controls each terminal potential, and hence individual regret. √ Proposition 4.9 (Path Length). Suppose every player uses MORM with η = 1/(32 n) in the same fixed game. Then, for every integer T ≥ 1, q q n X T 2 X (t) (t−1) xj − xj ≤ 16nc, 2
j=1 t=2
and, for every player i, (T +1)
Ψi (ηUi
) ≤ 4c.
Proof. Fix a finite horizon T . Summing (4.5) over i = 1, . . . , n and collecting the movement terms gives n X i=1
(T +1) Ψi (ηUi )+
X q q n X T 2 1 (t) (t−1) 2 − 50nη xj − xj ≤ 3nc + 10nη 2 . 4 2 j=1 t=2
Since each potential is positive, we may omit the first term on the left. Moreover, nη 2 =
1 , 1024
1 103 1 − 50nη 2 = > . 4 512 5 32
It follows that q q n X T 2 X (t) (t−1) xj − xj ≤ 15nc + 50nη 2 ≤ 16nc. 2
j=1 t=2
We now return to (4.5) for a fixed player i. Using the movement bound above and the nonnegativity of the player’s movement term, (T +1)
Ψi (ηUi
) ≤ 3c + 10η 2 + 50η 2 (16nc) = 3c + 10η 2 +
25 c. 32
Since 10η 2 ≤ 10/1024 < c/32, (T +1) Ψi (ηUi )≤
61 1 25 c = c < 4c. 3+ + 32 32 16
Both bounds therefore hold for every player and every finite horizon. The potential bound immediately yields the individual regret guarantee from Theorem 2.4. Theorem 4.10 (Individual regret). Consider a fixed n-player finite game with at most d ≥ 2 actions per player and utilities in [0, 1]. Suppose every player uses MORM (Algorithm 1) with c = 2 + log d √ (t) and η = 1/(32 n), and observes its exact expected-utility vector νi after each simultaneous play. Then, for every player i and every integer T ≥ 1, (T )
Regi
√ ≤ 96 n (2 + log d).
The algorithm is deterministic, uses only the player’s own past observations, and does not require knowledge of the horizon. Proof. By the potential certificate in Lemma 4.1, for every action a, (T +1)
c + ηUi
(T +1)
[a] ≤ Ψi (ηUi
) ≤ 4c.
Hence, (T )
η Regi
(T +1)
= η max Ui a
[a] ≤ 3c,
√ where we used (2.4). Substituting η = 1/(32 n) and c = 2 + log d gives (T )
Regi
√ ≤ 96 n (2 + log d). (t)
(t−1)
The response on round t depends only on Ui , ui , and the fixed public parameters, so it is deterministic, uncoupled, and independent of T . If |Ai | = 1, the unique action is always played and (t) ui = 0 on every round. √ The factor 2 + log d comes from the potential scale c, while the n dependence comes from the √ choice η = 1/(32 n).
33
4.7
The Equilibrium Guarantee
The individual regret bound immediately yields the corresponding coarse-correlated-equilibrium guarantee for the average distribution of play. Corollary 2.5 (CCE). Under the assumptions of Theorem 4.10, the distribution T
σ (T ) =
n
1 X O (t) xj T t=1 j=1
√ is a 96 n (2 + log d)/T -coarse correlated equilibrium. Hence, no player can improve its expected √ utility by more than 96 n (2 + log d)/T by committing to any fixed action. This completes the fixed-game self-play analysis. For arbitrary utility sequences, the potentiallevel RVU inequality remains valid, but the fixed-game prediction-error bound from Lemma 4.8 no longer applies. The separate adversarial guarantee obtained through the learning-rate safeguard is proved in Section E.
5
Conclusion
√ We introduced MORM, an uncoupled one-step optimistic learning rule with O( n log d) individual regret in finite general-sum self-play. Several questions remain open. The most basic is whether the √ n dependence is optimal. More generally, sharp lower bounds for uncoupled learning in general games are largely missing. It is also natural to ask whether horizon-independent individual regret is possible under substantially weaker feedback, such as bandit or noisy utility observations. Finally, it would be interesting to understand whether one-step multiplicative optimism can simultaneously yield constant regret and stronger last-iterate convergence guarantees in structured classes of games.
Acknowledgments The authors thank Gabriele Farina for insightful discussions on regret matching and multiplicative optimism, and especially for pointing out the connection in Remark 2.1 between our construction under entropic geometry and Optimistic Multiplicative Weights Update.
References Omar Abbadi, Rida Laraki, and Panayotis Mertikopoulos. Constant regret in general games via higher-order optimism. arXiv preprint arXiv:2609.04113, 2026. Jacob Abernethy, Peter L Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, 2011. Mete Şeref Ahunbay. First-order (coarse) correlated equilibria in non-concave games. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026. Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with O(log T ) swap regret in multiplayer games. Advances in Neural Information Processing Systems, 2022a.
34
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. In International Conference on Machine Learning, 2022b. Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of computing, 8(1):121–164, 2012. Robert J Aumann. Subjectivity and correlation in randomized strategies. Journal of mathematical Economics, 1(1):67–96, 1974. David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):1–8, 1956. doi: 10.2140/pjm.1956.6.1. Avrim Blum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research, 8(6), 2007. Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold’em poker is solved. Science, 347(6218):145–149, 2015. Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418–424, 2018. Noam Brown and Tuomas Sandholm. Solving imperfect-information games via discounted regret minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019a. Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885–890, 2019b. Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. Proximal regret and proximal correlated equilibria: A new tractable solution concept for online learning and games. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026. Nicolo Cesa-Bianchi and Gábor Lugosi. Potential-based algorithms in on-line prediction and game theory. Machine Learning, 51(3):239–261, 2003. Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press Cambridge, 2006. Xi Chen and Xiaotie Deng. Settling the complexity of two-player Nash equilibrium. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 261–270, 2006. Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 2020. Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory, 2012. Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Ratepreserving reductions for blackwell approachability. In Proceedings of Thirty Eighth Conference on Learning Theory, 2025. Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. Communications of the ACM, 52(2):89–97, 2009. 35
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 235–254. SIAM, 2011. Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 2021. Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021. Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning dynamics for general convex games. Advances in Neural Information Processing Systems, 2022. Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, and Haipeng Luo. Regret matching+ : (In)stability and fast convergence in games. In Advances in Neural Information Processing Systems, 2023. Dean P Foster and Rakesh V Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21(589):40–55, 1997. Dylan J. Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Éva Tardos. Learning in games: Robustness of fast convergence. In Advances in Neural Information Processing Systems, 2016. Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119–139, 1997. Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79–103, 1999. Drew Fudenberg and David K Levine. The theory of learning in games, volume 2. MIT press, 1998. Claudio Gentile. The robustness of the p-norm algorithms. Machine Learning, 53(3):265–299, 2003. James Hannan. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3(2):97–139, 1957. Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127–1150, 2000. Sergiu Hart and Andreu Mas-Colell. A general class of adaptive strategies. Journal of Economic Theory, 98(1):26–54, 2001. Sergiu Hart and Andreu Mas-Colell. Uncoupled dynamics do not lead to nash equilibrium. American Economic Review, 93(5):1830–1836, 2003. Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning. Advances in Neural Information Processing Systems, 2017. Mingyang Liu, Gabriele Farina, and Asuman Ozdaglar. Constant individual regret in general games. arXiv preprint arXiv:2608.31166, 2026. 36
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations, 2019. Jason Milionis, Christos Papadimitriou, Georgios Piliouras, and Kelly Spendlove. An impossibility theorem in game dynamics. Proceedings of the National Academy of Sciences, 120(41):e2305349120, 2023. Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisỳ, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508–513, 2017. Hervé Moulin and J-P Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3):201–221, 1978. John F Nash. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48–49, 1950. Vianney Perchet. Approachability, regret and calibration: Implications and equivalences. Journal of Dynamics and Games, 1(2):181–254, 2014. Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Beyond time-average convergence: Nearoptimal uncoupled online learning via clairvoyant multiplicative weights update. Advances in Neural Information Processing Systems, 2022. Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, 2013a. Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 2013b. Julia Robinson. An iterative method of solving a game. Annals of Mathematics, 54(2):296–301, 1951. Tim Roughgarden. Intrinsic robustness of the price of anarchy. Journal of the ACM (JACM), 62(5): 1–42, 2015. Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107–194, 2012. Yoav Shoham and Kevin Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, USA, 2008. ISBN 0521899435. David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354–359, 2017. Ashkan Soleymani, Georgios Piliouras, and Gabriele Farina. Cautious optimism: A meta-algorithm for near-constant regret in general games. In Proceedings of the 26th ACM Conference on Economics and Computation, 2025a. Ashkan Soleymani, Georgios Piliouras, and Gabriele Farina. Faster rates for no-regret learning in general games via cautious optimism. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025b. 37
Ashkan Soleymani, Gabriele Farina, and Patrick Jaillet. Exact-form regret for gradient descent, mirror descent and follow-the-regularized-leader. arXiv preprint arXiv:2609.09466, 2026. Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 2015. Taira Tsuchiya. Sublogarithmic swap regret in multiplayer general-sum games via hybrid regularization. arXiv preprint arXiv:2608.04149, 2026. Brian Hu Zhang, Ioannis Anagnostides, and Tuomas Sandholm. Scale-invariant regret matching and online learning with optimal convergence: Bridging theory and practice in zero-sum games. arXiv preprint arXiv:2510.04407, 2025. Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. Advances in neural information processing systems, 2007.
38
A
Related Work
The study of learning in games has developed through several closely related viewpoints. Fictitious play uses past play to predict an opponent’s future behavior, while no-regret learning evaluates a player’s cumulative performance against fixed actions in hindsight [Robinson, 1951, Hannan, 1957, Fudenberg and Levine, 1998]. Blackwell approachability gives a geometric way to study repeated vector-payoff problems [Blackwell, 1956]. Abernethy et al. [2011] establish reductions between approachability and no-regret learning, while Perchet [2014] develops further connections with calibration. These links make cumulative advantage vectors and their potentials natural objects in the analysis of learning in games. Recent work strengthens this connection by giving reductions that preserve quantitative convergence rates, so bounds proved in one formulation can be transferred to another without losing their dependence on the horizon and problem parameters [Dann et al., 2025]. The notion of regret determines which equilibrium deviations are controlled. Correlated equilibrium, introduced by Aumann [1974], allows a player to condition its deviation on the action it is recommended. Calibration and stronger notions of regret, such as internal and swap regret, provide learning procedures for this equilibrium concept [Foster and Vohra, 1997, Hart and Mas-Colell, 2000]. External regret controls only deviations to a fixed action chosen independently of the recommendation, and therefore leads to coarse correlated equilibrium [Moulin and Vial, 1978, Blum and Mansour, 2007]. Our results concern external regret and CCE. Multiplicative weights provides a particularly clear bridge between learning and computation. In zero-sum games, adaptive multiplicative updates can be used to compute approximate equilibria [Freund and Schapire, 1999], while closely related ideas also underlie boosting and a broad range of optimization methods [Freund and Schapire, 1997, Arora et al., 2012]. The possibility of learning faster in self-play than against an arbitrary sequence was already studied in zero-sum games [Daskalakis et al., 2011]. General games are more delicate because there is no common saddle-point objective whose decrease simultaneously controls every player. Each player must instead obtain its own regret guarantee from its own observations. Our analysis reflects this separation. We maintain a nonnegative potential for each player and combine the resulting playerwise inequalities directly, without reducing the game to a single global optimization problem. Prediction-sensitive regret bounds provide another important ingredient. Chiang et al. [2012] show that regret can improve when consecutive loss functions vary gradually, while Rakhlin and Sridharan [2013a,b] develop optimistic online learning around a prediction available before the next observation. The prediction need not be the previous utility vector; what matters in the regret bound is how accurately it predicts the realized sequence. Related optimistic methods also exploit predictability in saddle-point problems. For example, Mertikopoulos et al. [2019] study optimistic mirror descent with an extra-gradient step, which queries the gradient again at an intermediate point before forming the next iterate. Such oracle access is different from the simultaneous uncoupled setting considered here, where a player chooses its strategy before observing the current utility vector. Syrgkanis et al. [2015] connect recency-biased regularized learning to faster rates in general games through RVU inequalities. Their bounds couple utility variation with a negative strategy-movement term. This coupling is especially useful in self-play because one player’s movement determines how much the utility vectors of the other players can change. A related but distinct line of work studies what no-regret dynamics imply for welfare. Under suitable smoothness conditions, welfare guarantees extend from equilibrium to no-regret outcomes [Roughgarden, 2015]. Foster et al. [2016] obtain faster convergence results using approximate regret, where the comparison with a fixed action is relaxed multiplicatively. The regret-matching line takes a different starting point from regularized learning on the strategy 39
simplex. Regret matching builds the response directly from actionwise cumulative regret [Hart and Mas-Colell, 2001], while potential-based analyses relate the evolution of these cumulative quantities to regret guarantees [Cesa-Bianchi and Lugosi, 2003]. This viewpoint also underlies counterfactual regret minimization, which decomposes regret in extensive-form games into local regret-minimization problems [Zinkevich et al., 2007]. Several later variants improve practical performance by giving recent observations more influence, including discounted regret minimization and predictive regret matching [Brown and Sandholm, 2019a, Farina et al., 2021]. These two forms of recency are conceptually different. Discounting changes the contribution of past observations to the accumulated regret, whereas predictive methods retain the accumulated history and use recent information to anticipate the next update. MORM follows the latter principle. Its cumulative centered-utility vector keeps every past observation with its original weight, while the preceding centered utility enters separately through the multiplicative optimistic correction. Predictive Blackwell approachability provides a useful point of comparison. Farina et al. [2021] connect regret matching and regret matching+ with FTRL and mirror descent through an approachability formulation, and derive predictive variants from this connection. In those methods, the prediction enters additively by shifting the cumulative regret before the response is computed. MORM uses the previous observation in a different way. The cumulative state is left unchanged, and the prediction instead modifies the action weights multiplicatively before normalization. This choice is closely tied to our potential-based analysis. We construct the potential so that the effect of the optimistic correction, the curvature of the potential, and the resulting strategy movement can all be controlled within the same argument. In this sense, multiplicative optimism and the potential are designed together. Normalization introduces another difficulty. A collection of positive action weights can change only slightly in absolute terms while the normalized strategy changes substantially, especially when the total weight becomes small. This issue also appears in regret-matching dynamics. Farina et al. [2023] identify instability in regret matching+ and its predictive variant and study modifications that restore stability, while Zhang et al. [2025] develop scale-invariant predictive regret matching with optimal average convergence in zero-sum games and extensions to other structured settings. For our analysis, stability must hold even when some action weights become very small. We therefore construct the potential so that the relative sensitivity of these weights decreases together with their total mass. This allows normalization to preserve the movement control needed in the regret analysis without resetting or discounting the cumulative state. Lifted regularization offers another route to individual regret. LRL-OFTRL achieves logarithmic regret in general convex games by using a nonnegative regret formulation and logarithmic regularization [Farina et al., 2022]. Cautious Optimism interprets acceleration through dynamic pacing and introduces intrinsic Lipschitzness to relate regularizer variation to the geometry of its divergence [Soleymani et al., 2025a]. Its diverse-self-play and convex-game guarantees have broader scope than our guarantees. We instead construct one specific potential to improve the joint dependence on n, d, and T . A player’s ordinary regret may remain negative throughout our proof. The positive quantity that survives summation in our proof is its potential. The order of a prediction and the order of an analysis are distinct. Chen and Peng [2020] improve Optimistic Hedge in two-player games, and Daskalakis et al. [2021] prove a multiplayer polylogarithmic bound by analyzing higher-order discrete differences of the trajectory. Their algorithm still uses a one-step predictor. ECHO-OFTRL and HOOD instead incorporate higher-order filtered predictions into the updates themselves [Liu et al., 2026, Abbadi et al., 2026]. Our comparison therefore concerns both the observed rates and the mechanisms used to obtain them. The temporal error in our proof (t) (t−1) is only ui − ui . The additional control comes from the potential and the Hellinger comparison.
40
The dependence on the number of players is similarly tied to the specific comparison used in the proof. Standard game-level ℓ1 estimates can introduce two factors of order n after squaring and summing, as in RVU and path-length analyses [Syrgkanis et al., 2015, Anagnostides et al., 2022b,a, Farina et al., 2022, 2021]. Those estimates do not prove that linear player dependence is necessary for every learning rule. Our potential controls squared Hellinger movement, whose product inequality √ avoids one of the two factors that leads to n improvement. Several nearby results obtain fast convergence under a different protocol or for a different notion of regret. Clairvoyant MWU [Piliouras et al., 2022] starts from an implicit update in which the next strategy is evaluated against the next strategy profile itself. Its uncoupled implementation recovers a bounded-regret guarantee on a sparse subsequence of the realized play, leading to fast convergence to CCE. This is a different guarantee from ordinary external regret on the full sequence of simultaneous rounds considered here. A separate line of work strengthens the class of deviations against which the learner competes. Anagnostides et al. [2022a] obtain O(log T ) swap regret in multiplayer games using optimistic regularized learning and self-concordant barriers. Their analysis controls a second-order path √ length of the dynamics and also retains an O( T ) adversarial guarantee. More recently, Tsuchiya [2026] obtain sublogarithmic swap regret by combining entropy and log-barrier regularization with a sensitivity bound for the stationary distributions arising in the swap-regret reduction. These guarantees imply convergence to correlated equilibrium, which controls a richer class of deviations than the CCE guarantee associated with external regret. Recent work has also explored intermediate deviation classes between external and swap regret. Ahunbay [2026] study first-order equilibrium notions in smooth games and characterize the continuous strategy modifications controlled by projected gradient ascent through tangent gradient fields. In normal-form games, these guarantees include deviation classes richer than external regret and lead to refinements such as semicoarse correlated equilibrium. Cai et al. [2026] introduce proximal regret, which lies strictly between external and swap regret, and show that ordinary gradient descent already achieves sublinear proximal regret. The resulting proximal correlated equilibria form a refinement of CCE. Soleymani et al. [2026] give a broader geometric characterization for mirror descent, and FTRL. Their exact-form framework identifies the deviation classes controlled by each method through the geometry of the corresponding update, with proximal deviations appearing as a special case. Finally, fast self-play is useful as an individual learning prescription only if a player also has protection when its opponents behave differently. Adaptive wrappers already appear in fast optimistic learning [Syrgkanis et al., 2015, Daskalakis et al., 2021]. HOOD also provides an adversarial extension that permanently switches to another learner after a threshold violation [Abbadi et al., 2026, Appendix D]. Our distinction is the rate-only safeguard. A violation of the potential threshold decreases only the scalar learning rate. No cumulative observation is reset, and the update remains within the same algorithm albeit with a smaller learning rate. The threshold is never violated in the self-play, so the protected rule preserves every iterate of the constant-regret trajectory in the self-play.
B
Potential Geometry and the Taylor Bound
This appendix proves the analytic properties of the potential used in Section 4.1. We proceed from the scalar function to the geometry of the aggregated potential, then to multiplicative stability and the finite-step Taylor bound. Throughout the proofs, once a player i is fixed, we suppress its index on Ψi and on the game vectors. All sums over actions are over Ai . The vector U denotes an arbitrary input to the potential;
41
along the learning trajectory, this input is ηU (t) .
B.1
Scalar Properties, Derivatives, and Curvature
Lemma 4.1. Fix a player i and let c = 2 + log d. The potential Ψi is convex and continuously differentiable on R|Ai | , with locally Lipschitz gradient. For every U , Ψi (0) = c|Ai |1/(c−1) < 3c,
Ψi (U ) > 0,
Ψi (U ) ≥ c + max U [a]. a
Moreover, ∂a Ψi (U ) =
Ψi (U ) c
2−c ac (U [a]) > 0,
X
∂a Ψi (U ) ≤ 3.
a
Where the Hessian exists, 0 ⪯ ∇2 Ψi (U ) ⪯ diag ∂a Ψi (U ) . The same directional second-derivative bound holds almost everywhere along every line segment. Proof. Scalar properties. Recall that ( (1 − z)−1 , z ≤ 0, f (z) = 1 + z, z ≥ 0,
( (1 − z)−2 , z ≤ 0, f (z) = 1, z ≥ 0. ′
The two branches agree in value and first derivative at zero. Hence, f is positive and continuously differentiable, with 0 < f ′ (z) ≤ 1. Away from zero, ( 2(1 − z)−3 , z < 0, ′′ f (z) = 0, z > 0. Thus, f is convex and f ′ is globally 2-Lipschitz. We will use the identity f ′ (z) = min{f (z)2 , 1}. We will also use the lower bound f (z) ≥ 1 + z. It is immediate for z ≥ 0, while for z ≤ 0, f (z) − (1 + z) =
z2 ≥ 0. 1−z
Convexity and the potential certificate. Since c−1 > 1, the ℓc−1 norm is convex and coordinatewise nondecreasing on the nonnegative orthant. For 0 ≤ α ≤ 1, convexity of f gives, coordinatewise, αU [a] + (1 − α)V [a] U [a] V [a] f ≤ αf + (1 − α)f . c c c Monotonicity and convexity of the norm therefore imply Ψ(αU + (1 − α)V ) ≤ αΨ(U ) + (1 − α)Ψ(V ), so Ψ is convex.
42
Since the norm dominates each of its coordinates, for every action a, U [a] ≥ c + U [a]. Ψ(U ) ≥ cf c Taking the maximum over a gives the stated lower bound. Moreover, f (0) = 1, so Ψ(0) = c|Ai |1/(c−1) . Since |Ai | ≤ d and c − 1 = 1 + log d, 1/(c−1)
|Ai |
1/(1+log d)
≤d
log d < e < 3. = exp 1 + log d
Hence Ψ(0) < 3c. Positivity follows immediately from f > 0. Gradient and total derivative mass. Direct differentiation of the potential gives ∂a Ψ(U ) =
Ψ(U ) c
2−c U [a] c−2 ′ U [a] f f . c c
Using f ′ (z) = min{f (z)2 , 1}, the action-dependent factor is −c 1 − U [a] , U [a] ≤ 0, c c−2 1 + U [a] , U [a] ≥ 0. c This is exactly ac (U [a]), and therefore ∂a Ψ(U ) =
Ψ(U ) c
2−c ac (U [a]) > 0.
To bound the total derivative mass, use f ′ ≤ 1 and Hölder’s inequality, X U [a] c−2 f ≤ c a
!(c−2)/(c−1) X U [a] c−1 |Ai |1/(c−1) . f c a
Since the power of the sum equals (Ψ(U )/c)c−2 , we obtain X ∂a Ψ(U ) ≤ |Ai |1/(c−1) < 3. a
Weighted curvature. For z ̸= 0, a′c (z) = ac (z)
( (1 − z/c)−1 , z < 0, (c − 2)/(c + z), z > 0.
Both branches belong to [0, 1]. At an input with no zero coordinates, differentiating the gradient formula gives a′ (U [a]) c−2 ∂b ∂a Ψ(U ) = 1{a=b} ∂a Ψ(U ) c − ∂a Ψ(U )∂b Ψ(U ). ac (U [a]) Ψ(U ) 43
Equivalently, c−2 a′c (U [a]) − ∇ Ψ(U ) = diag ∂a Ψ(U ) ∇Ψ(U )∇Ψ(U )⊤ . ac (U [a]) Ψ(U ) 2
The second term is positive semidefinite before subtraction. Hence, for every v, X a′ (U [a]) ∂a Ψ(U ) c ∂a Ψ(U )v[a]2 . v[a]2 ≤ a (U [a]) c a a
X
v ⊤ ∇2 Ψ(U )v ≤
Since Ψ is convex, its Hessian is positive semidefinite wherever it exists. This proves 0 ⪯ ∇2 Ψ(U ) ⪯ diag ∂a Ψ(U ) at every point where the Hessian exists. Regularity at zero coordinates. It remains to justify the regularity needed when a coordinate crosses the junction at zero. The scalar function f is continuously differentiable with Lipschitz derivative. On every compact set of inputs, the values f (U [a]/c) are uniformly bounded away from zero. Since the ℓc−1 norm is smooth on the strictly positive orthant, the gradient formula above is locally Lipschitz on all of R|Ai | . Now fix a line U + sv. Every nonconstant coordinate crosses zero at most once. Away from these finitely many crossing points, the Hessian exists and the preceding quadratic-form bound applies. A coordinate that is identically zero has v[a] = 0 and does not contribute to the directional second derivative. Thus, almost everywhere along the line, 0≤
X d2 Ψ(U + sv) ≤ ∂a Ψ(U + sv)v[a]2 . 2 ds a
Finally, local Lipschitz continuity of ∇Ψ makes the first derivative along the line absolutely continuous on compact intervals, so this bound can be integrated across the zero crossings. No Hessian value at a crossing is required.
B.2
Multiplicative Stability
We next prove the multiplicative stability bounds used in the Taylor and movement analyses. The first controls the gradient coordinates under a finite change of the potential input. The second transfers this control to the normalized probabilities of MORM. Lemma 4.2 (Multiplicative stability). For every U , u ∈ R|Ai | , every η > 0, and every action a ∈ Ai , log
∂a Ψi (U + ηu) ≤ 2η ∥u∥∞ . ∂a Ψi (U )
For MORM with a fixed rate 0 < η ≤ 1/16 and any sequence of utility vectors in [0, 1]|Ai | observed after play, (t+1)
log
xi
[a]
(t) xi [a]
(t+1)
In particular, if η ≤ 1/32, then xi
(t)
≤ 2η ui
∞
+
(t)
8η (t) (t−1) ui − u i . 1 − 4η ∞
[a]/xi [a] ∈ [1/2, 2] for every action a. 44
Proof. We first prove (4.1). By (3.8), the logarithmic derivative of ac has absolute value at most one on both open branches. Since the branches of log ac agree at zero, log ac is globally 1-Lipschitz. Hence, ac (U [a] + ηu[a]) ≤ η|u[a]|. ac (U [a])
log
From the scalar formulas in the preceding subsection, 0 < f ′ (z)/f (z) ≤ 1. Thus, for every action a, −η∥u∥∞ /c
e
U [a] f c
U [a] + ηu[a] ≤f c
η∥u∥∞ /c
≤e
U [a] f c
.
Applying the coordinatewise monotonicity and homogeneity of the ℓc−1 norm gives log
Ψ(U + ηu) η ≤ ∥u∥∞ . Ψ(U ) c
Using the gradient factorization, log
∂a Ψ(U + ηu) Ψ(U + ηu) ac (U [a] + ηu[a]) = (2 − c) log + log . ∂a Ψ(U ) Ψ(U ) ac (U [a])
Therefore, ∂a Ψ(U + ηu) ≤ log ∂a Ψ(U )
c−2 + 1 η ∥u∥∞ ≤ 2η ∥u∥∞ , c
which proves (4.1). We next prove the probability-ratio bound. Let qt [a] := ac (ηU (t) [a]) 1 + 4ηu(t−1) [a] denote the unnormalized weight on round t. Since u(t−1) ∞ ≤ 1 and η ≤ 1/16, all correction factors are positive. The cumulative update U (t+1) = U (t) + u(t) and the Lipschitz bound for log ac give log
ac (ηU (t+1) [a]) ≤ η u(t) . ∞ ac (ηU (t) [a])
Moreover, the derivative of s 7→ log(1 + 4ηs) on [−1, 1] is at most 4η/(1 − 4η), so log
1 + 4ηu(t) [a] 4η ≤ u(t) − u(t−1) . (t−1) 1 − 4η ∞ 1 + 4ηu [a]
Hence, if Bt = η u(t)
∞
+
4η u(t) − u(t−1) , 1 − 4η ∞
then every unnormalized weight satisfies e−Bt ≤
qt+1 [a] ≤ eBt . qt [a] 45
Let Qt =
P
a qt [a]. Since
Qt+1 X (t) qt+1 [a] x [a] = , Qt qt [a] a the normalization ratio also belongs to [e−Bt , eBt ]. Consequently, log
x(t+1) [a] ≤ 2Bt , x(t) [a]
which is exactly (4.2). Finally, if η ≤ 1/32, then u(t) ∞ ≤ 1 and u(t) − u(t−1) ∞ ≤ 2. Thus, 2Bt ≤ 2η +
16η 1 4 71 ≤ + = < log 2. 1 − 4η 16 7 112
Exponentiating gives x(t+1) [a]/x(t) [a] ∈ [1/2, 2] for every action a.
B.3
The Finite-step Taylor Estimate
We now combine the weighted curvature bound with multiplicative stability to obtain the finite-step Taylor estimate used in the main analysis. Lemma 4.3. For every U , u ∈ R|Ai | with ∥u∥∞ ≤ 1 and every 0 < η ≤ 1/8, Ψi (U + ηu) − Ψi (U ) ≤ η ⟨∇Ψi (U ), u⟩ +
2η 2 X ∂a Ψi (U )u[a]2 . 3 a
Proof. Consider the segment from U to U + ηu, parameterized by U + θηu for 0 ≤ θ ≤ 1. By the chain rule, d Ψ(U + θηu) = η ⟨∇Ψ(U + θηu), u⟩ . dθ Where the Hessian exists, differentiating once more gives d2 Ψ(U + θηu) = η 2 u⊤ ∇2 Ψ(U + θηu)u. dθ2 The weighted curvature bound from Lemma 4.1 therefore implies, almost everywhere along the segment, X d2 2 Ψ(U + θηu) ≤ η ∂a Ψ(U + θηu)u[a]2 . dθ2 a At this point the weights are evaluated at the intermediate input U + θηu, whereas the desired Taylor bound uses the weights at the initial input U . This is where multiplicative stability enters. By (4.1), 4 ∂a Ψ(U + θηu) ≤ e2θη∥u∥∞ ∂a Ψ(U ) ≤ ∂a Ψ(U ), 3
46
0 ≤ θ ≤ 1,
(B.1)
where the last inequality follows from ∥u∥∞ ≤ 1, η ≤ 1/8, and e1/4 < 4/3. Hence, throughout the segment, d2 4η 2 X ∂a Ψ(U )u[a]2 Ψ(U + θηu) ≤ dθ2 3 a almost everywhere. We now integrate this second-order bound along the segment. The integral form of Taylor’s theorem gives Z 1 d2 Ψ(U + ηu) − Ψ(U ) − η ⟨∇Ψ(U ), u⟩ = (1 − θ) 2 Ψ(U + θηu) dθ. dθ 0 R1 Using the preceding bound and 0 (1 − θ) dθ = 1/2, we obtain Ψ(U + ηu) − Ψ(U ) − η ⟨∇Ψ(U ), u⟩ ≤
2η 2 X ∂a Ψ(U )u[a]2 . 3 a
Rearranging proves the lemma. The argument remains valid when the segment crosses zero coordinates. Indeed, Lemma 4.1 shows that the first derivative along the segment is absolutely continuous and that the weighted second-derivative bound holds almost everywhere, which is sufficient for the integral Taylor formula above. Taking U = ηU (t) and u = u(t) gives the Taylor estimate used in the round-by-round analysis.
C
Stability of the Normalized Response
This appendix proves the response-stability estimates used in Section 4.3. We first establish (3.10), P which relates the total derivative mass a ∂a Ψ(U ) to the logarithmic sensitivity of the power weights ac (U [a]). We then derive a differentiation identity for normalized responses and apply it to the two changes between consecutive rounds. One path changes the optimistic correction while keeping the cumulative input fixed, and the other changes the cumulative input while keeping the correction fixed. The two paths meet at the intermediate distribution used in the proof of Lemma 4.6. Fix a player i and suppress its index throughout the proofs. All sums over actions are over Ai , and square roots of probability vectors are taken coordinatewise. In the path arguments below, θ ∈ [0, 1] parametrizes an interpolation between two responses.
C.1
Compensation for Normalization
In Section 3.4.1, the negative branch of f was chosen so that the squared relative sensitivity of a small weight decreases together P with the weight itself. After aggregation, normalization depends on the total derivative mass a ∂a Ψ(U ). We now prove the corresponding relation for the gradient weights of Ψ and the power weights ac . Lemma C.1. For every input U ∈ R|Ai | , ( ) 1 Ψ(U ) 2 ∂a Ψ(U ) ≥ min ,1 . 3 c a
X
47
(C.1)
For each action a with U [a] ̸= 0, ( ) ′ ac (U [a]) 2 Ψ(U ) 2 ≤ min ,1 . ac (U [a]) c
(C.2)
Consequently, a′c (U [a])/ac (U [a]) P b ∂b Ψ(U )
2 ≤3
where the derivatives exist.
Proof. We first lower bound the total derivative mass. Since the ℓc−1 norm defining Ψ dominates each coordinate, Ψ(U ) U [a] ≤ 0<f c c for every action a. Using the derivative formula from Lemma 4.1 together with f ′ (z) = min{f (z)2 , 1} gives ( ) X Ψ(U ) 2−c X U [a] c−2 U [a] 2 ∂a Ψ(U ) = f min f ,1 . c c c a a The coordinatewise bound above implies ) ( ( ) U [a] 2 Ψ(U ) −2 U [a] 2 . ,1 ≥ f min 1, min f c c c To see this, if Ψ(U )/c ≤ 1, then f (U [a]/c) ≤ 1, and the two sides are equal. If Ψ(U )/c > 1, the right-hand side equals f (U [a]/c)2 , (Ψ(U )/c)2 which is at most both f (U [a]/c)2 and 1. Substituting this bound into the derivative sum yields ( ) X Ψ(U ) −2 X U [a] c Ψ(U ) 2−c min 1, f . ∂a Ψ(U ) ≥ c c c a a It remains to lower bound the final sum. Hölder’s inequality gives X U [a] c−1 f ≤ c a
!(c−1)/c X U [a] c f |Ai |1/c . c a
The left-hand side equals (Ψ(U )/c)c−1 . Raising the inequality to the power c/(c − 1) and rearranging therefore gives c X U [a] c −1/(c−1) Ψ(U ) f ≥ |Ai | . c c a 48
Combining the last two inequalities and simplifying the powers gives ( ) X Ψ(U ) 2 −1/(c−1) ∂a Ψ(U ) ≥ |Ai | min ,1 . c a Since |Ai |1/(c−1) < 3, this proves (C.1). We next bound the logarithmic sensitivity of ac . If U [a] < 0, then a′c (U [a]) = ac (U [a])
U [a] −1 U [a] . 1− =f c c
On this branch, f (U [a]/c) ≤ 1, while the coordinate bound above gives f (U [a]/c) ≤ Ψ(U )/c. Hence, ( ) ′ ac (U [a]) 2 Ψ(U ) 2 ≤ min ,1 . ac (U [a]) c If U [a] > 0, then f (U [a]/c) > 1, which implies Ψ(U )/c > 1. Moreover, 0≤
c−2 a′c (U [a]) = ≤ 1. ac (U [a]) c + U [a]
Since the minimum in (C.2) is now equal to one, the same bound follows on the positive branch. Finally, dividing (C.2) by (C.1) cancels the common factor ( ) Ψ(U ) 2 min ,1 c and gives precisely the compensation bound (3.10). At a coordinate with U [a] = 0, the two one-sided logarithmic derivatives of ac may differ, but both satisfy the sensitivity bound above. Along any affine path used below, a nonconstant coordinate crosses zero at most once, while a coordinate that remains zero has zero rate of change. Consequently, (3.10) holds almost everywhere along each path, which is sufficient for the integrations below.
C.2
Normalized Paths and Square-root Movement
We next relate the change of a normalized response to the derivatives of its action weights along a path. The key identity expresses the squared speed of the square-root probabilities as a variance of logarithmic derivatives. Integrating this speed then bounds the squared movement between the endpoints of the path. Lemma C.2. Let x(θ), 0 ≤ θ ≤ 1, be a Lipschitz path of strictly positive probability vectors on Ai . Then, for almost every θ, 2 2 dp 1X d 1 d x(θ)[a] log x(θ)[a] = Vara∼x(θ) log x(θ)[a] . (C.3) x(θ) = dθ 4 a dθ 4 dθ 2 Moreover, Z 1 p p 2 x(1) − x(0) ≤ 2
0
49
2 dp x(θ) dθ. dθ 2
(C.4)
Proof. Since every coordinate of x(θ) is continuous and strictly positive on [0, 1], it is bounded away from zero along this fixed path. Thus, the coordinatewise logarithms and square roots are absolutely continuous, and the following derivatives exist almost everywhere. For each action a, the chain rule gives dp 1p d x(θ)[a] = x(θ)[a] log x(θ)[a]. dθ 2 dθ Squaring and summing over actions gives 2 dp 1X x(θ) = x(θ)[a] dθ 4 a 2
d log x(θ)[a] dθ
2 .
The logarithmic derivatives have mean zero under x(θ). Indeed, X
x(θ)[a]
a
X d d X d log x(θ)[a] = x(θ)[a] = x(θ)[a] = 0. dθ dθ dθ a a
Their second moment is therefore equal to their variance, which proves (C.3). To compare the endpoints, absolute continuity gives Z 1 p p p d x(1) − x(0) = x(θ) dθ. 0 dθ The triangle inequality followed by Cauchy–Schwarz yields p p x(1) − x(0)
Z 1 2
≤ 0
dp x(θ) dθ ≤ dθ 2
Z 1 0
2 dp x(θ) dθ dθ 2
!1/2 .
Squaring proves (C.4). We will apply the lemma to normalized positive action weights. Suppose qa (θ) x(θ)[a] = P , b qb (θ)
qa (θ) > 0.
Differentiating the logarithm gives X d d d log x(θ)[a] = log qa (θ) − x(θ)[b] log qb (θ). dθ dθ dθ b
Thus, normalization subtracts the x(θ)-average logarithmic derivative from every action. Since subtracting a common scalar does not change variance, (C.3) becomes 2 dp 1 d x(θ) = Vara∼x(θ) log qa (θ) . dθ 4 dθ 2 The two path estimates below follow by substituting the corresponding unnormalized weights qa (θ) into this identity.
50
C.3
Changing the Optimistic Correction
We first compare x(t) with the intermediate distribution from the proof of Lemma 4.6. The cumulative input ηU (t) remains fixed, while the optimistic correction changes from u(t−1) to u(t) . Lemma C.3. Fix a round t and 0 < η ≤ 1/16. For 0 ≤ θ ≤ 1, let ac (ηU (t) [a]) 1 + 4η((1 − θ)u(t−1) [a] + θu(t) [a]) . x(θ)[a] = P (t) (t−1) [b] + θu(t) [b]) b ac (ηU [b]) 1 + 4η((1 − θ)u Then p p 2 2 . x(1) − x(0) ≤ 8η 2 u(t) − u(t−1) ∞
2
(C.5)
Proof. The path starts at x(0) = x(t) . At θ = 1, the cumulative input is still ηU (t) , while the correction has changed from u(t−1) to u(t) . Thus, x(1) is exactly the intermediate distribution used in the proof of Lemma 4.6. For every θ ∈ [0, 1], the interpolated correction satisfies (1 − θ)u(t−1) [a] + θu(t) [a] ≤ 1. Since η ≤ 1/16, 5 3 ≤ 1 + 4η (1 − θ)u(t−1) [a] + θu(t) [a] ≤ . 4 4 Hence all unnormalized weights remain strictly positive, and the path is Lipschitz. We now apply the normalized-path identity from Lemma C.2. The power weight ac (ηU (t) [a]) is constant along this path, so the logarithmic derivative of the unnormalized weight is 4η u(t) [a] − u(t−1) [a] . 1 + 4η (1 − θ)u(t−1) [a] + θu(t) [a] Using (C.3) and bounding the variance by its second moment gives 2 1X dp x(θ) ≤ x(θ)[a] dθ 4 a 2
!2 4η u(t) [a] − u(t−1) [a] . 1 + 4η (1 − θ)u(t−1) [a] + θu(t) [a]
The denominator is at least 3/4, so 2 2 dp 64η 2 x(θ) ≤ u(t) − u(t−1) . dθ 9 ∞ 2
Finally, (C.4) yields p p 2 2 2 64η 2 x(1) − x(0) ≤ u(t) − u(t−1) ≤ 8η 2 u(t) − u(t−1) . 9 2 ∞ ∞ This proves (C.5).
51
C.4
Changing the Cumulative Input
We next keep the optimistic correction fixed at u(t) and change the potential input from ηU (t) to ηU (t+1) . Our goal is to control the resulting strategy movement by the same gradient-weighted square that appears in (4.3). The compensation bound from Lemma C.1 is what preserves these gradient weights after normalization. Lemma C.4. Fix a round t and 0 < η ≤ 1/16. For 0 ≤ θ ≤ 1, let ac (ηU (t) [a] + θηu(t) [a])(1 + 4ηu(t) [a]) x(θ)[a] = P . (t) (t) (t) b ac (ηU [b] + θηu [b])(1 + 4ηu [b]) Then X p p 2 ∂a Ψ(ηU (t) )u(t) [a]2 . x(1) − x(0) ≤ 2η 2 2
(C.6)
a
Proof. The path starts at the intermediate distribution from the proof of Lemma 4.6, which uses the old cumulative input and the new correction. At the other endpoint, ηU (t) + ηu(t) = ηU (t+1) , so x(1) = x(t+1) . Since u(t) ∞ ≤ 1 and η ≤ 1/16, the fixed correction satisfies 3 5 ≤ 1 + 4ηu(t) [a] ≤ . 4 4 Thus all weights along the path are strictly positive. We apply the normalized-path identity from Lemma C.2. Away from zero crossings, the logarithmic derivative of the unnormalized weight of action a is a′ (ηU (t) [a] + θηu(t) [a]) ηu(t) [a] c . ac (ηU (t) [a] + θηu(t) [a]) Bounding the variance in (C.3) by its second moment therefore gives 2 dp η2 X x(θ) ≤ x(θ)[a] dθ 4 a 2
a′c (ηU (t) [a] + θηu(t) [a]) ac (ηU (t) [a] + θηu(t) [a])
!2 u(t) [a]2 .
We now compare the corrected probabilities with the normalized gradient coordinates. Using the bounds 3/4 and 5/4 on the correction, x(θ)[a] ≤
5 ac (ηU (t) [a] + θηu(t) [a]) P . 3 b ac (ηU (t) [b] + θηu(t) [b])
By the gradient formula in Lemma 4.1, the common factor in ∂a Ψ cancels under normalization. Hence, x(θ)[a] ≤
5 ∂a Ψ(ηU (t) + θηu(t) ) P . 3 b ∂b Ψ(ηU (t) + θηu(t) ) 52
Substituting this bound into the square-root speed gives 2 ′ (ηU (t) [a] + θηu(t) [a])/a (ηU (t) [a] + θηu(t) [a]) 2 a 5η 2 X dp c c P x(θ) ≤ ∂a Ψ(ηU (t) + θηu(t) ) u(t) [a]2 . (t) + θηu(t) ) dθ 12 a 2 b ∂b Ψ(ηU The ratio in each summand is exactly the quantity controlled by (3.10). Applying that bound yields 2 5η 2 X dp x(θ) ≤ ∂a Ψ(ηU (t) + θηu(t) )u(t) [a]2 . dθ 4 2 a
Integrating with (C.4) gives Z p p 2 5η 2 1 X x(1) − x(0) ≤ ∂a Ψ(ηU (t) + θηu(t) )u(t) [a]2 dθ. 4 0 a 2 Finally, (B.1) gives 4 ∂a Ψ(ηU (t) + θηu(t) ) ≤ ∂a Ψ(ηU (t) ), 3 because u(t) ∞ ≤ 1 and η ≤ 1/16. Therefore, X p p 2 5η 2 X ∂a Ψ(ηU (t) )u(t) [a]2 ≤ 2η 2 ∂a Ψ(ηU (t) )u(t) [a]2 . x(1) − x(0) ≤ 3 a 2 a This proves (C.6). The derivative calculations hold almost everywhere along the path. As noted after Lemma C.1, each nonconstant coordinate crosses zero at most once, so these exceptional points do not affect the integral.
C.5
Combining the Correction and Input Changes
The two paths from the preceding subsections meet at the same intermediate distribution. We now use this common endpoint to combine the correction-change and cumulative-input bounds and recover the strategy-movement estimate from the main analysis. Lemma 4.6. Suppose player i uses MORM with a fixed rate 0 < η ≤ 1/16 and receives any sequence of utility vectors in [0, 1]|Ai | after play. For every t ≥ 1, q
(t+1) xi −
q 2 X (t) (t) (t) (t) (t−1) 2 xi ≤ 4η 2 ∂a Ψi (ηUi )ui [a]2 + 16η 2 ui − ui . 2
∞
a
ei denote the intermediate distribution with probabilities Proof. Let x (t)
(t)
ac (ηUi [a])(1 + 4ηui [a]) ei [a] = P . x (t) (t) a (ηU [b])(1 + 4ηu [b]) c b i i (t)
ei . Hence, The correction path from Lemma C.3 starts at xi and ends at x p
q 2 (t) (t) (t−1) 2 ei − xi x ≤ 8η 2 ui − ui . ∞
2
53
(t+1)
ei . Since Ui The cumulative-input path from Lemma C.4 starts at x (t+1) xi . Therefore, q
(t+1)
xi
−
(t)
(t)
= Ui + ui , its endpoint is
2 X p (t) (t) ei ≤ 2η 2 x ∂a Ψi (ηUi )ui [a]2 . 2
a
The triangle inequality for the square-root vectors gives q q q q p p (t+1) (t) (t+1) (t) ei + ei − xi xi − xi ≤ xi − x x 2
2
. 2
Squaring and using (r + s)2 ≤ 2r2 + 2s2 , followed by the two bounds above, yields q
(t+1)
xi
−
q 2 X (t) (t) (t) (t−1) 2 (t) . ≤ 4η 2 ∂a Ψi (ηUi )ui [a]2 + 16η 2 ui − ui xi 2
∞
a
ei is used only to separate the two changes in This proves the lemma. The intermediate distribution x the response and is never played by the algorithm.
D
Hellinger Distance and Prediction Error
The proof of Lemma 4.8 uses two properties of the square-root distance underlying Hellinger distance. First, it controls changes in expectations of bounded functions. Second, for product distributions it factorizes nicely, i.e., its square is at most the sum of the squared distances between the factors. The second property is what avoids an additional factor in the number of opponents. We prove these two facts below. The game-specific application, including the effect of centering the utility vectors, is carried out in Section 4.5.
D.1
Hellinger Distance and Differences of Expectations
We first relate square-root distance to total variation. This immediately gives the expectation bounds used in the fixed-game analysis. Lemma D.1. Let x, x′ be probability vectors on the same finite action set. Then √ √ x − x′ 1 ≤ 2 x − x′ . 2
For a function g on this set with values in [−1, 1], |Ea∼x [g(a)] − Ea∼x′ [g(a)]| ≤ 2
√
x−
√
x′
2
.
If g takes values in [0, 1], the factor 2 can be replaced by 1. Proof. For each action, x[a] − x′ [a] =
p p p p x[a] − x′ [a] x[a] + x′ [a] .
Hence, by Cauchy–Schwarz, x − x′ 1 ≤
√
x−
√
54
x′
√ 2
√ x+
x′
2
.
(D.1)
Since
√
x 2=
√
x′
2
= 1, the triangle inequality gives √
√ x+
x′
2
≤ 2,
which proves (D.1). Notice that the argument also allows zero-probability coordinates. Now suppose g takes values in [−1, 1]. Then |Ea∼x [g(a)] − Ea∼x′ [g(a)]| =
X
(x[a] − x′ [a])g(a) ≤ x − x′ 1 .
a
Combining this with (D.1) gives the factorP2. If instead g takes values in [0, 1], then a (x[a] − x′ [a]) = 0, so subtracting 1/2 from g does not change the expectation difference. Therefore, X 1 1 ′ (x[a] − x [a]) g(a) − x − x′ 1 . |Ea∼x [g(a)] − Ea∼x′ [g(a)]| = ≤ 2 2 a Applying (D.1) once more gives the stated factor 1. The two versions of the expectation bound are both used in Lemma 4.8. The [−1, 1] bound controls changes in payoff differences caused by the opponents, while the [0, 1] bound controls the player’s centering term.
D.2
Hellinger Distance between Product Distributions
The second property concerns product distributions. The square-root overlap factors across independent coordinates, which allows the squared distance between two products to be controlled by the sum of the squared distances between their factors. Lemma D.2. Consider any finite collection of pairs xj , x′j of probability vectors, where each pair is defined on the same finite set Aj . Then 2
sO
xj −
j
sO
x′j
j
≤
X √
xj −
j
2
q 2 x′j . 2
(D.2)
All products and sums are over the same collection. The statement also holds for the empty collection, with both sides equal to zero. Proof. For each factor j, define its square-root overlap by Xq hj = xj [a]x′j [a]. a∈Aj
Cauchy–Schwarz gives 0 ≤ hj ≤ 1. Expanding the squared square-root distance gives √
xj −
q 2 x′j = 2(1 − hj ). 2
55
The corresponding overlap of the product distributions factors into the product of the individual overlaps. Indeed, Y X Yq xj [s[j]]x′j [s[j]] = hj . s∈
Q
j Aj
j
j
Therefore, 2
sO
xj −
sO
j
x′j
j
= 2 1 −
Y
hj .
j
2
It remains to compare the product overlap with the individual ones. Since every hj belongs to [0, 1], Y X 1− hj ≤ (1 − hj ). j
j
Q For example, this follows by expanding 1 − j hj successively and observing that every remaining product of overlaps is at most one. Multiplying by two gives Y X hj ≤ 2(1 − hj ), 2 1 − j
j
which is exactly (D.2). For the empty collection, both product distributions are the point mass on the empty profile, so both sides are zero. The two lemmas together give the comparison used in the fixed-game analysis. If g takes values in [−1, 1], then Es∼Nj xj [g(s)] − Es∼Nj x′j [g(s)] ≤ 2
X √
1/2 q 2 xj − x′j .
j
2
In Lemma 4.8, the factors are the opponents’ strategies and g(s−i ) = Ui (a, s−i ) − Ui (b, s−i ). Thus, the change in a payoff difference is controlled directly by the sum of the opponents’ squared Hellinger movements.
E
Adversarial Regret with a Learning-Rate Safeguard
We now establish the adversarial guarantee by adding a learning-rate safeguard to MORM. The potential, multiplicative correction, centered-utility update, and cumulative vector remain unchanged. Only the learning rate is allowed to decrease. The construction is inspired by the adaptive-step-size argument of Daskalakis et al. [2021, Appendix D], which monitors a condition satisfied under self-play and adjusts the learning rate when that condition fails. Here we monitor the potential bound obtained in the fixed-game analysis. If 56
the potential crosses the threshold 4c, we decrease the learning rate before the next round. There is no restart and no switch to a different learning rule. The analysis has two parts. For an arbitrary sequence of utility vectors, we show that the learning-rate adjustment keeps (t)
(t)
Ψi (ηi Ui ) ≤ 4c (t)
on every round. We then show that 1/(ηi )2 increases by at most 49/c per round, which prevents the learning rate from becoming too small. In fixed-game self-play, the potential never crosses the threshold, so the safeguard never changes the learning rate and the trajectory remains exactly the one analyzed in Section 4.
E.1
The Safeguarded Update
Fix a player i, set c = 2 + log d, and initialize (1)
Ui
(0)
= 0,
ui
(1)
= 0,
ηi
=
1 √ . 32 n
On round t, the player uses the current learning rate in both parts of the MORM response, (t) (t) (t) (t) (t−1) xi ∝ ∇Ψi (ηi Ui ) ⊙ 1 + 4ηi ui .
(E.1)
(t)
After observing νi , the player performs the same centering and cumulative updates as before, D E (t) (t) (t) (t) (t+1) (t) (t) 1, Ui = Ui + ui . ui = νi − xi , νi The safeguard is applied after this update. We measure the amount by which the potential, evaluated using the round-t learning rate, exceeds 4c, (t) (t) (t+1) δi = Ψi (ηi Ui ) − 4c + , and choose (t)
(t+1)
ηi
ηi
=
(t)
.
(E.2)
1 + δi /c
Thus the learning rate remains unchanged whenever the potential stays below 4c and decreases only after the threshold is crossed. (t) The potential defining δi uses the round-t rate and the cumulative vector after incorporating the round-t utility. Any rate decrease takes effect only on round t + 1.
E.2
The Adversarial Regret Bound
Theorem E.1 (Adversarial regret). Fix n ≥ 1, d ≥ 2, and a player i with 1 ≤ |Ai | ≤ d. With √ (1) c = 2 + log d and initial rate ηi = 1/(32 n), the rule (E.1)–(E.2) satisfies p √ (T ) Regi ≤ 96 n (2 + log d) + 21 T (2 + log d) (t)
for every sequence of utility vectors νi ∈ [0, 1]|Ai | observed in full after play and every integer T ≥ 1. The utility vectors may be chosen adaptively, with no assumption on the other players’ behavior. The rule is deterministic, uncoupled, and independent of the horizon. 57
(t)
Proof. Positivity of the learning rates and response weights. The excess δi at every finite time. Hence, (E.2) gives (t+1)
0 < ηi (t)
Moreover, centering gives ui
∞
is finite and nonnegative
1 1 √ ≤ . 32 32 n
(t)
≤ ηi ≤
≤ 1. Therefore every optimistic correction factor satisfies (t) (t−1)
1 + 4ηi ui
7 (t) [a] ≥ 1 − 4ηi ≥ . 8
Together with the positivity of the gradient coordinates from Lemma 4.1, this shows that the response is well defined on every round. Keeping the potential below the threshold. We first prove (t)
(t)
Ψi (ηi Ui ) ≤ 4c
for every t ≥ 1.
(E.3)
At t = 1, the input is zero and Lemma 4.1 gives Ψi (0) < 3c < 4c. (t) Suppose (E.3) holds at the beginning of round t. If δi = 0, then (t)
(t+1)
Ψi (ηi Ui
) ≤ 4c
and the learning rate does not change. Hence (E.3) also holds at t + 1. (t) Now suppose δi > 0. By its definition, (t)
(t+1)
Ψi (ηi Ui
(t)
) = 4c + δi .
The rate update gives (t+1)
ηi
(t+1)
Ui
(t)
c
=
(t)
(t+1)
η Ui (t) i
+
c + δi
δi
(t)
0.
c + δi
Thus the new potential input lies on the segment between the old scaled input and zero. By convexity of Ψi and Ψi (0) < 3c, (t+1)
Ψi (ηi
(t+1)
Ui
c
)≤
(t)
δi
(t)
(4c + δi ) + (t)
c + δi
(t)
3c = 4c.
c + δi
This proves (E.3). The argument uses convexity of the potential along this segment and does not require the potential to be monotone as the learning rate decreases. Bounding the excess above the threshold. We next control how far the potential can move above 4c before the rate adjustment is applied. Although the cumulative fixed-rate bound (4.3) does not telescope when the learning rate changes, the one-round estimate in Lemma 4.4 remains valid with the rate used on that round. (t) Apply Lemma 4.4 with η = ηi . Since (E.1) is exactly the corresponding one-round response, X 2 (t) (t+1) (t) (t) (t) (t) (t) (t) (t−1) Ψi (ηi Ui ) − Ψi (ηi Ui ) ≤ 2(ηi )2 ∂a Ψi (ηi Ui ) ui [a] − ui [a] a (t)
−(ηi )2
X
(t)
(t)
(t)
∂a Ψi (ηi Ui )ui [a]2 .
a
58
P
a ∂a Ψi ≤ 3 from Lemma 4.1 therefore gives
The last term is nonpositive. Using (t)
(t+1)
Ψi (ηi Ui
(t)
(t)
(t−1) 2
(t)
(t)
) − Ψi (ηi Ui ) ≤ 6(ηi )2 ui − ui
∞
.
Both centered-utility vectors have infinity norm at most one, so (t)
(t−1)
ui − ui
∞
≤ 2.
Consequently, (t)
(t+1)
Ψi (ηi Ui
(t)
(t)
(t)
) − Ψi (ηi Ui ) ≤ 24(ηi )2 .
Together with (E.3), this yields (t)
(t)
0 ≤ δi ≤ 24(ηi )2 . Controlling the decrease of the learning rate. The preceding estimate controls the rate update through the reciprocal squared learning rate. From (E.2), 1
−
(t+1) 2
(ηi (t)
)
(t)
1 (t)
(ηi )2
2δi
=
(t)
c(ηi )2
(t)
+
(δi )2 (t)
c2 (ηi )2
.
(t)
Using δi ≤ 24(ηi )2 gives 1 (t+1) 2
(ηi
−
)
(t)
1
≤
(t)
(ηi )2
48 576(ηi )2 + . c c2
(t)
Since ηi ≤ 1/32 and c > 2, (t)
576(ηi )2 ≤
576 < c, 1024
and hence 1 (t+1) 2 (ηi )
−
1 (t) (ηi )2
≤
49 . c
Summing from t = 1 to T telescopes these reciprocal-rate differences, which gives 1 (T +1) 2
(ηi
)
≤
1 (1)
(ηi )2
49T 49T = 1024n + . c c
+
Thus the safeguard can decrease the learning rate only at the rate allowed by this finite-horizon bound. Converting the potential bound into regret. After round T , (E.3) gives (T +1)
Ψi (ηi
(T +1)
Ui
) ≤ 4c.
Applying the potential certificate from Lemma 4.1, (T +1)
c + ηi
(T +1)
max Ui a
(T +1)
[a] ≤ Ψi (ηi 59
(T +1)
Ui
) ≤ 4c.
Using (2.4), (T )
3c
Regi
≤
1024n +
√ √ 49T ≤ 96 n c + 21 cT . c
(T +1) ηi
.
The reciprocal-rate bound now gives r
(T ) Regi ≤ 3c
Substituting c = 2 + log d proves the stated regret bound. All inequalities above hold pathwise for every realized sequence of utility vectors. No independence or probabilistic assumption on the sequence is used, so the result also allows the utility vectors to be chosen adaptively from the preceding history. The update uses only quantities available by the end of the current round and does not depend on T .
E.3
The Safeguard under Self-play
We finally show that the safeguard is inactive in the fixed-game self-play setting. Thus the adversarial protection does not alter the trajectory used to obtain the stronger self-play guarantee. Proposition E.2. Suppose all players use (E.1)–(E.2) in the fixed-game setting of Theorem 4.10. Then (t)
ηi =
1 √ 32 n
for every player i and every t ≥ 1.
Their mixed strategies coincide, round by round, with those of the fixed-rate algorithm. The regret and equilibrium bounds in Theorem 4.10 and corollary 2.5 therefore remain unchanged. Proof. We argue by induction on the round. Initially, every player has the same learning rate, cumulative vector, and preceding centered utility as in the fixed-rate algorithm. Hence the first√ round strategies coincide. Suppose all players have retained the rate 1/(32 n) through round t. Their played strategies and observations through that round then coincide with those of fixed-rate (t+1) self-play, so their updated cumulative vectors Ui also coincide. Apply Proposition 4.9 to this finite prefix. For every player i, ! (t+1) Ui √ ≤ 4c. Ψi 32 n (t)
Therefore δi = 0 for every player, and (E.2) gives (t+1)
ηi
=
1 √ . 32 n
This proves the induction step simultaneously for all players. Hence the safeguard never changes a learning rate, and the entire self-play trajectory agrees with the fixed-rate trajectory. The safeguard requires only one additional scalar learning rate for each player and one evaluation of the closed-form potential after each round. It does not change the cumulative vector or centered utilities, introduce an additional play, or require an optimization subroutine. 60
E.4
Completing the Main Guarantee
The self-play result and the adversarial bound together give the main theorem. Theorem 2.4 (Regret bounds for MORM). Consider a fixed n-player finite game with at most d ≥ 2 actions per player and utilities in [0, 1]. If all players i ∈ [n] follow MORM (Algorithm 1) with √ c = 2 + log d and learning rate η = 1/(32 n), observing their exact expected-utility vectors after each round, then every player i ∈ [n] has external regret (T )
Regi
√ ≤ O( n log d).
Moreover, MORM is adaptive to adversarial utilities through the learning-rate safeguard in Section E, which only decreases the learning rate adaptively and leaves the rest of the update unchanged. The safeguarded rule for any individual player i guarantees p √ (T ) Regi ≤ O( n log d + T log d) (t)
against arbitrary, possibly adaptive, utility vectors νi all T ≥ 1.
∈ [0, 1]|Ai | . Both bounds hold uniformly over
Proof. The self-play assertion follows from Theorem 4.10, which gives the explicit bound (T )
Regi
√ ≤ 96 n (2 + log d).
The adversarial assertion follows from Theorem E.1, which gives p √ (T ) Regi ≤ 96 n (2 + log d) + 21 T (2 + log d). For d ≥ 2, 2 + log d ≤ 1 +
2 log 2
log d,
so these two explicit estimates imply the stated asymptotic bounds with universal constants. Both hold for every finite horizon without requiring T in advance. Finally, Proposition E.2 shows that the safeguard never changes the learning rate in fixed-game self-play, so the stronger self-play trajectory and its equilibrium guarantee remain unchanged.
61