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

Thank you for the very positive review. We address your questions below.

Q1: I’m confused about the notation \delta_{\ge}: aren’t all the strategies in \delta already probability distribution that whose sum is exactly 1?

A: It is correct that all the strategies in $\Delta$ are probability distributions whose sum is exactly 1. The ExRM+ and SPRM+ algorithm (proposed in [1]) use the regret operator (Equation 2) which is defined over the lifted space $\Delta_{\ge}:= \\{ u \in R+, 1^T u \ge 1 \\}$. We can map a point $z$ in $\Delta_{\ge}$ to a point in $\Delta$ by $\ell_1$ normalization: the normalized point $z’ = g(z) = z/||z||_1$ is a probability distribution.

Q2: For the numerical run on the 3X3 algorithm, it would be very insightful to plot the actual trajectory of the algorithms (it should be relatively easy to plot in 2D since the strategies are probability distributions over 3 actions)

A: Thanks for this suggestion. We have run additional experiments to obtain plots showing the trajectories of RM+, alt. RM+, PRM+, alt. PRM+, ExRM+, and SPRM+ on the $3\times 3$ matrix. We plot the last 2000 iterations (out of $10^5$ iterations) of both players in 2D. The results show that the trajectories of RM+, alt. RM+, PRM+ cycle while alt. PRM+, ExRM+, and SPRM+ converge. The empirical results can be found at this anonymized link: https://docdro.id/KUGvPvg We thank you for this interesting point, we will add this in the revised paper.

Q2a. Related, I’m curious if best-iterate convergence of RM+ etc is any better?

A: No. As shown in Figure 1 in the paper, the duality gap of the best-iterate of RM+ is also at least $10^{-1}$ after $10^5$ iterates. Thus the non-convergence holds for both the best-iterate and last-iterate. Moreover, in additional experiments above, we observe the cycling behavior of RM+, which further shows that the best-iterate does not converge.

Q3: The bulk of the work in Sections 4 and 5 is, AFAICT, to deal with solutions of the VI that are not NE. I’m a bit confused about it – when you introduced the VI notation I expected that NE would be the only solutions. Maybe you could give a simple example of a non-NE solution? That would really help build intuition.

A: This is not correct. Every solution of the VI corresponds to a NE after normalization. In section 4 and 5, the main technical challenge is that some solutions do not satisfy the Minty condition. In the following, we first explain with an example that every solution of the VI corresponds to a NE after normalization.

Every solution of the VI corresponds to a NE after normalization: Specifically, the VI is defined over the lifted space $Z_{\ge} = \Delta_{\ge}^{d_1} \times \Delta_{\ge}^{d_2}$ as defined above (also in page 4 at the paragraph introducing ExRM+ and SPRM+). Note that for $x \in \Delta^{d_1}_{\ge}$, $\sum_i x_i$ could be greater than 1. Thus $x$ may not be a probability distribution and may not be in an NE. However, we have shown in Lemma 2 that for any solution $z = (x, y)$ of the VI in the lifted space (they may not be probability distributions), they corresponds to a Nash equilibrium in the sense that after $\ell_1$ normalization, the point $g(z) = (x/||x||_1, y /||y||_1)$ must be a Nash equilibrium.

Example: The Rock-Paper-Scissors game has a unique Nash equilibrium where both players use $x^* = y^*= (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$. In the lifted space, any point of the form $(Qx^*, R y^*)$ with $Q, R \ge 1$ is a solution to the variational inequality $VI(F, Z_{\ge})$. When $Q > 1$ or $R > 1$, $z = (Qx^*, R y^*)$ is not a Nash equilibrium but corresponds to the Nash equilibrium $g(z) = (x^*, y^*)$ after $\ell_1$ normalization.

Some solutions do not satisfy the Minty condition: Let $(x, y)$ be any Nash equilibrium. In Fact 1, we show that $(Q x, Qy)$ for any $Q \ge 1$ satisfies the Minty condition for the $VI(F, Z_\ge)$. However, there exists solutions of the form $(Qx, Ry)$ where $Q \ne R$ and such solutions may not satisfy the Minty condition. The existence of non-Minty solutions of the VI adds difficulty to proving last-iterate convergence. In section 4 and 5, we overcome this challenge by establishing structural characterization of the limit points of the learning dynamics (Lemma 3).

Q4: I probably missed something, but I didn’t understand why you need to talk about best iterate vs last iterate in Section 4.2. Does the guarantee of Lemma 1 not imply something about the convergence of last z^t?

A: Lemma 1 does not immediately imply last-iterate convergence, unless one first establishes stronger properties of the operator, which are not known to hold in general in our setting. The key is that Lemma 1 establishes geometric decrease in distance on the lifted joint strategy set $\mathcal{Z}_{\ge}$. However, this does not imply a geometric improvement of the distance for the normalized strategies.

Q: As previously mentioned, the empirical success of RM+ algorithms lacks a solid theoretical foundation. In this context, investigating the last-iterate convergence properties of RM or RM+ appears to be a reasonable step in the right direction. However, I do have reservations about the significance of establishing last-iterate convergence results for artificial RM variants, especially given the existing results for Extragradient and OMD.

A: We thank you for your time reviewing our work. In Figure 1 in the paper, we show that vanilla RM+, alternating RM+ and Predictive RM+ may not converge in iterates. This is the reason why we focus on Smooth Predictive RM+ (SPRM+) and ExRM+ [4]. Additionally, we would like to clarify that our proofs of last-convergence for SPRM+ and ExRM+ do not follow from the existing analysis of Extragradient (EG) and optimistic mirror descent (OMD) [1]. Indeed, the results in [1] rely on the motonicity of the gradient operator. However, ExRM+ and SPRM+ are equivalent to running EG and OG using the regret operator $F(z) := (Ay - x^T A y \cdot 1_{d_1} , -A^Tx + x^T A y \cdot 1_{d_2})$ over a lifted space $Z_{\ge}$ (F is defined in equation (2) in the paper). The regret operator $F$ is not monotone over $Z_{\ge}$. That is why we cannot derive last-iterate convergence rates for ExRM+ or SPRM+ via existing results in [2]. The non-monotonicity of the regret operator also partly explains why the last-iterate convergence behavior of regret matching-type algorithms was previously not understood.

Q: Additionally, I suggest that the paper could enhance its value by presenting time-average results for the different RM variants. It would be particularly intriguing to see the time-average convergence rates of the alternating PRM+ algorithm, which, as demonstrated in the provided experiments, seems to significantly outperform other RM methods in terms of last-iterate convergence. Furthermore, an experimental comparison of the last-iterate properties of Extragradient and OMD would be a valuable addition.

A: We have conducted additional numerical experiments to answer your question. In the following anonymized link: https://docdro.id/6dvF63M, we plot in Figure 2 the average performance of SPRM+, ExRM+, alt PRM+, Extragradient algorithm (EG) and optimistic mirror descent (OMD). on the 3x3 matrix game from Section 3 in the paper. As evident from the plots, all these algorithms have similar empirical performances (for the average of the iterates). In the same document in Figure 1, we compare the last-iterate performance of all the algorithms presented in the paper, as well as EG and OMD. We see that ExRM+ and SPRM+ have similar performances as EG and OMD, and alt PRM+ is faster. We would like to conclude by highlighting two facts:

1. The performance of the average iterates of (predictive) RM+ with/without alternation have been studied in the past [3, 4].
2. While the alt PRM+ algorithm appears to have strong empirical performance, in the existing literature, there is no proof that alt PRM+ converges either on average or in iterates.

We thank you for this interesting point, we will add this in the revised paper.

Q: Is there a limit for the constant $c$ in Proposition 2? Could it potentially be exceedingly small, perhaps even exponentially so?

A: The constant $c$ depends on the game matrix and can be arbitrarily small. The metric subregularity condition on the constant $c$ is introduced and utilized in previous works (see e.g., [2] and references therein). Our results are comparable to the linear last-iterate convergence results for OGDA [2], which also depend on the constant $c$. We remark that we also provide a $1/\sqrt{T}$ best-iterate convergence rate that is independent of $c$.

[1] Finite-Time Last-Iterate Convergence for Learning in Multiplayer Games. Yang Cai, Argyris Oikonomou, Weiqiang Zheng. NeurIPS 2022

[2] Wei, Chen-Yu, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. "Linear Last-iterate Convergence in Constrained Saddle-point Optimization." ICLR 2021

[3] Burch, N., Moravcik, M., & Schmid, M. Revisiting CFR+ and alternating updates. JAIR, 2019

[4] Farina, Gabriele, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, and Haipeng Luo. "Regret Matching+:(In) Stability and Fast Convergence in Games. " NeurIPS, 2023

I think the main point of the submission is to analyze plausible uncoupled dynamics by which players can converge to Nash equilibrium - not just an algorithm for computing one.

This is why last iterate convergence is important, and why comparison to sota LP solvers is not so relevant.

I am not sure I understand why the results of the authors is not something already known? Am I missing something?

We already know that in convex-concave min-max games optimistic gradient descent ascent, and extragradient descent ascent converges in last-iterates. One of these algos (namely extragradient descent ascent) is one that the authors propose... but the convergence rate and last-iterate convergence is known (see for instance [1])?

I am not disputing the correctness of the results of the paper, but I think that the authors' results are subsumed by previous papers.

[1] Cai, Yang, Argyris Oikonomou, and Weiqiang Zheng. "Tight last-iterate convergence of the extragradient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities." arXiv preprint arXiv:2204.09228 (2022).

Q: I do not understand why the last-iterate property is important. The convergence results can still be obtained by averaging the outputs of iterative OLO-based algorithms (such as Hedge). Maybe a more important issue is the speed itself, not whether the property holds or not.

A: We can average the iterates and get convergence results. However, last-iterate convergence is still important from both theoretical and practical point of view, as we have motivated in the introduction of the paper. If we view learning as a model of agents’ strategic behavior, then only the last-iterate convergence of learning dynamics guarantees that agents’ strategies (day-to-day behavior) stabilize at Nash equilibrium. Learning dynamics with only average-iterate convergence is unstable and exhibits cycling and divergence behavior. For example, the Hedge algorithm does not converge in last-iterate even for simple zero-sum games [8]. The problem of understanding last-iterate convergence for learning in games has received extensive attention in recent years, see e.g [9, 10, 11, 12, 13] and more references therein. Last-iterate is widely used in practice for simplicity. In some cases, iterate averaging can be cumbersome and even impractical when neural networks are involved. Thus it is crucial to develop theoretical tools to understand last-iterate convergence of learning algorithms.

Q: Are the analyses for the last iterate property useful for constructing a new online-to-batch conversion technique (e.g., averaging all outputs of OCO algorithms)?

A: We think the online-to-batch technique is not related to last-iterate convergence. This is because online convex optimization is a single-agent learning problem, where the goal is to minimize regret against an adversary; while learning in games is a multi-agent learning problem and the goal is to prove last-iterate convergence to Nash equilibrium. The following examples further illustrate the differences between regret minimization and last-iterate convergence in games.

1. The Extragradient (EG) algorithm suffers linear regret [11] in OCO but when both players employ EG in a zero-sum game, their joint strategy converges to a Nash equilibrium [13].
2. The online gradient descent (OGD) algorithm is a no-regret online algorithm but when both players employ OGD in a zero-sum game, their joint strategy diverges from Nash equilibrium [8].

[8] Mertikopoulos, Panayotis, Christos Papadimitriou, and Georgios Piliouras. "Cycles in adversarial regularized learning." SODA, 2018

[9] Daskalakis, Constantinos, and Ioannis Panageas. "Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization." ITCS, 2019

[10] Lin, T., Zhou, Z., Mertikopoulos, P., & Jordan, M. I.. Finite-time last-iterate convergence for multi-agent learning in games. ICML 2020.

[11] Golowich, N., Pattathil, S., & Daskalakis, C. Tight last-iterate convergence rates for no-regret learning in multi-player games. NeurIPS, 2020

[12] Wei, C. Y., Lee, C. W., Zhang, M., & Luo, H. Linear Last-iterate Convergence in Constrained Saddle-point Optimization. ICLR, 2021

[13] Cai, Y., , Oikonomou, A., Zheng W. Finite-Time Last-Iterate Convergence for Learning in Multiplayer Games. NeurIPS 2022

Q: The min-max game itself is known to be an LP and thus solved in polynomial time. Iterative algorithms are one of the approaches to solving the LPs. The paper should consider comparing the state-of-the-art LP solvers with iterative algorithms. Although iterative algorithms are easy to implement, practical LP solvers have been improved for a long time and could be faster than naive iterative algorithms.

A: Thanks for your comment! The focus on iterative algorithms like Regret Matching (RM), RM+ and their variants over Linear Programming (LP) methods is driven by two reasons.

One of our motivations to study RM and its variants is that they are simple online learning algorithms, and understanding the convergence properties of uncoupled learning dynamics in games is an important question at the intersection of machine learning and game theory. In a multi-agent learning scenario, agents interact with each other and update their strategies in their own interest. Existence of simple learning dynamics that converge to Nash equilibrium in a day-to-day sense (i.e. in last iterate) provide stability guarantees for multi-agent systems, and provide some justification for using Nash equilibrium to predict the outcome of real-life multi-agent interactions. Prior to our work, the literature had focused on the behavior of optimistic variants of FTRL and OMD. Yet RM-type algorithms are very simple, and have a history of performing well in practice (more on that in the next paragraph), and thus their last-iterate convergence behavior is of interest in its own right.

Our study is also motivated by the strong practical performance of RM-type iterative algorithms, especially in the context of large-scale extensive-form games. While LP methods might offer advantages in smaller games, their application becomes less feasible in larger, more complex scenarios. This is evident from the historical context: the last notable application of LP for offline two-player zero-sum games was in 2005, which successfully solved Rhode Island Hold’em [1, 2]. However, the practicality of LP diminishes as the game size increases. The size of LP formulations is linear in the game tree size, making the use of simplex or Interior Point Method (IPM) iterations extremely slow for larger games. Since 2007, there has been a significant shift in the field towards using iterative algorithms like Counterfactual Regret Minimization (CFR) [3], dilated Entropy-regularized algorithms such as excessive gap technique (EGT) and CFR+ [4]. We remark that CFR and CFR+ build upon RM and RM+, respectively. Every superhuman poker AI developed since then has utilized CFR+ [5, 6, 7]. Despite their strong practical performance in large-scale games, RM-type algorithms are not well-understood theoretically, which motivates our study.

[1] Gilpin, Andrew, and Tuomas Sandholm. “Optimal Rhode Island Hold’em Poker.” AAAI, 2005

[2] Gilpin, Andrew, and Tuomas Sandholm. "Lossless abstraction of imperfect information games." Journal of the ACM, 2007

[3] Zinkevich, M., Johanson, M., Bowling, M., Piccione, C. Regret minimization in games with incomplete information. NeurIPS, 2007

[4] Tammelin, Oskari. "Solving large imperfect information games using CFR+." 2014

[5] Bowling, M., Burch, N., Johanson, M., & Tammelin, O. Heads-up limit hold’em poker is solved. Science, 2015

[6] Brown, Noam, and Tuomas Sandholm. "Superhuman AI for heads-up no-limit poker: Libratus beats top professionals." Science, 2018

[7] Brown, Noam, and Tuomas Sandholm. "Superhuman AI for multiplayer poker." Science, 2019

Thanks for your reivew and we address your questions below.

Q: Can you clarify the comments at the bottom of page 5? It is not clear to me why your setting is not a monotone game setting?

A: Our results do not follow from the referenced analysis of EG and OG [2]. We will clarify the misunderstanding below. First, monotonicity is defined on an operator. In the literature, a game is called monotone if its gradient operator is monotone: a zero-sum game is a monotone game because its gradient operator $F_G(z) := (Ay, -A^Tx)$ is a monotone operator (i.e., it satisfies $\langle F_G(z)- F_G(z’), z-z’ \rangle \ge 0$ for all $z, z’ \in \Delta^{d_1} \times \Delta^{d_2}$). We can run EG and OG regardless of the monotonicity of the operator. The paper [2] shows that when the operator is monotone, EG and OG have last-iterate convergence rates, which is also acknowledged in the current paper (page 5, bullet point 2).

However, the algorithms ExRM+ and SPRM+ (proposed by a recent paper [1]) studied in this paper are regret matching-type algorithms. ExRM+ and SPRM+ are equivalent to running EG and OG using the regret operator $F(z) := (Ay - x^T A y \cdot 1_{d_1} , -A^Tx + x^T A y \cdot 1_{d_2})$ over a lifted space $Z_{\ge}$ (F is defined in equation (2) in the paper). The regret operator $F$ is not monotone over $Z_{\ge}$. That is why we can not derive last-iterate convergence rates for ExRM+ or SPRM+ by existing results in [2]. The non-monotonicity of the regret operator also partly explains why last-iterate convergence of regret matching-type algorithms are poorly understood before.

Q: Can you explain why the restarted variants of your algorithms converge faster?

A: The short answer is that they may not converge faster. We prove sublinear $1/\sqrt{t}$ best-iterate convergence rates of ExRM+ and SPRM+ and linear last-iterate convergence of restarted variants of ExRM+ and SPRM+. But our experiments show that restarting does not significantly affects the last-iterate convergence speed of ExRM+ and SPRM+ (see Appendix E.2). Thus we conjecture that ExRM+ and SPRM+ without restarting already have linear last-iterate convergence. It would be very interesting to investigate this problem in the future.

[1] Regret Matching+: (In)Stability and Fast Convergence in Games. Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, and Haipeng Luo. NeurIPS 2023

[2] Finite-Time Last-Iterate Convergence for Learning in Multiplayer Games. Yang Cai, Argyris Oikonomou, Weiqiang Zheng. NeurIPS 2022

Thank you for your comment. We address you questions below.

Q1: In what way is Algorithm 1 (RM+) different from the classical algorithm of Hart and Mas-Colell (2000), who coined the term and introduced this class of algorithms 25 years ago? Is the algorithm of Tammelin (2014) different? If so, in what sense?

A: The classical algorithm of [1] is called Regret Matching (RM), while [2] proposes a variant of RM, called RM+. RM and RM+ are different and we provide their update rule below. The difference between RM and RM+ is that in each iteration, after observing a new utility, RM+ projects the cumulative regret $R^t$ onto the positive orthant, while RM does not perform such projections. As a result, the output strategy of RM+ is simply the $\ell_1$-normalization of $R^t$, while the output strategy of RM is to apply $\ell_1$-normalization only to positive coordinates of $R^t$.

For the sake of clarity, we recall the update rule of RM and RM+ (for the $x$ player). Here we define $f(x, Ay) = Ay - x^T A y 1_{d_1}$ and $[ \cdot ]^+$ the projection operator onto the positive orthant.

RM: $R^{t+1}_x = R^t_x - f(x^t, A y^t)$ and $x^{t+1} = [R^{t+1}]^+/ ||[R^{t+1}]^+ ||_1$;

RM$^+$ :$R^{t+1}_x = [R^t_x - f(x^t, A y^t)]^+$ and $x^{t+1} = R^{t+1} / ||R^{t+1}||_1$.

Q2: I am perplexed by Theorem 1. If I'm not mistaken, RM+ is simply projected descent on the operator $F$ defined in (2). Since $z^*$ is strict, $F$ satisfies the strict version of the Minty inequality of Fact 1, so the theorem would seem to follow from classical results in the VI literature - I'm thinking of the Facchinei-Pang textbook, but this result is likely more classical.

A: For RM+, the regret operator $F$ is defined on the whole positive orthant $R_{+}^n$ and is not a Lipschitz operator on $R_{+}^n$ [3]. This is because we transform a point $z \in R_{+}^{n}$ back to $(x ,y)$ in the simplex to calculate the regret. Lack of Lipschitzness is the reason why Theorem 1 may not follow from classical results. We remark that for ExRM+ and SPRM+, the regret operator $F$ is restricted to the clipped positive orthant, which we denote as $\Delta_{\geq}$ in the paper, and $F$ is Lipschitz on $\Delta_{\geq}$.

Q3: Lemma 12.1.10 of Facchinei-Pang indeed concerns pseudomonotone operators. However, from the very first line of its proof, it is clear that it only requires $z^{\star}$ to be a solution to a Minty inequality. In view of this, how is Theorem 2 different from the standard result for extra-gradient applied to $F$?

A: This is a great question! Lemma 12.1.10 of [FP03] indeed only requires $z^*$ to be a solution to a Minty inequality and that is why in the paper we say Lemma 1 is adapted from Lemma 12.1.10 in [FP03]. However, the convergence of EG in Theorem 12.1.11 [FP03] does require $F$ to be pseudomonotone with respect to the whole solution set (that is, for any $z^* \in SOL(Z, F)$, it holds that $\langle F(z), z -z^* \rangle \ge 0$ for all $z \in Z$). However, the regret operator $F$ defined in equation (2) does not satisfy this condition for the entire solution set (see an example below), and therefore Theorem 2 does not follow from Theorem 12.1.11 in [FP03]. To prove Theorem 2, we first characterize the limit points of the dynamics (Lemma 3) and then combine it with the interchangeability property of Nash equilibria in two-player zero-sum games.

Example: Let us consider the game with matrix $[[3,1], [4,5]]$ whose unique Nash equilibrium is $z^*=[x^* = [1, 0], y^* = [1,0]]$. Consider any solution $z’ = (a x^*, b y^*)$ with $1 \le a < b/4$. Let $z = [x = [0, 1], y = [0,1]]$, then we can check $\langle F(z), z - z’ \rangle = 4a- b < 0$. Thus $F$ is not pseudomonotone with respect to the whole solution set $SOL(\Delta_{\ge}, F)$.

Thanks for mentioning this. We will add this discussion in the revised manuscript.

Q4: A conceptual question: since the regret does not appear at all in ExRM+, in what sense is it a "regret-matching" algorithm?

A: The operator $F$ defined in equation (2) is the regret operator, which is the same as RM and RM+. Specifically, the regret operator is defined as $F(z) = F((Rx, Qy)) = [f(x, Ay), f(y, -A^T x)] = [Ay - x^T Ay \cdot 1_{d_1}, -A^T x + x^T Ay \cdot 1_{d_2}]$ for all $z \in R_{+}^{d_1 + d_2}$.

References

[1] Hart, Sergiu, and Andreu Mas‐Colell. "A simple adaptive procedure leading to correlated equilibrium." Econometrica, 2000

[2] Tammelin, Oskari. "Solving large imperfect information games using CFR+." 2014

[3] Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, and Haipeng Luo. Regret Matching+: (In)Stability and Fast Convergence in Games. NeurIPS 2023

[FP03] Facchinei, Francisco, and Jong-Shi Pang. Finite-dimensional variational inequalities and complementarity problems. 2003

Q1: If I'm not mistaken, the field of applications of RM+ concerns primarily extensive-form games, does it not? However, your paper concerns normal-form games, so my question stands: what is the concrete benefit of using RM+ over RM in a normal form game? And, if ExtraRM+ is not regret-minimizing, what is the benefit of using ExtraRM+ over "vanilla" extra-gradient gradient methods that are regret-minimizing?

A: Here we provide one advantage of RM+ over RM. RM corresponds to the lazy version of OGD while RM+ corresponds to the more standard agile version [FKS21]. While RM+ does not exactly "match regret", it in a sense matches something even better. For RM+, the maintained $R^t_{i}$ is not only an upper bound on the regret to action $i$ from round 1 to $t$, but also an upper bound on the regret from round $s$ to $t$ for any $s \le t$. In other words, RM+ provides a regret guarantee for any interval (the so-called adaptive regret guarantee by [HS07]). Our ultimate goal is to analyze RM+ for EFGs. But as the first step, we must understand the performance of RM+ for NFGs, a special case of EFGs. Note also that even in NFGs, RM+ performs better than RM (see e.g. these lecture notes, Figure 3). Providing further results for RM / RM+ in EFGs is an interesting future direction.

We clarify that neither ExRM+ or extra-gradient (EG) is a regret minimization algorithm (See [GPD20 Appendix A.3 Proposition 10] for an example where EG suffers linear regret). But when both players run EG/ExRM+ in a two-player zero-sum game, each player’s regret vanishes and the dynamics converges to a Nash equilibrium. Moreover, we remark that the SPRM+ algorithm we analyze is a regret minimization algorithm.

[HS07] Hazan, Elad, and Comandur Seshadhri. "Efficient learning algorithms for changing environments." ICML, 2007

[FKS21] Farina, Gabriele, Christian Kroer, Tuomas Sandholm. "Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent." AAAI, 2021

[GPD20] Golowich, Noah, Sarath Pattathil, and Constantinos Daskalakis. "Tight last-iterate convergence rates for no-regret learning in multi-player games." NeurIPS, 2020

Q2: Regarding $F$: I am looking at the definition (2) of your paper - and, in particular, the second equality. Either there is (yet) another typo on the definition, or I don't understand how a function of the form $xAy$ is "badly behaved" at the origin.

A: There is no typo. Let us clarify again why $F$ is not Lipschitz over the positive orthant.

1. The definition of $F$ over the positive orthant $R_{+}^{d_1 + d_2}$ is as follows (the same as equation (2)): For a point $z \in R_{+}^{d_1 + d_2}$, we can always write it as $z = (Rx, Qy)$ where the $\ell_1$-norm $1^T x= 1^Ty = 1$ (so $(x, y) \in \Delta^{d_1} \times \Delta^{d_2}$ are strategies in the simplex). The operator $F$ is defined as $F(z) = F((Rx, Qy)) = [ f(x, Ay), f(y, -A^T x) ] = [Ay - x^T A y 1_{d_1}, -A^T x + x^T A y 1_{d_2}].$ Note that the argument of $F$ is not $(x,y)$, but $z$, so $xAy$ being nicely behaved does not imply $F$ being Lipschitz with respect to $z$.
2. Now it is clear that if two points $z, z’$ are very close to the origin, then $||z -z’||$ can be arbitrarily small. However, since the operator $F$ calculates regret by mapping $z = (Rx, Qy)$ back to $(x, y)$ in the simplex $\Delta^{d_1} \times \Delta^{d_2}$, the term $||F(z) - F(z’)||$ can be large. This is why $F$ is not Lipschitz over the positive orthant.
3. If we clip the origin and restrict $F$ on the clipped positive orthant $Z_{\ge}$, then $F$ is Lipschitz over the clipped positive orthant $Z_{\ge}$.