Regret Matching+: (In)Stability and Fast Convergence in Games
Authors: Gabriele Farina
Julien Grand-Clément
Christian Kroer
Chung-Wei Lee
Haipeng Luo
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Regret Matching
Predictive algorithms
Extensive-Form Games

Abstract: Regret Matching$^+$ (RM$^+$) and its variants are important algorithms for solving large-scale games.
However, a theoretical understanding of their success in practice is still a mystery.
Moreover, recent advances on fast convergence in games are limited to no-regret algorithms such as online mirror descent, which satisfy stability.
In this paper, we first give counterexamples showing that RM+ and its predictive version can be unstable, which might cause other players to suffer large regret. 
We then provide two fixes: restarting and chopping off the positive orthant that RM$^+$ works in.
We show that these fixes are sufficient to get $O(T^{1/4})$ individual regret and $O(1)$ social regret in normal-form games via RM$^+$ with predictions.
We also apply our stabilizing techniques to clairvoyant updates in the uncoupled learning setting for RM$^+$ and prove desirable results akin to recent works for Clairvoyant online mirror descent. 
Our experiments show the advantages of our algorithms over vanilla RM$^+$-based algorithms in matrix and extensive-form games.

Regret Matching (In)Stability and Fast Convergence in Games
Gabriele Farina MIT g gfarina@mit.cmm edu
Julien Grand-Clément ISOM, HEC Paris grand-clement@hec.. fr
Christian Kroer IEOR, Columbia University
Chung-Wir Wei Lee Department of Computer Science University of Southern California
christian, www.erooleubleeeeee....oo edu
Leechung@usc.edt
Haipeng Luo
Department of Computer Science University of Southern California haipeng @usc.edu
Abstract
Regret Matching (RM+) and its variants are important algorithms for solving large-scale games [35]. However, theoretical understanding their success practice is still mystery. Moreover, recent advances [34] on fast convergence in games are limited to no-regret algorithms such as online mirror descent, which satisfy stability. In this paper, we first give counterexamples showing that RM+ and its predictive version [12] can be unstable, which might cause other players suffer large regret. We then provide two fixes: restarting and chopping off the positive orthant that RM* operates in. Combined with RM* with predictions, we show that restarting is sufficient to get O(T1/1) individual regret and that chop- ping off achieves O(1) social regret in normal-form games. We also apply stabilizing techniques to clairvoyant updates in the uncoupled learning setting for RM+ introduced Extragradient RM and prove desirable results akin to recent works for Clairvoyant online mirror descent [31, 14]. Our experiments show the advantages of our algorithms over vanilla extensive-form games.
algorithms in matrix and
Introduction
Regret minimization is an important framework for solving games. Its connection to game theory provides practically efficient way approximate game- theoretic equilibria [16, 19]. Moreover, provides a scaleable way to solve large-scale sequential games, for example using the Counterfactual Regret Minimization (CFR) decomposition [37]. Consequently, regret minimization algorithms are a central component in recent superhuman poker AIs [2, 28, 3]. Regret Matching (RM+) ) [35] the most prevalent regret minimizer in these applications. In theory, guarantees an O(1/VT) convergence rate after I' iterations, but its practical performance is usually significantly faster.
On the other hand, a line of recent works show that regret minimizers based on follow the regular- ized leader (FTRL) online mirror descent (OMD) enjoy faster convergence rates in theory when combined with the concept of oppimissmprrddictiveness [32, 34]. The result was originally proven
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Algorithms
Social regret in multi-player NFGs
RM+ [19]
O (T
Predictive RM* [10]
0 (T
Stable Predictive RM (Alg. 1)
0 (T
Smooth Predictive RM+ (Alg. 2)
0(1)
Conceptual RM+ (Alg. 3)
0(1)
Approximate Conceptual RM* (Alg. with log(T))
0(1)
Extragradient RM* (Alg. 5)
0(1)
Table I: Summary of regret guarantees for the algorithms studied in this paper. The constants hidden
in the O()) notations depends on initialization and the dimensions of the games and are given in our theorems.
in matrix games [32]. and later extended to multiplayer normal-form games [34, 6, 7], extensive- form games [8, 10, 15, 1]. and general convex games [22, 13]. However, despite their favorable properties in theory, optimistic algorithms based on FTRL/OMD are usually numerically inferior to RM* when applied to solving large-scale sequential games. It remains mystery whether some optimistic variant of RM+ enjoys a theoretically faster convergence rate, considering the strong em- pirical performance of RM+ It is also an open question whether there exists algorithm that has both favorable theoretical guarantees similar to FTRL/OMD algorithms and practical performance comparable RM+ Inspired by recent work on the connection between OMD and RM+ [12), provide new insights on the theoretical and empirical behavior of RM+-ba algorithms, and we show that the analysis of fast convergence for OMD can be extended RM+ with some simple modifications to the algorithm. Specifically, our main contributions can be summarized as follows.
1. We provide a detailed theoretical and empirical analysis of the potential for slow performance of RM+ and predictive RM We start by showing that, in stark contrast to FTRL/OMD al- gorithmms that are stable inherently, there exist loss sequences that make RM+ and its variants unstable, leading to cycling between very different strategies. The key reason for such insta- bility is that the decisions of these algorithms are chosen by normalizing an aggregate payoff vector; thus, in a region close to the origin, two consecutive aggregate payoffs may point in very different directions, despite being close, resulting in unstable iterations. Surprisingly, note that this can only happen when the aggregate payoff vectors, which essentially measure the algorithm's 's regret against each action, are small, so instability can only happen when one's s regret is small and thus is seemingly not an issue. However, in a game setting, such instability might cause other players to suffer large regret because they have to learn in unpredictable environment. Indeed, we identify a 3 x 3 matrix game where this is the case and both RM+ and predictive RM* converge slowly at rate of O(I/VT) (Fig. 1). We emphasize that very little is known about the properties of (predictive) RM+ and we are the first to show concrete examples of stability issues in matrix games and in the adversarial setting.
2. Motivated by our counterexamples, we propose two methods to stabilize RM+ restarting, which reinitializes the algorithms when the aggregate payoff's are all below threshold, and chopping off the origin from the nonnegative orthant to smooth the algorithms. When apply- ing these techniques to online learning with RM+, we show improved regret and fast con- vergence similar to predictive OMD: we obtain ((T1/4) individual regrets for Stable Predic- tive RM+ (which uses restarting) and 0(1) social regret for Smooth Predictive RM+ (which chops off the origin). We also consider conceptual prox and extragradient versions of RM+ for normal-form games. We show that our stabilizing ideas also provide the required stabil- ity in these settings and thus give strong theoretical guarantees: Conceptual RM+ achieves O(1) individual regrets (Theorem 5.3) while Extragradient RM+ achieves ((1) social regret (Theorem 5.6). See Table for summary of our results for normal-form games. We further extend Conceptual RM+ to extensive-for games (EFG), yiclding ((1) regret in iterations with OTT lTg( gradient computation. The key step here is to show the Lipschitzness of the CFR decomposition (Lemma J.1).
3. We apply our algorithms to solve matrix games and EFGs. For the matrix game in- stability counterexample, our algorithms indeed perform significantly better than (predictive)

---

RM For random matrix games, we find that Stable and Smooth Predictive RM* have very strong empirical performance, on par with (unstabilized) Predictive RM*, and greatly out- performing RM+ in all our experiments; Extragradient RM+ appears to be more sensitive to the choice of step sizes and sometimes performs only as well as RM Our experiments on 4 different EFGs show that our implementation of clairvoyant CFR outperforms predictive CFR in some, but not all, instances.
2 Preliminaries
Notations. For d E N, we write 1a E Rd the vector with 1 on every component. The simplex of dimension 1 is A {ar E IR4 (a, 1d) = 1]. The vector has on every component and its dimension is implicit. For z E R, we write [x]* for the positive part of æ [x] max(0, 2), and we overload this notation to vectors component-wise. For two vectors a and b, 2 b means is at least b component-wisg We write || |]. for the dual norm of norm -|--
Online Linear Minimization, In online linear minimization, at every decision period / 2 1, an algorithm chooses decision x' from a convex decision set X. A loss vector Le is chosen arbitrarily and an instantaneous loss of (e", æ²) is incurred. The regret of an algorithm generating the sequence of decisions x² ..... x is defined as the difference between the cumulative loss generated and that of any fixed strategy & Xt: Reg" (œ) E'= (e', x² at.
regrel minimizer guarantees that
Reg" (Ø) ) o(T) for any ă E X.
Online Mirror Descent. A famous regret minimizer is Online Mirror Descent (OMD) [30], which generates the decisions x² ,..,,""' as follows (with a learning rate > 0):
x+1 -Iaxxx (nl*)
(OMD)
where for any a X, and any loss l, the proximal operator é ll,,x(e) is defined as x ( arg mingex (,, + D( x) where D is the Bregman divergence associated with o + IR, a 1-strongly convex regularizer (with respect to some norm || |]): (
( - (x)) (V x),V å, x E X. OMD guarantees that the worst-case regret against any & grows O(VT) (omitting other dependence for simplicity; the same below). Other popular regret minimizers include Follow- The-Rehueeeeeeeeeeeeeeeee ReegeReaizzed-Leeeeee
(FTRL), and adaptive variants of OMD and FTRL; refer the reader to [20] for an extensive survey on regret minimizers.
Regret Matching and Regret Matching*. + Regret Matching (RM) and Regret Matching (RM+)
are two regret minimizers that achieve (VVT) worst-case regret when X Ad, RM [19] maintains Rgla. and for t 2 1, R
a sequence of aggregate payoffs R
121
x²
R
R Ih,
R - (x' (x',
where Ro 2 O specifies an initial point and 0/0 is defined as the uniform distribution for conve- making the algorithm completely parameter-free, very
nience. The original RM sets Ro appealing property in practice. RM- is a simple variation of RM, where the aggregate payoffs are thresholded at every iteration [35]. In particular, RM+ only keeps track of the non-negative components of the aggregate payoff's to compute decision: R = Rold, and for t 2 1,
x' ='=R'/10 |
R
R
+ (x'
( 1. -1)
We highlight that very little is known about the theoretical properties of RM+ despite its strong em- pirical performances: [36] show that RM+ is a regret minimizer (and enjoys the stronger K K-tracking regret property), and [4] show that it can safely be combined with alternation ([18) prove strict im- provement when using alternation), Farina et al. [12] show an interesting connection between RM* and Online Mirror Descent: the update R R + - la
etI+ of RM+ can be rewritten (xx e
as
R²+1 = -R (nf(x',e))
for X RC 111 1, and f(x', defined as f(x ( (x", (e) La. Therefore,
RM+ generating sequence of decisions x -.. facing sequence of losses (e') (2)))>) is closely connected to OMD instantiated with the non-negative orthant the decision set and facing
quence of losses (f (x'((())))))) (2)))21- We have the following relation for the regret in x "....., x
and the
regret in R .... Rd (the proof follows [12] and is deferred to the appendix).
3

---

Lemma 2.1. Let x², x'...., x!..."" E A be generated as x' = R R'/1 for some sequence
R'..... R E RQ.. The regret Reg' (a) of x' a'....,'' facing sequence of losses l, e.,..., l. is equal
to (R)" the regret of R', ..... R" facing the sequence of losses f (a) .e) ..... ... f (z ,T),
compared against R = x: Reg' T R Ei= (f (x),))), R)
Since OMD is regret minimizer guaranteeing Reg" (R) = O(vT), Lemma 2.1 directly shows that RM is also regret minimizer: Reg" (Φ) - O(vT).
Multiplayer Normal-Form Games, In multiplayer normal-form game, there are n E N players. Each player has d; strategies and their decision space A is the probability simplex over the d; strategies. We denote A x== A de the joint decision space of all players and d = d1 +.....+ dn. The utility function for player is concave function
A + [-1, 1] that maps every joint strategy profile x = (21, ...; v..) E A to a payoff. We assume bounded gradients and T,,-smoothness for the utilities of the players: there exists B,, > 0, T. > O such that for any F. x' E A and any player i,
VV,, S Bu, Va, (xx) Va, (xx))22 S I.u ||: x z'122-
(1)
The function mapping joint strategies to negative payoff gradients for all players is vector-valuee
function A + Rd such that G(x)) = --Va Ve, u1 (z).... ................................ Vv_ un (z)). It is well known that running a regret minimizer for (æf.-.., 21, E leads to strong theerehc guarantees (c.g., the average iterate being an approximate coarse cor- related equilibrium). However, in light of Lemma 2.1, we will instead perform regret minimization on (R. .... R X x x,=1 R with the losses (f(x), fi)....... f( ())). For conciseness, we thus define the operator F X -> TRd as, for 2 (RI.... Rn), F(z)= (f(11, (1), f (xx,, where z; R R. |I V = I,.... n, (4)))E()) = G(z).
x ==1 A facing the loss G(æ²) (ei ........0 e
Predictive OMD and Its RVU Bounds. The predictive version of OMD proceeds as follows:
x²
aTxx (1m²))
a -T (1)²*
When setting m = -0- C'-1, predictive OMD satisfies Reg" (.) D(a,a") By Ex=1 || This regret bound satisfies the RVU (regret bounded by variation in utilities) condition, introduced [34]. The authors show that this type of bound guarantees that the social regret (i.c., sum of the regrets of all players) is O(1) when all players apply this special instance of predictive OMD. Syrgkanis et al. [34] further prove that each player has improved O(T4/4) individual regret by the stability of predictive OMD. Specifically, they show that predictive OMD guarantees ||x++11 x'| = O(1) against any adversarial loss sequence, i.c., the algorithm is stable the sense that the change in the iterates can be controlled by choosing r) appropriately.
+ I 26-11-
"
Predictive RM* + Similar to OMD, we can generalize RM to Predictive Regret Matching*[11 define R¹ m Rola (with Ro by default), and for / 2 1,
x' = R' R' for R = [ + m']+, R++1 R f(x', [ for f(x', ,4") ll - (x", ee) 1a.
We call the algorithm predictive RM* (PRM*) when m ff((='''' - and it recovers RM+ when m = O. A regret bound with a similar RVU condition is attainable for predictive RM+ by its connection predictive OMD [12], but only in the non-negative orthant space instead of the actual strategy space. To make connection between them, stability is required as we show later. A natural question is then whether (predictive) RM+ is also always stable. We show that the answer is no by giving an adversarial example in the next section.
3 Instability of (Predictive) Regret Matching*
We start by showing that there exist adversarial loss sequences that lead to instability for both RM+ and predictive RM+ Our construction starts with an unbounded loss sequence L so that x' alternates between 1/2,1/2) and (0, 1): we set Lt = (e*, where E 2, and for / 2 2, ge -2(-)))) if is even and l 2(t-1)/2 if is odd. Our proof is completed by normalizing the losses to [-1, given fixed time horizon (see Appendix B for details).

---

-
Regret plapyay))
0.06
RM
10"
lincar lit
Noon
0.04
Regret
Duality soip
10"2
0.02
10'4
100
10
10
107
10
10P
10
10
10"
10
fserations (out 10")
Number of Sterations
Number iterations.
10
+-
Regret (y-player)
PRM
10
10"1
lincar
Duilty gap
Norn
Regnet
70-2
10
10"1
10
108
10
10P
100
10*
10
10P
102
10'
10P
10a
10"
10P
10"
107
Last 100 iterations (out ot 10")
Number of iterations
Number of ieerations
Left plots show the iterate-to-iterate variation in the last 100 iterates of predictive RM Center plots show the regret for the x and y players under predictive RM Right plots show empirical convergence speed of RM* (top row) and Predictive RM* (bottom row).
Figure 1:
Theorem 3.1. There exist fiite sequences of losses in R2 for RM+ and its predictive version such that x² = (2 1) when t is odd and x' = (0,1) when t is even.
This is in stark contrast to OMD which always ensures || - x'1| = O(n) and is thus inherently stable. However, somewhat surprising property about (predictive) RM+ + is that instability actually implies low regret. To see this, we first present the following Lipschitz property of the normalization function g x + x ||=]| for E TR..
Proposition Let a. y E IR4, with 1T 1. Then, ll g()) S vd. 11 2112-
This proposition shows that the normalization step has reasonable Lipschitz constant (Vd) as long as its input is not too close to the origin, which further implies the following corollary.
Corollary 3.2. RM+ with | 2 Ro satisfies ||a:+11
R++1
||,
2d8
Ro
Put differently, the corollary states that instability can happen only when the cumulative regret vector R' is small. For example, if || xx|| 12(1). then we must have | Odd and thus the regret at that point at most (ddB,). similar argument holds for predictive RM* as well.
Therefore, instability is in fact not an issue for these algorithms' own regret.
However, when using these algorithms play game, what could happen that such instabil- ity leads to other players learning in an unpredictable environment with large regret. We show this phenomenon via an example of 3 matrix game max min (zz Ay). where A (33 3), 30, 4)), (0, O, 1)). The first column of Fig. shows the squared la norm of the consecutive difference of the last 100 iterates of Predictive RM for the x player (top) and the player (bottom). The iterates of the x player are rapidly changing iterates of the y player are stable with changes on the order of 10 In the center plots where we show the individual regret for each player, player is near zero as implied by instability, but it causes large regret (close to 7.5 empirically) for the y player. (We show the same plots for RM+ in Fig. in Appendix B; there, the iterates of both players are stable, but since RM+ lacks predictivity, it still leads to larger regret for one player.)
periodic fashion while the
indeed observe that the cumulative regret of the
The right column of Fig. shows the duality gap achieved by the linear average (T), 2 T(T+I Σt= lax" T[T+ Ei= 19y). when the iterates are generated by RM+ with alternation
2
(top) and predictive RM+ (bottom). For both algorithms the convergence rate slows down around 10a iterations. linear regression estimate on the rate for the last 10 iterates shows rates of -0.497 and -0.496 for RM- and predictive RM+ respectively. To the best of our knowledge, this is the
5

---

first known case of empirical convergence rates on the order of T.5 for either RM* predictive RM"; the worst prior instance for RM was T in Farina et al. [10]; no hard instance was known for predictive RM*
4 Stabilizing RM and Predictive RM
Based on the discussions in the previous section, we aim make every player stable despite the fact that being an unstable player may actually be good for that particular player. By Corollary 3.2, it suffices make sure that [| is never too small. We provide two approaches to ensure this property and thereby stabilize (predictive) RM
Stable Predictive RM One way to maintain the required distance to the origin is via restarting: We initialize the algorithm with the cumulative regret vector equal to some non-zero amount, instead of the usual initialization zero. Then, when the cumulative regret vector gets below the initial- ization point, we restart the algorithm from the initialization point. Applying this idea to predictive Player starts with R Rgld, runs predictive RM* and restarts
RM* yields Algorithm whenever R < Ro l.. In the algorithm we write [ .,,,,., R2, compactly as w (similarly for z"). Note, though, that the updates are decentralized for each player, in vanilla predictive RM+
Given this modification, Stable PRM t achieves improved individual regret in multiplayer games, as stated in Theorem 4.1. We defer the proof to the appendix. One key step in the analysis is to note that by definition, the regret against any action is negative when the restarting event happens, so is sufficient to consider the regret starting from the last restart. Thanks to the stability enforced by the restarts, the regret from the last restart also well controlled and the results follow by tuning and Ro optimally. In fact, since the algorithm is scale-invarian up to the relative scale of the two parameters, it is without loss generality to always set R = 1.
Algorithm Stable Predictive RM*
Algorithm 2 Smooth Predictive RM*
1: Input: Rg O, step size 0
1: Input: Step size >> 0
2: Initialization: w Rgla
2: Initialization: w E Xzz
3: for 1...., T do
3: for t 1...., T do
4: x' -I (1)²²
4: x² = -1,2' (nm²)
5: w² = 1o 1.x (2))
5: w² = II 1,8, (1)((2))
6: (æf....., .......... xxh)
6: (of...., x²1) (g(2))....,g( (x(())
....)........
7: for 1,... do
8: uo < Rold. then
9:
wi Rold.
Theorem 4.1. Let = (dTT) and Ro = 1. Let (f) = F(x*) for 2 1. For each player set the sequence of predictions m when O or restart happens at t 1; otherwise, m f!-1.y N 1. Then Algorithu guarantees that the individual regret Reg] (+.) = -in VV., (x"=)")),)))) L; x²) of each player i is bounded by O (42/2T1144 in multi- player normal-form games.
Although the restarting idea successfully stabilizes the RM algorithm, the discontinuity created by asynchronous restarts causes technical difficulty for bounding the social regret by O(1). Next we introduce an alternative stabilization idea fix this issue.
Smooth Predictive RM+ Our second stabilization idea is to restrict the decision space to a subset where we "chop of the area that is too close to the origin, that is, project the vector R the set A (R R4:
|| | 2 1). We denote the joint chopped-off decision space as X² x A We call the resulting algorithm smooth predictive RM+ (Algorithm 2). Besides a similar result to Theorem 4.1 the individual regret (omitted for simplicity), Algorithm 2 also guarantees that the social regret is bounded by game-depender constant, as shown in Theorem 4.2.
(2v2(n- 1) max;(d) (12/2)) (oxx(( Using the sequence of predic-
Theorem 4.2. Let 1 tions m m F(2'-1), t 2 1. Algorithm 2 guarantees that the

---

Algorithm 3 Conceptual RM+
Algorithm 4 Conceptual RM+ with approximate fixed-point
1: Input: Step size y) with yf 1/LF
2: Initialization: z E 2
1: Input: Step size > with < 1/LF
3: for 1,... T do
2: Initialization: 2 X²
4: z² 11, (1)((²))
3: for / 1, 1,...? T do
4: w z'-1
5: (ff,..... ,1h))
5: for = 0....,k do
6: w --11--11,0 X2 (nF(wi))
7:
= 11 ,2 (n](w*))
8:
(of..... x²n) ((. g(w
cial
regrel
E Reg (2:)
E==1 Et= (V
m; (a("""; a; ad) is upper bounded by {|/2 0:13] in multiplayer normal-form games.
2 max 0
12/2 max;=1,....
Algorithm 2 dominates Algorithm in terms of our theoretical results so far, but it has one drawback: requires occasional projection onto Xs. In Appendix we show that this can be done with a sorting trick in Odd d) time, whereas the restarting procedure is implementable in linear time.
5 Conceptual Regret Matching*
In this section, we depart from the predictive OMD framework and develop new smooth variants of RM+ from a different angle. Instead of using predictive OMD to compute the iterates (R)) we consider the following regret minimizer that we call cheating OMD, defined for some arbitrary
closed decision set 2 and an arbitrary sequence of losses (Z') x¹ -T ., (nll) for 2 1, and n0 E Xz. Cheating OMD inspired by the Conceptual Prox method for solving variational inequalities associated with monotone operators [5, 23, 29]. We call it cheating OMD because at iteration t, the decision z is chosen as a function of the current loss lt, which is revealed after the decision x has been chosen. It is well-known that cheating OMD yields a sequence of decisions with constant regret; we show for our setting the following lemma.
Lemma 5.1. The Cheating OMD iterates {2'}, satisfy 1 (f' -)
11
2112, V2 E Z.
To instantiate RM+ with Cheating OMD regret minimizer for the sequence (R)) of each player i, we need show the existence of a vector zt X2 such that
z' = =1 11 (n)(2²))
Equation (2) can be interpreted fixed-point equation for the map - Tgi-1 (nF(2)) For any z' E X2, the map z + II,, (n)((=) is n/L-ipschitz continuous as long as F is L- Lipschitz continuous. Therefore, is contraction when r) 1/L,, and then the fixed-point equaiioooonuuonnn z = TT,, (n)) has a unique solution. Recall that for z = (Ri..., RT)) E Xx, the operator F defined as F(z)= (f( ..)..... f(zn. ln)) where æ; = g( R.) and & = - (x)), for all i E {1...., n1). We now show the Lipschitzness of F over X² for normal-form games.
Lemma 5.2. For a normal-form game, the operator
L--Lisschitz continuous over Xz. with
LF = (max; d,) /2B3 + 4L2, with Bu, Lu defined in (1).
For LF defined as in Lemma 5.2 and < 1/Lp, the existence of the fixed-point z( 1111,x (nF(z') is guaranteed. This yields Conceptual RM* defined in Algorithm In the following theorem, we show that Conceptual RM+ ensures constant regret for each player.
Theorem 5.3. Let Lr > O be defined as in Lemma 5.2. For r < 1/Tr, Algorithm 3 guarantees that the individual regret Reg (æ.) = Σt (Va, uu(x"))))))) Z; at) of each player i is bounded by 2y || 1b. 2 in multiplayer normal-fome games.
7

---

Note that the requirement of < LF in Theorem 5.3 and Algorithm 3 is only needed in order ensure existence of fixed-point. If the fixed-point condition holds for some larger 17, then the algorithm is still well-defined and the same convergence guarantee holds.
Remark 5.4. Piliouras et al. [31] propose the clairvoyant multiplicate weights updates (MWU) algorithm, based on the classical MWU algorithm, but where the rescaling at iteration t involves the payoff of the players iteration I. The connection with the conceptual prox method made explicit by { [14], where they show how to extend clairvoyant MWU for normal-fore games to clairvoyant OMD for general convex games. Our algorithm uses the same idea but for RM+
For z' E Xx, we can approximate the fixed-point of z + 212 (n)(2)) by performing k E N fixed-point iterations. This results in Algorithm 4. We give the guarantees for Algorithm 4 below.
Theorem 5.5. Let LE > O be defined as in Lemma 5.2 and 1) < L/Lp. Assume that in Algorithm 4, we ensure 1 - -x (11(("") |l2 S for all 1 2 1. Then Algorithm 4 guarantees that the individual regret Reg. (a:)) = =EE= (V,,u((²),, ă;; - a²) of each player i bounded by
2n || - 2.113 + 2B. Vd; E/= c(t) in multiplayer normal-fome games.
1
By Theorem 5.5, if we ensure enror (*) 1/t² in Algorithm 4 then the individual regret of each player is bounded by constant. Since w + 1,, (nF(w)) is contraction for < 1/ this only requires k O (log(t)) exed-point iterations at each time t. If the number of iterations T is known in advance, we can choose k (log( to ensure e (1) O /T) and therefore that the individual regret of each player i is bounded by the constant 2ny | - 2.113 + O (2B.vd)))
Recall that the uniform distribution over sequence of strategy profiles {=²)(_ is (max; Reg!') )/TT-aprroximate coarse correlated equilibrium (CCE) of a multiplayer normal-form game (see e.g. Theorem 2.4 in Piliouras et al. [31].. Therefore, Algorithm 3 guarantees ( convergence to CCE after T iterations. With the setup from Theorem 5.5 and k = Olog (T)). Algorithm 4 guarantees (log(T))TT) convergence to CCE after T evaluations of the operator F.
Extragradient RM We now consider the case of Algorithm/ but with only one fixed- point iteration (k: 1). This is similar to the mirror prox algorithm [29] or the extragradient method [24]. We call this algorithm extragra- dient RM (EXRM++ Algorithm 5). We show that one fixed-point iteration (k 1) at every iteration ensures constant social regret.
Algorithm 5 Extragradient RM (ExRM+)
1: Input: Step size 1) 0 with 1 1/LF
2: Initialization: z" E A'z
3: for = 1,..., T..,Td doo
4: w' = -I1=--1,' (n=((*-1)
5: z' == ===1lg--1, 11g--118² (nF(w"))
6: (af,...., xrhh) (g(w)),... "......g(())) g(wh))
Theorem 5.6. Define LF as in Lemma 5.2
and let 17 (v2Lr)- Algorithm 5 guarantees that the social regret Σ Reg! (æ.) 1 E ||z - 2 in multiplayer normal-form
EL Ets (V),u(z"), R; - x²) is bounded by 2n games.
We now apply Theorem 5.6 to the case of matrix games, where the goal is to solve
min max (x,, Ay) wE y
for A Adxd2 The operator F is defined as
R F
I (R) Ag R2)) If (g(R)), A g g(n))
R2
=
and X3= = A x dd. The next lemma gives the Lipschitz constant of the operator in the case of matrix games.
Lemma 5.7. For matrix games, the operator F is Lp-Lipschizz over Nz. with LF Al||A|lop max maxx(ii,4 d2) with ||A = sup Amll2|/ v E RRd, u + 0}.
Combining Lemma 5.7 with Theorem 5.6, ExRM+ for matrix games with X'~ decision set and 7) (v2LF) guarantees constant social regret, so that the average of the iterates computed by ExRM+ converges to Nash Equilibrium at rate of O(1/T) [16].
8

---

Extensive-form games Our convergence results for Conceptual RM* apply beyond normal-form games, EFGs. Briefly, EFG is game played on tree, where each node belongs to some player, and the player chooses a probability distribution over branches. Moreover, players have information sets, which are groups of nodes belonging to a player such that they cannot distinguish among them, and thus they must choose the same probability distribution at all nodes in an information set. As is standard, we assume that each player never forgets information. Below, we describe the main ideas behind the extension; details are given in Appendix J.
In order to extend our results, we use the CFR regret decomposition [37, 9]. CFR defines notion of local regret at each information set, using so-called counterfactual values. By minimizing the regret incurred at each information set with respect to counterfactual values, CFR guarantees that the overall regret over tree-form strategies is minimized. Importantly, counterfactual values are multilinear the strategies of the players, and therefore they are Lipschitz. functions of the strategies of the other players. Hence, using Algorithm 4 at each information set with counterfactual value and applying Theorem 5.5 begets a amooth-RM' -based algorithm that computes sequence of iterates with regret at most in at O(1/e) iterations and using (log({/e))e) gradient computations.
6 Numerical experiments
Matrix games. We compute the performance of ExRM+, Stable and Smooth PRM+ on the 3 x matrix game instance from Section 2 (with step size = 0.1) and on 30 random matrix games of size (d1, d2) = (30, 40) with normally distributed coefficients of the payoff matrix and with step sizes E {0.1, 1, 10). We initialize our algorithms at (1/d, 11,, all algorithms use linear averaging, and all algorithms (except ExRM+) use alternation. The results are shown in Figure 2. Our new algorithms greatly outperform RM+ and PRM+ in the 3 x 3 matrix game; linear regression finds an asymptotic convergence rate of O(1/T"). More detailed results for this instance are given in Appendix K.1. For random matrix games, PRM all outperform RM+ for stepsize n = 0.1. ExRM* performs on par with RM for larger values of 17. while Stable PRM* and Smooth PRM* remain very competitive, performing par with the unstabilized version of PRM We note that we use step sizes that are larger than the theoretical ones since the latter may be overly conservative [10, 25].
algorithms ExRM Smooth PRM* and Stable
RM
PRM
ExRM
Stable PRM "..... Smooth PRM
3x3 matrix game
random (1) 0.1)
random (1y 1)
random (g) 10)
10
10-1
10
Duality gap
10
10
10
100
10
10
10
11
10 10 30
10 108 10 10²
10P
10
Number iterations
10
10a
102
10"
30
30'
10a
10
10*
Figure 2: Empirical performances of RM+ PRM+, EXRM Stable PRM + and Smooth PRM on +n our 3 x 3 matrix game (left plot) and on random instances for different step sizes.
Extensive-form games. We implemented and evaluated our CFR-based clairvoyant algorithm (henceforth 'Clairvoyant CFR') for extensive-form games. To our knowledge, it is the first time that clairvoyant algorithms are evaluated in extensive-form games. Overall, we were unable to ob- serve the same strong performance observed in formal-form games (Figure 2), for a combination of reasons. First, we observe that the stepsize 17 calculated in Appendix to make the operator F' contraction in extensive-forn games is prohibitively small in the games we test on, each of which has number of sequences on the order of tens of thousands. At the same time, we observe that ignoring the issue by setting large constant stepsize in practice often leads to non-convergence of the fixed point iterations. To sidestep both issues, we considered a variant of the algorithm which only performs single fixed-point iteration, and uses stepsize hyperparameter 7). where we pick the best from the set (1, 10, 20). We remark that this variant of the algorithm is clairvoyant only in spirit, and while it is sound regret- minimiiiiniiootionn algorithm, we expect that the strong theoretical

---

2-plaeer Sheriff
3 player Ledue poker
4 A-paaer Kuhn poker
4 plaaer Liar's dice
10
Cryat CPR in 1.0
Ceyss CPR in 1000) Prodictive CFR
10
Ciysa CIS 2009 Predictive CFR
Puslicticc CFR
10-1
11
10-11
pap
100"2
10
10-1
10-12
10-11
OF 10.0)
10
Predictvo CER
2.50
500
7.50
1000
2.50
500
750
1000
2.0
500
7.50
1000
250
500
750
1000
Gradient computatations
Gradient computatations
Gradlient computatations
Gradient computatations
Figure 3: Practical performance of our variant of clairvoyant CFR ('Cvynt CFR') compared to predictive CFR, across four multiplayer extensive-form games. Note that on Liar's dice, both algo- rithms are down to machine-prectio preciisooeeiionnn accuracy immediately, which explains the jittery plot.
guarantees of constant per-player regret do not apply. Nevertheless, in Fig. 3 we show that we are able to sometimes observe superior performance to (non-clairvoyant) predictive CFR the four games we tried, which are described in the appendix. For both algorithms, we ignore the first 100 iterations, which the iterates are very far from convergence. To compensate for the increased amount of computation needed at each iteration by our clairvoyant algorithm, we plot on the x-axis not the number of iterations but rather the number of gradients of the utility functions computed for correlated equilibrium, which is equal to
each player. On the y-axis, measure the gap to the maximum regret across the players, divided by the number of iterations.
7 Conclusion
We initiated the study of stability for RM+ and showed that both RM+ predictive R from stability issues that lead to slow convergence in games. We introduced two simple ideas, restarting and chopping off. that ensure stability. Consequently, we introduced stable/smooth Pre- dictive RM+, conceptual RM+ and Extragradient RM+, all with strong regret guarantees. Our results yield the first RM--based algorithms with better than O(VT) regret guarantees, thus par- tially resolving the open question of whether optimism can yield theoretical speedup for RM+ Future directions include understanding whether our stability observations can be leveraged more directly in RM+ without adding our stability tricks, extending our results to general convex games, for which a regret minimizer based on Blackwell approachability similar to RM has been proposed recently [17], and combining clairvoyant updates with alternation
Funding. J. Grand-Cled Clément supported by the Agence Nationale de la Recherche [Grant 11- LABX-0047] and by Hi! Paris. Christian Kroer is supported by the Office of Naval Research awards N00014-22-11 22-1-23303 and N00014-23-1-2374 and the National Science Foundation awards IIS-2147361 and IIS 113-2238960. Haipeng Luo and Chung- Wei Lee supported by National Science Foundation award IIS- 1943607.
References
[1] Bai, Y., Jin, C., Mei, S., Song, Z., and Yu, T. Efficient phii-regret minimization in extensive- form games online mirror descent. arXiv preprint arXiv:2205. 1...22945...94, 2022.
[2] Bowling, M.. Burch, N., Johanson, M., and Tammelin, O. Heads-up limit hold' em poker is solved. Science, 347(6218), January 2015.
[3] Brown, N. and Sandholm, T. Superhuman Al for heads-up no-limit poker: Libratus beats top professionals. Science, pp. eaao1733 Dec. 2017.
[4] Burch, N., Moravcik, M., and Schmid, M. Revisiting cfr+ and alternating updates. Journal of Artificial Intelligence Research, 64:429-443, 2019.
[5] Chen, and Teboulle, M. Convergence analysis of proximal-like minimization algorithm using bregman functions. SIAM Journal Optimization, 3(3):538-543, 1993.
10

---

[6] Chen, X. and Peng, B. Hedging in games: Faster convergence of external and swap regrets. 2020.
[7] Daskalakis, C., Fishelson, M., and Golowich, N. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27644-7761, 2021.
[8] Farina, G., Kroer, C., Brown, N., and Sandholm, Stable-predictive optimistic counterfactual regret minimization. 2019.
[9] Farina, G., Kroer, C., and Sandholm, Online convex optimization for sequential decision processes and extensive-fore games. In AAAI Conference on Artificial Intelligence, 2019.
[10] Farina, G., Kroer, C., and Sandholm, T. Optimistic regret minimization for extensive-fom games via dilated distance-generating functions, In Conference on Neural Information Pro- cessing Systems, 2019.
[11] Farina, G., Ling, C. K., Fang, F., and Sandholm, T. Correlation in extensive-form games: Saddle-point formulation and benchmarks. In Conference Neural Information Processing Systems (NeurIPS), 2019.
[12] Farina, G. Kroer, C.,, and Sandholm, T. Faster game solving via predictive blackwell ap- proachability: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 5363-5371, 2021.
[13] Farina, G., Anagnostides, I., Luo, H., Lee, C.-W., Kroer, C., and Sandholm, Near-optimal no-regret learning dynamics for general convex games. In Advances in Neural Information Processing Systems, 2022.
[14] Farina, G., Kroer, C., Lee, C.-W., and Luo, H. Clairvoyant regret minimization: Equivalence with nemirovski's s conceptual prox method and extension to general convex games. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022.
[15] Farina, G., Lee, C.-W., Luo, H., and Kroer, C. Kernelized multiplicative weights for 0/1- polyhedral games: Bridging the gap between learning in extensive-form and normal-form games. In Proceedings of the 39th International Conference on Machine Learning, volume 162 Proceedings of Machine Learning Research. PMLR, 2022.
[16] Freund, Y. and Schapire, R. E. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):99-103, 1999.
[17] Grand-Clément, J. and Kroer, C. Conic blackwell algorithm: Parameter-free convex-concave saddle-point solving. Advances in Neural Information Processing Systems, 34:9587-9599 2021.
[18) Grand-Clément, J. and Kroer, C. Solving optimization problems with blackwell approachabil- ity. arXiv preprint arXiv:2202.12277 2022.
[19] Hart, S. and Mas-Colde Colell, A. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 127-1155,, 2000.
[20] Hazan, F. et al. Introduction to online convex optimization. Foundations and Trends in Optimization, 233-4))157-325, 2016.
[21] Hoda, S., Gilpin, A., Pena, J., and Sandholm, T. Smoothing techniques for computing nash equilibria of sequential games. Mathematics of Operations Research, 35(2):494-512, 2010.
[22] Hsich, Y., Antonakopoulos, K., and Mertikopoulos, P. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In Belkin, M. and Kpotufe, S. (eds.), Conference on Learning Theory, COLT 202/, volume 134 of Proceedings of Machine Learning Research, pp. 2388 2422. PMLR, 2021.
[23] Kiwiel, K. C. Proximal minimization methods with generalized bregman functions. SIAM journal on control and optimization, 35(4): 1997.

---

[24] Korpelevich, G. M. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[25] Kroer, C., Waugh, K., Kılıne-Karzan, F., and Sandholm, T. Faster algorithms for extensive- form game solving via improved smoothing functions, Mathematical Programming, 179(1): 385 417, 2020.
[26] Kuhn, H. W. A simplified two-person poker. In Kuhn, H. W. and Tucker, A. W. (eds.), Contri- butions to the Theory of Games, volume of Annals of Mathematics Studies, 24, pp. 97-103. Princeton University Press, Princeton, New Jersey, 1950.
[27] Lisy, V., Lanctot, M., and Bowling, M. H. Online monte carlo counterfactual regret minimiza- tion for search in imperfect information games. 2015.
[28] Moravčík, M., Schmid, M., Burch, N., Lisy, V., Morrill, D., Bard, N., Davis, T., Waugh, K., Johanson, M., and Bowling, M. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, May 2017.
[29] Nemirovski, A. Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-coneave saddle point problems. SIAM Journal on Optimization, 15(1):229-25 2,,, 2004.
[30] Nemirovski, A. and Yudin, D. Problem complexity and method efficiency in oplimization. 1983.
[31] Piliouras, G., Sim, R., and Skoulakis, Optimal no-regret learning in general games: Bounded regret with unbounded step-sizes via clairvoyant mwu. arXiv preprint arXiv:2111.14377, 2021.
[32] Rakhlin, A. and Sridharan, K. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, pp. 3066-3074, 2013.
[33] Southey, F., Bowling, M., Larson, B., Piccione, C., Burch, N., Billings, D., and Rayner, C. Bayes' bluff: Opponent modelling in poker. July 2005.
[34] Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. E. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
[35] Tammelin, O. Solving large imperfect information games using cfr+. arXiv preprint 2014.
[36] Tammelin, O., Burch, N., Johanson, M., and Bowling, M. Solving heads-up limit texas hold'em Twenty-forrhh international joint conference on artificial intelligence, 2015.
[37] Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C. Regret minimization in games with incomplete information. Advances in neural information processing systems, 20, 2007.
12

---

A Proof of Lemma 2.1
Proof of Lemma 2.1. Let us write R c. Note that
T
Reg (x)) = Σ ( et) Σ (
④b f('
(3)
Σ
RR f
Σ R f(a', ,))
E (R,
(4)
Reg" R
(5)
where (3) follows from 11 1 and the definition of the map f(..), (4) follows from
RR' f(''(((__" )) 0 because x' RR |||R'|| (note that this is also trivially true when R' 0),
and (5) follows from the definition of Reg" i2)
B Instability of RM+ and predictive RM+
B.1 Proof of Theorem 3.1
Proof of Theorem 3.1. We first prove the case for RM+ Since we consider x'' E R2, we can express a. (p', 1-pp) for some scalar p' E [0, 1] (starting with p¹ 11/2). In our counterexample, we set lr = (E) for some scalar ll to be specified. Consequently, we have
f(x' e') = (x',e' 12 ((1 p')e", - p²t").
To make the algorithm highly unstable, we first provide unbounded sequence of l so that the resulting Re alternates between vectors with the same value on both entries and vectors with only the first entry being which means p' by definition alternates between 1/2 and O. Noting that RM+ is scale-invariant to the loss sequence, our proof is completed by normalizing the losses so that they all lie in [_,
Specifically, we set = 2, which gives ( = (1, (1) R² = (0, 1), and p² = 0. Then for t 2 2 we set &t = - 21/2 when t is even and ge = 11/2 when is odd. By direct calculation
it is not hard to verify that
((*,,') (-2(t-2)/2, 0),
R (2 200/2,2(0-2)) 2(1-2)/2).
pe = 7 when t is even, and
f(x', = (2(t-3)/2 -2,-3) 2(t-3)/2)
R (0, 2(1-1)/2)
+1 when is odd, completing the counterexample for RM
It remains to prove the case for predictive RM- where m = (1al-1,ee-)) Initially, let f 4, e 1. Recall that
f(æ², ((e",e))=E - -2' e 1 = ((1-101)) - p')et -p:tt)
By direct calculation, we have
f(xt,et) (2, 2)), f(z2, (-1.0),
R² (0,2),
πt² = (-2,4),
D²² 0
p² = 1
R² = (1,2),
R = (2,2),
2
13

---

Thereafter, we set l = 22++1//2 the next steps are:
when t is odd and f = 2((-2)) when f is even. The updates for
f(x", ()) (2, -2),
R (0, 4),
R (0, 6),
p² 0
f(x", (t) = (-2,0),
R (2, 4)
R = (4, 4)
pd 2
f(e", (9) (4, -4),
R (0,
R (0, 12),
p 0
R (4,8), is not hard to verify (by induction) that
f(x (*) 0),
R² = 18,8),
p² 2
f e²)) (2(-1)// 211-,) R+ = (0, 2(02)()))))))
R+ 20,2(t-1)/2 2(t-1)/2)
p =0
when is odd and
f(x', ,()) = (-2 2)/2 0), R = (2 (2(tt22)/2,21/3)
R = (2 2(/2), pt 2
when t is even. This completes the proof.
Remark B.1. The losses are unbounded in the examples. but note that the update rules for the algorithms imply that all the algorithms remain unchanged after scaling the losses, so we can rescale them accordingly. Specifically, if we have a loss sequence E ......"" E we can de- fine LT max |.... 13 and consider another loss sequence e LT....., ( E LT, which is
bounded in 1-1, 1] and will make the algorithms produce the same outputs.
B.2 Counterexample on 3 x 3 matrix game for RM+
11s 1
16
10-3
Nem
North
20
10-7
10
302
10
102
111
10P
11
(a) ||ar ++
x
1
(b) 11 4+1
Figure 4: ||x++1
x² 112 (Figure 4a) and
| y'll 112 (Figure 4b) for RM
Regret (x-player)
Regret ty-player)
108
100
Regest
100
11f
-300
10"
162
10
102
30P
Number
(a) Regret of the first player
(b) Regret of the second player
Figure 5: Individual regret each player for RM
C Proof of Proposition and Corollary 3.2
We start with a couple of technical lemmas.
Lemma C.1. Given any y E Rd. and æ E d such that 1 x O.
1 x
14

---

Proof. If æ = O the claim is trivial, so we focus on the other case. Let & be the (Euclidean) projection of y onto the orthogonal complement of span az 1}. Since by hypothesis æ, it holds that
1sy y 1 +
y
y
x
1
and therefore
y
x)²
(1 y)
x)²
(1 y)
a
x
12
|
Using the hypothesis that y O, we can bound
1 1'
y laill
2 1
where used the well-known inequality between the -noom and the 82-norm. Substituting the previous inequality into (6), and using the fact that | = d.
y x)²
1
d
Rearranging the terms yields the statement.
Lemma C.2. For any D E 14 such that 10ll2 1, 1 1 + 0 and for any æ E Rd such that
1x==1
1 x 4
(d-1)
1) || ") 10
1 T ạ
Proof. The main idea of the proof is to introduce
1 1
Note that 1 2 1TT 0. Furthermore,
1 ú
+
IT ÿj
1
Substituting the previous equality in the statement, we obtain
2
x: T 1/
(d 1)
|| ")
1 9
(z Tg)) - (d - 1)
x 2 1
2
1
(z [0)² - (d - 1)
[] T ")) 1
(z (=)))² (d 1)
(z (=T))² || 2(2 /)
d (z (z) 0) d
||>|
d
where used the hypothesis that |0l concludes the proof.
1 in the third equality. Using the inequality of Lemma C.1
We now ready prove Proposition 1.
Proof of Proposition I. If = O, the statement holds trivially. Hence, we focus on the case * 0.
Let y := y/1yy/2 be the direction of y: clearly, ||0 2 1. Note that
ll == 2=1 = (1lvl12 x T ") +
(xc
x
(x 2
15

---

(1 (1==)²
x)² [g( (g(x)
2 ||((z) (g(x) 8) 61
where we used the hypothesis that x 2 in the last step. On the other hand, using Lemma C.2 (note that 1 # since y # 0 by hypothesis),
|1(()) - (g(x)) 9) ull2
= -21o((0) (g(x) 9) 0ll
-='11((0)) (g(x)) 1) 0
1 )llo()) (g(x) T 8
((x)(( T y
)
T ÿ 1 2g(2) T y
d [la(=)112
1
(1
1 ÿ
1
d [la())]1 + | 2g(x)) 2g(x))((y))
d | 9
(8)
Combining (7) and (8), we obtain the statement.
Proof of Corollary 3.2. The condition means that 1 1
R
2
and
Rg
R++1
R'
|| | 22'12 S vd
(by Proposition 1)
Ro
Ro
1
Vd
f e²)
Ro
Vd
(11e111 + -1(2'', (e)) 1a lallz)
Ro
Vd
Bu + vd ae|l011 [101112
(by (I))
Ro
BdB
Ro
D Proof of Theorem 4.1
Proof of Theorem 4.1. When the algorithm restarts, the accumulated regret is negative all actions, so it is sufficient to consider the regret from To, the round when the last restart happens to the end. In that case, we can analyze the algorithm as a normal predictive regret matching algorithm. By Proposition 5 in [12], we have that the regret for player i is bounded by
Reg T (x²) S || - -
T
Σ |
m
Σ 1
- x
(9)
2m
8n
T=
T=
where 2/th (Ro...., Ro) and ($² (1--1) iE(m) = F(z--1). When setting m
f then
llft mlll be bounded by
|]{t mill ||<25, 1a, (00 -,,11,-1) la; (e: -
16

---

= || - -|- L)) 1d.
t-1 - et) 1d, (E: e;- 111
< ||a| x " ||
|| ll2 + || 11 || -Rill2 ||
+ || 1
s BuVd, Vd,
|| - x 11 v d: [ - 1 + l|e; 2
-
(by (1))
x B. d || = x 112 + V d, D
2 || 2 '12
(by (1))
$2vd((B, + Lu)
Σ
x x 11
12n d. (Bu, Lu) Ev dy
Ro
12n (Bu + Ld3
Ro
where the last-but-one inequality is because
|| 2. x0/111
112 = |19(2() - g _ )|1
|[/ - g( ( 1112 |1g(w( glwe ([ll(( -g(z) )ll
Bn, Bnd
Ro
Ro
and we bound each RHS of the first inequality using restatement of Corollary 3.2, shown in
Lemma D.I. Therefore, we can further bound (9) it by dropping the negative terms and bounding the rest by
x
12
1
||
f--
111
1 RBd
ST
144B BB, + I.,)
1
7
n
RØ
T=
Choosing Rg and 17 (d2T) - 1/4 finishes the proof.
Lemma D.1. Let z IT (nf e)) for E Ad, EE IRd, [lel12 S BB- Suppose ||m||| 2 Ro. then we have
Vd
2rddB, Ru
[1[()) g(w)))12 S
112 w|12
Ro
Proof. The proof is essentially the same as Corollary 3.2. The condition means that T w
Rg 2 1 and
[[ - g(w)ll2 = 11g( Ro)
-g(w/ Ro)ll
Vdl
z
w
(by Proposition 1)
R
Ro
2
Vd
||nf( 2)11
R
ndd
(|181l2 + 11((x E) 1allz)
Ro
nvd
(B. + Vd (2
(by (1))
Ro
2ndB,
Ro
17

---

E Proof of Theorem 4.2
write (Ris..., R, = z². Let us consider the regret Reg/ (æ.) of player {I,..,, n.. Lemma
2.1 shows that
Reg/ (f::) = Reg? R:
with Reg. T (R,) the regret against R, c. incurred by decision- maker choosing the decisions
(R) 1121 and facing the sequence of losses (fi))21 with f Li (a) L.) 1d,
Reg. T
R
Σ
R R.
(10)
Note that R2; R is computed by Predictive OMD with A as decision set, fi, the sequence of predictions. Therefore, Proposition 5 in [12] applies, and we can write the following regret bound:
St as the
sequence of losses and m y.... m.
2
Reg. T'
R2
f m!ll
21
1=1
(11)
R
R
817
Since maintain R2 E A at every iteration, using Proposition we find that
|
2
d
R
R 2
Plugging this into (11), we obtain
Reg."
T' R
x
Σ
|
mil?
2n
1
++
xx'
8d
Using 11 $ |1- vdill l12, obtain
T Σ
Reg.
T'
1i
sa
||
ml
1=1
T
x ++1
with 1/00 -a. 12
3 d 7
To conclude Theorem in [34] we need 3 < Therefore, using 1) 2vZ(n max, (ax777 we conclude that
2n
5d
7/(n 1)2, i.e., 17
2/2(n-1ja"
the sum of the individual regrets is bounded by
o ( max (a912)
max {llwp 22 i= L.....
i= L.n..
F Proof of Theorem 5.3
Proof of Lemma 5.1. The first-order optimality condition gives
(ne + x' - 111 x²) > 2v Z.
18

---

Rearranging gives that for any & E 2, we have
(ne", & - x²) 2 (z'-1 x², 2 x²) = - 2
2 2- 212
+
2 11 2=1 112.
2
Multiplying by -1 and summing over all t = I,..!? I gives the regret bound:
me, x' - 2) s 211== - -2112
1 2 11 -211 2 12 -
11-
2²
1 2212²0 - -2112.
Proof of Lemma 5.2. Let æ, x' E A and E fI. Let us write l, = - -va; (,)), - ~v (z('. We have, for i E n),
|f (mi, li) - f (2) f.) 11
= ((a: ee)_e
ei - -arl - Te)
d;
Σ ((ar; - -e,) l - -004- - ej) ls + (ar - -ez) - -mxl - -ep) e))2
j=1
4.
Σ ((z; xx)TT, 4, (σ) - -e)) (4.
TT) -e))
1=1
s 2d, ((z)) - T (i)
2 +2 Σ ((o) e;) T))(( (e. - -2))²
j=1
di
s 2d; -0 2
+ Σ
| - e 12.
j=1
where the last inequality follows from Cauchy-Schward inequality. Now from (1) and the definition of Lú C, we have
| 12 S Bu, l|e:
fill2 S Lul x 112.
This yields
II (z., f (a/, 2 11 S 2d, x;; - 1:113 + 4rl, 1.2 1 - a:' a:'13 S (2d, + Ld) ||<0 - x' 1/1
Since the function is Viy-Lipschitz continuous over each decision set A (Proposition 1), we have shown that the Lipschitz constant of F Lp (max; d:) /2B2 + 4L2.
We are now ready to prove Theorem 5.3. We write (R) -.... R z
Proof of Theorem 5.3. We use the fact that (z') is computed following the Cheating OMD up- date with L = F(z") at every iteration t 2 1. Therefore, the first-order optimality condition in
z' 2-1 X (1))) yields
(nF(x') + +2' -'' x²) 2 20 E Xz.
Similarly for the proof of Lemma 5. we obtain that for any X2z we have
(n)())), 2²) 1=' - - 2 + 1 - -1-2'-²'-1 2
Let E {l,...,n} n). We apply the inequality above to the vector & X2 x A defined
as 2 = 2) for j # i and 2, = R, for some R, E Ag. This yields, for any R. E A di for
2 = g R)) and (e,,..., (.) G(x²) for all j E {1, (1,....,)) n).
(nf(a' 1), R R > } | R 1
R
R +
1 2 I R
19

---

Summing the above inequality for t = 1,.., T, we obtain our bound on the individual regrets of each player: for any RS E A we have
T R
Enf e), R R
R R
R
11 -
Σ
R
2 | R 11
2
Note that from Lemma 2.1, we have that the individual regret of player i
Reg.
T (.t,) - Σ ( (x 2t)
against decision a; A4 is equal to (f ,L)), Ry RR)) for R. =2,- Therefore, conclude that
1 || a:112
Reg (.:) S 21j
This concludes the proof of Theorem 5.3.
G Proof of Theorem 5.5
Proof of Theorem 5.5. At iteration / 2 1, let w E Az such that 1//0 - -Ig--1 X2 (nF(ww)) l12 s
(l)), Then the first order optimality condition gives, for z' 11g (nF(w')).
1 || - 2112 - (nF(w"), & =²) 2
1 マ || - 212 + 2112²² - x'- -0-="==0-1100 11
X2.
Let us fix a player i E {1...., We apply the incquality above with 2n 23 for # i. This yields,
for x, ( ) V p E {1,.... n and f Vv..,
(nf(g(w)) 4), 2 21) 2 _ || م 1B -
2, + |z| - 1 21 E Ad.
We now upper bound the left-hand side of the previous incquality. Note that (nf(g(w)) e, 2, = = (g e), & - w/) + (nf e,), un 21) Cauchy- incquality ensures that
(nf(g(w)))() wi 2/) s nl flllf(((w)) 122lw (ll z/1l2- Note that Igg-- (nF(wo") = 2t, so that |o zfll2 I c0) To bound ()())))) we
note that by definition,
d. llf 4:11 = Σ ((x, - -ec,-e,,T[p Te)2 - Σ
|| - 1 < 4d.
5=l
This gives
[f(g(w))) e2 S 2B. di.
Overall, we have obtained that for all é; E Ad, we have
(nf())))) w - 2.) ك - 2
1
-
2 _112/ 2, + 1/2B, v (1)
+
2
We sum the previous inequality for L -= 1,..., T to obtain that for all
2;
E
A di
we have
T
T
T + 172 v de Σ (t)
1
1 1 - 22113 Σ
Einf(gwo)) 4), - -2,) S = || 2.112
-
Overall, we conclude that
T
T
E(r(o(w))))) ()) - -2)) < -
|| - 2.112 + +B, v d,
Σ
(1) 4 24 E
21
From Lemma 2.1 the left-hand side is equal to Regf (ax)) for कं E. This concludes the proof of Theorem 5.5.
20

---

H
Proof of Theorem 5.6
Proof of Theorem 5.5. We will show that for any E X2, we have
T
Σ F(w"'), w -1) - 21
11000
Since i = w/ Wt2 1, (1...,, n). this is enough to prove Theorem 5.5. Note that
(F(w'), w u) (F(w'), x' w) (ww)) w' =²)).
We will independently analyze each term of the right-hand side of the above equality.
For the first term, we that the first-order optimality condition for z' -1 (nF(ww gives, for any in Xzz
(nF(w'), 2 S 112000 x/
2 E
2112
(12)
2
2
For the second term, we will prove the following lemma. Lemma H.l. Let 17 > 0 such that w + (F(w) is 1/v2 Lipschitz continuous over Xz. Then
1
(nF(w'), w² - x²) s 2 E| - x² 11.
(13)
Proof of Lemma H.l. We write
(nF(w"), wt - x²) = (nF((==11) w' - =²) (nF((w)) -FF(2'11) ),"²
w² =z¹).
We will bound independently each term in above equation. From w = -121-1,X5 (11(((111)
we have
(nF(2"1)),0 20 -2")
112
1
1 11
w'11
1 x¹ 1 112
2
2
which gives
1
1
(nF(2"=1), w0 - =²')= 2 x/" x² 11
w011
=1'2"
111
(14)
2
2
From inequality, we have
(nF(w"') 1)((2²-1) w¹ - x²) s (lnF((w9) - \122100000 - =2112-
Recall that
w/ -1 (nF(2*-1)) z' = =1 1xx (nF(w"))
Since the proximal operator is 1-Lipschitz continuous, and since w + nF(w) is 1/ 1/V2-Lipschie continuous, we obtain
(noo'))nF(''"") w - -x)) - 2 1w' - x' 11.
(15)
We can now sum (14) and (15) to obtain
(nF(w""), wi - 2²) 5 112 - 1-11
1 2
w
112
12
2t
We have shown in Lemma 5.2 that F' is Lr-Lipschitz continuous for normal-form games. Our
choice of step size 1) L, ensures that that w - 1)F(w) is 1/ 1-V-psictt continuous as the assumptions of Lemma H.I.
21

---

Combining (12) with (13) yields
1 (n u² - 2
2 1 2-11
11
2²112
2
Summing this inequality for t = I,... T and telescoping, we obtain
(nF(w"), w0 w) u))= 111 1
1 11
which directly yields
T
Σ
(nF(ww), w0 - -w0) I
1 21/00 - -2 1012-
(16)
2
Overall, for any (R), .Ri,.... Rm)
E X3 we obtain that E/=1 Regi (R:) is upper bounded by
Exs 27 / R. 11.. Now from Lemma 2.1, for any (0) :..9 fin) A, conclude that
T
1
Σ
Reg (æ.) S Σ
w 2/.12.
2nj
1=1
This concludes the proof of Theorem 5.6.
I Proof of Lemma 5.7
Proof of Lemma 5.7. The proof of Lemma 5.7 follows the lines of the proof of Lemma 5.2. Clearly, for matrix games we have F h g with h IR I2 Fd gd defined Proposition
x = f
f(x (y.-A x)
(17)
The function is Lipschitz continuous over A (Proposition 1), with Lipschitz constant of Lg VT. Let us now compute the Lipschitz constant h. Observe that:
Il (x, Ay) f (a', Ay') 22
((x: -e:)T Ay (a' ei) Any)
41
Σ
((x - e.) Tyy - (x' e.) T.)TAy Ay + (a' TT)TTAy Ay (a' - e Ag))2
1=1
di
((x T²)T Ay + (x' - e,) A(3 -2')2
1=1
2d, ((x x²)² Ay) +2 > ((x' ez) A(y 4/))²
i=1
2d Al? æ x 2111 1|2 + 4d || 2 yy y'112.
Similarly, we have that | (.. - A x) - f (v' - x') 1| is upper bounded by
2d
22 y 2'112 + 4d 1 x x 2'122
and thus
h1
h
< ||Alloop mmx d2f
y
Therefore, the Lipschitz constant of is LA = || / mmmx(111 dz Since F = h o g. we obtain that the Lipschitz constant LE of F is Lp 66| A|l op max(di,dg)
La Lg
22

---

Extensive-Form Games
In this section show how extend convergence results for Conceptual RM+ from normal- form games to EFGs. Briefly, an EFG is game played on a tree, where each node belongs to some player, and the player chooses a probability distribution over branches. Moreover, players have in- formation sets, which are groups of nodes belonging to a player such that they cannot distinguish among them, and thus they must choose the same probability distribution at all nodes in an infor- mation set. When a leaf h is reached, each player i receives some payoff 2; (h) E [0, 1]. In order to extend our results, we will use the CFR regret decomposition [37. 9]. and then show how to run the Conceptual RM+ algorithm on the resulting set of strategy spaces (which will be a Cartesian prod- uet of positive orthants). The CFR regret decomposition works in the space of behavioral strategies, which represents the strategy space of each player as a Cartesian product of simplices, with each simplex corresponding to the set of possible ways to randomize over actions at a given information set for the player. Formally, we write the polytope of behavioral-foo form strategies as
X' = XiE[n]JED; A"),
where Dj is the set of information sets for player i and n, the number of actions at information set j. Let P = Eigjol.EED n be the dimension of X. In EFGs with perfect recall, meaning that a player never forgets something they knew in the past, the sequence-form is an equivalent represen- tation of the set of strategies, which allows one to write the payoffs for each player as a multilinear function. This in turn enables optimization and regret minimization approaches that exploit multi- linearity, e.g. bilinearity in the two-player zero-sum setting [21, 25, 10]. Instead of working on this representation, the CFR approach minimizes a notion of local regret at each information set, using so-called counterfactual values. The weighted sum of counterfactual regrets at each information set is upper bound on the sequence-form regret [37], and thus a player in EFG can minimize their regret by locally minimizing each counterfactual regret. Informally, the counterfactual value is the expected value of action at information set, conditional on the player the information set playing to reach that information set and then taking the corresponding action. The counter- factual value associated to each tuples of player information set j D;, and action a E A, is
Gija (z) == Enec, IGG,))r, æ1j; a] (h), where Lja is the set of leaf nodes reachable from information set j after taking action a, and (h) is the set of pairs of information sets and actions () on the path from the root to h, except that information sets belonging to player i are excluded, unless they occur after j.a. a.
We will be concerned with the counterfactual regret, given by the operator H X' + R Ee "o defined as (x)a(x)) Gıja(z) (G x²). Now can show that the counterfactual regret operator is Lipschitz continuous. Intuitively, this should hold since H is multilinear.
Lemma J.1. For any behavioral strategies x, x' E X. [x) H(x')l S v <2P| - x'112-
Proof. We start by showing a bound for G. We first analyze the change in single coordinate of G for a given i E [n].j E Di,a E Aj. We focus on how Gija changes with respect to the change in |m[] a] - x' [ū, a]] for some arbitrary information set-action pair (i,û) E (h)) for some h E Lja- To alleviate inline notation, let pp: (h) = (h) \ (G,a))
Gijo(x) = =xli,a]
Σ
II
WE naja (.))
Σ
II
al;.a),;(h)
NEC 3a (1,))EP;sh)
$ |m|], a]
x [ū,aal
Σ
II
.I.. (h)
hEC he (a)))))))))
+ Σ
II
NEDianG ne G.a)EP5(M)
Σ II al..a)u.(h))
Le (a))P,(h)
23

---

Now let us bound the error term by noting that (4(1)) S 1 for all h by assumption:
|x B a] x' aل]
Σ
II
æ (l,
G.a)ep).
[ a] - x x'( all
Σ
II
heLggnCre (.a)E))
S | a] - x' [ا,āā
ä]],
where the last inequality is because the sum of reach probabilities on leaf nodes in Lja n Lja after conditioning on player i playing to reach (j. a) and (j. à) being played with probability one, is less than or equal one.
By iteratively applying this argument to each (.a)) E Pt)h), we get
Gaja(a)) S Gijala') + Σ Σ
[ x x'G. a]]
(18)
NECYa (M))
I Gija(z') + ||0 - 2'111. Repeating the same argument for x' gives
(a)ja()) Gúja (x') S 1 x'1l1-
Secondly, we bound the difference in the inner product terms. (G.,
Σ aEA;
æزjه a a))a
Σ
[ æ'Ii,a] + æ''i, al Gija(()))
oEA,
xx' ||| + Σ x' a'jjaa)Gija(e'++ + Σ x'liaa]
Σ Σ heE (.a))P,
| al
x [].a]]
aEA,
aeA,
(G.y xx') + ||æ x'
where the second-to-last line is by Eq. (18). Again we can start from x' instead to get KG (a:), x²) (G)j(a') '')l < -|-- man===lla-- m'Il1-
Putting together all our bonds and applying norm equivalence, we get that
[[())))) H(x')
Σ Σ iE(n) JED,,eA, < 2P - 11
2|10 x' 1
Taking square roots completes the proof.
Since we want to run smooth RM+ we will need to consider the lifted strategy space for each decision point. Let Z be the Cartesian product of the positive orthants for each information set, i.e. 2 = XiE ". Now let ğ + X' be the function that normalizes each vector from the positive orthant to the simplex such that we get a behavioral strategy, i.e. 0z(x) = g(2²). where z² the slice of corresponding information set j. The function is also Lipschitz continuous.
Lemma J.2. Suppose that 2, z' E Z satisfy || 11 2 Ro,j, || 2 Ro,; for all E [n], e D.
Then, (lğ(z) 522')112 max Vn; Ro. 2'112-
Proof. We have from Proposition that
[lو(z) 0(>')11 =
Σ
[g(()) g(>')11
iE|n),ED;
24

---

Σ
ng/Ro,J (Ro,,,ll= x012
iEIn).JD.
- iE|D)JED;
max
Now let us introduce the operator 2 -> RR " for EFGs. For a given z 2, the operator will output the regret associated with the counterfactual values for each decision set j. F will be composed of two functions, first maps a given to some behavioral strategy = ((2),
and then the operator H : X + R=icthis " outputs the regrets for the counterfactual values.
Now can apply our bounds the Lipschitz constant for ğ and H to get that F is Lipschitz continuous with Lipschitz constant 2P maxigi=).jED, Vn, Ro.j- Combining our Lipschitz result with our setup of and F, we can now run Algorithm on X' and and apply Theorem 5.5 to get smooth-RM. -based algorithm that allows compute sequence of iterates with regret at most e in at (11/e) iterations and using Ollog(1e)/4 gradient computations.
K
Details on the Numerical Experiments
Efficient orthogonal projection on Ag. Recall that A =
R E 1
R 0,1, R 2 1). Let
y E R" and let us consider
min a 2001 m21
1 u11..
Introducing a Lagrange multiplier μ 2 0 for the constraint 1 - 1, S arrive
min max x v1l2 + pa -1-1 1..) 220
Let us call (x. 14) E ET x R optimal solution to the above saddle-point problem. Stationarity of the Lagrangian function shows that x; 3 u1]t, V E [n:] Therefore, could simply use binary search to solve the following univariate concave problem:
1 2
[1 +12
max L #20
Let us use the Karush- Kuhhh Tucker conditions. Complementary slackness gives μ4 (1 1, x) = 0. If = O, then = [y]+, and by primal feasibility we must have 1, 2 1, i.e., [g] - 2 1. If that is not the case, then we can not have l O, and we must have 1 1,
A", Overall, 0. i.., x E A", In
this case, we obtain that is the orthogonal projection of
that is always
either (y] the orthogonal projection of on Re or æ is the orthogonal projection of y on A Since AZ R7. we can compute the orthogonal projection on Az follows:
Compute x [1]+t 1f 2 1, then we have found the orthogonal projection of y on A.. Else, return the orthogonal projection of y on the simplex A
K.1 Performances of E Stable PRM and Smooth PRM on our small matrix game example
In this section we provide detailed numerical results for ExRM Stable PRM and Smooth + on our 3 x 3 matrix-game counterexample. All algorithms use linear averaging and Stable and Smooth PRM+ algorithms. The results are presented in Figure 6 for ExRM+ in Figure 7 for Stable PRM+ and in Figure for Smooth *
alternation. We choose step size of 0.1 for our implementation of these
K.2 Extensive-form game used in the experiments
We used the following games in the experiments:
25

---

1|x
10"2
p0p
10"
10-0
Nom
Nomt
10
10
10"
107
10
10
10 Number neriiions
Number leetatioss
Number henatons
(a) Duality gap
(b) ||
x
112
(c) 11
y 112
2.50
Regrot (seplayor)
0.0
Regrt (ygpoyye)
2.5
Reya
2.00
Reggee
-0.4
1.75
-0.6
1.50
-0.8
10P
10F
10"
10
10a
10
101
102
10P
109
107
10
107
Nomber derations
Number of iterutions
(d) Reg!
T (e) Reg
Figure 6: Empirical performance of ExRM+ (with linear averaging) on our x matrix game from
Section 2.
Stable PRM
[| 2-'
I1v /
10-2
10
10-1
10
Narn
21
Norm
24r-1
10-11
10-29
10'
10'
102
11t
Itf
10
107
10
107
107
10
107
107
10
10'
107
10
1PP
10
107
Number llerations
menacons
(a) Duality gap
(b)
||
++11
1/2
(c) 11y
Regret (x-player)
1.0
(y-slaye))
0.5
Reuret
Rejoct
-1.0
Numberr Herusions
(d) Reg
(e) Reg"
Figure 7: Empirical performance of Stable PRM (with alternation and linear averaging) on our 3 x 3 matrix game from Section 2.
26

---

Smooth MRM
11
10
11v
10
20-11
111
Nora
Nerr
(0-11
10
10-12
107
107 102
10 11F
10
10
107
10
101
10P
10'
107
10F
Number Recaatoos
menocons
(a) Duality gap
(b) -|
++11
(c) 11y
y
1
2.0
Regret (x player)
0.5
<-- Regret py-loyer
Reget
Regint
-0.5
10a
1:F
101
16a
10f
11f
20F
11F
10F
10f
10
10
10
Number of lterations
Number of inmmtions
(d) Reg
(e) Reg.
Figure 8: Empirical performance of Smooth PRM+ (with alternation and linear averaging) on our 3 x 3 matrix game from Section 2.
2-player Sheriff is two-player general-sum game inspired by the Sheriff of Nottingham board game. It was introduced
benchmark for correlated equilibria by Farina et al. [1]]. The variant of the game we use has the following parameters:
maximum number of items that can be smuggled: 10
maximum bribe amount: 3
number of bargaining rounds:
value of each item: 5
penalty for illegal item found in cargo: 1
penalty for Sheriff if no illegal item found cargo:
The number of nodes in this game is 9648.
3-player Ledue poker is a 3-player version of the standard benchmark of Ledue poker [33]. The game has 15659 nodes.
4- 4-player Kuhn poker is 4-player version the standard benchmark of Kuhn poker [26]. We use larger variant the standard one, to assess the scalability of our algorithm. The variant we use has six ranks in the deck. The game has 23402 nodes.
4-player Liar's dice is 4-player version of the game Liar's dice, already used a bench- mark by Lisý et al. [27]. We use a variant with die per player, each with two distinct faces. The game has 8178 nodes.
27


Reviews:
[{"review_id": "GAX1t9fC86", "reviewer": "Reviewer_zLtq", "summary": "The paper focuses on investigating the stability of the Regret Matching+ based algorithm. It demonstrates that both RM+ and predictive RM+ algorithms exhibit instability, leading to significant regret for other players within a game setting. To address this issue, the authors propose two methods: restarting and chopping off. By incorporating these methods, the authors introduce several variants of RM+-based algorithms, including stable/smooth Predictive RM+, conceptual RM+, and Extragradient RM+. The paper also provides theoretical regret bounds for these proposed algorithms, further establishing their efficacy in mitigating instability and reducing regret.", "questions": "The thoerem need $\\eta$ to be small. However, in the matrix game experiment, $\\eta$ is chose as $10$. Is $\\eta = 10$ too big in this setting?", "limitations": "The authors have adequately addressed the limitations.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "One of the key contributions of this paper is the theoretical speedup provided for the RM+ based algorithm, which is crucial for achieving fast convergence in games. By offering improved convergence guarantees, the proposed advancements in the algorithm can significantly enhance its practical utility.\n\nThe writing in the paper is well-organized and clear, effectively conveying the technical details. The strength of the paper's technical aspects further adds to its overall quality, making it more accessible and understandable for readers.\n\nThe comprehensive experimental results presented in the paper further enhance its credibility. Notably, the authors also consider the application of the algorithm in extensive form games, which is important for real-world scenarios. This consideration highlights the practical relevance and versatility of the proposed techniques.\n\nOverall, the paper provides valuable theoretical insights, demonstrates technical proficiency, and showcases the practical applicability of the proposed algorithm, making it a strong contribution to the field.", "weaknesses": "Just a small point about presentation. It would be beneficial for the authors to consider organizing the algorithms discussed in the paper by creating a table. This table can help provide a clear overview of the different algorithms, highlighting their similarities and differences.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time reviewing the paper. In the final version of the paper, we will add a table to summarize the different regret guarantees for the algorithms introduced in this paper. Regarding your question: you are right that the stepsizes we use in the experiments are generally larger than what the theory requires. This is a commonly-found phenomenon, that the theoretical stepsizes are too conservative, see e.g. the related literature in [10,25]. We will make sure to emphasize this more in the final version."}, {"review_id": "26WFv0oE35", "reviewer": "Reviewer_jyGc", "summary": "This paper studies the RM+ algorithm and its variants in the context of learning in games.\n- They first show that RM+ and predictive RM+ can be unstable in certain environments. Although the unstable player benefits from instability, the regret of other players may blow up because they are forced to make predictions in an unstable environment.\n- Then they provide several approaches to stabilize RM+.\n\t- The first approach, called **stable predictve RM+**, requires each player to (asynchronously) restart whenever $\\mathbf{R}^t_i$ becomes small. Although this stabilizes the algorithm and guarantees $O(T^{1/4})$ regret for each player, it's hard to bound the social regret by $O(1)$ .\n\t- The second approach is called **smooth predictive RM+**. It chops off the area of decision space that is too close to the origin by adding projection steps. Besides individual regret bounds, this approach also guarantees $O(1)$ social regret.\n\t- They also propose **Conceptual RM+** (and the one fixed-point approximation of it) that achieves $O(1)$ individual regret and **Extragradient RM+** that achieves $O(1)$ social regret.\n- The authors conduct experiments on matrix games and extensive-form games.", "questions": "In the proof of Theorem 3.1, the authors constructed an example where the precision of the losses increases with $T$ (the minimum value is exponentially small), a scenario that may not practically appear.\n- Is this phenomenon of increasing precision the fundamental reason of instability, or is it merely an artifact of the proof?\n- Does this same phenomenon appear in the subsequent experiments involving the $3\\times3$ matrix game?\n- If a bounded precision assumption were introduced, could this potentially stabilize RM+ or PRM+?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper contributes to the theoretical understanding of the RM+ and its variants. It is the first one to show the instability of RM+ and predictive RM+ by concretely constructing a hard case that exhibits the $T^{-0.5}$ convergence rate.\n- The paper proposes several variants of RM+ that not only have appealing theoretical guarantees on both individual regret and social regret, but also perform well in experiments.\n- The paper is very well-written. The authors clearly explain the intuition behind the theoretical results.", "weaknesses": "- In section 3, the authors construct a hard case for RM+ and predictive RM+ where the empirical convergence rate are on the order of $T^{-0.5}$. However, the residue errors of the linear fit in Figure 1 are quite large. Providing a theoretical proof that the asymptotic convergence rate is indeed $T^{-0.5}$ would strengthen the result.\n- Given the connection between RM+ and OMD in [12] and the fast convergence properties of OMD in games, the performance guarantee for the stabilized variants of RM+ do not seem surprising. Nonetheless, as mentioned by the authors, RM+-based algorithms are not inherently stable, so they need extra considerations.\n- The experiments show the strong performances of the proposed algorithms compared to RM+ and PRM+. It would be better if the authors also compared their performance with the optimistic/predictive FTRL/OMD algorithms that enjoy fast convergence rates in theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time reviewing the paper.\n- We have run additional numerical experiments to compare Optimistic OMD (OOMD) and Optimistic FTRL (OFTRL) with ExRM+, Stable and Smooth PRM+. We ran these algorithms for the $3 \\times 3$ matrix game instance and for  $10$ random matrix game instances of size $15 \\times 15$, with a step size of $\\eta = 0.1$ for all algorithms. We present the empirical results in Figure 1 in the PDF attached to our response common to all reviewers. We found that ExRM+, Smooth and Stable PRM+ perform on par with Optimistc FTRL and Optimistic OMD, two methods that achieve the theoretical state-of-the-art guarantees for solving two-player zero-sum games.\n\nQuestion about the diminishing norm of the loss: We believe that this is simply an artifact of the proof, as we do not observe this phenomenon for our $3 \\times 3$ matrix game instance.\n    \n- We have verified this with additional numerical experiments, by computing the $\\ell_{2}$-norm of the losses faced by each player at every iteration and the minimum absolute value of the coefficients of the losses faced by each player at every iteration. We refer to Figure 2 in the attached PDF document (in the responses common to all reviewers). As you can note, we found that these two quantities become in the order of $10^{-1}$ after $10^3$ iterations but do not converge to $0$. Therefore we do not believe that a \"bounded precision assumption\" would stabilize RM+ or PRM+.\n\nFinally, you say \"_Given the connection between RM+ and OMD in [12] and the fast convergence properties of OMD in games, the performance guarantee for the stabilized variants of RM+ do not seem surprising._\"\n\n- We disagree with this framing of our paper. While it is true that [12] shows a connection to OMD, it has been an open problem since [12] whether (predictive) RM+ can achieve a fast convergence as with optimistic OMD. Whether our result is \"surprising\" or not is of course debatable (and perhaps not a good way to evaluate it one way or the other), but we do believe that this was a significant problem that had been open for a few years. Reducing it to \"not surprising due to OMD\" is too dismissive, in our view.\n    Moreover note that, in a sense, we resolve the PRM+ open problem in the \\emph{negative}, since our counterexamples show that in fact PRM+ does not achieve a faster rate. This is in spite of the fact that PRM+ is also equivalent to optimistic OMD (on a different feasible set than our stabilized variants). Only through our stabilizing ideas is a faster rate possible.\n"}, {"review_id": "JedyTP4VgU", "reviewer": "Reviewer_NRiL", "summary": "The paper studies variants of the RM+ algorithm for learning in games. They show that RM+ does not satisfy stability, which is an important property for proving good regret bounds, if all players play according to the same algorithm. The paper \"fixes\" the instability of RM+ by considering a restarting and chopping variant which stabilise RM+ and then prove O(T^{1/4}) and O(1) individual and social regret bounds respectively.\n", "questions": "1. It seems that for the restarting trick you cannot prove O(1) social regret. Is this because restarting may happen at different times for different players? If so I think you should include a larger discussion on this. Moreover in the abstract it seems like both restarting and chopping would give O(1) social regret. I think you should state explicitly in the abstract that only holds for the chopping variant.\n2. Do you conjecture that O(1) social is only hard to prove for the restarting method or that is not reached?", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "For the most part paper is well written and easy to follow.\nThe paper points to the importance of stability for proving sub-sqrt regrets bounds, which I find interesting.\n", "weaknesses": "In my opinion Sec 5 too dense and thus it lacks clarity. I would suggest to put only the main technical result there , or to give a skimmed version, in which the more technical assumptions are deferred to the appendix. I think that 4 statements with little discussion, cannot convey clarity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time reviewing the paper. We now answer your question and remarks on the manuscript.\n\n- Clarity: in the final version we will use the additional page to provide more details on the results in Section 5 (Conceptual RM+/ExRM+). This will improve the overall clarity of the paper.\n- Social regret for restarting (theory): we believe that it is hard to prove that restarting achieves $O(1)$ social regret; this is precisely for the reason that you give: restarting may happen asynchronously across players. We are not ready to make a conjecture about whether this is true or not.\n    We will provide more details on this in the revised version. We will also clarify the abstract.\n- Social regret for restarting (experiments): in our numerical experiments, we observed that restarting yields $O(1)$ social regret on the hard $3 \\times 3$ matrix game instance (see Figure 7 in Appendix K). The numerical performances from Figure 2 also suggest that this is the case for random matrix game instances. However we did not search extensively over matrix game instances to try to disprove this statement, so we do not make any claims on this matter in the paper.\n\nOverall, we would like to emphasize that our paper is the first to provide some explanations on the very strong performances of RM+ and CFR+, which usually converge much faster than their $O(\\sqrt{T})$ theoretical guarantees and routinely outperform theoretically stronger algorithms. Because of the widespread use of these algorithms (it was used in recent poker AI milestones, where poker AIs beat human poker players [1,2,3,4]), it has become an important open problem to explain their strong empirical behaviors, e.g. as mentioned in [5]. Apart from the regret guarantees in $O(\\sqrt{T})$, prior to our work virtually nothing was known that could provide a sound theoretical argument explaining RM+ and CFR+. In light of this, we would like to invite you to reconsider the importance of our contributions, which identify the instability of RM+ as a key issue for proving stronger convergence rates, and to which we propose two practical solutions, restarting and clipping, leading to state-of-the-art convergence rates and strong practical performances for matrix games.\n\n[1] M. Bowling, N. Burch, M. Johanson, and O. Tammelin. Heads-up limit hold’em poker is solved. Science,\n347(6218):145–149, 2015.\n\n[2] N. Brown and T. Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals.\nScience, 359(6374):418–424, 2018.\n\n[3] N. Brown and T. Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456):885–890, 2019\n\n[4] M. Moravcık, M. Schmid, N. Burch, V. Lisy, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, and M. Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508– 513, 2017.\n\n[5] Farina, G., Kroer, C., and Sandholm, T. (2021, May). Faster game solving via predictive Blackwell approachability: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 6, pp. 5363-5371).\n"}, {"review_id": "joK8BWUbEV", "reviewer": "Reviewer_GXrh", "summary": "The authors study $\\text{RM}^+$. They show that there are instances of loss sequences in variants of $\\text{RM}^+$ unstable. The authors point out that the decisions of $\\text{RM}^+$-based algorithms are performed by normalizing an aggregate payoff vector. Hence, if one inputs an instance that is \"close\" to the origin, two consecutive aggregate payoffs can point in different directions in spite of being relatively close, which could make the algorithm cycle between two strategies. The authors exhibit an example establishing that the potential instability mentioned does indeed occur. \n\nThe authors then present two methods to the instability discussed dealing with having two consecutive aggregate payoffs being too close to the origin. In one, they simply re-initialize the regret vector too some non-zero amount. The other solution is simply to ignore an area of the space near the origin and projecting onto that space. Not surprisingly, the second method seems to have a better theoretical guarantee but it's more expensive to implement.", "questions": "Q1: More the smooth predictive RM^+, was there anything essentially different if one uses a different threshold for $||R_1||$? Now, 1 is being used, which seems very reasonable. However, how ``far away\" does one need to know from 0 to help stabilization? Like if I were to change 1 for a constant C, how does this affect the theoretical guarantees? \n\nQ2: I must be missing something, but I don't fully understand why clairvoyant CFR doesn't seem to perform as well with EFG as it does with matrix games. If you were to use the strategic game equivalent of the EFGs tested, what is the performance. I apologize because there is probably something I'm missing.\n\nQ3: In your experiments, it seems the data was generated randomly. This is good to know. However, did you try to create data that would be more \"difficult\" like maybe a space that is an annulus?", "limitations": "The authors make an effort of what they have consider and the limitations of their work in terms of experimental results obtained for EFGs\n\nI also would like to see how the algorithm performs in \"harder\" spaces than simply random ones.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is very-well written. It was a pleasure to read. I had some very minor comments about the draft in regards to exposition and writing. \n\nI also like how natural their solutions are to the issue of instability. The proofs seem to be correct and everything feels very natural, which is probably due to the authors' writing. The experiments also seem reasonable and establish that their methods perform well with random synthetic data.", "weaknesses": "Would the authors please put their contribution in context? How \"important\" it is to the overall community? They have already addressed some of this in the draft, but I was hoping for longer explanation in the rebuttal period. \n\nSome small suggestions \n1. Generally, I think citations are not appropriate for abstracts since abstracts are often read independently of the full paper, so readers may not have access to the cited sources at that stage. If you want to include a specific reference or highlight previous related work in the abstract, I recommend paraphrasing the information or briefly mention the authors' names and year of publication without the specific citation. This maintains the abstract's clarity and conciseness while still giving credit to the relevant work. I realize adding the references simply as numbers might have done intentionally to hide the identity of the authors. \n2. I'd recommend combining the sentences for on lines 45 to 48 \"However, in a game setting...\" and \"Indeed, we identify...\" to avoid using the word \"this\" which is a bit ambiguous.\n3. Would it be possible to list the references in increasing order?\n4. For the sake of completeness, it would be useful if T were defined as the horizon or something like that before being used.\n5. Notation-wide, I think $\\Delta(3)$ should probably be $\\Delta^3$ on line 169.\n6. The definition of $\\mathbf{z}^t$ in Theorem 4.1 was a bit unclear to me until I saw it defined in Algorithm, 1. Maybe declare it before like you did for Theorem 5.1 in expression (2)\n7. On line 346, when you say \"$\\text{RM}^+$-based algorithms\" I would add in parenthesis to refer to which algorithms are meant (either by number or name)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback and valuable comments. We will revise the citations, notations, and definitions based on your suggestions. Below we answer your questions. \n\n- _How important is it to the overall community?_ Understanding how CFR+ works well in game solving is an important open question in the community. Because of the widespread use of these algorithms (for one, it was used in recent poker AI milestones, where poker AIs beat human poker players [1,2,3,4]), it has become an important open problem to explain their strong empirical behaviors, e.g. as mentioned in [5].\n    Apart from the regret guarantees in $O(\\sqrt{T})$, prior to our work virtually nothing was known that could provide a sound theoretical argument explaining RM+ and CFR+.\n    Although we don't fully answer this question, in this paper we point out that (in)stability plays a crucial role in their empirical performances. Lacking stability can ruin CFR+ in some simple examples.\n    On the other hand, from the theoretical perspective, we are the first to show fast convergence of RM-based algorithms by stabilizing the algorithms. This not only greatly shrinks the discrepancy between theory (usually OMD-based) and practice (usually RM-based), but also sets a cornerstone for developing better and more robust variants of CFR+.  \n    \n- _Different threshold for $\\|R_1\\|$:_ Changing the threshold for $\\| R \\|_{1}$ has an impact on the Lipschitz constant of the function $g$ as defined in Proposition 1, line 159 of our submission. In particular, in our algorithms, there are 2 tunable parameters: the threshold you mentioned and the step size $\\eta$. It suffices to fix the threshold and tune $\\eta$ only. The theorems still hold when changing the threshold to another constant $C>0$ by adjusting $\\eta$ accordingly.  We will provide more details on this in the final version of our paper.\n- _Clairvoyant CFR doesn't seem to perform as well with EFG as it does with matrix games:_ You are correct that Clairvoyant CFR appears to have weaker performances (Figure 3) than its counterpart ExRM+ on matrix games (Figure 2), as we also point out in the paper.\n    We do not currently have an explanation for this. However, note that it is consistent with some of the experiences for some of the other $O(1/T)$ convergence-rate methods such as e.g. mirror prox and optimistic mirror descent/FTRL in the prior literature. For those algorithms, it has been observed that they can sometimes beat RM+ on matrix games, but it is much harder to beat CFR+ on EFGs. We view this as a general open problem regarding the \"hard\" structure of EFGs that makes it more difficult to attain fast convergence rates than for matrix games. See e.g. [6,7] below for past observations of this phenomenon.\n- _Converting into strategic game equivalent:_ The equivalent strategic-form representation of an EFG is exponentially large in the EFG size, and thus not practical for most of the games that we consider (see appendix K.2 line 696 for the description of the EFGs used in the experiments).\n- _Did you try to create data that would be more \"difficult\" like maybe a space that is an annulus?_ We did not try this, but it is an interesting idea and we will attempt it for the final version. We remark that unlike extensive form games—for which established benchmark games exist—there are no clearly established normal-form benchmark games, and it seems common practice in the literature to experiment on random matrix games.\n\nWe hope that we have answered your questions and addressed your concerns about the significance of our results. \nIn light of our responses, we would like to invite you to reconsider the importance of our contributions.\n\n[1] M. Bowling, N. Burch, M. Johanson, and O. Tammelin. Heads-up limit hold’em poker is solved. Science,\n    347(6218):145–149, 2015.\n    \n[2] N. Brown and T. Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals.\n    Science, 359(6374):418–424, 2018.\n\n[3] N. Brown and T. Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456):885–890, 2019\n    \n[4] M. Moravcık, M. Schmid, N. Burch, V. Lisy, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, and M. Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508– 513, 2017.\n    \n[5] Farina, G., Kroer, C., and Sandholm, T. (2021, May). Faster game solving via predictive Blackwell approachability: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 6, pp. 5363-5371).\n\n[6] Gao, Yuan, Christian Kroer, and Donald Goldfarb. \"Increasing iterate averaging for solving saddle-point problems.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 9. 2021.\n\n[7] Farina, Gabriele, Christian Kroer, and Tuomas Sandholm. \"Optimistic regret minimization for extensive-form games via dilated distance-generating functions.\" Advances in neural information processing systems 32 (2019)."}, {"review_id": "IiKUbFR0m4", "reviewer": "Reviewer_QXqy", "summary": "The paper pushed RM+ based algorithm better than $O(\\sqrt T)$ theoretically the first time. Specifically, the authors proposed smooth RM+, conceptual RM+ and extragradient RM+ with theoretical regret guarantee.", "questions": "I'm a bit confused about the CFR part. Does CFR equipped with the new RM+ has constant social regret?", "limitations": "The authors discussed limitations in the conclusion.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "To the best of my knowledge, this paper is the first one to establish RM+ based algorithm with better theoretical gurantee than $O(\\sqrt T)$. Before, although people observe $O(1)$ regret guarantee of RM+ in *most* games (there exist counterexamples that make it around $O(T^{0.7})$), there's no variant of RM+ that has better than $O(\\sqrt T)$ regret bound.\n\nHowever, this paper proposed a really simple and straight-forward version of RM+ and proved better regret bound. This may partially reveal why RM+ and CFR+ have good performance in many games.", "weaknesses": "- The main text of the paper does not reveal much about the proof intuition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. Please see below for our response. \n\n- _The proof intuition in the main text:_ We will make sure to provide more intuition of the proofs in the final version when an additional page is available. \n- _Does CFR equipped with the new RM+ have constant social regret?_ Yes, as we mentioned at the end of Section 5, the Clairvoyant CFR algorithm that computes a sequence of iterates with regret at most $\\epsilon$ in $O(1/\\epsilon)$ iterations using $O(\\log(1/\\epsilon)/\\epsilon)$ gradient computations. Proofs for extensive-form games are in Appendix J.\n"}]

Author rebuttal:
We thank all the reviewers. We responded to each of your questions in individual comments. Here we upload a PDF of two figures to support those responses. Specifically, in the PDF, we plotted:

- Figure 1: Comparison of Optimistic OMD, Optimistic FTRL, ExRM+, Stable and Smooth PRM+ on random matrix instances and our hard $3 \times 3$ matrix game instance.

- Figure 2: Minimum absolute value of the losses of each player and $\ell_{2}$-norm for the loss of each player, for the $3 \times 3$ hard matrix game instance.

Meta-review: This paper focuses on regret matching (a standard no-regret algorithms) in games where it might become unstable. The authors nicely prove that fix a few fixes, those properties can be recovered.

All the reviewers, and myself, enjoyed that paper !
Decision: Accept (spotlight)