Convergence of No-Swap-Regret Dynamics in Self-Play
Authors: Renato Paes Leme
Georgios Piliouras
Jon Schneider
Venue: NeurIPS 2024 poster (2024)
Keywords: online learning
game theory
dynamics
Primary area: algorithmic_game_theory
TL;DR: We study convergence properties of no-swap-regret dynamics in zero-sum-games.

Abstract: In this paper, we investigate the question of whether no-swap-regret dynamics have stronger convergence properties in repeated games than regular no-external-regret dynamics. We prove that in almost all symmetric zero-sum games under symmetric initializations of the agents, no-swap-regret dynamics in self-play are guaranteed to converge in a strong ``frequent-iterate'' sense to the Nash equilibrium: in all but a vanishing fraction of the rounds, the players must play a strategy profile close to a symmetric Nash equilibrium.  Remarkably, relaxing any of these three constraints, i.e. by allowing either i) asymmetric initial conditions, or ii) an asymmetric game or iii) no-external regret dynamics suffices to destroy this result and lead to complex non-equilibrating or even chaotic behavior. 

In a dual type of result, we show that the power of no-swap-regret dynamics comes at a cost of imposing a time-asymmetry on its inputs. While no-external-regret dynamics can be completely determined by the cumulative reward vector received by each player, we show there does not exist any general no-swap-regret dynamics defined on the same state space. In fact, we prove that any no-swap-regret learning algorithm must play a time-asymmetric function over the set of previously observed rewards, ruling out any dynamics based on a symmetric function of the current set of rewards.

Convergence of No-Swap-Regret Dynamics in Self-Play
Renato Paes Leme Google Research
Georgios Piliouras Google Deepmind
Jon Schneider Google Research
Abstract
In this paper, we investigate the question of whether no-swap-regret dynamics have stronger convergence properties in repeated games than regular no-external-regret dynamics. We prove that almost all symmetric zero-sum games under symmetric initializations of the agents, no-swap-regrel dynamics in self-play are guaranteed to converge in a strong "frequent-iterate" sense to the Nash equilibrium: in all but a vanishing fraction of the rounds, the players must play strategy profile close symmetric Nash equilibrium. Remarkably, relaxing any of these three constraints, i.c. by allowing either i) asymmetric initial conditions, or ii) an asymmetric game or iii) no-external regret dynamics suffices to destroy this result and lead to complex non-equilibrating or even chaotic behavior.
In a dual type of result, we show that the power of no-swap-regret dynamics comes of imposing time-asymmetry
its inputs. While no-external-regret dynamics can be completely determined by the cumulative reward vector received by each player, we show there does not exist any general no-swap-regret dynamics defined on the same state space. In fact, we prove that any no-swap-regret learning algorithm must play time-asymmetric function over the set of previously observed rewards, ruling out any dynamics based on a symmetric function of the current set of rewards.
Introduction
The analysis of learning dynamics in games is a well-established problem situated at the intersection
of game theory, online optimization and evolutionary game theory []6
47
[54].
The significance
of this area has been amplified by the emergence of prominent machine learning architectures
and applications relying multi-agent, typically zero-sum, games 42 32
46
52
49 [0].
Symmetric zero-sum games and their dynamics are actually of particular interest both from a
traditional evolutionary perspective [54] [3] well as from modern Machine Learning perspective as creating population of agents that compete against each other in heads-up fashion to outperform each other ("self-play") has been shown to be reliable recipe for creating super-humant capable
agents for a wide range of tasks 38
Despite growing interest in understanding and predicting the long-term behavior of such systems, recent studies have revealed a wide array of negative results, demonstrating the elusiveness of game dynamics. These range from non-convergence results to the establishment of chaotic or even essentially arbitrary behavior chaotic behaviors persist in the analysis of well- online optimization algorithms, such as Multiplicative Weights Updates (MWU/Hedge), Online Gradient Descent, Follow- theeRegularized Leader a.o., even within the narrow but seminal class of (symmetric) zero-sum games I8 [9 20).
30 40 3 55 26 45). Notably, these instability and
Although it possible stabilize learning dynamics zero-sum games using e.g., optimistic variants of MWU 22 43 23 such results leave something to be desired as they presuppose that the agents
coordinate to use specific instantiation of learning algorithm. Ideally, we would like instead to be able to prove such strong convergence results based more abstract properties of the dynamics.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Swap (internal) regret is once such abstract property of online learning dynamics. Unlike the more permissive case of no-(external) regret, where the algorithm's 's performance needs to compete against the best fixed action with hindsight, no-swap-regret algorithms need to compete against the best adaptive deviation policy with hindsight (i.e., for each occurrence of action we consider to the best possible deviating action j with hindsight). Somewhat surprisingly, it is possible to adapt no-regret algorithms to no-internal-regret algorithms efficiently [I] [53 with very recent work providing further efficient such reductions [21 48). The stronger nature of swap regret results into numerous
331, robustness against dynamic strategic behavior 24 15 5 and AI Safety [17]. Arguably, however, its most important application is due to its tight connection to correlated equilibria, introduced by Aumann (6. as it is well known that the tineraeerage empirical distribution of play resulting from no-internal/swap regret algorithms is guaranteed to converge to the set of correlated equilibria (CH a (typically strict) relaxation of the predominant game theoretic solution concept of Nash equilibria. In contrast, no-regret algorithms only guarantee time-average convergence to the even more relaxed solution concept of coarse correlated equilibria (CCE) (see preliminary section for precise definitions). Interestingly, in the special case of zero-sum games, for almost all but pathological zero-measure instances of them, the notions of Nash equílibria and correlated equilibria coincide and are in fact unique (whereas CCE do not). This opens the following tantalizing possibility:
applications, such as (multi)-calibration [I
37
51
351
Does no- po--swap--ggeee minimization suffice for Nash convergence in (almost) all zero-sun games?
The answer to above question is strongly negative. Even in trivial two strategy zero-sum games, such as Matching Pennies, swap regret minimization does not suffice for convergence. Interestingly, however, sweeping positive result holds for the case of symmetric zero-sum games.
Informal theorem: In almost all symmetric zero-sum games, under arbitrary symmetric initializations for both agents, any no-swap-regret algorithm in self-play guaranteed to converge the Nash equilibrium, excepp] 2 for a vanishingly small fraction of iterates.
At technical level, the result depends two different arguments. First, even in the case of symmetric zero-sum games it is still possible to show that generically the correlated equilibria remain unique, however, the argument does not follow the analysis of general zero-sum games as symmetric cases themselves non-generic within the larger class. Secondly, we leverage the symmetry of the trajectories to show that averaged convergence of symmetric action profiles to a product distribution implies the desired convergent behavior.
This unexpected connection between swap regret minimization and symmetry in games inspires the investigation of other ways that symmetry can insert itself in the study of online learning itself. For example, it is well understood that most standard no-regret algorithms such MWU, can be completely determined by the vector of cumulative rewards and thus their outputs remain invariant to any permutation of their history, i.c. they exhibit a strong type of time symmetyyy Interestingly, show that such time-symmetry is provably at odds with swap regret minimization. At a technical level, this argument is based particular classes of card guessing games (e.g., (55 that enable precise control over the algorithm's optimal expected utility (in particular, showing that the play of any such algorithm must be very close to the Dollow-The-Leadde algorithm, at least when averaged over certain segments of time).
construction that couples the behavior of online learning dynamics to
Model and Preliminaries
2.1 Games and learning
We consider a setting where two learners (Alice and Bob) are repeatedly playing game G for T rounds. We assume the game G has N actions for both Alice and Bob, and Alice and Bob will play mixed strategies belonging to the N-dimensional simplex AN. The game G can be thought of as a pair of bilinear functions (GA, GB) describing the payoffs for Alice and Bob: in round f, if Alice plays action a₂ E Ay and Bob plays action 62 E AN, then Alice receives payoff G G by) and Bob receives utility Gz(a,, b.). One specific class of games consider zero-sum games, where
'Due their connections equilibria, establishing fast swap regret minimization (and variations thereof) for different classes of games is subject of lot of recent work (e.g., 22 50 56 27))
"This minor disclaimer is necessary as it is always possible to inject such vanishingly small "noise" in any trajectory without affecting its aveeree regret.
2

---

bi);;; for such games we will omit the subscript and write G(a bi) to denote GB(ar,b) (a)la,,b)=-aaa - Cglaubb)=-aa(o.b))) Ga(a,,b)).
For our purposes, a learning algorithm for Alice in this repeated game a function which maps the history of played mixed strategies (e.g., d1, d,, 022 - bt-1) will play next (az). Learning algorithms for Bob are defined symmetrically. Note that we operate in the deterministic full-information setting where both Alice and Bob know the game G and can see each other's ' mixed strategy after each round
Ot-1;
to the mixed strategy that Alice
We consider two classes of learning algorithms, no-regret algorithms and no-swap-regrer algorithms. Alice's 's (external) regret is defined via
RegA t=1
ba(
max Gaa("", b.) a'E t=1
(with Bob's external regret Reg defined similarly). Alice's swap regret is defined via
S E Ga(a,,))))
max (G((TA(a)).b.) [M
(2)
In (2). the maximum over all "swap functions" x mapping the set of N actions to itself. We extend
to act mixed strategies (elements of Ax) in the natural way (i.e., T(x); -E, -E 1(T(j) = i)). We say Alice's learning algorithm is no-regrel if it is guaranteed that Reg. =(T). Similarly, we say it no-swap-regret it is guaranteed that SwapReg, o(T). is known that both efficient
no-regret and no-swap-regres algorithms exist, with regret scaling as Õ(VT) 11
2.1.1 Symmetric games and symmetric learners
In this note we primarily consider symmetric learning dynamics in symmetric games. A game G is symmetric G((a,, by) (b,, As with zero-sum games, for symmetric games we will omit subscripts and use G(a,, by) to refer to GA Ca(a,,b)) Some games are both symmetric and zero-sum (e.g., the Rock- Pock-Paper-See Paper-Scissors example we introduce later in Ex
In a symmetric game, it's natural to consider the setting where Alice and Bob play identical learning algorithms with identical initialization. This results in completely symmetric learning dynamics for Alice and Bob (i.c., a₂ = by for all rounds t). We write 2₁ A to denote the common strategy that Alice and Bob play at time
2.2 Equilibria in games
We are interested the convergence of various types of learning algorithms to specific equilibria of G. We begin by defining the equilibria of interest.
For game G, (not necessarily symmetric) joint strafegy profile is distribution over all N2 pairs of pure strategies for Alice and Bob. Note that this is not necessarily a product distribution, and in particular allows for Alice's mixed strategy and Bob's mixed strategy to be correlated. is convenient to identify the set of joint distributions A with the convex subset S of the tensor product space RN @ N defined the convex hull of all elements of the form a where a, b AN. In particular, given b E AN. the element a @ b corresponds to the joint strategy profile where Alice plays mixed strategy and Bob independently plays mixed strategy b. In other words, the pair (i.j) played with probability azby.
We consider three different types of equilibria, which are (in increasing order of fineness) coarse- correlated equilibria, correlated equilibria, and Nash equilibria. We define these below:
A coarse-correlated equilibrium is joint strategy profile where neither Alice nor Bob has an incentive to unilaterally deviate to a single pure action. Formally, a a coarse-correlated equilibrium if both
3 Alternatively, everything we describe also holds in a slightly weaker setting, where the players do not know the game G but instead after each round each player sees the counterfactual payoff's they would have received for each of their possible N actions.
3

---

[GA(1.])] E [G^(1, (C)( VI {[N] (i.))a
E [GD(it)) E [GB(i.))], [N]
(k.))~a
(i))aa
correlated equilibrium joint strategy profile where neither Alice nor Bob has an incentive to deviate from their assigned action, where their deviation may depend on their original action. Formally, a correlated equilibrium if both
E [GA(1,)) (65)-
E [GA(TA(O).)) [N] [N]
(1,))
E [GB(L))) (i.j)-o
E [G [N] - [N] (1,))a
Finally, is Nash equilibrium if a product distribution @ b and neither Alice
Bob has an incentive to deviate (G A (a, 2 Ga b) and G (a, b) 2 GB (a, I)). Note that alternatively think of Nash equilibria the intersection of coarse-correlated (or correlated) equilibria with the set of product distributions.
Example 1. Consider the Rock- Soeck-Pppe-SSeissone zero-sum game, defined via:
G(i,i) 0, G(i, (i+ 1) mod 3) 1, G(i, (i (i-1) mod 3) =-1.
The unique correlated equilibrium (and hence unique Nash equilibrium) this game is the product distribution (#1t09661 & (03003)))) ). However, the set of coarse correlated equilibria is much larger-
contains, for example, the element (e1 61 + 62 e2 eg @ e3). Here there is no incentive to unilaterally deviate, but there is an incentive to deviate based on your choice of action (c.g., whenever you play e1, you can improve your utility by instead playing ez).
2.3 Convergence equilibria
When players run learning algorithms in repeated games, they may over time converge to an equilib- rium. There three senses which this may happen (that discuss here). We say that Alice and Bob's strategies have fine-averaged convergence to joint strategy profile a if
( (
lim T0
a & by
-
In other words, time-averaged convergence means that the average of the joint strategy profiles Alice and Bob play converges over time to a.
Likewise, we say that Alice and Bob's strategies have frequent-tterate convergence to if for any E 0,
lim Pr [Il @ b,) ol| = To IST
Here the probability is taken over being drawn uniformly random from all rounds between and T. In other words, frequent-iterate convergence means that, as time goes on, almost all joint strategies profiles Alice and Bob play will be arbitrarily close a.
Finally, we say that Alice and Bob's strategies have last-iterate convergence to a
lim (aT 2 br) all 0. T
Last-iterate convergence means that the sequence of joint action profiles played by Alice and Bob directly converge to ar. Note that last-iterate convergence is a stronger property than frequent-iterate convergence, which in is stronger property than time-averaged convergence.
It known that Alice and Bob run certain types learning algorithms, they will have time-averaged convergence certain type of equilibrium. Here some known facts about learning dynamics []:

---

Tayocwy RAU
Trgectory um Mansout
640
D15
0.6
0.26
0.22
Figure 1: Trajectories of two learning algorithms (Multiplicatiie Weights and Blum-Mansour) playing Boock-Papr-SSiisoot The axis corresponds to the probability of playing Rock and Paper. The blue dot corresponds to the probabilities Nash equilibrium while the red dot the last iterate after 10000 steps with learning rate 0.001.
TapoCtory MAU
Trgectory Bannaarouu
018
0.4
032
636
6.56
8.16
00.00
0.22
0.24
0.25
0.5
633
033
0.0
321
Figure 2: Trajectories of Multiplicative Weights and Blum-Mansonn for Rock-Paper- Lock-Pappr-SSesssors Scissors-Lizard- Spock (a the 5-strategy generalization of Rock-Paper-Scissee
If Alice and Bob are running no-regret algorithms general game G, their strategies will have time-averaged convergence to coarse correlated equilibrium of G.
If Alice and Bob running no-swap-regret algorithms in general game G, their strategies will have time-averaged convergence to correlated equilibrium of G.
There exist zero-sum games G (including Rock-Paper-Scissory of Example where if Alice and Bob run certain no-regret algorithms (e.g. Multiplicative Weights) Alice and Bob's strategics will not have last-iterate convergence to coarse correlated equilibrium.

---

3 Convergence of Symmetric Swap Regret in Symmetric Zero Sum Games
There exist zero-sum games (including Kock-Paper-Scissonn of Example [ where if Alice and Bob run certain no-regret algorithms (e.g. Multiplicative Weights) Alice and Bob's strategies will have last-iterate convergence a equilibrium. In the left side of Figure plot the trajectory of Multiplicative Weights when Alice and Bob have the same initialization. The blue dot in the middle corresponds the Nash equilibrium. While the strategies played average to the equilibrium, they never converge there.
In this section, will show that for almost all symmetric, zero-sum games G, if Alice and Bob employ the same no-swap-regret learning algorithms with symmetric initializations they will have frequent-iterate convergence Nash equilibrium of G. In the right side of the same figure, show the Muuu-r trajectory converging to equilibrium. In Appendix [A] we show via simple counter-example that symmetric initializations are necessary to achieve such strong convergence guarantees.
Our main tool is the following technical lemma, which shows that time-averaged convergence of symmetric action profiles to a product distribution implies frequent- iterate convergence to the same distribution.
Lemma 1.
Let I1, 22,.... be sequence of elements in AN such that
lim T-000
(1
for some element y of AN (Le., the profiles 34 z4 time-averaged converge to y y). Then it is the case that for any O,
lim Pr [1(, (y y) > =.
T T- E2
(i.e., the profiles 2, 24 frequent-itenne -iteratt converge y @ y).
Proof. For any E AN. we will show that there exists a linear functional Ly R- @ RV R with the property that, among all elements of the form x with x AN. Ly is uniquely minimized @ y. As consequence, this implies that that there exists a 8 0 such that if
(x (y 2 v) >
for some element & AN, then (x @ x) T,y 0 v) 8. In particular, if for some T we have that
Pr [r oz, (y > tsT
then we consequently have that
(Ly(2,0x) -x, (, 2 78.
and in turn that
( - Σ co s sx))
(y 2 8) 2 76|1L,1|+,
(where ||, is the dual norm of the linear functional L, and is bounded below by some constant). This directly implies the lemma statement (it is impossible for the second quantity to approach as T goes to infinity without the first quantity approaching zero).
We now describe the linear functional Ly. Let y (yi, ..,..., .yn) (and for general x AN. let
(æ1, F2, IN)). Note that for any linear functional Ly R N R, the value of

---

will be homogeneous quadratic polynomial over the 2;; conversely, any such polynomial can be implemented as a linear functional over R. @ R.". Moreover, since Σx; 1, we can convert any mnn-homogenneus) quadratic polynomial to homogeneous one (e-g. transforming = + 21 to z + 21 Σ + (E.:) )) It therefore suffices to find a quadratic polynomial over the z; that is minimized when x y.
We begin with the case where all y/ > 0. In this case, we claim that the polynomial
(2 = Σ -
1-1 U/
satisfies these constraints. To see this, note that by
N yi
N
Vi
= 1,
Vi
with equality only holding when x²/ Ay; for some fixed X. Since v and y both belong AN. this is only possible when À = and a = y-
What if some of the yi equal zero? Without loss of generality, assume 0 for 1 s sis and yi 0 for 7 isis S N. Now, consider the polynomial
Σ
yi
We begin by minimizing this expression subject to Σ 2; 8, for some 0 S 1. In this the second term in the above polynomial is identically -2s, so it suffices to minimize the first term. Again applying Cauchy-Schwartz, Schwartz, we find the minimum of the first term occurs only when 2; = 8y,, where it equals s². The overall minimum of Ly (subject to this constraint) is therefore 8² 2s. This is in turn uniquely minimized when (and I, for all n), and therefore this Ly uniquely minimized at x y.
Next show 'generic' symmetric zero-sum game has unique correlated equilibrium and hence coincides with the Nash equilibrium this game. First, we define what we mean by generic. We can identify the of zero-sum games with N&N, where each element corresponds an N N payoff matrix for Alice. We say that property P holds for a generic zero-sum game, if the set of points in IRNN for which P doesn't 't holds form a measure zero subset of IR Nx.
By this definition, the set of symmetric zero-sum games forms a measure zero subset of the set of zero-sum games, so need a refined definition to describe a generic symmetric zero-sum game, We can identify the set of symmetric zero-sum games with with R. (NN))/ where each element corresponds to neew-symmetri N x N payoff matrix for Alice, We say that a property P holds for generic symmetric zero-sum game, if the set of points in NxN for which P doesn't holds form measure zero subset of (NN-)/2
The uniqueness of a correlated equilibrium for zero-sum games is known for generic zero-sum games by combining results by Forges [29] and Bohnenblust, Karlin and Shapley [12]. But since symmetric zero-sum games are a measure zero subset of zero-sum games, this result does not directly extend. Below, we extend it to symmetric zero-sum games.
Finally, to complete the picture, we further establish that this generic uniqueness of correlated equilibria strongly does not extend to the case of coarse correlated equilibria, which are the limit points of (external) regret-minimizing algorithms.
Lemma 2. Almost all (ie., all but measure zero set of) two-player symmetric zero-sum games have a unique correlated/Nash equilibrium.
Proof. By 29 zero-sum game has a unique correlated equilibrium if and only if it has a unique Nash equilibrium, thus it suffices to prove the generic uniqueness of Nash equilibria. Let be the skew-symmetric (A" AA) payoff matrix corresponding to the symmetric zero-sum game. A Nash
7

---

equilibrium is called quasi-strict (sometimes also referred to as regular or quasi-strong (34) if for all agents deviations to strategies outside their support result in strict decrease of their payoff. By Corollary 3.4 in [36] we have that in any two agent game if all equilibria are quasi-strict then the number of equilibria is finite. Thus, if a symmetrie zero-sum game has multiple equilibria, this implies the existence of a non-quasi-strict equlibriiumoppimal strategy. Let be that non-quasi-strict mixed strategy and let S₂ denote its support, i.c., the set of strategies played in a with positive probability and let i be the index of the strategy not in S, such that deviating to that strategy from the symmetric (z, x) Nash equilibrium still results into payoff of zero (since the game value of any zero-sum symmetrie game is zero). This implies that both antisymmetric sub-matrices of A defined by its restrictions to the sets S₂ and S₂ U i respectively have a zero eigenvalue where the corresponding eigenvector is the analogously restricted subvector of æ. Thus. both of their determinants to zero. However, at least one of them has even dimension. It is well known that the determinant of even dimension skew-symmetric matrix is non-trivial polynomial (and in fact is the square of a polynomial in its coefficients, see e.g. [39].. The entries of this submatrix correspond to the vanishing set of non-trivial polynomial and therefore have Lebesgue measure zero. Thus, the set of all symmetric zero-sum games with unique Nash/correlated equilibrium has zero measure.
equal
Combining Lemma D and Theorem we arrive at the result mentioned at the beginning of this section.
Theorem generic symmetrrc zero-sum game G. if Alice and Bob run identical no-swap-regre algorithms with the same initialization to play G repeatedly, their joint strategy profiles will have frequent-iterate convergence to a Nash equilibrium of G. Furthermore, this result tight, i.e., is not possible to prove (last-iterate) convergence to Nash equilibrium.
Proof. Since Alice and Bob are both running the same no-swap-regret algorithm, their strategy profiles stay identical and hence their joint strategy profile is of the form Iz @ z₁. Since no-swap- regret algorithms have time average convergence to correlated equilibrium, then there a correlated equilibrium of G such that 1 ΣL Iy @ r₁ all O. By Lemma 2 a is Nash equilibrium, so we can write y @ y. Now, we can apply Lemma D to obtain frequent iterated convergence to a.
It is not possible to prove anything stronger, i.e., convergence Nash, based on (symmetric) no-swap- regret learning because we can take any such no-swap-regret dynamics and interject for vanishing fraction of the history some arbitrary symmetric play where those payoff inputs are ignored by the learning dynamics (e.g. the Blum-Mansout algorithm does not see these fictitious entries). This rare interleaving of the trajectory with noise does not significantly affect the swap regret analysis which will remain sublinear if the original dynamic is no-swap-regret but at the same time it suffices to destroy any hope of true last iterate convergence.
3.1 Differences with respect to External Regret
is useful to consider which parts of the proof break when we move from swap to external regret.
Both Lemma T and Lemma no longer hold.
Consider for example the executions of MWU and BM in Figure I In both cases we have that
(E, .r2) + Nash := (3 3 4. If we look at the empirical joint distribution ōy = + (Ee @ x2) we
obtain the following:
T0.111
0.111
0.111
T0.120
0.105
0.105
GT
BM
0.111
0.111
0.111
MWU o
0.105
0.120
0. 0.105
0.111
0.111
0.111
00.10
0.105
0.120
Only in the swap regret algorithm we have ā ~ TNash & TNash-
Lemma
| crucially relies on
7 (E. xa @ 1x) converging a product distribution.
Lemma 2 also breaks when we replace CE (achieved by swap regret minimization) with CCE (achieved by external regret minimization):
Lemma 4. Given any symmetric zero-sum game long as its set of optimal strategies does not consist of a single pure (iee. deterministic) strutegy then it has a continuum of coarse correlated equilibria.
8

---

Proof. In any such game there exists an optimal (Nash) strategy that is randomizing amongst at least two strategies. We will define the correlated distribution that applies positive probability only symmetric outcomes of the game (e.g, such as (Rock, Rock) (Paper, Paper) and (Scissors, Scissors) in the RPS game) such as its resulting marginal distribution corresponds to the Nash equilibrium strategy. The expected payoff of each agent in this distribution is equal to zero. Furthermore, any deviating strategy cannot result in positive payoff since the marginal distribution encodes a Nash equilibrium. Thus, the original distribution is CCE. By taking convex combinations of these CCE and the Nash equilibrium we have that each such game has a continuum of CCE.
An immediate corollary of Lemma is that the rich, non-equilibrating behavior of MWU and other no-regret dynamics, even under symmetric initializations, shown for Sork-PPper-Scisooee and Look--Pper-Scissoottt symmetric games and eegret-miimizzin dynamics as well.
Spockk shown in Figures [ should be common for many other
3.2 Asymmetric Zero Sum Games
We remark that the results don't 't generalize to asymmetric zero sum games. One example of such games is matching pennies where no-external regret dynamies like MWU are known not to exhibit last- iterate convergence and in fact diverge chaotically towards the boundary for all interior initializations, including all symmetric (non-Nash) initial conditions R [8. For games with 2 actions per player, any no-external-regrel algorithm is also no-swap-regret we show in the following lemma.
Lemma 5. For a game with actions per player, SwapReg s 2 Reg.
Proof. Let {0, be Alice's 's actions in let ae. b, Ag be sequence of strategies played by Alice and Bob. There are 3 non-trivial swap strategies π [2] + [2] for Alice: 8 + 0, s + 1, 8 + 1 - s. The regret of using the first two swap strategies is bounded by Reg since they map to a constant action. Let ar [x[ be the s-th component of a₂ A2. Then, the regret of the third strategy x is bounded by:
Caa(asb)) (G (T(T()),bb))
a [=10][Ga(O.b)-GGAtt [ ( b,))
+5
[Galanb)-Ca(hbb)) -Galaa,b)-Ga((.. < 2 Reg [
4 No-Swap-Regret Algorithms are Time-Asymmetric
One interesting feature of no(-external)--egeee -regret algorithms in two two-player games is that the action they select at time can depend entirely on the average historical strategy played by the other player up to time t- 1, and not on any other information about how this strategy (or the player's 's own strategy) evolved over time.
In this section we show that it is impossible for a no-swap-regret learning algorithm to have this property. In fact, we prove the following more general statement.
Theorem 6. Consider any learning algorithm A which decides what action to take on behalf of Alice in a game at round L via a symmetric function A, .2......b.-)) ) of Bob mixed strategies up until I - (here symmetric means that the function is unchanged for any permutation of the inputs). Then there exists game G and a sequence of play for Bob where Alice incurs 2(T) swap regret.
As mentioned, many no no-external-reegeee regret algorithms (such as multiplicative weights, and follow- the-regularized leader) have the property that each A, can be written as a function of the average 1 + b,. and hence are symmetric. F-T
We provide a sketch of the proof of Theorem 6. deferring all details and proofs of lemmas to Appendix B We will consider the game G given by the three-action generalization of Matching Pennies. Specifically, Alice and Bob will both have 3 actions, and G (t. j) equals 1 if = j and 0 otherwise (since we will specify Bob's sequence of actions adversarially, his payoff G is irrelevant).
We will construct an adversarial sequence of actions for Bob where in each round Bob plays one of the three pure actions in As (i.c., b, e {e1, e) For each i E [3], let n4,s equal the number

---

of rounds s $ t-1 1 where Bob played action i. Since A, is a symmetric function of the b₂ for 1 1 s 1, we can write A, as a function A, (n R4,,, n4,3). Moreover, since we must have R4,1 + 14,2 14. = 1 1, we can summarize the entire learning algorithm with a single 3-variable function A(R1, R2,, na) 2 A3 satisfying
A(R1, n2, na) An, +12tnn+1 (11, n3).
Our main strategy will be to show that if A has no swap regret (or even no external regret), on average A must be very close the "follow the leader" strategy, which puts all the weight action if n, is significantly larger than the other ny. We formalize this in the following lemma (which employs a result of [25] the number of mistakes necessary in certain card guessing games):
Lemma 7. Assume that the algorithm A guarantees that Alice incurs at most sublinear external
regret, ie., Reg, = =(T). Then for any L 2 T/100 and nı, 122 S n2 S T - L, we have that
1
na+L
Σ A(, = = m=
L
Lemma shows that mostly plays the leader (i.e., highest-utility) action in any sufficiently long segment of rounds where Bob is playing the leader action. We would also like to show that A mostly plays the leader action stretches where Bob playing some other fixed action. The following lemma gives a weak form of this claim (but that will be sufficient for proving Theorem
Lemma 8. Fix any L'L' T/100 and let ne 2 min(n1. L'). Then there exists an é [12, n2 + L] such that
ng-1 Σ A(ni,m ns))s = = w/
L'
With I Lemmas 7 and 8 (and their symmetric counterparts), we can construct sequence of play for Bob where Alice incurs high swap regret. Roughly, this sequence of play proceeds as follows.
First Bob plays action for approximately T/3 rounds. By Lemma 7 we can guarantee that Alice plays action 1 for most of these rounds.
Bob then plays action 2 for approximately T/3 rounds. By the guarantee of Lemma g Alice will still play action 1 for most of these rounds.
Bob then plays action for the remaining rounds. Again by applying Lemma g we can guarantee that Alice will play action 2 for most of these rounds.
It is straightforward to check that Alice incurs linear swap regret in the above trajectory Alice would improve her expected utility by S2T)) she played action every time she played action The details of this proof are deferred to Appendix B
Conclusion
In this paper, we study the role of symmetry in the behavior of no-swap regret dynamics. In our first result, we show that no-swap-regret dynamics in self-play in symmetric zero-sum games lead to converge in a strong "frequent-iterate" sense to the Nash equilibrium. Specifically, all but vanishing fraction of the rounds, the players must play strategy profile close to symmetric Nash equilibrium. Furthermore, we show that the power of no-swap-regret dynamics comes at a cost of imposing time-asyme asymmetry its inputs. Specifically, any such algorithm, unlike no-external regret dynamics, must apply a time-asymmetric function over the set of previously observed rewards.
The interplay between symmetry, (external/swap) regret and learning in games emerges as as in- teresting direction for future work. One particularly interesting such direction would be explore generalizations of our results beyond two player games.
10

---

References
[1] I. Anagnostides, G. Farina, C. Kroer, C.-W. Lee, H. Luo, and Sandholm. Uncoupled learning dynamics with (llog swap regret in multiplayer games. Advances in Neural Information Processing Systems, 35:3292-3304 2022.
[2] I. Anagnostides, G. Farina, and T. Sandholm. Near-optimal ø-regret learning in extensive-form games. In International Conference on Machine Learning, pages 814-839, PMLR, 2023.
[3] G. P. Andrade, R. Frongillo, and G. Piliouras. Learning in matrix games can be arbitrarily complex. In M. Belkin and S. Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 159-185. PMLR, 15-19 Aug 2021.
[4] G. Andrade, Frongillo, and Piliouras. No-regret learning games is turing complete. arXiv preprint 1tXXi:2202211871,, 2022.
[5] E. R. Arunachaleswaran, N. Collina, and J. Schneider. Pareto-optimal algorithms for learning in games. arXiv preprint arXiv:2402.09549) 2024.
[6] R. J. Aumann. Subjectivity and correlation in randomized strategies. Journal of mathematical Economics, 1(1):67-96 1974.
[7] J. P. Bailey and G. Piliouras. Multiplicative weights update in zero-sum games. In ACM Conference on Economics and Computation, 2018.
[8] P. Bailey and G. Piliouras. Multiplicative weights update zero-sum games. Proceedings of the 2018 ACM Conference on Economics and Computation, pages 321-338, 2018.
[9] D. Balduzzi, M. Garnelo, Y. Bachrach, W. Czarnecki. J. Perolat, M. Jaderberg, and T. Graepel. Open-ended learning in symmetric zero-sum games. In International Conference on Machine Learning, pages 434 443. PMLR, 2019.
[10] A. Bighashdel, Y. Wang. S. McAleer, R. Savani, and F. A. Olichock. Policy space response oracles: A survey, arXiv preprint SiXi:2203.002227,, 2024.
[11] A. Blum and Y. Mansour. From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
[12] H. Bohnenblust, S. Karlin, and L. Shapley. Solutions of discrete, two-person games. Contribu- tions to the Theory of Games, 1:51-72, 1950.
[13] V. Boone and G. Piliouras. From Darwin to Poincaré and von Neumann: Recurrence and cycles in evolutionary and algorithmic game theory. In International Conference on Web and Internet Economics, pages 85-99. Springer, 2019.
[14] N. Brown and T. Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456):885-890)) 2019.
[15] W. Brown, J. Schneider, and K. Vodrahalli. Is learning in games good for the learners? Advances in Neural Information Processing Systems, 36, 2024.
[16] N. Cesa-Bianchi and G. Lugoisi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[17] X. Chen, A. Chen, D. Foster, and E. Hazan. Playing Large Games with Oracles and Al Debate. arXiv e-prints, page arXiv:2312.04792, Dec. 2023.
[18] Y. K. Cheung and G. Piliouras. Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games. In Conference on Learning Theory, pages 807-834, PMLR, 2019.
[19] Y. K. Cheung and G. Piliouras. Chaos, extremism and optimism: Volume analysis of learning in games. In NewrIPS, 2020.

---

[20] Y. K. Cheung, G. Piliouras, and Y. Tao. The evolution of uncertainty of learning in games, In International Conference on Learning Representations, 2021.
[21] Y. Dagan, C. Daskalakis, M. Fishelson, and N. Golowich. From external to swap regret 2.0: An efficient reduction and oblivious adversary for large action spaces. arXiv preprint arXiv:2310.19788 2023.
[22] C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng. Training gans with optimism. In ICLR, 2018.
[23] C. Daskalakis and Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. ITCS, 2019.
[24] Y. Deng. J. Schneider, and B. Sivan. Strategizing against no-regret learners. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 1577-1585, 2019.
[25] P. Diaconis and R. Graham. The analysis of sequential experiments with feedback to subjects. The Annals of Statistics, 91)::3223, 1981.
[26] M. Engel and G. Piliouras. A stochastic variant of replicator dynamics in zero-sum games and its invariant measures. arXiv preprint arXiv: 2023.
[27] G. Farina and C. Pipis. Polynomial-time computation of exact phi-equilibria in polyhedral games, arXiv preprint arXiv:2402.163/6, 2024.
[28] L. Flokas, E.-V. Vlatakis-Gkaragiee regret learning and mixed nash equilibria: They do not mix. In NeurIPS, 2020.
T. Lianeas, P. Mertikopoulos, and G. Piliouras. No-
[29] F. Forges. Correlated equilibrium in two-person zero-sum games. Econometrica (1986-1998), 58(2):515, 1990.
[30] A. Giannou, E. V. Vlatakis- Gkaragkounis, and Mertikopoulos. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In M. Belkin and Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2147-2148. PMLR, 15-19 Aug 2021.
[31] I. Globus-Harte D. Harrison, M. Kearns, A. Roth, and J. Sorrell. Multicalibration as boosting for regression. arXiv preprint 1777, 2023.
[32] I. Goodfellow, J. Pouget- Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Bengio. Generative adversarial nets. In Advances neural information processing systems, pages 2672-2680, 2014.
[33] N. Haghtalab, C. Podimata, and K. Yang. Calibrated stackelberg games: Learning optimal commitments against calibrated agents. Advances Neural Information Processing Systems, 36, 2024.
[34] J. C. Harsanyi. Oddness of the number of equilibrium points: a new proof. International Journal of Game Theory, 2(1):235-250, 1973.
[35] L. Hu and Y. Wu. Calibration error for decision making, 2024.
[36] M. Jansen. Regularity and stability of equilibrium points of bimatrix games. Mathematics of Operations Research, 6(4):530-550, 1981.
[37] B. Kleinberg, R. P. Leme, J. Schneider, and Y. Teng. U-calibration: Forecasting for an unknown agent. In The Thirty Sixth Annual Conference on Learning Theory, pages 5143-5145. PMLR. 2023.
[38] M. Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, J. Pérolat, D. Silver, and Graepel. unified game-theoretic approach to multiagent reinforcement learning. Advances in neural information processing systems, 30, 2017.
12

---

[39] W. Ledermann. A note skew-symmetric determinants. Proceedings of the Edinburgh Mathematical Society, 36(2):335-338, 1993.
[40] A. Letcher. On the impossibility global convergence multi-loss optimization, 2021.
[41] Y. Mansour, M. Mohri, J. Schneider, and B. Sivan. Strategizing against learners in bayesian games. In Conference on Learning Theorr, pages 5221-5252. PMLR, 2022.
[42] H. B. McMahan, G. J. Gordon, and A. Blum. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pages 536-543, 2003.
[43] Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Op- timistic mirror descent in saddle-poin problems: Going the extra( (arr(-gradeent) mile. In ICLR, 2019.
[44] Mertikopoulos, C. Papadimitriou, and G. Piliouras. Cycles in adversarial regularized learning. In ACM- Symposium Discrete Algorithms, 2018.
[45] J. Milionis, C. Papadimitriou, G. Piliouras, and K. Spendlove. An impossibility theorem in game dynamics. Proceedings of the National Academy of Sciences, 120(41):e2305349120, 2023.
[46] M. Moravčík, M. Schmid, N. Burch, V. Lisý, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, and M. Bowling. Deepstack: Expert-level artificial intelligence in heads-up nomlimit poker. Science, 356(6337) 513, 2017.
[47] N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007.
[48] B. Peng and A. Rubinstein. Fast swap regret minimization and applications to approximate correlated equilibria. arXiv preprint arXiv:2310.19617, 2023.
[49] J. Perolat, B. De Vylder, D. Hennes, E. Tarassov, F. Strub, V. de Boer, P. Muller, J. T. Connor, N. Burch, T. Anthony, al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 37866623) 2022.
[50] G. Piliouras, M. Rowland, S. Omidshafiei, R. Elie, D. Hennes, J. Connor, and K. Tuyls. Evolutionary dynamies and phi-regret minimization in games. Journal of Artificial Intelligence Research, 74:1 125 111112211555 1158, 2022.
[51] A. Roth and M. Shi. Forecasting for swap regret for all downstream agents. arXiv preprint vrXiv:2402.08753, 2024.
[52] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang. A. Guez, T. Hubert, Baker, M. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. nature,
550(7676):354-359 2017.
[53] G. Stoltz and G. Lugosi. Internal regret in on-line portfolio selection. Machine Learning, 59:125-159, 2005.
[54] W. Weibull. Evolutionary Game Theory. MIT Press; Cambridge, MA: Cambridge University Press., 1995.
[55] A. Wibisono, M. Tao, and G. Piliouras. Altematinn mirror descent for constrained min-max games. In Proceedings of the 36nd International Conference on Neural Information Processing Systems, 2022.
[56] B. H. Zhang, I. Anagnostides, G. Farina, and T. Sandholm. Efficient phi-regret minimization with low-degree swap deviations in extensive-form games. arXiv preprint arXiv:2402.09677, 2024.
13

---

A No-swap regret dynamics with asymmetric initial conditions do not converge to Nash equilibrium
We show via simple counter-example that symmetric initializations necessary for convergence to Nash. Specifically, in Figure 3 we show the trajectory of two players running the Blum-Mae Mansour no-swap-regret algorithm against each other, initialized with asymmetric starting conditions in the symmetric zero-sum game Rock- Rock-Paper-Se Paper-Scissons Their behavior does not converge to Nash, whereas have seen in Figure [ symmetric initialization in the same game would have led to convergence.
Pogeccrry of thur-Maniou playes
Fegedaay of Mlamn-aa Mariss (layst
0.8
0.4
020
038
Pub
Pobedt actinn
Figure 3: This figure shows the trajectory of two players running the Blum-Mansour no-swap-regret algorithm against each other initialized with asymmetric starting conditions. Unlike the symmetric dynamics, these do not ultimately converge the unique symmetric Nash equilibrium (the blue point).
B Omitted proofs of Section 4
B.1 Proof of Lemma
Proof of Lemmal 7 Define W Zm=ng+1 A(n1, A2,,, m)s. We will present a distribution D over action sequences of length 7' for Bob such that the expected regret Reg, that Alice incurs when playing against randomly drawn sequence from D is at least (I- - -)-W(((T)) A has the guarantee that Reg A o(T), then this implies that we must have W I, oT)), from which the theorem statement follows.
R
the algorithm
We will construct the distribution D as follows:
For the first nı + n2 nı rounds, Bob will play uniform random sequence that includes action nı times, action 2 n2 times, and action 3 ng times.
In the next L rounds, Bob will always play action 3.
Finally, in the last 7' T (r + + n2)) rounds, Bob will play uniform random sequence that includes action T3/3 times, action / times, and action T'/3 times.
Note that for any such sequence, the best action in hindsight for Alice is action 3, which achieves utility exactly ng L T'/3. compute Alice's expected regret, suffices compare Alice's expected utility to this quantity.
14

---

To bound Alice's optimal expected utility, we will make use of the following result of Diaconis and Graham [25]_ Consider a game where there a uniformly shuffled deck of N n1 + n2 + ng cards with cards labeled 1, cards labeled 2, and ng cards labeled 3. In this game, the player must repeatedly guess the label of the card on the top of the deck, at which point it revealed to the player and discarded. Then Diaconis and Graham show that the expected number of correct guesses of
the player is at most max(11 R2, Ra) O(VN) (in fact in Theorem 3 of [25] provides bounds that apply to any number of labels, but we only need this specific consequence).
Note that in the first п1 + n2 + rounds, Alice is facing essentially this exact game (since she gains utility 1 when she matches the action of Bob, and 0 otherwise). Therefore Alice's expected utility in the first segment of the rounds is at most nı + O(vni n2 + (1)) ng + O(VT). Similarly, in the last segment of rounds, Alice's ' expected utility is at most T / + Q(VT). Finally, the middle segment of rounds, Alice's utility is exactly W (as this is the total weight she places action 3). It follows that Alice's expected regret is at least (L W) O(VT). as desired.
B.2
Proof of Lemma g
Proof of Lemma g
By applying Lemma] 7 times, we have that:
noth
Σ Σ
(ni,m'mm)) =1 o(1)
L'- L m'=ng=L'' m=ng
By switching the order of summation, this implies that there must exist fixed value of m [m2, n2 L] such that
1 n
Σ A(m m)) o(1).
L' m/-n3-1/
We can take fig to be this value of m.
With Lemmas and g (and their symmetric counterparts), we can construct a sequence of play for Bob where Alice incurs high swap regret.
B.3 Proof of Theorem 6
Proof of Theorem 6 Fix L = T/100. Bob will begin by selecting an [T/8.T/3+ such
that:
T/3 Σ T/3
A(n1, m', 0)s= = o(1.
(Such n is guaranteed to exist by symmetric variant of Lemma N.. Bob will then play action 1 for nı rounds followed by action for T/3 rounds.
Bob will then select value [T/3 T/1000, T/3+ 2T/1000] such that:
T/3-T/100
Σ
A(m1, m2,
(T/3) (T/100)
m
(Again, such an n2 is guaranteed to exist by a symmetric variant of Lemma 8 Bob will then play action 2 for n22 T/33 rounds, and action 3 for the remaining rounds.
What does Alice do against this sequence of play of Bob? We break this down segment by segment:
First Bob plays action for n1 rounds, moving the state from (0,0,0) to (n1 0, 0). Since > T//000, Lemma liplies that Alice plays action 1 for 1 -o(1 of these rounds.
15

---

Bob then plays action 2 for T/3 rounds, moving the state to (11. T/3.0/) 0). By the guarantee Lemma 8 Alice will still play action for o(1) of these rounds.
Bob then plays action for n2 - T/3 more rounds, moving the state to (n1, n2, 0). This at most 7/500 rounds, which will be negligible in our final swap regret computation.
Bob then plays action for (T/3) (T/100) rounds, moving the state to ( ./3 T/100). By the guarantee of Lemma Alice will play action for 1-o(1) o(1) of these rounds.
Bob then plays action 3 for the remaining rounds. This most T/100 rounds, which will be negligible in our final swap regret computation.
The key observation is that Alice would significantly improve her expected utility (by S2(2)) by playing action 3 every time she played action 2, and therefore Alice has linear swap regret. To see this, note that Alice plays action for least (1-ol (1-)(1))(((3)))
T/4 rounds when Bob is playing action 3. On the other hand the number of rounds where both Alice and Bob play action 2 most the T /500 rounds the third segment. Therefore the expected gain from switching from action 2 to action 3 is at least 7/4- 7/500- = (2(),, and therefore the algorithm A incurs ((T) swap regret.
(T/100))
16

---

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: This is a theoretical paper, and the claims made in the abstract and introduction don't tt overstate what's theoretically established in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Conditions and assumptions for all results are clearly stated.
Guidelines:
The answer NA means that the paper has no 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 a separate "Limitations" section 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-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
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]
17

---

The proofs of all theorems and supporting lemmas are provided in the main text or the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not 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 to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of 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)?
Answer: [NA]
Justification: The paper does not include experiments. (We have produced some helpful illustrations with code, but these serve entirely to help illustrate the mathematical theorems in the text).
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a 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 a 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 often one good way to 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 a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require 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 new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to 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 have some path reproducing verifying the results.
5. Open access to data and code
18

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pippscc/puullc//uuu /tte:///uuddde/oooSuuubbmiibia ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
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 to appreciate the results and make sense of them.
The full details can be provided either with the code, in 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: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error 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.)
19

---

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 1-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 enror rates).
If error bars reported in tables 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
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The research conforms to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed (it focuses on a fundamental theoretical question).
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 societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release models nor datasets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source 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 com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's '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: The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. 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 nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
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 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: The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on 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 NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "6OPLVvQi6o", "reviewer": "Reviewer_b4Uc", "summary": "The paper studies the convergence of no-swap-regret dynamics in zero-sum games. In particular, it is shown that in almost all symmetric zero-sum games and under a symmetric initialization, no-swap-regret dynamics are guaranteed to converge in a last-iterate sense to a Nash equilibrium; all of the previous assumptions are necessary. This establishes a stark separation between external and swap regret as a predictor for the day-to-day behavior of the dynamics. Furthermore, they complement the previous result by showing that any no-swap-regret algorithm must rely on an asymmetric function of the previously observed rewards.", "questions": "See above.", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "One important question in the theory of learning in games is to characterize learning algorithms which guarantee iterate-convergence to Nash equilibria in zero-sum games. Many common algorithms, such as MWU, do not have that property. While there are some positive results in the literature mostly concerning optimistic mirror descent, they are rather isolated and do not provide a more appealing characterization. This paper provides an interesting such class of algorithms: those minimizing swap regret. I believe that this is an important contribution, and further complements a recent line of work that illuminates other strong properties of swap regret. The result is also surprising; at first glance, studying no-swap-regret dynamics in zero-sum games seems counterintuitive because of the connection between CCE and NE in such games. The necessity of using a time-asymmetric function for minimizing swap regret is also interesting, and appears to be new. Overall I believe that this paper would be well-received from the learning in games community at NeurIPS.", "weaknesses": "One weakness is that the proof of the main result is fairly straightforward and somewhat uninformative, in that it relies on an elementary observation (Lemma 1), perhaps suggesting that the result is not particularly deep. \n\nIn terms of the organization of the paper, I feel that not enough gravity has been given to Section 4. The proof in Appendix A appears to contain a number of interesting ideas which are not discussed in the main body. One suggestion would be to expand that section, perhaps at the cost of deferring to the appendix some of the earlier proofs that are not particularly interesting, such as those of Lemmas 1 and 2. It would also strengthen the paper if the authors could explain further the significance of the main result in Section 4, potentially discuss implications and applications. It also seems that the results in Section 3 are not particularly well-connected with the result of Section 4; perhaps the authors can address this point in the revision as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your support! We particularly appreciate that you point out that you find our contribution to be both important as well as surprising!\n\nWe believe that the relative simplicity of our proof (when e.g. compared against the analysis of optimistic mirror descent) should be seen as an important benefit of our analysis. Not only is this result surprising and important but it is also easy to articulate and parse, while at the same time being applicable to a wide range of no-swap regret algorithms.   \n\nFurthermore, we very much appreciate your acknowledgement that the proofs of Section 4 that have been deferred to the Appendix have a number of interesting ideas! We will follow your suggestions to move these points in the main body as well as overall implement your helpful recommendations to further enhance our paper.   One interesting implication of Section 4 is that although the vector of aggregate payoffs/probabilities of historical play is a natural and concise state space for no-regret algorithms such as FTRL, it does not suffice for swap-regret, raising interesting questions about exploring the Pareto frontier of space-efficient and easily interpretable no-swap regret algorithms.     \n\nWe hope that our answers, including our commitment to reorganize Section 4, addressed your remaining concerns and if so you would be willing to increase your score. Thank you again for your helpful suggestions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RZRhYFu34A", "reviewer": "Reviewer_xwUS", "summary": "This submission studies no-swap-regret dynamics in two-player zero-sum games. In particular, they make the novel observation that no-swap-regret dynamics provably converge in a last-iterate-like sense (\"frequent iterate convergence\") to Nash equilibria in symmetric two-player zero-sum games. In order to show this result, the authors prove that time-averaged convergence of symmetric action profiles implies frequent-iterate convergence to the same distribution. This, combined with the fact that \"almost all\" (in a measure-theoretic sense) two-player symmetric zero-sum games have a unique Nash/correlated equilibrium, yields the authors' main result. \n\nThe authors also show that this result does not hold for no-external-regret dynamics, and that it does not hold for no-swap-regret dynamics outside the class of symmetric two-player zero-sum games in general.", "questions": "If you fix the swap regret dynamics of each player (e.g., the Blum-Mansour algorithm instantiated with MWU), can you say anything about the last-iterate convergence of the dynamics (beyond the frequent-iterate convergence shown in the submission)? Can you give a necessary/sufficient condition for last-iterate convergence of no-swap-regret dynamics?\n\nDo your results carry over to symmetric extensive-form games with incomplete information? \n\nComment: The writing is a bit sloppy in places, and the submission could benefit from another pass by the authors. For example, there are typos/missing references in footnote 1, line 155, and line 166.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The fact that no-swap-regret dynamics converge to Nash equilibria in a near-last-iterate sense is interesting, and is the first result of its kind to the best of my knowledge. (As the authors point out, one can get last-iterate convergence convergence to equilibria if all players use \"optimistic\" no-regret learning algorithms, but this presupposes that all players coordinate ahead of time to use a specific instantiation of a learning algorithm.)\n\nThis result is important because it gives a reason why one may prefer to play no-swap-regret dynamics over no-external-regret dynamics in (a subset of) two-player zero-sum games. Moreover, the results are interesting for using learning dynamics for the purposes of equilibrium computation: computing the time-average distribution over actions for each player is no longer required in symmetric two-player zero-sum games if both players are instantiated with no-swap-regret dynamics. \n\nThe authors' other results are complementary, in the sense that they answer several obvious questions that the reader may have after reading the authors' main result. (E.g., \"Do these results extend to no-external-regret dynamics?\", \"Do these results extend beyond symmetric games?\")\n\nFinally, the theoretical analysis is presented in a straightforward manner and was relatively easy for me to follow.", "weaknesses": "While the authors main result is interesting, I would have like to have seen it fleshed out a bit more, especially with respect to frequent-iterate convergence vs last-iterate convergence. (See 'Questions' for more details.) \n\nThe empirical results in Figures 1 and 2 are cool, and it would have been nice to see a more robust set of experiments/simulations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your support! We are very encouraged to hear that you find our results to be both important as well as interesting!\n\nCurrently, we do not have any stronger analysis for the case of specific no-swap regret algorithms such as e.g., the Blum-Mansour initiated with MWU. Empirically, we observe last-iterate convergence and so we believe that this holds. Overall, we agree that each well studied instance of no-swap algorithms deserves individual attention and we are happy to explicitly pose this an open question for future work.  \n\nOur results should extend to any game that has even an inefficient interpretation as a 2-agent normal form game (e.g. extensive form games or Bayesian games with private information). However note that we do assume we operate in a full-information setting (where the full counterfactual of losses is available to us) -- it is not obvious how to extend these results to e.g. the case of bandit feedback (it is not even clear what “symmetric dynamics” should mean in such partial-information settings).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Yd1OW0gxrL", "reviewer": "Reviewer_r1mG", "summary": "This paper studies the convergence properties of no-swap-regret learning dynamics in symmetric two-player zero-sum games. The paper's main result is that in almost all symmetric zero-sum games with symmetric initializations, if both agents run identical no-swap-regret algorithms, their joint strategy profiles will have frequent-iterate convergence to a Nash equilibrium. This result is enabled by showing (1) almost all symmetric zero-sum games have a unique Nash equilibrium and thus a unique correlated equilibrium; (2) time-averaged convergence of symmetric strategy profiles to *a* product distribution implies frequent-iterate convergence to the same distribution. Here, frequent-iterate convergence to some strategy profile $\\sigma$ means that almost all joint strategy profiles will be arbitrarily close to $\\sigma$ as time goes on. Moreover, this convergence result does not generalize to asymmetric games. This paper also shows that any no-swap-regret algorithm must play time-asymmetric functions over the set of history rewards. In contrast, specific no-external-regret algorithms, like Multiplicative Weights Update, are based on symmetric functions.", "questions": "1. Is it possible to prove a convergence rate to a Nash equilibrium in terms of the swap regret of the algorithm?\n2. In the abstract, it is claimed that relaxing the symmetric initializations would destroy the convergence result. But I do not find this result in the main body. Does the convergence hold regardless of the initialization as OGDA/OMWU?\n3. What are the convergence properties when both agents use non-identical swap-regret algorithms in symmetric zero-sum games? Is there a counterexample that they do not converge in this case?", "limitations": "See weakness.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper studies an interesting question of the convergence properties of no-swap-regret learning in two-player zero-sum games. Although we know no-swap-regret dynamics diverge for general zero-sum games, this paper shows a frequent-iterate convergence to a Nash equilibrium in symmetric zero-sum games with symmetric initialization. These assumptions on the game and initializations are very strong, but the paper also shows they are necessary for convergence. The proofs in the paper are also simple.", "weaknesses": "1. In the introduction, the paper motivates the study by \"*Although it is possible to stabilize learning dynamics in zero-sum games using, e.g., optimistic variants of MWU, such results leave something to be desired as they presuppose that the agents coordinate to use a specific instantiation of a learning algorithm.* I thought the result would allow the two agents to use any algorithms so long as they are no-swap-regret. However, the convergence result still requires both agents to coordinate and use an identical algorithm. Moreover, this result also requires both agents to have symmetric initializations, while no-external-regret algorithms like OGDA and OMWU do not. Why is this an advantage over using OGDA/OMWU?\n2. There are no results on the rates of convergence. \n3. Typos:\n   1. Line 104: \"$G_A(a_t, b_t) = G_B(b_t, a_t)$\" should be $G_A(a_t, b_t) = G_A(b_t, a_t)$?\n   2. Line 155: Missing reference\n   3. Line 173: change to \"an equilibrium\"\n   4. Line 216: \"with with\"\n   5. Line 251: \"identical identical\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your support. We are very happy to hear that you found the subject matter interesting and that you appreciate the simplicity of our proofs!\n\n\nThe reviewer asks “why is this an advantage over using OGDA/OMWU?” We don’t think OGDA/OMWU is inherently better or worse than NoSwapRegret algorithms, it really depends on the application. Our goal is to expand the set of algorithms/settings where it is known that we can obtain last-iterate convergence. If last-iterate convergence is the only goal, then OGDA/OMWU may be sufficient. But if we have other goals like robustness to manipulation or a correlated-equilibrium-like structure, then we may prefer to use no swap regret instead. Our result shows that in that case, we obtain (essentially) last-iterate convergence for free.\n\nWhile the symmetric initialization may appear restrictive at first, it is commonly used in practice in what we call “self-play” — i.e., we only keep a single agent that competes against themselves (see [1-3] for a handful examples in different applications). Hence, understanding self-play behavior can lead to new insights in many such real world applications. An important emerging application is “AI Debate” (see e.g. [4] and references therein) a zero-sum game with a very large strategy space in the area of AI Safety for which novel no-swap regret algorithms have been recently developed. For symmetric versions of those games, no swap regret provides important benefits since Nash equilibria can be computed without averaging over a large number of strategies which are not easy to keep in memory.\n\nQ1. Although we didn’t explicitly consider convergence rates in our paper, we immediately inherit the known time-averaged convergence rates to the space of CE (since the unique CE of the game is this symmetric NE that we are converging to). That is, if we have a learning algorithm with swap regret bounded by R(T), we should approach this NE at a rate of ~R(T)/T. We are happy to add a discussion of rates to the paper. It is an interesting question to understand if variations on our analysis can lead to rates stronger than those naively obtained through the existing time-average convergence bounds.\n\nQ2.  Asymmetric initializations destroy the convergence theorem:  In terms of establishing that relaxing the symmetric initializations destroys the convergence result it suffices to run a single simulation of e.g. Blum-Mansour algorithm in Rock-Paper-Scissors with asymmetric initial state. Since this is relatively easy to verify we had initially decided against adding such a figure, however, if you think this will strengthen our paper, we will be happy to add it. (See figure attached to the general response).\n\n Q3. Non-identical swap regret algorithms in symmetric zero-sum games destroy the convergence theorem: Again a single simulation would suffice to establish this result. E.g. Running Blum-Mansour algorithm with MWU and different rates of decreasing step-sizes would suffice. Interestingly, one can argue that this question reduces to Q2 hence the above counter-example suffices. We can interpret Blum-Mansour with MWU and different initializations as running two different variants of Blum-Mansour each of them running with a slightly different FTRL algorithm where the regularizer has absorbed their distinct initializations.  \n\n\nWe hope that our answers addressed your questions above and if so you would consider increasing your score accordingly. Thank you again for your interesting questions!\n\n[1] Lanctot, Marc, et al. Section A.3 in \"A unified game-theoretic approach to multiagent reinforcement learning.\" Advances in neural information processing systems 30 (2017).\n\n[2] McAleer, S., Lanier, J. B., Wang, K., Baldi, P., Fox, R., & Sandholm, T. (2022). Self-play psro: Toward optimal populations in two-player zero-sum games. arXiv preprint arXiv:2207.06541.\n\n[3] Swamy, Gokul, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alekh Agarwal. \"A minimaximalist approach to reinforcement learning from human feedback.\" arXiv preprint arXiv:2401.04056 (2024).\n\n[4] Chen, Xinyi, Angelica Chen, Dean Foster, and Elad Hazan. \"Playing large games with oracles and ai debate.\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1m92wWr0sI", "reviewer": "Reviewer_NEnG", "summary": "The paper proves that in \"almost all\" symmetric zero-sum two-player games (excluding a measure zero set), if both players apply the same no-swap-regret algorithm with the same initialization, then the players' iterates satisfy frequent-iterate convergence to Nash-equilibrium.\n\nThe main two lemmas forming the proof are: Lemma 1, which shows that time-average convergence of symmetric action profiles leads to frequent-iterate convergence; and Lemma 2, which demonstrates that almost all symmetric zero-sum games have a unique correlated equilibrium (CE), thereby implying a unique Nash equilibrium (NE).\n\nFinally, the paper shows that no-swap-regret algorithm cannot be determined entirely by cummulative cost induced by the opposing's player strategy (this is unlike to some no-regret algorithm such as vanilla FTRL). This result is outside the scope of games (the other player is adverserial and induce some arbitrary loss).", "questions": "* Do you think it is possible to show a non-asymptotic guarantee in this setting? I.e., to show the convergence rate in terms of the algorithm's regret guarantee?\n* In line 246: what do you mean by the \"*vanishing set* of a non-trivial polynomial\"?", "limitations": "See Weaknesses", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper is quite self-contained and gives a good background on game theory and the different notions of convergence to equilibria.\n* Overall, the paper is well written, and most of the proofs are quite clear and easy to follow.", "weaknesses": "The main limitation of this paper is that while the it demonstrates frequent-iterate convergence to Nash equilibrium for the family of no-swap-regret algorithms under specific conditions, there are existing algorithms that achieve last-iterate convergence to Nash equilibrium, in any zero-sum game, without the need for the symmetry and uniqueness constraints assumed here. In this context, the significance of the paper appears somewhat limited, as it establishes a much weaker guarantee than what is generally achievable.\n\nIt should also be noted that the abstract is somewhat misleading: The autors say that *no-swap-regret dynamics are guaranteed to converge in a strong, last-iterate sense to the Nash equilibrium*. This is not true, the dynamics will give frequent-iterate convergence. In fact the authos explicitly state in Thorem 3 that *\"it is not possible to prove (last-iterate) convergence to Nash equilibrium\"*. \n\n************************************\n\n#### Typos and other comments\n\nLine 101: There are also exist algorithms with regret $\\tilde O (1)$.\n\nLine 155: missing citations\n\nLine 247: unique -> multiple?\n\nLine 249: Theorem -> Lemma\n\nLine 251: identical identical -> identical\n\nLine 300: It is a feature of only **some** no-regret algorithms", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We are happy to hear that you found our paper to be self-contained, well written and easy to read!\n\nWe view the main contribution of our paper mapping the landscape of which algorithms/settings it is possible to obtain last-iterate convergence. Note that in terms of algorithms our result is very general as it captures widely used algorithms such as Blum-Mansur and Stolz-Lugosi as well as newly developed ones [18,42].\n\nWe believe the class of symmetric zero-sum games is central to many Machine learning  applications, e.g., [1-4]. The uniqueness assumption is somewhat technical and easily achieved by any tiny perturbation of payoffs. A technique commonly used in practice is  “self-play” — i.e. we only keep a single agent that competes against themselves. We observe that our analysis exactly corresponds to self-play using no swap regret algorithms. In many situations we may want to use no swap regret algorithms for other reasons such as robustness to manipulation or a correlated-equilibrium-like structure. Our result shows that in that case, we obtain last-iterate convergence for free.\n\nWe opted for not mentioning novel technical terminology of frequent iterate convergence in the abstract to improve readability, but we are happy to change that if the reviewer thinks it will improve the paper. We made sure to clarify what we mean in the intro and explain in simple language why this result is the strongest possible without further assumptions.\n\n\nQ1. See our comment in response to Q1 of Reviewer r1mG re: rates of convergence.\n\nQ2. A non-trivial polynomial is a polynomial that does not always evaluate to zero. The vanishing set of a (multi-variate) polynomial is the set of input values such that its value becomes equal to zero.\n\nWe hope that our answers addressed your initial questions and if so that you would consider increasing your score. Thank you again for your time and interesting questions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their careful and thoughtful reviews of our paper. We respond to each review individually below. (The PDF attached to this global rebuttal contains a figure accompanying a response to a question of Reviewer r1mG).

Meta-review: This paper proves that in symmetric zero-sum games that satisfy some additional assumptions (symmetric initialization), no-swap-regret dynamics will provably converge to Nash equilibrium in the frequent-iterate sense.  This guarantee does not extend to asymmetric games.  It includes additional results that are likely to be significant (e.g., no-swap-regret dynamics cannot be implemented as a time-symmetric function of observed rewards).

Most of the reviewers found the paper's results to be an important contribution to the growing literature on the properties of no-swap-regret algorithms.  One reviewer was concerned that the language of last-iterate convergence was misleadingly strong; the authors proposed using more precise frequent-iterate language in the camera-ready revision, and I encourage them to do so.
Decision: Accept (poster)