Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games

## Abstract

Abstract Algorithms based on regret matching, specifically regret matching + (RM + ), and its variants are the most popular approaches for solving large-scale two-player zero-sum games in practice.
Unlike algorithms such as optimistic gradient descent ascent, which have strong last-iterate and ergodic convergence properties for zero-sum games, virtually nothing is known about the last-iterate properties of regret-matching algorithms.
Given the importance of last-iterate convergence for numerical optimization reasons and relevance as modeling real-word learning in games, in this paper, we study the last-iterate convergence properties of various popular variants of RM + . First, we show numerically that several practical variants such as simultaneous RM + , alternating RM + , and simultaneous predictive RM + , all lack last-iterate convergence guarantees even on a simple 3 × 3 3 3 3\times 3 game.
We then prove that recent variants of these algorithms based on a smoothing technique do enjoy last-iterate convergence: we prove that extragradient RM + and smooth Predictive RM + enjoy asymptotic last-iterate convergence (without a rate) and 1 / t 1 𝑡 1/\sqrt{t} best-iterate convergence. Finally, we introduce restarted variants of these algorithms, and show that they enjoy linear-rate last-iterate convergence.

## 1 Introduction

Saddle-point optimization problems have attracted significant research interest with applications in generative adversarial networks (Goodfellow et al., ), imaging (Chambolle & Pock, ), market equilibrium (Kroer et al., ), and game-solving (Von Stengel, ).
Matrix games provide an elementary saddle-point optimization setting, where the set of decisions of each player is a simplex and the objective function is bilinear. Matrix games can be solved via self-play, where each player employs a regret minimizer, such as online gradient descent ascent (GDA), multiplicative weight updates (MWU), or Regret Matching^+ (RM^+). In this case, a well-known folk theorem shows that the average of the strategies visited at all iterations converges to a Nash equilibrium of the matrix game, at a rate of $O(1/\sqrt{T})$ for GDA, MWU and RM^+, and at a rate of $O(1/T)$ for predictive variants of GDA and MWU (Syrgkanis et al., ; Rakhlin & Sridharan, ).

In recent years, there has been increasing interest in the last-iterate convergence properties of algorithms for saddle-point problems (Daskalakis & Panageas, ; Golowich et al., ; Wei et al., ; Lee et al., ).
There are multiple reasons for this.
First, since no-regret learning is often viewed as a plausible method of real-world gameplay, it would be desirable to have the actual strategy iterates to converge to an equilibrium instead of only having the average converge.
Secondly, suppose self-play via no-regret learning is being used to compute an equilibrium. In that case, iterate averaging can often be cumbersome, especially when deep-learning components are involved in the learning approach, since it may not be possible to average the outputs of a neural network.
Thirdly, iterate averaging may be slower to converge since the convergence rate is limited by the extent to which early “bad” iterates are discounted in the average.
Even in the simple matrix game setting, interesting questions arise when considering the last-iterate convergence properties of widely used algorithms.
For instance, both GDA and MWU may diverge (Bailey & Piliouras, ; Cheung & Piliouras, ), whereas their predictive counterparts, Optimistic GDA (OGDA) (Daskalakis et al., ; Mertikopoulos et al., ; Wei et al., ) and Optimistic MWU (OMWU) (Daskalakis & Panageas, ; Lei et al., ) converge at a linear rate under some assumptions on the matrix games. Furthermore, it has been demonstrated that OGDA has a last-iterate convergence rate of $O(1/\sqrt{T})$ without any assumptions on the game (Cai et al., ; Gorbunov et al., ).

On the other hand, very little is known about the
last-iterate convergence properties of RM^+ and its variants, despite their huge popularity in solving large-scale games in practice.
Specifically, RM^+ (Hart & Mas-Colell, ; Tammelin et al., ) is a simple, stepsize-free regret minimizer, guaranteeing $O(1/\sqrt{T})$ ergodic convergence in self-play for matrix games. When combined with counterfactual regret minimization (Zinkevich et al., ), linear averaging, and alternation, RM^+ has been used in multiple important milestones in solving extremely large poker games (Bowling et al., ; Moravčík et al., ; Brown & Sandholm, ). Despite its very strong empirical performance, the last-iterate behavior of (vanilla) RM^+ may diverge even on small matrix games, e.g., rock-paper-scissors (Lee et al., ).

Moreover, unlike OGDA and OMWU, the predictive variants of RM^+ do not enjoy similar theoretical speed up.
Specifically,
predictive RM^+ (PRM^+), a predictive variant of RM^+, was introduced in (Farina et al., ) and shown to achieve very good empirical performance in some games. However, it still only guarantees $O(1/\sqrt{T})$ ergodic convergence for matrix games (unlike OGDA and OMWU). To address this, Farina et al. () introduce two variants of RM^+ with $O(1/T)$ ergodic convergence for matrix games, namely, Extragradient RM^+ (ExRM^+) and Smooth Predictive RM^+ (SPRM^+), but the last-iterate convergence properties of all these variants remain unknown.(^1^11We note that a recent work (Meng et al., ) does study the last-iterate convergence of RM^+ variants, but for strongly-convex strongly-concave games, which is incomparable to our matrix game setting.)

Motivated by this, in this work, we
study both theoretically and empirically the last-iterate behavior of RM^+ and its various variants.
Our main results are as follows.

- 1.
We provide numerical evidence that RM^+ and important variants of RM^+, including alternating RM^+ and PRM^+, may fail to have asymptotic last-iterate convergence. Conversely, we also prove that RM^+ *does* have last-iterate convergence in a very restrictive setting, where the matrix game admits a strict Nash equilibrium.
- 2.
We then study the convergence properties of two recently proposed variants of RM^+: ExRM^+ ([Algorithm 4](#alg4)) and SPRM^+ ([Algorithm 5](#alg5)). For these two algorithms, we first prove the asymptotic convergence of the last iterate (without providing a rate). We then show a $O(1/\sqrt{t})$-rate for the duality gap for the best iterate after $t$ iterations.
Building on this last observation, we finally introduce new variants of ExRM^+ and SPRM^+ that restart whenever the distance between two consecutive iterates has been halved, and prove that they enjoy linear last-iterate convergence.
- 3.
Existing last-iterate convergence results rely heavily on the monotonicity assumption (or even strong monotonicity), while RM^+ and its variants are equivalent to solving a variational inequality (VI) problem with a *non-monotone* operator which satisfies the Minty condition. Our proofs use new observations on the structure of the solution set and provide characterizations of the limit points of the learning dynamics, which might be of independent interest for analyzing last-iterate convergence of other algorithms.
- 4.
We verify the last-iterate convergence of ExRM^+ and SPRM^+ (including their restarted variants that we propose) numerically on four instances of matrix games, including Kuhn poker and Goofspiel. We also note that while vanilla RM^+, alternating RM^+, and SPRM^+ may not converge, alternating PRM^+ exhibits a surprisingly fast last-iterate convergence.

#### Notation.

We write $\bm{0}$ for the vector with 0 0 on every component and $\bm{1}_{d}$ for the vector in $\mathbbm{R}^{d}$ with $1$ on every component. We use the convention that $\bm{0}/0=(1/d)\bm{1}_{d}$. We denote by $\Delta^{d}$ the simplex: $\Delta^{d}=\{{x}\in\mathbbm{R}^{d}_{+}\;|\;\langle{x},\bm{1}_{d}\rangle=1\}$.
For $x\in\mathbbm{R}$, we write $[x]^{+}$ for the positive part of $x:[x]^{+}=\max\{0,x\}$, and we overload this notation to vectors component-wise. We use $\|z\|$ to denote the $\ell_{2}$ norm of a vector $z$.

## 2 Preliminaries on Regret Matching + and Self Play

In this paper, we study iterative algorithms for solving the following matrix game:

$$ $\min_{x\in\Delta^{d_{1}}}\max_{y\in\Delta^{d_{2}}}x^{\top}Ay$ (1) $$

for a payoff matrix $A\in\mathbbm{R}^{d_{1}\times d_{2}}$. We define $\mathcal{Z}=\Delta^{d_{1}}\times\Delta^{d_{2}}$ to be the set of feasible pairs of strategies. The duality gap of a pair of feasible strategy $(x,y)\in\mathcal{Z}$ is defined as

$$ $\operatorname{DualityGap}(x,y):=\max_{y^{\prime}\in\Delta^{d_{2}}}x^{\top}Ay^{\prime}-\min_{x^{\prime}\in\Delta^{d_{1}}}x^{\prime\top}Ay.$ $$

Note that we always have $\operatorname{DualityGap}(x,y)\geq 0$, and it is well-known that $\operatorname{DualityGap}(x,y)\leq\epsilon$ implies that the pair $(x,y)\in\mathcal{Z}$ is an $\epsilon$-Nash equilibrium of the matrix game ([1](#S2.E1)). When both players of ([1](#S2.E1)) employ a regret minimizer, a well-known folk theorem shows that the averages of the iterates generated during self-play converge to a Nash equilibrium of the game (Freund & Schapire, ). This framework can be instantiated with any regret minimizers, for instance, online mirror descent, follow-the-regularized leader, regret matching, and optimistic variants of these algorithms. We refer to (Hazan et al., ) for an extensive review on regret minimization. From here on, we focus on solving ([1](#S2.E1)) via Regret Matching^+ and its variants.
To describe these algorithms, it is useful to define for a strategy $x\in\Delta^{d}$ and
a loss vector $\ell\in\mathbbm{R}^{d}$, the negative instantaneous regret vector ${f}({x},{\ell})=\ell-{x^{\top}\ell}\cdot\bm{1}_{d}$,(^2^22Here, $d$ can be either $d_{1}$ or $d_{2}$. That is, we overload the notation $f$ so its domain depends on the inputs.)
and also define the normalization operator $g:\mathbbm{R}_{+}^{d_{1}}\times\mathbbm{R}_{+}^{d_{2}}\rightarrow\mathcal{Z}$ such that for $z=(z_{1},z_{2})\in\mathbbm{R}_{+}^{d_{1}}\times\mathbbm{R}_{+}^{d_{2}}$, we have $g(z)=(z_{1}/\|z_{1}\|_{1},z_{2}/\|z_{2}\|_{1})\in\mathcal{Z}$.

#### Regret Matching + (RM + ), alternation, and Predictive RM + .

We describe Regret Matching^+ (RM^+) in Algorithm [1](#alg1) (Tammelin, ).(^3^33 Typically, RM^+ and PRM^+ are introduced as regret minimizers that return a sequence of decisions against any sequence of losses (Tammelin et al., ; Farina et al., ). For conciseness, we directly present them as self-play algorithms for solving matrix games, as in Algorithm [1](#alg1) and Algorithm [3](#alg3).)
It maintains two sequences: a sequence of joint aggregate payoffs $(R^{t}_{x},R^{t}_{y})\in\mathbbm{R}_{+}^{d_{1}}\times\mathbbm{R}_{+}^{d_{2}}$ updated using the instantaneous regret vector, and a sequence of joint strategies $(x^{t},y^{t})\in\mathcal{Z}$ directly normalized from the aggregate payoff.
Note that the update rules are stepsize-free and only perform closed-form operations (thresholding and rescaling).

A popular variant of RM^+, Alternating RM^+ (Tammelin et al., ; Burch et al., ), is shown in Algorithm [2](#alg2). In alternating RM^+, the updates between the two players are asynchronous, and at iteration $t$, the second player observes the choice $x^{t+1}$ of the first player when choosing their own decision $y^{t+1}$. Alternation leads to faster empirical performance for solving matrix and extensive-form games, even though the theoretical guarantees remain the same as for vanilla RM^+ (Burch et al., ; Grand-Clément & Kroer, ).

Figure: Algorithm 1 Regret Matching^+ (RM^+)

Figure: Algorithm 3 Predictive RM^+ (PRM^+)

Finally, we describe Predictive RM^+ (PRM^+) from (Farina et al., ) in Algorithm [3](#alg3). PRM^+ incorporates predictions of the next losses faced by each player (using the most recent observed losses) when computing the strategies at each iteration, akin to predictive/optimistic online mirror descent (Rakhlin & Sridharan, ; Syrgkanis et al., ).

In practice, PRM^+ can also be combined with alternation, but despite strong empirical performance, it is unknown if alternating PRM^+ enjoys ergodic convergence. In contrast, based on the aforementioned folk theorem and the regret guarantees of RM^+ (Tammelin, ), alternating RM^+ (Burch et al., ), and PRM^+ (Farina et al., ), the duality gap of the average strategy of all these algorithms goes down at a rate of $O(1/\sqrt{T})$.
However, we will show in the next section that the iterates $(x^{t},y^{t})$ themselves may not converge. We also note that despite the connections between PRM^+ and predictive online mirror descent, PRM^+ does not achieve $O(1/T)$ ergodic convergence, because of its lack of stability (Farina et al., ).

#### Extragradient RM + and Smooth Predictive RM +

We now describe two theoretically-faster variants of RM^+ recently introduced in (Farina et al., ). To provide a concise formulation, we first need some additional notation.
First, we define the clipped positive orthant $\Delta^{d_{i}}_{\geq}:=\{u\in\mathbbm{R}^{d_{i}}_{+}:u^{\top}\bm{1}_{d_{i}}\geq 1\}$ for $i=1,2$ and $\mathcal{Z}_{\geq}=\Delta^{d_{1}}_{\geq}\times\Delta^{d_{2}}_{\geq}$. For a point $z\in\mathcal{Z}_{\geq}$, we often write it as $z=(Rx,Qy)$ for positive real numbers $R$ and $Q$ such that $(x,y)=g(z)$. Moreover, we define the operator $F:\mathcal{Z}_{\geq}\rightarrow\mathbbm{R}^{d_{1}+d_{2}}$ as follows: for any $z=(Rx,Qy)\in\mathcal{Z}_{\geq}$,

$$ $F(z)=F((Rx,Qy))=\begin{bmatrix}f(x,Ay)\\ f(y,-A^{\top}x)\end{bmatrix}=\begin{bmatrix}Ay-x^{\top}Ay\cdot\bm{1}_{d_{1}}\\ -A^{\top}x+x^{\top}Ay\cdot\bm{1}_{d_{2}}\end{bmatrix},$ (2) $$

which is $L_{F}$-Lipschitz-continuous over $\mathcal{Z}_{\geq}$ with $L_{F}=\sqrt{6}{\mathchoice{\left\|A\right\|}{\|A\|}{\|A\|}{\|A\|}}_{op}\max\{d_{1},d_{2}\}$ (Farina et al., ).
We also write $\Pi_{\mathcal{Z}_{\geq}}(u)$ for the $L_{2}$ projection onto $\mathcal{Z}_{\geq}$ of the vector $u$: $\Pi_{\mathcal{Z}_{\geq}}(u)=\arg\min_{z^{\prime}\in\mathcal{Z}_{\geq}}\|z^{\prime}-u\|_{2}$.
With these notations, Extragradient RM^+ (ExRM^+) and Smooth PRM^+ (SPRM^+) are defined in Algorithm [4](#alg4) and in Algorithm [5](#alg5).

Figure: Algorithm 4 Extragradient RM^+ (ExRM^+)

ExRM^+ is connected to the Extragradient (EG) algorithm (Korpelevich, ) and SPRM^+ is connected to the Optimistic Gradient algorithm (Popov, ; Rakhlin & Sridharan, ) (see [Section 4](#S4) and [Section 5](#S5)
for details). Farina et al. () show that ExRM^+ and SPRM^+ enjoy fast $O(\frac{1}{T})$ ergodic convergence for solving matrix games.

## 3 Non-convergence of RM + , alternating RM + , and PRM +

In this section, we show empirically that several existing variants of RM^+ may not converge in iterates. Specifically, we numerically investigate four algorithms—RM^+, alternating RM^+, PRM^+, and alternating PRM^+—on a simple $3\times 3$ game matrix $A=[[3,0,-3],[0,3,-4],[0,0,1]]$ that has the unique Nash equilibrium $(x^{\star},y^{\star})=([\frac{1}{12},\frac{1}{12},\frac{5}{6}],[\frac{1}{3},\frac{5}{12},\frac{1}{4}])$. The same instance was also used in (Farina et al., ) to illustrate the instability of PRM^+ and slow ergodic convergence of RM^+ and PRM^+. The results are shown in [Figure 1](#S3.F1).
We observe that for RM^+, alternating RM^+, and PRM^+, the duality gap remains on the order of $10^{-1}$ even after $10^{5}$ iterations. Our empirical findings are in line with Theorem 3 of Lee et al. (), who pointed out that RM^+ diverges on the rock-paper-scissors game. In contrast, alternating PRM^+ enjoys good last-iterate convergence properties on this matrix game instance. Overall, our empirical results suggest that RM^+, alternating RM^+, and PRM^+ all fail to converge in iterates, *even when the game has a unique Nash equilibrium*, a more regular and benign setting than the general case.

Figure: Figure 1: Duality gap of the current iterates generated by RM^+, RM^+ with alternation, Predictive RM^+ (PRM^+), and Predictive RM^+ with alternation on the zero-sum game with payoff matrix $A=[[3,0,-3],[0,3,-4],[0,0,1]]$.

We complement our empirical non-convergence results by showing that RM^+ has asymptotic convergence under the restrictive assumption that the game has a *strict* Nash equilibrium. To our knowledge, this is the first positive last-iterate convergence result related to RM^+. In a strict Nash equilibrium $(x^{\star},y^{\star})$, $x^{\star}$ is the *unique* best-response to $y^{\star}$ and vice versa. It follows from this definition that the equilibrium is unique and that $x^{\star},y^{\star}$ are pure strategies. As an example, the game matrix $A=[[2,1],[3,4]]$ has a strict Nash equilibrium $x^{\star}=[1,0]$ and $y^{\star}=[1,0]$.

###### Theorem 1 (Convergence of RM + to Strict NE) .

If a matrix game has a *strict Nash equilibrium* $(x^{\star},y^{\star})$, RM^+ ([Algorithm 1](#alg1)) converges in last-iterate, that is, $\lim_{t\rightarrow\infty}\{(x^{t},y^{t})\}=(x^{\star},y^{\star})$.

We remark that the assumption of strict NE in Theorem [1](#Thmtheorem1) cannot be weakened to the assumption of a unique, non-strict Nash equilibrium, as our empirical counterexample shows.
Despite the isolated positive result given in Theorem [1](#Thmtheorem1) (under a very strong assumption that we do not expect to hold in practice), the negative empirical results encountered in this section paint a bleak picture of the last-iterate convergence of unmodified regret-matching algorithms. This sets the stage for the rest of the paper, where we will show unconditional last-iterate convergence of variants of RM^+.

###### Theorem 1 (Convergence of RM + to Strict NE) .

## 4 Convergence properties of ExRM +

In this section, we prove that ExRM^+ exhibits favorable last-iterate convergence results. The section is organized as follows. In Section [4.1](#S4.SS1), we prove asymptotic last-iterate convergence of ExRM^+. Then, in Section [4.2](#S4.SS2), we provide a concrete rate of $O(1/\sqrt{T})$ for the best iterate, based on which we finally show a linear last-iterate convergence rate using a restarting mechanism in Section [4.3](#S4.SS3). All omitted proofs for this section can be found in Appendix [C](#A3).

### 4.1 Asymptotic last-iterate convergence of ExRM +

ExRM^+ ([Algorithm 4](#alg4)) is equivalent to the Extragradient (EG) algorithm of Korpelevich () for solving a *variational inequality* $VI(\mathcal{Z}_{\geq},F)$.
For a closed convex set $\mathcal{S}\subseteq\mathbbm{R}^{n}$
and an operator $G:\mathcal{S}\rightarrow\mathbbm{R}^{n}$, the variational inequality problem $VI(\mathcal{S},G)$ is to find $z\in\mathcal{S}$, such that ${\mathchoice{\left\langle G(z),z-z^{\prime}\right\rangle}{\langle G(z),z-z^{\prime}\rangle}{\langle G(z),z-z^{\prime}\rangle}{\langle G(z),z-z^{\prime}\rangle}}\leq 0$ for all $z^{\prime}\in\mathcal{S}$. We denote $SOL(\mathcal{S},G)$ the solution set of $VI(\mathcal{S},G)$.
EG has been extensively studied in the literature, and its last-iterate convergence properties are known in several settings, including:

- 1.
If $G$ is Lipschitz and *pseudo monotone with respect to the solution set $SOL(\mathcal{S},G)$*, i.e., for any $z^{\star}\in SOL(\mathcal{S},G)$, it holds that ${\mathchoice{\left\langle G(z),z-z^{\star}\right\rangle}{\langle G(z),z-z^{\star}\rangle}{\langle G(z),z-z^{\star}\rangle}{\langle G(z),z-z^{\star}\rangle}}\geq 0$ for all $z\in\mathcal{S}$, then iterates produced by EG converge to a solution of $VI(\mathcal{S},G)$ (Facchinei & Pang, , Ch. 12);
- 2.
If $G$ is Lipschitz and *monotone*, i.e., ${\mathchoice{\left\langle G(z)-G(z^{\prime}),z-z^{\prime}\right\rangle}{\langle G(z)-G(z^{\prime}),z-z^{\prime}\rangle}{\langle G(z)-G(z^{\prime}),z-z^{\prime}\rangle}{\langle G(z)-G(z^{\prime}),z-z^{\prime}\rangle}}\geq 0$ for all $z,z^{\prime}\in\mathcal{S}$, then iterates $\{z^{t}\}$ produced by EG have $O(\frac{1}{\sqrt{t}})$ last-iterate convergence such that ${\mathchoice{\left\langle G(z^{t}),z^{t}-z\right\rangle}{\langle G(z^{t}),z^{t}-z\rangle}{\langle G(z^{t}),z^{t}-z\rangle}{\langle G(z^{t}),z^{t}-z\rangle}}\leq O(\frac{1}{\sqrt{t}})$ for all $z\in\mathcal{S}$ (Golowich et al., ; Gorbunov et al., ; Cai et al., ).

Unfortunately, these results do not apply directly to our case: although the operator $F$ (as defined in [Equation 2](#S2.E2)) is $L_{F}$-Lipschitz-continuous over $\mathcal{Z}_{\geq}$, it is not monotone or even pseudo monotone with respect to $SOL(\mathcal{Z}_{\geq},F)$. However, we observe that $F$ satisfies the *Minty condition*: there exists a solution $z^{\star}\in SOL(\mathcal{Z}_{\geq},F)$ such that ${\mathchoice{\left\langle F(z),z-z^{\star}\right\rangle}{\langle F(z),z-z^{\star}\rangle}{\langle F(z),z-z^{\star}\rangle}{\langle F(z),z-z^{\star}\rangle}}\geq 0$ for all $z\in\mathcal{Z}_{\geq}$. The Minty condition is weaker than pseudo monotonicity with respect to $SOL(\mathcal{Z}_{\geq},F)$ (note the different quantifiers $\forall$ and $\exists$ for $z^{\star}$ in the two conditions).

###### Fact 1 ( $F$ satisfies the Minty condition) .

For any Nash equilibrium $z^{\star}\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ of the matrix game $A$, ${\mathchoice{\left\langle F(z),z-az^{\star}\right\rangle}{\langle F(z),z-az^{\star}\rangle}{\langle F(z),z-az^{\star}\rangle}{\langle F(z),z-az^{\star}\rangle}}\geq 0$ holds for all $a\geq 1$.

###### Proof.

Let $z^{\star}=(x^{\star},y^{\star})\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ be a Nash equilibrium of the matrix game. For any $z=(Rx,Qy)\in\mathcal{Z}_{\geq}$, we have ${\mathchoice{\left\langle F(z),z-az^{\star}\right\rangle}{\langle F(z),z-az^{\star}\rangle}{\langle F(z),z-az^{\star}\rangle}{\langle F(z),z-az^{\star}\rangle}}=-{\mathchoice{\left\langle F(z),az^{\star}\right\rangle}{\langle F(z),az^{\star}\rangle}{\langle F(z),az^{\star}\rangle}{\langle F(z),az^{\star}\rangle}}=a(x^{\top}Ay^{\star}-(x^{\star})^{\top}Ay)\geq 0,$ using ${\mathchoice{\left\langle F(z),z\right\rangle}{\langle F(z),z\rangle}{\langle F(z),z\rangle}{\langle F(z),z\rangle}}=0$ and the definition of Nash equilibrium.
∎

We are not aware of last-iterate convergence results for variational inequalities under only the Minty condition, but
with this condition and Lipschitzness, a standard analysis shows that the distance between any $z^{\star}$ that satisfies the Minty condition and the sequence $\{z^{t}\}$ produced by ExRM^+ is decreasing. This serves as an important cornerstone for the rest of our analysis.

###### Lemma 1 (Adapted from Lemma 12.1.10 in (Facchinei & Pang, 2003 ) ) .

Let $z^{\star}\in\mathcal{Z}_{\geq}$ be a point such that ${\mathchoice{\left\langle F(z),z-z^{\star}\right\rangle}{\langle F(z),z-z^{\star}\rangle}{\langle F(z),z-z^{\star}\rangle}{\langle F(z),z-z^{\star}\rangle}}\geq 0$ for all $z\in\mathcal{Z}_{\geq}$. Let $\{z^{t}\}$ be the sequence produced by ExRM^+. Then for every iteration $t\geq 0$ it holds that
${\mathchoice{\left\|z^{t+1}-z^{\star}\right\|}{\|z^{t+1}-z^{\star}\|}{\|z^{t+1}-z^{\star}\|}{\|z^{t+1}-z^{\star}\|}}^{2}\leq{\mathchoice{\left\|z^{t}-z^{\star}\right\|}{\|z^{t}-z^{\star}\|}{\|z^{t}-z^{\star}\|}{\|z^{t}-z^{\star}\|}}^{2}-(1-\eta^{2}L_{F}^{2}){\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}^{2}.$

By [Lemma 1](#Thmlemma1), the sequence $\{z^{t}\}$ is bounded, so it has at least one limit point $\hat{z}\in\mathcal{Z}_{\geq}$. We next show that every limit point $\hat{z}$ lies in the solution set of $VI(\mathcal{Z}_{\geq},F)$ and induces a Nash equilibrium of the matrix game $A$. Moreover, we have $\lim_{t\rightarrow\infty}{\mathchoice{\left\|z^{t}-z^{t+1}\right\|}{\|z^{t}-z^{t+1}\|}{\|z^{t}-z^{t+1}\|}{\|z^{t}-z^{t+1}\|}}=0$.

###### Lemma 2 .

Let $\{z^{t}\}$ be the iterates produced by ExRM^+. Then $\lim_{t\rightarrow\infty}{\mathchoice{\left\|z^{t}-z^{t+1}\right\|}{\|z^{t}-z^{t+1}\|}{\|z^{t}-z^{t+1}\|}{\|z^{t}-z^{t+1}\|}}=0$ and also:

- 1.
If $\hat{z}$ is a limit point of $\{z^{t}\}$, then $\hat{z}\in SOL(\mathcal{Z}_{\geq},F)$.
- 2.
If $\hat{z}\in SOL(\mathcal{Z}_{\geq},F)$, then $(\hat{x},\hat{y})=g(\hat{z})$ is a Nash equilibrium of the matrix game $A$.

Now we know that the sequence $\{z^{t}\}$
has at least one limit point $\hat{z}\in SOL(\mathcal{Z}_{\geq},F)$. If $\hat{z}$ is the unique limit point, then $\{z^{t}\}$ converges to $\hat{z}$. To show this, we first provide another condition under which $\{z^{t}\}$ converges in the following proposition.

###### Proposition 1 .

If the iterates $\{z^{t}\}$ produced by ExRM^+ have a limit point $\hat{z}$ such that $\hat{z}=az^{\star}$ for $z^{\star}\in\mathcal{Z}$ and $a\geq 1$ (equivalently, colinear with a pair of strategies), then $\{z^{t}\}$ converges to $\hat{z}$.

###### Proof.

Denote by $\{z_{t}\}_{t\in\kappa}$ a subsequence of $\{z^{t}\}$ that converges to $\hat{z}$. By [1](#Thmfact1), the Minty condition holds for $\hat{z}$, so by [Lemma 1](#Thmlemma1), $\{{\mathchoice{\left\|z^{t}-\hat{z}\right\|}{\|z^{t}-\hat{z}\|}{\|z^{t}-\hat{z}\|}{\|z^{t}-\hat{z}\|}}\}$ is monotonically decreasing and therefore converges. Since $\lim_{t\rightarrow\infty}{\mathchoice{\left\|z^{t}-\hat{z}\right\|}{\|z^{t}-\hat{z}\|}{\|z^{t}-\hat{z}\|}{\|z^{t}-\hat{z}\|}}=\lim_{t(\in\kappa)\rightarrow\infty}{\mathchoice{\left\|z^{t}-\hat{z}\right\|}{\|z^{t}-\hat{z}\|}{\|z^{t}-\hat{z}\|}{\|z^{t}-\hat{z}\|}}=0,$ $\{z^{t}\}$ converges to $\hat{z}$.
∎

However, the condition of [Proposition 1](#Thmproposition1) may not hold in general, and we empirically observe in experiments that it is not uncommon for the limit point $\hat{z}=(R\hat{x},Q\hat{y})$ to have $R\neq Q$. To proceed, we will use the observation that the only “bad” case that prevents us from proving convergence of $\{z^{t}\}$ is that $\{z^{t}\}$ has infinitely-many limit points (note that the number of solutions $|SOL(\mathcal{Z}_{\geq},F)|$ is indeed infinite). This is because if $\{z^{t}\}$ has a finite number of limit points, then since $\lim_{t\rightarrow\infty}{\mathchoice{\left\|z^{t+1}-z^{t}\right\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}}=0$ ([Lemma 2](#Thmlemma2)), it must have a unique limit point (see a formal proof in [Proposition 3](#Thmproposition3)).
In the following, to show that it is impossible that $\{z^{t}\}$ has infinitely many limit points, we first prove a lemma showing the structure of limit points of $\{z^{t}\}$.

Figure: Figure 2: Pictorial illustration of [Lemma 3](#Thmlemma3).
Refer to caption: /html/2311.00676/assets/structure_limit_points.pdf

###### Lemma 3 (Structure of Limit Points) .

Let $\{z^{t}\}$ be the iterates produced by ExRM^+ and $z^{\star}\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ be any Nash equilibrium of $A$. If $\hat{z}$ and $\tilde{z}$ are two limit points of $\{z^{t}\}$, then the following holds.

- 1.
${\mathchoice{\left\|az^{\star}-\hat{z}\right\|}{\|az^{\star}-\hat{z}\|}{\|az^{\star}-\hat{z}\|}{\|az^{\star}-\hat{z}\|}}^{2}={\mathchoice{\left\|az^{\star}-\tilde{z}\right\|}{\|az^{\star}-\tilde{z}\|}{\|az^{\star}-\tilde{z}\|}{\|az^{\star}-\tilde{z}\|}}^{2}$ for all $a\geq 1$.
- 2.
${\mathchoice{\left\|\hat{z}\right\|}{\|\hat{z}\|}{\|\hat{z}\|}{\|\hat{z}\|}}^{2}={\mathchoice{\left\|\tilde{z}\right\|}{\|\tilde{z}\|}{\|\tilde{z}\|}{\|\tilde{z}\|}}^{2}$.
- 3.
${\mathchoice{\left\langle z^{\star},\hat{z}-\tilde{z}\right\rangle}{\langle z^{\star},\hat{z}-\tilde{z}\rangle}{\langle z^{\star},\hat{z}-\tilde{z}\rangle}{\langle z^{\star},\hat{z}-\tilde{z}\rangle}}=0$.

See Figure [2](#S4.F2) for an illustration of this lemma.(^4^44Note that we draw $z^{\star}$ in a simplex only as a simplified illustration—technically $z^{\star}$ should be from the Cartesian product of two simplexes instead.)
With such structural understanding of limit points, we are now ready to show that $\{z^{t}\}$ necessarily has a unique limit point.

###### Lemma 4 (Unique limit Point) .

The sequence $\{z^{t}\}$ produced by ExRM^+ has a unique limit point.

###### Fact 1 ( F 𝐹 F satisfies the Minty condition) .

###### Proof.

###### Lemma 1 (Adapted from Lemma 12.1.10 in (Facchinei & Pang, 2003 ) ) .

###### Lemma 2 .

###### Proposition 1 .

###### Proof.

###### Lemma 3 (Structure of Limit Points) .

###### Lemma 4 (Unique limit Point) .

#### Proof Sketch

As discussed above, since $\lim_{t\rightarrow\infty}{\mathchoice{\left\|z^{t+1}-z^{t}\right\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}}=0$, it suffices to prove that $\{z^{t}\}$ has finitely many limit points. Let $\hat{z}=(\widehat{R}\hat{x},\widehat{Q}\hat{y})$ and $\tilde{z}=(\widetilde{R}\tilde{x},\widetilde{Q}\tilde{y})$ be any two distinct limit points of $\{z^{t}\}$ such that $\widehat{R}\neq\widehat{Q}$ and $\widetilde{R}\neq\widetilde{Q}$ (otherwise we can apply [Proposition 1](#Thmproposition1) to prove convergence). By careful case analysis, the structure of limit points ([Lemma 3](#Thmlemma3)), and properties of Nash equilibrium, we prove a key equality: $\widehat{R}+\widetilde{R}=\widehat{Q}+\widetilde{Q}$. Now $\hat{z}$ and $\tilde{z}$ must be the only two limit points: suppose there exists another limit point $z=(Rx,Qy)$ with $R\neq Q$, then at least one of $\widehat{R}+R=\widehat{Q}+Q$ and $\widetilde{R}+R=\widetilde{Q}+Q$ would be violated and lead to a contradiction. Thus $\{z^{t}\}$ has at most two distinct limit points, which, again, when further combined with the fact $\lim_{t\rightarrow\infty}{\mathchoice{\left\|z^{t+1}-z^{t}\right\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}}=0$ implies that it in fact has a unique limit point ([Proposition 3](#Thmproposition3)).

The last-iterate convergence of ExRM^+ now follows directly by [Lemma 2](#Thmlemma2) and [Lemma 4](#Thmlemma4).

###### Theorem 2 (Last-Iterate Convergence of ExRM + ) .

Let $\{z^{t}\}$ be the sequence produced by ExRM^+, then $\{z^{t}\}$ is bounded and converges to $z^{\star}\in\mathcal{Z}_{\geq}$ with $g(z^{\star})=(x^{\star},y^{\star})\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ being a Nash equilibrium of the matrix game $A$.

###### Theorem 2 (Last-Iterate Convergence of ExRM + ) .

### 4.2 Best-Iterate Convergence Rate of ExRM +

To remedy not having a concrete convergence rate in the last result,
we now prove an $O(\frac{1}{\sqrt{T}})$ best-iterate convergence rate of ExRM^+ in this section.
The following key lemma relates the duality gap of a pair of strategies $(x^{t+1},y^{t+1})$ and the distance ${\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}$.

###### Lemma 5 .

Let $\{z^{t}\}$ be iterates produced by ExRM^+ and $(x^{t+1},y^{t+1})=g(z^{t+1})$.
Then $\operatorname{DualityGap}(x^{t+1},y^{t+1})\leq\frac{12{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}}{\eta}$.

Now combining [Lemma 1](#Thmlemma1) and [Lemma 5](#Thmlemma5), we conclude the following best-iterate convergence rate.

###### Theorem 3 .

Let $\{z^{t}\}$ be the sequence produced by ExRM^+ with initial point $z^{0}$.
Then for any Nash equilibrium $z^{\star}$, any $T\geq 1$, there exists $t\leq T$ with $(x^{t},y^{t})=g(z^{t})$ and

$$ $\displaystyle\operatorname{DualityGap}(x^{t},y^{t})\leq\frac{12{\mathchoice{\left\|z^{0}-z^{\star}\right\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}}}{\eta\sqrt{1-\eta^{2}L_{F}^{2}}}\frac{1}{\sqrt{T}}.$ $$

If $\eta=\frac{1}{\sqrt{2}L_{F}}$, then $\operatorname{DualityGap}(x^{t},y^{t})\leq\frac{24L_{F}{\mathchoice{\left\|z^{0}-z^{\star}\right\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}}}{\sqrt{T}}.$

###### Proof.

Fix any Nash equilibrium $z^{\star}$ of the game. From [Lemma 1](#Thmlemma1), we know $\sum_{t=0}^{T-1}{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}^{2}\leq\frac{{\mathchoice{\left\|z^{0}-z^{\star}\right\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}}^{2}}{1-\eta^{2}L_{F}^{2}}.$
This implies that there exists $0\leq t\leq T-1$ such that ${\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}\leq\frac{{\mathchoice{\left\|z^{0}-z^{\star}\right\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}}}{\sqrt{T}\sqrt{1-\eta^{2}L_{F}^{2}}}$. We then get the desired result by applying [Lemma 5](#Thmlemma5).
∎

###### Lemma 5 .

###### Theorem 3 .

###### Proof.

### 4.3 Linear Last-Iterate Convergence for ExRM + with Restarts

In this section, based on the best-iterate convergence result from the last section, we further provide a simple restarting mechanism under which ExRM^+ enjoys linear last-iterate convergence.
To show this, we recall that
zero-sum matrix games satisfy the following *metric subregularity* condition.

###### Proposition 2 (Metric Subregularity (Wei et al., 2021 ) ) .

Let $A\in\mathbbm{R}^{d_{1}\times d_{2}}$ be a matrix game. There exists a constant $c>0$ (only depending on $A$) such that for any $z=(x,y)\in\Delta^{d_{1}}\times\Delta^{d_{2}}$, it holds that $\operatorname{DualityGap}(x,y)\geq c{\mathchoice{\left\|z-\Pi_{\mathcal{Z}^{\star}}[z]\right\|}{\|z-\Pi_{\mathcal{Z}^{\star}}[z]\|}{\|z-\Pi_{\mathcal{Z}^{\star}}[z]\|}{\|z-\Pi_{\mathcal{Z}^{\star}}[z]\|}}$ where $\mathcal{Z}^{\star}$ denotes the set of all Nash equilibria.

Together with the best-iterate convergence rate result from [Theorem 3](#Thmtheorem3) (with $\eta=\frac{1}{\sqrt{2}L_{F}}$), we immediately get that for any $T\geq 1$, there exists $1\leq t\leq T$ such that

$$ ${\mathchoice{\left\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\right\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}}\leq\frac{\operatorname{DualityGap}(x^{t},y^{t})}{c}\leq\frac{24L_{F}}{c\sqrt{T}}\cdot{\mathchoice{\left\|z^{0}-\Pi_{\mathcal{Z}^{\star}}[z^{0}]\right\|}{\|z^{0}-\Pi_{\mathcal{Z}^{\star}}[z^{0}]\|}{\|z^{0}-\Pi_{\mathcal{Z}^{\star}}[z^{0}]\|}{\|z^{0}-\Pi_{\mathcal{Z}^{\star}}[z^{0}]\|}}.$ $$

The above inequality further implies that if $T\geq\frac{48^{2}L_{F}^{2}}{c^{2}}$, then there exists $1\leq t\leq T$ such that

$$ $\displaystyle{\mathchoice{\left\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\right\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}}\leq\frac{1}{2}{\mathchoice{\left\|z^{0}-\Pi_{\mathcal{Z}^{\star}}[z^{0}]\right\|}{\|z^{0}-\Pi_{\mathcal{Z}^{\star}}[z^{0}]\|}{\|z^{0}-\Pi_{\mathcal{Z}^{\star}}[z^{0}]\|}{\|z^{0}-\Pi_{\mathcal{Z}^{\star}}[z^{0}]\|}}.$ $$

Therefore, after at most a constant number of iterations (smaller than $\frac{48^{2}L_{F}^{2}}{c^{2}}$),
the distance of the best-iterate $(x^{t},y^{t})$ to the equilibrium set $\mathcal{Z}^{\star}$ is halved compared to that of the initial point.
If we could somehow identify this best iterate, then we just need to restart the algorithm with this best iterate as the next initial strategy.
Repeating this would then lead to a linear last-iterate convergence.

The issue in the argument above is obviously that we cannot exactly identify the best iterate since ${\mathchoice{\left\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\right\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}}$ is unknown.
However, it turns out that we can use ${\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}$ as a proxy since ${\mathchoice{\left\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\right\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}}\leq\frac{1}{c}\operatorname{DualityGap}(x^{t},y^{t})\leq\frac{12{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}}{c\eta}$ by [Lemma 5](#Thmlemma5).
This motivates the design of our algorithm:
Restarting ExRM+ (RS-ExRM^+ for short; see Algorithm [6](#alg6)), which restarts for the $k$-th time if ${\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}$ is less than $O(\frac{1}{2^{k}})$.
Importantly, RS-ExRM^+ does not require knowing the value of $c$, the constant in the metric subregularity condition, which can be hard to compute.

Figure: Algorithm 6 Restarting ExRM^+ (RS-ExRM^+)

The main result of this section is the following linear convergence rates of RS-ExRM^+.

###### Theorem 4 (Linear Last-Iterate Convergence of RS-ExRM + ) .

Let $\{z^{t}\}$ be the sequence produced by RS-ExRM^+ and let $\rho=\frac{4}{\sqrt{1-\eta^{2}L_{F}^{2}}}$. Then for any $t\geq 1$, the iterate $(x^{t},y^{t})=g(z^{t})$ satisfies

$$ $\displaystyle{\mathchoice{\left\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\right\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}}\leq\frac{\operatorname{DualityGap}(x^{t},y^{t})}{c}\leq\alpha\cdot(1-\beta)^{t}$ $$

where $\alpha=\frac{576}{c^{2}\eta^{2}(1-\eta^{2}L_{F}^{2})}$ and $\beta=\frac{1}{3(1+\alpha)}$.

###### Proposition 2 (Metric Subregularity (Wei et al., 2021 ) ) .

###### Theorem 4 (Linear Last-Iterate Convergence of RS-ExRM + ) .

#### Proof sketch

Let us denote by $t_{k}$ the iteration at which the $k$-th restart happens. According to the restart condition and [Lemma 5](#Thmlemma5), we know that at iteration $t_{k}$, the duality gap of $(x^{t_{k}},y^{t_{k}})$ and its distance to $\mathcal{Z}^{\star}$ is at most $O(\frac{1}{2^{k}})$. For iterate $t\in[t_{k},t_{k+1}]$ at which the algorithm does not restart, we can use [Theorem 3](#Thmtheorem3) to show that its performance is not much worse than that of $(x^{t_{k}},y^{t_{k}})$. Then we prove $t_{k+1}-t_{k}$ is upper bounded by a constant for every $k$, which leads to a linear last-iterate convergence rate for all iterations $t\geq 1$.

## 5 Last-Iterate Convergence of Smooth Predictive RM+

In this section we study another RM^+ variant, SPRM^+ ([Algorithm 5](#alg5)). We present convergence results very similar to those in the last section for ExRM^+.
Given the similarity and for the sake of conciseness, we only state the main results here, with all details and proofs deferred to Appendix [D](#A4).

###### Theorem 5 (Asymptotic Last-Iterate Convergence of SPRM + ) .

Let $\{w^{t}\}$ and $\{z^{t}\}$ be the sequences produced by SPRM^+, then $\{w^{t}\}$ and $\{z^{t}\}$ are bounded and both converge to $z^{\star}\in\mathcal{Z}_{\geq}$ with $g(z^{\star})=(x^{\star},y^{\star})\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ being a Nash equilibrium of the matrix game $A$.

###### Theorem 6 (Best-Iterate Convergence Rate of SPRM + ) .

Let $\{w^{t}\}$ and $\{z^{t}\}$ be the sequences produced by SPRM^+. For any Nash equilibrium $z^{\star}$ of the game, any $T\geq 1$, there exists $1\leq t\leq T$ such that the iterate $g(w^{t})\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ satisfies

$$ $\displaystyle\operatorname{DualityGap}(g(w^{t}))\leq\frac{10{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}}{\eta}\frac{1}{\sqrt{T}}.$ $$

Moreover, for any Nash equilibrium $z^{\star}$ of the game, any $T\geq 1$, there exists $0\leq t\leq T$ such that the iterate $g(z^{t})\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ satisfies

$$ $\displaystyle\operatorname{DualityGap}(g(z^{t}))\leq\frac{18{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}}{\eta}\frac{1}{\sqrt{T}}.$ $$

We apply the same idea of restarting to SPRM^+ to design a new algorithm called Restarting SPRM^+(RS-SPRM^+; see [Algorithm 7](#alg7)) that has provable linear last-iterate convergence.

###### Theorem 7 (Linear Last-Iterate Convergence of RS-SPRM + ) .

Let $\{w^{t}\}$ and $\{z^{t}\}$ be the sequences produced by RS-SPRM^+. Define $\alpha=\frac{400}{c^{2}\eta^{2}}$ and $\beta=\frac{1}{3(1+\alpha)}$. Then for any $t\geq 1$, the iterate $g(w^{t})\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ satisfies

$$ $\displaystyle{\mathchoice{\left\|g(w^{t})-\Pi_{\mathcal{Z}^{*}}[g(w^{t})]\right\|}{\|g(w^{t})-\Pi_{\mathcal{Z}^{*}}[g(w^{t})]\|}{\|g(w^{t})-\Pi_{\mathcal{Z}^{*}}[g(w^{t})]\|}{\|g(w^{t})-\Pi_{\mathcal{Z}^{*}}[g(w^{t})]\|}}\leq\frac{\operatorname{DualityGap}(g(w^{t}))}{c}\leq\alpha\cdot(1-\beta)^{t}.$ $$

Moreover, the iterate $g(z^{t})\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ satisfies

$$ ${\mathchoice{\left\|g(z^{t})-\Pi_{\mathcal{Z}^{*}}[g(z^{t})]\right\|}{\|g(z^{t})-\Pi_{\mathcal{Z}^{*}}[g(z^{t})]\|}{\|g(z^{t})-\Pi_{\mathcal{Z}^{*}}[g(z^{t})]\|}{\|g(z^{t})-\Pi_{\mathcal{Z}^{*}}[g(z^{t})]\|}}\leq\frac{\operatorname{DualityGap}(g(z^{t}))}{c}\leq 2\alpha\cdot(1-\beta)^{t}.$ $$

###### Theorem 5 (Asymptotic Last-Iterate Convergence of SPRM + ) .

###### Theorem 6 (Best-Iterate Convergence Rate of SPRM + ) .

###### Theorem 7 (Linear Last-Iterate Convergence of RS-SPRM + ) .

## 6 Numerical experiments

Next, we numerically evaluate the last-iterate performance of each algorithm studied in this paper.
We use the $3\times 3$ matrix game instance from Section [3](#S3), the normal-form representations of Kuhn poker and Goofspiel, as well as $25$ random matrix games of size $(d_{1},d_{2})=(10,15)$ (for which we average the duality gaps across the instances and show the associated confidence intervals). More details on the games can be found in Appendix [E](#A5). We set $\eta=0.1$ for all algorithms with a stepsize and we initialize all algorithms at $\left((1/d_{1})\bm{1}_{d_{1}},(1/d_{2})\bm{1}_{d_{2}}\right)$. In every iteration, we plot the duality gap of $(x^{t},y^{t})$ for RM^+, PRM^+, and alternating PRM^+; the duality gap of $g(z^{t})$ for ExRM^+ and RS-ExRM^+; the duality gap of $g(w^{t})$ for SPRM^+ and RS-SPRM^+.
The results are shown in Figure [3](#S6.F3).
For the $3\times 3$ matrix game, we see that alternating PRM^+, ExRM^+, and SPRM^+ achieve machine precision after $10^{3}$ iterations (while others stay around $10^{-1}$ as discussed earlier).
On Kuhn poker, PRM^+ and alternating PRM^+ have faster convergence before $10^{3}$ iterations, and perform on par with ExRM^+ and SPRM^+ after that.
On Goofspiel, Alternating PRM^+ is again the best algorithm, although all algorithms (except RM^+) have comparable performance after $10^{5}$ iterations.
Finally, on random instances, the last iterate performance of ExRM^+ and SPRM^+ vastly outperform RM^+, PRM^+, and alternating RM^+, but we note that alternating PRM^+ seems to outperform all other algorithms.
Overall, these results are consistent with our theoretical findings of ExRM^+ and SPRM^+. That said, understanding the superiority of alternating PRM^+ (an algorithm that we do not analyze in this work and for which neither ergodic nor last-iterate convergence guarantees are known) remains open. We also numerically investigate the impact of restarting for RS-ExRM^+ and RS-SPRM^+. For the sake of space we provide our analysis in Appendix [E](#A5), where we note that restarting does not significantly change the empirical convergence of ExRM^+ and SPRM^+, which is coherent with the fact that ExRM^+ and SPRM^+ (without restarting) already exhibit fast last-iterate convergence.

Figure: Figure 3: Empirical performances of several algorithms on the $3\times 3$ matrix game (left plot), Kuhn poker and Goofspiel (center plots), and random instances (right plot).

## 7 Conclusions

In this paper, we investigate the last-iterate convergence properties of regret-matching algorithms, a class of extremely popular methods for equilibrium computation in games. Despite these methods enjoying strong *average* performance in practice, we show that unfortunately many practically-used variants might not converge to equilibrium in iterates. Motivated by these findings, we set out to investigate those variations with provable last-iterate convergence, establishing a suite of new results by using techniques from the literature on variational inequalities. For a restarted variant of these algorithms, we were able to prove, for the first time for regret matching algorithms, *linear-rate* convergence in iterates. Finally, we point out that several questions remain open, including giving concrete rates for the (non-restarted) ExRM^+, SPRM^+ and alternating PRM^+ algorithms.

## Appendix A Useful Propositions

###### Proposition 3 .

Let $\mathcal{S}\subseteq\mathbbm{R}^{n}$ be a compact convex set and $\{z^{t}\in\mathcal{S}\}$ be a sequence of points in $\mathcal{S}$ such that $\lim_{t\rightarrow\infty}{\mathchoice{\left\|z^{t}-z^{t+1}\right\|}{\|z^{t}-z^{t+1}\|}{\|z^{t}-z^{t+1}\|}{\|z^{t}-z^{t+1}\|}}=0$, then one of the following is true.

- 1.
The sequence $\{z^{t}\}$ has infinite limit points.
- 2.
The sequence $\{z^{t}\}$ has a unique limit point.

###### Proof.

We denote a closed Euclidean ball in $\mathbbm{R}^{n}$ as $B(x,\delta):=\{x^{\prime}\in\mathbbm{R}^{n}:{\mathchoice{\left\|x^{\prime}-x\right\|}{\|x^{\prime}-x\|}{\|x^{\prime}-x\|}{\|x^{\prime}-x\|}}\leq\delta\}$. For the sake of contradiction, assume that neither of the two conditions are satisfied. This implies that the sequence $\{z^{t}\}$ has a finite number ($\geq 2$) of limit points. Then there exists $\epsilon>0$ and two distinct limit points $\hat{z}_{1}$ and $\hat{z}_{2}$ such that

- 1.
${\mathchoice{\left\|\hat{z}_{1}-\hat{z}_{2}\right\|}{\|\hat{z}_{1}-\hat{z}_{2}\|}{\|\hat{z}_{1}-\hat{z}_{2}\|}{\|\hat{z}_{1}-\hat{z}_{2}\|}}\geq\epsilon$;
- 2.
$\hat{z}_{1}$ is the only limit point of $\{z^{t}\}$ within $B(\hat{z}_{1},\epsilon/2)\cap\mathcal{S}$;
- 3.
$\hat{z}_{2}$ is the only limit point of $\{z^{t}\}$ within $B(\hat{z}_{2},\epsilon/2)\cap\mathcal{S}$.

Given that $\lim_{t\rightarrow\infty}{\mathchoice{\left\|z^{t}-z^{t+1}\right\|}{\|z^{t}-z^{t+1}\|}{\|z^{t}-z^{t+1}\|}{\|z^{t}-z^{t+1}\|}}=0$, there exists $T>0$ such that for any $t>T$, ${\mathchoice{\left\|z^{t}-z^{t+1}\right\|}{\|z^{t}-z^{t+1}\|}{\|z^{t}-z^{t+1}\|}{\|z^{t}-z^{t+1}\|}}\leq\frac{\epsilon}{4}$. Now since $\hat{z}_{1}$ and $\hat{z}_{2}$ are limit points of $\{z^{t}\}$, there exists sub-sequences $\{z^{t_{k}}\}$ and $\{z^{t_{j}}\}$ that converges to $\hat{z}_{1}$ and $\hat{z}_{2}$, respectively. This means that there are infinite points from $\{z^{t_{k}}\}$ within $B(\hat{z}_{1},\epsilon/4)\cap\mathcal{S}$ and infinite points from $\{z^{t_{j}}\}$ within $B(\hat{z}_{2},\epsilon/4)\cap\mathcal{S}$. However, for $t>T$, there must also be infinite points from $\{z^{t}\}$ within the region $(B(\hat{z}_{1},\epsilon/2)-B(\hat{z}_{1},\epsilon/4))\cap\mathcal{S}$. This implies there exists another limit point within $B(\hat{z}_{1},\epsilon/2)\cap\mathcal{S}$ and contradicts the assertion that $\hat{z}_{1}$ is the only limit point within $B(\hat{z}_{1},\epsilon/2)\cap\mathcal{S}$.
∎

###### Proposition 3 .

###### Proof.

## Appendix B Proof of Theorem 1

###### Proof of Theorem 1 .

We will use an equivalent update rule of RM^+ ([Algorithm 1](#alg1)) proposed by Farina et al. ():
for all $t\geq 0$, $z^{t+1}=\Pi_{\mathbbm{R}^{d_{1}+d_{2}}_{\geq 0}}{\mathchoice{\left[z^{t}-\eta F(z^{t})\right]}{[z^{t}-\eta F(z^{t})]}{[z^{t}-\eta F(z^{t})]}{[z^{t}-\eta F(z^{t})]}}$ where we use $z^{t}$ to denote $(R^{t}_{x},R^{t}_{y})$ and $F$ as defined in ([2](#S2.E2)). The step size $\eta>0$ only scales the $z^{t}$ vector and produces the same strategies $\{(x^{t},y^{t})\in\Delta^{d_{1}}\times\Delta^{d_{2}}\}$ as [Algorithm 1](#alg1). In the proof, we also use the following property of the operator $F$.

###### Claim 1 (Adapted from Lemma 5.7 in (Farina et al., 2023 ) ) .

For a matrix game $A\in\mathbbm{R}^{d_{1}\times d_{2}}$, let $L_{1}={\mathchoice{\left\|A\right\|}{\|A\|}{\|A\|}{\|A\|}}_{op}\sqrt{6\max\{d_{1},d_{2}\}}$ with ${\mathchoice{\left\|A\right\|}{\|A\|}{\|A\|}{\|A\|}}_{op}:=\sup\{{\mathchoice{\left\|Av\right\|}{\|Av\|}{\|Av\|}{\|Av\|}}_{2}/{\mathchoice{\left\|v\right\|}{\|v\|}{\|v\|}{\|v\|}}_{2}:v\in\mathbbm{R}^{d_{2}},v\neq\bm{0}\}$. Then for any $z=(x,y)\in\mathbbm{R}^{d_{1}+d_{2}}_{\geq 0}$ and $z^{\prime}=(x^{\prime},y^{\prime})\in\mathbbm{R}^{d_{1}+d_{2}}_{\geq 0}$ it holds that ${\mathchoice{\left\|F(z)-F(z^{\prime})\right\|}{\|F(z)-F(z^{\prime})\|}{\|F(z)-F(z^{\prime})\|}{\|F(z)-F(z^{\prime})\|}}\leq L_{1}{\mathchoice{\left\|(x,y)-(x^{\prime},y^{\prime})\right\|}{\|(x,y)-(x^{\prime},y^{\prime})\|}{\|(x,y)-(x^{\prime},y^{\prime})\|}{\|(x,y)-(x^{\prime},y^{\prime})\|}}$.

For any $t\geq 1$, since $z^{t+1}=\Pi_{\mathbbm{R}^{d_{1}+d_{2}}_{\geq 0}}{\mathchoice{\left[z^{t}-\eta F(z^{t})\right]}{[z^{t}-\eta F(z^{t})]}{[z^{t}-\eta F(z^{t})]}{[z^{t}-\eta F(z^{t})]}}$, we have for any $z\in\mathbbm{R}^{d_{1}+d_{2}}_{\geq 0}$

$$ $\displaystyle{\mathchoice{\left\langle z^{t}-\eta F(z^{t})-z^{t+1},z-z^{t+1}\right\rangle}{\langle z^{t}-\eta F(z^{t})-z^{t+1},z-z^{t+1}\rangle}{\langle z^{t}-\eta F(z^{t})-z^{t+1},z-z^{t+1}\rangle}{\langle z^{t}-\eta F(z^{t})-z^{t+1},z-z^{t+1}\rangle}}\leq 0.$ $\displaystyle\Rightarrow$ $\displaystyle{\mathchoice{\left\langle z^{t}-z^{t+1},z-z^{t}\right\rangle}{\langle z^{t}-z^{t+1},z-z^{t}\rangle}{\langle z^{t}-z^{t+1},z-z^{t}\rangle}{\langle z^{t}-z^{t+1},z-z^{t}\rangle}}\leq-{\mathchoice{\left\langle z^{t}-z^{t+1},z^{t}-z^{t+1}\right\rangle}{\langle z^{t}-z^{t+1},z^{t}-z^{t+1}\rangle}{\langle z^{t}-z^{t+1},z^{t}-z^{t+1}\rangle}{\langle z^{t}-z^{t+1},z^{t}-z^{t+1}\rangle}}+{\mathchoice{\left\langle\eta F(z^{t}),z-z^{t+1}\right\rangle}{\langle\eta F(z^{t}),z-z^{t+1}\rangle}{\langle\eta F(z^{t}),z-z^{t+1}\rangle}{\langle\eta F(z^{t}),z-z^{t+1}\rangle}}.$ (3) $$

By three-point identity, we have

$$ $\displaystyle{\mathchoice{\left\|z^{t+1}-z\right\|}{\|z^{t+1}-z\|}{\|z^{t+1}-z\|}{\|z^{t+1}-z\|}}^{2}$ $\displaystyle={\mathchoice{\left\|z^{t}-z\right\|}{\|z^{t}-z\|}{\|z^{t}-z\|}{\|z^{t}-z\|}}^{2}+{\mathchoice{\left\|z^{t+1}-z^{t}\right\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}}^{2}+2{\mathchoice{\left\langle z^{t}-z^{t+1},z-z^{t}\right\rangle}{\langle z^{t}-z^{t+1},z-z^{t}\rangle}{\langle z^{t}-z^{t+1},z-z^{t}\rangle}{\langle z^{t}-z^{t+1},z-z^{t}\rangle}}$ $\displaystyle\leq{\mathchoice{\left\|z^{t}-z\right\|}{\|z^{t}-z\|}{\|z^{t}-z\|}{\|z^{t}-z\|}}^{2}-{\mathchoice{\left\|z^{t+1}-z^{t}\right\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}}^{2}+2{\mathchoice{\left\langle\eta F(z^{t}),z-z^{t+1}\right\rangle}{\langle\eta F(z^{t}),z-z^{t+1}\rangle}{\langle\eta F(z^{t}),z-z^{t+1}\rangle}{\langle\eta F(z^{t}),z-z^{t+1}\rangle}}.$ (by ( 3 )) $$

We define $k^{t}:=\operatorname*{argmin}_{k\geq 1}{\mathchoice{\left\|z^{t}-kz^{\star}\right\|}{\|z^{t}-kz^{\star}\|}{\|z^{t}-kz^{\star}\|}{\|z^{t}-kz^{\star}\|}}$. With $z=k^{t}z^{\star}$, the above inequality is equivalent to

$$ $\displaystyle{\mathchoice{\left\|z^{t+1}-k^{t}z^{\star}\right\|}{\|z^{t+1}-k^{t}z^{\star}\|}{\|z^{t+1}-k^{t}z^{\star}\|}{\|z^{t+1}-k^{t}z^{\star}\|}}^{2}+2\eta{\mathchoice{\left\langle F(z^{\star}),z^{t+1}\right\rangle}{\langle F(z^{\star}),z^{t+1}\rangle}{\langle F(z^{\star}),z^{t+1}\rangle}{\langle F(z^{\star}),z^{t+1}\rangle}}$ $\displaystyle\leq{\mathchoice{\left\|z^{t}-k^{t}z^{\star}\right\|}{\|z^{t}-k^{t}z^{\star}\|}{\|z^{t}-k^{t}z^{\star}\|}{\|z^{t}-k^{t}z^{\star}\|}}^{2}+2\eta{\mathchoice{\left\langle F(z^{\star}),z^{t}\right\rangle}{\langle F(z^{\star}),z^{t}\rangle}{\langle F(z^{\star}),z^{t}\rangle}{\langle F(z^{\star}),z^{t}\rangle}}-{\mathchoice{\left\|z^{t+1}-z^{t}\right\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}}^{2}+2\eta{\mathchoice{\left\langle F(z^{t})-F(z^{\star}),z^{t}-z^{t+1}\right\rangle}{\langle F(z^{t})-F(z^{\star}),z^{t}-z^{t+1}\rangle}{\langle F(z^{t})-F(z^{\star}),z^{t}-z^{t+1}\rangle}{\langle F(z^{t})-F(z^{\star}),z^{t}-z^{t+1}\rangle}}$ $\displaystyle\quad+2\eta{\mathchoice{\left\langle F(z^{t}),k^{t}z^{\star}\right\rangle}{\langle F(z^{t}),k^{t}z^{\star}\rangle}{\langle F(z^{t}),k^{t}z^{\star}\rangle}{\langle F(z^{t}),k^{t}z^{\star}\rangle}}$ (We use ${\mathchoice{\left\langle F(z^{t}),z^{t}\right\rangle}{\langle F(z^{t}),z^{t}\rangle}{\langle F(z^{t}),z^{t}\rangle}{\langle F(z^{t}),z^{t}\rangle}}=0$ ) $\displaystyle\leq{\mathchoice{\left\|z^{t}-k^{t}z^{\star}\right\|}{\|z^{t}-k^{t}z^{\star}\|}{\|z^{t}-k^{t}z^{\star}\|}{\|z^{t}-k^{t}z^{\star}\|}}^{2}+2\eta{\mathchoice{\left\langle F(z^{\star}),z^{t}\right\rangle}{\langle F(z^{\star}),z^{t}\rangle}{\langle F(z^{\star}),z^{t}\rangle}{\langle F(z^{\star}),z^{t}\rangle}}+\eta^{2}{\mathchoice{\left\|F(z^{t})-F(z^{\star})\right\|}{\|F(z^{t})-F(z^{\star})\|}{\|F(z^{t})-F(z^{\star})\|}{\|F(z^{t})-F(z^{\star})\|}}^{2}+2\eta{\mathchoice{\left\langle F(z^{t}),k^{t}z^{\star}\right\rangle}{\langle F(z^{t}),k^{t}z^{\star}\rangle}{\langle F(z^{t}),k^{t}z^{\star}\rangle}{\langle F(z^{t}),k^{t}z^{\star}\rangle}}$ ( $-a^{2}+2ab\leq b^{2}$ ) $\displaystyle\leq{\mathchoice{\left\|z^{t}-k^{t}z^{\star}\right\|}{\|z^{t}-k^{t}z^{\star}\|}{\|z^{t}-k^{t}z^{\star}\|}{\|z^{t}-k^{t}z^{\star}\|}}^{2}+2\eta{\mathchoice{\left\langle F(z^{\star}),z^{t}\right\rangle}{\langle F(z^{\star}),z^{t}\rangle}{\langle F(z^{\star}),z^{t}\rangle}{\langle F(z^{\star}),z^{t}\rangle}}+\eta^{2}L_{1}^{2}{\mathchoice{\left\|(x^{t},y^{t})-z^{\star}\right\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}}^{2}+2\eta{\mathchoice{\left\langle F(z^{t}),k^{t}z^{\star}\right\rangle}{\langle F(z^{t}),k^{t}z^{\star}\rangle}{\langle F(z^{t}),k^{t}z^{\star}\rangle}{\langle F(z^{t}),k^{t}z^{\star}\rangle}}.$ $$

Since $z^{\star}=(x^{\star},y^{\star})$ is a strict Nash equilibrium, by [Lemma 6](#Thmlemma6), there exists a constant $c>0$ such that

$$ $\displaystyle 2\eta{\mathchoice{\left\langle F(z^{t}),k^{t}z^{\star}\right\rangle}{\langle F(z^{t}),k^{t}z^{\star}\rangle}{\langle F(z^{t}),k^{t}z^{\star}\rangle}{\langle F(z^{t}),k^{t}z^{\star}\rangle}}$ $\displaystyle=-2\eta k^{t}{\mathchoice{\left((x^{t})^{\top}Ay^{\star}-(x^{\star})^{\top}Ay^{t}\right)}{((x^{t})^{\top}Ay^{\star}-(x^{\star})^{\top}Ay^{t})}{((x^{t})^{\top}Ay^{\star}-(x^{\star})^{\top}Ay^{t})}{((x^{t})^{\top}Ay^{\star}-(x^{\star})^{\top}Ay^{t})}}$ $\displaystyle\leq-2\eta ck^{t}{\mathchoice{\left\|(x^{t},y^{t})-z^{\star}\right\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}}^{2}$ $\displaystyle\leq-2\eta c{\mathchoice{\left\|(x^{t},y^{t})-z^{\star}\right\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}}^{2},$ $$

where in the last inequality, we use $k^{t}\geq 1$ by definition. Thus, combining the above two inequalities gives

$$ $\displaystyle{\mathchoice{\left\|z^{t+1}-k^{t}z^{\star}\right\|}{\|z^{t+1}-k^{t}z^{\star}\|}{\|z^{t+1}-k^{t}z^{\star}\|}{\|z^{t+1}-k^{t}z^{\star}\|}}^{2}+2\eta{\mathchoice{\left\langle F(z^{\star}),z^{t+1}\right\rangle}{\langle F(z^{\star}),z^{t+1}\rangle}{\langle F(z^{\star}),z^{t+1}\rangle}{\langle F(z^{\star}),z^{t+1}\rangle}}\leq{\mathchoice{\left\|z^{t}-k^{t}z^{\star}\right\|}{\|z^{t}-k^{t}z^{\star}\|}{\|z^{t}-k^{t}z^{\star}\|}{\|z^{t}-k^{t}z^{\star}\|}}^{2}+2\eta{\mathchoice{\left\langle F(z^{\star}),z^{t}\right\rangle}{\langle F(z^{\star}),z^{t}\rangle}{\langle F(z^{\star}),z^{t}\rangle}{\langle F(z^{\star}),z^{t}\rangle}}+(\eta^{2}L_{1}^{2}-2\eta c){\mathchoice{\left\|(x^{t},y^{t})-z^{\star}\right\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}}^{2}.$ $$

Using definition of $k^{t+1}$ and choosing $\eta<\frac{c}{L_{1}^{2}}$, we have $2\eta c-\eta^{2}L_{1}^{2}>0$ and

$$ $(2\eta c-\eta^{2}L_{1}^{2}){\mathchoice{\left\|(x^{t},y^{t})-z^{\star}\right\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}}^{2}\leq{\mathchoice{\left\|z^{t}-k^{t}z^{\star}\right\|}{\|z^{t}-k^{t}z^{\star}\|}{\|z^{t}-k^{t}z^{\star}\|}{\|z^{t}-k^{t}z^{\star}\|}}^{2}+2\eta{\mathchoice{\left\langle F(z^{\star}),z^{t}\right\rangle}{\langle F(z^{\star}),z^{t}\rangle}{\langle F(z^{\star}),z^{t}\rangle}{\langle F(z^{\star}),z^{t}\rangle}}-{\mathchoice{\left\|z^{t+1}-k^{t+1}z^{\star}\right\|}{\|z^{t+1}-k^{t+1}z^{\star}\|}{\|z^{t+1}-k^{t+1}z^{\star}\|}{\|z^{t+1}-k^{t+1}z^{\star}\|}}^{2}-2\eta{\mathchoice{\left\langle F(z^{\star}),z^{t+1}\right\rangle}{\langle F(z^{\star}),z^{t+1}\rangle}{\langle F(z^{\star}),z^{t+1}\rangle}{\langle F(z^{\star}),z^{t+1}\rangle}}.$ $$

Telescoping the above inequality for $t\in[1,T]$ gives

$$ $\displaystyle(2\eta c-\eta^{2}L_{1}^{2})\sum_{t=1}^{T}{\mathchoice{\left\|(x^{t},y^{t})-z^{\star}\right\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}}^{2}\leq{\mathchoice{\left\|z^{1}-k^{1}z^{\star}\right\|}{\|z^{1}-k^{1}z^{\star}\|}{\|z^{1}-k^{1}z^{\star}\|}{\|z^{1}-k^{1}z^{\star}\|}}^{2}+2\eta{\mathchoice{\left\langle F(z^{\star}),z^{1}\right\rangle}{\langle F(z^{\star}),z^{1}\rangle}{\langle F(z^{\star}),z^{1}\rangle}{\langle F(z^{\star}),z^{1}\rangle}}<+\infty$ $$

It implies that the sequence $\{(x^{t},y^{t})\}$ converges to $z^{\star}$. Moreover, it also gives a $O(\frac{1}{\sqrt{T}})$ best-iterate convergence rate with respect to ${\mathchoice{\left\|(x^{t},y^{t})-z^{\star}\right\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}{\|(x^{t},y^{t})-z^{\star}\|}}^{2}$.
∎

###### Lemma 6 .

If a matrix game $A$ has a strict Nash equilibrium $(x^{\star},y^{\star})$, then there exists a constant $c>0$ such that for any $(x,y)\in\Delta^{d_{1}}\times\Delta^{d_{2}}$,

$$ $x^{\top}Ay^{\star}-(x^{\star})^{\top}Ay\geq c{\mathchoice{\left\|(x,y)-(x^{\star},y^{\star})\right\|}{\|(x,y)-(x^{\star},y^{\star})\|}{\|(x,y)-(x^{\star},y^{\star})\|}{\|(x,y)-(x^{\star},y^{\star})\|}}^{2}.$ $$

###### Proof.

Since $(x^{\star},y^{\star})$ is strict, it is also the unique and pure Nash equilibrium. we denote the unit vector $e_{i^{\star}}=x^{\star}$ with $i^{\star}\in[d_{1}]$(^5^55Given a positive integer $d$, we denote the set $\{1,2,\dots,d\}$ by $[d]$.) and constant $c_{1}:=\max_{i\neq i^{\star}}e_{i}^{\top}Ay^{\star}-e_{i^{\star}}^{\top}Ay^{\star}>0$. Then, by definition, we have

$$ $\displaystyle x^{\top}Ay^{\star}-(x^{\star})^{\top}Ay^{\star}$ $\displaystyle=\sum_{i\neq i^{\star}}x[i]{\mathchoice{\left(e_{i}^{\top}Ay^{\star}-e_{i^{\star}}Ay^{\star}\right)}{(e_{i}^{\top}Ay^{\star}-e_{i^{\star}}Ay^{\star})}{(e_{i}^{\top}Ay^{\star}-e_{i^{\star}}Ay^{\star})}{(e_{i}^{\top}Ay^{\star}-e_{i^{\star}}Ay^{\star})}}$ $\displaystyle\geq c_{1}\sum_{i\neq i^{\star}}x[i]$ $\displaystyle=\frac{c_{1}}{2}\sum_{i\neq i^{\star}}x[i]+\frac{c_{1}}{2}(1-x[i^{\star}])$ ( $\sum_{i\in[d_{1}]}x[i]=1$ ) $\displaystyle\geq\frac{c_{1}}{2}\sum_{i\neq i^{\star}}x[i]^{2}+\frac{c_{1}}{2}(1-x[i^{\star}])^{2}$ ( $x[i]\in[0,1]$ ) $\displaystyle=\frac{c_{1}}{2}{\mathchoice{\left\|x-x^{\star}\right\|}{\|x-x^{\star}\|}{\|x-x^{\star}\|}{\|x-x^{\star}\|}}^{2}.$ $$

Similarly, denote $e_{j^{\star}}=x^{\star}$ with $j^{\star}\in[d_{2}]$ and constant $c_{2}=(x^{\star})^{\top}Ay^{\star}-\max_{j\neq j^{\star}}(x^{\star})^{\top}Ae_{j}$, we get $(x^{\star})^{\top}Ay^{\star}-\max_{j\neq j^{\star}}(x^{\star})^{\top}Ay\geq\frac{c_{2}}{2}{\mathchoice{\left\|y-y^{\star}\right\|}{\|y-y^{\star}\|}{\|y-y^{\star}\|}{\|y-y^{\star}\|}}^{2}$. Combining the two inequalities above and let $c=\frac{1}{2}\min(c_{1},c_{2})$, we have $x^{\top}Ay^{\star}-(x^{\star})^{\top}Ay\geq c{\mathchoice{\left\|(x,y)-(x^{\star},y^{\star})\right\|}{\|(x,y)-(x^{\star},y^{\star})\|}{\|(x,y)-(x^{\star},y^{\star})\|}{\|(x,y)-(x^{\star},y^{\star})\|}}^{2}$ for all $(x,y)$.
∎

###### Proof of Theorem 1 .

###### Claim 1 (Adapted from Lemma 5.7 in (Farina et al., 2023 ) ) .

###### Lemma 6 .

###### Proof.

## Appendix C Proofs for Section 4

### C.1 Proofs for Section 4.1

###### Proof of Lemma 2 .

From [Lemma 1](#Thmlemma1), we know

$$ $(1-\eta^{2}L_{F}^{2})\sum_{t=0}^{\infty}{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}^{2}\leq{\mathchoice{\left\|z^{0}-z^{\star}\right\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}}^{2}.$ $$

Since $1-\eta^{2}L_{F}^{2}>0$, this implies

$$ $\lim_{t\rightarrow\infty}{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}=0.$ $$

Using [Proposition 4](#Thmproposition4), we know that ${\mathchoice{\left\|z^{t+1}-z^{t+\frac{1}{2}}\right\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}}\leq\eta L_{F}{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}$. Thus

$$ $\lim_{t\rightarrow\infty}{\mathchoice{\left\|z^{t+1}-z^{t}\right\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}}\leq\lim_{t\rightarrow\infty}{\mathchoice{\left\|z^{t+1}-z^{t+\frac{1}{2}}\right\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}}+{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}=\lim_{t\rightarrow\infty}(1+\eta L_{F}){\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}=0.$ $$

If $\hat{z}$ is the limit point of the subsequence $\{z^{t}:t\in\kappa\}$, then we must have

$$ $\lim_{t(\in\kappa)\rightarrow\infty}z^{t+\frac{1}{2}}=\hat{z}.$ $$

By the definition of $z^{t+\frac{1}{2}}$ in [Algorithm 4](#alg4) and by the continuity of $F$ and of the projection, we get

$$ $\hat{z}=\lim_{t(\in\kappa)\rightarrow\infty}z^{t+\frac{1}{2}}=\lim_{t(\in\kappa)\rightarrow\infty}\Pi_{\mathcal{Z}_{\geq}}{\mathchoice{\left[z^{t}-\eta F(z^{t})\right]}{[z^{t}-\eta F(z^{t})]}{[z^{t}-\eta F(z^{t})]}{[z^{t}-\eta F(z^{t})]}}=\Pi_{\mathcal{Z}_{\geq}}{\mathchoice{\left[\hat{z}-\eta F(\hat{z})\right]}{[\hat{z}-\eta F(\hat{z})]}{[\hat{z}-\eta F(\hat{z})]}{[\hat{z}-\eta F(\hat{z})]}}.$ $$

This shows that $\hat{z}\in SOL(\mathcal{Z}_{\geq},F)$.
Moreover, by $\hat{z}=\Pi_{\mathcal{Z}_{\geq}}{\mathchoice{\left[\hat{z}-\eta F(\hat{z})\right]}{[\hat{z}-\eta F(\hat{z})]}{[\hat{z}-\eta F(\hat{z})]}{[\hat{z}-\eta F(\hat{z})]}}$ and [Lemma 7](#Thmlemma7), we conclude $(\hat{x},\hat{y})=g(\hat{z})\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ is a Nash equilibrium of $A$.
∎

###### Proof of Lemma 3 .

Let $\{k_{i}\in\mathbb{Z}\}$ be an increasing sequence of indices such that $\{z^{k_{i}}\}$ converges to $\hat{z}$ and $\{l_{i}\in\mathbb{Z}\}$ be an increasing sequence of indices such that $\{z^{l_{i}}\}$ converges to $\tilde{z}$. Let $\sigma:\{k_{i}\}\rightarrow\{l_{i}\}$ be a mapping that always maps $k_{i}$ to a larger index in $\{l_{i}\}$, i.e. $\sigma(k_{i})>k_{i}$. Such a mapping clearly exists. Since [Lemma 1](#Thmlemma1) applies to $az^{\star}$ for any $a\geq 1$, we get

$$ ${\mathchoice{\left\|az^{\star}-\hat{z}\right\|}{\|az^{\star}-\hat{z}\|}{\|az^{\star}-\hat{z}\|}{\|az^{\star}-\hat{z}\|}}^{2}=\lim_{i\rightarrow\infty}{\mathchoice{\left\|az^{\star}-z^{k_{i}}\right\|}{\|az^{\star}-z^{k_{i}}\|}{\|az^{\star}-z^{k_{i}}\|}{\|az^{\star}-z^{k_{i}}\|}}^{2}\geq\lim_{i\rightarrow\infty}{\mathchoice{\left\|az^{\star}-z^{\sigma(k_{i})}\right\|}{\|az^{\star}-z^{\sigma(k_{i})}\|}{\|az^{\star}-z^{\sigma(k_{i})}\|}{\|az^{\star}-z^{\sigma(k_{i})}\|}}^{2}={\mathchoice{\left\|az^{\star}-\tilde{z}\right\|}{\|az^{\star}-\tilde{z}\|}{\|az^{\star}-\tilde{z}\|}{\|az^{\star}-\tilde{z}\|}}^{2}.$ $$

By symmetry, the other direction also holds. Thus ${\mathchoice{\left\|az^{\star}-\hat{z}\right\|}{\|az^{\star}-\hat{z}\|}{\|az^{\star}-\hat{z}\|}{\|az^{\star}-\hat{z}\|}}^{2}={\mathchoice{\left\|az^{\star}-\tilde{z}\right\|}{\|az^{\star}-\tilde{z}\|}{\|az^{\star}-\tilde{z}\|}{\|az^{\star}-\tilde{z}\|}}^{2}$ for all $a\geq 1$.

Expanding ${\mathchoice{\left\|az^{\star}-\hat{z}\right\|}{\|az^{\star}-\hat{z}\|}{\|az^{\star}-\hat{z}\|}{\|az^{\star}-\hat{z}\|}}^{2}={\mathchoice{\left\|az^{\star}-\tilde{z}\right\|}{\|az^{\star}-\tilde{z}\|}{\|az^{\star}-\tilde{z}\|}{\|az^{\star}-\tilde{z}\|}}^{2}$ gives

$$ $\displaystyle{\mathchoice{\left\|\hat{z}\right\|}{\|\hat{z}\|}{\|\hat{z}\|}{\|\hat{z}\|}}^{2}-{\mathchoice{\left\|\tilde{z}\right\|}{\|\tilde{z}\|}{\|\tilde{z}\|}{\|\tilde{z}\|}}^{2}=2a{\mathchoice{\left\langle z^{\star},\hat{z}-\tilde{z}\right\rangle}{\langle z^{\star},\hat{z}-\tilde{z}\rangle}{\langle z^{\star},\hat{z}-\tilde{z}\rangle}{\langle z^{\star},\hat{z}-\tilde{z}\rangle}},\quad\forall a\geq 1.$ $$

It implies that ${\mathchoice{\left\|\hat{z}\right\|}{\|\hat{z}\|}{\|\hat{z}\|}{\|\hat{z}\|}}^{2}={\mathchoice{\left\|\tilde{z}\right\|}{\|\tilde{z}\|}{\|\tilde{z}\|}{\|\tilde{z}\|}}^{2}$ and ${\mathchoice{\left\langle z^{\star},\hat{z}-\tilde{z}\right\rangle}{\langle z^{\star},\hat{z}-\tilde{z}\rangle}{\langle z^{\star},\hat{z}-\tilde{z}\rangle}{\langle z^{\star},\hat{z}-\tilde{z}\rangle}}=0$.
∎

###### Proof of Lemma 4 .

For the sake of contradiction, let $\hat{z}=(\widehat{R}\hat{x},\widehat{Q}\hat{y})$ and $\tilde{z}=(\widetilde{R}\tilde{x},\widetilde{Q}\tilde{y})$ be any two distinct limit points of $\{z^{t}\}$. In the following, we will show a key equality:

###### Claim 2 .

$\widehat{R}+\widetilde{R}=\widehat{Q}+\widetilde{Q}$.

###### Proof of Lemma 2 .

###### Proof of Lemma 3 .

###### Proof of Lemma 4 .

###### Claim 2 .

#### Case 1: z ^ = ( R ^ ​ x ⋆ , Q ^ ​ y ⋆ ) ^ 𝑧 ^ 𝑅 superscript 𝑥 ⋆ ^ 𝑄 superscript 𝑦 ⋆ \hat{z}=(\widehat{R}x^{\star},\widehat{Q}y^{\star}) and z ~ = ( R ~ ​ x ⋆ , Q ~ ​ y ⋆ ) ~ 𝑧 ~ 𝑅 superscript 𝑥 ⋆ ~ 𝑄 superscript 𝑦 ⋆ \tilde{z}=(\widetilde{R}x^{\star},\widetilde{Q}y^{\star}) for a Nash equilibrium z ⋆ = ( x ⋆ , y ⋆ ) superscript 𝑧 ⋆ superscript 𝑥 ⋆ superscript 𝑦 ⋆ z^{\star}=(x^{\star},y^{\star}) .

Part 2 of [Lemma 3](#Thmlemma3) gives

$$ ${\mathchoice{\left\|\hat{z}\right\|}{\|\hat{z}\|}{\|\hat{z}\|}{\|\hat{z}\|}}^{2}={\mathchoice{\left\|\tilde{z}\right\|}{\|\tilde{z}\|}{\|\tilde{z}\|}{\|\tilde{z}\|}}^{2}\Rightarrow(\widehat{R}^{2}-\widetilde{R}^{2}){\mathchoice{\left\|x^{\star}\right\|}{\|x^{\star}\|}{\|x^{\star}\|}{\|x^{\star}\|}}^{2}=(\widetilde{Q}^{2}-\widehat{Q}^{2}){\mathchoice{\left\|y^{\star}\right\|}{\|y^{\star}\|}{\|y^{\star}\|}{\|y^{\star}\|}}^{2}.$ $$

Part 3 of [Lemma 3](#Thmlemma3) gives

$$ ${\mathchoice{\left\langle z^{\star},\hat{z}-\tilde{z}\right\rangle}{\langle z^{\star},\hat{z}-\tilde{z}\rangle}{\langle z^{\star},\hat{z}-\tilde{z}\rangle}{\langle z^{\star},\hat{z}-\tilde{z}\rangle}}=0\Rightarrow(\widehat{R}-\widetilde{R}){\mathchoice{\left\|x^{\star}\right\|}{\|x^{\star}\|}{\|x^{\star}\|}{\|x^{\star}\|}}^{2}=(\widetilde{Q}-\widehat{Q}){\mathchoice{\left\|y^{\star}\right\|}{\|y^{\star}\|}{\|y^{\star}\|}{\|y^{\star}\|}}^{2}.$ $$

Combining the above two inequalities with the fact that $\hat{z}\neq\tilde{z}$, we get

$$ $\widehat{R}+\widetilde{R}=\widehat{Q}+\widetilde{Q}.$ $$

#### Case 2: z ^ = ( R ^ ​ x ^ , Q ^ ​ y ^ ) ^ 𝑧 ^ 𝑅 ^ 𝑥 ^ 𝑄 ^ 𝑦 \hat{z}=(\widehat{R}\hat{x},\widehat{Q}\hat{y}) and z ~ = ( R ~ ​ x ~ , Q ~ ​ y ~ ) ~ 𝑧 ~ 𝑅 ~ 𝑥 ~ 𝑄 ~ 𝑦 \tilde{z}=(\widetilde{R}\tilde{x},\widetilde{Q}\tilde{y}) .

Note that by [Lemma 2](#Thmlemma2), both $(\hat{x},\hat{y})$ and $(\tilde{x},\tilde{y})$ are Nash equilibrium of $A$ and thus $(\hat{x},\tilde{y})$ is also a Nash equilibrium of $A$. Using [Lemma 3](#Thmlemma3), we have the following equalities

- 1.
${\mathchoice{\left\|\hat{z}\right\|}{\|\hat{z}\|}{\|\hat{z}\|}{\|\hat{z}\|}}^{2}={\mathchoice{\left\|\tilde{z}\right\|}{\|\tilde{z}\|}{\|\tilde{z}\|}{\|\tilde{z}\|}}^{2}$ $\Rightarrow$ $\widehat{R}^{2}{\mathchoice{\left\|\hat{x}\right\|}{\|\hat{x}\|}{\|\hat{x}\|}{\|\hat{x}\|}}^{2}-\widetilde{R}^{2}{\mathchoice{\left\|\tilde{x}\right\|}{\|\tilde{x}\|}{\|\tilde{x}\|}{\|\tilde{x}\|}}^{2}=\widetilde{Q}^{2}{\mathchoice{\left\|\tilde{y}\right\|}{\|\tilde{y}\|}{\|\tilde{y}\|}{\|\tilde{y}\|}}^{2}-\widehat{Q}^{2}{\mathchoice{\left\|\hat{y}\right\|}{\|\hat{y}\|}{\|\hat{y}\|}{\|\hat{y}\|}}^{2}$
- 2.
$0={\mathchoice{\left\langle(\hat{x},\hat{y}),\hat{z}-\tilde{z}\right\rangle}{\langle(\hat{x},\hat{y}),\hat{z}-\tilde{z}\rangle}{\langle(\hat{x},\hat{y}),\hat{z}-\tilde{z}\rangle}{\langle(\hat{x},\hat{y}),\hat{z}-\tilde{z}\rangle}}=\widehat{R}{\mathchoice{\left\|\hat{x}\right\|}{\|\hat{x}\|}{\|\hat{x}\|}{\|\hat{x}\|}}^{2}-\widetilde{R}{\mathchoice{\left\langle\hat{x},\tilde{x}\right\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}}+\widehat{Q}{\mathchoice{\left\|\hat{y}\right\|}{\|\hat{y}\|}{\|\hat{y}\|}{\|\hat{y}\|}}^{2}-\widetilde{Q}{\mathchoice{\left\langle\hat{y},\tilde{y}\right\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}}$
- 3.
$0={\mathchoice{\left\langle(\tilde{x},\tilde{y}),\hat{z}-\tilde{z}\right\rangle}{\langle(\tilde{x},\tilde{y}),\hat{z}-\tilde{z}\rangle}{\langle(\tilde{x},\tilde{y}),\hat{z}-\tilde{z}\rangle}{\langle(\tilde{x},\tilde{y}),\hat{z}-\tilde{z}\rangle}}=\widehat{R}{\mathchoice{\left\langle\hat{x},\tilde{x}\right\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}}-\widetilde{R}{\mathchoice{\left\|\tilde{x}\right\|}{\|\tilde{x}\|}{\|\tilde{x}\|}{\|\tilde{x}\|}}^{2}+\widehat{Q}{\mathchoice{\left\langle\hat{y},\tilde{y}\right\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}}-\widetilde{Q}{\mathchoice{\left\|\tilde{y}\right\|}{\|\tilde{y}\|}{\|\tilde{y}\|}{\|\tilde{y}\|}}^{2}$
- 4.
$0={\mathchoice{\left\langle(\hat{x},\tilde{y}),\hat{z}-\tilde{z}\right\rangle}{\langle(\hat{x},\tilde{y}),\hat{z}-\tilde{z}\rangle}{\langle(\hat{x},\tilde{y}),\hat{z}-\tilde{z}\rangle}{\langle(\hat{x},\tilde{y}),\hat{z}-\tilde{z}\rangle}}=\widehat{R}{\mathchoice{\left\|\hat{x}\right\|}{\|\hat{x}\|}{\|\hat{x}\|}{\|\hat{x}\|}}^{2}-\widetilde{R}{\mathchoice{\left\langle\hat{x},\tilde{x}\right\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}}+\widehat{Q}{\mathchoice{\left\langle\hat{y},\tilde{y}\right\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}}-\widetilde{Q}{\mathchoice{\left\|\tilde{y}\right\|}{\|\tilde{y}\|}{\|\tilde{y}\|}{\|\tilde{y}\|}}^{2}$

Combing the last three equalities gives

$$ $c:=\widehat{R}{\mathchoice{\left\|\hat{x}\right\|}{\|\hat{x}\|}{\|\hat{x}\|}{\|\hat{x}\|}}^{2}-\widetilde{R}{\mathchoice{\left\langle\hat{x},\tilde{x}\right\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}}=\widehat{R}{\mathchoice{\left\langle\hat{x},\tilde{x}\right\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}}-\widetilde{R}{\mathchoice{\left\|\tilde{x}\right\|}{\|\tilde{x}\|}{\|\tilde{x}\|}{\|\tilde{x}\|}}^{2},$ $$

and

$$ $-c=\widehat{Q}{\mathchoice{\left\|\hat{y}\right\|}{\|\hat{y}\|}{\|\hat{y}\|}{\|\hat{y}\|}}^{2}-\widetilde{Q}{\mathchoice{\left\langle\hat{y},\tilde{y}\right\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}}=\widehat{Q}{\mathchoice{\left\langle\hat{y},\tilde{y}\right\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}}-\widetilde{Q}{\mathchoice{\left\|\tilde{y}\right\|}{\|\tilde{y}\|}{\|\tilde{y}\|}{\|\tilde{y}\|}}^{2}.$ $$

Further combining the first equality gives

$$ $\displaystyle(\widehat{R}+\widetilde{R})c+(\widehat{Q}+\widetilde{Q})(-c)$ $\displaystyle=\widehat{R}(\widehat{R}{\mathchoice{\left\|\hat{x}\right\|}{\|\hat{x}\|}{\|\hat{x}\|}{\|\hat{x}\|}}^{2}-\widetilde{R}{\mathchoice{\left\langle\hat{x},\tilde{x}\right\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}})+\widetilde{R}(\widehat{R}{\mathchoice{\left\langle\hat{x},\tilde{x}\right\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}}-\widetilde{R}{\mathchoice{\left\|\tilde{x}\right\|}{\|\tilde{x}\|}{\|\tilde{x}\|}{\|\tilde{x}\|}}^{2})+\widehat{Q}(\widehat{Q}{\mathchoice{\left\|\hat{y}\right\|}{\|\hat{y}\|}{\|\hat{y}\|}{\|\hat{y}\|}}^{2}-\widetilde{Q}{\mathchoice{\left\langle\hat{y},\tilde{y}\right\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}})+\widetilde{Q}(\widehat{Q}{\mathchoice{\left\langle\hat{y},\tilde{y}\right\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}}-\widetilde{Q}{\mathchoice{\left\|\tilde{y}\right\|}{\|\tilde{y}\|}{\|\tilde{y}\|}{\|\tilde{y}\|}}^{2})$ $\displaystyle=\widehat{R}^{2}{\mathchoice{\left\|\hat{x}\right\|}{\|\hat{x}\|}{\|\hat{x}\|}{\|\hat{x}\|}}^{2}-\widetilde{R}^{2}{\mathchoice{\left\|\tilde{x}\right\|}{\|\tilde{x}\|}{\|\tilde{x}\|}{\|\tilde{x}\|}}^{2}-\widetilde{Q}^{2}{\mathchoice{\left\|\tilde{y}\right\|}{\|\tilde{y}\|}{\|\tilde{y}\|}{\|\tilde{y}\|}}^{2}+\widehat{Q}^{2}{\mathchoice{\left\|\hat{y}\right\|}{\|\hat{y}\|}{\|\hat{y}\|}{\|\hat{y}\|}}^{2}$ $\displaystyle=0.$ $$

If $c\neq 0$, then we get

$$ $\widehat{R}+\widetilde{R}=\widehat{Q}+\widetilde{Q}.$ $$

If $c=0$, then $\widehat{R}\widetilde{R}{\mathchoice{\left\|\hat{x}\right\|}{\|\hat{x}\|}{\|\hat{x}\|}{\|\hat{x}\|}}^{2}{\mathchoice{\left\|\tilde{x}\right\|}{\|\tilde{x}\|}{\|\tilde{x}\|}{\|\tilde{x}\|}}^{2}=\widehat{R}\widetilde{R}{\mathchoice{\left\langle\hat{x},\tilde{x}\right\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}{\langle\hat{x},\tilde{x}\rangle}}^{2}$ and $\widehat{Q}\widetilde{Q}{\mathchoice{\left\|\hat{y}\right\|}{\|\hat{y}\|}{\|\hat{y}\|}{\|\hat{y}\|}}^{2}{\mathchoice{\left\|\tilde{y}\right\|}{\|\tilde{y}\|}{\|\tilde{y}\|}{\|\tilde{y}\|}}^{2}=\widehat{Q}\widetilde{Q}{\mathchoice{\left\langle\hat{y},\tilde{y}\right\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}{\langle\hat{y},\tilde{y}\rangle}}^{2}$ gives the equality condition of Cauchy-Schwarz inequality and we get $\hat{x}=\tilde{x}$ and $\hat{y}=\tilde{y}$. This reduced to Case 1 where we know $\widehat{R}+\widetilde{R}=\widehat{Q}+\widetilde{Q}$ holds. This completes the proof of the claim.

Note that $\widehat{R}+\widetilde{R}=\widehat{Q}+\widetilde{Q}$ must hold for any two distinct limit points $\hat{z}$ and $\tilde{z}$ of $\{z^{t}\}$. If $\widehat{R}=\widehat{Q}$, then $\hat{z}=\widehat{R}(\hat{x},\hat{y})$ is colinear with a Nash equilibrium $(\hat{x},\hat{y})$ and by [Proposition 1](#Thmproposition1)$,\{z^{t}\}$ converges to $\hat{z}$ and $\hat{z}$ is the unique limit point. If $\widehat{R}\neq\widehat{Q}$, we argue that $\hat{z}$ and $\tilde{z}$ are the only two possible limit points. To see why, let us suppose that there exists another limit point $z=(Rx,Qy)$ distinct from $\hat{z}$ and $\tilde{z}$. If $R=\widehat{R}$, then by $R+\widetilde{R}=Q+\widetilde{Q}$, we know $Q=\widehat{Q}$. However, $R+\widehat{R}=2\widehat{R}\neq 2\widehat{Q}=Q+\widehat{Q}$ gives a contradiction to [2](#Thmclaim2). If $R\neq\widehat{R}$, then combing

$$ $\widehat{R}+R=\widehat{Q}+Q,\quad\widetilde{R}+R=\widetilde{Q}+Q,\quad\widehat{R}+\widetilde{R}=\widehat{Q}+\widetilde{Q}$ $$

gives

$$ $\widehat{R}-\widehat{Q}=Q-R=\widetilde{R}-\widetilde{Q}=\widehat{Q}-\widehat{R}.$ $$

Thus, we have $\widehat{R}=\widehat{Q}$, and it contradicts the assumption that $\widehat{R}\neq\widehat{Q}$. Now we conclude that $\{z^{t}\}$ has at most two distinct limit points which means $\{z^{t}\}$ has a unique limit point given the fact that $\{z^{t}\}$ is bounded and $\lim_{t\rightarrow\infty}{\mathchoice{\left\|z^{t+1}-z^{t}\right\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}}=0$.
∎

### C.2 Proofs for Section 4.2

We will need the following lemma. Recall the normalization operator $g:\mathbbm{R}_{+}^{d_{1}}\times\mathbbm{R}_{+}^{d_{2}}\rightarrow\mathcal{Z}$ such that for $z=(z_{1},z_{2})\in\mathbbm{R}_{+}^{d_{1}}\times\mathbbm{R}_{+}^{d_{2}}$, we have $g(z)=(z_{1}/\|z_{1}\|_{1},z_{2}/\|z_{2}\|_{1})\in\mathcal{Z}$.

###### Lemma 7 .

Let $z\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ and $z_{1},z_{2},z_{3}\in\mathcal{Z}_{\geq}$ such that $z_{3}=\Pi_{\mathcal{Z}_{\geq}}{\mathchoice{\left[z_{1}-\eta F(z_{2})\right]}{[z_{1}-\eta F(z_{2})]}{[z_{1}-\eta F(z_{2})]}{[z_{1}-\eta F(z_{2})]}}$. Denote $(x_{3},y_{3})=g(z_{3})$, then

$$ $\operatorname{DualityGap}(x_{3},y_{3}):=\max_{y\in\Delta^{d_{2}}}x_{3}^{\top}Ay-\min_{x\in\Delta^{d_{1}}}x^{\top}Ay_{3}\leq\frac{({\mathchoice{\left\|z_{1}-z_{3}\right\|}{\|z_{1}-z_{3}\|}{\|z_{1}-z_{3}\|}{\|z_{1}-z_{3}\|}}+\eta L_{F}{\mathchoice{\left\|z_{3}-z_{2}\right\|}{\|z_{3}-z_{2}\|}{\|z_{3}-z_{2}\|}{\|z_{3}-z_{2}\|}})({\mathchoice{\left\|z_{3}-z\right\|}{\|z_{3}-z\|}{\|z_{3}-z\|}{\|z_{3}-z\|}}+2)}{\eta}).$ $$

###### Proof of Lemma 7 .

Let $\hat{x}\in\operatorname*{argmin}_{x}x^{\top}Ay_{3}$ and $\hat{y}\in\operatorname*{argmax}_{y}x_{3}^{\top}Ay$. Then we have

$$ $\displaystyle\max_{y}x_{3}^{\top}Ay-\min_{x}x^{\top}Ay_{3}$ $\displaystyle=x_{3}^{\top}A\hat{y}-\hat{x}^{\top}Ay_{3}$ $\displaystyle=-{\mathchoice{\left\langle F(z_{3}),\hat{z}\right\rangle}{\langle F(z_{3}),\hat{z}\rangle}{\langle F(z_{3}),\hat{z}\rangle}{\langle F(z_{3}),\hat{z}\rangle}}$ $\displaystyle=\frac{1}{\eta}({\mathchoice{\left\langle z_{1}-z_{3}+\eta F(z_{3})-\eta F(z_{2}),z_{3}-\hat{z}\right\rangle}{\langle z_{1}-z_{3}+\eta F(z_{3})-\eta F(z_{2}),z_{3}-\hat{z}\rangle}{\langle z_{1}-z_{3}+\eta F(z_{3})-\eta F(z_{2}),z_{3}-\hat{z}\rangle}{\langle z_{1}-z_{3}+\eta F(z_{3})-\eta F(z_{2}),z_{3}-\hat{z}\rangle}}+{\mathchoice{\left\langle z_{1}-\eta F(z_{2})-z_{3},\hat{z}-z_{3}\right\rangle}{\langle z_{1}-\eta F(z_{2})-z_{3},\hat{z}-z_{3}\rangle}{\langle z_{1}-\eta F(z_{2})-z_{3},\hat{z}-z_{3}\rangle}{\langle z_{1}-\eta F(z_{2})-z_{3},\hat{z}-z_{3}\rangle}})$ $\displaystyle\leq\frac{1}{\eta}{\mathchoice{\left\langle z_{1}-z_{3}+\eta F(z_{3})-\eta F(z_{2}),z_{3}-\hat{z}\right\rangle}{\langle z_{1}-z_{3}+\eta F(z_{3})-\eta F(z_{2}),z_{3}-\hat{z}\rangle}{\langle z_{1}-z_{3}+\eta F(z_{3})-\eta F(z_{2}),z_{3}-\hat{z}\rangle}{\langle z_{1}-z_{3}+\eta F(z_{3})-\eta F(z_{2}),z_{3}-\hat{z}\rangle}}$ ( $z_{3}=\Pi_{\mathcal{Z}_{\geq}}{\mathchoice{\left[z_{1}-\eta F(z_{2})\right]}{[z_{1}-\eta F(z_{2})]}{[z_{1}-\eta F(z_{2})]}{[z_{1}-\eta F(z_{2})]}}$ ) $\displaystyle\leq\frac{({\mathchoice{\left\|z_{1}-z_{3}\right\|}{\|z_{1}-z_{3}\|}{\|z_{1}-z_{3}\|}{\|z_{1}-z_{3}\|}}+\eta L_{F}{\mathchoice{\left\|z_{3}-z_{2}\right\|}{\|z_{3}-z_{2}\|}{\|z_{3}-z_{2}\|}{\|z_{3}-z_{2}\|}}){\mathchoice{\left\|z_{3}-\hat{z}\right\|}{\|z_{3}-\hat{z}\|}{\|z_{3}-\hat{z}\|}{\|z_{3}-\hat{z}\|}}}{\eta}.$ $$

Moreover, we have

$$ ${\mathchoice{\left\|z_{3}-\hat{z}\right\|}{\|z_{3}-\hat{z}\|}{\|z_{3}-\hat{z}\|}{\|z_{3}-\hat{z}\|}}\leq{\mathchoice{\left\|z_{3}-z\right\|}{\|z_{3}-z\|}{\|z_{3}-z\|}{\|z_{3}-z\|}}+{\mathchoice{\left\|z-\hat{z}\right\|}{\|z-\hat{z}\|}{\|z-\hat{z}\|}{\|z-\hat{z}\|}}\leq{\mathchoice{\left\|z_{3}-z\right\|}{\|z_{3}-z\|}{\|z_{3}-z\|}{\|z_{3}-z\|}}+2.$ $$

Combining the above two inequalities completes the proof.
∎

We now show a few useful properties of the iterates.

###### Proposition 4 .

In the same setup of [Lemma 1](#Thmlemma1), for any $t\geq 1$, the following holds.

- 1.
${\mathchoice{\left\|z^{t+1}-z^{t+\frac{1}{2}}\right\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}}\leq\eta L_{F}{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}\leq{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}$;
- 2.
${\mathchoice{\left\|z^{t+1}-z^{t}\right\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}}\leq(1+\eta L_{F}){\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}\leq 2{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}$.

###### Proof of Proposition 4 .

Using the update rule of ExRM^+ and the non-expansiveness of the projection operator $\Pi_{\mathcal{Z}_{\geq}}[\cdot]$ we have

$$ $\displaystyle{\mathchoice{\left\|z^{t+1}-z^{t+\frac{1}{2}}\right\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}}$ $\displaystyle\leq{\mathchoice{\left\|z^{t}-\eta F(z^{t})-(z^{t}-\eta F(z^{t+\frac{1}{2}}))\right\|}{\|z^{t}-\eta F(z^{t})-(z^{t}-\eta F(z^{t+\frac{1}{2}}))\|}{\|z^{t}-\eta F(z^{t})-(z^{t}-\eta F(z^{t+\frac{1}{2}}))\|}{\|z^{t}-\eta F(z^{t})-(z^{t}-\eta F(z^{t+\frac{1}{2}}))\|}}$ $\displaystyle=\eta{\mathchoice{\left\|F(z^{t+\frac{1}{2}})-F(z^{t})\right\|}{\|F(z^{t+\frac{1}{2}})-F(z^{t})\|}{\|F(z^{t+\frac{1}{2}})-F(z^{t})\|}{\|F(z^{t+\frac{1}{2}})-F(z^{t})\|}}\leq\eta L_{F}{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}.$ $$

Using triangle inequality, we have

$$ ${\mathchoice{\left\|z^{t+1}-z^{t}\right\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}}\leq{\mathchoice{\left\|z^{t+1}-z^{t+\frac{1}{2}}\right\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}}+{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}\leq(1+\eta L_{F}){\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}.\qed$ $$

We are now ready to prove Lemma [5](#Thmlemma5).

###### Proof of Lemma 5 .

Let $z^{\star}$ be any Nash equilibrium of the game. Since $z^{t+1}=\Pi_{\mathcal{Z}_{\geq}}[z^{t}-\eta F(z^{t+\frac{1}{2}})]$, applying [Lemma 7](#Thmlemma7) gives

$$ $\displaystyle\operatorname{DualityGap}(x^{t+1},y^{t+1})$ $\displaystyle\leq\frac{({\mathchoice{\left\|z^{t+1}-z^{t}\right\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}{\|z^{t+1}-z^{t}\|}}+\eta L_{F}{\mathchoice{\left\|z^{t+1}-z^{t+\frac{1}{2}}\right\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}{\|z^{t+1}-z^{t+\frac{1}{2}}\|}})({\mathchoice{\left\|z^{t+1}-z^{\star}\right\|}{\|z^{t+1}-z^{\star}\|}{\|z^{t+1}-z^{\star}\|}{\|z^{t+1}-z^{\star}\|}}+2)}{\eta}$ $\displaystyle\leq\frac{3{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}({\mathchoice{\left\|z^{t+1}-z^{\star}\right\|}{\|z^{t+1}-z^{\star}\|}{\|z^{t+1}-z^{\star}\|}{\|z^{t+1}-z^{\star}\|}}+2)}{\eta}$ ( $\eta L_{F}\leq 1$ and Proposition 4 ) $\displaystyle\leq\frac{3{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}({\mathchoice{\left\|z^{0}-z^{\star}\right\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}}+2)}{\eta}$ ( Lemma 1 ) $\displaystyle\leq\frac{12{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}}{\eta},$ ( $z^{0}$ and $z^{\star}$ are both in the simplex $\Delta^{d_{1}}\times\Delta^{d_{2}}$ ) $$

which finishes the proof.
∎

###### Lemma 7 .

###### Proof of Lemma 7 .

###### Proposition 4 .

###### Proof of Proposition 4 .

###### Proof of Lemma 5 .

### C.3 Proofs for Section 4.3

###### Proof of Theorem 4 .

We note that RS-ExRM^+ always restarts in the first iteration since ${\mathchoice{\left\|z^{\frac{1}{2}}-z^{0}\right\|}{\|z^{\frac{1}{2}}-z^{0}\|}{\|z^{\frac{1}{2}}-z^{0}\|}{\|z^{\frac{1}{2}}-z^{0}\|}}\leq\frac{{\mathchoice{\left\|z^{0}-z^{\star}\right\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}{\|z^{0}-z^{\star}\|}}}{\sqrt{1-\eta^{2}L_{F}^{2}}}\leq\frac{2}{\sqrt{1-\eta^{2}L_{F}^{2}}}$. Let $1=t_{1}<t_{2}<\ldots$ be the iterations where the algorithm restarts with $(x^{t_{k}},y^{t_{k}})$. Using [Lemma 5](#Thmlemma5) and the restart condition, we know that for any $k\geq 1$,

$$ $\displaystyle\operatorname{DualityGap}(x^{t_{k}},y^{t_{k}})$ $\displaystyle\leq\frac{12{\mathchoice{\left\|z^{t_{k}-\frac{1}{2}}-z^{t_{k}-1}\right\|}{\|z^{t_{k}-\frac{1}{2}}-z^{t_{k}-1}\|}{\|z^{t_{k}-\frac{1}{2}}-z^{t_{k}-1}\|}{\|z^{t_{k}-\frac{1}{2}}-z^{t_{k}-1}\|}}}{\eta}\leq\frac{48}{\eta\sqrt{1-\eta^{2}L_{F}^{2}}}\cdot\frac{1}{2^{k}}$ $\displaystyle{\mathchoice{\left\|(x^{t_{k}},y^{t_{k}})-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\right\|}{\|(x^{t_{k}},y^{t_{k}})-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\|}{\|(x^{t_{k}},y^{t_{k}})-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\|}{\|(x^{t_{k}},y^{t_{k}})-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\|}}$ $\displaystyle\leq\frac{\operatorname{DualityGap}(x^{t_{k}},y^{t_{k}})}{c}\leq\frac{48}{c\eta\sqrt{1-\eta^{2}L_{F}^{2}}}\cdot\frac{1}{2^{k}}.$ $$

Moreover, for any iterate $t\in[t_{k}+1,t_{k+1}-1]$, using [Lemma 5](#Thmlemma5), we get

$$ $\displaystyle\operatorname{DualityGap}(x^{t},y^{t})\leq\frac{12{\mathchoice{\left\|z^{t-\frac{1}{2}}-z^{t-1}\right\|}{\|z^{t-\frac{1}{2}}-z^{t-1}\|}{\|z^{t-\frac{1}{2}}-z^{t-1}\|}{\|z^{t-\frac{1}{2}}-z^{t-1}\|}}}{\eta}\leq\frac{12{\mathchoice{\left\|z^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\right\|}{\|z^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\|}{\|z^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\|}{\|z^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\|}}}{\eta\sqrt{1-\eta^{2}L_{F}^{2}}}\leq\frac{576}{c\eta^{2}(1-\eta^{2}L_{F}^{2})}\cdot\frac{1}{2^{k}}.$ $$

Using metric subregularity ([Proposition 2](#Thmproposition2)), we have for any iterate $t\in[t_{k}+1,t_{k+1}-1]$,

$$ $\displaystyle{\mathchoice{\left\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\right\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}}\leq\frac{576}{c^{2}\eta^{2}(1-\eta^{2}L_{F}^{2})}\cdot\frac{1}{2^{k}}.$ $$

If we can prove $t_{k+1}-t_{k}$ is always bounded by a constant $C\geq 1$, then $t_{k}\leq C(k-1)+1\leq Ck$. Then for any $t\geq 1$, we have $t\geq t_{\lfloor\frac{t}{C}\rfloor}$ and

$$ $\displaystyle{\mathchoice{\left\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\right\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}}\leq\frac{576}{c^{2}\eta^{2}(1-\eta^{2}L_{F}^{2})}\cdot\frac{1}{2^{\lfloor\frac{t}{C}\rfloor}}\leq\frac{576}{c^{2}\eta^{2}(1-\eta^{2}L_{F}^{2})}\cdot 2^{-\frac{t}{C}}\leq\frac{576}{c^{2}\eta^{2}(1-\eta^{2}L_{F}^{2})}\cdot(1-\frac{1}{3C})^{t}.$ $$

###### Proof of Theorem 4 .

#### Bounding t k + 1 − t k subscript 𝑡 𝑘 1 subscript 𝑡 𝑘 t_{k+1}-t_{k}

If $t_{k+1}-t_{k}=1$, then the claim holds. Now we assume $t_{k+1}-t_{k}\geq 2$. Before restarting, the updates of $z^{t}$ for $t_{k}\leq t\leq t_{k+1}-2$ is just ExRM^+. By [Lemma 1](#Thmlemma1), we know

$$ $\displaystyle\sum_{t=t_{k}}^{t_{k+1}-2}{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}^{2}\leq\frac{{\mathchoice{\left\|(x^{t_{k}},y^{t_{k}})-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\right\|}{\|(x^{t_{k}},y^{t_{k}})-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\|}{\|(x^{t_{k}},y^{t_{k}})-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\|}{\|(x^{t_{k}},y^{t_{k}})-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\|}}^{2}}{1-\eta^{2}L_{F}^{2}}$ $$

It implies that there exists $t\in[t_{k},t_{k+1}-2]$ such that

$$ $\displaystyle{\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}\leq\frac{{\mathchoice{\left\|(x^{t_{k}},y^{t_{k}})-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\right\|}{\|(x^{t_{k}},y^{t_{k}})-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\|}{\|(x^{t_{k}},y^{t_{k}})-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\|}{\|(x^{t_{k}},y^{t_{k}})-\Pi_{\mathcal{Z}^{\star}}[(x^{t_{k}},y^{t_{k}})]\|}}}{\sqrt{1-\eta^{2}L_{F}^{2}}\sqrt{t_{k+1}-t_{k}-1}}\leq\frac{48}{c\eta(1-\eta^{2}L_{F}^{2})\sqrt{t_{k+1}-t_{k}-1}\cdot 2^{k}}.$ $$

On the other hand, since the algorithm does not restart in $[t_{k},t_{k+1}-2]$, we know for every $t\in[t_{k},t_{k+1}-2]$,

$$ ${\mathchoice{\left\|z^{t+\frac{1}{2}}-z^{t}\right\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}{\|z^{t+\frac{1}{2}}-z^{t}\|}}>\frac{4}{\sqrt{1-\eta^{2}L_{F}^{2}}\cdot 2^{k+1}}.$ $$

Combining the above inequalities gives

$$ $\displaystyle t_{k+1}-t_{k}-1$ $\displaystyle\leq\frac{48^{2}}{c^{2}\eta^{2}(1-\eta^{2}L_{F}^{2})^{2}\cdot 2^{2k}}\cdot\frac{(1-\eta^{2}L_{F}^{2})\cdot 2^{2k+2}}{16}$ $\displaystyle=\frac{48^{2}/4}{c^{2}\eta^{2}(1-\eta^{2}L_{F}^{2})}=\frac{576}{c^{2}\eta^{2}(1-\eta^{2}L_{F}^{2})}.$ $$

#### Linear Last-Iterate Convergence

Combing all the above, we get for all $t\geq 1$,

$$ $\displaystyle\operatorname{DualityGap}(x^{t},y^{t})$ $\displaystyle\leq\frac{576}{c\eta^{2}(1-\eta^{2}L^{2})}\cdot\left(1-\frac{1}{3(1+\frac{576}{c^{2}\eta^{2}(1-\eta^{2}L_{F}^{2})})}\right)^{t}$ $\displaystyle{\mathchoice{\left\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\right\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}{\|(x^{t},y^{t})-\Pi_{\mathcal{Z}^{\star}}[(x^{t},y^{t})]\|}}$ $\displaystyle\leq\frac{576}{c^{2}\eta^{2}(1-\eta^{2}L^{2})}\cdot\left(1-\frac{1}{3(1+\frac{576}{c^{2}\eta^{2}(1-\eta^{2}L_{F}^{2})})}\right)^{t}.$ $$

This completes the proof.
∎

## Appendix D Proofs for Section 5

### D.1 Asymptotic Convergence of SPRM +

In the following, we will prove last-iterate convergence of SPRM^+ ([Algorithm 5](#alg5)). The proof follows the same idea as that of ExRM^+ in previous sections. Applying standard analysis of OG, we have the following important lemma for SPRM^+.

###### Lemma 8 (Adapted from Lemma 1 in (Wei et al., 2021 ) ) .

Let $z^{\star}\in\mathcal{Z}_{\geq}$ be a point such that ${\mathchoice{\left\langle F(z),z-z^{\star}\right\rangle}{\langle F(z),z-z^{\star}\rangle}{\langle F(z),z-z^{\star}\rangle}{\langle F(z),z-z^{\star}\rangle}}\geq 0$ for all $z\in\mathcal{Z}_{\geq}$. Let $\{z^{t}\}$ and $\{w^{t}\}$ be the sequences produced by SPRM^+. Then for every iteration $t\geq 0$ it holds that

$$ ${\mathchoice{\left\|w^{t+1}-z^{\star}\right\|}{\|w^{t+1}-z^{\star}\|}{\|w^{t+1}-z^{\star}\|}{\|w^{t+1}-z^{\star}\|}}^{2}+\frac{1}{16}{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}\leq{\mathchoice{\left\|w^{t}-z^{\star}\right\|}{\|w^{t}-z^{\star}\|}{\|w^{t}-z^{\star}\|}{\|w^{t}-z^{\star}\|}}^{2}+\frac{1}{16}{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}^{2}-\frac{15}{16}{\mathchoice{\left({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2}\right)}{({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2})}{({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2})}{({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2})}}.$ $$

It also implies for any $t\geq 0$,

$$ ${\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}\leq 2{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}},\quad{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}\leq 2{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}.$ $$

###### Lemma 9 .

Let $\{z^{t}\}$ and $\{w^{t}\}$ be the sequences produced by SPRM^+, then

- 1.
The sequences $\{w^{t}\}$ and $\{z^{t}\}$ are bounded and thus have at least one limit point.
- 2.
If the sequence $\{w^{t}\}$ converges to $\hat{w}\in\mathcal{Z}_{\geq}$, then the sequence $\{z^{t}\}$ also converges to $\hat{w}$.
- 3.
If $\hat{w}$ is a limit point of $\{w^{t}\}$, then $\hat{w}\in SOL(\mathcal{Z}_{\geq},F)$ and $g(\hat{w})$ is a Nash equilibrium of the game.

###### Proof.

By [Lemma 8](#Thmlemma8) and the fact that $w^{0}=z^{-1}$, we know for any $t\geq 0$,

$$ ${\mathchoice{\left\|w^{t+1}-z^{\star}\right\|}{\|w^{t+1}-z^{\star}\|}{\|w^{t+1}-z^{\star}\|}{\|w^{t+1}-z^{\star}\|}}^{2}+\frac{1}{16}{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}\leq{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}^{2},$ $$

which implies the sequences $\{w^{t}\}$ and $\{z^{t}\}$ are bounded. Thus, both of them have at least one limit point.
By [Lemma 8](#Thmlemma8), we have

$$ $\frac{15}{32}\sum_{t=1}^{T}{\mathchoice{\left\|w^{t+1}-w^{t}\right\|}{\|w^{t+1}-w^{t}\|}{\|w^{t+1}-w^{t}\|}{\|w^{t+1}-w^{t}\|}}^{2}\leq\frac{15}{16}\sum_{t=1}^{T}{\mathchoice{\left({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2}\right)}{({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2})}{({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2})}{({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2})}}\leq{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}^{2}+\frac{1}{16}{\mathchoice{\left\|w^{0}-z^{-1}\right\|}{\|w^{0}-z^{-1}\|}{\|w^{0}-z^{-1}\|}{\|w^{0}-z^{-1}\|}}^{2}.$ $$

This implies

$$ $\lim_{t\rightarrow\infty}{\mathchoice{\left\|w^{t+1}-w^{t}\right\|}{\|w^{t+1}-w^{t}\|}{\|w^{t+1}-w^{t}\|}{\|w^{t+1}-w^{t}\|}}=0,\quad\lim_{t\rightarrow\infty}{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}=0,\quad\lim_{t\rightarrow\infty}{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}=0.$ $$

If $\hat{w}$ is the limit point of the subsequence $\{w^{t}:t\in\kappa\}$, then we must have

$$ $\lim_{(t\in\kappa)\rightarrow\infty}w^{t+1}=\hat{w},\quad\lim_{(t\in\kappa)\rightarrow\infty}z^{t}=\hat{w}.$ $$

By the definition of $w^{t+1}$ in SPRM^+ and by the continuity of $F$ and of the projection, we get

$$ $\hat{w}=\lim_{t(\in\kappa)\rightarrow\infty}w^{t+1}=\lim_{t(\in\kappa)\rightarrow\infty}\Pi_{\mathcal{Z}_{\geq}}{\mathchoice{\left[w^{t}-\eta F(z^{t})\right]}{[w^{t}-\eta F(z^{t})]}{[w^{t}-\eta F(z^{t})]}{[w^{t}-\eta F(z^{t})]}}=\Pi_{\mathcal{Z}_{\geq}}{\mathchoice{\left[\hat{w}-\eta F(\hat{w})\right]}{[\hat{w}-\eta F(\hat{w})]}{[\hat{w}-\eta F(\hat{w})]}{[\hat{w}-\eta F(\hat{w})]}}.$ $$

This shows that $\hat{w}\in SOL(\mathcal{Z}_{\geq},F)$. By [Lemma 7](#Thmlemma7), we know $g(\hat{w})$ is a Nash equilibrium of the game.
∎

###### Proposition 5 .

Let $\{z^{t}\}$ and $\{w^{t}\}$ be the sequences produced by SPRM^+. If $\{w^{t}\}$ has a limit point $\hat{w}$ such that $\hat{w}=az^{\star}$ for $z^{\star}\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ and $a\geq 1$ (equivalently, colinear with a pair of strategies in the simplex), then $\{w^{t}\}$ converges to $\hat{w}$.

###### Proof.

By [1](#Thmfact1), we know the MVI condition holds for $\hat{w}$, Then by [Lemma 8](#Thmlemma8), $\{{\mathchoice{\left\|w^{t}-\hat{w}\right\|}{\|w^{t}-\hat{w}\|}{\|w^{t}-\hat{w}\|}{\|w^{t}-\hat{w}\|}}^{2}+\frac{1}{16}{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}^{2}\}$ is monotonitically decreasing and therefore converges. Let $\hat{w}$ be the limit of the sequence $\{w^{t}:t\in\kappa\}$. Using the fact that $\lim_{t\rightarrow\infty}{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}=0$, we know that $\{{\mathchoice{\left\|w^{t}-\hat{w}\right\|}{\|w^{t}-\hat{w}\|}{\|w^{t}-\hat{w}\|}{\|w^{t}-\hat{w}\|}}\}$ also converges and

$$ $\lim_{t\rightarrow\infty}{\mathchoice{\left\|w^{t}-\hat{w}\right\|}{\|w^{t}-\hat{w}\|}{\|w^{t}-\hat{w}\|}{\|w^{t}-\hat{w}\|}}^{2}+\frac{1}{16}{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}^{2}=\lim_{t\rightarrow\infty}{\mathchoice{\left\|w^{t}-\hat{w}\right\|}{\|w^{t}-\hat{w}\|}{\|w^{t}-\hat{w}\|}{\|w^{t}-\hat{w}\|}}^{2}=\lim_{t(\in\kappa)\rightarrow\infty}{\mathchoice{\left\|w^{t}-\hat{w}\right\|}{\|w^{t}-\hat{w}\|}{\|w^{t}-\hat{w}\|}{\|w^{t}-\hat{w}\|}}^{2}=0$ $$

Thus, $\{w^{t}\}$ converges to $\hat{w}$.
∎

###### Lemma 10 (Structure of Limit Points) .

Let $\{z^{t}\}$ and $\{w^{t}\}$ be the sequences produced by SPRM^+. Let $z^{\star}\in\Delta^{d_{1}}\times\Delta^{d_{2}}$ be any Nash equilibrium of $A$. If $\hat{w}$ and $\tilde{w}$ are two limit points of $\{w^{t}\}$, then the following holds.

- 1.
${\mathchoice{\left\|az^{\star}-\hat{w}\right\|}{\|az^{\star}-\hat{w}\|}{\|az^{\star}-\hat{w}\|}{\|az^{\star}-\hat{w}\|}}^{2}={\mathchoice{\left\|az^{\star}-\tilde{w}\right\|}{\|az^{\star}-\tilde{w}\|}{\|az^{\star}-\tilde{w}\|}{\|az^{\star}-\tilde{w}\|}}^{2}$ for all $a\geq 1$.
- 2.
${\mathchoice{\left\|\hat{w}\right\|}{\|\hat{w}\|}{\|\hat{w}\|}{\|\hat{w}\|}}^{2}={\mathchoice{\left\|\tilde{w}\right\|}{\|\tilde{w}\|}{\|\tilde{w}\|}{\|\tilde{w}\|}}^{2}$.
- 3.
${\mathchoice{\left\langle z^{\star},\hat{w}-\tilde{w}\right\rangle}{\langle z^{\star},\hat{w}-\tilde{w}\rangle}{\langle z^{\star},\hat{w}-\tilde{w}\rangle}{\langle z^{\star},\hat{w}-\tilde{w}\rangle}}=0$.

###### Proof.

Let $\{k_{i}\in\mathbb{Z}\}$ be an increasing sequence of indices such that $\{w^{k_{i}}\}$ converges to $\hat{w}$ and $\{l_{i}\in\mathbb{Z}\}$ be an increasing sequence of indices such that $\{w^{l_{i}}\}$ converges to $\tilde{w}$. Let $\sigma:\{k_{i}\}\rightarrow\{l_{i}\}$ be a mapping that always maps $k_{i}$ to a larger index in $\{l_{i}\}$, i.e. $\sigma(k_{i})>k_{i}$. Such a mapping clearly exists. Since [Lemma 8](#Thmlemma8) applies to $az^{\star}$ for any $a\geq 1$ and $\lim_{t\rightarrow\infty}{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}=0$, we get

$$ $\displaystyle{\mathchoice{\left\|az^{\star}-\hat{w}\right\|}{\|az^{\star}-\hat{w}\|}{\|az^{\star}-\hat{w}\|}{\|az^{\star}-\hat{w}\|}}^{2}$ $\displaystyle=\lim_{i\rightarrow\infty}{\mathchoice{\left\|az^{\star}-w^{k_{i}}\right\|}{\|az^{\star}-w^{k_{i}}\|}{\|az^{\star}-w^{k_{i}}\|}{\|az^{\star}-w^{k_{i}}\|}}^{2}+\frac{1}{16}{\mathchoice{\left\|w^{k_{i}}-z^{k_{i}-1}\right\|}{\|w^{k_{i}}-z^{k_{i}-1}\|}{\|w^{k_{i}}-z^{k_{i}-1}\|}{\|w^{k_{i}}-z^{k_{i}-1}\|}}^{2}$ $\displaystyle\geq\lim_{i\rightarrow\infty}{\mathchoice{\left\|az^{\star}-w^{\sigma(k_{i})}\right\|}{\|az^{\star}-w^{\sigma(k_{i})}\|}{\|az^{\star}-w^{\sigma(k_{i})}\|}{\|az^{\star}-w^{\sigma(k_{i})}\|}}^{2}+\frac{1}{16}{\mathchoice{\left\|w^{\sigma(k_{i})}-z^{\sigma(k_{i})-1}\right\|}{\|w^{\sigma(k_{i})}-z^{\sigma(k_{i})-1}\|}{\|w^{\sigma(k_{i})}-z^{\sigma(k_{i})-1}\|}{\|w^{\sigma(k_{i})}-z^{\sigma(k_{i})-1}\|}}^{2}$ $\displaystyle={\mathchoice{\left\|az^{\star}-\tilde{w}\right\|}{\|az^{\star}-\tilde{w}\|}{\|az^{\star}-\tilde{w}\|}{\|az^{\star}-\tilde{w}\|}}^{2}.$ $$

By symmetry, the other direction also holds. Thus, ${\mathchoice{\left\|az^{\star}-\hat{w}\right\|}{\|az^{\star}-\hat{w}\|}{\|az^{\star}-\hat{w}\|}{\|az^{\star}-\hat{w}\|}}^{2}={\mathchoice{\left\|az^{\star}-\tilde{w}\right\|}{\|az^{\star}-\tilde{w}\|}{\|az^{\star}-\tilde{w}\|}{\|az^{\star}-\tilde{w}\|}}^{2}$ for all $a\geq 1$.

Expanding ${\mathchoice{\left\|az^{\star}-\hat{w}\right\|}{\|az^{\star}-\hat{w}\|}{\|az^{\star}-\hat{w}\|}{\|az^{\star}-\hat{w}\|}}^{2}={\mathchoice{\left\|az^{\star}-\tilde{w}\right\|}{\|az^{\star}-\tilde{w}\|}{\|az^{\star}-\tilde{w}\|}{\|az^{\star}-\tilde{w}\|}}^{2}$ gives

$$ $\displaystyle{\mathchoice{\left\|\hat{w}\right\|}{\|\hat{w}\|}{\|\hat{w}\|}{\|\hat{w}\|}}^{2}-{\mathchoice{\left\|\tilde{w}\right\|}{\|\tilde{w}\|}{\|\tilde{w}\|}{\|\tilde{w}\|}}^{2}=2a{\mathchoice{\left\langle z^{\star},\hat{w}-\tilde{w}\right\rangle}{\langle z^{\star},\hat{w}-\tilde{w}\rangle}{\langle z^{\star},\hat{w}-\tilde{w}\rangle}{\langle z^{\star},\hat{w}-\tilde{w}\rangle}},\quad\forall a\geq 1.$ $$

It implies that ${\mathchoice{\left\|\hat{w}\right\|}{\|\hat{w}\|}{\|\hat{w}\|}{\|\hat{w}\|}}^{2}={\mathchoice{\left\|\tilde{w}\right\|}{\|\tilde{w}\|}{\|\tilde{w}\|}{\|\tilde{w}\|}}^{2}$ and ${\mathchoice{\left\langle z^{\star},\hat{w}-\tilde{w}\right\rangle}{\langle z^{\star},\hat{w}-\tilde{w}\rangle}{\langle z^{\star},\hat{w}-\tilde{w}\rangle}{\langle z^{\star},\hat{w}-\tilde{w}\rangle}}=0$.
∎

With [Lemma 8](#Thmlemma8), [Lemma 9](#Thmlemma9), [Proposition 5](#Thmproposition5), and [Lemma 10](#Thmlemma10), by the same argument as the proof for ExRM^+ in [Lemma 4](#Thmlemma4), we can prove that $\{w^{t}\}$ produced by SPRM^+ has a unique limit point and thus converges, as shown in the following lemma.

###### Lemma 11 (Uniqueness of Limit Point) .

The iterates $\{w^{t}\}$ produced by SPRM^+ have a unique limit point.

Thus, [Theorem 5](#Thmtheorem5) directly follows from [Lemma 9](#Thmlemma9) and [Lemma 11](#Thmlemma11).

###### Lemma 8 (Adapted from Lemma 1 in (Wei et al., 2021 ) ) .

###### Lemma 9 .

###### Proof.

###### Proposition 5 .

###### Proof.

###### Lemma 10 (Structure of Limit Points) .

###### Proof.

###### Lemma 11 (Uniqueness of Limit Point) .

### D.2 Best-Iterate Convergence of SPRM +

###### Lemma 12 .

Let $\{z^{t}\}$ and $\{w^{t}\}$ be the sequences produced by SPRM^+ ([Algorithm 5](#alg5)). Then

- 1.
$\operatorname{DualityGap}(g(w^{t+1}))\leq\frac{5({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}})}{\eta}$;
- 2.
$\operatorname{DualityGap}(g(z^{t}))\leq\frac{9({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}})}{\eta}$.

.

###### Proof of Lemma 12 .

Since $w^{t+1}=\Pi_{\mathcal{Z}_{\geq}}{\mathchoice{\left[w^{t}-\eta F(z^{t})\right]}{[w^{t}-\eta F(z^{t})]}{[w^{t}-\eta F(z^{t})]}{[w^{t}-\eta F(z^{t})]}}$, by [Lemma 7](#Thmlemma7), we know
for any $z^{\star}\in\mathcal{Z}^{\star}$

$$ $\displaystyle\operatorname{DualityGap}(g(w^{t+1}))$ $\displaystyle\leq\frac{({\mathchoice{\left\|w^{t+1}-w^{t}\right\|}{\|w^{t+1}-w^{t}\|}{\|w^{t+1}-w^{t}\|}{\|w^{t+1}-w^{t}\|}}+\eta L_{F}{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}})({\mathchoice{\left\|w^{t+1}-z^{\star}\right\|}{\|w^{t+1}-z^{\star}\|}{\|w^{t+1}-z^{\star}\|}{\|w^{t+1}-z^{\star}\|}}+2)}{\eta}$ $\displaystyle\leq\frac{(1+\eta L_{F})({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}})({\mathchoice{\left\|w^{t+1}-z^{\star}\right\|}{\|w^{t+1}-z^{\star}\|}{\|w^{t+1}-z^{\star}\|}{\|w^{t+1}-z^{\star}\|}}+2)}{\eta}$ $\displaystyle\leq\frac{(1+\eta L_{F})({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}})({\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}+2)}{\eta}$ $\displaystyle\leq\frac{5({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}})}{\eta},$ $$

where in the second inequality we apply ${\mathchoice{\left\|w^{t+1}-w^{t}\right\|}{\|w^{t+1}-w^{t}\|}{\|w^{t+1}-w^{t}\|}{\|w^{t+1}-w^{t}\|}}\leq{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}$; in the third inequality we use ${\mathchoice{\left\|w^{t+1}-z^{\star}\right\|}{\|w^{t+1}-z^{\star}\|}{\|w^{t+1}-z^{\star}\|}{\|w^{t+1}-z^{\star}\|}}\leq{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}$ by [Lemma 8](#Thmlemma8); in the last inequality we use $\eta L_{F}\leq\frac{1}{8}$ and ${\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}\leq 2$ since $w^{0},z^{\star}\in\Delta^{d_{1}}\times\Delta^{d_{2}}$.

Similarly, since $z^{t}=\Pi_{\mathcal{Z}_{\geq}}[w^{t}-\eta F(z^{t-1})]$, by [Lemma 7](#Thmlemma7), we know for any $z^{\star}\in\mathcal{Z}^{\star}$

$$ $\displaystyle\operatorname{DualityGap}(g(z^{t}))$ $\displaystyle\leq\frac{({\mathchoice{\left\|z^{t}-w^{t}\right\|}{\|z^{t}-w^{t}\|}{\|z^{t}-w^{t}\|}{\|z^{t}-w^{t}\|}}+\eta L_{F}{\mathchoice{\left\|z^{t}-z^{t-1}\right\|}{\|z^{t}-z^{t-1}\|}{\|z^{t}-z^{t-1}\|}{\|z^{t}-z^{t-1}\|}})({\mathchoice{\left\|z^{t}-z^{\star}\right\|}{\|z^{t}-z^{\star}\|}{\|z^{t}-z^{\star}\|}{\|z^{t}-z^{\star}\|}}+2)}{\eta}$ $\displaystyle\leq\frac{(1+\eta L_{F})({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}})({\mathchoice{\left\|w^{t}-z^{\star}\right\|}{\|w^{t}-z^{\star}\|}{\|w^{t}-z^{\star}\|}{\|w^{t}-z^{\star}\|}}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+2)}{\eta}$ $\displaystyle\leq\frac{(1+\eta L_{F})({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}})({\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}+2{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}+2)}{\eta}$ $\displaystyle\leq\frac{9({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}})}{\eta},$ $$

where in the second inequality we apply ${\mathchoice{\left\|z^{t}-z^{t-1}\right\|}{\|z^{t}-z^{t-1}\|}{\|z^{t}-z^{t-1}\|}{\|z^{t}-z^{t-1}\|}}\leq{\mathchoice{\left\|z^{t}-w^{t}\right\|}{\|z^{t}-w^{t}\|}{\|z^{t}-w^{t}\|}{\|z^{t}-w^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}$ and ${\mathchoice{\left\|z^{t}-z^{\star}\right\|}{\|z^{t}-z^{\star}\|}{\|z^{t}-z^{\star}\|}{\|z^{t}-z^{\star}\|}}\leq{\mathchoice{\left\|z^{t}-w^{t}\right\|}{\|z^{t}-w^{t}\|}{\|z^{t}-w^{t}\|}{\|z^{t}-w^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{\star}\right\|}{\|w^{t}-z^{\star}\|}{\|w^{t}-z^{\star}\|}{\|w^{t}-z^{\star}\|}}$; in the third inequality we use ${\mathchoice{\left\|w^{t+1}-z^{\star}\right\|}{\|w^{t+1}-z^{\star}\|}{\|w^{t+1}-z^{\star}\|}{\|w^{t+1}-z^{\star}\|}}\leq{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}$ and ${\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}\leq 2{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}$ by [Lemma 8](#Thmlemma8); in the last inequality we use $\eta L_{F}\leq\frac{1}{8}$ and ${\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}\leq 2$ since $w^{0},z^{\star}\in\Delta^{d_{1}}\times\Delta^{d_{2}}$.
∎

###### Proof of Theorem 6 .

Fix any Nash equilibrium $z^{\star}$ of the game. From [Lemma 8](#Thmlemma8), we know that

$$ $\displaystyle\sum_{t=0}^{T-1}{\mathchoice{\left({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2}\right)}{({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2})}{({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2})}{({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2})}}\leq\frac{16}{15}\cdot{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}^{2}.$ $$

This implies that there exists $0\leq t\leq T-1$ such that ${\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}\leq\frac{2{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}}{\sqrt{T}}$ (we use $a+b\leq\sqrt{2(a^{2}+b^{2})}$). By applying [Lemma 12](#Thmlemma12), we then get

$$ $\operatorname{DualityGap}(g(w^{t+1}))\leq\frac{5({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}})}{\eta}\leq\frac{10{\mathchoice{\left\|w^{0}-z^{*}\right\|}{\|w^{0}-z^{*}\|}{\|w^{0}-z^{*}\|}{\|w^{0}-z^{*}\|}}}{\eta\sqrt{T}}.$ $$

Similarly, using [Lemma 8](#Thmlemma8) and the fact that $w^{0}=z^{-1}$, we know

$$ $\displaystyle\sum_{t=0}^{T}{\mathchoice{\left({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}^{2}\right)}{({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}^{2})}{({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}^{2})}{({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}^{2})}}\leq\sum_{t=0}^{T}{\mathchoice{\left({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}\right)}{({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2})}{({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2})}{({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2})}}\leq\frac{16}{15}\cdot{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}^{2}.$ $$

This implies that there exists $0\leq t\leq T$ such that ${\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}\leq\frac{2{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}}{\sqrt{T}}$ (we use $a+b\leq\sqrt{2(a^{2}+b^{2})}$). By applying [Lemma 12](#Thmlemma12), we then get

$$ $\operatorname{DualityGap}(g(z^{t}))\leq\frac{9({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}})}{\eta}\leq\frac{18{\mathchoice{\left\|w^{0}-z^{*}\right\|}{\|w^{0}-z^{*}\|}{\|w^{0}-z^{*}\|}{\|w^{0}-z^{*}\|}}}{\eta\sqrt{T}}.$ $$

∎

###### Lemma 12 .

###### Proof of Lemma 12 .

###### Proof of Theorem 6 .

### D.3 Linear convergence of RS-SPRM + .

###### Proof of Theorem 7 .

We note that [Algorithm 7](#alg7) always restarts in the first iteration $t=1$ since ${\mathchoice{\left\|w^{1}-z^{0}\right\|}{\|w^{1}-z^{0}\|}{\|w^{1}-z^{0}\|}{\|w^{1}-z^{0}\|}}+{\mathchoice{\left\|w^{0}-z^{0}\right\|}{\|w^{0}-z^{0}\|}{\|w^{0}-z^{0}\|}{\|w^{0}-z^{0}\|}}\leq\sqrt{\frac{32}{15}{\mathchoice{\left\|w^{0}-z^{\star}\right\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}{\|w^{0}-z^{\star}\|}}^{2}}\leq 4=\frac{8}{2^{1}}$. We denote $1=t_{1}<t_{2}<\ldots<t_{k}<\ldots$ the iteration where [Algorithm 7](#alg7) restarts for the $k$-th time, i.e., the “If” condition holds. Then by [Lemma 12](#Thmlemma12), we know for every $t_{k}$, $w^{t_{k}}=g(w^{t_{k}})\in\mathcal{Z}=\Delta^{d_{1}}\times\Delta^{d_{2}}$ and

$$ $\displaystyle\operatorname{DualityGap}(w^{t_{k}})\leq\frac{5({\mathchoice{\left\|w^{t_{k}}-z^{t_{k}-1}\right\|}{\|w^{t_{k}}-z^{t_{k}-1}\|}{\|w^{t_{k}}-z^{t_{k}-1}\|}{\|w^{t_{k}}-z^{t_{k}-1}\|}}+{\mathchoice{\left\|w^{t_{k}-1}-z^{t_{k}-1}\right\|}{\|w^{t_{k}-1}-z^{t_{k}-1}\|}{\|w^{t_{k}-1}-z^{t_{k}-1}\|}{\|w^{t_{k}-1}-z^{t_{k}-1}\|}})}{\eta}\leq\frac{40}{\eta\cdot 2^{k}},$ $$

and by metric subregularity ([Proposition 2](#Thmproposition2)), we have

$$ $\displaystyle{\mathchoice{\left\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\right\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\|}}\leq\frac{\operatorname{DualityGap}(g(w^{t_{k}}))}{c}\leq\frac{40}{c\eta\cdot 2^{k}}.$ $$

Then, for any iteration $t_{k}+1\leq t\leq t_{k+1}-1$, using [Lemma 8](#Thmlemma8) and [Lemma 12](#Thmlemma12), we have

$$ $\displaystyle\operatorname{DualityGap}(g(w^{t}))$ $\displaystyle\leq\frac{5({\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}}+{\mathchoice{\left\|w^{t-1}-z^{t-1}\right\|}{\|w^{t-1}-z^{t-1}\|}{\|w^{t-1}-z^{t-1}\|}{\|w^{t-1}-z^{t-1}\|}})}{\eta}$ ( Lemma 12 ) $\displaystyle\leq\frac{10{\mathchoice{\left\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\right\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\|}}}{\eta}$ ( Lemma 8 ) $\displaystyle\leq\frac{400}{c\eta^{2}\cdot 2^{k}}.$ $$

Then again by metric subregularity, we also get ${\mathchoice{\left\|g(w^{t})-\Pi_{\mathcal{Z}^{\star}}[g(w^{t})]\right\|}{\|g(w^{t})-\Pi_{\mathcal{Z}^{\star}}[g(w^{t})]\|}{\|g(w^{t})-\Pi_{\mathcal{Z}^{\star}}[g(w^{t})]\|}{\|g(w^{t})-\Pi_{\mathcal{Z}^{\star}}[g(w^{t})]\|}}\leq\frac{400}{c^{2}\eta^{2}\cdot 2^{k}}$ for every $t\in[t_{k}+1,t_{k+1}-1]$.

Similarly, for any iteration $t_{k}\leq t\leq t_{k+1}-1$, using [Lemma 8](#Thmlemma8) and [Lemma 12](#Thmlemma12), we have

$$ $\displaystyle\operatorname{DualityGap}(g(z^{t}))$ $\displaystyle\leq\frac{9({\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t-1}\right\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}{\|w^{t}-z^{t-1}\|}})}{\eta}$ ( Lemma 12 ) $\displaystyle\leq\frac{18{\mathchoice{\left\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\right\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\|}}}{\eta}$ ( Lemma 8 ) $\displaystyle\leq\frac{720}{c\eta^{2}\cdot 2^{k}}.$ $$

Then by metric subregularity, we also get ${\mathchoice{\left\|g(z^{t})-\Pi_{\mathcal{Z}^{\star}}[g(z^{t})]\right\|}{\|g(z^{t})-\Pi_{\mathcal{Z}^{\star}}[g(z^{t})]\|}{\|g(z^{t})-\Pi_{\mathcal{Z}^{\star}}[g(z^{t})]\|}{\|g(z^{t})-\Pi_{\mathcal{Z}^{\star}}[g(z^{t})]\|}}\leq\frac{400}{c^{2}\eta^{2}\cdot 2^{k}}$ for every $t\in[t_{k},t_{k+1}-1]$.

###### Proof of Theorem 7 .

#### Bounding t k + 1 − t k subscript 𝑡 𝑘 1 subscript 𝑡 𝑘 t_{k+1}-t_{k}

Fix any $k\geq 1$. If $t_{k+1}=t_{k}+1$, then we are good. Now we assume $t_{k+1}>t_{k}+1$. By [Lemma 8](#Thmlemma8), we know

$$ $\displaystyle\sum_{t=t_{k}}^{t_{k+1}-2}({\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}^{2}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}^{2})\leq\frac{16}{15}{\mathchoice{\left\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}\right\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}\|}}^{2}.$ $$

This implies that there exists $t\in[t_{k},t_{k+1}-2]$ such that

$$ $\displaystyle{\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}\leq\frac{2{\mathchoice{\left\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\right\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\|}{\|w^{t_{k}}-\Pi_{\mathcal{Z}^{\star}}[w^{t_{k}}]\|}}}{\sqrt{t_{k+1}-t_{k}-1}}\leq\frac{80}{c\eta 2^{k}}\frac{1}{\sqrt{t_{k+1}-t_{k}-1}}.$ $$

On the other hand, since [Algorithm 7](#alg7) does not restart in $[t_{k},t_{k+1}-2]$, we have for every $t\in[t_{k},t_{k+1}-2]$,

$$ ${\mathchoice{\left\|w^{t+1}-z^{t}\right\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}{\|w^{t+1}-z^{t}\|}}+{\mathchoice{\left\|w^{t}-z^{t}\right\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}{\|w^{t}-z^{t}\|}}>\frac{8}{2^{k+1}}.$ $$

Combining the above two inequalities, we get

$$ $\displaystyle t_{k+1}-t_{k}-1\leq\frac{400}{c^{2}\eta^{2}}.$ $$

#### Linear Last-Iterate Convergence Rates

Define $C:=1+\frac{400}{c^{2}\eta^{2}}\geq t_{k+1}-t_{k}$. Then $t_{k}\leq Ck$ and for any $t\geq 1$, we have $t\geq t_{\lfloor\frac{t}{C}\rfloor}$ and

$$ $\displaystyle\operatorname{DualityGap}(g(w^{t}))\leq\frac{400}{c\eta^{2}}\cdot 2^{-\lfloor\frac{t}{C}\rfloor}\leq\frac{400}{c\eta^{2}}\left(1-\frac{1}{3C}\right)^{t}=\frac{400}{c\eta^{2}}\cdot\left(1-\frac{1}{3(1+\frac{400}{c^{2}\eta^{2}})}\right)^{t}.$ $$

Using metric subregularity, we get for any $t\geq 1$.

$$ $\displaystyle{\mathchoice{\left\|g(w^{t})-\Pi_{\mathcal{Z}^{\star}}[g(w^{t})]\right\|}{\|g(w^{t})-\Pi_{\mathcal{Z}^{\star}}[g(w^{t})]\|}{\|g(w^{t})-\Pi_{\mathcal{Z}^{\star}}[g(w^{t})]\|}{\|g(w^{t})-\Pi_{\mathcal{Z}^{\star}}[g(w^{t})]\|}}\leq\frac{400}{c^{2}\eta^{2}}\cdot\left(1-\frac{1}{3(1+\frac{400}{c^{2}\eta^{2}})}\right)^{t}.$ $$

Similarly, we have for any $t\geq 1$

$$ $\displaystyle\operatorname{DualityGap}(g(z^{t}))$ $\displaystyle\leq\frac{720}{c\eta^{2}}\cdot\left(1-\frac{1}{3(1+\frac{400}{c^{2}\eta^{2}})}\right)^{t},{\mathchoice{\left\|g(z^{t})-\Pi_{\mathcal{Z}^{\star}}[g(z^{t})]\right\|}{\|g(z^{t})-\Pi_{\mathcal{Z}^{\star}}[g(z^{t})]\|}{\|g(z^{t})-\Pi_{\mathcal{Z}^{\star}}[g(z^{t})]\|}{\|g(z^{t})-\Pi_{\mathcal{Z}^{\star}}[g(z^{t})]\|}}\leq\frac{720}{c^{2}\eta^{2}}\cdot\left(1-\frac{1}{3(1+\frac{400}{c^{2}\eta^{2}})}\right)^{t}.$ $$

This completes the proof.
∎

## Appendix E Additional numerical experiments

### E.1 Game instances

Below we describe the extensive-form benchmark game instances we test in our experiments. These games are solved in their *normal-form* representation. For each game, we report the size of the payoff matrix in this representation.

#### Kuhn poker

Kuhn poker is a widely used benchmark game introduced by Kuhn (). At
the beginning of the game, each player pays one chip to the
pot, and each player is dealt a single private card from a deck containing three cards: jack, queen, and king. The first
player can check or bet, i.e., putting an additional chip in
the pot. Then, the second player can check or bet after the first
player’s check, or fold/call the first player’s bet. After a bet of
the second player, the first player still has to decide whether to fold or to call the bet. At the showdown, the player with the highest card who has not folded wins all the chips in the pot.

The payoff matrix for Kuhn poker has dimension $27\times 64$ and $690$ nonzeros.

#### Goofspiel

We use an imperfect-information variant of the standard benchmark game introduced
by Ross (). We use a 4-rank variant, that is, each player has a hand of cards with values $\{1,2,3,4\}$. A third stack of cards with values $\{1,2,3,4\}$ (in order) is placed on
the table. At each turn, a prize card is revealed, and each
player privately chooses one of his/her cards to bid. The players do not reveal the cards that they
have selected. Rather, they show their cards to a fair umpire,
which determines which player has played the highest card
and should receive the prize card as a result. In case of a tie, the
prize is split evenly among the winners. After 4 turns, all
the prizes have been dealt out and the game terminates. The payoff of each player is computed as the sum of the values of the cards they won.

The payoff matrix for Goofspiel has dimension $72\times 7,\!808$ and $562,\!176$ nonzeros.

#### Random instances.

We consider random matrices of size $(10,15)$. The coefficients of the matrices are normally distributed with mean 0 0 and variance $1$ and are sampled using the numpy.random.normal function from the numpy Python package (Harris et al., ). In all figures, we average the last-iterate duality gaps over the $25$ random matrix instances, and we also show the confidence intervals.

### E.2 Experiments with restarting

In this section, we compare the last-iterate convergence performances of ExRM^+, SPRM^+ and their restarting variants RS-ExRM^+ and RS-SPRM^+ as introduced in Section [4.3](#S4.SS3) and Section [5](#S5). We present our results when choosing a stepsize $\eta=0.05$ in Figure [4](#A5.F4).

Figure: Figure 4: For a stepsize $\eta=0.05$, empirical performances of several algorithms on our $3\times 3$ matrix game (left plot), Kuhn Poker and Goofspiel (center plots) and on random instances (right plot).

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See Weaknesses.
soundness: 3
strengths: 1) The paper is generally well written .

2) They show that RM+ and PRM+ have last-iterate convergence (asymptotically) only in the case of having a strict-NE and provide a numerical example that this assumption is necessary.

3) Moving on to the smooth variants of RM+ introduced in [Farina et al., 2023], they show that the operators corresponding to these algorithms are non-monotone and satisfy only a weak condition known as the Minty condition.

4) Furthermore, they provide structural analysis on the limit points of the dynamics and show last-iterate convergence and this can be extended with additional regularity assumptions (metric-subregularity) and with restarts to show linear last-iterate convergence as well.

References:
Farina, Gabriele, et al. "Regret matching+:(in) stability and fast convergence in games." Advances in Neural Information Processing Systems 36 (2024).
summary: The authors study last-iterate convergence  for Regret Matching + (RM+) algorithm and its recent variants PRM+ (Predictive RM+), ExRM+ (Extragradient RM+) and Smooth Predictive RM+(SPRM+) in two-player zero-sum bimatrix games. They show asymptotic last-iterate convergence of these variants (linear last-iterate with restarts). They also show ($1/\sqrt{t})$ best-iterate convergence.
weaknesses: 1) Their paper is restricted to two-player zero-sum games (bimatrix) games. It would be great to get a clarity as to if these techniques can be extended for general convex-concave games? (And also for general convex sets).

2) Is it possible to obtain asymptotic rates of convergence for the last-iterate analysis shown here?

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: Do you have any insight about the rate of convergence of the result of the Theorem 1? I think this will be a good direction for future work.
soundness: 3
strengths: In my opinion I think that the problem of learning algorithms in games is one of the fundamental problems in algorithmic game theory. Thus, the contribution of this paper is significant since not only the authors give results for variants of the RM+ algorithm (a well-known algorithm), but also give nice and novel techniques and directions, such as the algorithms with the restart, that can potentially help the research to go further on the learning algorithms. All these along with the quality of the paper make it a nice piece of research work.
summary: Learning algorithms for games is one of the fundamental research areas in algorithmic game theory. In this direction the authors of the paper study the (variants of) Regret Matching+ (RM+) algorithms in terms of last/best-iterate convergence.

Firstly, the authors give instances that (variants of) the RM+ algorithm diverges for last/best-iterate convergence even if the Nash equilibrium of the game is unique, so quasi-strict NE. On the other hand, interestingly enough, if there is a unique Nash equilibrium that is strict, so pure NE, they give a Theorem that PM+ converges in last-iterate, but without giving any rate guarantee.   

After this analyzing properties of the operator, they give last-iterate convergence and best-iterate convergence for the EXRM+ algorithm giving also convergence rate for the duality gap matching the state of the art O(1/sqrt{t}) for last-iterate algorithms. Similarly, they prove last/best-iterate convergence for the SPRM+ algorithm with same rate of convergence guarantee. Furthermore, they give, in my opinion a very interesting, variant of them that achieves linear last iterate convergence.

Finally the authors give experiments to give evidence for their results.
weaknesses: My only minor concern is that in Theorem 4 and 7 I think that η must be constant (not function of t) since β must be upper bounded by a constant strictly less than 1 in order to have linear (geometric/inverse exponential) convergence. Thus, I think, if I am correct, that this should be explicitly stated in the Theorems.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. Can you elaborate on the motivation behind considering RM+ algorithm in NFGs? Why are they important in NFGs, given that there are convergence algorithms like EG/OG. 
2. How can the results be extended to EFGs?
3. Is it possible to modify EXRM+ to be no regret? Is SPRM+ no regret? ( i believe OG is no regret, so does this extend to SPRM+?)
soundness: 3
strengths: The last iterate convergence of RM algorithms is important and the nonconvergence results are new and interesting. The paper is well-written and the results are sound.
summary: The paper studies the last iterate convergence of regret matching and its variant in two-player zero-sum games. The results show that RM+ and its predictive variants may not converge, but the extra gradient and optimistic gradient varients can converge.
weaknesses: The main weakness i that RM+ and its variants are mainly applied in EFGs, and so is the paper introduced and motivated. However, the results in the paper only hold for normal-form games. It is hard to be convinced that the results can be extended to EFGs without major revisions, so the motivation to study RM+ in NFGs is insufficient. 

The other major problem is that ExtraRM+ is not no-regret, this somewhat contradicts the purpose of regret-matching.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. What is the exact difference between "Convergence of the iterates" and "Convergence in the Duality Gap"? What are the advantages of "Convergence of the iterates" compared to "Convergence in the Duality Gap"?

2. Why does the first author in prior works use tangent residual to claim "last-iterate convergence," while this paper distinguishes between "Convergence of the iterates" and "Convergence in the Duality Gap"?

3. Is the claim in the conclusion about "linear-rate convergence in iterates" correct?

If the authors can address my concerns regarding the "Convergence of the iterates," I would be willing to increase my score.
soundness: 3
strengths: This paper was previously submitted to ICLR 2024. This paper investigates the convergence of RM+ algorithms, an important topic that has been missing in prior research. It offers valuable insights for future studies. To the best of my knowledge, this is the second paper to explore the convergence properties of RM+ algorithms.
summary: This paper investigates the last-iterate convergence rate of RM+ algorithms. Firstly, they provide numerical evidence that RM+ and PRM+,may fail to have asymptotic last-iterate convergence and best-iterate convergence. Secondly, they prove that ExRM+ and SPRM+ exhibit asymptotic last-iterate convergence. Lastly, they prove an $O(1/T)$ best-iterate convergence for ExRM+ and SPRM+, and use this best-iterate convergence to introduce new variants of ExRM+ and SPRM+, which achieve linear last-iterate convergence.
weaknesses: 1. Although this paper considers a different game from [Meng et al., 2023], its analysis of the convergence of RM+ largely depends on the analysis of the convergence of RM+ in [Meng et al., 2023]. More precisely, the proofs of RM+ convergence in this paper and in [Meng et al., 2023] are identical. The primary novelty of convergence results of RM+ of this paper relative to [Meng et al., 2023] lies in the properties of strict NE. Therefore, the authors should revise the introduction to remove the claim that [Meng et al., 2023] is "incomparable to our matrix game setting" and instead explicitly acknowledge that the convergence proof of RM+ of this paper largely depends on [Meng et al., 2023].

2. The second, and most critical, weakness of this paper is the lack of clarity in its explanation of the convergence of the iterates.
   - Convergence in the Duality Gap indicates that the iterates converge to the set of NE. For solving NE, this is sufficient, as the goal is merely to find one NE.
   - The metric used in the first author's previous works about the  last-iterate convergence of OMD-based algorithms, Tangent Residual means the upper bound of Duality Gap. In other words, the convergence in the tangent residual means the convergence in the duality gap. Why the convergence in the tangent residual is this sufficient to claim the last-iterate convergence in the earlier works but not in this paper?
   - In Section 7 Conclusions, the authors claim “linear-rate convergence in iterates.” However, the metric for linear-rate convergence is also the Duality Gap.

Meta-review: A great paper in last-iterate convergence of learning in games!

Decision: Accept (Poster)