Convergence of No-Swap-Regret Dynamics in Self-Play

Authors: renato  paes leme
georgios  piliouras
google  deepmind
jon  schneider
google  research
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:39:46

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.

Main paper: 
 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 [16, 47, 54] . The significance of this area has been amplified by the emergence of prominent machine learning architectures and applications relying on multi-agent, typically zero-sum, games [42, 32, 46, 52, 14, 49, 10] . Symmetric zero-sum games and their dynamics are actually of particular interest both from a traditional evolutionary perspective [54, 13] as well as from a modern Machine Learning perspective as creating a population of agents that compete against each other in a heads-up fashion to outperform each other ("self-play") has been shown to be a reliable recipe for creating super-humanly capable agents for a wide range of tasks [9, 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 [44, 28, 30, 40, 3, 4, 55, 26, 45] . Notably, these instability and chaotic behaviors persist even in the analysis of well-known online optimization algorithms, such as Multiplicative Weights Updates (MWU/Hedge), Online Gradient Descent, Follow-the-Regularized-Leader a.o., even within the narrow but seminal class of (symmetric) zero-sum games [7, 18, 19, 20] .Although it is possible to stabilize learning dynamics in 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 a specific instantiation of a learning algorithm. Ideally, we would like instead to be able to prove such strong convergence results based on more abstract properties of the dynamics. 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 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 i 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 [11, 53] with very recent work providing further efficient such reductions [21, 48] . The stronger nature of swap regret results into numerous applications, such as (multi)-calibration [31, 37, 51, 35, 33] , robustness against dynamic strategic behavior [24, 41, 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 time-average empirical distribution of play resulting from no-internal/swap regret algorithms is guaranteed to converge to the set of correlated equilibria (CE) 1 , 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 equilibria and correlated equilibria coincide and are in fact unique (whereas CCE do not). This opens the following tantalizing possibility: Does no-swap-regret minimization suffice for Nash convergence in (almost) all zero-sum 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, a sweeping positive result holds for the case of symmetric zero-sum games.In almost all symmetric zero-sum games, under arbitrary symmetric initializations for both agents, any no-swap-regret algorithm in self-play is guaranteed to converge to the Nash equilibrium, except 2 for a vanishingly small fraction of iterates.At a technical level, the result depends on 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 are themselves non-generic within the larger class. Secondly, we leverage the symmetry of the trajectories to show that time-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 as MWU, can be completely determined by the vector of cumulative rewards and thus their outputs remain invariant to any permutation of their history, i.e. they exhibit a strong type of time-symmetry. Interestingly, we show that such time-symmetry is provably at odds with swap regret minimization. At a technical level, this argument is based on a construction that couples the behavior of online learning dynamics to particular classes of card guessing games (e.g., [25] ) 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 Follow-The-Leader algorithm, at least when averaged over certain segments of time). 
games and learning: 
 We consider a setting where two learners (Alice and Bob) are repeatedly playing a 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 ∆ N . The game G can be thought of as a pair of bilinear functions (G A , G B ) describing the payoffs for Alice and Bob: in round t, if Alice plays action a t ∈ ∆ N and Bob plays action b t ∈ ∆ N , then Alice receives payoff G A (a t , b t ) and Bob receives utility G B (a t , b t ). One specific class of games we consider are zero-sum games, where G B (a t , b t ) = -G A (a t , b t ); for such games we will omit the subscript and write G(a t , b t ) to denote G A (a t , b t ).For our purposes, a learning algorithm for Alice in this repeated game is a function which maps the history of played mixed strategies (e.g., a 1 , b 1 , a 2 , b 2 , . . . , a t-1 , b t-1 ) to the mixed strategy that Alice will play next (a t ). 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 3 .We consider two classes of learning algorithms, no-regret algorithms and no-swap-regret algorithms. Alice's (external) regret is defined viaEQUATION(with Bob's external regret Reg B defined similarly). Alice's swap regret is defined viaEQUATIONIn ( 2), the maximum is over all "swap functions" π mapping the set of N actions to itself. We extend π to act on mixed strategies (elements of ∆ N ) in the natural way (i.e., π(x) i = ∑ j x j ⋅ 1(π(j) = i)).We say Alice's learning algorithm is no-regret if it is guaranteed that Reg A = o(T ). Similarly, we say it is no-swap-regret if it is guaranteed that SwapReg A = o(T ). It is known that both efficient no-regret and no-swap-regret algorithms exist, with regret scaling as Õ( √ T ) [11] .In this note we primarily consider symmetric learning dynamics in symmetric games.A game G is symmetric if G A (a t , b t ) = G B (b t , a t ).As with zero-sum games, for symmetric games we will omit subscripts and use G(a t , b t ) to refer to G A (a t , b t ). Some games are both symmetric and zero-sum (e.g., the Rock-Paper-Scissors example we introduce later in Example 1).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.e., a t = b t for all rounds t). We write x t ∈ ∆ N to denote the common strategy that Alice and Bob play at time t.We are interested in the convergence of various types of learning algorithms to specific equilibria of G. We begin by defining the equilibria of interest.For a game G, a (not necessarily symmetric) joint strategy profile σ is a distribution over all N 2 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. It is convenient to identify the set of joint distributions ∆ N 2 with the convex subset S of the tensor product space R N ⊗ R N defined as the convex hull of all elements of the form a ⊗ b where a, b ∈ ∆ N . In particular, given a, b ∈ ∆ N , the element a ⊗ b corresponds to the joint strategy profile where Alice plays mixed strategy a and Bob independently plays mixed strategy b. In other words, the pair (i, j) is played with probability a i b j .We consider three different types of equilibria, which are (in increasing order of fineness) coarsecorrelated equilibria, correlated equilibria, and Nash equilibria. We define these below:• A coarse-correlated equilibrium is a joint strategy profile where neither Alice nor Bob has an incentive to unilaterally deviate to a single pure action. Formally, σ is a coarse-correlated equilibrium if bothE (i,j)∼σ [G A (i, j)] ≥ E (i,j)∼σ [G A (i * , j)], ∀i * ∈ [N ] E (i,j)∼σ [G B (i, j)] ≥ E (i,j)∼σ [G B (i, j * )], ∀j * ∈ [N ]• A correlated equilibrium is a 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, σ is a correlated equilibrium if bothE (i,j)∼σ [G A (i, j)] ≥ E (i,j)∼σ [G A (π A (i), j)], ∀π A ∶ [N ] → [N ] E (i,j)∼σ [G B (i, j)] ≥ E (i,j)∼σ [G B (i, π B (j))], ∀π B ∶ [N ] → [N ]• Finally, σ is a Nash equilibrium if σ is a product distribution σ = a ⊗ b and neither Alice nor Bob has an incentive to deviate(G A (a, b) ≥ G A (a ′ , b) and G B (a, b) ≥ G B (a, b ′ )). Note that we can alternatively think of Nash equilibria as the intersection of coarse-correlated (or correlated) equilibria with the set of product distributions. Example 1. Consider the Rock-Paper-Scissors zero-sum game, defined via:G(i, i) = 0, G(i, (i + 1) mod 3) = 1, G(i, (i -1) mod 3) = -1.The unique correlated equilibrium (and hence unique Nash equilibrium) in this game is the product distributionEQUATION). However, the set of coarse correlated equilibria is much largerit contains, for example, the element 1 3 (e 1 ⊗ e 1 + e 2 ⊗ e 2 + e 3 ⊗ e 3 ). Here there is no incentive to unilaterally deviate, but there is an incentive to deviate based on your choice of action (e.g., whenever you play e 1 , you can improve your utility by instead playing e 3 ).When players run learning algorithms in repeated games, they may over time converge to an equilibrium. There are three senses in which this may happen (that we discuss here). We say that Alice and Bob's strategies have time-averaged convergence to a joint strategy profile σ iflim T →∞ ∥( 1 T T ∑ t=1 a t ⊗ b t ) -σ∥ = 0.In other words, time-averaged convergence means that the average of the joint strategy profiles Alice and Bob play converges over time to σ.Likewise, we say that Alice and Bob's strategies have frequent-iterate convergence to σ if for any ε > 0, limT →∞ Pr t≤T [∥(a t ⊗ b t ) -σ∥ > ε] = 0.Here the probability is taken over t being drawn uniformly at random from all rounds between 1 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 to σ.Finally, we say that Alice and Bob's strategies have last-iterate convergence to σ iflim T →∞ ∥(a T ⊗ b T ) -σ∥ = 0.Last-iterate convergence means that the sequence of joint action profiles played by Alice and Bob directly converge to σ. Note that last-iterate convergence is a stronger property than frequent-iterate convergence, which in turn is a stronger property than time-averaged convergence.It is known that if Alice and Bob run certain types of learning algorithms, they will have time-averaged convergence to a certain type of equilibrium. Here are some known facts about learning dynamics []: • If Alice and Bob are running no-regret algorithms in a general game G, their strategies will have time-averaged convergence to a coarse correlated equilibrium of G.• If Alice and Bob are running no-swap-regret algorithms in a general game G, their strategies will have time-averaged convergence to a correlated equilibrium of G.• There exist zero-sum games G (including Rock-Paper-Scissors of Example 1) where if Alice and Bob run certain no-regret algorithms (e.g. Multiplicative Weights) Alice and Bob's strategies will not have last-iterate convergence to a coarse correlated equilibrium. 
convergence of symmetric swap regret in symmetric zero sum games: 
 There exist zero-sum games G (including Rock-Paper-Scissors of Example 1) where if Alice and Bob run certain no-regret algorithms (e.g. Multiplicative Weights) Alice and Bob's strategies will not have last-iterate convergence to a equilibrium. In the left side of Figure 1 plot the trajectory of Multiplicative Weights when Alice and Bob have the same initialization. The blue dot in the middle corresponds to the Nash equilibrium. While the strategies played average to the equilibrium, they never converge there.In this section, we 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 to a Nash equilibrium of G. In the right side of the same figure, we show the Blum-Mansour trajectory converging to equilibrium. In Appendix A, we show via a 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 x 1 , x 2 , . . . be a sequence of elements in ∆ N such that lim T →∞ ∥( 1 T T ∑ t=1 x t ⊗ x t ) -(y ⊗ y)∥ = 0for some element y of ∆ N (i.e., the profiles x t ⊗ x t time-averaged converge to y ⊗ y). Then it is the case that for any ε > 0, limT →∞ Pr t≤T [∥(x t ⊗ x t ) -(y ⊗ y)∥ > ε] = 0.(i.e., the profiles x t ⊗ x t frequent-iterate converge to y ⊗ y).Proof. For any y ∈ ∆ N , we will show that there exists a linear functional L y ∶ R N ⊗ R N → R with the property that, among all elements of the form x ⊗ x with x ∈ ∆ N , L y is uniquely minimized at y ⊗ y. As a consequence, this implies that that there exists a δ > 0 such that if∥(x ⊗ x) -(y ⊗ y)∥ > ε, for some element x ∈ ∆ N , then L y (x ⊗ x) -L y (y ⊗ y) > δ.In particular, if for some T we have thatPr t≤T [∥(x t ⊗ x t ) -(y ⊗ y)∥ > ε] ≥ γ,then we consequently have that1 T T ∑ t=1 (L y (x t ⊗ x t ) -L y (y ⊗ y)) ≥ γδ,and in turn that∥( 1 T T ∑ t=1 (x t ⊗ x t )) -(y ⊗ y)∥ ≥ γδ||L y || * ,(where ||L y || * is the dual norm of the linear functional L y and is bounded below by some constant). This directly implies the lemma statement (it is impossible for the second quantity to approach zero as T goes to infinity without the first quantity approaching zero).We now describe the linear functional L y . Let y = (y 1 , y 2 , . . . , y N ) (and for a general x ∈ ∆ N , let x = (x 1 , x 2 , . . . , x N )). Note that for any linear functional L y ∶ R N ⊗ R N → R, the value of L y (x ⊗ x) will be a homogeneous quadratic polynomial over the x i ; conversely, any such polynomial can be implemented as a linear functional over R N ⊗ R N . Moreover, since ∑ x i = 1, we can convert any (non-homogeneous) quadratic polynomial to a homogeneous one (e.g. transformingx 2 1 + x 1 + 1 to x 2 1 + x 1 ∑ x i + (∑ x i ) 2). It therefore suffices to find a quadratic polynomial over the x i that is minimized when x = y.We begin with the case where all y i > 0. In this case, we claim that the polynomialL y (x ⊗ x) = N ∑ i=1 1 y i x 2i satisfies these constraints. To see this, note that by Cauchy-Schwartz,N ∑ i=1 1 y i x 2 i = ( N ∑ i=1 x 2 i y i ) ( N ∑ i=1 y i ) ≥ ( N ∑ i=1 x i ) 2 = 1,with equality only holding when x 2 i /y i = λy i for some fixed λ. Since x and y both belong to ∆ N , this is only possible when λ = 1 and x = y.What if some of the y i equal zero? Without loss of generality, assume y i > 0 for 1 ≤ i ≤ n and y i = 0 for n + 1 ≤ i ≤ N . Now, consider the polynomialL y (x ⊗ x) = ( n ∑ i=1 1 y i x 2 i ) -2 ( n ∑ i=1 x i ) .We begin by minimizing this expression subject to ∑ n i=1 x i = s, for some 0 ≤ s ≤ 1. In this case, the second term in the above polynomial is identically -2s, so it suffices to minimize the first term. Again applying Cauchy-Schwartz, we find the minimum of the first term occurs only when x i = sy i , where it equals s 2 . The overall minimum of L y (subject to this constraint) is therefore s 2 -2s. This is in turn uniquely minimized when s = 1 (and x i = 0 for all i > n), and therefore this L y is uniquely minimized at x = y.Next we show a 'generic' symmetric zero-sum game has a unique correlated equilibrium and hence coincides with the Nash equilibrium of this game. First, we define what we mean by generic. We can identify the set of zero-sum games with R N ×N , where each element corresponds to an N × N payoff matrix for Alice. We say that a property P holds for a generic zero-sum game, if the set of points in R N ×N for which P doesn't holds form a measure zero subset of R N ×N . By this definition, the set of symmetric zero-sum games forms a measure zero subset of the set of zero-sum games, so we 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 N (N -1)/2 where each element corresponds to a skew-symmetric N × N payoff matrix for Alice. We say that a property P holds for a generic symmetric zero-sum game, if the set of points in R N ×N for which P doesn't holds form a measure zero subset of R N (N -1)/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 (i.e., all but a measure zero set of) two-player symmetric zero-sum games have a unique correlated/Nash equilibrium. Proof. By [29] a 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 A be the skew-symmetric (A ⊺ = -A) payoff matrix corresponding to the symmetric zero-sum game. A Nash 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 a 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 symmetric zero-sum game has multiple equilibria, this implies the existence of a non-quasi-strict equilibrium/optimal strategy. Let x be that non-quasi-strict mixed strategy and let S x denote its support, i.e., the set of strategies played in x with positive probability and let i be the index of the strategy not in S x such that deviating to that strategy from the symmetric (x, x) Nash equilibrium still results into payoff of zero (since the game value of any zero-sum symmetric game is zero). This implies that both antisymmetric sub-matrices of A defined by its restrictions to the sets S x and S x ∪ i respectively have a zero eigenvalue where the corresponding eigenvector is the analogously restricted subvector of x. Thus, both of their determinants are equal to zero. However, at least one of them has even dimension. It is well known that the determinant of an even dimension skew-symmetric matrix is a 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 a 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.Combining Lemma 1 and Theorem 2, we arrive at the result mentioned at the beginning of this section. Theorem 3. In a generic symmetric zero-sum game G, if Alice and Bob run identical no-swap-regret 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 is tight, i.e., it 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 x t ⊗ x t . Since no-swapregret algorithms have time average convergence to correlated equilibrium, then there is a correlated equilibrium σ of G such that ∥ 1 T ∑ T t=1 x t ⊗ x t -σ∥ → 0. By Lemma 2, σ is a Nash equilibrium, so we can write σ = y ⊗ y. Now, we can apply Lemma 1 to obtain frequent iterated convergence to σ.It is not possible to prove anything stronger, i.e., convergence to Nash, based on (symmetric) no-swapregret learning because we can take any such no-swap-regret dynamics and interject for a vanishing fraction of the history some arbitrary symmetric play where those payoff inputs are ignored by the learning dynamics (e.g. the Blum-Mansour 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.It is useful to consider which parts of the proof break when we move from swap to external regret. Both Lemma 1 and Lemma 2 no longer hold.Consider for example the executions of MWU and BM in Figure 1 . In both cases we have thatEQUATION). If we look at the empirical joint distribution σT = 1 T (∑ t x t ⊗ x t ) we obtain the following: 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 as long as its set of optimal strategies does not consist of a single pure (i.e., deterministic) strategy then it has a continuum of coarse correlated equilibria.EQUATIONProof. 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 a 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 4 is that the rich, non-equilibrating behavior of MWU and other no-regret dynamics, even under symmetric initializations, shown for Rock-Paper-Scissors and Rock-Paper-Scissors-Lizard-Spock shown in Figures 1, 2 should be common for many other symmetric games and regret-minimizing dynamics as well.We remark that the results don't generalize to asymmetric zero sum games. One example of such games is matching pennies where no-external regret dynamics like MWU are known not to exhibit lastiterate convergence and in fact diverge chaotically towards the boundary for all interior initializations, including all symmetric (non-Nash) initial conditions [8, 18] . For games with 2 actions per player, any no-external-regret algorithm is also no-swap-regret as we show in the following lemma. Lemma 5. For a game with 2 actions per player, SwapReg ≤ 2 Reg.Proof. Let {0, 1} be Alice's actions in let a t , b t ∈ ∆ 2 be a sequence of strategies played by Alice and Bob. There are 3 non-trivial swap strategies π ∶ [2] → [2] for Alice: s ↦ 0, s ↦ 1, s ↦ 1 -s. The regret of using the first two swap strategies is bounded by Reg since they map to a constant action. Let a t [s] be the s-th component of a t ∈ ∆ 2 . Then, the regret of the third strategy π is bounded by:∑ t G A (a t , b t ) -G A (π(a t ), b t ) = ∑ t a t [0](G A (0, b t ) -G A (1, b t )) + ∑ t a t [1](G A (1, b t ) -G A (0, b t )) = [∑ t G A (a t , b t ) -G A (1, b t )] + [∑ t G A (a t , b t ) -G A (0, b t )] ≤ 2 Reg4 No-Swap-Regret Algorithms are Time-Asymmetric One interesting feature of no(-external)-regret algorithms in two-player games is that the action they select at time t 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 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 G at round t via a symmetric function A t (b 1 , b 2 , . . . , b t-1 ) of Bob's mixed strategies up until t -1 (here symmetric means that the function is unchanged for any permutation of the inputs). Then there exists a game G and a sequence of play for Bob where Alice incurs Ω(T ) swap regret.As mentioned, many no-external-regret algorithms (such as multiplicative weights, and followthe-regularized leader) have the property that each A t can be written as a function of the average 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 A (i, j) equals 1 if i = j and 0 otherwise (since we will specify Bob's sequence of actions adversarially, his payoff G B 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 ∆ 3 (i.e., b t ∈ {e 1 , e 2 , e 3 }). For each i ∈ [3], let n t,i equal the number of rounds s ≤ t -1 where Bob played action i. Since A t is a symmetric function of the b s for 1 ≤ s ≤ t -1, we can write A t as a function A t (n t,1 , n t,2 , n t,3 ). Moreover, since we must have n t,1 + n t,2 + n t,3 = t -1, we can summarize the entire learning algorithm with a single 3-variable functionA(n 1 , n 2 , n 3 ) ∶ Z 3 ≥0 → ∆ 3 satisfying A(n 1 , n 2 , n 3 ) = A n1+n2+n3+1 (n 1 , n 2 , n 3 ).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 to the "follow the leader" strategy, which puts all the weight on action i if n i is significantly larger than the other n j . We formalize this in the following lemma (which employs a result of [25] on 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, i.e., Reg A = o(T ). Then for any L ≥ T /100 and n 1 , n 2 ≤ n 3 ≤ T -L, we have that1 L n3+L ∑ m=n3+1 A(n 1 , n 2 , m) 3 = 1 -o(1).Lemma 7 shows that A 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 in stretches where Bob is playing some other fixed action. The following lemma gives a weak form of this claim (but that will be sufficient for proving Theorem 6).Lemma 8. Fix any L, L ′ ≥ T /100 and let n 2 ≥ min(n 1 , L ′ ). Then there exists ann 3 ∈ [n 2 , n 2 + L] such that 1 L ′ n2-1 ∑ m ′ =n2-L ′ A(n 1 , m ′ , n 3 ) 3 = 1 -o(1).With Lemmas 7 and 8 (and their symmetric counterparts), we can construct a sequence of play for Bob where Alice incurs high swap regret. Roughly, this sequence of play proceeds as follows.• First Bob plays action 1 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 8, Alice will still play action 1 for most of these rounds.• Bob then plays action 3 for the remaining rounds. Again by applying Lemma 8, 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 Ω(T ) if she played action 3 every time she played action 2. 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, in all but a vanishing fraction of the rounds, the players must play a strategy profile close to a symmetric Nash equilibrium. Furthermore, we show that the power of no-swap-regret dynamics comes at a cost of imposing a time-asymmetry on 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 interesting direction for future work. One particularly interesting such direction would be to explore generalizations of our results beyond two player games. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: The paper does not release models nor datasets.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that 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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We show via a simple counter-example that symmetric initializations are necessary for convergence to Nash. Specifically, in Figure 3 we show the trajectory of two players running the Blum-Mansour no-swap-regret algorithm against each other, initialized with asymmetric starting conditions in the symmetric zero-sum game of Rock-Paper-Scissors. Their behavior does not converge to Nash, whereas as we have seen in Figure 1 , symmetric initialization in the same game would have led to convergence. We will construct the distribution D as follows:• For the first n 1 + n 2 + n 3 rounds, Bob will play a uniform random sequence that includes action 1 n 1 times, action 2 n 2 times, and action 3 n 3 times.• In the next L rounds, Bob will always play action 3.• Finally, in the last T ′ = T -(n 1 + n 2 + n 3 ) rounds, Bob will play a uniform random sequence that includes action 1 T ′ /3 times, action 2 T ′ /3 times, and action 3 T ′ /3 times.Note that for any such sequence, the best action in hindsight for Alice is action 3, which achieves utility exactly n 3 + L + T ′ /3. To compute Alice's expected regret, it suffices to compare Alice's expected utility to this quantity.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 is a uniformly shuffled deck of N = n 1 + n 2 + n 3 cards with n 1 cards labeled 1, n 2 cards labeled 2, and n 3 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 is 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(n 1 , n 2 , n 3 ) + O( √ N ) (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 n 1 + n 2 + n 3 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 mostn 3 + O( √ n 1 + n 2 + n 3 ) = n 3 + O( √ T ).Similarly, in the last segment of rounds, Alice's expected utility is at mostT ′ /3 + O( √ T ).Finally, in the middle segment of rounds, Alice's utility is exactly W (as this is the total weight she places on action 3). It follows that Alice's expected regret is at least (L -W ) -O( √ T ), as desired.Proof of Lemma 8. By applying Lemma 7 L times, we have that:1 L ′ ⋅ L n2-1 ∑ m ′ =n2-L ′ n2+L ∑ m=n2 A(n 1 , m ′ , m) 3 = 1 -o(1).By switching the order of summation, this implies that there must exist a fixed value of m ∈[n 2 , n 2 + L] such that 1 L ′ n2-1 ∑ m ′ =n2-L ′ A(n 1 , m ′ , m) 3 = 1 -o(1).We can take n 3 to be this value of m.With Lemmas 7 and 8 (and their symmetric counterparts), we can construct a sequence of play for Bob where Alice incurs high swap regret.Proof of Theorem 6. Fix L = T /100. Bob will begin by selecting an n 1 ∈ [T /3, T /3 + T /1000] such that:1 T /3 T /3 ∑ m ′ =1 A(n 1 , m ′ , 0) 3 = 1 -o(1).(Such an n 1 is guaranteed to exist by a symmetric variant of Lemma 8). Bob will then play action 1 for n 1 rounds followed by action 2 for T /3 rounds.Bob will then select a value n 2 ∈ [T /3 + T /1000, T /3 + 2T /1000] such that:1 (T /3) -(T /100) T /3-T /100 ∑ m ′ =1 A(n 1 , n 2 , m ′ ) 3 = 1 -o(1).(Again, such an n 2 is guaranteed to exist by a symmetric variant of Lemma 8). Bob will then play action 2 for n 2 -T /3 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 1 for n 1 rounds, moving the state from (0, 0, 0) to (n 1 , 0, 0). Since n 1 > T /1000, Lemma 7 implies that Alice plays action 1 for 1 -o(1) of these rounds.• Bob then plays action 2 for T /3 rounds, moving the state to (n 1 , T /3, 0). By the guarantee of Lemma 8, Alice will still play action 1 for 1 -o(1) of these rounds.• Bob then plays action 2 for n 2 -T /3 more rounds, moving the state to (n 1 , n 2 , 0). This is at most T /500 rounds, which will be negligible in our final swap regret computation.• Bob then plays action 3 for (T /3) -(T /100) rounds, moving the state to (n 1 , n 2 , T /3 -T /100). By the guarantee of Lemma 8, Alice will play action 2 for 1 -o(1) of these rounds.• Bob then plays action 3 for the remaining rounds. This is at 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 Ω(T )) 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 2 for at least (1 -o( 1))((T /3) -(T /100)) ≥ 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 is at most the T /500 rounds in the third segment. Therefore the expected gain from switching from action 2 to action 3 is at least T /4 -T /500 = Ω(T ), and therefore the algorithm A incurs Ω(T ) swap regret.Question Justification: There is no societal impact of the work performed (it focuses on a fundamental theoretical question). Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024).Due to their connections to equilibria, establishing fast swap regret minimization (and variations thereof) for different classes of games is a subject of a lot of recent work (e.g.,[1,2,50,56,27]).2 This minor disclaimer is necessary as it is always possible to inject such vanishingly small "noise" in any trajectory without affecting its time-average regret.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 payoffs they would have received for each of their possible N actions. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

In 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.
questions: questions: See above.
limitations: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_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. 

The 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.
strength_weakness: strength_weakness: 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.) 

The empirical results in Figures 1 and 2 are cool, and it would have been nice to see a more robust set of experiments/simulations.
questions: 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?

Do your results carry over to symmetric extensive-form games with incomplete information? 

Comment: 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: limitations: The authors have adequately addressed the limitations of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?
2. There are no results on the rates of convergence. 
3. Typos:
   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)$?
   2. Line 155: Missing reference
   3. Line 173: change to "an equilibrium"
   4. Line 216: "with with"
   5. Line 251: "identical identical"
questions: questions: 1. Is it possible to prove a convergence rate to a Nash equilibrium in terms of the swap regret of the algorithm?
2. 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?
3. 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: limitations: See weakness.
paper_summary: paper_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.

The 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).

Finally, 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).
strength_weakness: strength_weakness: 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.

It 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"*. 

************************************

#### Typos and other comments

Line 101: There are also exist algorithms with regret $\tilde O (1)$.

Line 155: missing citations

Line 247: unique -> multiple?

Line 249: Theorem -> Lemma

Line 251: identical identical -> identical

Line 300: It is a feature of only **some** no-regret algorithms
questions: 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?
* In line 246: what do you mean by the "*vanishing set* of a non-trivial polynomial"?
limitations: limitations: See Weaknesses

Comments: title: Response by the Reviewer
comment: I thank the authors for the response. I have no further questions, and I maintain my positive evaluation.
I thank the authors for answering my questions. After reading all the reviews and rebuttals, I decided to increase my score by 1.

Additional Comment: I believe It is better to define and use the "frequent iterate convergence" terminology in the abstract since it could be misleading as it differs greatly from the literature's traditional notion of "last-iterate convergence." I suggest adding the sentence in the main body (Line 148) to the abstract: "Frequent-iterate convergence means that, as time goes on, almost all joint strategies profiles the players play will be arbitrarily close to a Nash equilibrium." Also, I found the notion of "frequent iterate convergence" to be similar to the "time-average convergence" defined in [DHLZ22]: the fraction of rounds where bidders play a Nash equilibrium approaches 1 in the limit (see their abstract). Their "time-average convergence" definition is also non-standard and is not the same as "average-iterate convergence" in the literature. Thus, I think adding at least one informal definition to the abstract would help the reader understand the result better. 

Deng, X., Hu, X., Lin, T., & Zheng, W. (2022, April). Nash convergence of mean-based learning algorithms in first price auctions. In Proceedings of the ACM Web Conference. 2022
Thank you for your response and the clarifications provided. I have read all the reviews and your rebuttals. At this point, I will retain my initial score.

Regardless of the final decision on the acceptance of the paper to NeurIPS, and although this is not my primary concern, I encourage the authors to include the rate of convergence in terms of the swap regret guarantee in future versions of the paper. Additionally, I recommend being more precise in the abstract regarding the claim on last-iterate convergence - as the body of the paper demonstrates, this claim is not true.
Thanks for your reply. I will maintain my score. 

Moreover, I disagree with Reviewer NEnG that the significance of this paper is limited because there are other algorithms which are known to converge in a last-iterate sense to NE in two-player zero-sum games. I agree with the authors that there is value in discovering new properties of existing/popular algorithms for playing in games.