Optimism Without Regularization: Constant Regret in Zero-Sum Games
Authors: John Lazarsfeld
Georgios Piliouras
Ryann Sim
Stratis Skoulakis
Venue: NeurIPS 2025 poster ()
Keywords: optimistic fictitious play
learning in games
zero-sum games
Primary area: theory

Abstract: This paper studies the *optimistic* variant of Fictitious Play for learning in two-player zero-sum games. While it is known that Optimistic FTRL -- a *regularized* algorithm  with a bounded stepsize parameter -- obtains constant regret in this setting, we show for the first time that similar, optimal rates are also achievable *without* regularization: we prove for two-strategy games that Optimistic Fictitious Play (using *any* tiebreaking rule) obtains only *constant regret*, providing surprising new evidence on the ability of *non*-no-regret algorithms for fast learning in games. Our proof technique leverages a geometric view of Optimistic Fictitious Play in the dual space of payoff vectors, where we show a certain energy function of the iterates remains bounded over time. Additionally, we also prove a regret *lower bound* of $\Omega(\sqrt{T})$ for *Alternating* Fictitious Play. In the unregularized regime, this separates the ability of optimism and alternation in achieving $o(\sqrt{T})$ regret.

Optimism Without Regularization: Constant Regret in Zero-Sum Games
John Lazarsfeld SUTD"
Georgios Piliouras SUTD
Ryann Sim SUTD
Stratis Skoulakis Aarhus University
Abstract
This paper studies the optimistic variant of Fictitious Play for learning in two- player zero-sum games. While it known that Optimistic FTRL- regularized algorithm with bounded stepsize parameter obtains constant regret in this setting, we show for the first time that similar, optimal rates are also achievable without regularization: we prove for two-strategy games that Optimistic Fictitious Play (using any tiebreaking rule) obtains only constant regret, providing surprising evidence the ability of non-no-regret algorithms for fast learning in games. Our proof technique leverages a geometric view Optimistic Fictitious Play in the dual space of payoff vectors, where show certain energy function of the iterates remains bounded over time. Additionally, we also prove a regret lower bound of O2( ((VT)) for Alternating Fictitious Play. In the unregularized regime, this separates the ability of optimism and alternation in achieving of o(v"T) regret.
Introduction
Despite the fact that regularization is essential for no-regret online learning in general adversarial settings, unregularized algorithms still able obtain sublinear regret the case of two-player zero-sum games. Fictitious Play (FP), dating back to Brown (1951), is the canonical example of such unregularized algorithm, and results from both players independently running Follow-the- Leader (FTL).² In the worst case, FTL can have (2T)) regret due to its sensitivity to oscillations in udversarially-chont choseen reward sequences "Shalev-Shwarte settings, the classic result of Robinson (1951) proved that, under Fictitious Play, the sum of the players' regrets (henceforth referred to as regret) indeed sublinear (thus implying time-average convergence a Nash equilibrium), albeit the very slow ((rl-1/m) rate for n X n games (which was shown to be tight by Daskalakis and Pan (2014) using an adversarial tiebreaking rule).
al., 2012). However, zero-sum game
However, the recent works of Abernethy al. (2021a) and Lazarsfeld et al. (2025) have established improved O(VT) regret guarantees for Fictitious Play diagonal payoff matrices (using lexico- graphical tiebreaking) and on generalized Sacc-PPper-Scisson matrices (using any tiebreaking rule), respectively. As result, there is growing evidence the robustness of unregularized awbeedalggon algorithms like FP (not a no-regret algorithm in general) for obtaining fast, sublinear regret zero-sum games.
On the other hand, the past decade has seen regularized learning algorithms exhibit a remarkable success in providing even better of ((VT) regret guarantees for learning in games. In zero-sum games, optimistic variants FTRL (including Optimistic Multiplicative Weights and Optimistic Gradient Descent) obtain only constant regret (with respect to the time horizon I'), implying optimal O(1/T) time-average convergence to Nash (Rakhlin and Sridharan, 2013; Syrgkanis et al., 2015). While such guarantees can be obtained using absolute constant stepsizes (with no dependence on 7'), standard
*Correspondence to: jlazarsfe eld0gmail. com FFTL is a particular instance of Follow-the the Regulagglr Leaderr (FTRL) with unbounded stepsize 0c.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

proof techniques (e.g. the RVU bound approach of Syrgkanis et al. (2015)) still crucially require a finite upper bound on stepsize, corresponding to constant magnitudes of regularization. This raises the following, fundamental question: Is O(1) regret attainable in zero-sum games without regularization (equivalently, with unbounded stepsizes)? Can variants of Fictitious Play achieve O(1) regret?
Apart from its theoretical interest, this question admits crucial applications in the context of equilib- rium computation algorithms for combinatorial games (Beaglehole et al., 2023), as well during training via self-play in certain multi-agent reinforcement learning settings ( (Vinyals et al., 2019).
1.1 Our Contributions
In this work, we establish an affirmative answer to the question above. Our main result establishes that, in the case of 2x2 zero-sum games, Optimistic Fictitious Play obtains constant regret:
Informal Theorem (See Theorem 3.1). Optimistic Fictitious Play, using any tiebreaking rule, obtains O(1) regret in all 2 2x2 zero-sum games with a unique, interior Nash equilibrium.
Our result gives surprising new evidence that, even without regularization, optimism can be used to obtain an accelerated regret bound, matching the optimal rate obtained by regularized Optimistic FTRL algorithms (Syrgkanis et al., 2015). While our theorem establishes constant regret only for the case of two-strategy zero-sum games, our proof techniques offer indication that similar, optimal regret bounds may further hold in we also experimentally evaluate Optimistic FP on nigher-dimensional zero-sum games, and these evaluations suggest that, even for much larger games, Optimistic FP still obtains constant regret.
settings. Apart from our theoretical results,
Our proof technique is based on a novel geometrie perspective of Optimistic FP in the dual space of payoff vectors. Our main technical contribution is showing that an energy function function of the dual iterates of the algorithm is upper bounded by a constant. This energy upper bound can then be easily used to establish constant regret of the primal iterates. The latter comes in contrast to the energy growth of the iterates of standard FP, which strictly increases over the time horizon (Lazarsfeld et al., 2025).
We also consider the alternating variant of Fictitious Play. Recent work has studied the use of alternation (independently of optimism) as a method for obtaining o( o(vT) regret guarantees in both the adversarial (Gidel al., 2019; Bailey al., 2020; Cevher et al., 2023; Hait et al., 2025) and the zero-sum game setting (Wibisono et al., 2022; Katona et al., 2024). Contrary to optimism, we show in the case of alternation that regularization is necessary to achieve o(vT) regret:
Informal Theorem (See Theorem 3.2). On the 2x2 Matching Pennies game, Alternating Fictitious Play, using any tiebreaking rule and for nearly all initializations, has regret at least Q(VT).
Together, our results separate the regret guarantees of using optimism and alternation in the regime of no regularization: while optimism without regularization can obtain optimal O(1) regret (Theo- rem 3.1), alternation alone is in general insufficient for improving beyond O( O(VT) (Theorem 3.2), the same rate achievable by standard (non-ald (ton-alternating) FP in the 2x2 setting. To this latter point, note that the lower bound of Theorem 3.2 comes in contrast to the improved OTT)//5) /66) rate obtainable by Alternating FTRL under a sufficiently small stepsize (Katona et al., 2024).
Table summarizes our results and the landscape of regret guarantees in the 2x2 setting for FTRL and FP variants, and Figure shows example of the empirical regret guarantees of standard, Optimistic, and Alternating FP variants in several games (additional results are presented in Sections 5 and E).
Standard
Optimistic
Alternating
7) bounded (FTRL)
O(VT) i
0(1)* ^ O(T1/5) M
17 + 00 (FP)
O(VT)+
0(1)
2(VT))
Table 1: Regret guarantees for FTRL and Fictitious Play variants in 2 zero-sum games, with our contributions
shaded in gray. t: Using the standard setting of 1 1/VT (Shalev-Shwartz et al., 2012). ^: Via the RVU bounds of Syrgkanis et al. (2015). ^^; (Katona et al., 2024), extending on the prior ((T)/3) bound of Wibisono al. (2022). 4: Implicit in the proof of Robinson (1951)." *: Theorem 3. ":: Theorem 3.2.
2

---

Matching Pennies
Identity
15x15
FP
200
OFP
OFP
OFP
Tatal Regret
150
100
50
2500
5000
7500
10000
2500
5000
7500
10000
0
2500
5000
7500
10000
Figure Empirical regret standard (FP), Optimistic (OFP), and Alternating (AFP) Fictitious Play in Matching Pennies (from z = (1/3, 2/3). x = (2/3, 1/3)), on the 15x 15 identity matrix (from z = c1, 22 e.), and on 15x 15 generalized Rock Sock-PPper--e Paper-Scisson (from xf = c1. 222 = en). Each algorithm was run for T' = 10000 iterations using lexicographical tiebreaking rule. Each subtigure demonstrates the constant empirical regret of OFP compared to the roughly v regret growth of standard FP and AFP. More experimental details and results given in Section 5 and Section E.
1.2 Other Related Work
Optimistic learning in games. Our work relates to a line of research on the convergence prop- erties of optimistic and extragradient-Iype algorithms in both normal-form and extensive-form games (Daskalakis et al., 2021; Fasoulakis et al., 2022; Anagnostides et al., 2022a; Zhang et al., 2024; Farina al., 2022; Hsich et al., 2022: Anagnostides et al., 2022b; Piliouras et al., 2022; Anagnostides et al., 2022c). As previously noted, a key difference is that these approaches typically rely on constant time-decreasing step sizes, corresponding to some level of regularization. Recent works have also investigated last-iterate convergence properties of optimistic and extragradient methods (Daskalakis and Panageas, 2019; Cai al., 2022; Abernethy et al., 2021b; Hsich et al., 2020), as well as for variants of regret-matching, including under alternation (Cai et al., 2025a). Other works have studied accelerated rates using optimism without regularization certain Frank-War Wolfe-type, convex-concave saddle-poite pootle-pointttee problems (Wang and Abernethy, 2018; Abernethy et al., 2018).
Learning in 2x 2 games. Our work adds to growing recent literature studying online learning algorithms in 2x2 games: in two-strategy zero-sum games, Bailey and Piliouras (2019) proved that Online Gradient Descent obtains O (VVT) regret even with large constant stepsizes. More recent works of Cai et al. (2024) and Cai et al. (2025b) establish lower-bounds on the last-iterate and random-iterate convergence rates of Optimistic MWU using a hard 2x2 construction, as well as an OTT1/0) upper bound on best-iterate convergence for 2x2 zero-sum games. Chen and Peng (2020) similarly used 2x2 construction establish general ? ((vT) lower bound on the regret of standard Multiplicative Weights. In a family of two-strategy congestion games, Chotibut et al. (2021) also showed that the iterates of Multiplicative Weights can exhibit formally chaotic behavior.
Fictitious Play. We refer the reader to the recent results of Daskalakis and Pan (2014), Abernethy et al. (2021a), and Lazarsfeld al. (2025) (and the references therein) for background on standard Fictitious Play. Abernethy et al. (2021a) also briefly introduced the optimistic variant of Fictitious Play, and they informally conjecture the algorithm have constant regret diagonal payoff matrices. The convergence behavior of FP has also been studied in potential games (Monderer and Shapley, 1996; Panageas al., 2023), near-potedr pear-potential games (Candogan al., 2013), Markov games (Sayin et al., 2022; Baudin and Laraki, 2022), and extensive-form games (Heinrich et al., 2015).
2 Preliminaries
Let [n] (1, (1....,,)) ,n], let A,, be the probability simplex in R", and let {e+) (e; : E [n]] c An denote the set of standard basis vectors in RR, which correspond to vertices of An. For x E An we say is interior if 24 for all e [n].
2.1 Online Learning in Zero-Sum Games
Let A E Rmmx be the payoff matrix for a two-player zero-sum game, and let T be a fixed time horizon. At round t, Players and 2 simultaneously choose mixed strategies 21 E A. and 2 A... obtain payoffs (xf, Ark) and - -2z,, A 2f), and observe feedback Azh and -A Ta respectively.
3

---

Regret and Convergence to Nash. Each player seeks to maximize their cumulative payoff, and their performance is measured by the individual regrets Reg, (I') max Σi= x Azi) and (eg = minzea,, ΣT= (arz
J. A A=a)). From global perspective, we study the total regret (henceforth regret) Reg(T) Regi (I') + Reg2 (I') given by
Reg(T)
max ZE
(a, Σ Arh) And)
T
T E. A ATa) rEAn
min (x,,
(I)
is well known that sublinear bounds on Reg (T) correspond to convergence (in duality gap) of the players' time-average iterates to Nash equilibrium (NE) of A. Recall that the duality gap of a joint strategy profile (æ1, 22) is given by D= Ø2) = max,fE4... (4i, Ax2) minzeed. (2/2. A æ1).
and that (æi, x5) is an NE of A if and only if (G ; x5)) = 0. Then the following relationship holds (see Section A for proof):
Proposition 2.1. Let क. = (Et= x1) and 7 = (Ei= x²2) denote the time-average iterates of Players and 2, respectively, and suppose Reg(T") = o(T). Then (if x2") converges (in duality-gap) an NE of rate of Reg(T)/TT o(1)
2.2 Fictitious Play and Optimistic Fictitious Play
We now introduce the Optimistic Fictitious Play (and standard Fictitious Play) algorithms. The primal update rules for both standard and Optimistic Fictitious Play be described via the following a- a-Optimistic Fictitious Play (a-OFP) expression:
1
1+1 = argmax (I,,
E
Any + aA1z))
k=
#E(e.)m
(a-OFP)
1+1 = argmax (ar, Σ Ei A - aA aAA
22
When a O, then (a-OFP) recovers standard Fictitious Play, where each player's strategy time I ++ a best response to the sum of feedback vectors through round I. Optimistic Fictitious Play (OFP) is the setting of (a-OFP) with 1. Observe this recovers the unregularized variant of Optimistic FTRL (equivalently, with 7) + oo) the zero-sum game setting (c.f., (Rakhlin and Sridharan, 2013; Syrgkanis al., 2015)), which adds bias to the most recent feedback vector.
Remark 2.2 (Tiebreaking Rules). Observe that the argmax sets in (a-OFP) may contain multiple vertices. For this, we assume that the argmax operator encodes a tiebreaking rule that returns distinct element. Throughout, we make no assumptions on the nature of the tiebreaking rule, and in general ties can be broken deterministically, randomly, or adaptively/avverssarally
Dual payoff vectors and primal-dual update. Optimistic FP can be equivalently written with respect to the cumulative payoff vectors yí = -E' Art E R" and 2/ = -E A a e R.. Specifically, the iterates of the algorithm can be expressed in the following primal-dual form:
Definition 2.3. Let yf 0 E R and 2/ = 0 e R", and fix any initial xf E Am and z An. Then for t 2 1, the dual (i.c., (vi vt)) and primal (i.c., (zf, x²)) iterates of Optimistic FP are:
x
argmax (x, ví + Anh-1)
{ vi - + Arb-1
re (cs)m
and
(OFP)
1 v2 A x1
argmax (a, A AT
re
3 Regret Bounds for Optimistic and Alternating Fictitious Play
The main result of this paper establishes constant regret bound for Optimistic Fictitious Play in two-strategy zero-sum games. Formally we prove the following theorem:
Theorem 3.1. Let be a 2x2 zero-sum game with a unique interior NE, and let ((1),ah)) be the iterates of (OFP) on A using any tiebreaking rule. Then Reg(T") O(1).
As mentioned, this result establishes the first constant regret bounds for Fictitious Play variants in the two-player zero-sum game setting, and the result holds regardless of the ticbreaking rule used.

---

Moreover, this bound matches the optimal rate obtained by Optimistic FTRL variants for zero-sum games (Syrgkanis al., 2015), but notably. our proof technique departs significantly from the RVU bound approach used to obtain those results.
As consequence of the techniques we develop for proving Theorem 3.1, we also establish lower bound on the regret of Alternating Fictitious Play. In particular, for the corresponding alternating regret Reg al (T') (see Definition D.2), we prove on the 2x2 Matching Pennies game the following:
Theorem 3.2. Suppose zj = (p, 1 --p) E f2r irrational p E (3/4, 4 1), and let {x²) be the iterates of Alternating FP on (Matching Pennies) using any tiebreaking rule. Then Reg" (T) 2 ((VT)..
To streamline the presentation of the paper, we defer the precise descriptions of the alternating play model, alternating regret, and the Alternatin FP algorithm to Section D, where we also develop the proof of Theorem 3.2. Instead, in the remainder of the main text, we focus on developing the proof of Threorem 3.1. To this end, we proceed to give an overview of our techniques.
3.1 Intuition and Overview of Proof Techniques for Theorem 3.1
To prove Theorem 3.1, we leverage a geometric view of Optimistic Fictitious Play in the dual space of payoff vectors. We give a brief overview of this geometric perspective here:
Energy and regret. First, we show that the regret of the primal iterates {a*) } is equivalent the growth of an energy function of the dual iterates {y'}. Specifically, define the energy V as follows: Definition 3.3. Let y² = (vis y$) be the concatenated primal and dual iterates of (OFP) time t 12 1. Then for y = (y,, U2) E Rm++n, the energy function V IR -> is given by
max L (v) m X
(I, y)
(2)
In other words, & is the support function of Am x An. Then by definition of Reg(T) and the payoff vectors (v') the following relationship holds (see Section A for proof): Proposition 3.4. Let {x²} and {y'} be the iterates of (OFP). Then Reg(T) V (y²
Due to Proposition 3.4, it is immediate that a constant upper bound on (y implics a constant upper bound on Reg(T). To this end, our main technical contribution is prove the following upper bound on the energy V under Optimistic Fictitious Play:
Theorem 3.5. Assume the setting of Theorem 3. Let Omna = || denote the largest entry of A, and let agap = (in((..).(kkEE)) [Arj- - Axel denote the smallest absolute difference between two entries
of A. Let {y'} denote the dual iterates of (OFP) on A. Then Ve (y < 80 (1 + 2 Amazz
Ggsp
In other words, the energy of the dual iterates under Optimistic FP are bounded by an absolute constant that depends only on the entries of A. In Section 4, we give a technical overview of the proof of Theorem 3.5, but we first present more introduction and intuition on the geometric perspective of Optimistic Fictitious Play that is used to prove the result.
Fictitious Play Skew-Gradient Descent. As shown in Abernethy et al. (2021a) and Lazarsfeld et al. (2025), in the dual space of payoff vectors, standard Fictitious Play can be viewed as a certain skew-gradient descent with respect to the energy V. In light of this, we introduce common geometric viewpoint that captures both standard and Optimistic FP and gives insight into their differences in energy growth, as implied by Theorem 3.5.
For this, note that the subgradient set of V at y E Rm+* is given by (v) argmax ae xAn. (x, y). Then both standard FP and Optimistic FP can be expressed as a skew-(sub) /ttps/bbbbddiieeeeeeeeeen with respect to V evaluated at a predicted dual vector gzt+1 (see Section A.3 for a full derivation):
Proposition 3.6. Let {y'} denote the dual iterates of either standard Fictitious Play (e.g. (a-OFP) with a = 0) or Optimistic Fictitious Play. Then for all 2 1, the iterates of each algorithm evolve as
yf -y²- --++-x'-- x' E au (T
where J = - 0 A) A) and gH
y¹ 2yy²
for FP
(3)
-AT
for OFP
and it follows inductively that t = y + JON (T++1), where 2V (g)+)) denotes a fixed vector in the subgradient set of v at if i
5

---

One-step energy growth comparison of Fictitious Play variants. For standard FP. due to its Hamiltonian structure, the analogous skew-gradient flow in continuous-time known to exactly conserve V, leading to constant regret (see, e.g., Mertikopoulos et al. (2018); Abernethy et al. (2021a); Wibisono et al. (2022)). However, due to discretization, this energy conservation does not hold in general under discrete-time Fictitious Play variants. For example, under each step of standard Fictitious Play, V is always non-decreasing. To see this, let A (yy) = ((y(+)) - (yy)), and by slight abuse of notation, let @v denote a fixed vector in the subgradient set of v/ at y E B=***
Then by Jensen's 's inequality and skew-symmetry of J =J it holds for all 2 1 that
For FP: A (v)) 2 (JV("") ( JOH (v')
0
(4)
In fact, the recent upper bounds of Abernethy et al. (2021a) and Lazarsfeld et al. (2025) imply that under FP, V is strictly increasing by a constant roughly vT iterations.
On the other hand, for Optimistic FP using 7 = -2y - y²-1, we instead have by Jensen's 's inequality: ).
For Optimistic FP: AV((y) S (v) ( (ON
(5)
Thus by skew-symmetry of J, expression (5) reveals that for any / where (V (v)+)++
(e.g., true dual vector t and predicted dual vector g²+1 both "map" to the same primal vertex), then the one-step energy growth Av S 0 is non-increasing under Optimistic FP.
Challenges in establishing non-positive energy growth for OFP. Naively, one might in general hope the invariant OV (y = (4 simple experiments reveal that this is not true: in general v can increase during one step of the algorithm. Thus, understanding when and why such an invariant does hold is still a challenging task that may require leveraging structural properties of the payoff matrix. In the proof of Theorem 3.5, we leverage such properties of 2x2 games to establish sufficient conditions for when the above invariant holds, and this subsequently leads to a constant upper bound energy.
holds at every timestep under Optimistic FP. However,
4 Bounded Energy Under Optimistic Fictitious Play
In this section, we now give technical overview of the proof of Theorem 3.5. Throughout the proof, we make the following assumptions on the payoff matrix A: Assumption 1. Let A E 1R2222 Assume that
6) d
{ (i) det A = ad bc =
A =
where
(ii a, > max b, b.c]
As proven by Bailey and Piliouras (2019), who studied online gradient descent in 2x2 games, for any Fictitious Play or FTRL variant, Assumption 1 holds without loss of generality:
Proposition 4.1 (Bailey and Piliouras (2019)). Let A E 22x2 have umique, interior NE, and let {et) } be the iterates of (OFP) on A. Then there exists A E IR2X2 satisfying Assumption I such that (1) A and A have the same NE and (2) the iterates {T'} of running (OFP) on À are identical to {x²}.
For completeness, we include full proof of this result in Proposition 4.1 of Section B. The key consequence of the assumption is that, under Optimistic FP, the dual payoff vectors y = (vi w²) E RA all lie in the same two-dimensional subspace. Formally, we have:
Proposition 4.2. Let A satisfy Assumption 1, and let {ví} and {32} be the dual payoff vectors of (OFP). Then for every > 1, it holds that viz -PI vin and yon pp yin where Pi = (d - c) b) > and p2 = (d- - b)/(a - c) > 0.
The proof of Proposition 4.2 is given in Section C. Importantly, as Pl. P2 > O, observe that yf > 0 + vi > vig. and 2 > 0 < v/1 > 2 for all times 2 1. Thus, in the 2x2 setting, the coordinates vi and v encode all information needed to analyze the iterates of Optimistic FP in (3).
With this in mind, the strategy for proving the upper bound on the energy T (TT+1) is as follows: first, leveraging the observations above, and as in Bailey and Piliouras (2019), we restrict our study of the dual iterates (ví.v)) E Rd to the pair of scalar iterates 1/113/1 E IR.. For this, we introduce in Section 4. I new set of notation to capture this lower-dimensional subspace dynamics, which also naturally leads to the definition of an equivalent energy function. For the new, equivalent energy function, we then prove in Section 4.2 a set of invariants that allow for establishing a uniform, constant upper bound on the energy of the dual iterates over time.

---

4.1 Subspace Dynamies of Optimistic Fictitious Play
We now introduce an equivalent of primal and dual iterates {w") and {2*} for (OFP), as well as new, equivalent energy function ub. We will establish in Proposition 4.6 that (y = (1(
Primal variables. First, by definition of (OFP), both zf and z are vertices of Ag. Letting =' {(1, 0), (0, 1)} x {(1,0) (0, 1)} C R$ denote the vertices of the joint simplex 4₂ x A2. it follows for each 2 that x' X. We define new primal iterates w' R4, where each w is
standard basis vector of Rt. Let W = {e1, e2, e3.
e3, ea) C R denote this set. Then for t 2 1, let:
{ [a==
= x' (0,1,1,0)
= x² = = (1,0,100 C4 4 x² = (1,0,,,)
wf
(6)
c x' (0,1,0,1)
c1
Dual variables. For each t 0, let zj vir R and
V RR. Let 2' (2), 25) RR?.
Primal-dual map. To aid the description and analysis of the subspace dynamics, we describe the following partition of the dual space IR3. We then describe a corresponding choice map Q RR + X that relates the primal and dual variables {w"} and {
Definition 4.3. First, let P (P1, P2, P3, P.] C R?, where each P. is the set
P2 {= E R²2 < 0 and > 0}
P3 {= R > 0 and 22 > 0}
(7)
Pi e R² 21 and 22 < <0}
Pa {z R 21 0 and 22 0)
Next, let P = {PIn2, P2-3, P3-4, Pa-1} } C RR?,, where we define
Pa-3 {= I²² :21 and > 0} Pa {2 R² :21 and 0}
(8)
Pi-2 {= : :1 and =}
Pa-1 {s R #1 and 0]
Finally let P UiE(4) P., where P P. S.P.P (i- Observe by definition that P ((000)
R..
Note that for notational convenience, when us- ing an index [4] in the context of the sets of Definition 4.3, we assume addition and subtrac- tion to are performed (mod 4) in the natural way that maps to the set {1, 2,3, 3, 4J. For exam- ple, Pe-(141) is the P4-1 when
P2-3
P2
P3
4, and P:-2 = P:+2 is the set P3 when i = 1, etc. Figure depicts the sets from Definition 4.3.
P1
P4
Moreover, Definition 4.3 allows for defining choice map Q R² + W that encodes the
Figure 2: Examples of the sets in P. P. and P.
primal update rule (OFP). In particular, Q maps dual variables to primal vertices w depending on the membership of = in P or P. Formally:
Definition 4.4. Let Q : R² + W be the map defined as follows: first, let Q( 61. Then
For = E P: if = E P. for i E [4], then Q(=) = Cj.
For = E P: if E Peo()+1) for i E [4], then Q(=) E {Ee, ei41
As in the full update rule of (OFP), we assume Q encodes a tiebreaking rule to ensure Q(z) returns a single element from W. As in Remark 2.2, make assumptions on how such ties are broken.
Primal-dual dynamics. Using the definitions of the primal and dual variables {w'} and {2*} and the choice map Q, the primal-dual dynamics of (OFP) can be rewritten follows: for all t 2 2, let
x² 2²1 Sw wt Q(2 + -wwt
where S ( aa -a)
(9)
Observe that the i'th column S E R2x1 are the entries (Ayí1- Awja) when w² = e; (cf., the definition of w from expression (6)). Moreover, expression (9) implics Swi-1 2¹ =² for all
7

---

t t2 2. Thus, we can further describe the primal-dum dynamics of (9) solely in terms of the sequence of dual variables {z*}. In particular, for all 2, we have
z+t 2² + (2' - 2 SQ(E+11
(OFP Dual)
Energy function. Using the new notation and dual variables {z'}, we define an energy function wb: R
R over the new dual space IR let ()0, 0)) O, and for all other E R2 let
if Pa. if E Pl.
if E Ps. 2 E P4 if
(12) =
- P1 21 P1 21
21 22
(10)
P2
21 P2
is also more expressive to write & using the choice map Q from Definition 4.4, Recall for any E IR that Q(z) W {er, e2, 63, 64). Then we have the following equivalent definition of ih: Definition 4.5. For E IR2 the function v R2 + given by
v(z) (z, MQ(=))
where M
P1 P2
P1
(11)
P22
Due to the relationship between the coordinates of vi and v from Proposition 4.2, the following relationship between V and vi (and by Proposition 3.4, between V and Reg(T)) is immediate:
Proposition 4.6. For all ((y') 1b(z)). Moreover, Reg(T) (T = (=
4.2 Bounded Energy of Subspace Dynamics
Leveraging Proposition 4.6, it suffices to derive upper bound on (2(2++1 in order prove Theorem 3.5. For this, the key step is to prove a set of invariants on the dual iterates which establish that. if the magnitude of & ever exceeds some constant threshold, the subsequent one-step change in & non-increasing (thus crystalizing the intuition from expression (5)).
For this, we first define absolute constant B as follows:
Definition 4.7. Fix A satisfying Assumption 1, and recall Omax
|| Then define B > 0 by
min (6 e E. for all R23 || 1 < 6amax
bb)
In words, is the smallest constant whose sublevel set (2) I B contains an l ball radius 6amax- Moreover, the magnitude of B can be bounded from above follows (see Section C for the proof);
Proposition 4.8. Let B be the constant from Definition 4.7. Then B 60 (1 P1 P2).
Worst-case upper bound on energy. Observe that if (x²2) < B for all times f, then the statement of Theorem 3.5 trivially holds. the other hand, the energy & crosses this threshold under one step of the dynamics, then we have the following constant upper bound (b(=+11):
Lemma 4.9. Suppose (02²) < B, and let B' = 8a (1 + + p2) Then (bz < B'
Cycling invariants and controlled energy growth. The remaining step is to then control the energy growth whenever (x²²) B. For this, prove the following key lemma:
Lemma 4.10. Suppose (b(²)) > B and et Po [4]. Then the following hold:
(1) Either (i) g++1, g E P. (i) 241,20011 e Pit
(2) AD(2t) (12 (2²)) < 0.
Part (1) of the lemma establishes invariants relating the true payoff vectors and predicted payoff vectors whenever energy is above the threshold B. Roughly speaking, when t larger than B, the dual vectors cycle consecutively through the regions P Pi..... Pa (similarly to the iterates of standard Fictitious Play), and this roughly implies that Q(2++1) Q(2++1).

---

Importantly, this alignment between 2 and E is the key step needed to establish non non- increasing change energy, as stated in part (2). To see why this is true, observe that using the definition of ş from (1 I), we can compute the one-step change Anb(=") = ((++tt) (=²) under (OFP Dual) as
A=) (=*+), MQ(= (2', MQ(=1))
(12)
(2 + SQ()tt)), MQ( (M( - (2', (+,))(=')
- ( + (Q( S M
(13)
(14)
Here, (14) essentially encodes the expression for Av from (5). In particular, straightforward calculations show that the matrix S M is skew-symmetric, and as Part (1) of the lemma roughly implies 1)= = Q( term (b) of (14) vanishes. Together with the column structure of M, the invariants of part (1) imply that part (a) of (14) is non-positive, and thus overall Ab(2²)) S 0.
The full proofs of the preceding lemmas are developed in Section C and account more carefully for boundary conditions and tiebreaking. Figure 3 of Section C.3 also gives more visual intuition for the invariants and energy-grovd mergy--roothh behavior of Lemma 4.10. Granting these lemmas as true for now, we then give the proof of Theorem 3.5:
Proof of Theorem 3.5. Suppose for L > that (xx-11) S B and xx²) > B. By Lemma 4.9, we must have ()))) < 8amax + PI p2)². Moreover, Lemmas C.2 and C.6 together imply follows inductively that 2b T+) 8amaa (1 + P1 + p2)2 By definition, Pl P2 (amax/ agap), and thus conclude
that A (2)) I 0, and thus also () I Samax + P1 + +p2)2
16 (+1) (y (+)) < Samax (1 + 2(Amaxx/ (0yp))
Discussion and Conclusion
In this work, we established for the first time that the unregularized Optimistic Fictitious Play algo- rithm can obtain constant (11) regret in two-player zero-sum games. Our proof technique leverages geometric viewpoint of Fictitious Play algorithms, and we believe the techniques established for the 2x2 regime can be extended to higher dimensions.
Additional experimental results. To this end, in Table we present additional experimental evidence indicating that constant regret bounds for Optimistic FP (similar Theorem 3.1) hold more generally in gigher-dimensoona, settings. The table shows the empirical regret of Optimistic FP and standard FP (using lexicographical tiebreaking) on three classes of zero-sum games, in three higher dimensional settings. For each setting, the algorithms were run from 100 random initializations, each for T 10000 iterations, and we report the average regret over all initializations.
Dimension:
15x15
25x25
50 50
Payoff Matrix +
FP
OFP
OFP
FP
OFP
Identity
155.1 = 3.9
8.1 1.6
161.3 +
12.5 1.7
167.2 2.5
25.2 2.1
RPS
235.6 = 7.6
2.9
0.5
242.2
2.9
242.7 5.9
2.5 + 0.8
Random [0,
116.2 5.8
4.3
1 0.8
118.6 5.7
0.9
177.0 1 6.5
13.0 1 1.5
Table 2: Empirical regret of FP and OFP using lexicographical tiebreaking. Each entry reports average and standard deviation (over 100 random initializations) total regret after T 10000 steps.
The results indicate that, in each class of payoff matrix and in each dimension, Opimistic FP has only constant regret compared to the regret of roughly vT sJ 100 obtained by standard FP. In Table 3 of Section E, also report results using randomized riebreaking for both algorithms and find similar conclusions, thus highlighting the robustness of the constant regret of OFP to tiebreaking rules. In Section E, we give more details on the experimental setup and additional plots similar to Figure
Limitations. Formally proving whether Optimistic Fictitious Play obtains constant regret in all zero-sum games remains important open question.
Broader impact. We acknowledge that there are many potential societal consequences of our theoretical results, however none of which we feel must be specifically highlighted.

---

Acknowledgements. JL and RS were supported by the MOE Tier 2 Grant SMOE--22P20223-00018 the National Research Foundation. Singapore, under its QEP2.0 programme (NRF202I-QED) PO5), the National Research Foundation Singapore and DSO National Laboratories under the AI Singapore Programme (Award Number: AISG2-RP-2020-00 and SS was supported by the Villum Young Investigator Award (Grant no. 72091). The authors thank Anas Barakat and Andre Wibisono for helpful discussions.
References
Abernethy, J., Lai, K. A., and Wibisono, A. (2021a). Fast convergence of fictitious play for diagonal payoff matrices. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1387-1404. SIAM.
Abernethy, J. D., Lai, K. A., Levy, K. Y., and Wang. (2018). Faster rates for convex-concave games. In Bubeck, S., Perchet, V., and Rigollet, P., editors, Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages 1595-1625. PMLR.
Abernethy, J. D., Lai, K. A., and Wibisono, A. (2021b). Last-iterate convergence rates for min- max optimization: Convergence hamiltonian gradient descent and consensus optimization. In Feldman, V., Ligett, K., and Sabato, S., editors, Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132 Proceedings of Machine Learning Research, pages 3-47. PMLR.
Anagnostides, L., Daskalakis, C., Farina, G., Fishelson, M., Golowich, N., and Sandholm, T. (2022a). Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pages 736-749.
Anagnostides, I., Farina, G., Kroer, C.,, Lee, C., Luo, H., and Sandholm, T. (2022b). Uncoupled learning dynamics with Ollog T) swap regret in multiplayer games. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A., editors, Advances in Neural Information Processing Systems 35: Anmual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022.
Anagnostides, I., Panageas, I., Farina, G., and Sandholm, T. (2022c). On last-iterate convergence beyond zero-sum games. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári. C., Niu, G., and Sabato, S., editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 536-581. PMLR.
Bailey, J. and Piliouras, G. (2019). Fast and furious learning in zero-sum games: Vanishing regret with non- vonishiig step sizes. Advances in Neural Information Processing Systems, 32.
Bailey, J. P., Gidel, G., and Piliouras, G. (2020). Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. In Conference on Learning Theory, pages 391-407. PMLR.
Baudin, L. and Laraki, R. (2022). Fictitious play and best-response dynamics in identical interest and zero-sum stochastic games. In Chaudhuri, K., Jegelka, S., Song, L.,, Szepesvári, C., Niu, G., and Sabato, S., editors, International Conference on Machine Learning, ICMI. 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 1664-1690, PMLR.
Beaglehole, D., Hopkins, M.. Kane, D., Liu, S., and Lovett, S. (2023). Sampling equilibria: Fast no-regret learning in structured games. In Bansal, N. and Nagarajan, V., editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 3817-3855. SIAM.
Brown, G. W. (1951). Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1):374.
10

---

J., Kroer, C., Lee, Luo, H.,, and Zheng. W. (2025a). Last-iterate Cai, Y., Farina, G., regret-matching algorithms in games. In The Thirteenth International convergence properties of Conference on Learning Reprexentations, ICLR 2025, Singapore, April 24-28, 2025. OpenRe- view.net.
Cai, Y., Farina, G., Grand-Clément. J., Kroer, C., Lee, C., Luo, H., and Zheng, W. (2025b). On separation between best-iterate, random-iterau iteraate and last-iterate convergence of learning in games. CoRR, abs/2503.02825.
Cai, Y., Farina, G., Grand Clément, J., Kroer, C., Lee, C.-W., Luo. H., and Zheng, W. (2024). Fast last-iterate convergence of learning in games requires forgetful algorithms. arXiv preprint arXiv:2406.106 10631.
Cai, Y., Oikonomou, A., and Zheng, W. (2022). Finite-time last-iterate convergence for learning in multi multi-player games. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A.. editors, Advances in Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA. USA, November 28 December 9, 2022.
Candogan, O., Ozdaglar, A. E., and Parrilo, P. A. (2013). Dynamics in near- pear-potential games. Games Econ. Behav. 82:66-900 90.
Cevher, V., Cutkosky, A., Kavis, A., Piliouras, G., Skoulakis, S., and Viano, L. (2023). Alternation makes the adversary weaker in two-player games, Advances in Neural Information Processing Systems, 36:18263-1820
Chen, X. and Peng, B. (2020). Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 33:18990-18999
Chotibut, T., Falniowski, F., Misiurewicz, M., and Piliouras, G. (2021). Family of chaotic maps from game theory. Dynamical Systems, 36(1):48-63.
Daskalakis, C., Fishelson, M., and Golowich, N. (2021). Near-optimal no-regret learning in general games. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 1021, virtual, pages 77604-27616
Daskalakis, C. and Pan, Q. (2014). A counter-example to Karlin's strong conjecture for fictitious play. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 11-20. IEEE.
Daskalakis, C. and Panageas, I. (2019). Last-iterate convergence: Zero-sum games and constrained min-max optimization. In Blum, A., editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 27:1-27:18. Schloss Dagstuhl Lcibniz-Zentrum für Informatik.
Farina, G., Anagnostides, I., Luo, H., Lee, C.,, Kroer, C., and Sandholm, T. (2022). Near-optimal no-regret learning dynamics for general convex games. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A., editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022.
Fasoulakis, M., Markakis, E.,, Pantazis, Y., and Varsos, C. (2022). Forward looking best-response multiplicative weights update methods for bilinear zero-sum games. In Camps- Valls, G., Ruiz, F. J. R., and Valera, I., editors, International Conference Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 Proceedings of Machine Learning Research, pages 1 11966-1 1117. PMLR.
Gidel. G., Hemmat, R. A., Pezeshki, M., Le Priol, R., Huang, G., Lacoste-Julien. S., and Mitliagkas, I. (2019). Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1802-1811. PMLR.
Hait, S., Li, P., Luo, H., and Zhang, M. (2025). Alternating regret for online convex optimization. Conference Learning Theory (COLT2025)

---

Heinrich, J., Lanctot, M., and Silver, D. (2015). Fictitious self-play in extensive- form games. In International Conference on Machine Learning, pages 803-813. PMLR.
Hsieh, Y., Antonakopoulos, K., Cevher, V., and Mertikopoulos, P. (2022). No-regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate separation. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A., editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, S 2022, New Orleans, LA, USA, November 28 December 9, 2022.
Hsieh, Y., Iutzeler, F., Malick, J., and Mertikopoulos, P. (2020). Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual.
Katona, J., Wang, X., and Wibisono, A. (2024). symplectic analysis of alternating mirror descent. arXiv preprint 2755:2240..0347..
Lazarsfeld, J., Piliouras, G., Sim, R., and Wibisono, A. (2025). Fast and furious symmetric learning in zero-sum games: Gradient descent as fictitious play. Conference on Learning Theory (COLT 2025).
Mertikopoulos, P., Papadimitriou. C., and Piliouras, G. (2018). Cycles in adversarial regularized learning. In Proceedings of the twenty-ninth annual ACM SIAM symposium discrete algorithmss, pages 2703-2717. SIAM.
Monderer, D. and Shapley, L. S. (1996). Potential games. Games and economic behavior, 14(1):124- 143.
Panageas, I., Patris, N., Skoulakis, S., and Cevher, V. (2023). Exponential lower bounds for fictitious play in potential games. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S., editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023.
Piliouras, G., Sim, R., and Skoulakis, S. (2022). Beyond time-average convergence: Near-optimal uncoupled online learning via clairvoyant multiplicative weights update. Advances in Neural Information Processing Systems, 35:22258-227 -22699.
Rakhlin, S. and Sridharan, (2013). Optimization, learning, and games with predictable sequences. Advances in Neural Informaiion Processing Systems, 26.
Robinson, J. (1951). An iterative method of solving a game. Annals of Mathematics, 54(2):296 301.
Sayin, M. O., Parise, F., and Ozdaglar, A. E. (2022). Fictitious play in zero-sum stochastic games. SIAM J. Control. Optim., 2014)4..95
Shalev-Shwarzz, et al. (2012). Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 107--107-
Syrgkanis, V., Agarwal. A., Luo, H., and Schapire, R. E. (2015). Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28.
Vinyals, O., Babuschkin, I., Czarnecki, W. M.. Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds. T., Georgiev, P., al. (2019). Grandmaster level in starcraft ii using multi-agent reinforcement learning. nature, 575(7782):350-335
Wang, J.-K. and Abernethy, J. D. (2018). Acceleration through optimistic no-regret dynamics. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa- Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.
Wibisono, A., Tao, M., and Piliouras, G. (2022). Alternating mirror descent for constrained min-max games. Advances in Neural Information Processing Systems, 35:35201-35212.
12

---

Zhang, B. H., Anagnostides, I., Farina, G., and Sandholm, T. (2024). Efficient SiphiS-regres mini- mization with low-degree swap deviations in extensive-form games. In Globersons, A., Mackey. I.., Belgrave, D., Fan, A., Paquet, U.. Tomezak, J. M., and Zhang, C., editors, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurlPS 2024, Vancouver, BC, Canada, December 10 15, 2024.
13

---

Table of Contents
1
Introduction
1.1
Our Contributions
1.2
Other Related Work
2
Preliminaries
2.1
Online Learning in Zero-Sum Games
2.2
Fictitious Play and Optimistic Fictitious Play
3
Regret Bounds for Optimistic and Alternating Fictitious Play
3.1
Intuition and Overview of Proof Techniques for Theorem 3.1
Bounded Energy Under Optimistic Fictitious Play
4.1 Subspace Dynamies of Optimistic Fictitious Play
4.2 Bounded Energy of Subspace Dynamies
5 Discussion and Conclusion
A Details on Regret, Energy, and Fictitious Play
15
A.1 Zero-Suma Sum Games and Convergence to Nash Equilibrium
15
A.2 Proof of Proposition 3.4
15
A.3 Details on Fictitious Play Variants as Skew-Gradien Descent
15
B Assumptions Payoff Matrix
16
B.1 Proof of Proposition 4.1
16
B.2 Proof of Proposition 4.2
17
C Proofs for Optimistic Fictitious Play Regret Upper Bound
18
C.1 Properties of the Energy Threshold B
18
C.2 Energy Upper Bound: Proof of Lemma 4.9
19
C.3 Cycling Invariants and Non-Increasing Energy Growth: Proof of Lemma 4.10
19
Proofs for Alternating Fictitious Play Regret Lower Bound
22
D.1 Details Alternating Play and Alternating Regret
22
D.2 Details Alternttnn Fictitious Play
24
D.3 Proof of Theorem 3.2: Regret Lower Bound on Matching Pennies
24
Additional Experimental Results
27
E.1 Details on Experimental Setup
27
E.2 Empirical Regret Comparisons of Fictitious Play and Optimistic Fictitious Play
28
14

---

A Details on Regret, Energy, and Fictitious Play
A.1 Zero-Sum Games and Convergence to Nash Equilibrium
Proposition 2.1. Let कं = t =f) and zy = = xh)) denote the time-average iterates of Players and respectively, and suppose Reg(T) = o(T). Then (oī ..a converges (in duality-gap) to an NE of A at rate of Reg(())T o(1).
Proof. By definition of Reg(T) from (1), we have that
Reg(T")
E t= mb))
(s, A ( x DG +4)
max
(x,, A
min DE
ZEAm
where we use the definitions of Ø and 722 and of the duality gap DG :). Thus if Reg(T) = of (T)
then DG oo Reg(T) o(1).
A.2 Proof of Proposition 3.4
In this section, we prove Proposition 3.4, which shows the equivalence between energy and regret. Restated here: Proposition 3.4. Let {x²} and {v'} be the iterates of (OFP). Then Reg(T) (yy+
Proof. For convenience, we let d = m + n, and we write X' = Am x A.. Then recall from Definition 3.3 that for all y E Wdd, the energy function Rd + R is given by
Vry)
max ==())
{xr, y)
(15)
for y = (y1, y2) E Rd. Using the definitions of regret from from (1) and of the dual variables from Definition 2.3, we have
T
T
Reg(T)
max
211
Axh
min 2IEA,
x2:
Taa
# mAaAm
= max
(11,yl Vi
T+1)
+
max
(12,
+1)
21EAm
22EA..
(x, T+1)
max
= (17+)).
A.3 Details on Fictitious Play Variants as Skew-Gradient Descent
In this section, we give more details on the geometric viewpoint of Optimistic FP and standard FP introduced in Section 3.
Dual dynamics of fictitious play variants. that its subgradient set at y E Rd defined as
First, we recall that for a convex function H Rdd - IR
(H = {g E Id :Y Rd H(2) 2 Hyy + (g. --)-
(16)
Let = m Then for the energy function V from Definition 3.3, it follows that, for any y Rd the subgradient set ()) is the set of maximizers (v) = argmax are xA, (x, y). The next proposition (originally stated in Section 3) then follows by (1) using the definition of standard (a 0) and Optimistic FP (a = 1) from (a-OFP), and (2) by the definition of the dual payoff vectors.
Proposition 3.6. Let {y') denote the dual iterates of either standard Fictitious Play (e.g. (a-OFP) with = 0) or Optimistic Fictitious Play. Then for all 2 1, the iterates of each algorithm evolve as
y' ---1+ - J
0 A 0) where J = -AT
(-A-
y² 2yy yy
for FP
xt Du (v++)
and g(+1
(3)
for OFP
and it follows inductively that t y' J.N where 2V (T denotes a fixed vector in the subgradient set of v at a if-t1
15

---

One-step energy growth of FP variants. Using Proposition 3.6, we can then derive the bounds on the one-step energy growth under FP and Optimistic FP, as stated expressions (4) and (5).
For standard FP, using the convexity of v and Jensen's 's inequality (equivalently, the subgradient definition from (16)), and letting (y) denote fixed vector in the subgradient set of v at y, have for all 2
V Avy)'
( ( v(y') z (O)))") 1 - v²)
= (ov (1") (O = (iV()"), JOV = 0.
Here, the first two equalities follow by the inductive update rule for from Proposition 3.6, and the final equality follows by skew-symmety of J JJ (since Jv) = 0 for all E IR4).
For Optimistic FP, again using the subgradient definition of expression (16), we have for 1: (v = (yy (''' v (av()*))))
(aV(y Ja
where the equality uses the update rule from Proposition 3.6 for Optimistic FP. Thus, by the skew- symmetry of J, and as explained in Section 3, the energy growth (v( for Optimistic FP is non-positive whenever
(yt) = av = O2 - 1)
B Assumptions on Payoff Matrix
Recall from Section 4 that in the proof of Theorem 3.5 for the 2x2 setting, we make the following assumption on the entries the payoff matrix:
Assumption 1. Let A E R2x2 Assume that
{ ii) det A = ad bc
A
d where
{1)
a, max b, c}
In this section, give the proof's of Proposition 4.1 and Proposition 4.2. Proposition 4.1 establishes that the conditions Assumption hold without loss of generality, and Proposition 4.2 derives the resulting subspace invariance property of the payoff vectors under A.
B.1 Proof of Proposition 4.1
We restate the proposition here:
Proposition 4.1 (Bailey and Piliouras (2019)). Let R have a umique, interior NE, and let {at) be the iterates of (OFP) on A. Then there exists A E IR2x2 satisfying Assumption 1 such that (1) A and A have the same NE and (2) the iterates (z'} of running (OFP) Á are identical to {x*).
The proof of Proposition 4.1 follows from the arguments in Bailey and Piliouras (2019, Appendix D). For completeness, we re-derive the full proof here.
Proof. Fix A, and let (x], A2 A2 denote its unique, interior equilibrium. coordinates oj and 25 are given by
Then the
d
a
d-b aad--ttto (17) 2 a d (b c) a atd (odd((+)))))
a-c
o a - (b (b)c)) + d (b (b+
Suppose that A does not satisfy the conditions of Assumption 1. We will then construct Ā 2 that both satisfies the assumption, and such that the two claims of the proposition statement hold.
For this, suppose that the entries of A are shifted by the same additive constant and define the best responses u and o'
= argmax (Ei, Az) (el.ea)
(18)
o' argmax (er, (A+cl)x) argmax (ei, Ar) + c, (e),)))
(19)
c.Eler,22)
16

---

where z E A2 and 1 E IR is the matrix of all ones. Thus for fixed sequence of tiebreaking rules (e.g., the same udversarially--hhn determine v²), it follows that the primal iterates of running (OFP) on A will be identical to those of running (OFP) on (A + cl) (and note the same argument holds for any FTRL algorithm or variant, including standard Fictitious Play and Alternating Fictitious Play).
tiebreak direction that is applied to determine is also applied to
Now suppose det A + O. Let Á be the matrix
Ā A- (a det
(a+d d - (b (b+c) .1
By straightforward calculations, follows that det A = 0. Moreover, by (17), À has the same unique interior Nash equilibrium as A, and by the arguments above, the iterates of running (OFP) on are equivalent to those on A. Thus without loss of generality, we assume det A O.
We now establish that we can assume a > max (0, b, cf without loss of generality. First, we show j 0 holds: by the assumption that det A = ad be 0, if a 0. then be 0. However, by (17) and the assumption that z5) is interior, we must have a C + 0 = & O, which implies b 0. This violates the constraint from (17) that b = b & 0, and thus without loss of generality,
a * 0. To show without loss of generality that also a > O, observe that the bilinear objective of the zero-sum game is given by
max min (2), Arz) max min (x), AA2) max min (12, -A #1 EAE #2E
ET m2EA;
#2E EA2
Thus, by switching the maximization by -I), we may assume that a > 0. Finally, to show a > max(b, e} holds without loss of generality, observe from (17) that if + d - (b + > 0, then the interior Nash condition in (17) implies a >> and a > If instead a + d - (b + c) < 0, then < a < min (b, c), and we can then rewrite the bilinear objective of the zero-sum game using a new payoff matrix with relabeled strategies (i.e..
minimization role between the players (via scaling the matrix
permuting the columns of A), as
max min (x1, Axz) = max min (I1. A d'x2) where A'= (a :) 1EA2
(20)
E2 22EA2
Under A', we have b + c- (a d) O, which from (17) and the reasoning above implies b > max(a, d} > O. As a consequence, by possibly permuting the columns of and relabeling the strategies of Player 1, we can assume in either case that > max c}. Together, we conclude that max(0. b, c} holds without loss of generality.
the assumption
Similarly, it follows that we may also assume d > max b, c} without loss of generality. Specifically, using the relabeling argument above, may assume interior Nash and det A = 0 assumptions, it follows from (17) (using similar arguments as for a # 0) that d A 0 and d > max(b, cj. Moreover, as a 0, if also d O, then this implies c, < meaning det A = ab - ed < O, contradicting the assumption that det A = O. Thus also d > 0, and we conclude that the assumption d > max(0, b, e} holds without loss of generality.
d (b (b++ c) O. Then under the unique
B.2 Proof of Proposition 4.2
We restate the proposition here for convenience:
Proposition 4.2. Let A satisfy Assumption 1, and let {vf} and {uh} he the dual payoff vectors of (OFP). Then for every > 1, holds that v -Pi vi and vhz -P2 V21 where
P1 = (d (a b) > and p2 = (d - b)/((a > 0.
Proof. For player 1, let 01 = (d - c, a - b). Then observe that
a d 6) = (dd - ac + ac - be
bd be ad bel = (0)
A A
b
where the final equality follows from the assumption that det A = ab - cd = 0. Then for any x E Ag. we have
0 (I, AT.ATor vn) Az).
17

---

As vi - Ard this implies
vi) =
Σ ==1
(01, Ar2) 0.
Thus for t, we have (1), vi) = (d - c) vi1 + (a b) v12 - 0. Rearranging, and recalling that
Pi :- cddcc/(u b) > 0 (where the inequality follows by Assumption 1), we find v -Pi 1 vi1
For the second player, let 22 ADs = 0 E I and thus
b, c). Using similar argument and calculation, we have
[-1 Σ
(12, v2)
Σ (v2 -A
(aa Au2) 0.
k=1
For all f, it then follows that (02, 1/2 (d- b) b),2))2211 121 + +a (a- .222 = 0, meaning v/2 - P2 -2-121-
C Proofs for Optimistic Fictitious Play Regret Upper Bound
In this section, we develop the omitted proofs from Section that are needed to establish the main technical result of Theorem 3.5 (showing Optimistic FP has bounded energy in 2x2 games).
C.1 Properties of the Energy Threshold B
In this section, prove several properties related to the threshold B that is used in the proof of Theorem 3.5: Recall that B is defined as follows:
Definition 4.7. Fix A satisfying Assumption 1, and recall Omax = || alc Then define > 0 by
min {6 e R+ for all R2? || S 60max
</(2) S b)
First, we prove the following upper bound on the magnitude of B with respect to the constants Qmaxe P1, and P2:
Proposition 4.8. Let B be the constant from Definition 4.7. Then B < 60max (1 + Pt + P2).
Proof. By definition of B, the level set L = {a E R2 (=)) B} must intersect the boundary of the ball { F² | $ B} on least one of the boundaries P=-(1+1) in the set P from Definition 4.3. Let = P n Bn C be the intersection of these three sets. Using the definition of vi from (10) follows that for
P1 21 P1 6a
if z E Piw2 if E P2~3 if E P3n4 x E PA-l
F2
60max
B = (12)
F1
60max
P2 22l = P2 6amax
where in each case the equality comes from the fact that if E I then ||^||| 6a follows that
B < 6amax max {1, 11, P1, P2) 60 P1 p2),
where the final inequality comes from the fact that Pl. 0.
Next, we establish the following invariant:
Proposition C.1. Let B be the constant from Desinition 4.3. Suppose (1)) > and suppose
2 E P; U P(--)) for some i [4]. Assume either ž = = Sq or z== = 2 S, + Sx for j. [4] and
S as in (OFP Dual). Then
2 Φ P,42 U P(+1))((2))
(21)
18

---

Proof. We prove the claim for the case that ž = 2 S, + Sk. which by the same argument implies the result when ズ + Sj. Without loss of generality, assume i 1. Under the assumptions of the proposition, we will show that if 2 E Pi UUUPP Pa~l, then ā & P3 U P2-3. For this, observe first by definition of B that if (x) > B then |=||a > 6dmax- By definition of the sets P1 and P3 U P2-3, this implies that
60max
min P'PPs
1 22122 2 ||212 2
1211/
2
40max
(22)
V2
V2
On the other hand, by construction of 2, and using the fact that ||S||2 S 20maax we have
|| - 2||2 < || + 1 S 2((2mmax) = 44mmx
(23)
Then combining expressions (22) and (23), we find
|| 2
min x' e'EPss
12-2'112
and thus 3 Ps U P2~3-
C.2 Energy Upper Bound: Proof of Lemma 4.9
This section gives the proof of Lemma 4.9, which derives an upper bound on the energy (22++1
when (b²") I B. Restated here:
Lemma 4.9. Suppose v(=t) & B, and let B' = 80 (1 P1 + p2)2. Then (b2 s B'
Proof. Using the definition of dh from (10), observe that 1( < max { max(p1, P2) ||
++ 111, || S (1+ P1 + P2) -2))112++111 1122+1111
(24)
Now recall by definition of the constant B that v0(2t) S B = || s B. Then as || ||2 + SyIlı for some j E [4]. we have that
|| S || + 20max
B + 20
6a (1 pl p2) + 22mmxx
W1 80max (1 + P1 + P2)
(25)
Here, the penultimate inequality follows from the upper bound on B from Proposition 4.8, and the final inequality follows from the positivity of P1,
Combining expressions (24) and (25), we conclude that
(1+++1) < 80max (1 + p1 + p2)2
C.3
Cycling Invariants and Non-Increasing Energy Growth: Proof of Lemma 4.10
In this section, we develop the proof of Lemma 4.10, restated here:
Lemma 4.10. Suppose (xx') > and at E P. e [4]. Then the following hold:
(I) Either (i) +1+ ++ E P or (i) z+ , e P+41
+1
(2) Ap(2*) = (1) (x*)) < 0.
We give the proof of Lemma 4. in two parts: first in Lemma C.2 (Section C.3. prove the invariants from Part (1). Then, Lemma C.6 (Section C.3.2), we prove the non-posinn non-positive energy growth bounds from Part (2).
In Figure 3, we also give visual intuition for the two claims of Lemma 4.10. In the figure, each subfigure shows the dual space R and the green region denotes the sublevel set v5(2) S B. The left subfigure illustrates that for (==))= > B, the vectors z++1 and g*+1 will lie the same region of P. and thus A1)(2') < 0 (the latter point is captured by the fact that z++1 lies within the sublevel set (b))) S B). In contrast, as illustrated the right subfigure, when (x2x) & B, then in general the invariants of Part (1) of the lemma may not hold, and (2)(2)) can be strictly positive.
19

---

((2)
z t111
z
z
z
zt1
gt+1
g++1
z zt+1
22
Z/
Figure 3: Visual intuition for the claims and proof of Lemma 4.10.
C.3.1 Cycling Invariants: Part 1 of Lemma 4.10
In this section, we state and prove the following lemma, which establishes certain "cycling invariants" on the relationship between the predicted cost vector g++1 and true cost vector 21+1 that hold when the energy (²²²) is sufficiently large.
Lemma C.2. Suppose (=²) > B and x' E for i E (4). Then either
(i) g++1 E P, and ++1 E P., or
(ii) g+t E Pi+1 and 21+1 E Pi+1-
Proof of Lemma C.2. The proof of Lemma C.2 proceeds using three separate propositions, which we state and prove as follows:
First, we establish regions in which 3++1 and 2 cannot lie when the energy vf is sufficiently large. Proposition C.3. Suppose (x²)) > B and 2 P. some [4]. Then
z++1 241 & L Cu2UUP(411 U
Proof. We first show that z4+1 , 111 & P442 ((442)((42)) For this, recall that both 24+1 = + and g++1 = + S₁ for some j. k E [4]. As wxz²) > B. then applying Proposition C.I implies that both 211 1111 & Pi+z (((41))((++2)
Next, we establish that 24+1 $ P._.. For this, x' P.. then either (a) g++1 P or (b) ge+1 E Pi+2 ((++))((+2)- We have already established case (b) cannot hold. Similarly, as (222) B implies ||2$|] 30maxx then case (a) implies that either (b(2) B or 2t+1 P.-1. which is contradiction. So 2+1 $ P
Similarly, have z++ P.-1. then by definition of S we must have either (a) - - S or (b) - = S:+1- Case (a) implies Et P.42 U P(G-1)~(H42) which cannot hold due to Proposition C.I. Case (b) implies zt P.+1 U PPo(it1). which again due to the definition of B
=
contradicts that either v0(=") > or that gt+1 E P.-.. Thus we conclude g++1 & P.-
-++1,2t0 Proposition C.3 establishes that (x=²)= > B, then we must have g++1 2111 E P. P1-1. Thus to conclude the proof of Lemma C.2, it suffices to establish that z++1 E P: = 2041 E P: and that zt+1 P++1 = 2++1 P.+1. We prove these claims in the following two propositions:
Proposition C.4. Suppose (x22)) B and z' Poror some i [4]. Then:
z++1 E P.
+ 2 E P.
20

---

Proof. We distinguish the cases when 2 E P. and 21 E Pi-(i+1). In the first case, if z E P.. then by definition 2²+1 = 2t + St If (b
,x²"), then 21+1 g++1 E P. If instead - S for some j * E [4]. However, by definition of the
))=-11 * (z*), then ø++ constant B, we must have 21 & Pi+1, as otherwise the assumption 1b(2)) B would be violated. Then Proposition C.3 implies 2t E P.. Thus if 2 E P. then 2 E P..
For the second case, suppose g++1 E Pin(i+1). Then we must have g++1 2' E {St, S.+1). Moreover, recall that Q(*++) E {es; }. In either case, using the structure of adjacent columns i and i of S, follows that 2t=1 E Pin(+t1) P.. Thus if g++ Piv(-11). then also 2 E P.. which concludes the proof.
Proposition C.5. Suppose (x²)) > B and 2t E Poror some i E [4]. Then:
2+1 P.+1 = 2 E P.+1.
Proof. Suppose z' E P. 1 P.+1. then Q(2 e++1. and also 241 - E {S S Using the structure of adjacent columns and it of S, it then follows that =++1 x' + Si+1 E P.+1-
Similarly, if instead z' E (.-(+1)). then z²+1 x' + S141 E Pi+1 by definition of S. Thus in either case, if g++1 Pi+1, then also 2t+1 E Pe+1-
C.3.2 Non-Increasing Energy Growth: Part (2) of Lemma 4.10
In this section we state and prove the following lemma, which gives non-positive bounds on the energy growth under the two cases in Part (I) of Lemma 4.10:
Lemma C.6. Fix E [4], and suppose 2' P.. Suppose that either (i) E+1 E P, and 211 P. or (ii) g E P.41 and +1 E P.+1- Then AD(2*) S O.
Proof. To start, we rederive the one-step change in energy growth under (OFP Dual).
One-step change in energy: Using (OFP Dual) and Definition 4.5, we have for any t 2 1:
ax))")
((2 (²²")
(26)
(M(= (=',
(27)
(2' SQ(E+)), ).QE+)). - (Q(2))))))
(28)
(2), (Q(=
- Q(x+))))))))))))))))))))))))QQ + (Q(E++)), (M(=*+1)
(29)
By the definitions of S and M from expressions (OFP Dual) and (1 I), respectively, recalling that P1 (d ca b) and P2 = (d b)/(a c). and using the fact from Assumption that
det A = ab ed = 0, we can compute
b
0
d
b
b d
STM M a c
P1
P1
1
C d
a - c d
(30)
P2
1
1
P2
0 b
a
b a b a
Thus, expression (30) shows S M skew-symmetric.
Proof for Case (i): To prove the claim for case (i) of the lemma, we start with the case that 2¹ E P;
and also 34+1,2 E P,. Then by definition of Q, we have Q(z') Q(3++1) Q(3") 6;- By skem-symmetry of S M, observe in part (b) of expression (29) that
(Q ST MQ()++1)) = (Q(2 MQ() = 0.
Moreover, in part (a) of expression (29), we also have
( 0, M -
21

---

and thus (x² = O. In the case that 2" E P. and 3 E Pa-(e+1), then observe from the structure of S that we must also have 2 Pir(i+1)- Then by definition of v) for any E (i-(i+1) we have (z) = (z, Me,). Thus we can rewrite expression (26) as
Arb(2') = (2' +='+ -5(E"(("-))) Me,) - ,=', MQ(=)) = (2", Q(="))) + (Q( MM))
(31)
(32)
As x E P. = Q(z") ei the first term above vanishes. Moreover, as 3H E (i)(+1)) we have Q(=++1) fer, e. ). By skew-symmetry of S M, Q(=*+1) = then the second term of (32) also vanishes. On the other hand, if Q = e++1, then the second term is negative, which follows from the fact that, under Assumption 1, each entry (ST MM), O. In either case, find Ab((*) S O.
Finally, observe that if 2' E 1)- then by definition of (OFP Dual), we cannot have both 3++1 , E P.. Thus the conditions of case (i) do not apply, which concludes the proof of the lemma under case (i).
Proof for Case (ii): To prove the claim for case (ii), suppose first that 2f E P, and thus Q(=²) Cz- By the assumptions of claim (ii), we also have Q( )) = Q(=(+1) = Ei41. Thus it again follows by skew-symmetry of S M that for part (b) of expression (29)
(Q( MQ(='t)) 0.
(33)
For part (a) of (29), by case analyis on the columns of M, it follows that when Q(z²) and Q)2++1) = Cs+1, then
(1 + p2) 2
Qf* = 61
(1+P)) -2.
if = e2
( =
(34)
-(1 p2)
Qf C3
- (1 + -2)
ifQ(z*) 64
Given the definition of Q, it follows that Q(2*)
22 < 0, that Q(=") e2 of < 0.
that Q(2²) = E3 + z/ 2 O, and that Q(=²) = e4 of 2 0. Together with the fact that
P1.P2 > by definition, each case of expression (34), we find (2', (M,,((((*+))) Q(²))) s
Together with (33), this means (+)(2') S O.
In the case that 2² E Pi-(i+1); then either Q(z') = 6; or Q(2*) = 6++1- If the latter holds, given that also Q(z = e;-1 by assumption, then part (a) of (29) is trivially O. If the former holds, we recover the cases of expression (34), and thus part (a) of (29) is non-positive. In either case, part
(b) of (29) remains as in expression (33), and thus we conclude that (v(2*) < O. This proves the
lemma under case (ii).
D Proofs for Alternating Fictitious Play Regret Lower Bound
In this section, we develop the proof of Theorem 3.2, which gives lower bound of 1( on the regret of Alternating Fictitious Play. Restated here:
Theorem 3.2. Suppose 2 = (p, 1 p) E for irrational p E (3/4, 1), and let {a*} } be the iterates of Alternating FP on (Matching Pennies) using any tiebreaking rule. Then Reg'l 2 ((VT).
The organization of this section is as follows: in Section D.I recall the setup of alternating play in zero-sum games, as well as on the notion of alternating regret. In Section D.2, we formally define the Altemating Fictitious Play algorithm. Finally, in Section D.3, we give the proof of Theorem 3.2.
D.1 Details on Alternating Play and Alternating Regret
Alternating play. We consider the model of alternating online learning in two-player zero-sum games as in Bailey et al. (2020); Wibisono et al. (2022); Katona et al. (2024). Defined formally: Definition D.1 (Alterating Play). Fix a payoff matrix E Rmxn, Over T rounds, Players and alternate updating their strategies z Am and æh e An follows:
22

---

Assume without loss of generality T even. At time t = 1, Player chooses an initial z A.. and Player 2 observes -A" xi.
(Initiaizzatio)
(Even rounds- Player 2 updates) When t 2k (for k 1):
Player sets zí = x1-1 E Am
Player 2 updates z E An.
Player observes Ar
Player observes - A x 1-1
(Odd rounds - Player 1 updates) When 2k + (for k 2 1):
Player I updates zi Am
Player 2 sets 2² 4/2 E An.
Player observes Axi Ax--1
Player 2 observes A AAzi.. z1.
Alternating regret. Under alternating play, we now measure the performance of each player by its alternating regret (Wibisono al., 2022; Cevher et al., 2023; Hait et al., 2025). For this, first observe under alternating play that each player's ' cumulative payoff can be written as:
T/2
Player cumulative payoff::
1
2k
A(22
2h
+ +
2k 1)2
k=1
(35)
T/2
Player 2 cumulative payoff: Σ A (12 + x 1)
Here and throughout, we assume for notational convenience that z. 0 E R² and æ T+1 = 0 E R"
Then alternating regret defined as follows:
Definition D.2 (Altemating Regret). Let T be even. Define Reg! (T) and RegE (T) as
T/2
Regl (T) = max aEA, m
Σ
x
2k-1 A(x22 + 2 2)
k=1
T/2
Reg all
(7) = min REA..
2
I, A Txu2ttt + 1)
k=1
Then define Reg"l (T) = Regll (T') + (egg((T)
Similar to standard (simultaneous) play, sublinear regret bounds for Reg correspond to conver- gence of the time-average iterates under alternating play to a Nash equilibrium of A. For this, define the time-average iterates x²"' Am and To E A, by
T/2
T/2
i
T
Σ
1
2k-1 1
+ x1
2k+11
and Y = T
2
2k-2
+ x
2k+2
(36)
k=1
k=
Then we have the following proposition (analogous to Proposition 2.1 for simultaneous play): Proposition D.3. Fix A Rmxxn Let oी Am and ThL An, denote the time-average iterates
under the alternating play Definition D.2, as in expression (36). Suppose Reg (T) S a= =
Then (TT 23 converges in duality gap to an NE of A at a rate of oz o())
Proof. By definition of the player-wist wise cumulative costs from (35) (and recalling that set x9-
0 E _2n and 27'+1 0 E Rm for notational convenience), observe that
T/2
T/2
Σ
x
2k-1
A
24 + x2 2)-
2k
A (a 2k+1 + xt =b--1)) 0
It follows from the Definition D.2 that
(Tg) Regil (T) + Rega (T)
T/2
T/2
max
Σ
(r, A( 2k
+ x22
2k 2)-
min
xr A (122++) + +x2 22
Am
k=
Am
max AE
(I, A(T 3
min YEAn
(I, A (T x < a
23

---

where in the final line we use the definition of कं and Z2 from (36) and the assumption that
Reg(T) a. Then dividing by T gives
DG
max #e
(o,, (r,) min zEan
(a, A 11 S T
which yields the statement of the proposition.
D.2
Details on Alternating Fictitious Play
Under the alternating play setup of Definition D.I, now specify the Alternating Fictitious Play algorithm. For any even 2 2, the primal iterates of Players and 2 at times t and t + 2 update according to
1/2
[+1 = argmax (x,,
A(r²
+ +.2 2) and x2² = 2
(e(e:)
1=1
f/2 2x+1 A (a
1+2 argmax (x.
+ x22 2(--1)) and #1
[++
22
(e(e.)
1=1
In other words, as in standard Fictitious Play (c.f., (a-OFP) for a 0), in Alternating Fictitious Play each player (in an alternating fashion), selects the best-response to the cumulative observed payoff vectors over prior rounds.
Primal-Dual update for Alternating FP. Similar to the analysis for Optimistic FP, define the dual payoff vectors yf = Ar E R and y = = - E R". Then the iterates of Alterating FP can be equivalently expressed follows:
Definition D.4. Assume the alternating play setting of Definition D.I. Let vी = 0 E I"", and let v = A T 2 E R". Then for t 2 2, the dual (i.c., (vi v5)) and primal (i.e., (z x²))) iterates of Alternating FP are given by
vi w1t1 yi + Axd (uzz v/ A AT ATa--1
(f even)
1
and
22 argmax (x, v2)
(AFP)
2 argmax E (z, vi) and
[vft1 = ví + Ar (1/2 v2 A AT
(t odd)
2
Moreover, recall the energy function T from Definition 3.3 and Reg" from Definition D.2. Then, analogously to Proposition 3.4, following equivalence between energy and alternating regret holds: Proposition D.5. Let {x'} and { be iterates of (AFP). Then Reg (T) (1+
D.3 Proof of Theorem 3.2: Regret Lower Bound on Matching Pennies
We now prove the lower bound on the regret of (AFP) on Matching Pennies. For this, recall that the Matching Pennies payoff matrix is given by
A [1 -)
(Matching Pennies)
Subspace Dynamics of AFP for Matching Pennies. It is straightforward to check that (Matching Pennies) satisfies the conditions of Assumption 1. Moreover, this also implies Proposi- tion 4.2 holds for the dual iterates of (AFP), in particular for P1 = P2 =
Thus, to prove the theorem, we reuse the components of the subspace dynamics introduced in Section 4. Specfically, reuse the notation the primal and dual iterates (w') and {=(), well as the choice map Q from Definition 4.4, and the energy v from Definition 4.5.
Under (Matching Pennies), it is then straightforward to check that the matrix S from (9) and the energy si from Definition 4.5 are given by:
(11
(-1 1 1
=)
and for all RR: (2)) = ||

---

Similarly to Proposition 4.6, and using the definition of & and the iterates {2r) } we also have the following relationship between and th:
Proposition D.6. Let { be the iterates of (AFP) (Matching Pennies), and let {2²) be the corresponding subspace iterates. Then (1y"+t) = ()
Moreover, under the primal-dual definition of (9) it follows inductively (and using the definition of {w"), {2"}, and Q) that for all 3:
[Q((=) ,5)) for f even (0(
wf
(37)
for t odd
Then for 1 that the dual iterates {=9} can be further rewritten as
(2 (= 1
for & even for i odd
2 t+1 = SQ(2*+!) where 2
(AFP Dual)
Thus, similar to (AFP Dual), the subspace iterates of Alterating Fictitious Play can be expressed with respect to predicted payoff vector z*+1, Now, due to the alternating play setting, the position of this predicted vector depends on the parity of l.
Overall proof strategy. Given the equivalence between (T') and My from Proposi- tion D.5, and on the equivalence between (yy+I) and ((2++) from D.6, to prove Theorem 3.2, suffices to establish the following lower bound on the energy (==T+I);
Lemma D.7. Assume the setting of Theorem 3.2, and let {='} be the dual iterates of (AFP Dual).
Then (2 2 ((VT).
To prove Lemma D.7, we introduce a phase structure (in similar spirit to the analysis of Lazarsfeld et al. (2025)), where each phase tracks subsequence of consecutive time steps where the iterates {w*} are at the same primal vertex. Formally, we define:
Definition D.8. Let {w"} be the primal iterates from (37), and fix to = 2. For 2 1, let ty := minft > f f w² * w Then define Phase i as the subsequence of iterates from times t t= tk, to + 1. 1.... tk+1 - 1, and let Tą = tx+1 t& be the length of the phase. Let K 2 0 denote the total number of phases in T rounds such that T = Ei=o Tk-
Using the phase setup of Definition D.8, the core technical component of proving Lemma D.7 is to establish the following proposition:
Proposition D.9. Assume the setting of Theorem 3.2. Then for each Phase 1, 1...., K, the following hold:
(i) (=**) S (1=+t-1)) +2
(ii) ((b(zt)))
Moreover, for at least phases holds that (iii) (x**k) 2 (b(k 1) 1.
The proof of Proposition D.9 is developed in Section D.3.1. Granting the claims of the proposition as true for now, we give the proof of Lemma D.7 (and thus also of Theorem 3.2):
Proof (of Lemma D.7). By claim (iii) of Proposition D.9, the energy v is strictly increasing in at least K/2 phases, and thus
K
(38)
2
To prove the statement of the lemma, it then suffices to derive lower bound on For this, recall by Definition D.8 that T _K_ Te. Moreover, combining claims (i) and (ii) of Proposition D.9, we (2 (e < (kk). Combining these pieces, we have
1=
find for all k that T. O
K T
K
<
(k) < (
(39)
A=
km
Thus 2 2 ((T)
K 2 l ((VT). Substituting into (38), conclude 4/22 ((2T+1) ((vT))))
25

---

D.3.1 Proof of Proposition D.9
We now prove the claims of Proposition D.9. For this, we start by establishing the following invariant between the dual iterates z²-1, x
, z(t1 and the predicted vector 34+1
Analysis of initial phases. We begin by computing the dual iterates during the first two phases, which helps to both give intuition for the energy growth behavior of Alterntting FP, as well as to streamline the remainder of the proof. For this, recall that initially x2 = (p. - p) E A2 for irrational p E (3/4, 1), and that of 0 E IR?
It follows by definition of (AFP) at time = 2 that vi = of 0 E R and y -A (-p 1). (2p 1)), and that of = क E A2 and x = (0,1) E A2. Then, at t = 3, we further
have y = 5f + Ax3 = (-1, 1) and 1/² = v/ A at 2 y
Then for 2 3. switching to the equivalent, lower-dimensional iterates {wr) and {="). we can further directly compute (by definition of (AFP Dual)):
23 (-1,
(t=3)
w = =( 61
Ed (-1.-(2)))) 1)) Pr
x+ = 23 (-111))=
(t=
w ((3)) 61
1 = +=
Ps
51=5)
w Q( 61
E (4f (-)
2 25 (-1,)) 4p+ 5) E Ps
61=
w Q(27) = 02.
E = (9) = (-3, +5) E P2
Observe by Definition D.8 and the calculations above that Phase begins at step fj 3, and Phase begins at phase to = 6. Moreover, A = (=) = 1, meaning ()²²)) (za1) 2 > 0.
This strictly increasing energy growth between phases stems from the geometry of the predicted payoff vectors: in this instance, under Alternating Fictitious Play, when 2², 2² E Pi and z' is near the boundary P1~2, the predicted vector zz-1 always remains in P1 and fails to "predict" the next region P2. This results in strictly increasing energy growth when 21 E Ps. This positive energy growth behavior near the boundary regions is the key difference between Alternating and Optimistic Fictitious Play (c.f., the invariants and energy growth claims of Lemma 4. 10).
--1
Cycling invariants. By continuing to compute the dual iterates {2*}, we arrive at the following invariants, which establish certain cycling behavior through the regions of P. Specifically, it follows inductively that 2²11 and 2' must fall under one of the following cases (which subsequently determines g++1, 241,, and the energy growth Ax)(
Case 1: 2t-1,,0 2 E P., and 2' - --- = St. Then 31+1 E P,, and either 2t+1 P.+1 with Ad(=t) = 1, or or E P. with A8b(z)) = O.
Case 2: _11 E P., x' E P.+1, and z' = 1111 + St.
Then 21+1 E P1+1, and either z++1 E P. and Ax((t) = 1, or 7t+1 or E P41 and AD(zt) =
Case 3: 1²11 E P,, 2t E Pi-(i+1)) and 2' = 2-1 S
Inzt+1 E P., then 21+1 E Pi+1 and (=b(')) 1. gr E Pao(Ht)) then also 2411 E P with (+") E 10 depending on the tiebreaking of Q
Case 4: zt11 E Pi-(1+1) and x' E P.+1. If gr+1 e Pii(ft)), then 20+1 E PHt., and Au(2') E (0, 1) depending on the tiebreaking of Q. If E Poti, then 2411 E P.l1 and A1((2t) = 0.
Note that the cases above account for (a) the variability of z depending on the parity of 4, and (b) any variability in 2 depending on the tiebreaking decision encoded in Q. summary, we deduce from the four cases above the following consequences:
26

---

1. Between phases, energy strictly increases in at most 2 iterations. By definition of the energy function & under Matching Pennies, each one-step increase has magnitude 1, and thus (=**))
(b(2*-11 S 2, which proves claim (i) of the proposition.
2. Again using the definition of 1/ under Matching Pennies, we have (x=²) = ||="||-- The cases above then imply that each 7 = ||=||| Cj (for some aboslute constant cx). and it follows that
Th = =+)((=)), which proves claim (ii) of the proposition.
3. Finally, using the definition of under Matching Pennies, along with the fact that initially
=f 0, it holds that each zf is integral. Thus between regions P2 and Ps. and between Pa these cases, depending on the tiebreaking rule of Q, the change in energy may be zero when crossing between regions of P. On the other hand, due to the initialization z (p, 1 - p) for irrational p E (3/4, 1), it follows for f 2 that all 2 are irrational. Thus no tiebreaking occurs when the dual iterates transition between regions P1 and P2 and between P3 and Pa- Thus under transitions between these phases (which by symmetry amount for at least S2( ((KK2) total phases), we have by the cases above that energy is strictly increasing by at least 1. This proves claim (iii) of the proposition.
and Pt. one dual iterate will always lic on the boundary P2-3 or P3-4. respectively.
E Additional Experimental Results
In this section, we provide more details on the experimental evaluations from Figure and Section 5, and we also present additional experimental results. The goal of these experiments is give further empirical evidence that the constant regret guarantee of Theorem 3.5 for two-strategy games also holds in higher dimensions.
E.1 Details on Experimental Setup
First, we note that all code used to run experiments can found the supplementary material. In this paper, all experiments were run locally single personal computer.
Families of payoff matrices. Aside from the (Matching Pennies) game, our experimental evalua- tions of Fictitious Play variants are performed on three high-dimensional families of payoff matrices:
Identity matrices: Here, the payoff matrix is the n identity matrix I, (i.e., the diagonal matrix with diagonal entries all 1). Recall that for standard FP, Abernethy et al. (2021a) established O(vT) regret bound using fixed lexicographical tiebreaking.
Generalized Rock-Paper-Seisee generalization of the classic three-strategy Kock-Paper-Secisoors game. Specifically, A is the matrix with entries Ai,j given by
(RPS) matrices: Here, the payoff matrix the n x n
if = i+ + (mod n) if =f (mod n) otherwise
As 1
for all i,j [n]]
(40)
For standard FP, Lazarsfeld et al. (2025) established an O(v regret bound for all such RPS matrices (using any tiebreaking rule), including when scaled by a constant, and when the non-zero entries have non-uniform weights.
Random [0,1] matrices: We also consider n x n payoff matrices with uniformly random entries in [0, 1]. For these payoff matrices, there are no existing O(VT) regret bounds for standard FP.
Tiebreaking rules. To evaluate the robustness of regret guarantees to the tiebreaking method, we run the FP variants using both (a) fixed lexicographical tiebreaking (e.g., in Abernethy et al. (2021a)) and (b) uniformly random tiebreaking (e.g., over the entries of the argmax set).
Random initializations. To evaluate the robustness of regret guarantees to the players' initial strategies, we evaluated the Fictitious Play variants over multiple random initializations of x 26 A, (for the Alternating FP initialization from Figure 1, note that the stated initialization is for
27

---

o1 E An. as in the notation of Definition D.1). To generate random initialization I E An. we sample E [0, 1|" with independent, uniformly random entries, and normalize := e/||o|]1-
E.2 Empirical Regret Comparisons of Fictitious Play and Optimistic Fictitious Play
Regret comparisons under randomized tiebreaking. In Table 2 of Section 5, we presented regret comparisons of Optimistic FP and standard FP the three families of payoff matrices described above in Section E.I, using fixed lexicographical tiebreaking. In Table 3, we show the results of an identical experimental setup, now using randomized tiebreaking. As Table 2, the entries of Table report average empirical regrets (and standard deviations) over 100 random initializations, where for each initialization, each algorithm was run for 10000 iterations.
Dimension:
15x15
25x
50x50
Payoff Matrix
FP
OFP
FP
OFP
FP
OFP
Identity
154.4 4.2
8 1.7
162.3 + 3.4
12.9 + 1.6
166.9 + 2.2
25.0 2.3
RPS
235.2 - 6.6
2.8 + 0.5
241.5
3.2 0.9
242.9 + 5.6
2.6 0.8
Random [0, 1]
93.4 5.0
2.7
1 0.6
137.1
6.1
7.0 1.1
176.2 1
12.2 1.4
Table 3: Empirical regret FP and OFP using randomized tiebreaking. Each entry reports an average and
standard deviation (over 100 random initializations) of total regret after T 10000 steps.
As in Table 2, the results of Table similarly show that Optimistic FP empirically obtains bounded regret compared to the roughly O(VT) regret standard FP for each payoff matrix and dimension.
Additional plots from fixed initializations. To further compare the empirical regrets of standard FP and Optimistic FP, we present plots of the two algorithms run from fixed initializations, similar to Figure from Section (which also included a comparison with AFP). In each plot, consider the three families identity, RPS, and random matrices described earlier in Section E.I. Note in particular that for the RPS game (including in Figure of Section 1), for better visual comparison with the other games, we use the payoff matrix specified in (40), but scaled by the constant 2/3.
Figures 4, 5, and 6 show these comparisons for 15 x 15 and 25 25 matrices, using both randomized and lexicographical tiebreaking. In each instance, we again observe that Optimistic FP has bounded empirical regret compared vT regret of standard
15x15 Identity
15x15 RPS
15x15 Random [0.1]
150
125
OFP
OFP
OFP
100
Total
0
2500
5000
7500
10000
2500
5000
7500
10000
0
2500
5000
7500
10000
Figure 4: Empirical regret standard and Optimistic (OFP) using randomized tiebreaking on three 15 x 15 payoff matrices. For each payoff matrix, each algorithm was initialized from z! = = x2 6n and run for = 10000 iterations.
28

---

25x25 Identity
25x25
25x25 Random [0.1]
FP
FP
150
OFP
OFF
tetal Regret
100
10000
7500
5000
10000
T
T
Figure 5: Empirical regret of standard FP and Optimistic FP (OFP) using lexicographical tiebreaking on three 25 x 25 payoff matrices. For each payoff matrix, each algorithm was initialized from xi e1, x2 for 10000 iterations.
and
25x25 Identity
25x25 RPS
25x25 Random [0,1]
150
FP
FP
125
OFP
OFP
OFP
Total Regret
100
75
50
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
T
T
Figure 6: Empirical regret of standard FP and Optimistic FP (OFP) using randomized tiebreaking on three 25 x 25 payoff matrices. For each payoff matrix, each algorithm was initialized from x? 61, and for 10000 iterations.
0
29

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:
[Yes]
Justification:
Our abstract and introduction introduce the new regret bounds of our work and also mention the limitations of the low-dimensional setting.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
Yes, throughout the Introduction (Section and Discussion (Section 5), we mention and discuss the limitation of the low-dimensional nature of our main theoretical guarantees.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well vell-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
30

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Yes]
Justification:
Yes, the full proofs of all our theoretical results are developed the appendix sections of our paper. We also give proof sketches of main results in the main body of the paper.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
Yes, describe the full details of our experimental evaluation in Section E. We provide the scripts used to run the experiments in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
31

---

(d)
The authors should provide scripts to reproduce all experimental results for the new reproducible, they We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Yes, include the code used to perform experimental evaluation in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
Saaiddss/oodSuumisse
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/niis. /twpsscccppu///////// wttpcc/ccclllgpuiiicei gwwpc//gggu///eeeeeeeeeiecesssee CCte//Cooeuuiiiiccce ceommisssinnn asionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer:
[Yes]
Justification:
Yes, specify all details related to our experimental evaluation in Section R.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
32

---

Justification:
Yes, in the tables report empirical regret (c.g., Table 2 and Table 3), report averages and standard deviations over the 100 random initializations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emoor bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
Yes, in Section E we provide full details on the computer resources needed to reproduce the experiment (which are minimal).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurrpss http://aww.pp...ppaa.accaaacaaaa
Answer:
[Yes]
Justification:
Yes, the research conducted in this paper conforms, in every respect, with the NeurIPS Code Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
33

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification:
Yes, in Section 5 we mention potential impacts of our work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation. generating fake profiles, surveillance), fairesss considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer:
[NA]
Justification:
Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
34

---

12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Our paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer:
[NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
35

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer:
[NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer:
[NA]
Justification:
The research in this paper does involve LLMs as any important, original, or non-standard component.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy (https: httpp::///nuurips/ http:/psssc///oooeeeeo////////// for what should or should not be described.
36


Reviews:
[{"review_id": "fjd2MfDmov", "reviewer": "Reviewer_ySgf", "summary": "This paper studies the regret of optimistic fictitious play in $2 \\times 2$ zero-sum games. The authors show that the algorithm achieves constant regret without requiring any regularization. The main technical contribution lies in proving that an energy function (or potential function) remains bounded by an absolute constant. Numerical simulations are provided to support the theoretical findings.", "questions": "Can the authors more clearly state the fundamental challenges in extending their result beyond the $2 \\times 2$ setting, and discuss any potential directions or ideas for addressing these challenges?", "limitations": "The main limitation is that the results work only for $2 \\times 2$ games.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- The paper is very well-written. The contributions are clearly stated, the results and simulations are nicely presented, and the technical approach is easy to follow.\n\n- Zero-sum games are a benchmark setting in game theory, and fictitious play is one of the most classical algorithms. However, understanding the convergence rate of the average iterate (or regret) has remained a long-standing open problem (e.g., Karlin’s weak conjecture). Showing constant regret—which implies a $\\mathcal{O}(1/T)$ convergence rate for the average iterate—using a variant of fictitious play is a significant and meaningful contribution.\n\nWeaknesses:\n\n(1) The main result is limited to $2 \\times 2$ games, as acknowledged by the authors. While this is a natural first step, it limits the generality of the findings.\n\n(2) Since similar energy functions have already been constructed in prior work, the technical novelties of this paper are somewhat unclear.", "was_revised": true, "final_justification": "I am maintaining my score and my support for the acceptance of this work.", "rebuttal": "Thank you for reviewing our work. We are happy you found our contribution significant and our technical approach easy to follow! Below are replies to two points made in the review:\n\n**On the technical novelty of the paper.**\n\nNote that the energy function used in the analysis is equivalent to the scaled duality gap, which is a fundamental quantity of study for zero-sum games (see, e.g., Proposition 2.1 and Proposition 3.4). The technical novelty of the paper is in proving for Optimistic FP that the energy is bounded by a constant (leading to constant regret, and O(1/T) time-average convergence to Nash). This proof of bounded energy for Optimistic FP relies on new geometric insights that are different from the techniques of prior works that show \\sqrt{T} regret bounds for standard Fictitious Play (e.g., in [Abernethy et al., 2021a] and [Lazarsfeld et al., 2025]) where the energy is not bounded but in fact growing).\n\n**On extending the analysis beyond 2x2 zero-sum games**\n\nWe believe the core ideas and tools used to prove our main theorem will be useful for proving a more general result beyond 2x2 two-player zero-sum games. In short, we believe the key remaining challenge for many-action zero-sum games is to generalize the subspace dynamics machinery stemming from, e.g., Proposition 4.2 to the higher-dimensional regime, which will require additional insights.\n\nIn more detail: note that to prove the main theorem (Theorem 3.1), the analysis introduced in Section 4 is indeed somewhat specialized for the 2x2 case. However, this approach relies on the more general geometric intuition introduced in Section 3 (specifically, equation 5), which holds for all higher-dimensional two-player zero-sum games (see also the expanded derivation in Section A.3). Indeed, equation 5 implies that, for any general two-player zero-sum game, the one-step change in energy under OFP is always non-positive when the optimistic/predicted dual variable and the realized dual variable map to the same primal action under the update rule. The main technical lemma of Lemma 4.10 establishes sufficient invariants for when this alignment is true in the 2x2 case, and the proof leverages the subspace property (e.g., Proposition 4.2) for 2x2 zero-sum games with a unique, interior equilibrium.\n\nBased on our empirical results, we believe that similar invariants also hold for many-action two-player zero-sum games, and thus the high-level approach of our analysis (showing that the change in energy is always non-increasing if its magnitude ever exceeds some matrix-dependent constant) can be re-used. However, we believe that formally establishing such invariants in full generality will still require new insights, in particular due to the higher-dimensional nature of the dual iterates (e.g., the two-dimensional subspace property no longer holds). These new insights may also need to leverage structural properties of the underlying class of zero-sum game (for example, using properties of diagonal payoff matrices or skew-symmetric payoff matrices). \n\nWe believe that developing these new insights will contribute more broadly to better understanding the performance of unregularized learning in games, an area which has had an exciting recent resurgence in the past year, and as mentioned by Reviewer qaZX, also has implications for practical equilibrium computation. To this end, we believe our result and proof technique for the 2x2 case serves as a useful starting point for the learning in games community to continue to make progress in this area."}, {"review_id": "acVCZSOxDZ", "reviewer": "Reviewer_qaZX", "summary": "This work studies the performance of unregularized online learning (the fictitious play algorithm aka FTL) in two-player zero sum games.  More specifically, they analyze FTL with two classic modifications (optimism and alternation) known to improve regret performance of regularized learning algorithms in games, and establish a positive result for the former and a negative result for the latter when regularization is removed, specifically in two-action games such as matching pennies.", "questions": "Could the authors clarify where the potential approach fails for many-action games?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The positive result for optimistic FTL, though constrained to two-action games, I believe to be meaningful progress in the study of unregularized learning in games, which still has major open problems such as the weak fictitious play conjecture.  It is a genre of algorithms that is worth understanding due to their per-iterate time efficiency in solving large two-player zero-sum games in practice where the cost of computing a regularized best response is potentially high.  Also, the separation demonstrated from the performance of Alternating FTL gives grounds to the fact that optimism is perhaps the more natural modification to vanilla online learning in games.\n\nThis result is also interesting as it is somewhat unexpected to me.  The O(1) regret in two-player zero-sum games due to Syrgkanis et. al. comes from the RVU regret bound.  In the worst case, this regret bound makes no improvement over the adversarial $O(\\sqrt{T})$ rate, as to be expected due to the existence of simple Bernoulli adversaries forcing $\\Omega(\\sqrt{T})$.  However, with the added structure that the loss sequence experienced by the learner is coming from the learning of opponents in a game, we have that this loss sequence is *smooth*.  This smoothness, when plugged into the RVU bound, gives the improved $o(\\sqrt{T})$, even $O(1)$ sum of regret bound, which is sufficient for convergence to equilibrium in zero-sum games, unlike general sum games.  Thus, what astonishes me is that you can also get the matching $O(1)$ regret bound in this setting where non-regularized algorithms are inherently not smooth, having effectively infinite step size and always selecting actions at the boundary.  Accordingly, the proof technique of this result must be built in a fundamentally different way than RVU.  I find the potential argument the authors utilize instead to be quite satisfying.\n\nThe main drawback of this work is in its limitation to two-player zero-sum games, and more so *two-action* two-player zero-sum games.  As with my earlier skepticism, I find it unlikely that you will have a positive ($O(1)$ regret) result for unregularized learning in multi-player general-sum games as these learners lack smoothness.  Also, the potential argument as presented here does not seem to have hope to extend to many action two-player zero-sum games.  That said, the class of two-action two-player zero-sum games is sufficiently rich to establish learning-in-games lower bounds for even regularized algorithms without optimism (i.e. MWU having $\\Omega(\\sqrt{T})$ regret in matching pennies a la Chen and Peng).  So, the fact that you get a positive result for even matching pennies, as long as you are using optimism, even without regularization, I find to be a meaningful result standing on its own when juxtaposed to the Chen Peng result.  Thus, I recommend the acceptance of this result despite the aforementioned limitations, and perhaps the publicization of this result will encourage others to attempt to tackle the unregularized, optimistic, many action, two player zero sum setting.  A positive result there could be a potential boon for practical equilibrium computation.", "was_revised": true, "final_justification": "I stand by my positive assessment.", "rebuttal": "Thank you for reviewing our work. We are glad you found the main result meaningful and surprising, and we agree that our results can help set the stage for interesting followups and more progress in the area! Below we reply to the question asked in the review:\n\n**On extending the analysis beyond 2x2 zero-sum games**\n\nWe believe the core ideas and tools used to prove our main theorem will be useful for proving a more general result beyond 2x2 two-player zero-sum games. In short, we believe the key remaining challenge for many-action zero-sum games is to generalize the subspace dynamics machinery stemming from, e.g., Proposition 4.2 to the higher-dimensional regime, which will require additional insights.\n\nIn more detail: note that to prove the main theorem (Theorem 3.1), the analysis introduced in Section 4 is indeed somewhat specialized for the 2x2 case. However, this approach relies on the more general geometric intuition introduced in Section 3 (specifically, equation 5), which holds for all higher-dimensional two-player zero-sum games (see also the expanded derivation in Section A.3). Indeed, equation 5 implies that, for any general two-player zero-sum game, the one-step change in energy under OFP is always non-positive when the optimistic/predicted dual variable and the realized dual variable map to the same primal action under the update rule. The main technical lemma of Lemma 4.10 establishes sufficient invariants for when this alignment is true in the 2x2 case, and the proof leverages the subspace property (e.g., Proposition 4.2) for 2x2 zero-sum games with a unique, interior equilibrium.\n\nBased on our empirical results, we believe that similar invariants also hold for many-action two-player zero-sum games, and thus the high-level approach of our analysis (showing that the change in energy is always non-increasing if its magnitude ever exceeds some matrix-dependent constant) can be re-used. However, we believe that formally establishing such invariants in full generality will still require new insights, in particular due to the higher-dimensional nature of the dual iterates (e.g., the two-dimensional subspace property no longer holds). These new insights may also need to leverage structural properties of the underlying class of zero-sum game (for example, using properties of diagonal payoff matrices or skew-symmetric payoff matrices). \n\nTo reiterate, we believe that developing these new insights will contribute more broadly to better understanding the performance of unregularized learning in games, an area which has had an exciting recent resurgence in the past year, and as you mention, also has implications for practical equilibrium computation. To this end, we believe our result and proof technique for the 2x2 case serves as a useful starting point for the learning in games community to continue to make progress in this area."}, {"review_id": "vf0E0KR9tw", "reviewer": "Reviewer_kPJF", "summary": "The paper demonstrates that constant regret can be achieved with Optimistic Fictitious Play (OFP) without regularisation in two-player zero-sum games, and the key contribution is identifying that constant regret is possible by associating primal variables with enumerated game states, represented by vertices of the joint simplex. The authors leverage geometric insights and a Lyapunov-esque energy-function framework to establish a constant (joint) regret bound. Experimental evidence is provided suggesting that OFP enjoys the same constant-regret properties in higher-dimensional games.", "questions": "* Upon reviewing the proof, I don't see any obvious obstacles precluding direct generalization to higher-dimensional games. Is the primary bottleneck in extending results from 2x2 to higher-dimensional settings solely related to a generalization of Assumption 1 and Propositions 4.1 and 4.2? Would addressing these issues require only a more careful analysis of the relevant subspace dimensions, or might it necessitate different mathematical tools?\n* Do you have theoretical insights or intuitive explanations for why constant regret empirically holds in larger-dimensional games despite the theoretical analysis currently covering only 2×2 settings?\n* In some practical cases, the ratio $a_{\\max}/a_{\\min}$ might significantly exceed the actual realized losses. Could a tighter regret bound potentially be derived, possibly depending on the trajectories observed or norms of the subset of the payoff matrix A realized during play? Might gradient-adaptive methods provide tighter bounds here, even though they typically incorporate regularisation?\n* Regularised methods often exhibit greater robustness against perturbations in the payoff function. Given this, could the authors comment on how robust OFP is to noise or inaccuracies in the feedback or computation of the payoff matrix A?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* The presented results constitute the first O(1) regret bound for fictitious play without regularisation. This is already a result of interest.\n* The analysis utilizing energy functions is elegant, insightful, and affords some interesting tools to build upon, and potentially re-apply to the study of other approaches to the problem. In particular, I would foresee the energy function argument being applied to other related algorithmic approaches to two-player zero-sum games.\n* While analyzing this simple algorithm, the authors provide a series of intriguing observations that elegantly distinguish optimistic fictitious play from standard fictitious play. The observation of the existence of the invariant and the analysis stemming from the game-state representation are particularly interesting. \n* Experiments in higher-dimensional settings are compelling and strongly support the hypothesis that findings from the 2x2 setting extend to higher dimensions.\n* The story of the paper is extremely clear, and the writing and communication of key ideas is concise, intuitive and easy to follow.\n\nWeaknesses:\n* Despite strong evidence that higher-dimensional generalizations are plausible, the paper’s rigorous theoretical results remain limited explicitly to 2x2 settings.\n* The notation occasionally becomes cumbersome, making the proofs somewhat difficult to parse at certain points. However, given that the proof encompasses numerous intricate observations and ideas (and since it’s unclear how notation could be significantly simplified), this weakness is relatively minor.\n* The simplicity of the presented method raises questions about its broader applicability in more generic or practical scenarios (see final question).", "was_revised": true, "final_justification": "The authors' have clearly answered my questions, and nothing significant is unresolved. I attribute a high weight to technical novelty, which this paper exhibits in the geometric insights developed throughout, the possibility of extension, interest of results to a broad audience, overall significance, and a clear delineation of open problems. This paper is very comfortably aligned with all these desiderata, and I am therefore happy to recommend its acceptance.", "rebuttal": "Thank you for reviewing our work. We are glad you found the result interesting and clearly presented! Below we reply to some of the questions asked in the review:\n\n**On extending the analysis beyond 2x2 zero-sum games**\n\nWe believe the core ideas and tools used to prove our main theorem will be useful for proving a more general result beyond 2x2 two-player zero-sum games. In short, we believe the key remaining challenge for many-action zero-sum games is to generalize the subspace dynamics machinery stemming from, e.g., Proposition 4.2 to the higher-dimensional regime, which will require additional insights.\n\nIn more details: note that to prove the main theorem (Theorem 3.1), the analysis introduced in Section 4 is indeed somewhat specialized for the 2x2 case. However, this approach relies on the more general geometric intuition introduced in Section 3 (specifically, equation 5), which holds for all higher-dimensional two-player zero-sum games (see also the expanded derivation in Section A.3). Indeed, equation 5 implies that, for any general two-player zero-sum game, the one-step change in energy under OFP is always non-positive when the optimistic/predicted dual variable and the realized dual variable map to the same primal action under the update rule. The main technical lemma of Lemma 4.10 establishes sufficient invariants for when this alignment is true in the 2x2 case, and the proof leverages the subspace property (e.g., Proposition 4.2) for 2x2 zero-sum games with a unique, interior equilibrium.\n\nBased on our empirical results, we believe that similar invariants also hold for many-action two-player zero-sum games, and thus the high-level approach of our analysis (showing that the change in energy is always non-increasing if its magnitude ever exceeds some matrix-dependent constant) can be re-used. However, we believe that formally establishing such invariants in full generality will still require new insights, in particular due to the higher-dimensional nature of the dual iterates (e.g., the two-dimensional subspace property no longer holds). These new insights may also need to leverage structural properties of the underlying class of zero-sum game (for example, using properties of diagonal payoff matrices or skew-symmetric payoff matrices). \n\nWe believe that developing these new insights will contribute more broadly to better understanding the performance of unregularized learning in games, an area which has had an exciting recent resurgence in the past year, and as mentioned by Reviewer qaZX, also has implications for practical equilibrium computation. To this end, we believe our result and proof technique for the 2x2 case serves as a useful starting point for the learning in games community to continue to make progress in this area. \n\n**Reply to amax/amin question**\n\nYes, in general the constant amax/amin can be large, but this ratio essentially encodes the minimum-support mass in the Nash distribution (and note that constant regret and O(1/T) time-averaged convergence to Nash equilibrium essentially implies that at least a number of iterations inversely proportional to this magnitude must have occurred). It is possible that an even sharper (constant) bound can be derived in some instances, but in this work we did not attempt to optimize such constant dependencies. \n\n**Reply to noisy feedback question**\n\nWhile we did not investigate the robustness of Optimistic FP to perturbations in the payoffs or feedback vectors, we believe for (stochastically) unbiased noisy feedback that OFP may still have bounded energy / constant regret. Studying this formally would be an interesting direction for future work."}]

Author rebuttal:

Meta-review: This paper shows that in 2x2 zero-sum games optimistic fictitious play constant regret without any regularization, While this result is narrow, it represents a nice and perhaps surprising contribution to our theoretical understanding of learning in this space.  Based on the discussions with the authors, some of the reviewers feel (and I agree) that the paper stands a good chance of providing inspiration toward further development in this space and that the novel techniques it develops may be useful in that.
Decision: Accept (poster)