Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update
Authors: Georgios Piliouras
Ryann Sim
EFSTRATIOS PANTELEIMON SKOULAKIS
Venue: NeurIPS 2022 Accept (2022)
Keywords: Regret
Coarse correlated equilibria
Online learning
Game theory

Abstract: In this paper we provide a novel and simple algorithm, Clairvoyant Multiplicative Weights Updates (CMWU), for convergence to \textit{Coarse Correlated Equilibria} (CCE) in general games. CMWU effectively corresponds to the standard MWU algorithm but where all agents, when updating their mixed strategies, use the payoff profiles based on tomorrow's behavior, i.e. the agents are clairvoyant. CMWU achieves constant regret of $\ln(m)/\eta$ in all normal-form games with m actions and fixed step-sizes $\eta$. Although CMWU encodes in its definition a fixed point computation, which in principle could result in dynamics that are neither computationally efficient nor uncoupled, we show that both of these issues can be largely circumvented. Specifically, as long as the step-size $\eta$ is upper bounded by $\frac{1}{(n-1)V}$, where $n$ is the number of agents and $[0,V]$ is the payoff range, then the CMWU updates can be computed linearly fast via a contraction map. This implementation results in an uncoupled online learning dynamic that admits a $O(\log T)$-sparse sub-sequence where each agent experiences at most $O(nV\log m)$ regret. This implies that the CMWU dynamics converge with rate $O(nV \log m \log T / T)$ to a CCE and improves on the current state-of-the-art convergence rate. 

Beyond Time-Average Convergence:
Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update
Georgios Piliouras
Ryann Sim
Stratis Skoulakis
SUTD
SUTD
EPFL eistratios
euorgios@sut..dd..gg sutd.edu.sg
ryann_ Limn__si@@iie mym.il.uut..ddu......
Abstract
In this paper we provide a novel and simple algorithm, Clairvoyant Multiplicative Weights Updates (CMWU), for convergence to Coarse Correlated Equilibria (CCE) in general games. CMWU effectively corresponds to the standard MWU algorithm but where all agents, when updating their mixed strategies, the payoff profiles based on tomorrow's ' behavior, i.c. the agents are clairvoyant. CMWU achieves constant regret of (mm))/n in all normal-form games with actions and fixed step-sizes y). Although CMWU encodes in its definition fixed point computation, which in principle could result in dynamics that neither computationally efficient nor uncoupled, we show that both of these issues can be largely circumvented. Specifically, long the step-size 7/ is upper bounded by [n-1WV where is the
number of agents and [0. V] is the payoff range, then the CMWU updates can be computed linearly fast via contraction map. This implementation results in uncoupled online learning dynamic that admits a O(log -sparse sub-sequence where each agent experiences most OnnV log m) regret. This implies that the CMWU dynamics converge with rate O(nV log m log T/T) to a CCE and improves the current state-of-the-art convergence rate of uncoupled online learning dynamics [T
Introduction
The connection between online learning and game theory has been extensively studied for decades.
The emergence of online learning algoritlums guaranteeing comparable payoffs with the highest- rewarding strategy has provided a landmark method of understanding how selfish agents can act in an adversarial environment, while the notion of Coarse Correlated Equilibrium (CCE) has provided a game-theoretic characterization of the limiting behavior of such online learning dynamics
35 21
An important aspect online learning dynamics is that agents can collectively learn a CCE without having explicit knowledge of the full game description. By definition, online learning algorithms take as input the sequence of vectors corresponding to the payoff each possible action, making no assumption about how these payoff vectors are derived [22]. This idea of information exchange can be concisely described with the following distributed protocol, known in the literature as uncoupled online learning dynamics [II:
No agent aware of their payoff matrix or the payoff matrix of any other agent.
2. At each round f, each agent i announces their mixed strategy z;-
3. Based on the announced strategy vector x² := (0f . 2t),, each agent learns only their payoff vector (x<x..)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

4. Each agent uses (u,(=²;). (............ ..... ()(x",)) to update their mixed strategy at round t + 1.
If agents use one of the classical no-regrer online learning algorithms (e.g. Hedge, Regret Match- ing, Multiplicative Weights Update (MWU) etc), then the time-average behavior of the resulting uncoupled online learning dynamics will converge CCE with rate (L/vVT) [ Despite the fact
that (1/vT)) has proven to be the optimal time-average regret that an agent can achieve in the adversarial case, the question of determining which update rule gives the fastest convergence to CCE has remained open. Over the years, series of works has proposed update rules with better and better rates (9 222 24
33 37 [0] until the recent seminal work of Daskalakis et. al [13], which established that Optimistic Multiplicatiie Weights Update (OMWU) admits Ollog" A T/TT) rate of convergence. This rate matches (up to logarithmic factors) the lower bound (11/T) the convergence rate of any uncoupled online learning dynamic
Self-Play and Algorithmic Applications
Apart from theoretical interest, uncoupled online learning dynamics admit important applications which make the above line of research even more exciting and significant [35] 15|
25 28
39 32 27
Some of their interesting algorithmic properties are: i) their decentralized nature permits efficient distributed implementation, ix) the implicit access to the game via payoff vectors permits game- abstractions with vastly reduced size, and iii) their iterative guarantees can be preferable over the all-or-nothing guarantees of linear programs. A notable example of their algorithmic success is the design of state-of-the art Al poker programs based on iterative self-play that outperform previous LP-based approaches, and were able to compete with human professionals [6 38 40). We remark
that this result has motivated a parallel line of research studying the convergence rates of uncoupled online learning dynamics for extensive form games [17
66 18
Our Contribution and Results
All previous works in this area couple the goals of minimizing adversarial regret and fast time-average
37 10, Since many of the aforementioned applications are in the realm of self-play where all agents are programmed to follow the update rule, guaranteeing adversarial no-regret is not necessity. Indeed, it is not clear why time-average behavior should be the only way to deduce a CCE. In fact, any simple and efficient deduction rule would serve the algorithmic benefits of uncoupled online learning dynamics [8 25 Motivated by the above, our contributions can be summarized as follows:
convergence to CCE 2 24
33
15
We introduce a novel update rule, called Clairvoyant Multiplicative Weights Update (CMWU) that produces sequences of strategy profiles with constant regret in general games.
In its generic form, CMWU is a centralized update rule and does not fit in the online learning framework. However, based on CMWU we design an uncoupled online learning dynamic called CMWU dynamics which gives fast convergence to CCE beyond the time-average sense.
More precisely, we establish that given any trajectory of length T of CMWU dynamics, the log T-spare sub-trajectory always admits constant regret for all agents. As a result, the time-average behavior of the O(log -pparse sub-trajectory converges to CCE with θ (log T/T) rate, improving on the previous state-of fftte-of-the--ee the- θ (log* T/T) achieved by Daskalakis et al. 13.
The update rule of CMWU dynamics (presented in Algorithm 2 admits a simple form and efficient implementation (requiring only single step of the MWU algorithm at each round). The proof of convergence for CMWU dynamics is also far simpler than previous proofs of convergence of uncoupled online learning dynamics [3]
In T we summarize the most important results concerning the convergence to CCE of uncoupled online learning dynamics.
Remark 1.1. All the results mentioned in Table additionally admit Ö(VT) adversarial guarantees.
As mentioned above, this means that once subset of the agents act adversarially by not following the update rule of the online learning dynamic, the agents following the update rule are guaranteed to experience at most Ö(VT) regret. The reason why CMWU is able to achieve better guarantees with simpler analysis comes from the fact that it neglects the adversarial no-regret guarantees that are

---

Table Prior results for convergence to CCE in uncoupled online learning dynamics. n denotes the number of players, m denotes the number of actions per player and V denotes the maximum value in the game payoff tensor. The step-size for CMWU, 7, is set to 1/2V n.
Update Rule
Deduction Rule
Rate of Convergence
Game Type
MWU
Time-average
o
(v fog m
General-sum
Excessive Gap
O (V m(log T + log 4/2 m)/T)
Time-average
12
2-player zero-sum
Technique
DS-OPtMD,
Time-average
log 0(V) (m)) 24
2-player zero-sum
OptDA
OMWU
Time-average
0 (V log m / 7//3/11
B3
General-sum
OMWU
Time-average
0 V l/g
5/6 m 5//
General-sum
OMWU
Time-average
0 (nV log log T/T)
General-sum
log T' -sparre
O (nV log m log T T/T)
CMWU
General-sum
average
(Theorem 4.1
irrelevant in self-play/training settings and focuses on minimizing the regret in specific parts of the sequence.
Remark 1.2. In another related work, M established an online learning dynamic that converges with rate O(n log(m) log a T/T) to Correlated Equilibria (CE), a subset of Coarse Correlated Equilibria. Finally, following our work, (2) produced time-average convergence to CE via online learning at a rate ((mm log T/T).. In comparison, our dependency on the number of actions m is exponentially smaller at (log(m.. Furthermore, their update rule is based on self-concordant regularization and thus admits high per-iteration complexity, a point which is mentioned by the authors.
Remark 1.3. Similarly to other standard no-regret algorithms, CMWU is designed to compute CCE via an uncoupled online learning dynamic and thus cannot be viewed as a rational behavioral assumption for selfish agents who seek to minimize their individual cost. One concrete example where the assumption fails is the case of auctions with a no-regret buyer [.), where the auctioneer can provably manipulate the behavior of any buyer learning according algorithms to guarantee themselves optimal revenue. This comes at the expense of higher prices no-
wide class of no-regret
for the buyer, since the auctioneer can take advantage of the commitment of the buyer regret learning strategy. Hence, it is clear that the learning in games community should discuss and differentiate in greater detail the uncoupled online learning dynamics that come as natural game-play and uncoupled dynamics that come as a means of decentralized, efficient computation.
The Philosophy and Design of CMWU
We introduce radically different philosophy in the design of online learning algorithms. We shift away from the prevailing paradigm by defining a novel algorithm that we call Cluirvoyant Multiplica- tive Weights Update (CMWU). CMWU is MWU equipped with mental/simulateed attta//siiiitttee//ttteeeeeeeeee model (jointly shared across all agents) about the state of the system in its next period. Each agent records its mixed strategy, i.e., its belief about what expects play in the next period in this shared mental model, which is internally updated using MWU without any changes to the real-world behavior up until it equilibrates, thus marking its consistency with the next day's real-world outcome. It is then and only then that agents take action in the real-world, effectively doing so with "full knowledge" of the state of the system on the next day, i.e., they are clairvoyant. CMWU acts as MWU with one day look-ahead, achieving bounded regret. CMWU update rule is closely related with the Proximal Point Method (PPM) 29 26 34 31 which is an implicit (and therefore unimplementable) method that admits arbitrarily fast convergence in the context of convex minimization. Similarly to PPM, in order to implement the update rule of CMWU one would require access to the explicit description of the game and to additionally solve fixed-poin problem.
3

---

Our main technical contribution consists of establishing that for sufficiently small step-sizes, the update rule of CMWU can be computed via the iterations of contraction map. This not only provides way to compute the CMWU update rule using simple and efficient process, but also opens pathway for decentralized computation in the context of uncoupled online learning dynamics. The basic idea behind CMWU dynamics (Algorithm 2 is to punctuate the history of play with anchor points which are equally spaced in distance + (log T"), such that any anchor point is the CMWU update of the previous anchor point. In this way, the regret in the anchor sequence is constant for any agent. Moreover, the intermediate points between two anchor points correspond to the iterations of the contraction map. Surprisingly enough, all of the above can be implemented with just an if condition and an MWU-esque exponentiation (see Algorithm
2
Preliminaries & Model
2.1 Normal Form Games
We begin with basic definitions from game theory. A finite normal-form game I I(N, u)
consists of a set of players N = {1....,,)) n1 where player i may select from a finite set of actions or pure strategies S,. Each player has payoff' function u, S II - R assigning reward (s) to player i. It is common to describe with payoff tensor ( where us(s) = A Let m max; [S.] denote the maximum number of pure strategies in r, and let V max;, (A!') denote the maximum payoff value of any strategy in l'
Players are also allowed to mixed strategies r; (Iis, strategy profiles is X' = II. X, A strategy is fully mixed if vis, > 0 for all 8; E S; and i e W Individuals compute the payoff of mixed strategy linearly using expectation. Formally,
ASS)) X, The set of mixed
(x(x)
Σ (s)s) SES
II VEN
DieL
(1)
We also introduce additional notation to express player payouts for brevity in analysis later. Let Wis, (x) = M4 (4; (8 denote the reward i receives i opts to play pure strategy 8; when everyone else commits their strategies described by xr. This results in u, (xr) = ()) Next will introduce the notion of Coarse Correlated Equilibria (CCE), which is the key equilibrium notion we explore in work.
Definition 2.1. A probability distribution μa over pure strategy profiles = (81, , 8n) E S is called an 6-approximate Coarse Correlated Equilibrium if for each agent E [n]].
Ex-p [v<(*)] 2 Exwp [uc(6), 8-:] - for all actions E S
Definition 2.2. Given a strategy profile x == (I1,..... ...) E X, Hx denotes the product probability distribution over strategy profiles (s1...., 8n) induced by x, (s( == II,
2.2 Uncoupled Online Learning Dynamies in Games
We study games from learning perspective where agents iteratively update their mixed strategies over time based on the performance of pure strategies in prior iterations via an uncoupled, online adaptive algorithm. We will start by describing one of the most classical online learning algorithms, Multiplicative Weights Update (MWU).
The update rule for MWU can be written as
Lia exp (1)s Via, (x*))
[+]
(MWU)
E ExEs,, a/s, exp (Mi Uis, (x²))
The remarkable guarantee of MWU and many other online learning algorithms that the actual payoff for agents is close to the highest-rewarding action of the game. This property is formally captured via the notion of regret.
(ss: x=:) denotes the strategy after replacing z; with

---

Definition 2.3 (Regret). Given a sequence of mixed strategies 2o..... 2T-1 the regret of agent i, (T),, defined as
T-1
T-1 (1((=_1),
(T) = max K ==
Σ
Σ (1)
Once agent adopts MWU, then they are ensured to experience sub-linear regret, RT(T) S (VT)
no matter how the other agents update their strategies ( This implies that the time-averaged difference between the payoff of the best fixed strategy and the actual produced reward goes to zero with rate O(1/VT). Any online learning algorithm that is able to guarantee RT(T) o(T) is called no-regret.
There exists a folklore connection between any no-regret online learning algorithms and Coarse Correlated Equilibrium.
Theorem 2.4 (Folkore h. Given a sequence of mixed strategies ... then the probability distribution ů ;= Ets pzz/T /T is an (TTTT)"T)-ppproxiiii Coarse Correlated Equilibriun where R(T) == max4e[n) (T).).
Theorem 2.4 lipllee that if all agents update their strategies with no-regret online learning algorithm, then the time-average strategy vector converges to CCE with rate o(T)/T. As a result, the time- average strategy vector converges CCE as + oo.
In Algorithm
!
we present a generic description of uncoupled online learning dynamics.
Algorithm 1 Uncoupled Online Learning Dynamics
1: for all round 0, -,... T- 1 do
2: Each player E [n]. broadcasts its mixed strategy of E Xr
3: Each agent E [n]] learns only its reward vector u,(x"),.
4: Each agent E [n]. updates x;" [+1 E X, based only on ux(x.)) .).................... us (x
5:
end for
If for example the update rule of MWU is implemented at Step 4 of Algorithm I then the distribution = ETD Mz, /T is approxxmaae CCE.
3 Clairvoyant MWU
In this section, we introduce a novel learning algorithm for games that we call Clairvoyant Mul- tiplicative Weights Updates (CMWU). Critically, CMWU, unlike MWU, forms self-confrmming predictions/beleess about what all opponents will play in the next time instance. Namely, all agents will form the same belief about what agent will play in the next period t + (x++1) These beliefs/estimates such that when agents simulate an extra period of play in their mind and update their current strategies using MWU, the resulting strategy for each agent is x All agents accurately predict the behavior of all other agents tomorrow, other words they are clairvoyant!
The update rule for (CMWU) is as follows:
ats. exp (TR Uie, (x'-1)
(CMWU)
83, Ex,s,, diss exp (7) Uis, (x++1))
implicit method: the strategy *1+1 appears on both sides of the equation, and thus the method needs to solve an algebraic/fixed point equation for the unknown s++
CMWU
Theorem 3.1.
The algebraic system of equations in (CMWU) defined by an arbitrary game I, an arbitrary tuple of learning rates ni, and any state x², always admits a solution.
See egg. fttps:///thorry.saattee www.norrdddd.ooo. wdtu//mm//t////1111// .pf
5

---

Theorem 3.1
follows directly by the Brouwer fixed fixed-point theorem. Having established the fact that the agents can always collectively compute next step of the CMWU update rule, we present the remarkable property of CMWU stated in Theorem 3.2
Theorem 3.2. Let Fo...., Pr-1 be a sequence of mixed strategies such that all pairs of consecutive mixed strategies (241) satisfy Equation (CMWU). Then, each agent i has bounded regret S log S.l/mp
The proof of Theorem 3.2 follows by standard arguments in online learning literature (e.g. Lemma 5.4 in (221). Moreover, we directly obtain the following corollary:
Corollary 3.3. Let Io....,,TT be sequence of mixed strategies such that all pairs of consecutive mixed strategies (241)++1) satisfy Equation (CMWU). Then, the probability distribution EL Pat /T is a (log " CCE where == minten U/-
From a computational complexity perspective, solving the algebraic/fixed point equation (CWU in general a hard problem. For instance, the computation of Nash Equilibrium (30 which has
proven to be PPAD-complete [14), reduces to the computation of a solution for equation (CMWU) 1) oc. Moreover, even if we assume that the agents possess unlimited computational power, it is not clear how they can compute a solution to Equation (CMWU) in the context of uncoupled online learning dynamics.
In Section 3.1 we show that if each 7): is upper bounded by some game-dependent parame- ters, (CMWU) is contraction map (Theorem 3.6 Corollary 3.7p. This not only implies that there exists a unique exed-point solution that can be computed very efficiently, but also that the Clairvoyant MWU update rule can be simulated via uncoupled online learning dynamic.
3.1 Uniqueness of Fixed Point via Map Contraction
We will establish uniqueness of the fixed point in CMWU for a specific range of step-sizes. The proof will be based on an application of the Banach fixed- point theorem (mapping theorem or contraction mapping theorem) [] Thus, we simultaneously provide a constructive method compute these fixed points with linear convergence rate. In what follows, it will be useful to consider (MWU) as map from vector of payoff's v; , Uiss)) to mixed strategies parameterized by the current initial position x!:
2 exp (m) val)
T.s. exp (m (iss,i)
(vz(1)) =
(MWU,)
E Enes, d/s, exp (m) Uis.) Exes w/s, exp (T viz,)
We first establish the fact that (e;( is an 2m--contiuuous mapping.
Lemma 3.4. For any choice of at A(S)), the (MWU map Jaę RIS. + A(S.) satisfies that for any utility vectors Us, of RIS.
(v,); fag (1/0l 2n/le vfll
In the rest of the section establish that once all 17s selected sufficiently small then Equa- tion MWU, admits unique fixed point and is in fact a contraction map.
Definition 3.5. The distance between the strategy profiles x (#1, (II,...,,I,) In) X and x' (x/,... x E X is defined as D(z, x²) == maxigigallzz 2f/11-
In Theorem 3.6 we show that the computation of CMWU is a contraction map once all do not exceed a game-dependent constant.
Theorem 3.6. Consider the mixed strategy profile (xf, ..., ......)))) and the map G : X + X' defined as follows:
G(x) = (fzy (f1 far, (cn(z)))
Then for any x. x' E X,
(IG(s),G(z)) S v 1) 1))-x(())
where yj the maximum step-size over all players, [0, V] the payoff range of the game and n is the number of players.

---

Proof. Let us denote by drv æ²) the total variation distance between product distributions z, x,.''
G(a())
= [[))(()())) - fat (vx for some player E [vx]
s 2n [|u;(()) - ( by Lemma (3.4
S 24 dTv(#_-=='1))
s 2nV Ejz; dTV (Tj,
by known properties of total variation (e.g.. 23
- nV. E.-E,ae ش 12 -2y1=
I n/(n - 1) D(x,x')
Corollary 3.7. The MWU map with maximum step-size 1) < "T-IJV is contraction and thus converges to its unique fixed point at a linear rate.
Uncoupled Clairvoyant MWU Online Learning Dynamics
In this section we present an uncoupled online learning dynamic based on the Clairvoyant MWU update rule, which we call CMWU dynamics. More precisely, the agents follow the distributed protocol described in Algorithm T while each agent runs Algorithm internally update their strategy æf at each round. To simplify notation in Algorithm 2 agent be m
we set the number of actions of any
[S)].
Algorithm 2 Internal update rule of Clairvoyant MWU Dynamics
1: Input: 0, k EN
2: x; < (1/m..... 1/m) and 2, +- (1/m, ..... / 1/m)
3: for each round = ...... T do
4: if t mod == then
5:
2 x
6: Agent broadcasts the mixed strategy a and then receives the payoff vector v;(x".).
7:
Updates zद such that for all 8; E S.,
1-1 1r (x'
2is,
218: + Σxes,, 2/ errvis (xe)
8:
else
9:
=f 21-- 2!-1
Updates at such that for all 8; E S,,
2/e, mils (atT))
Lis; Enes, 2/s, enr (x'T1)
Agent broadcasts the mixed strategy of and then receives the payoff vector vz(xf :).
12:
end end for
Theorem 4.1. Let To. ...0.....5.................. IT-1 be the strategy vector once each agent internally adopts Algorithm with 1j 1/2nV and k [log T.. Then for each agent i,
T'
Σ
(vi(a"))),
Σ
(1;(1 2 -12nV -12nVlogm
max B.EN.
7=0
where T T-1 approximate CCE.
Thus, the distribution
I' Etsol IT' is a O (nV (nVlogin m log T/T)-

---

Proof. Notice that 2 = [1/k] when (1 mod k) of 0 and that
Lia, (o
Pis; F Ea.ss,
2-2 Sis; (xL) when (t mod k) = 0
(2)
As result, the sequence =! 2 ..... 2, is the sequence produced by MWU with look-ahead (Be- The- Regularized-Lcadeee applied on the sequence reward vectors ey (x (x ;), .).... (1(x)))
and it is known to admit the following regret guaranted
T Σ (v.(a
log m
max Z,ER,
(w ,,,)))
-2nV logm
Up next, establish that definition of Algorithm Net
|| 1 1 I 8/2 for all 2 1. Let Tm == (T 1) k + m. By the
Fqj
and 2, Tm 2 for all m o,..., 1. Thus,
To MMii (x-
(x for all 8y E St..
E
Using Equation MWU, of Section 3.1 the above system of equations be concisely written as,
fez0 (u:(x"r) (x_"-(
and since all agents follow Algorithm Since 77 1/2nV by Theorem 3.6 G (z) is contraction map with constant 1/2. Thus,
Tm = G (z where G (z) ==
f2z (x)).
8
D (G (x= ,0 , S 2 D (x x0 I
2
The second incquality follows by D (I,) (,)) S (see Definition and that eh (xTh-1) (Equation 3). As a result, for each agent i
3.5
Recall that s rT
| k-
1 S D (z , = D (x G
(xxxt-1))
2
We are now ready to complete the proof of Theorem 4.1
T
Σ (v:(x"1))
2 ((v(a= x,
bo - -2
ul ( ( 11 2/ (vr(a (T) 2// Σ
T
A
(or(a"T) ( 8V
1|
2 21111
k2t
7=0
T
W
max EX
Σ
(2 R. )), xzi)
2n log m 10V
T
max E.
Σ
(x 2),)))
12nV Vog
LLemma 5,4 in 122 or attps://veet http:://veb.stanford stw.forrd.
pd For completeness include the full proof in Lemma A.l

---

5 Conclusion
In this paper we analyze a novel algorithm achieving the strongest to-date results for time-average convergence to coarse correlated equilibria (CCE) in general games. We call this Clairvoyant Multiplicatiie Weights Updates (CMWU). Although CMWU includes in its definition a fixed-point computation and effectively enables the agents to access the future behavior of their opponents, show that it can be implemented efficiently in an online and totally uncoupled manner. A critical conceptual innovation of the uncoupled implementation of CMWU is that the CCE computation is done not via the standard techniques (uniform time averaging or last-iterate implementation) but an averaging of pre-specified and game independent (log -spaase sub-sequence of the whole history of play. This type of implementation, as far as we know, is novel not only from a theoretical but even from a practical perspective.
Indeed, learning in games has become a fundamental as well as ubiquitous tool for numerous machine learning applications. These include the most well known Al headline success stories such as Generative Adversarial Networks [9], achieving superhuman performance in diverse settings such Poker 77] a.o. Despite this wide range of settings,
Go (6), heads-up Poker (28), there is a roughly common pattern in achieving these results - design an optimization-driven learning dynamic and have it compete against itself in self-play. In poker style applications, the typical technique is to approximately solve the zero-sum game via low-regret time-averaging (typically uniform, sometimes with recency bias) over the whole history of play. In other applications such as Go, where the policy/strategy encoding is achieved by DeepNets with many parameters and any notion of averaging is totally impractical, the hope that self-play leads ever improving agents with the solution being the last-iterate of the self-play process, Our analysis shows that exploring different averaging techniques enables efficient, simple-to-ing tommlleeemmm uncoupled and otate-of-the-art algorithms to solving general normal-fore games. This points to a rather under-explored hyper- parameter of online algorithm design, the averaging policy, and raises tantalizing questions about extending our results both in theory well as experimentally to more complex settings.
Acknowledgments
This research/project is supported by the National Research Foundation, Singapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No: LISG-RRP-2020-016 NRF 2018 Fellowship NRF-NRFF201 8-07,
ALIAS grant, grant PIE-SGP-AI-200000,, AME Programmatic Fund (Grant No. A20H6b0151) from the Agency for Science, Technology and Research (A STAR), Provost's s Chair Professorship grant RGEPPV2101 and by EPSRC grant EP/R018472/1. Ryann Sim gratefully acknowledges support from the SUTD President's 's Graduate Fellowship (SUTD-PGF).
References
[1] loannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. arXiv preprint arXiv:2111.06000 2021.
[2] Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung- Wei Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with o(log T) swap regret in multiplayer games. CoRR, abs/2204. 11417, 1417, 2022.
[3] Stefan Banach. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fund. math, 3(1):133-111 1922.
[4] David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6:1 1956.
[5] Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinberg. Selling no-regret buyer. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 523-538,
2018.
[6] Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals, Science, 359(6374) 2018.

---

[7] Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science,
365(6456):885-8888 890. 2019.
[8] Andrea Celli, Alberto Marchesi, Gabriele Farina, and Nicola Gatti. Decentralized no-regret learning algorithms for extensive-form correlated equitibria (extended abstract). In Zhi-Hua Zhou, editor, Proceedings the Thirtieth International Joint Conference on Artificial Intelli- gence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 4755-4759. ijcai.org, 2021.
[9] Nicolo Desa-Bianchi and Gåbor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[10] Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. In In Advances in Neural Information Processing Systems, 2020.
[11] Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algo- rithms for zero-sum games. In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11, pages 235-254, Philadelphia, PA, USA, 2011. 1. Society for Industrial and Applied Mathematics.
[12] Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algo- rithms for zero-sum games. Games and Economic Behavior, 92:327-348, 2015.
[13] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34, 2021.
[14] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a nash equilibrium. SIAM J. Comput., 39(1):195-259 2009.
[15] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In ICLR, 2018.
[16] Gabriele Farina, Tommaso Bianchi, and Tuomas Sandholm. Coarse correlation in extensive- form games. In The Thirty-Fourte AAAI Conference Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 1934-1941. AAAI Press, 2020.
[17] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic regret minimiza- tion for extensive-form games via dilated distance-generating functions. arXiv preprint arXiv:1910. 101..10900.000 2019.
[18] Gabriele Farina, Alberto Marchesi, Christian Kroer, Nicola Gatti, and Tuomas Sandholm. Trembling- hand perfection in extensive-form games with commitment. Jérôme Lang, editor, Proceedings of the Twenty-Seventh International Joint Conference Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 233-239. ijeai.org, 2018.
[19] Ian Goodfellow, Jean Pouget-Abais Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 2, NIPS 14, Cambridge, MA, USA, 2014. MIT Press.
pages
[20] James Hannan. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3(2)997-339, 1957.
[21] Sergiu Hart and Andreu Mas-Colell. Simple adaptive strategies: from regret-matching to uncoupled dynamics, volume 4. World Scientific, 2013.
[22] Elad Hazan et Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-3255 2016.
[23] Wassily Hoeffding and Wolfowitz. Distinguishability of sets of distributions. The Annals of Mathematical Statistics, 2963):700-718, 1958.
[24] Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In In Conference Learning Theory, 2021.
[25] Christian Kroer, Gabriele Farina, and Tuomas Sandholm. Solving large sequential games with the excessive gap technique. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Bianchi, and Roman Gameet, editors, Advances in Neural Information
10

---

Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada. pages 872-882, 2018.
[26] Bernard Martinet. Régularisation d'inéquations variationnelles par approximations successives.
rev. française informat. Recherche Opérationnelle, 4: 4:154-158, 1970.
[27] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. SODA, pages 2703-2717, 2018.
[28] 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 in heads-up no-limit poker. Science, 356(6337):508-513 2017.
[29] Jean-Jacques Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société mathématique de France, 93:273-299, 1965.
[30] John Nash. Non-cooperative games. The Annals of Mathematics, 54(2):286-295, 1951.
[31] Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of convergence o (1/k" 2). In Doklady an ussr, volume 269, pages 543-547, 1983.
[32] Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. In Advances in Neural Information Processing Systems, pages 5872-5882, 2017.
[33] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, pages 3066-3074, 2013.
[34] Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5))877-898, 1976.
[35] Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78-86, 2010.
[36] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittweseer, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):444-88) 2016.
[37] Vasilis Syrgkanis, Alckh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games. In Proceedings of the 28th International Conference on Neural Information Processing Systems, NIPS' 15, pages 2989 2997, Cambridge, MA, USA, 2015.
MIT Press.
[38] Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit texas hold'em, em. In Qiang Yang and Michael J. Wooldridge, editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 645 AAAI Press, 2015.
[39]
Chen-Yu Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, pages 1263-1291. PMLR, 2018
[40] Martin Zinkevich, Michael Johanson, Michael H. Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In John C. Platt, Daphne Koller, Yoram Singer, and Sam T. Roweis, editors, Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 3-6, 2007, pages Associates, Inc., 2007.
Curran
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We argue for the results described in the abstract and intro in the remaining sections of the paper.
(b) Did you describe the limitations of your work? [Yes] We dedicate large portion of the paper to explaining how to circumvent the limitations of our proposed algorithm (see Section 4).
11

---

(c) Did you discuss any potential negative societal impacts of your work? [No] Our work primarily theoretical, with no potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We discuss the assumptions needed for each result explicitly.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are either given directly after the result, or deferred to the Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "wV2_DnskznX", "reviewer": "Reviewer_k1YV", "summary": "This paper proposes Clairvoyant Multiplicative Weight Update (CMWU), a simple alternative of Optimistic MWU that can compute CCE of a general-sum game in log(t)/t rates in a uncoupled manner. The idea of the algorithm is to compute the fixed point of the exponential weight update, similar to the idea of proximal-point method. It can be shown that if all players follow this dynamics, the time average of their iterates will be an approximate CCE, with the accuracy of approximation dependent on the step size. \n\nDue to the intractability of computing the fixed point, the authors proposes to approximate it when the step size is smaller than a constant, exploiting the fact that when the step size is sufficiently small, the exponential weight update is a contraction mapping. When every player synchronizes to find the fixed point, they can find the fixed point up to accuracy of 1/t in t steps. The procedure can be decoupled across all players and is very efficient. \n\nOverall, the algorithm can find CCE in a rate of $n\\log(m)\\log(t)/t$, where $n$ is the number of players and $m$ is the number of pure strategies (for a single player).  ", "questions": "- Please answer the questions asked in the \"weakness\" part above. \n- Corollary 3.3: the $\\eta$ should be in the denominator? \n- Is there a computational complexity lower bound (might be restricted to some class of algorithms) for the considered setting? \n", "limitations": "There is little/no limitations or potential negative societal impact. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n- The proposed algorithm has simple implementation and simple analysis, and achieves the state-of-the-art rate of computing CCE in a uncoupled manner. \n\nWeakness: \n- The proposed algorithm requires stronger coordination among players compared to OMWU, which might sacrifice some merits of OMWU. For example, the uncoupled version of CMWU requires a synchronization among players in updating z, what if the synchronization fails or the periods used by players differ? \n- Similarly, OMWU has the benefit of being a no-regret algorithm against any adversary (if the learning rate is adaptive). Can CMWU also be a no-regret algorithm? ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cVWzrL-Pdqf", "reviewer": "Reviewer_2XD2", "summary": "This paper considers using no-regret algorithms for solving general games. Their proposed algorithm for the players, named CMWU, achieves an O(nVlogmlogT) regret, which improves the previous best results by an O(log^3 T) factor. The main idea is to use future decision to update the current one in MWU.", "questions": "The main questions are listed above.\n\nPutting the game framework aside, I am a bit curious about this problem: can CMWU be applied to a learning with expert problem? If so, what is the regret? And what’s the relationship to OMWU?", "limitations": "I have some questions about the computational complexity, which are listed above. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The proposed algorithm improves the previous state of the art algorithm by an O(log^3 T) factor. \n\n2. The main idea of the algorithm, i.e., using the future to update the current decision in MWU, to my knowledge is novel. I think the main obstacle here is the computational issue, and it seems that the authors have successfully overcome it under certain assumptions. However, I have some concerns about this point, which is listed in the next part. \n\n\n\nWeakness: \n\n1. My main concern is about the computational complexity of the proposed algorithm (I realized that the authors say in Line 75 that the update only “requiring a single step of MWU”, so I may have some misunderstanding, and I hope the authors could help me clear the concerns): \n\n1) in general, as the authors pointed out, the CMWU update (Line 173) is very difficult to compute. \n\n2)  Under certain assumptions, the authors show that “the update can be computed linear fast via a contraction map”. However, I have two questions about this conclusion: \na) for the linear convergence rate, do the authors mean one can get a $\\epsilon$-approximate solution with O(log (1/epsilon)) number of iterations? \nB) If so, will the error  accumulate at each round? And will the real number of iterations become something like TlogT instead of T? \n\n3) I also have a question about the assumption related to the maximum eta. I was wondering if the authors could be more specific about how to set eta to get the regret bound in Table 1? \n\n2. Apart from the improvement on regret, another contribution is the more general deduction rule. Can the authors be more clear about the importance of this contribution? Why is it a significant result?\n\n3. I find the paper is not easy to read, especially to people who are not familiar with the specific area. For example, in the introduction, the authors leave many terminologies unexpaterned, such as mixed strightey and sparse sub-trajectory. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "Tdd3_G-Jkxd", "reviewer": "Reviewer_CoXh", "summary": "The authors propose a Clairvoyant Multiplicative Weights Updates (CMWU) for learning normal-form games. The new method achieves the optimal regret with constant stepsize. The authors also provide an efficient decentralized implementation of the proposed method, which enjoys the optimal regret for learning a CCE.", "questions": "- Why are regret bounds in Table 1 called **Rate of Convergence**? \n\n- References about Theorem 2.4 would be helpful.\n\n- Do you have experimental justification of improvements shown in Table 1? It would be very helpful.\n\n- Do you assume that the number of players is fixed? Is it restrictive? \n\n- A typo in line 159: implementatio", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality\n\n- The proposed CMWU is new and it improves existing regret bounds that have been compared. \n\n- The proof has several novel ingredients, e.g., contraction property of MWU mapping. \n\n- An uncoupled implementation of CMWU is a new decentralized multi-agent online learning algorithm.  \n\n## Quality & Clarity\n\n- The paper is well written and all claims are justified via proofs. \n\n## Significance\n\n- The proposed CMWU takes a nice decentralized online implementation which is important for online multi-agent game learning.\n\n- The defined regret bound measures performance via sparse part of history instead of time average of history. This goes beyond the standard metric in learning games. \n\n- The established regret bound improves the dependence on $T$ compared with the existing methods. This is an important advance in learning normal form games. \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EKBwZkRNXkw", "reviewer": "Reviewer_UCa9", "summary": "The paper introduces an uncoupled learning algorithm with efficient strategy updates, coined Clairvoyant Multiplicative Weights Update (CMWU). The algorithm produces a sequence of strategies, a subsequence of which minimizes regret.\n\nThe main idea behind CMWU stems from the known fact that by having a perfect (clairvoyant) prediction of the next loss vector in optimistic MWU, the regret of optimistic MWU grows constant. The contribution of the paper is in showing that such clairvoyant predictions can be obtained efficiently through fixed-point iterations of a contraction, and show that such fixed-point iterations can be interpreted as additional (but ignored in the computation of regret) iterates of a learning algorithm.", "questions": "Please feel free to push back on my analysis of weaknesses above, I'm certainly open to change my mind.\n\nBeyond that, I have a few questions:\n1. Other works in this space (e.g., the recent paper by Daskalakis et al. on near-optimal regret in games) stressed how the accelerated regret bounds can fall back to the usual, non accelerated, $O(\\sqrt T)$ regret dynamics when facing adversarial opponents. Is the same possible for CMWU?\n\n2. Can CMWU be run as an anytime algorithm, that is, without knowing the value of $T$ a priori? If so, I find that that would be an important addition to the paper.", "limitations": "Please see Strengths and Weaknesses above for a description of what limitations where not addressed adequately by the authors.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "While the paper relies on a simple and well-known observation---namely that the observation that clairvoyance leads to constant regret in MWU, which can be already found in these notes from 2008 (Section 2.3, [1])---and the proof of the contraction is incredibly elementary, I think the final result is noteworthy and deserves recognition. Indeed, I think that in this case the simplicity of the argument is a strength and not a weakness, and it is perhaps even surprising that this result had not been noted before.\n\nI find the biggest limitation of the work to be the fact that the iterates produced by the proposed algorithm, CMWU, do not minimize regret. Rather, only a specific (log T)-spaced subsequence of the iterates do. It is not known whether the full sequence of iterates (and not only the specific subsequence) is regret minimizing. For that reason, I find calling CMWU an \"algorithm for regret minimization\" (abstract, line 2) misleading, especially given that the paper insists on the algorithm being uncoupled. I would encourage the authors to reword the abstract to avoid the confusion. \n\nContinuing on the previous points, the authors call the fact that the dynamics only minimize regret when restricting to a specific (log T)-spaced subsequence of the iterates a \"critical conceptual innovation\" (line 255-256). On line 59-60, the authors try to back up the innovation by saying that \"it is not clear why time-average behavior should be the only way to deduce a CCE\". I only partially agree with this. I certainly agree that if the goal is CCE computation, then an alternative deduction rule that preserves uncoupledness and efficient strategy updates remains interesting (and in fact many alternative deduction rules have been tried in the literature, for instance alternative averaging of iterates are very popular in the extensive-form game community). Yet, assuming that dynamics are not run with the objective of computing a CCE, and rather only to guarantee some form of rational (i.e., regret-minimizing in this context) play/learning between the agents, the fact that the iterates as a whole do not minimize regret is clearly a downside. The paper seems to dance between these two intertwined but different goals---computing a CCE and defining regret-minimizing online play/learning---and so a clear discussion of the limitations of the alternative deduction rule (good for one scenario but not the other) gets missed. I strongly encourage the authors to elaborate on the downsides of the lack of the regret minimization property (at least in the usual sense) of their algorithm, and what problems remain open.\n\n\n[1] http://www.mit.edu/~rakhlin/papers/online_learning.pdf", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept