Stochastic No-regret Learning for General Games with Variance Reduction
Authors: Yichi Zhou
Fang Kong
Shuai Li
Venue: ICLR 2023 poster (2023)
Keywords: game theory

Abstract: We show that a stochastic version of optimistic mirror descent (OMD), a variant of mirror descent with recency bias, converges fast in general games. More specifically, with our algorithm, the individual regret of each player vanishes at a speed of $O(1/T^{3/4})$ and the sum of all players' regret vanishes at a speed of $O(1/T)$, which is an improvement upon the $O(1/\sqrt{T})$ convergence rate of prior stochastic algorithms, where $T$ is the number of interaction rounds. Due to the advantage of stochastic methods in the computational cost, we significantly improve the time complexity over the deterministic algorithms to approximate coarse correlated equilibrium. To achieve lower time complexity, we equip the stochastic version of OMD in \cite{alacaoglu2021stochastic} with a novel low-variance Monte-Carlo estimator. Our algorithm extends previous works \cite{alacaoglu2021stochastic,carmon2019variance} from two-player zero-sum games to general games. 

Published as a conference paper at ICLR 2023
STOCHASTIC NO-REGRET LEARNING FOR GENERAL GAMES WITH VARIANCE REDUCTION
Yichi Zhou
Fang Kong & Shuai Li Shanghai Jiao Tong University Shanghai, China { (f fangkknng.hhaal111@geee......
Microsoft Research, AI4Science, Asia Beijing, China
www.hhemicoosooooooooooooooooooe com
ABSTRACT
We show that stochastic version of optimistic mirror descent (OMD), variant mirror descent with recency bias, converges fast general games. More specifically, with algorithm, the individual regret of each player vanishes speed of O(1/T3/4) and the sum of all players' regret vanishes at speed of O11/T), which is improvement upon the O(1/VT) convergence rate of prior stochastic algorithms, where I' is the number of interaction rounds.
Due to the advantage of stochastic methods in the computational cost, sig- nificantly improve the time complexity over the deterministic algorithms to ap- proximate coarse correlated equilibrium. To achieve lower time complexity, we equip the stochastic version of OMD in (AM21) with novel low-variance Monte- Carlo estimator. Our algorithm extends previous works (AM21; CJSTI9) from two- awo-player zero-sum games to general games.
INTRODUCTION
How does a player in a game interact with others, and selfishly maximize its own utilities? This is central problem in online learning and game theory and has intimate connections to economics, auction design, and machine learning. The study of this problem was pioneered by (Bro49; Rob51). Robinson (Rob5l) shows that fictitious play asymptotically converges to Nash equilibrium in two- player zero-sum games. But its convergence rate is exponentially slow and may not even converge non-zero-sum games (Sha64).
Another natural choice for each player is to use no-regret learning algorithms. With some well-known families of no-regret learning algorithms, e.g., mirror descent (NY83) and folluw-the-rguularizee leader (K (KV)5), the average regret of each player vanishes speed of O(1/VT) where T is the number of interaction rounds. This regret bound implies an O(1/v convergence rate to the coarse correlated equilibrium in general games (or Nash equilibrium in two-player zero-sum games). And it noteworthy that Chen and Peng (CP20) show that these algorithms' convergence rate is Q(1/VT).
Players can do even better with some special no-regret algorithms tailored for games. The most representative one is known as optimistic mirror descent (OMD) which is variant of mirror descent with recency bias. Syrgkanis et al. (SALS15) and Rakhlin et al. (RS13) show that OMD approaches optimal social welfare (or cquivalently, minimizes the sum of all players' regrets) at speed of O(1/T) and minimizes each player's individual regret at speed of O(1/73/4). Several works (CP20; HAM21; DFG21) improve the results in (SALS15) under different settings or assumptions. Remarkably, Daskalakis et al. (DFG21) improve the convergence rate of players' individual regret of OMD to (poly log T/T) in general games.
However, the computational cost of players to OMD, well other deterministic no-regret algorithms, could be not managcable. Since each player needs to compute the exact loss vector to update its strategy in OMD. And the time complexity of computing this exact loss vector is. in the worst case, exponential in the number of players in the game. One standard method to accelerate the computation estimate the loss vector with Monte-Carlo methods. But Monte-Carlo estimator with uncontrolled variance will immediately make the convergence rate degenerate to O(1/VT).

---

Published as a conference paper at ICLR 2023
To alleviate the effect of Monte-Carke estimator's variance, Carmon et al. (CIST19) and Alacaoglu et al. (AM21) propose variance reduced stochastic no-regret algorithms with a convergence rate of (1/TT) for two-player zero-sum games. As a result, they improve the time complexity of computing <-Nash Equilibrium in two-player zero-sum games from (Cost//e) of deterministic algorithms to OCCost + /Cost/e) (some lower order terms are omitted) where Cost is the time complexity of computing the loss vector.
While Carmon et al. (CJST19) and Alacaoglu et al. (AM21) make a huge step towards developing efficient stochastic algorithms for games, their algorithms are tailored for the simplest two-player zero-sum games and could not cover more practical settings, such as auctions, which may involve multiple players and not be zero-sum. One crucial factor of the algorithms in Carmon et al. (CIST19) and Alacaoglu et al. (AM21) is a stochastic loss estimator with small variance. However, the time complexity of calculating this estimator is O(AN11) where N is the number of players, which is exponentially large in general games. The high complexity of the estimator becomes major obstacle to developing efficient stochastic algorithms for general games.
Contributions. We consider general normal-form games with an arbitrary number of players. Compared to the two-player zero-sum case, this is more challenging and practically significant. We show that in general games, stochastic version of OMD converges to the optimal social welfare (or equivalently, minimizes the of all players' regrets) at a rate of O(1/T) and minimizes the individual regret at speed of O /T3/4) in contrast to the O(1 (T) convergence rate of existing stochastic algorithms. Due to the advantage of stochastic methods in the computational cost, this significantly improves the time complexity to approximate coarse correlated equilibrium in general games, Please see Table for the comparison of the time complexity of our algorithm against prior works. Specifically, our result improves previous works for weak c-CCE when Cost 2 N A and for strong c-CCE when Cost 2 NA²/c.
To achieve the above regret bounds, we make two main technical contributions. Firstly, we extend the theoretical framework of analyzing regret bounds of stochastic OMD in (AM21) from two-player zero-sum games to general games. Secondly, we propose novel low-variance Monte-Carla estimator for general games. The computational complexity of this estimator is exponentially faster than Carmon et al. (CJST19) and Alacaoglu et al. (AM21) while the variance only slightly larger. The stochastic OMD algorithm equipped with our novel estimator achieves the above results.
The rest of the paper is organized as follows: In Section 2,
we discuss prior works related to this problem. In Section 3, we provide necessary preliminaries for games, coarse correlated equilibrium and optimistic mirror descent. In Section 4, we introduce our algorithm and present a general regret upper bound in Theorem 1. In Section 5, introduce our low-variance Monte-Card estimator and analyze its variance in Lemma 3. In Section 6, by combining the results in Theorem and Lemma 3, we present our final regret bounds in Theorem and 3, well as the time complexity approximate coarse correlated equilibrium in Corollary and 2.
2 RELATED WORK
Comparisons to existing algorithms. Table compares the time complexity of our algorithm to compute c-coarse correlated equilibrium for general games (and c-Nash equilibrium for two-player zero-sum games) against prior no-regret algorithms. The time complexity is determined by two terms: the convergence rate (or the regret) and the computational cost in each round. Deterministic algorithms (PSS21; DFG21; SALS15) converge fast, but with a relatively higher per round time complexity since they have to compute the loss in each round. Stochastic algorithms exploit the Monte-Carlo approach to accelerate the computation of loss. However, the variance of the estimated loss may slow down the convergence rate. To alleviate the effect of the variance, Carmon al. (CIST19) and Alacaoglu et al. (A.211) develop variance reduced stochastic no-regret learning algorithms. Their algorithms significantly accelerate the computation of e-Nash equilibrium in two-player zero-sum games.
Variance reduction. Variance reduction is one of the most useful techniques accelerate stochastic algorithms (see (GSBR20) for a comprehensive survey). Typically, when optimizing the finite sum problem ming F(x) = Σn" Fi(r), instead of estimating the gradient by Fz())) like Stochastic Gradient Descent (SGD), the variance reduction method proposes to use A F()) VF(w*)
2

---

Published as a conference paper at ICLR 2023
e-Nash equilibrium Two-player zero-sum
Weak e-CCE
Strong c-CCE
General games
General games
(DXSALS15) O(Cost/c)
O(N9oss)/c)
((st//oost/
(DXDFG21)
Ö(Cost/e)
O(N9Cost/e)
((N9Cost/e)
(D)PSS21)
O(Cost/c)
(ON
((N9Cost/e)
(S)AM221)
O(Cost ACCost/c)
(SXCIIT119 O(Cost v ACosttee
(S) Ours
Ö(Cost + VACost/c) Ö(Cost + N /Cost/c) OCCost Cost c478
N
Table 1: Comparisons of time complexity to compute e-CCE for general games and e-Nash equi- librium for two-player zero-sum games. Cost denotes the time complexity of computing the loss vector. N is the number of players and A is the number of actions for each player. (S) means the algorithm is stochastic and (D) means the algorithm is deterministic. For stochastic algorithms, the time complexity is the expected running time to achieve an expected approximation error, which directly follows (AM21). Ô hides factors which are polynomial terms of log(1/c) and log(A) (A).
(F(())) (w: where w* is called the "snapshot". In many cases, e.g., when Fj's are convex, sampling from uniform distribution is sufficient to reduce the variance. When dealing with games, it turns out that one has to be meticulous to design low-variance sampling distribution, even when the game is two-player zero-sum (CJST19; AM21). And remains unclear how to design such low-variance distribution for general games. One of our main contributions is Now-variance Monte-Carlo estimator for general games, which ensures fast convergence in general games.
Stochastic no-regret learning for large-scale sequential decision-making Counterfactual regret minimization (CFR) (ZJBPO7) generalizes no regret learning to games with sequential decision- making, namely extensive-form games. A long list of works study the variants of CFR (LWZB09; BS19a; ZRL+ 19; MSB 17; TBJB15) And these works lead to the superhuman AI, Libratus (BS18) for two-player and six-player heads-up no-limit Texas Hold'en em (HUNL). Since the state space of HUNL is super huge, both Libratus and Pluribus adopt the Monte-Caud CFR with external sampling (LWZB09). And the experimental results suggest that the variance of Monte-Carle sampling significantly slows down the convergence rate. Several works empirically reduce the variance of Monte-Carlo sampling (SBL+19) 19; BS19b). However, these algorithms do not enjoy any theoretical guarantees the convergence rate. We hope our algorithms could provide insights into the development low-variance stochastic algorithms for large-scale games.
and Pluribus
3 PRELIMINARY
Notation.
For any vector Rd. denote v(j) its jth coordinate, ||u||2 Σ/= |u()) as its 4n-nrmm ||u||a = / / (²) as its fz-norm, and ||e|oc maxj=1,--.d . |u(})] as its loo norm.
For general norm - let || ||+ represent its dual norm. Denote (u, w) Dd v(i)w(i) as the standard inner product of two vectors v. Rdd For positive integer let [m] (I,... n). For a discrete set S. let A(S) be the set of distributions over S.
Basics of game. We consider general games with N players. The action space of each player i E [N] is A. Denote = max; [A,] as the cardinality of the largest action space. The joint action space of all players is A AA x A2 x - AN. For simplicity, let A_; A .A; -
- .Ay be the joint action space of all players except for player i E [N]. The loss of players can be specified by the functions Fj, F2. FN A + J0, 1], which map the joint action space real value. Specifically, if each player j selects action aj E Aj. then (( is the loss of player where = (01, (2))..,nN)
X
3

---

Published as a conference paper at ICLR 2023
A mixed strategy or is a probability distribution over A, We say player p. plays according to o, if selects action a, E A:; with probability (((a)). For any strategy profile o = (d)) let 0-4 := (01,.... 1+::,-+ NN) denote the strategy profile after removing o, And for convenience, let (o,, a-)) denote the strategy profile after replacing o, with of. Similarly, given an action profile a = (at)sE(N), let a == (aI...., a4-1, ai+1...... ... denote the action profile after removing a; and (a/, a-;) be the action profile a after replacing d; with a'..
With little abuse of notation, for strategy profile o, let Fi(o) Eawo [F((a)] be the expected loss of player i if each player j [N] plays according to jj. For convenience, define the vector Fi(a=:) E [0, 1J1L with (a) = Fi((al, a-i)) representing the loss of player when each player + i selects aj and i selects af E A.. Similarly, define the vector (o(o-:) E [0, 1] E., ;~a [[af, a=:)]] representing the expected loss of player i if each player j plays according or and selects action d/. Further, denote Cost the time complexity of computing the vector :i))).
with [{(()=))(aa)
No-regret learning. In online learning, N players play the game for T rounds. In round A E [T], player i plays according to the strategy of and suffers the expected loss (F. of) Each player aims minimize its cumulative loss, which is equivalent to minimizing its regret max,, (o, :=
max., Σk=1 (Fi(o".) of - o2) where (o,))) is the cumulative loss difference between the adopted strategies and the fixed strategy o;-
Given the strategy at round I,.... k, the optimistic mirror descent (OMD) (RS13; SALSI5) method calculates the strategy in round k + 1 as:
arg min D(o D(or,aktt)) ) where Vh(ap (((()))(((((())) P((=""))) (1) o.EA(A.)
where is the step size and D(z, y) is the Bregman divergence induced by some miror map h(-) Without loss of generality, we mainly consider two common mirror maps in this paper: negative entropy (z) = Edm xxx)a((())))))))))))( x(a) and squared 42-norm h₂(x) = -
- x² (a). Their corresponding Bregman divergences are Dj (1( v) Ed= s<a) (og(x(a)/v(a)) and D2(1, (x(a) - y(a))? respectively. Our analyses apply to other mirror maps as well.
Coarse correlated equilibrium (CCE). A correlated strategy ( is a distribution over the joint action space A. We call (a a coarse correlated equilibrium (CCE) if no player can benefit from unilaterally deviating from Ç given that others take actions according to Ç. There are two versions of approximate CCE: one corresponds to the social welfare and is referred to as weak e-CCE; the other corresponds to the individual loss and is referred to as strong e-CCE. Intuitively, weak e-CCE states that the averaged difference among all players i E [N] between the expected loss Ea-c [Fi(a)] by following and the least expected loss mina; Ealç [Fi((a], a=:)]] by deviating from Ç is more than And strong e-CCE requires that the maximum difference among all players i E [N] between these two types of expected loss to be smaller than e. The formal definitions are as follows.
Definition 1. A correlated strutegy Ç is a weak e-CCE (corresponding to social welfare) if
Eagui [F((a)]
min Eaws [Fi((a], -.))) [F(((a),a)))] Se
aj
and it is strong c-CCE (corresponding to individual loss) if
Eawş [Fi(a)] min Banc [Fi((a) a. ([(aa)aa.))) cc.
[F(((a):
max [E[N]
of
Here for convenience, we simply multiply the average difference by N as the sum over all players in the definition of Weak 6-CCE Thus a strong c-CCE is weak Nc-CEE. Strong- CCE ensures that each player will not suffer a large loss, and Weak-CCE guarantees the con- vergence to the global optimal strategy within a large class of smooth games (SALS15). Since
h: Rd R is called mirror map if h is strongly convex with respect some norm and Vh(R") = Rd.
4

---

Published as a conference paper at ICLR 2023
this work mainly focuses the stochastic method, study the expected performance of the generated strategy. Specifically, randomly generated correlated strategy Ç is called weak e-CCE if Σ (Eçans [i(()] - mina; Bssa-s [ (-)))) S and strong e-CCE max (Bg,ass [F((a)] - mina; Rssanss [Fi((a), a-:))] Σ 6, where the expectation is addi- tionally taken over the randomness of the generated strategy Ç.
Connection between no-regret learning and CCE. connection between no-regret learning and CCE. Lemma 1. Let ot,... ,-,"" denote an arbitrary collection of strategy profiles and ((a) = E II (a.). It holds that
The following Lemma shows a well-known
Eanç [F((a)] min Eans Fi((aa), a.:)) S max R.ooR.//TTTWEEEE a;
Lemma shows that the running time approximate CCE depends both the regret and the running time in each round. Deterministic algorithms,, such as OMD, though enjoy excellent regret bounds, take a long running time for computation in each round. In the next sections, we will show how to use the Monte-Carlo method to accelerate the calculations without significantly hurting the regret bound.
4 OPTIMISTIC MIRROR DESCENT WITH MONTE-CARLO ESTIMATION
In this section, we present our algorithm. We first introduce some necessary notations. Let (a-;) = [((o=:)o-((a-)//0000 where a-; A-; denotes random variable drawn from a sampling distribution 9-i-
The algorithm is presented in Algorithm I, which is a stochastic version of OMD shown in equation 1 with variance reduction. There are two crucial modifications over the vanilla OMD to accelerate calculation: one is the estimated loss and the other is the update starting points.
Algorithm Optimistic mirror descent with variance reduction
1: Input: hyper- pepeer-prrametes p, and mirror map h.
2: Initialize: wi (a) = 1/A and af (a) = 1/A
3: for k = 1, 2, ... T do
4: Sample u from uniform distribution over [0, 1].
5: for 1,... ....N do
6: Compute of such that Vh((k) aVh(at)) + a)Vh(u?).
7: Sample a= LVE(i, a w²-1). (See section for the definition of LVE.]
8: Compute / such that
vh(oktt) Vh(ot) -00---(FF T(F((u"))) + Fiat, (0 ) Fratt, (w
9: Compute of arg min,, D(ai, 1,t11
Update w. A-1 of gi+1 if u and wit wi if 2p.
11: end for
end for
Estimated loss. As can be seen Line 8, Algorithm 1 updates the strategy using the estimated loss F((wE,) F (of,)
- Fiot (w= instead of (F - F((a"=1) in the vanilla OMD equa- tion By constructing appropriate distribution q-; sample a²,, (Line 7), it can be shown that the adopted estimated loss Fi," (ot,) - Fiat (w-=1) where F. Ft.o., (o_ F ((o_))o_(aaa)/((_) and a-; q-i in the algorithm is an unbiased estimator of F,(o ( in the vanilla OMD. The objective to introduce such estimated loss is reduce the computation complexity. Since *+1 only updated with probability p at each round (Line 10), the running time to compute (((wE, over T rounds is just O(pTCost) It is also worth noting that such estimator may bring high variance. So how to construct q- to accelerate convergence while ensuring low variance is the key innovation of our algorithm. We postpone the deseriptions and discussions this estimator Section 5.
5

---

Published as a conference paper at ICLR 2023
Different update starting points. As in Line 8, Algorithm 1 updates of k++1 from the starting point of instead of of in OMD equation 1. This modification was first introduced by (AM21) 1) for two-player zero-sum games. We prove its effect in general games is to admit a faster learning rate in the case of maximizing social welfare. The detailed proof for this part can be seen in the full analysis.
remarkable that under special settings syper-parameters, our Algorithm degenerates to standard OMD (SALS15) and stochastic OMD for two-player zero-sum games (AM21). Specifically, when setting p 1, equivalent to standard OMD (SALS15). And when the underlying game is two-player zero-sum, our constructed unbiased estimator for F. - F((w=,)) is equivalent to that (AM21) and thus Algorithm can also recover their stochastic OMD.
and using the exact value of F. (="""")) in Line 8, Algorithm 1
In the following, we show how to compute o++1 by taking two common examples of the mirror map function: negative entropy (x) = > x(a) logx(a) x(a) and square of 6--norm (x) (a). When the mirror map is h1, it is easy to verify that Vz(a)/((2))
log z(a). Then
according to Line 6, (a) = (of( (w)( (a)) So we can update k+1 in O(A) time as
(a) x (a)))
exp (-T(F((w(,) Featt (o
Fi,at, (w ((a)))(aa))))))))
Similarly, when the mirror map is h2, we can directly compute o (a) aot (a) + (1 a) a)w; (a). The computation of *++1 is easy according to the gradient of the f--norm and a can then be obtained by standard procedure of projecting o. k++ to the simplex.
4.1 THEORETICAL ANALYSIS
We first provide general regret upper bound for Algorithm in the following Theorem 1. The final results (Theorem and Theorem 3) will be postponed in later sections by combining this general upper bound and the variance upper bound for the unbiased estimator in Lemma well some delicate derivations.
Theorem 1. If D(x.v) 2 7/10 yll for all x. and some norm then the expected regret of Algorithm / upper-bounder by
with y > 0 being constant,
T
(o w 11
T max E [((o;)] SU- - (1- Σ
D
+ + (1+
T
Piat (oti)) - Pire ))?
(3)
ar
where U₁ = maxo, E (1,)) ( + maxo, D(or, o 0², w are uniform and
(o.) =aD(o, oft (1 aa)pp D(a,, w + D(oot w
+T(F((ot,) F ),,0, -
(4)
Due to the space limit, the full proof of Theorem is deferred to Appendix A.2. To obtain the main order of the above general upper bound, we first bound U,. i.e. the first term in equation 3. According to the following Lemma 2, is easy to see that U, is of order Ô (1 + + (1 a)/p). O(1), would have U, Ó(1).
When adopting hyper- parammersssssrss such that 2 1 p and Therefore, the key to bound the regret in Theorem is to control the variance of the estimator, i.e.,
the third term in equation 3, which will be completed by our estimator introduced in Section 5. Lemma 2 (Bounds for Φi defined in equation 4). For any k and d;, Φi (a,) 2 -4.. If the mirror (a) 1/A, then of (o+) I 47 + (1 + a)/p) (p) log A. If the mirror map is h and w (a) 1/A, then (a:) < 4T 2(1 + (1 o)/p).
map is hy and w
5 Low- VARIANCE MONTE-CARLO ESTIMATOR
In this section, we present our low-variance estimator for (i(o_;) (w where a and w are two strategy profiles. For convenience, assume f w. It is standard to importance sampling

---

Published as a conference paper at ICLR 2023
to construct unbiased estimator. Specifically,, let q-i denote distribution over A-; such that q-i(a-i) = 0 only if a-i(a-i) and w-i(a-i) O. Recall P.a_.(0-1) = (a
-_)(e-)) g(a
Clearly, we have Ea Ea- ; E.., F((a-i)o- = (o-
Therefore, (o (w_).(w_.)) an unbiased estimator for (o- Fi(w=;) when a- ~ Q-i. However, for an arbitrary q-i, the variance of the estimator can be very large. For example, let 9-i denote the uniform distribution over A-i. Then, in the worst case, the variance of (a
F can be A So we need to carefully design 9-s to ensure low variance.
is upper bounded by Intuitively, to control the variance, should allocate large probability mass to a-i where (a-i(a_<) w-i(a-;)2 is large. With the observation that the difference between a-i(a_i) and w-i(a_i) can be decomposed as (a) w(a) (o=(oo((.)) wy(a:)) II (z(ax) Iyys wy(ay) (sce Lemma 10 for more details), we propose to sample a according to the following distribution:
Note the variance Ea_rag- Fa, (a-:) (w (.. (o-i(a))) - w-; /a-((a))///-(aa))
1 q-i(a-i) Ex Zz
(oy(as)) wy((a))
II
(2(ax)
II wy(ay), w>int4
(5)
where 2, -a, loy(a)) wy w)(a)) is easy verify that q=i(a=;) 0 and Ea q q-1(a_.)
The following Algorithm 2 summarizes an efficient sampling procedure from q-i in equation with polynomial time complexity O((N - 1).A). It takes two main steps to sample a-;. Firstly, we sample index j with probability / Ey Zy (Line 1). And then, we sample a-; with probability proportional to lay(a,) - w,(a,)) II II on (a²) Iyyisv my(ay) (Line 3-5).
Algorithm 2 LVE(i, a, W)
Compute Zj E., [oy(a,) wy wy(a;)) for # 2;
2: Sample j with probability Ej'r: Z,'
For 1 j < j.J # i, sample ay according oyy
4: Sample a, with probability Enj (o,(0))-
5: For j & N ii sample ay according to wy.
6:
return a
The following Lemma provides an upper bound for the variance of the constructed estimator in equation 5. We believe this result is also of independent interest since it is quite general and may be used control the variance of other stochastic algorithms for general games.
Lemma 3 (Variance bound). Sampling a_ ~ q-s defined equation 5 can be implemented by Algorithm 2. Moreover, we can upper bound its variance by
Ea_iog_ (o_.a_..o. Fw.
$ (N- 1) Σ 10, - w,
(6)
jyti
Proof. According to the definition of q-i, the variance of the estimated loss is
Ea-ing-i [iaaa - Fia., (w )w < [loo_ - - w=((a=))) /q-i(a.)).
Further, recall that the difference between (a) and w(a) can be decomposed as EN (a;(aa) wx((:)) Ilees (2.a) II Iyy>: W.y (a,,) Lemma 10 (Please see appendix for the statement and proof),
II Theorem I, we consider the general dual norm the mirror map h2 h2, the dual norm
||- ||+. Here, we only upper bound || || because when
|| |loo
|| ll2 S vAll |loc, respectively.

---

Published as a conference paper at ICLR 2023
it holds that
Σ
0 (aa()))) - w (a) /a-aa-a)///-ll /q-i(a_;)
8-1
2 /9-i(an))
Σ
Σ (5y(ay) my(a,)) II (2(ax) II wylay)
2 /a-s(a>>)
Σ 0: (o:(a)) - wi(ai)
Oz (ax)
II uy(ay)
4-1
Σ 2
Σ
Σ (o.(a)) w;(a,))
II (a()))
II V>inti
wylag)
j/i
Σ jzt
$ (N - 1) Σ 1o, wylR Zj
jti
Discussion on the optimality LVE There are mainly two aspects examine the optimality of a Monte-Carlo estimator: the variance and computational complexity.
Variance: is obvious that the smallest variance w==(a==))² achieved by CISTI1 (CISTI9). Then, after noticing that q-i(a-i) > (a_)) lo-:(a-)) wa:((-)))// of our estimator is optimal within multiplicative factor N according Lemma 4.
q
1), the vari-
Lemma 4. For any a and w. we have the variance of estimator with q from equation is no more than (N -
w=)(2_:)l)?
Computational complexity: The computational cost of our LVE is also optimal among estimators with low variance. Intuitively, the time complexity of LVE equals access each entry of of and Wy k-1 for constant times, and it is unlikely to be improved. The following lemma formally shows this.
Lemma 5. We say is agnostic to q'=; if there are at least two entries of aj are not accessed when computing d'v.. Let m denote the number of j which is agnostic q'_.- Then, there exists a and w, the variance of the estimator is ()2
It is remarkable that though the estimator of (CJST19) achieves the smallest variance, its compu- tational complexity is ([A[[~1) to access every configuration of a-; to compute (a=i(a<<) w-:(a=;),, which is impractical in general games with multiple players. Our LVE estimator simulta- neously guarantees Jottimal variance and computational complexity.
REGRET UPPER BOUNDS AND TIME COMPLEXITY TO APPROXIMATE CCE
Now are ready to provide final guarantees reach weak e-CCE which corresponds social welfare and strong e-CCE which corresponds to individual loss. In addition, we also provide an adversarial regret bound of O(vT) to show the robustness of our algorithm.
6.1 SOCIAL WELFARE
We first consider the time complexity to reach a weak eCCEE For this case, we take the mirror map hi (x) = E (r)a log (a) as an example. Recall that Lemma shows that the time complexity to approximate CCE depends on both the regret and the per-round running time. So first provide an upper bound for the regret Σien maxo, E [[(a,) defined in weak e-CCE.
Theorem 2. Let hyper-parameters = p. (0, 1/2) be a constant and the mirror map be h1. Then there exists constant C such that max, E Σ 1= Ra(o.) < CN2 log A/vp.
1) + an), 7 e
8

---

Published as a conference paper at ICLR 2023
With the above upper bound, can then guarantee the time complexity reach weak e-CCE. Corollary 1. With N NAjCost and the hyper-parameters defined as Theorem 2, the time complex- ity of Algorithm to reach a weak e-CCE is O (Cost + (07/2/ACosi log A/e).
6.2 INDIVIDUAL REGRET
In this subsection, we provide the time complexity to reach strong e-CCE, As previous analysis, we will also first give the upper bound for the individual regret. Here we take the mirror map h2(x) = - x² (a) as an example.
Before providing the upper bound for the individual regret, first present useful lemma bound the term B |1a} w + appearing in the general upper bound in Theorem 1.
I|
Lemma 6. If the hyper- paper--arameter a then E
|1o} w 12 S 27 2T
With Lemma 6, we now provide an upper bound on individual regret.
Theorem 3. With (A (2 (N -N 1)8T/D2)
-1/1
1,7E (0, and mirror map ha,
we have maxo, E [R(o:)] 0 (A(N 1)2T/>²) 1/1 for any [N].
The above individual regret upper bound in Theorem 3 implies the following time-complexity to reach a strong e-CCE.
Corollary With p = NA/Coss and the hyper-parameters defined in Theorem 3, the running time reach strong e-CCE O (Cost N ACost ye/s). /(43))
6.3 ADVERSARIAL REGRET
While this work mainly focuses the case that every player adopts the same algorithm to optimize its own strategy, it also interesting to consider the case where some players play adversarially, i.e., player j who updates o and w k-1 adversarially, to see if the algorithm is robust. According to Lemma 3, we have
Ea_rgg [iFia, - (w S (N 1) Σ lo, jØL
- w,ll < N(N -),
1),
which also holds in the adversarial setting. Then, inserting this inequality into Theorem and with standard derivation, have O(VT) adversarial regret which is formally presented below.
Lemma With the mirror map fuz a = T NVT and 7 E (0, 1/2). if player follows Algorithm I, then for any of w . i, = 1, .... T, we have [R(a,)) = O(NVT).
7 CONCLUSION
In this paper, we propose a stochastic version of OMD with variance reduction. Our algorithm extends prior works variance-reduced stochastic algorithms from two-player zero-sum games to general games. The key innovation of this work is a low-variance Monte-Carlo estimator. In comparison with the prior estimator in (CJST19), our estimator exponentially fast with slightly larger variance.
There are several directions to extend our algorithm: Firstly, despite our algorithm enjoying enjoiigg an O(1/s) convergence rate to weak-CCE, its convergence rate to strong CCE is (11/4/33 which seems to be sub-optimal in comparison the convergence rate in (DFG21) and (PSS21). Thus, developing stochastic algorithms with an O(1/e) convergence rate to strong-CCE is an interesting direction; Secondly, we only consider normal-fore games. However, is more realistic consider games with sequential structures, e.g., extensive-for games. We hope this work could be starting point for developing more efficient stochastic algorithms for general games.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
Shuai Li is supported by National Natural Science Foundation of China (92270201, 62006151, 62076161) and Shanghai Sailing Program. The underlining research carried out in this paper is not part of any projects funded by the National Natural Science Foundation of China.
REFERENCES
[AM21] Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. arXiv preprint arXiv:2102.08352, 2021.
[Bro49] George W Brown. Some notes on computation of games solutions. Technical report, RAND CORP SANTA MONICA CA, 1949.
[BS18] Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):441 424, 2018.
[BS19a] Noam Brown and Tuomas Sandholm. Solving imperfect-information games via dis- counted regret minimization. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 1829-1836, 2019.
[BS19b] Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(64566)885-880, 2019.
[CIST19] Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. Advances in Neural Information Processing Systems, 32, 2019.
[CP20] Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 33:189900 8990-18999, 2020.
[DFG21] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-
regret learning in general games. Advances in Neural Information Processing Systems, 34, 2021.
[GSBR20] Robert M Gower, Mark Schmidt, Francis Bach, and Peter Richtárik. Variance-reduced methods for machine learning. Proceedings of the IEEE, 108(11):1668-1885 2020.
[HAM21] Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learn- ing continuous games: Optimal regret bounds and convergence to nash equilibrium. In Conference on Learning Theory, pages 2388-2422 PMLR, 2021.
[KV05] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307, 2005.
[LWZB09] Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. Monte carlo sampling for regret minimization in extensive games. Advances in Neural Information Processing Systems, 22, 2009.
[MSB+17] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence heads-up no-limit poker. Science, 356(6337):508- 513, 2017.
[NY83] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[PSS21] Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Optimal no-regret learning in general games: Bounded regret with unbounded step-sizes via clairvoyant mwu. arXiv preprint arXiv:2111.14737, 2021. 2021.
[Rob51] Julia Robinson. An iterative method of solving a game. Annals of mathematics, pages 296-301, 1951.
10

---

Published as a conference paper at ICLR 2023
[RS13] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
[SALS15] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast conver- gence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
[SBL- 19] Martin Schmid, Neil Burch, Mare Lanctot, Matej Moravcik, Rudolf Kadlec, and Michael Bowling. Variance reduction in monte carlo counterfactual regret minimization (vr- mccfr) for extensive form games using baselines. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 2157-2164, 2019.
[Sha64] Lloyd Shapley. Some topics two-person games. Advances in Game Theory, 52:1-29, 1964.
[TBJB15] Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads- up limit texas ho.d'em. 2015.
em. In International Joint Conference on Artificial Intelligence,
[ZJBP07] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. Advances in neural information processing systems, 20, 2007.
19] Yichi Zhou, Tongzheng Ren, Jialian Li, Dong Yan, and Jun Zhu. Lazy-cfr: fast and near-optimal regret minimization for extensive games with imperfect information. In International Conference on Learning Representations, 2019.

---

Published as a conference paper at ICLR 2023
A PROOF
Our regret bounds are derived from the following first-order optimality condition which is according to the update rule in Line in Alg. 1. We have
[V((ott)) Vh(āā ',,; -
(Vi(o,+)) ) + ((P((w
+ Piaat, (o=2)) Fraat, (w o; - ,.
(7)
Adding 7 rFFi(o ((((o))))) of k+1 σ,) to both sides of equation 7, we immediately get an upper bound on the regret.
T(B(o k+1 os)
Vh(o,), -o 1111) + +F(((wEE,) + Fi,at, (ot - Fraat, (w (w F ) o.tt)).
The rest of our proof starts from equation 8.
A.1 USEFUL LEMMAS
The following lemmas are useful in the proof of Theorem and Lemma 3.
Lemma 8. Define Eg El-lo* w==1 '1. Recall = + (1-o)))))))))))))) = Vh((w() and
(T,)) aDa(; of +
a D(a,, w ++
have of(0,) - -ot+)(o))
ottl) 1 Ex D(o,,u, w(tht]] + t +
=(Vh(o,,t) - -
(1- - a)D - 1 d(t))
p
1 1-a DDo, uf + + T(Fi(oE.) B(w -of)
P
Proof.
We can decompose (Vh(o Vh(o,), of follows.
(Vi(o,tt) - V,(ot), o =a(Vh(ofth)
+ (1aa/// - vn(w)),,,- - dtt))
=a (D(o.. D(o,tt1 oft) - -(a,,
+1--a) D D(0 wut )- - D(or,
(D(on 1ooott1,000 ((o,,ott1)
(1 - a)
W( -( D(o,+1,, 1oght11,u wtt)
- of
1 1- a Es
D(os, "; ((t1) 1-a Es D(as. w
+
(a((onot) + 1-a D(o,, (()) - (aD(on ott1) + 1 1--ap
Ex Dio,,
w ((o,
aD(ott1 ,tt) -01 - (( k+1 w
(aD(onot) 1-a D(a,, w + - a wi
p
(aDios. k+t 1 a Es aD(ottl ott) Doo)
D(on witn - (1 - (L)ootttttt... .ut))
12

---

Published as a conference paper at ICLR 2023
where the first equality is based on the fact that = +1 a) V)(()))) ), the second one is based on the definition of the Bregman divergence, the fourth one is according to the updating rule w +++ (Line 10 in Alg. 1) and the third and the last equality holds obviously. Further with the definition of of we complete the proof.
Lemma 9 (Lemma 3.5 (AM21)). Let {F* be a filtration and (u²) be stochastic process adapted F with Blu | = Then for any zo and any compact set
K
K- Σ
E
max ZEC
Σ
(u
k+1
x))
S
max D(x, ZEC
B
I|u
k=0
k=0
Lemma 10. For any a(a)= (5a;), [1 wy Wz(a;), have
N
(aa) w(a) = > (o.(a.)) w;(a))) II (a II wyy(ay)
(9)
Proof. We prove this lemma by mathematical induction. The case when holds obviously. Further, assume Lemma 10 holds for N 1, then for N, it holds that
N N II o, - II wy(a,) 3=1
j=1
N-1
N-1
II (a,())) wN(aN) II [,(a,) uN(aN)
II (,)
II wy((a)
N-1
N-1
-
=(ox(aN) - wx(aN))
II (y(م +
03 (a))
II j=1
my (a,)
1=1
(a,(a)) wi(at)) II
oz (ax) II [wy(ay).
1=1
2<1
y>
A.2 PROOF OF THBOREM 1
D(x, y) 2 >|1 2 Summing equation 8 over & = 1,... T, applying Lemma 8 and taking expectation both sides, have
13

---

Published as a conference paper at ICLR 2023
(B - ,, k+1 oi))
max d
max d,
(o())) - (o:) + T T(Fs (o=h.)= Fiat, (wir²), of
-I(((o Fi (u )); - ot (a1 (1- w aaD ,of))
1
a Es ((o
-1--=1100 D(os, w !
p
p
S max E
(0:))
0 (0:)
di
T
+ max E
T( (F
(1aaat((==1)) (0_h)) - P. Prott (w==T)) - (B(oLt) - -B((u=))) oz - of
T(Fi,dt, (oth)) - Feat, (w "u )o - of ((1 (1-a) D(o + aD (o)+t))))) o
+ max E
T
Dior, u ( )]
+ max E
Σ
a Ex Olorw 1 1-a
p
2
(o:)) 0 (
S max
a
T
+ max E
T (Fr.at (o - Proot (w - (B(o - =((==(1)) oi of)) oo
(1-a) 101--((1000))))) + +DDoott .ot))
+ E
α77 Fiat (o=.)) - -Frot ( >>? + anllo,tt - 10312-(15)
< max (a,)) 05 [
+ max E
Σ T T(Fratt, (o Frios, (w - (Fr(ot.) - F((W"( o) of:)
Fiat (oth) - Fratt, (w= 1112 - (1 a)D( onf 1
+ E
a7
3
S maxx E (o((o)) 05 (o:)) + max D(o + +
Σ
[ aa (0t,)) - Fraee (w
+E E
| (o - Frot (1- w
(1
< max E (0))))
0f (oi)) + max D(o,
-(1 -IE
Diof wa 1) Σ
+ + (1+ 11+
1
E Σ Faaa (0th) (wtz ,
ar
14

---

Published as a conference paper at ICLR 2023
where ! is based Lemma 8; 2 is according to Young's 's inequality and 3 is derived from Lemma
B MISSING PROOFS
Proof of Lemma 2. The lower bound follows directly from the non-negativity of Bregman divergence D(r, y). The upper bound of of for hy is based on the fact that maxe, D(o;, w/) = log A when w (a) = 1/A. And the case of h2 can also be proved in a similar way.
Proof of Theorem 2. When the mirror map is (1) Σd= z(a) (og) it is known that D(z, y) 2 ||æ yIl and the dual norm is Ilae. Thus direct combination of Theorem and Lemma yields that
max E [Ri(or)] 36
SU: -0 (1-
Σ Diot u 1
1
+ (N - 1)7² 1+ an
E
1105
112
(10)
juts
Further, summing equation 10 over i = 1,.., ...
N, we have
N
N
T
Σ max
[R((:s)] S Σ
U
1 0
E
Σ
k
w
117
ai
2
1=1
i=1
N
N >
+ (N 1)
(1
E
Σ
1
w
1
U.
ary
when adopting mirror map h1- By choosing a = p and y E 1/2), we can see that there exist constants C, C' such that
Recall that Lemma 2 shows U2 is of order O ((1 - a) log A/p spp+ +
EN max E [[:( < C'N (1 + log A/T) s CN2 log A/Vp.
Proof of Corollary According Theorem 2. to arrive a weak e-CCE, we need to run Algorithm for T = (C'N A) / (EvP) rounds. Recall that the per round time complexity is OppNCoss 2 A). Then the total running time is O(Cost + (pNCost + N2 A2 A/(c/p) O(Cost
N7 / Aogst A/e) with p N NA/Cost
Proof of Lemma 6. With a 1, it holds that
E llo - |7]
-E
Probfu k- ojlloo ofl
Σ p(1 - p) k- - 110 - of
k-
Σ p(1 p) b- 1-1 t)222 s 22721p²
1=1
Proof of Theorem 3. When the mirror map is h2(2) = -
(a), is known that is D(x, v) ||1 2112 and the dual norm is l12. Combining the results of Theorem 1, L.Lmmm 3, Lemma
and the fact that FF (o - Fi,at (w==1)) < VAI a,at, (ot,) Fr,tt (w Moos we have
max E (((a))) < U./++ 27 (2 1/7) (N- 1)2T/p?
0,
15

---

Published as a conference paper at ICLR 2023
And Lemma 2 implies that U, 0(1+r) a Let (A (N (N-1)///7)-111 we have
max E [ = = (11-) 1/4
Proof of Corollary 2. According the upper bound in Theorem 3. it needs T = O((A(N 1)/p) 1 rounds to reach an expected strong e-CCE. Recall that the per round time com- plexity is OppNCost + N2A). A). Thus the expected running time is
o (Cost + (A(N 1)/p) 1/3 E4/3 (pNCost- (oCCost=~23]]] N²A)):
By replacing p with A//Costt, we can conclude that the running time to reach an expected strong
e-CCE is O Cost + N7/3 A2/3 /4/8))
Proof of Lemma 4. Recall
q-i(a-i)= = Ej'rs Z3 jti
-los(aj)- - wy(a;)]
II (2())) II wy(ay) センプØサşi
and
CISTI9 9-1 (a_i) (o_ w w_ila_.)) Σ
l0_1(d=;) w w-i(d'-)l.
a',1
We have
Ee,, lo_s(a",)) - -w-(a'i)) Eists los(a,) Wn w,(a,) IIs (x(ax) Aysssats Wilaa) lo-i(a-i) w (wi("=))
(a,(a_;)
9-1
CISTI9
(a_i)
Ex Pzg Ev, lo_1(a-;) -w E5tt)((a)) - wr(az) IIreja Oz(an) II Iyyiioss wy(ay))
Egeti Zy
(o_((a)) - w_,(a_;)l
Ed' lo- - -w -w=ila=i)
Ept:
where the last equality is according to Lemma 10. Further, let a-i,- denote the action profile after removing a; and aj. we have
Σ
Σ>
[oy(a,) wy(a;))
371
j7i 0
ΣΣ Σ
jti dj
d-i,-
Σ
- w (0
J 2j a-i1s
Σ Σ
(a-=(a-<) ---(a_;))
i
(N - 1) Σ
(a_=(a_,,) w w-aaa.))
a_
Therefore, we have
q la .) 7 (0sli(aa (a_1)
2 1/(N - 1). And the variance of our LVE estimator can be bounded
as
Σ - / (q-)(--;)
3
S(N - 1) Σ (o- - w=>(a=)) -aaoo-))w--(aaaj
/ cisl9 (a = (N 17-11 -)( lo (==(a_>) w iia
We finish the proof.
16

---

Published as a conference paper at ICLR 2023
Proof of Lemma 5. Let AG denote the set of agnostic j. If j is agmostic to g',;- assume oJ (2y for all aj which has been accessed by q'g.. We further assume of = wy for j' & AG. Then we can construct equivalent game G with |AG] + 1 = m + 1 players and AA = 2", Moreover, g'=; does not know any entries of a-;- Then for w==(aa;)) = 1/2 and s'i., we have
(a w wliaa i)) / /0=i(ams)
max
a
(1 - w-i(a_i)) 2 /g-i(a=;)+ + E
w (d'( q-i(d'-))
2 max
a-1
a' ita-
2 w-i(a_i) pーv(a-;)
w
=max
a- g-i(a-s)
g-i(d'2))
22 22
17


Reviews:
[{"review_id": "etbu4U_zifH", "reviewer": "Reviewer_ZKef", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studied a notion of variance-reduced stochastic OMD for multi-agent general-sum standard games with an improved convergence speed over prior stochastic methods. The methods show improved convergence complexity over deterministic algorithms, especially when computing the full loss vector for each player is expensive. The method is a nontrivial generalization over the previous two-player zero-sum variance-reduced methods which uses Monte-Carlo estimator to deal with the challenge in high-variance of previous estimators due to the potentially large number of players.", "summary_of_the_review": "I think this is a technically nice paper that studies an important problem for stochastic OMD for multi-agent games. The authors clearly state their contribution and point out the future work in their main paper. Due to these reasons I recommend acceptance of the paper.", "strength_and_weaknesses": "I think the paper studies a natural and important problem, the presentation is clear and the results look sound to me. I have greatly enjoyed reading this paper. I only have a few minor comments:\n\n1) When presenting the table for comparison in time complexities, it may be helpful to highlight in which regime the first time in your complexity bound will directly dominate? And for what threshold of cost will your method offer improvement over prior ones? It may also be helpful to r remark that your method actually recovers two-player zero-sum case in prior work. Out of curiosity, I also wonder would a purely stochastic method (without variance reduction) work and be favorable here?\n\n2) In section 5, it may be helpful (if you know about it) to remark a bit on the optimality of your constructed estimator, in terms of variance and computational complexity.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "bMQW74lB9E", "reviewer": "Reviewer_nWqn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors in this paper provide an algorithm which is a stochastic variant of OMD, that converges in the expected sense to a weak and strong $\\varepsilon$-CCE. This is done by bounding the expected regret of the algorithm by, extending the\ntheoretical framework of analyzing regret bounds of stochastic OMD in (Alacaoglu and Malitsky 2021)  from two-player\nzero-sum games to general sum games. In addition, they propose a low-variance Monte-Carlo estimator\nfor general sum games and the computational complexity of this estimator is only $O(A(N-1))$, where $A$ is the number of actions and $N$ is the number of players in the game, whereas previous works (Carmon et al. 2019) and (Alacaoglu and Malitsky 2021) analyze the stochastic variant of OMD for two player zero-sum games.\n", "summary_of_the_review": "Overall, I think the paper tries to address an interesting direction to understand stochastic variants of OMD algorithms for general sum-games and its convergence to CCE's. ", "strength_and_weaknesses": "Strengths:\nThis paper extends the idea of using stochastic methods for learning the CCE in normal form general games and show convergence in the expected sense to a weak $\\varepsilon$-CCE and strong  $\\varepsilon$-CCE This requires a new low-variance estimator that is different from (Alacaoglu and Malitsky 2021)  and (Carmon et al. 2019). This matches the time-complexity in (Alacaoglu and Malitsky 2021)  and (Carmon et al. 2019), when its a two player zero-sum game and when dealing with $\\varepsilon$-Nash equilibrium. For general games the time complexity for convergence to a weak $\\varepsilon$-CCE is arguably claimed to be faster than (Daskalakis, Fishelson and Golowich 21).\n\nWeaknesses:\nThey mainly analyze the expected regret with a stochastic algorithm, whilst (Daskalakis, Fishelson and Golowich 21) analyze the actual regret, albeit they have a deterministic algorithm. In my view, the time to converge may not be directly comparable as it is currently done in Table 1. However, one can see this is an extension to papers like (Alacaoglu and Malitsky 2021) and (Carmon et al. 2019), which is focused on the general-sum game setting.\n\nIn addition, in the algorithm, all the players seem to have a shared random bit. Do the authors think it is possible to overcome this? \n\nOne minor comment: In Line 6 of the Algorithm 1, it says compute $\\hat{\\sigma}^{k}_i$ such that... But nowhere, is the actual $\\hat{\\sigma}^{k}_i$ used and all the proofs mainly require the gradient, which is the term on the right hand side. I think it might be better to say that we compute the gradient of h, than the actual estimate $\\hat{\\sigma}^{k}_i$. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "GAH7b67FpA7", "reviewer": "Reviewer_pnEU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies regret minimization in general-sum finite games. Such guarantees directly translate into the ones on convergence rate to approximated coarse correlated equilibrium. The main contribution is a stochastic version of the optimistic mirror descent algorithm that allows to achieve smaller regret (in expectation) within a given computational budget. In particular, a SVRG-like variance reduction mechanism along with a tailored sampling distribution are the key components that enable the improvement.", "summary_of_the_review": "Overall, I believe both the variance-reduction and the sampling algorithms are valuable (in terms of novelty, the former is a rather straightforward generalization from the two-player case while the later requires non-trivial modification). I thus recommend acceptance of the paper.", "strength_and_weaknesses": "**Strength**\n\nThe paper brings variance reduction into general-sum games and shows promising results in computing a CCE more efficiently. This seems to be a worthful attempt on the road to addressing more complicated games in a efficient manner by incorporating stochasticity.\n\nThe main algorithm construction and the design choices are clearly explained, modulo some minor points that may hinder the understanding (as listed below).\n\n**Weakness**\n\nI don't think there are any major flaws. Here are a few typos and minor remarks that I think should be addressed.\n1. In the caption of Table 1, there are two phrases that begin with \"For stochastic algorithms\". The first one should be removed. Moreover, in the second one the first expected should be removed (i.e. the time complexity is the ~~expected~~ running time of achieving an expected approximation error).\n2. The authors mention that weak $\\epsilon$-CCE is related to social welfare without further explanation. Some clarification may be needed here. As far as I am aware, this does not apply to all the general-sum games but only to those that satisfy a certain 'smoothness' condition.\n3. While the algorithm stated in the pseudo-code is correct, equation (1) seems to be wrong. In particular, the term $\\sigma_i^k-\\tau(\\ldots)$ mixes quantities that live in the primal (players' strategies) and live in the dual (gradients).\n4. At the beginning of Section 4: \"where $a_{-i}\\in\\mathcal{A}_{-i}$ denote**s** a random variable ...\" (add s)\n5. LVE used in Algorithm 1 is not yet defined at this point.\n6. It seems that $w^0_i$ and $\\sigma^0_i$ used in the definition of $U_i$ are never defined (I suppose they are uniform distribution over the simplex).\n7. On the third line of page 6, the phrase \"sampled from $q_{-i}$\" seems to be redundant.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "0DjYX0mF-L", "reviewer": "Reviewer_YwXx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work leverages recent techniques for variance reduction in solving variational inequalities to obtain better bounds simultaneously in individual and sum of all players' regret for a general type of games.\nMore precisely, in their model, the authors endowed continuous functions as utility functions (not necessarily convex loss/concave gain) but the strategy of each player belongs to the simplex of a discrete action set, which is actually equivalent to normal form games. (Please correct me if I am wrong)", "summary_of_the_review": "I had the chance to review the paper in this initial phase as emergency reviewer. \nHaving said that, I am very open to the discussion to be sure that I have not misunderstood anything in the paper. I am very familiar with the work of AM21 and the connections of Regret and CCE. Someone could say that there is at a first glance a plug-and-play situation. However, it seems that a new MC estimator is also a necessary contribution to go from minimization of one agent (AM21) to our CCE (collaborative regret minimization). \n\nI have set a series of questions which if they will be addressed, I will be convinced that the paper deserves a clear accept. My positive score should be explained as my positive propensity for the papers' result.\n\n", "strength_and_weaknesses": "Strengths:\n1) Introduction of a new variance reduction method (LVE) resolving the curse of dimensionality of Carmon's et al 19 estimator\n2) Leveraging SVRG techniques for VI and EG to describe an Optimistic Var Reduction Stochastic Mirror Descent method.\n3) Better bounds for the regret for each player.\n4) General Functions for simplex functions.\n\nPlease, I request from the authors for each of the weakness prescribed below to address it as a statement/question that necessates clarification\nWeaknesses:\n1) It was not clear to me what are the guarantees for the expected regret of the sum of all players and what is the statement for the pseudo-regret of the sum of all players. Can you please clarify\n2) Obtaining convergence to a weak CCE via a pseudo-regret has been typically described in the literature? Is there any novelty in this point? I assume no, the ingenuity starts with the variance reduction methods, correct?\n3) The authors proposed LVE instead of classical IWE with exploration term. Can the authors explain the details of their estimator. It would help if they provide some extended answer. how they derive this estimator. Is it something standard in the literature?\n4)There is another point which was not clear, the regret statements are correct if all the players employ the same algorithm? Do we have the adversarial 1/\\sqrt{T} case, if one of the players plays adversarially/stochastically?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster