Asynchronous Gradient Play in Zero-Sum Multi-agent Games
Authors: Ruicheng Ao
Shicong Cen
Yuejie Chi
Venue: ICLR 2023 poster (2023)
Keywords: asynchronous gradient play
OMWU
zero-sum polymatrix games

Abstract: Finding equilibria via gradient play in competitive multi-agent games has been attracting a growing amount of attention in recent years, with emphasis on designing efficient strategies where the agents operate in a decentralized and symmetric manner with guaranteed convergence. While significant efforts have been made in understanding zero-sum two-player matrix games, the performance in zero-sum multi-agent games remains inadequately explored, especially in the presence of delayed feedbacks, leaving the scalability and resiliency of gradient play open to questions. In this paper, we make progress by studying asynchronous gradient plays in zero-sum polymatrix games under delayed feedbacks. We first establish that the last iterate of entropy-regularized optimistic multiplicative weight updates (OMWU) method converges linearly to the quantal response equilibrium (QRE), the solution concept under bounded rationality, in the absence of delays. The linear convergence continues to hold even when the feedbacks are randomly delayed under mild statistical assumptions, albeit at a slower rate. Moving beyond random delays, we further demonstrate entropy-regularized OMWU with two-timescale learning rates enjoys faster last-iterate convergence under fixed delays, and continues to converge provably even when the delays are arbitrarily bounded. Our methods also lead to finite-time guarantees to approximate the Nash equilibrium (NE) by moderating the amount of regularization. To the best of our knowledge, this work is the first that aims to understand asynchronous gradient play in zero-sum polymatrix games under a wide range of delay assumptions.
 

Published as a conference paper at ICLR 2023
ASYNCHRONOUS GRADIENT PLAY IN ZERO-SUM MULTI-AGENT GAMES
Ruicheng Ao Peking University archer arcêpku... eettpkuuedd.cc. cn
Shicong Cen & Yuejie Chi Carnegie Mellon University
y (ecejiiceaaadreeee cmu, edu
ABSTRACT
Finding equilibria via gradient play in competitive multi-agent games has been attracting growing amount of attention in recent years, with emphasis on design- ing efficient strategies where the agents operate a decentralized and symmetric manner with guaranteed convergence. While significant efforts have been made in understanding zero-sum two-player matrix games, the performance in zero- sum multi-agent games remains inadequately explored, especially in the presence delayed feedbacks, leaving the scalability and resiliency gradient play open questions. In this paper, we make progress by studying asynchronous gradient plays in zero-sum polymatrix games under delayed feedbacks. We first establish that the last iterate of entropy-regularian (OMWU) method converges linearly to the quantal response equilibrium (QRE), the solution concept under bounded rationality, the absence of delays. While the linear convergence continues to hold even when the feedbacks are randomly de- layed under mild statistical assumptions, it converges noticeably slower rate due to a smaller tolerable range of learning rates. Moving beyond, we demon- OMWU-by adopting two-timescale learning rates a delay-aware manner- enjoys faster last-iterate convergence under fixed delays, and continues to converge provably even when the delays are arbitrarily bounded in an average-iterate manner. Our methods also lead to finite-time guarantees approximate the Nash equilibrium (NE) by moderating the amount of regulariza- tion. To the best of knowledge, this work is the first that aims understand asynchronous gradient play in zero-sum polymatrix games under a wide range of delay assumptions, highlighting the role of learning rates separation.
optimistic multiplicative weight updates
strate entropy-regularize
INTRODUCTION
Finding equilibria of multi multi-player games via gradient play lies at the heart of game theory, which permeates remarkable breadth of modern applications, including but not limited to competitive reinforcement learning (RL) (Littman, 1994), generative adversarial networks (GANs) (Goodfellow et al., 2014) and adversarial training (Mertikopoulos et al., 2018). While conventional wisdom leans towards the paradigm of centralized learning (Bertsekas & Tsitsiklis, 1989), retrieving and sharing information across multiple agents raise questions terms of both privacy and efficiency, leading to significant amount of interest in designing decentralized learning algorithms that utilize only local payoff feedbacks, with the updates at different agents executed in a symmetric manner.
In reality, there is shortage of scenarios where the feedback can be obtained only in delayed manner (He et al., 2014), i.., the agents only receive the payoff information sent from a previous round instead of the current round, due communication slowdowns and congestions, for example. Substantial progress has been made towards reliable and efficient online learning with delayed feed- backs in various settings, c.g., stochastic multi-armed bandit (Pike-Burke 2017), adversarial multi-armed bandit (Cesa- Bisachii et al., 2016; Li et al., 2019), online convex op- timization (Quanrud & Khashabi, 2015; McMahan & Streeter. 2014) and multi-play multi-player game (Meng et al., 2022; Héliou et al., 2020; Zhou et al., 2017). Typical approaches to combatting delays include subsampling the payoff history (Weinberger & Ordentlich, 2002; Joulani et al., 2013), or adopting
al., 2018; Vernade al.,
Author sorted alphabetically.

---

Published as a conference paper at ICLR 2023
lteration complexity
Learning rate
Type of delay
E-QRE
c-NE
none
T- dmax || loge-1
dmax || A
single-timescale
statistical
7 mmax ||-A || (7/ + loge
dmax ||A (7 11) E
constant
7
dmax || (7 + loge=
dmax
||A 11x (7 + 1))2--11
two-timescale
bounded
Indmax || 00 (7 + 1)8/26-1
nd max
[ 11c (7 + 1)0/2(-3 c-
Table 1: Iteration complexities of the proposed OMWU method for finding c-QRE/NE of zero-sum polymatrix games, where logarithmic dependencies are omitted. Here, denotes the maximal time delay when the delay is bounded, n denotes the number of agents in the game, dmax the maximal degree of the graph, and || maxi,j || (over all games the network). We only present the result under statistical delay when the delays are bounded for ease of comparison, while more general bounds are given in Section 3.2.
oo so is the &o norm of the entire payoff matrix A
adaptive learning rates suggested by delay-aware analysis (Quanrud & Khashabi, 2015; McMahan & Streeter, 2014; Hsieh al., 2020; Flaspohler al., 2021). Most of these efforts, however, have been limited to either the asymptotic convergence to the equilibrium (Zhou et al., 2017; Héliou al., 2020) or the study of individual regrer, which characterizes the performance gap between an agent's learning trajectory and the best policy in hindsight. It remains highly inadequate when it comes to guaranteeing finite-time convergence to the equilibrium in a multi-player environment, es- pecially in the presence of delayed feedbacks, thus leaving the scalability and resiliency of gradient play open to questions.
In this work, we initiate the study of asynchronous learning algorithms for an important class of games called zero-sum polymatrix games (also known as network matrix games (Bergman & Fokin, 1998)), which generalizes two-player zero-sum matrix games to the multiple-player setting and serves as an important stepping stone to more general multi-player general-sum games. Zero-sum polymatrix games are commonly used describe situations in which agents' interactions are cap- tured by an interaction graph and the entire system of games are closed so that the total payoffs keep invariant in the system. They find applications in an increasing number of important domains such as security games (Cai et al., 2016), graph transduction (Bernardi, 2021), and more.
In particular, we focus on finite-time last-iterale convergence to two prevalent solution concepts in game theory, namely Nash Equilibrium (NE) and Quantal Response Equilibrium (QRE) which con- siders bounded rationality (McKelvey & Palfrey, 1995). Despite the seemingly simple formulation, few existing works have achieved this goal even in the synchronous setting, i.e., with instantancous feedback. Leonardos et al. (2021) studied a continuous-time learning dynamics that converges the QRE at a linear rate. Anagnostides et al. (2022) demonstrated Optimistic Mirror Descent (OMD) (Rakhlin & Sridharan, 2013) enjoys finite-time last-iterate convergence to the NE, yet the analy- sis therein requires continuous gradient of the regularizer, which incurs computation overhead for solving a subproblem every iteration. In contrast, an appealing alternative is the entropy regular- izer, which leads to closed-form multiplicative updates and is computationally more desirable, but remains poorly understood. In sum, designing efficient learning algorithms that provably converge to the game equilibria has been technically challenging, even in the synchronous setting.
1.1 OUR CONTRIBUTIONS
In this paper, we develop provably convergent cttrrtthms-broaaee dubbed as asynchronous gradi- ent play-to find the QRE and NE of zero-sum polymatrix games in a decentralized and symmet- ric manner with delayed feedbacks. We propose an entropy-regularized Optimistic Multiplicative Weights Update (OMWU) method (Cen al., 2021), where each player symmetrically updates their strategies without access to the payoff matrices and other players' strategies, and initiate system- atic investigation on the impacts of delays on its convergence under two schemes of learning rates schedule. Our main contributions summarized as follows.
Finite-tine last-iterate convergence of single-timescale OMWU. We begin by showing that, in the synchronous setting, the single-timescale OMWU adopted for extrapolation and update-achie achieves last-iterate convergence to the QRE linear
the same learning rate is
2

---

Published as a conference paper at ICLR 2023
rate, which is independent of the number of agents as well as the size of action spaces (up to log- arithmic factors). In addition, this implies a last-iterate convergence to an e-approximate NE in ((==)) iterations by adjusting the regularization parameter, where (-) hides logarithmic depen- dencies. While the last-iterate linear convergence to QRE continues to hold in the asynchronous setting, as long as the delay sequence follows certain mild statistical assumptions, it converges at slower rate due smaller tolerable range of learning rates, with the iteration complexity to find an e-NE degenerating to O).
Finite-time convergence of two-timescale OMWU. To accelerate the convergence rate in the pres- ence of delayed feedback, we propose two-timescale OMWU method which separates the learn- ing rates of extrapolation and update in a delay-aware manner for applications with constant and known delays (e.g. from timestamp information). The learning rate separation is critical in by- passing the convergence slowdown encountered in the single-timescale case, where we show that two-timescale OMWU achieves faster last-iterate linear convergence to QRE in the presence of constant delays, with an improved O iteration complexity to e-NE that matches the rate without delay. We further tackle the more practical yet challenging setting where the feedback sequence is permutated by bounded delays- pooss-yosbbllyyl in adversarial manner and demonstrate provable convergence to the equilibria in an average-iterate manner.
We summarize the iteration complexities of the proposed methods for finding e-approximate solu- tions of QRE and NE in Table 1. To the best of our knowledge, this work presents the first algorithm design and analysis that focus on equilibrium finding in a multi-player game with delayed feedbacks. In contrast, most of existing works concerning individual regret in the synchronoussasynchrooouu settings typically yield average-iterate convergence guarantees (see e.g., Bailey (2021); ),; Meng et al. (2022)) and fall short of characterizing the actual learning trajectory to the equilibrium.
1.2 NOTATION AND PAPER ORGANIZATION
Denote by [n] the set {1, n and by A(S) the probability simplex over the set S. Given two probability distributions p, p' Á(S), the KL divergence from to p is defined by (L :- EKES p(k)
p(k) y'Aj" For any vector = [ælιısion E IR", we use exp(=) to represent [exp(=))] The rest of this paper is organized follows. Section 2 provides the preliminary on zero-sum polymatrix games and solution concepts. Performance guarantees of single-timescale OMWU and two-timescale OMWU are presented in Section and Section 4, respectively, Numer- ical experiments are provided in Section to corroborate the theoretical findings, and finally, we conclude in Section 6. The proofs are deferred the appendix.
PRELIMINARIES
In this section, introduce the formulation of zero-sum polymatrix games as well as the solution concept of NE and QRE. We start by defining the polymatrix game.
Definition 1 (Polymatrix game). Let G := {(V, E), (Si (Aij (Ag)EnE be an n-player poly- matrix game, where each element in the tuple is defined as follows.
An undirected graph (V,E), with V =In] denoting the set of players and E the set of edges;
For each player E V. S; represents action set, which is assumed to be finite;
For euch edge (i,j) E E, Aij RISS and Aji E RISSIXIS.) represent the payoff matrices associated with player and iee, when player and player choose 8; E S; and 85 E ES the received payoffs are given by Aig(s1:))) 8,). As((3, st), respectively.
Utility function. Given the strategy profile (s1. the utility function u; S + R player i is given by
.8n) == Illvv S taken by all players,
wx(s) EnanJe As)()
Suppose that player adopts a mixed/stochasticc strategy or policy, n. E A(S,), where the probability of selecting 8; S; is specified by ms())). With slight abuse of notation, denote the expected
3

---

Published as a conference paper at ICLR 2023
utility of player i with mixed strategy profile (TI1 -. TT)) E (()
(T((T)
lus [s)(
E mh Aty
ViEV
It turns out to be convenient to treat ni and as vectors in TRIS: and RRiev 1Sd without ambiguity, and concatenate payoff matrices associated with player into
A (An, Ain) R |S1 18;1
(2)
where Aij is 0 whenever (i,j) & E. In particular, follows that Aą 0 for all i V. With these notation in place, we can rewrite the expected utility function (1) as
u+(x)= = x; A
(3)
where A; E ISS can be interpreted as the expected utility of the actions in S; for player i. In ad- dition, we denote the maximum entrywise absolute value of payoff by || max,, ||Aty || max; || and the maximum degree of the graph by dmax maxigv deg, where deg, is the degree of player i. Moreover, we denote Smax = max; |S as the maximum size of the action space over all players.
Zero-sum polymatrix games. The game G is a zero-sum polymatrix game if holds that Diev us) = 0, E S. This immediately implies that for any strategy profile E A(S), it follows that Eiev (T( 0.
Nash equilibrium (NE). A mixed strategy profile π²' = (xi, ........... a is a Nash equilibrium (NE) when each player i cannot further increase its own utility function u, by unilateral deviation, i.c., u;(Ti (T/, =;) I (T, , x"1), for all i E V, TH E A(S)), where the existence is guaranteed by the work (Cai al., 2016). Here we denote the mixed strategies of all players other than by π- and write u, (Ty - = (T). To measure how close a strategy E A(S) is to an NE, we introduce
NE-Gap(T) max max (EA(S))
U1 T-4) u u,(T))
LEV
which measures the largest possible gain in the expected utility when players deviate from its strat- egy unilaterally. mixed strategy profile is called e-approximate Nash equilibrium (c-NE) when NE (T) S which ensures that (T T-i) S (1(T,, T -e; for all E V, कं E A(S)).
Quantal response equilibrium (QRE). The quantal response equilibrium (QRE), proposed by McKelvey & Palfrey (1995). generalizes the classical notion of NE under uncertain payoff's or bounded rationality, while balancing exploration and exploitation. A mixed strategy profile ग (Ti.r..... , ) is a QRE when each player assigns its probability of action according to the ex- pected utility every action in a Boltzmann fashion, i.e., for all V.
cxp((A,x*)k/T)
|H (k) Σ KES, exp([A,;:)*/))
k E
(4)
where is the regularization parameter temperature. Equivalently, this amounts max- imizing an entropy-regullrized utility of each player (Mertikopoulos & Sandholm, 2016), i.e., ui,r (m/, _-,,)) ) S Ui,r (T) --,r)) for all E V. T. A(S:). Here, the entropy-regularizee utility function Us S + IR of player is given by
(n,((x) (T) + HH((),
where H(TT.) = - log m, denotes the Shannon entropy of T. In Leonardos et al. (2021), it is shown that unique QRE exists in zero-sum polymatrix game. Similarly, we can measure the proximity of a strategy æ to QRE by
(RE-GaP,(T)
max NVV
max Wir (i. TT u..- T (EA(S.)
(6)
mixed strategy profile x is called an e-QRE when QRE- Gap- S e. According to the straight- log Smax. it follows immediately that we can link an c/2-QRE to c-NE by setting т = 2 2 Sam. This facilitates the translation conver- gence to the QRE to one regarding the NE by appropriately setting the regularization parameter
forward relationship NE (T) 5 QRE- (ap,
4

---

Published as a conference paper at ICLR 2023
Algorithm Entropy-reeuulaizee OMWU, agent i
1: Initialize (0) = "i as uniform distribution. Learning rates 1/, and 1j (optional).
(0)
2: for / = 0, 1..... do
3: Receive payoff vector A
4: When t 2 L, update т. according to
x (k) { (x) exp(r|A (x 1x),
wk E S..
5: Update गे according to the single-timescale rule
(k) TH. (9) (epp-//epppAAA
vk E St.
(9)
or the two-timescale rule
# (k) x q. (k)) (
vk St.
(10)
6: end for
PERFORMANCE GUARANTEES OF SINGSE-TIMESCALE OMWU
In this section, we present and study the entropy-regularized OMWU method (Cen et al., 2021) for finding the QRE of zero-sum polymatrix games. Whilst the method is originally proposed for finding QRE a two-player zero-sum game, the update rule naturally generalizes to the multi-player setting
(1+1)
(k) x म. (1) (K)² exp (+1 1c),
Vk E S.,
(7)
where > 0 is the learning rate and ((++1) serves as prediction for π (++1) via an extrapolation step
(1+1) (k) न. (A:) '- exp(y|4,7(0)))
A St
In the asynchronous setting, however, each agent i receives a delayed payoff vector (*7( instead of (t)(t) in the t-th iteration, where x!") max 0}, with 7 (t) 0 representing the length of delay. The detailed procedure is outlined in Algorithm using the single-timescale rule (9) for extrapolation.
3.1 PERFORMANCE GUARANTEES WITHOUT DELAYS
We first present our theorem concerning the last-iterate convergence of single-timescale OMWU for finding the QRE in the synchronous setting, i.e. 7/
(1) 0 for all E V and i > 0. For any n, n' E V.
let KL(T || x²)= = Eiev KL (T; m!).
Theorem (Last-iterate convergence without delays). Suppose that the learning rate of single- timescale OMWU in Algorithm obeys < 1 S min 2 7dmmal Al ] then for any T 2 0, the
iterates ne (T) and ((T=) converge at linear rate according to
IL( < (1 (1- 101-177 7)) ))), |
||()+ < 2(1 - 117) (LL) (0)) (11a)
Furthermore, the QRE-gap also converges linearly according to
QRE-Gap, (T()) < 2 da
(L)) (0))
(11b)
Theorem 1 demonstrates that as long the learning rate 7) is sufficiently small, the last iterate of single-timescale OMWU converges to the QRE at a linear rate. Compared with prior works for finding approximate equilibrium for zero-sum polymatrix games, approach features closed- form multiplicative update and fast linear last-iterate convergence. Some remarks are in order.
Linear convergence to the QRE. Theorem implies an iteration complexity of Ö log for finding cQRE in last-iterate manner, which leads iteration complexity of
5

---

Published as a conference paper at ICLR 2023
δ (( dmax dmmollAAlla + 1) log ! by optimizing the learning rate in Theorem 1.The result is especially well as the size of ac-
appealing it avoids direct dependency on the number of agents tion spaces (up to logarithmic factors), suggesting that learning in competitive multi-agent games be made quite scalable long as the interactions among the agents sparse (so that the maximum degree of the graph dmax is much smaller than the number of agents 12).
Last-iterate convergence to e-NE. By setting т appropriately, we end up with an iteration com- plexity of Ö draee Male mz)
for achieving last-iterate convergence to an e-NE, which outperforms
the best existing last-iterate rate of Ô (n [|A))l from Leonardos et al. (2021) by at least factor of (dmaxt).
Remark 1. Our results trivially extend to the setting of weighted zero-sun polymatrix games (Leonardos et al., 2021), which amounts to adopting different learning rates Jev at each player. In this case, the iteration complexity becomes Ö (maxiev - log log ) In addition, our convergence 7; result readily translates to a bound on individual regret as detailed Appendix C.
3.2 PERFORMANCE GUARANTEES UNDER RANDOM DELAYS
We continue examine single- minll-timescale OMWU in the more challenging asynchronous setting. In particularly, we show that the last iterate of single-timescale OMWU continues to converge linearly the QRE slower rate, as long as the delays satisfy some mild statistical assumptions given below.
Assumption (Random delays). Assume that for all i E V, t 2 0, the delay yi independently generated and satisfies
E
(2)
(0 (0) 2 S E(l),
ve I.......
(12)
Additionally, there exists some constant C > 1, such that L - Ee C² < co.
We remark that Assumption 1 is rather mild condition that applies typical delay distributions, such as the Poisson distribution (Zhang et al., 2020), as well as distributions with bounded support (Recht et al., 2011: Liu al., 2014; Assran al., 2020). Roughly speaking, Assumption implies that the probability of the delay decays exponentially with its length, where < approximately indicates the decay rate. We have the following theorem.
Theorem 2 (Last-iterate convergence with random delays). Under Assumption I, suppose that the regulari-zation parameter T <. min dmax ||]] OMWU Algorithm obeys
and the learning rate of single-timescale
5-1
0 < min
(13)
24d ||A|| (L+ 1)
T
then for any T 2 1, the iterates (T) and (T) converges to कं at the rate
max [LL ( 1/ [ML [1]]] {
(1- nT)² KL [1
(14a)
Furthermore, the QRE- also converges linearly according
E PRE--Gpp(TTT) (T<{)) < )
(L (L (I)))))))
(14b)
Theorem 2 suggests that the iteration complexity to c-QRE is no more than # log after optimizing the learning rate, whose range
δ (maxx {Penx |A|| (L + 11,, ) more limited compared with the requirement in Theorem without delays. In particular, the range of the learning rate is proportional to the regularization parameter F, an issue we shall try to address by resorting to two-timescale learning rates in OMWU. To facilitate further understanding, showcase the iteration complexity for finding c-QRE/NE under two typical scenarios: bounded delay and Poisson delay.

---

Published as a conference paper at ICLR 2023
Bounded random delay. When the delays are bounded above by some maximum delay % As- sumption is met with Ç -=1+==+0 and L = ey(r + 1). Plugging into Theorem 2 yields an iteration complexity of Ö d (1l. log !) for finding an e e-QRE, or Ö [d (ll.
for finding an e-NE, which increases quadratically as the maximum delay increases. Note that these rates are worse than those without delays (cf. Theorem 1).
Poisson delay. When the delays follow the Poisson distribution with parameter 1/T, it suffices to set Ç 11+7 and T, = e T) Assumption 1. This leads to an iteration complexity of δ
for finding an e- eRRR or ( T similar the bounded random delay case.
L I.P. log _
for finding an e-NE, which is
6²
4 PERFORMANCE GUARANTEES OF TWO-TIMESCALE OMWU
While Theorem 2 demonstrates provable convergence of single-timescale OMWU with random delays, remains unclear whether the update rule can be better motivated in more general asyn- chronous settings, and whether the convergence can be further ensured under adversarial delays. Indeed, theoretical insights from previous literature (Mokhtari et al., 2020; Cen et al., 2021) suggest the critical role of 7(1) as a predictive surrogate for T(*) in enabling fast convergence, which no
longer holds when (()) is replaced by delayed feedback from ((x[") To this end, we propose to replace the extrapolation update (9) with one equipped with a different learning rate:
(++1) (k) x ! (k)) exp(Tí AA; 1+)))
E E S,
(15)
which adopts a larger learning rate 7) > 17 to counteract the delay. Intuitively, choice of Tj ~ (1 +
(t)
1y would allow (((()) to approximate ((() by taking the intermediate updates {n(()) kg < 1 <
into consideration. We refer to this update rule the two-timescale entropy-regularrized OMWU,
whose detailed procedure is again outlined in Algorithm using (10) for extrapolation.
4.1 PERFORMANCE GUARANTEES UNDER CONSTANT AND KNOWN DELAYS
To highlight the potential benefit of learning rate separation, we start by studying the convergence of two-timescale OMWU in the asynchronous setting with constant and known delays, which has been studied in (Weinberger & Ordentlich, 2002; Flaspohler et al., 2021; Meng et al., 2022). We have the following theorem, which reveals a faster linear convergence to the QRE by using a delay-aware two-timescale learning rate design.
Theorem 3 (Last-iterate convergence with fixed delays). Suppose that the delays 7 y are fixed and known. Suppose that the learning rate n of two-timescale OMWU Algorithm satisfies
1
1
1 S min 2T( 1)
5dmax | (7 1)2
and rj is determined by 1 ワা (1 (0+ then the last iterate π x(1 and (()) converge to the
QRE at linear rate: for T 2
max {KL(=>) 11 (T+
KL (T; न ((T-++1)) S(1 5(1-177 KL (| + (1- T+1- <<(
2
In addition, the QRE-gap converges linearly according to
QRE-Gap, (-( S2 max { Laxx ||A||2
1 ( (/7 ( (1; +1 + +(1 (11 --)
By optimizing the learning rate 1), Theorem 3 implies that two-timescale OMWU takes at most log iterations to find an c-QRE in a last-iterate manner, which translates to an iteration complexity of δ dma (cmm Am for finding c-NE. This significantly improves over the iteration complexity of Õ || (r + 1)2/e²) for single- OMWU, verifying the positive role of adopting two-timescale learning rate in enabling faster convergence.
Amax AmaxllAl (1+a))11)))) (x+1)²
7

---

Published as a conference paper at ICLR 2023
4.2 PERFORMANCE GUARANTEES WITH PERMUTED BOUNDED DELAYS
The above result requires the exact information of the delay, which may not always be available. Motivated by the need address arbitrary even adversarial delays, we consider a more realistic scenario, where the payoff sequence arrives in a permuted order (Agarwal & Duchi, 2011) con- strained by a maximum bounded delay (McMahan & Streeter, 2014; Wan et al., 2022).
Assumption (Bounded delay). For any E V and > 0, holds that Y Assumption 3 (Permuted feedback). For any t O, the payoff vector at the t-th iteration is received by agent only once. The payoff at the O-th iteration can used multiple times.
(t) S.
The following theorem unveils the convergence of two-timescale OMWU to the QRE in an average sense under permutated bounded delays.
Theorem 4 (Average-iterate convergence under permutated delays). Under Assumption 2 and 3. suppose that the learning rate of two-timescale OMWU in Algorithm satisfies 1) S
min- 2r(7+13 28 ( 20 (1+1)// J. and vj determined by 1/T = (1 17)((t2) then for
T > 27,, it holds that
Σ
(L (L (1
1
Σ
KL ||
max
T-2 27
2=
t=
1
24nry log Smax
(KL =1 +
(16)
MT -27)
27
Furthermore, the average QRE-gap can be bounded by
1
QRE 1aB-Gap-(Fr (T(1))
T 27 2=
3d ||A||3
(
(KL [l [| + n) + 36ny log Smax)
< 27
max
2T
Theorem 4 guarantees that the best iterate among Jessigr is an c-QEE as long as (1r4))0/2))
T is on the order of Ö ndl ( Pe
which translates to an iteration complexity of
δ nd l (++1)0/)) for finding c-NE, While the rate seems slower than the previous the- orems, Theorem holds under arguably the weakest delay assumptions, where it can be even ad- versarially bounded. We remark that the result in (16) also guarantees the convergence of the last iterate a(+) to the QRE asymptotically, although without a finite-time rate. This is in sharp con- trast to typical average-iterate analysis that only applies to 1 Er (f) without implications on the convergence of the last iterate ((1)
The analysis in this section can be generalized more commonly-used delay models where the reward information is not assumed to be observed once per round (Quanrud & Khashabi, 2015; Joulani et al., 2013), i.e., in every round an agent may observe multiple reward feedbacks from previous iterations or receive no information. This can be achieved by storing reward feedbacks in a buffer memory and picking one for policy update every round in First-hi First-Fru manner.
Remark 2.
NUMERICAL EXPERIMENTS
In this section, we verify our theoretical findings by investigating the performance of both single- timescale and two-timescale OMWU on randomly generated zero-sum entropy- reguaay-eeullarized polyma- trix games with 10, |S|] 10, i E V and 7 0.1. For each (i,j) E E, set A. -A]. with entries of Ai independently sampled from the uniform distribution over [-1, 1]. All the results are averaged over five independent runs.
In Fig. (a), compare the performance of asynchronous settings, with delay uniformly sampled from 10 10). We adopt the opti- mal learning rate v from {0.1, 0.05, 0.02, 0.01....) that yields the highest accuracy. The method
OMWU in both synchronous and
8

---

Published as conference paper at ICLR 2023
difeeren
proposed f
single timescale
10'-2
[0-3
single timescale two timescalc
random delay
10
2000 4000
10"
lteration
Learning
Learning
Figure 1: (L( | (0) of single-timescale and two-timescale OMWU with respect to different values of learning rate and delay. (a): performance of single-timescake OMWU in the synchronous setting and asynchronous setting. (b) & (c): performance of the two methods after 5000 iterations under various choices of 7) and 17, with fj fixed fj T - 0.001 in (c).
mf) in (b) and r) fixed to
achieves linear convergence in both cases, yet the convergence rate slowed down by delayed feed- backs in the asynchronous setting. Fig. (b) and (c) compare the effect of different choices of learning rates 77 77 on the performance of the proposed methods, where the feedback is permutated with bounded delay y = 25 (cf. Assumptions 2 and 3). In general, two-timescale OMWU outper- OMWU given appropriate choices of learning rate 17. On the other hand, (c) demonstrates that the choice of (1 (1 y/r ) suggested by the theory (marked with star) indeed leads to near-optimal performance of two-timescale OMWU.
forms
Figure shows (L || (9) with respect the number of iterations of single-timescale and timescale OMWU under different asynchronous scenarios, with optimal choices of and r = 0.1. In particular, wwo-timescale OMWU adopts the extrapolation learning rate suggested by theory îj (1 (1 ) While both methods yield linear convergence to the QRE, two-timescale method outperforms its single-timescale counterpart in the case with constant and known delay and the case where the feedback is permutated with bounded delay, which verifies theory.
K0. (e10)
Kilec (e16g
309
10"
single timescale
10-4
single timescalo two-timescale
single timescale
two- timescale
10a1
two-timescan
15000
2000
2000
100000
count
(a) random delay
(b) fixed delay
(c) permuted feedback
Figure 2: (L || (0) with respect to iteration count of single-timescale and two-timescale OMWU under various asynchronous settings. (a): random delays bounded by 7 25. (b): constant delays 50. (c): permuted feedback with delay bounded by = 25.
6 CONCLUSION
This paper studies asynchronous gradient play in zero-sum polymatrix games, by investigating the convergence behaviors of entropy-regularized OMWU with delayed feedbacks under two different schedules of the learning rates. We demonstrate that single-timescale OMWU enjoys a linear last- iterate convergence to the QRE even under mild statistical delays. However, the presence of the delay noticeably limits the allowable range of learning rates and slows down the convergence. To mitigate the impact, we further show that the method benefits from adopting two-timescale learning rate in a delay-aware manner, which achieves a faster last-iterate convergence when the delay is fixed and known, and continues converge provably even when the delays arbitrarily bounded in an average-iterate manner. We believe our work lays the foundation for further understandings of delayed feedback in games under symmetric and independent learning.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
S. Cen and Y. Chi are supported in part by the grants ONR 100014-19-1-2404, NSF CCF-1901 199, CCF-2106778 and CNS-2148212. S. Cen also gratefully supported by Wei Shen and Xuchong Zhang Presidential Fellowship, and Nicholas Minnici Dean's 's Graduate Fellowship in Electrical and Computer Engineering at Carnegie Mellon University. R. Ao is supported by the Elite Undergradu- ate Training Program of School of Mathematical Sciences at Peking University.
REFERENCES
Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. Advances in neural information processing systems, 24, 2011.
Joannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games, arXiv preprint arXiv:2203./200 2022.
Mahmoud Assran, Arda Aytekin, Hamid Reza Feyzmahdavian, Mikael Johansson, and Michael G Rabbat. Advances in asynchronous parallel and distributed optimization. Proceedings of the IEEE, 108(11):2013-2031, 2020.
James Bailey. O(1/T) time-average convergence in a generalization of multiagent zero-sum games. arXiv preprint arXiv:2/100024:5 2021.
LM Bergman and IN Fokin. On separable non-cooperative zero-sum games. Optimization, 44(1): 69-84, 1998.
Riccardo Bernardi. Interactive image segmentation using graph transduction games. 2021.
Dimitri Bertsekas and John Tsitsiklis. Parallel and distributed computation: numerical methods, 1989.
Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Papadimitrion. Zero-sum poly- matrix games: A generalization of minmax. Mathematics of Operations Research, 41(2))648- 655, 2016.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint arXiv:2007.06558, 2020.
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34:27952- 27964, 2021.
Shicong Cen, Yuejie Chi, Simon Du, and Lin Xiao. Faster last-iterate convergence of policy opti- mization in zero-sum markov games. arXiv preprint arXiv:2210.01050, 2022.
Nicol'o Cesa-Bianchi, Claudio Gentile, Yishay Mansour, and Alberto Minora. Delay and coopera- tion in nonstochastic bandits. In Conference on Learning Theory, pp. 605-622, PMLR, 2016.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprins arXiv: 2018.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp. 235-254. SIAM, 2011.
Michail Fasoulakis, Evangelos Markakis, Yannis Pantazis, and Constantinos Varsos. Forward look- ing best-response multiplicative weights update methods for bilinear zero-sum games. In Inter- national Conference Artificial Intelligence and Statistics, pp. 11096-11117, PMLR, 2022.
Genevieve E Flaspohler, Francesco Orabona, Judah Cohen. Soukayna Mouatadid, Miruna Oprescu, Paulo Orenstein, and Lester Mackey. Online learning with optimism and delay. In International Conference Machine Learning, pp. 3373-3373. PMLR, 2021.
10

---

Published as a conference paper at ICLR 2023
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-133, 1999.
lan J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farles Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. arXiv preprint arXiv: 1eo614666,,11 2014.
Xinran He, Junfeng Pan, Ou Jin, Tianbing Xu, Bo Liu, Tao Xu, Yanxin Shi, Antoine Atallah, Ralf Herbrich, Stuart Bowers. et al. Practical lessons from predicting clicks on ads at facebook. In Proceedings of the eighth international workshop on data mining for online advertising, pp. 1-9, 2014.
Amélie Héliou, Panayotis Mertikopoulos, and Zhengyuan Zhou Gradient-free online learning in continuous games with delayed rewards. In International conference on machine learning, pp- 4172-4181. PMLR, 2020.
Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Multi-agent online optimization with delays: Asynchronicity, adaptivity, and optimism. arXiv preprint arXiv:2012.11579, 2020.
Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Online learning under delayed feedback. In International Conference on Machine Learning, pp. 1453-1461. PMLR, 2013.
Chung-Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive-form games. Advances in Neural Information Processing Systems, 34, 2021.
Stefanos Leonardos, Georgios Piliouras, and Kelly Spendlove. agent competition: convergence with bounded rationality. Advances in Neural Information Pro- cessing Systems, 34:26318-26332 2021.
in multi-
Bingcong Li, Tianyi Chen, and Georgios B Giannakis. Bandit online learning with unknown delays. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 993-1002. PMLR, 2019.
Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In Machine Learning Proceedings, pp. 157-163. Elsevier, 1994.
Ji Liu and Stephen J Wright. Asynchronous stochastic coordinate descent: Parallelism and conver- gence properties. SIAM Journal on Optimization, 25(1):351-376, 2015.
Ji Liu, Steve Wright, Christopher Ré, Victor Bittorf, and Srikrishna Sridhar. An asynchronous par- allel stochastic coordinate descent algorithm. In International Conference on Machine Learning, PMLR, 2014.
pp.
Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-38, 1995.
Brendan McMahan and Matthew Streeter. Delay-tolerant algorithms for asynchronous distributed online learning. Advances in Neural Information Processing Systems, 27, 2014.
Min Meng, Xiuxian Li, and Jie Chen. Decentralized nash equilibria learning for online game with bandit feedback. arXiv preprint vrXiv:2204.09467 2022.
Panayotis Mertikopoulos and William H Sandholm. Learning in games via reinforcement and regu- larization. Mathematics of Operations Research, 41 13447129771334, 2016.
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2703-2717. SIAM, 2018
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra- attra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference Artificial Intelligence and Statistics, pp. 1497-1507. PMLR, 2020.

---

Published as a conference paper at ICLR 2023
Yu Nesterov. Excessive gap technique in nonsmooth convex minimization. SIAM Journal on Opti- mization, (16(1):23522433 2005a.
Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 103(1):
127-152, 2005b.
Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-362. 2012.
Ciara Pike-Burke, Shipra Agrawal, Csaba Szepesvari, and Steffen Grunewalder. Bandits with de- layed, aggregated anonymous feedback. International Conference on Machine Learning, pp- 4105-4113, 13. PMLR, 2018.
Kent Quanrud and Daniel Khashabi. Online learning with adversarial delays. Advances in neural information processing systems, 28, 2015.
Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable se- quences. arXiv preprint 1311.
2013.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. Advances neural information processing systems, 24, 2011.
Samuel Sokota, Ryan D'Orazio, J Zico Kolter, Nicolas Loizou, Marc Lanctot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. unified approach to reinforcement learning, quantal sponse equilibria, and two-player zero-sum games. arXiv preprint vrXiv:2206.05822 2022.
Qianqian Tong, Guannan Liang, and Jinbo Bi. Effective federated adaptive gradient methods with non-iid decentralized data. arXiv preprint arXiv:2009.06557 2020.
Claire Vernade, Olivier Cappé, and Vianney Perchet. Stochastic bandit models for delayed conver- sions. arXiv preprint arXiv: 1706.09 0916, 2017.
Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang. Online strongly convex optimization with unknown delays. Machine Learning, (1(3):871-893,202
Chen-Yo Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent infinite-horizon competitive Markov games. arXiv preprini urXiv:2102..444:
2021.
Marcelo J Weinberger and Erik Ordentlich. On delayed prediction of individual sequences. IEEE Transactions on Information Theory, 18(7):1959- 1976, 2002.
Xin Zhang, Jia Liu, and Zhengyuan Zhu. Taming convergence for asynchronous stochastic gradi- descent with unbounded delay in non-convex learning. In 2020 59th IEEE Conference on Decision and Control ( (CDC), pp. 3580-3585 IEEE, 2020.
Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Peter W Glynn, and Claire Tomlin. Countering feedback delays multi-agent learning. Advances in Neural Information Processing Systems, 30, 2017.
12

---

Published as a conference paper at ICLR 2023
Appendix
Table of Contents
A Further related works
13
B Proof for single-timescale OMWU (Section 3)
14
B.I Proof of Thcorem
14
B.2 Proof of Theorem 2
16
C Regret analysis single-timescale OMWU
22
Proof Theorem
23
C.2 Proof Theorem
26
D Proof for two-timescale OMWU (Section 4)
29
D.1 Proof of Theorem 3
29
D.2 Proof of Theorem
33
E Proof auxiliary lemmas
E.1 Proof of Lemma
................................
39
E,2 Proof of Lemma 2
39
E,3 Proof of Lemma 3
40
E,4 Proof of Lemma
41
Proof Lemma
42
E,6
Proof of Lemma
42
E.7 Proof of Lemma 7
43
E.8 Proof of Lemma 8
44
E.9 Proof of Lemma
46
A FURTHER RELATED WORKS
Learning in two-player zero-sum matrix games. Freund & Schapire (1999) proved that Multi- plicative Weights Update (MWU) method achieve an average-iterate convergence rate of ( (T) through the lens of regret analysis. Daskalakis et al. (2011) is the first to achieve optimal conver- gence rate of (1/TT) with the excessive gap technique of Nesterov (Nesterov, 2005a;b). Rakhlin & Sridharan (2013) achieved the same rate with OMD, which is more commonly referred to as OMWU when entropy regularization in use for the mirror descent update rule. In terms last- iterate convergence, Daskalakis & Panageas (2018) established asymptotic last-iterate convergence for OMWU assuming the uniqueness of NE. Wei et al. (2021) improved upon the analysis under the same assumption by showing mooblem-dependent linear rate of convergence, which is extended to a class of extensive-form games (Lee et al., 2021). Cen et al. (2021) showed that entropy-regularize OMWU converges linearly the QRE of two-player zero-sum matrix game, which translates an iteration complexity of (1/TT) for finding an c-NE, without assuming its uniqueness; the linear convergence to the QRE continues to hold with smooth value updates (Cen et al., 2022). Sokota et al. (2022) showed that linear convergence to QRE can be achieved without resorting to optimistic update rules, e.g., using entropy-regularized MWU, albeit with a more restrictive learning rate. It is worth pointing out that the idea learning rate separation has been explored for equilibrium finding in two- wo-player zero-sum games with instant feedback (Fasoulakis al., 2022) and online learning with delayed feedback (Hsieh et al., 2020), but lacks study in an asynchronous multi- multi-player game setting.
13

---

Published as a conference paper at ICLR 2023
Asynchronous optimization. Asynchronous and decentralized optimization algorithms have been extensively studied since the proposal of Bertsekas & Tsitsiklis (1989), where a number of agents seek find approximate global optimizer of common loss function, by performing iterative gradient-based methods in collaborative manner. Typical approaches including parallelizing the computation of gradient with regard to data (Tong et al., 2020), parallelizing the model updates by imposing coordinate update rules (Nesterov, 2012: Liu et al., 2014; Liu & Wright, 2015). Delayed gradient (feedback) also common in these scenarios due the existence of other agents updating the model. Moreover, the zero-sum polymatrix setting considered in this work is inherently non- collaborative by requiring every agent to maximize its own utility function and compete with other agents, and leads to substantially difference analysis techniques.
B PROOF FOR SINGLE-TIMESCALL OMWU (SECTION 3)
Before delving into the main proof, we first record a useful lemma pertaining to a basic property of zero-sum polymatrix games; the proof is deferred to Appendix E.1. For i E V, we denote by A = {j (i,j) E F.) the neighbors of agent i in the graph (V, F).. For notational simplicity, we denote by æ _ y the equivalence between two vectors x and y up to a global shift, i.c..
y c-
(17)
for some constant e R. where 1 is the all-one vector. Lemma 1. For any zero-sum polymatrix game G, it holds that for n, n' E A(S) that
Σ
[ x'1)) + u, m-1) 0.
(18)
Or equivalently,
Σiev [ AAT + (mT)
A = 0. follows that
Σ
T4 The AT T')) Σ
(T) + =1((T')]
Σ iEV
A + (T/) A,T]
LEV
B. PROOF OF THEOREM 1
We start with the following lemma that characterizes the iterates of OMWU, which generalizes Cen et al. (2021, Lemma 1) for zero-sum two-player games to zero-sum polymatrix games. The proof can be found in Appendix E.2.
Lemma 2. The iterates of OMWU based on the update rule (9) satisfy
(log (++1) (1 (1-17) log=(") - nt nog ", 7(++1) π;;)
To continue, by the definition of KL divergence, we have
(log (1 1/7) log (1) 177 lo (1+2)) =(log 1 (1+1) - (1 177) log (1) - TfT log क,, n (142))
< log (log - log (1+1) x ((+1)) - ( (log ((+1) - log ((+1) #(++1) ((+11)
(1 177 KTL ( 1| m(1) (1) + KTTKL(TT (+(++)) || وマ) + (L( (
- (log - log (1+1) ((+11) (1+1))
In addition.
-(log (1+1) - (1 - 7)) log (1) yp log म. x;) = (L (+++))) - (1 - (7) (T)KL(T (KKL(T))) T(0).
Summing up the above two relations, view of Lemma 2, it holds that
KL KL(m; | [((11))))))))))) = (1 -
(+) - (1 (L)) (11) - (L(T(e+1)) [(++)
+ ( log (1+1) log (t+11) ((++1) - (KTKL(((+1))) कマ)
(19)
We now proceed to bound the terms of interest one by one.
14

---

Published as a conference paper at ICLR 2023
Bounding (L; || ) We aim to control the right-hand-side (RHS) of (19). Based on the
update rule of म. (1+1) in Algorithm 1, we have
log ;
(t-1) log m3 (++1) 1 () π (112) (T((((()) - (1)))) -.Ai(T(()) -
(20)
-n((T((-((+1)) -)
It follows that
(log
(++1) log q
(1+1), x((++)
R, R3z 1
=1
1++1)
T (r)(T (1)
(1)) + Σ
(
(++1) x. (( Ais(TTT - m| (
JEV,
JEN.
|| | n
(++1) 1)
|1 |1 (1) 11, 17
Σ |Aiillo 1
| - - " 11m55/ - m5 x l|2
"
jeN;
JEN:
1
||A Pmc
(1 - Jj
10 || 1) - ブ
(1) 1|2 + 2|| (1+1)
- -, 11
2
JEN.
S n b0
Σ
(++1) ( + 2KL (T+(++)))) (T(( (1) |mfg)) + (L
(1+11) || क, )
(21)
JEN:
where the last line follows from Pinsker's inequality. Summing the inequality over i E V, we get
< Ilg Mogg((HH) (1+1) - log ( (++1,, =((+1) - x ((+1)))
S 1/dmax 1l (KL(T() (1) || [1))- + KL (L( || x00) + 2KL
2KL(( (z((++
|| (
Plugging the above inequality back into (19) yields
KL (L(x; (++1)) < (1 <TTT (1))) - (1 177 nydmax |1 ) KL ( || (1)
(1 - 21ddmax b0 (LL))((+())))) || (() + nddmax || KL (i)() x())
(T TTt).
(22)
With the choice of the learning rate
{1 1
22T" 4dmax I|All l.Allo> }.
0< min
it holds that 1-17- -/T 1ydmax || > 0 and
ndmmax || S S - 11) - 21ddmax |Alloo)
(23)
This allows us to further relax (22) by
(L + (1 2nddmax || KLL (1((11))
< (1 (1- (-= || T (1)) + 1ydmax || (L(T!!) || (10)
< (1 (7) (KL(T.) || (0) + (1 - 221dmmxx [KL
JKL (L((((() || (()))
Let us now introduce the potential function of iterates
I KL (L(T;; || ()) + (1 21dmax 1141 1
which allows us to simply the previous inequality as
L (++1) < - (0) where the last equality follows from the definition (0) = (0))) Hence, we have
(1) < (1 - (1--)))+110 (0) (1 (-- KLIK,LL(T)T) (T (0))
(24)
KL( (=; || ()) < r,()) < (1 )rrr)rr)(())))) (KL(",; ())
15

---

Published as a conference paper at ICLR 2023
Bounding (L; || [(()))). Following similar approaches to (21), we can bound
- (Tir R (1+1) 1og (1+1) - log 1og=, (
= n( --(,)) A
( (T(1)) - x(1) + n (++1] -[,)) - A - -((+1)
S < ||
Σ [KL (TT) (1) 3 + KL (L (T. (1+2) || ( + 2KL ( [|:
(25)
JEN;
Summing the inequality over i E V leads to
- ( - न ((+1), log न ((+1) log ग. +11
I mddma || [KL( (t) - ()) KL xL(=((+1) || (9)) 2KL(T; || [.]
On the other hand, by the definition of KI. divergence, we have
KL (T; || म 1) KL (-; || - KL (+(++1) x((+1)) - -- ((+11 (t log ग7 (1=11))
(26)
Combining the above two inequalities, we get
(1 2ndmax )KL() || (1(
s KL (=* π (((+) + nddmax ||All (KL(T(() [ + KL( || (
Plugging the above inequality back into (22), we have
(1 2ax || KL (L(T; (0+1)
< (1 777 )L mT; || 7 (1))) - (1 1/T 1/7 2mxmx || )KL (KL(T(+1)) [1x(1) -L ( || TT;)
- (1 21ydmmax (LL || (1= + 21pdmax || KL [=#'0
$ (1 )L ( || 7t (0) 21/dmax |1 KL (1) || 7z (0)
$ (KL(T) || (1 + (1 2nydmax 11. (z 1) (1)
where the second and third inequalities follow from the choice of the learning rate, and the last line
follows from the definition of the potential function (t). Then the result follows from (24) as
KL (L ((+)) S (1 21jdmax || ) (T;; || (1+2)) s (()) < (1- KKL (0). 2
Bounding the QRE-Gap. Finally, bound the QRE-gap, which can be linked to the KL diver- gence using the following lemma. The proof can be found in Appendix E.3.
Lemma 3.
For any (S) and QRE x E A(S), holds that
QRE Gap, I TKL T;) + Leax || 2
KL (T:
Lemma 3 tells us
ORE-Gap,(7!)) S TKL(7(1) [ & ||l
KL (T (1)
(27)
With (L( (()) controlled in the above, we still need to control KL( T.). From (22), it
follows that
TKL (#() || )
KL (1;
Plugging them back to (27), we arrive at
ORE-Gap,(F()) (17 + 2r d 2 (1- - ())
B.2 PROOF OF THEOREM? 2
We begin with bounding the KL divergence KL KL(#²) || (!1) and then move to bound the QRE-gap by linking it to the KI. divergence.
16

---

Published as a conference paper at ICLR 2023
Bounding the term KL (T; xx))..
We start with the following equation
(1 (1-17) ()) ( (1 7 KL [ ( || (
) + (=. (=( m + KL (=+ (=(((t2) ((
+ [KL(TT,
| (++) (logm1++1) (++)) log q. (e+1), x((+1) n((t1)) - || |
+ { (++1) ;,,))) T A, -x;, x77)
(28)
where its proof follows a similar deduction as (19). Our first target is to bound the last two terms on the RHS of (28) with
ny kT
) + (L( "
+ (1-11111)
kTL n.. (((+11 (!")
Let us introduce the potential function of iterates
V (
KL (T( प +KL( I !")).
(1(1) Σ
T KL (L( xل + (T(()) x²)).
EV
which will be used repetitively in the rest of this proof. For notational simplicity, let w!!) = 0 when 1 O.
Step 1: bounding (log=!t*) (f+1) log म Ri
(1+1)
=(((11)
mi
(111)).
Following similar argument as
(21), we get
(log -. ((+1) log (1+1) =((++1 .. ((+11)
1/ (++1) ;;; (1+2)T T Aig (T,
(nc (
(nc (1r(t))
JEN
||All (L(T (1+1) || ক (((+1)) + 17
(112)
(0
S 1ddax
00
(29)
2
JEM.
To control the term
|
(n
(1((11))
(nc(1) (1)
1/2 when we have
(ni
- - 1 s |1 - x 1011 < 2
= |
(30)
by Pinsker's 's inequality. Fort 2 1, consider the decomposition
(1+1) (++1)) - =.)). viskSt
1=t-k k
it then follows that
-
12
| (--1) - 1/00
k
1=
(1 (1+1) 101 + | (0) - -. 1/'1
2k
4k
(31)
(++) > O, we proceed to
where the last line applics Pinsker's incquality. Depending on whether 7 (4))
bound the terms |
7 ||2 in (29) considering the following two cases based on (31).
(1g5))
(++1)
%
0. Then
(ne (1)))
(n(9)) 7
112
22| ((+1)
mT - 1?
(ne(t) +21(==50 m 1|
17

---

Published as a conference paper at ICLR 2023
Σ /./
S / + +8y (t
1= (t)
where the last step uses (31) and
3 l2 -
[ (++1)
- -3 + ||=]] -
- =/ s $4
via again Pinsker's inequality.
((+1) > O. Then it follows similarly that
7/3
||
Σ
|
-
5/ 20 1/2
|
[ - -
1=++1 (142)
1=(-7
(1+1)
Σ
V 47 (0)
Σ
S 47
l=t-
1= 10
Combining the above two bounds together, we get
( TT
(1c ( 1| S / +87 (1)
Σ
w/th
(1)
+ 47 (1+1)
Σ
(32)
(0)
L= (1+3)
when & > In view of (30) when O, the above bound (32) holds for all 2 0. Plugging the above inequality into (29) yields
(log ;
((+1) logg
x!! ((+1)
(((11))
m. (((t1))
(-1
< $2n 11All Σ Σ
Ve 10 + 4n A1 Σ
JEN, 1=(-)(( (e+1)
JEN: |=! 7
+ +47 ||All
Σ (1) + mddmax
A| KL KL (1+1)
ক [++
(1++1))
(33)
JEN:
Step 2: bounding (n. (1+1) nZ,T) T A, (1((1)) (1( n;)) Let us begin with the following decompo-
sition
(T) (1(++) - - T.. (1(((())
)ラ) = (T (1+1] - ) (((1((+1) xT))
+ (मा (1+1) m ( -((11)) (34)
x((+1))
where the second term in the RHS of (34) can be bounded by
11+1) ) A (n) (((+))) (((11)
Σ (T( (1+1)
T Aig -;tr)
(11)
7 (((-1))
JENr
< ||Al|
| (++1)
(1 (111)
JENi
<
1
||All Σ
| (((11)
- 112
dmax
||
|T
(n)
x
2
dmax |A||
5
JEN;
< <TKL || (TT,)
dmax
||
(1+1)
p.
2T
3
JEN.
Following similar deduction of (32) for the second term, we attain (1+1) (m (m((+)) T(,))² Ae(=!!!
((+1)
18

---

Published as a conference paper at ICLR 2023
S <TKL(T; (1((1 mit)) + 4dmax |
( +
Σ
1-1
10)
JEN,
|= (1+1)
Plugging the above inequality back to (34) results in ) A; (
(T) 1++
m²) S (T (++1)
T
A:
(1((1+1) - n
|| m++)) + 4dmax ||Al||
+ (KL (++1)
(9) +
(--
71
JEN.
1=1-7
(++1)
(35)
Step 3: combining the bounds. For simplicity, we introduce the short-hand notation
dmax
| and
CA = <mmax ||
(36)
Combining (33) and (35) into (28), and summing over E V gives
(1 (1-17 (- )L (-² (0)
2 (1 - 1/7 KL
(5((++1
|| (1) +(1 (1
(MCc))L(TTT (T((++)) [ + KKT || 10))
1-1
4n 10
EΣ Σ
cr7
(
+
Σ ui + c. cv
iEV
1=t
(1+))
E 50
2 KL (=(
+ (1- 4ncccc + 1)) 4(()
1-1
-47
Σ
(1+1) 1))
+ Σ
(2)
(37)
iEV JEN,
(=t-g(/))) (1+1)
where we make use of the fact
Σ
T
(1+1)
) (x(
x;,)) =0
KEV
from Lemma I in the first inequality, and the second inequality uses the relation
Σ
( Σ _dv
I dmax (1) (1))
JEN:
EV
Step 4: finishing up via averaging the delay. We evaluate the expectation of (((+))). Recall that we subscript Eyt [1] to represent the conditional expectation given (0) {7; Jiv.. We shall first control the conditional expectation of the last term in (37). Ob- serving that 7/. =((+1)) . are independent of y for e M, and < - 1. Using the definition of
KL KL(m; (;;
E(t 1), we have
E
E. Ex00)
Σ
(1))
E 1S
NEVJEN, JEN;
1=t--
NVV 1=0 JEN;
E(t 1) 3 Σ (1
iEV JEN:
Σ E(t 1) Σ
NEV JEN;
1-1
< dmax
Σ E(t - 1) Σ v
dmax
E(t - 1) (38)
1=0
1VV
1=0
19

---

Published as a conference paper at ICLR 2023
where the second line follows from the definition of E(t 1) in Assumption 1. Applying sim- ilar argument to bound Σiev EjEN, Be(et1) 776
((+1) t-1
21 ((-1)) / and taking expectation of
y(t), ((+++) both sides of (37), we get
(1 - (1-17r)BBcc B2yc0 (TL || x [00]
2 E Fa0 (L
म, (| + (1 -c44(c + 1))
1-1
Anca(c +1) +1) Elt 1)
1=0
Taking expectation on both sides over all the delays yields
(1 - m KL (,x || [0
> E KL((T; (| E (1 4njaale 1)) (p(1) 4ncaae + E E(L 1)
1=
=:010)
(39)
Telescoping over t 0, 1...,... we get
(1 (1-n7) +KL KL
(L("(((('' (T> ||) 2 E |KL(= [|
Σ (1-11) (1- T-E [r]]]
(40)
which leads to the desired bound if
T- -
[10o] 2 O.
(41)
t=
Proof of (41), To begin, notice that with the choice of the learning rate
T
0 < S min
24d
||Al133 (L+ + 1)
ST
it follows that
SC
(42a)
1 77T
and
2 dmax ||A1|
Anc 1) < 4
dmax |A
(L
+ 1)
24d2 max
||Al|es (L +
2 dmax |
1
(42b)
6dmax | |
3dmax
||ll
2
a S dmax ||| Both of these relations will be useful in our follow-up analysis.
Now, taking the definition of (T()) (cf. (39)), we have
Σ - (1- (1
Anealer + 1)) vp(t)
4nca +1)
Σ
E(1 - ((1-1)v(()
0=
1=0
where the second half of the RHS can be further controlled via
T Σ (1- (1-m9 T- 1)
TT-
Σ E(t 1y
(
0=
1=0
T
T-t
(t)
Σ (1 - np) ) -((+'")) E(I')
<
1=
P=0
20

---

Published as a conference paper at ICLR 2023
T
T-t
Σ
(1 7 T T((
Σ
11
1=0
P==0
Σ (1 m77) 777) T0
(lE(1)
t=
= Σ - (1-
where the first line follows by changing the order of summation, the second line follows from the change of variable 1' 1- i, and the last line follows from (42a) and the definition of L in Assump- tion 1. Plugging the above relation back leads to
E 77) t=
Σ
((1--
4mcale+ + 1)) 4nca( + 1)4] (())
1=U
2
Σ (1 1777) T(p(1) 20,
(43)
where the second line results from (42b).
Bounding the term KL (T; x ((()))).
With a similar deduction of (19), we get
(1 - 1T) [T= || (0) +
(++1) xx,) (T( (1)) x;²))
iV
= <TL [[+;||(((()) + (1 - TyT KL (1+11) || (00) + sy 1TTKL (=((++)) T+))
(44)
Following the similar argument of (35), we have
(T (1+11 ) A (n/5)) - m S (T. (e+1) )(,)) T (1(T - -++
T - KL [L |म: ) Sdlmax ||Al| 2
(1+1)
(T(())
Σ
vt (0)
T
JENS
1= 10
Summing over i E V and plugging into (44) yields
(1 17 [L (1))) + 8tydmax ||A 2
1-1
Σ (1) + Σ
7
(3,))
1=ا (t)
+ (1 - <K) (1+11 || (+)
+ !T
(L((TT/ (z((++)) || (T;)
2
2 |[(
nTT (L( |T))
Taking expectation on both sides over all delays and using (38) leads to
- (1-7T)E [KL(= [1=[1]]] + Syndeax ||
2 E
1-1
(1()) +
Σ
E(t - 1)
1=0
2 |L || [+
+ 2 E [KL(7((+2) x+:]]
(45)
Notice that with the choice of the learning rate
S-1
0 < 17 5 min
24d
||A113 (L + 1)
ST
we have
8(L + 1)ddkaax
|1
1
T
2
21

---

Published as a conference paper at ICLR 2023
and
1
(1
r+1 KL (न ||
_ m7) ' 1 (1))
by combining (43) and (40). It follows that
E
2(1 -
and
(
E
Et
1)
SE E
177) (1() ..(t).E(t-- 1)
E(t - -15--1 Σ
1-1
$ E
177)² 1g (1)
1=0
1=
2L (/) ) (0)),
where (i) is by the bound (1-1))) < { and (ii) uses the definition of L in Assumption Plugging the above inequalities into (45) leads to
(1 - TT KL ( || [
+ (1 - mT) ( (0))
2 E
[L [
+
175t
E (KL( || m;:]]
2
Then from (40) we have
KL , || 1)
s E [KL || 7 1)]
+ ç7 KL (L( (++1) || m+:)
2
I (1 myr) 8+ KLL ( || (0))
+ (1 का) + KL || (00
= 2(1 - )パ) + KL (L((LLTT))) || T
(46)
Bounding the QRE-Gap.
Combining (27) and (46), have
|| . + danxx ||A||3 E [LL (((t))
E QRE- Gee-Gap, Gap, 1)]
7E KL (1(
< 2 1 E KL (LL( (1+1) n=:]] + E [KL(=) || m
s 4(1
++
KL( | (0)),
where the second line uses the learning rate bound
2 24d2 max || (L+ + 1)
da da ||A||
>
7
C REGRET ANALYSIS OF
OMWU
For completeness, we also provide the regret analysis of single-timescale OMWU in both syn- chronous and asynchronous settings, which might be of independent interest. To begin, for > 0, the regret for each player i E V is defined as
T Σ
T
Regret, (T) = max (S.))
U
TT.
Ui (7()),
(47)
which measures the performance gap compared to the optimal fixed strategy in hindsight for player when the rest of the players follow the strategies derived from Algorithm 1.
22

---

Assumption (Random delays). Recall the definition of E(E) in (12). There exists some constant Published as a conference paper at ICLR 2023
Synchronous setting. We begin with the following no-regret guarantee of single-timescale timescale OMWU in the synchronous setting.
Theorem (No-regret without delays). Suppose all players V follow single-timescale OMWU
in Algorithm 1 with the initialization x; $ and the learning rate obeys 0 < n S
4dmax Al +4 Then, for T 1, it holds that
Regret,, (T) S log [S:] 16n deg, ||Al|
Σ
log [Sx|-
KEV
By optimizing the learning rate Theorem 5 suggests that the regret is bounded by
max Regret, s,r (T) x (IAllso V /ndmax
iEV
up to logarithmic factors. Compared with the OMD method for multi- multi-agent games in Anagnostides al. (2022), which only provided the regret bound for r entropy regularization. Moreover, our bound is tighter by a factor of n/ //ax by exploiting the graph connectivity pattern, which is significant for large sparse graphs.
bound is more general by allowing
Asynchronous setting. We next move to the asynchronous case, and show that single-timescale OMWU continues to enjoy no-regret learning as long as the delays have finite second-order mo- ments.
0, such that (7 ( Er E(t) for all t and E V.
Clearly Assumption 4 is weaker than Assumption 1, since it only requires the second-order moments be finite, instead of an exponential decay of 7/ (t) We have the following theorem.
Theorem (No-regret with random delays). Under Assumption 4, suppose all players E V follow
single-timescale OMWU in Algorithm I with the initialization n. (0)
1 1, the regularization
[
parameter < min(1, [l h. and the learning rate obeys 0 < n S 24d (0241)
Then, for
T 2 1, it holds that
E Regret, (T)] log [S,] + 8dlmax ||All dmmxx ||Alloo +2 (0² +1) Σ
1 r7
log [Sp). (48)
iEV
Theorem guarantees that the iterate among (1(1 J fiz1 enjoys a regret bound on the order of
o2ndmmax ||ll
max Regreet, i,r (T) S ②
iEV
7
by optimizing the learning rate 7).
C. PROOF OF THEOREM 5
Recall the expression of the regret
Regret, (T) = max EA(S))
Regret; ( T),
where
T
T
Regret, (T:;, T) =
Σ
Wi.r (1y - Σ (T))
T
(
x (t+1) (,((++1)) + + - -+((T((+1))) -
(49)
Therefore, it is sufficient to bound Regret; (m, T) for any т; E A(S)). To begin, we record the following useful lemma whose proof can be found in Appendix E.4.
23

---

Published as a conference paper at ICLR 2023
Lemma 4. For any 0 and T 2 O, we have
Regret, (1+
Σ
max LEV (SA)
Σ ( 1e-m(((t)
A + +H((xs) =H((m,t11)) 2 0.
NEV
Let us now proceed with the following regret decomposition
( - || ((++1,, A, + +H((),
-H(TT(+1)
= (T : 1++1) A,T (1+)) + T((T:) + (T (1+1)
(++1)
AAT(0)) - -H((TT ((((tttt))
() (1(11) m3 ((+1), A (1)
(50)
We proceed to bound each term the RHS of (50).
To begin, note that log m; ((+1) 1 (1 mr) log mi (8) written as
+ (, The first term in (50) can then be
{ 1
n; ((+1) (17((+1)) + TH(TT,
1 (logm( (++1) - -log q; (t)
=(log mi
T ,. ((+1)) + T (log ! (1)
Ti - m(/tt)) - -Illog Tis mi)
11
- -r) (L(TT || (1(0) 17
1 (KL(T: || +2) KL(T, (++1) || |, ((4)) T (log q. (t)
: m ((+1))
(51)
where the second step is derived from the definition of KL divergence. Similarly, the second term in (50) has the form
7 ;; 11-1), (1) - -((T((1))
(1+1)
1 (L (1+1) || (0) (=. 11+1) || ( - (--r) KL KL(T, (1+1)
mm("))
7 + (log n. o 1
(52)
Moving to the third term the RHS of (50), we first make the following claim, which shall be proven at the end of this proof:
T
(++1)
|| S // 11| (,7(1)
(53)
With (53) in place, have
-(T (++1) - 7( 1((+1), (, - A( 5
| |[-((((11) - 2 ||]
(++1) -//) 112
jEN;
s " Σ
||
- -
|| (1+1)) - 53²² 11
JeN
- 2
S 1 1|
JEN;
The latter term can be further bounded by
Σ | f++)) JEN;
-
< deg, jeN,
n 3 + TT) -
((+1)
< 2 deg, Σ
|| - 3 112 ||= - 1/))
JEN,
< 4 4eg,
Σ
(KL(Z((tt)) ;
|| + KL (TT)" | (
JEN;
24

---

Published as a conference paper at ICLR 2023
where it follows respectively from Cauchy-Schwarl inequality, ||a+ bll = 2[ + [[b|1]) and Pinsker's 's inequality. Plugging this into the previous inequality leads to
- -IT (++2) - क ((t+1),, (, - A, S 4n deg, || Σ (KL(
|| - ( + KL (T:"") " l| ))
JEN.
(54)
Plugging (51), (52), and (54) into (50) yields
(T: |t (1+1), A + 7 ( - T (
1 _ (TT (m/ (1+2) || )1(+)) - ( ( (L(T || (I!
(KL(T: (To || (0) - KL [Ts || ب. )
< 1)
1)
71
-KL(TT || ( + 4n deg, ||A||
Σ (KL(T) (1+11 || (|m] + KL(T,²) |
JEV.
Telescoping the sum over t = -0,,..., T leads to
Regret,,, ,, (TT, + 1) < - [ || m..
1 T
(L
(+11) | (((+)))) - (- - -
Σ KL (+++1) (|=
I
1
17
T
+ 4n deg, ||
KL (LL
( (++1 || ( + KL | (55)
1=0
JEN;
T
< _ log |S + 4n deg, ||A113
Σ (KL(T(++1) || ( + (L(TT() ([(T0)][(()) |
1
t=0
(56)
where the last line follows from the fact that KL [T: S log Sai and 1/n > The proof is thus complete if we can establish
Σ [L
Σ (L || S log |Sa).
(57)
keV
Therefore, it remains to establish (53) and (57), which shall be completed as follows.
मे Proof of (53). By the update rules of (t+1) and मं (t+1) from (0 we can deduce that
(oggt((t))) - log (t+1), न. (1+1) - a, (()+)))) = n A: (T(()) - (112)), क. (((+1) - x, ((+1))
(58)
By Pinsker's inequality, we have (logm((+1) log m
((+1) (l+1)
n, n ((+1)} 2 || (1++1) n. (a+1) |
In addition,
(A,(T(()) - n (1+1)), x. (t+1) - m. 1) S || (++1) - m.
((+1))
|| || (,(00 - π (1+2)
Plugging the above two relations into (58) then leads to (53).
Proof of (57). Summing (55) over E V gives
1 T
T
Σ
Regret, (Ti, T + 1) < - (L (0 17
(L(x((+1)||
- (
17 (---)
Σ
KL (1+(1) || (00)
KEV
0=
+ 4ypllax ||A11/
(KL(7((+1))
|| (0)) + KLL || |
20
0
< - (KL (T || (0)) + KL || ) -(- r - 4nddkn ||
T Σ
KL (L( (=((+1) || (0))
1=0
25

---

Published as a conference paper at ICLR 2023
T
1
4np max
||
Σ
KL
KL (t( ||
1=0
T
log
|Sk
1
KL
1
Σ
KL(
||(())
4m
4n 1=0
REV
t=
(59)
where the last line follows from æ (0) T(), KL("T (T || I Evey log [Sk] for any л since x is a uniform distribution, as well as the choice of the learning rate such that
1
Andmax ||A111 S
and
T TS
47j
21j
Taking supremum both sides of (59) and applying Lemma 4 gives (57) advertised.
C.2 PROOF OF THEOREM 6
Similar to the proof of Theorem in Appendix C.I, it suffices to bound Regret, (TI, T) for any
T, ASS)), where
T
T
Regret, Regr =
-i [T; TT (t)
Σ (T())
1=1
T
(T:
- x (1+1) (rT(())) +H(TT) -T(()(()))
(60)
t=0
Consider the following decomposition:
T Tt 1++1) (++()) + +H((T) - =H(m (1+11)
(TT, (1+1) A (m) 1)) + (TT, - -x((+1) (, - A + +H((m) +H(
-IT; .. (++1) A,
+ ((((+))) x((-1) A
(1+1) (T((+1) i (1+1) 1A 11 {
(T ( क| (1+1) (,+1( A
(61)
We now bound each term on the RHS of (61). For simplicity, we reuse the short-hand notation in (36).
To begin with, note that constant e5. Thus we have
क. (++1) (1 प)) + nA + e11 for some normalization
T me. ((+1) A
1
(logm; (++1) - log q. (1)
- (((11))) + T (log ((1) = 11(111)
7
(KL [| KL KL(T,, || n((+)1)) KL (L( (++1) a. ((()) + T ((log (h), - m ((+1)))
(62)
where the second step is derived from the definition of KL-divergence.
Similarly, it holds that
(m. (++1))))) _. 11++1) Arx!"!
= 1
(KL(T((( ((+11 ((()) (L( (++1) || - KL(T!" (++1) || (((())) + 7 (log 1000 ((+11)
7((+1)).
17
(63)
26

---

Published as a conference paper at ICLR 2023
For the term
(an 1++ x;
11+1)
A Apt (utttt))
AAT((S5))
in (61), following the deduction of (33), we get
- (mx ((+1)_ ( -F _((11), A ((((tt))
< <|||||| Σ
( +
Σ
(+1) (1)
Σ
(0) ) + 2c, KL (L (1((+1) { [
Vi
JEN,
1=t-x 1))1)
a=t-a( (9)
(64)
For the last term in (61), it similarly follows that
(T. ; 1+1) (,++11)_ A
= -m= (1))) (x((+1) A
+ (T.(")
-,; 7((11), A,T(1(1)
A,
A (
1-1
s 22eaKL(T
(T, (1+1)
क: (1) + 4c, ||
Σ
(v/0+ + Σ
vo (p
(65)
JEN.
1= (++1)
Plugging (62) (63) (64) (65) into (61) yields
(m - (1+1) A, 1)) + - (H((=t)) - H1(
s - (KL [., || -ي ) - KL KL || (((+t))
(T,
1 - 20a v7(1)
-
17
1-1
+ || E 109 + 27/ (2
||ll
Σ Σ v
JEN:
JEN. 1=1-1 (2)
+ 4cr |1A
(111) Σ Σ
( j + 7 log ; m x(11) + (H((T)) - -H(T!(1))
JENI
1=(- (+1)
Note that
H((T.) - H| 11) + (log n; (1)
n. - n((t1)} = -(log न. - log ,. log me) + (log न. ((!+1) log 7. 7 =(((!1))
KL( || (((")) KL(TT, || (l,
Then we have
{T= -((+() (++))) + (H((T:)) - H(()((1)))
1 (KL (0)) KL(TTell [[(((((( - ( -2cA
-) v1(0)
2CAA -7)
1)
4c, ||A
Σ 100 + +2 (6) ||A||
Σ
4 4ct ||A ?4
(1+1)
Σ
Σ w
JEN
JEN: 1=t (0)
JEN L=( ((4))
(41)
(66)
Since the learning rate satisfies
1
24d2
||Al3
2
20 (a2 + +)
2dmax ||Al +T= = 2cA +
1
T
taking expectation on both sides of (66) leads to
(m= - 7( (++1)
A, + (7((TT)) - :((T(((t1))]
S E (KL(TT. (1:00 - KL(TT, || (: [11))
1 77
2CA -T -) E [v.
n
27

---

Published as a conference paper at ICLR 2023
T--
+ 4c7 1o E [wic)] + 4c | E
Σ 1=0
Elt - 1)
< 1 E [ (1(]) - KL(Ti: || m (
+ 4ct a1 B [wcco] + 4cr 11 E
F(I - 1)
17
11=0
(67)
where we use the fact E, JeN; w/ S y0(0) and the definition of Et - 1). Since Ei E(!) S 0² by definition in Assumption 4, summing (67) over L = 0.1...., T yields
T
E Regret,, (T 1)] - 1 |KL [LL || [ + 4c, ||All (0² + 1)E
Σ t==
v(t)
T
v log |S:| + 4c 11 (a² 1)E
Σ
(t)
(68)
remains to establish
T
E
(t()
S Σ
log |S:].
(69)
iEV
Proof of (69).
Summing (66) over i E V gives
Σ T -((+))) (++(+))) + - (H((..) --(T((+
VEV
$ , (KL(TT) || 10) KL ([([(=((+11)
1
(2 -20A
2CA -) (1())
17
+ 4e, || 1mc Σ Σ
w/0 + 2 (1)
||
Σ Σ
1-1
+ 4c,
||A11
Σ 7
(111)
Σ
Σ
w
1
EVV JEA
EVV JEML 1=t 75
iEV
JEN, 1=t 11+1)
Taking expectation of on both sides and using (38) leads to
(++1)
(+1)) + (M(m)))))(((())))))))))))))))))
E
q. n;
LEV
s L B [KL(T (1
KL( (L(III [|
1))=>) ( 4ca +1) -) E [m))))
"
L-1
+ 4c + +1]E
Σ
E(t - -1)((())
I [KL(T] || π [00]]
2
1=0
Summing over 1. = 1, ,,.1,,.77
T yields
E
Regret, (T. (T.
< LR (LL(TT [TT1I [1=]
- (1_ - 4ca + 1)(02 +1(02+1)] E
Σ ((t)
17
77
ev
1=0
s R KL (TT [1])0
1 E
Σ (p())
(70)
"
2m
where the second line follows from
4ca + 1)(22 + 1)m S 4dmax A (2 dmax ||All
(02 (o² +11
T
<
24d || (a2 + 1)
2
due to r & dmax |1 and 1) S 24d | 1) Taking supremum with respect to ' on both sides, in view of Lemma 4, we arrive at the advertised bound (69).
28

---

Published as a conference paper at ICLR 2023
D PROOF FOR TWO-TIMESCALE OMWU (SECTION 4)
D.1 PROOF OF THEOREM 3
Bounding KL (L | (0)) For notational convenience, we set T()) x(() T(0) for < O. The following lemma parallels Lemma 2 by focusing on delayed feedbacks. The proof is postponed to Appendix E.5.
Lemma 5. Assuming constant delays satisfy
7
(1) 7/s the iterates of OMWU based on the update rule (10)
(Iogn((+1) - (1 - '77) log ( log ,, ((--+1) - -m=²) =0.
By following a similar argument in (19), we conclude that
(L(T; [++l| (++1)) = (1 (TT; (0) (1 TT)KL( (0) - (=(x((+1) (((-)
KL
+ (log (( - log n (1++1), (1- - =((+1)) 1/ KL (AL(T* (-((-)+1) TT;) (71)
It boils down to control the term - (logT('-11
log π (++1), (((-++1) ((()))). When t 2 % by taking logarithm on the both sides the update rules (7) and (10), we have
11) (1 17)) log n. (1-7) + (1,,2(--2))
log n
and
(t-1) 1 (1 17-) 1 (1) (1,
log q
n.
(1 - ,イ)) log (1-2) + Σ - (1-17)'Appa (1--111)
1=0
Subtracting the above equalities and taking inner product with -: (1--++1
((+1)
x,
gives
(log 1!! (+1 11) log प.
(++1)
- (((-1))
Σ (1 1 ( ب. ((+1) A:( -7(1----+-)))
1=0
where the log n; ((-3) i iVV,
terms cancel out due to the choice 1 - Tjr = - , Summing over
(log (1- 7+1)
log x (t+1), -((- =((+11)
(1 nT) ( (x((-++1) -( 1,+1), Ar Ar (1((-))) _ x(1 ((1-)1(11))
n
iEV 1=0
1A
Σ Ea-m)
((-1)) || || マ// -((-7-1+1)
(72)
Using the triangle inequality, we can bound [,( - x(( z as
(1) -11-91++1||
(11 7)  +-11
|| (| cي (c) || 1 (1111) - (11)))))
4=-->
Substitution of the bound into (72) yields
(log (1-++1) log n (1+1), n( (1- ((+11))
29

---

Published as a conference paper at ICLR 2023
- - ااا
( ( -.
+  - 1 (1,
S <n||A|ls Σ Σa-
Σ
|
((-)+
(1
( -
1 1| m3
I|1 1111],
(Na)EE 1=0
4=
- x. ا
- -
1 11 +  -141 - - 33 7 (11
=1
Σ
77 [
(W))B 11 st-y 1=0
|| - :: elaa 1|
1 2/1l Σ
2
Σ
(1
(K.)EF
11=t-7 1=0
Σ 1-4
- - =
(1 n (
-
 11 + | -
1=--- 1=0
S <ndmax |x
2(7 + 1)2KL ( (+t)t) || || ((1 
Σ Ea-my (TL( (1)) || +))
+ (L (-t))))))))) || || )
(73)
4= 1=0
Plugging the above inequality into (71) and recursively a caweelaypplyiunn
cecellspplliiinn applying the inequality gives I
- || x
|| | +1) - + (
KL (T; || 1(()))) + KL (1((+))
+
+ (1- -1- -)-r)))k Cel---ii
 || (
S (1 - 177)++1- (Tr क (1)) -
(1 - )77 1
(KL (KL(  || ||
+ +ddmax al 2(x+1)²
Σ (1 n - ( (1+ اااب )
(1  ( (KL (K((T())
 || || || + + 7y Wللرiيي
|| ((((
Σ (1 (1-11) (1-)7r)'-3 12 Σ
4 4m22- 7
1=
(0 (KL اe ||ا ال
)
$ (1 ) (411-KL((m)) (TT (T= || (T))
-
Σ (1 (1- -
+ (1 - 1il (
JKL
(((())))) lll
k=y
+ +227 + 1mam |A Σ
(1 - कpr )r 12 KL
(LKKL(T'0 ( | || ((tبب
11=7
|| ((i1  (1-177) -1 (KL(
(KL ||
+ (1 T -
+ +2(77 + 1)3rddmax |
4,
2 <1 - (11-)r)(1-7711 XKL (TT || (1))
Miliini || ((thii
| +( + 1) - 1yl)k- (1-77)) (KL(T ||
+ +2(7 + mdmm |A
1--0
where (i) results from basic calculation
1--
(rr))(KK(a))) ( ااا + + 17 ( |1te
(1 m-)) 12
Σ
Σ (1- 7778((())))) (1-
|l || ((tt)
12
11=1--
4 b-
(-) 12 (KL ( (
|| الااا マ + KL  الا (
Σ (1
)77)
)
Σ
(1 (1-
| i x(l11)
1==0 -
1 1=
7
r
- (KL(=(i)) | + + + الي --
|| ((()))
Σ(-
-
4
Σ Σ
(1
-
10
1=
30

---

Published as a conference paper at ICLR 2023
+ ( || | )
$ Σ
mT) 177 (7 + 1)8 (1-
-(+11)
(1- (1- [KL (T( ( + (L((
2(7 + 1)
1=
2 + 1)
Σ
(1 (1- m7) m7) / (1 - 177) KL ( - + KL ( || (((11))
1==0
$ 2 + 1)2
(1 - 177 (KL (L((T((+))) (())) + (1 - .p. kT)
(TL))K(T( (Trl || (211i))
1=
and (ii) is due to v min
2 5d || (++1y To proceed, we introduce the following
lemma concerning the error (L(T= || ( with the proof postponed to Appendix E.6.
Lemma 6. With constant delays Y satisfy
(t) % the iterates of OMWU based on the update rule (10)
KL (=(17|1x(7)
2-1
$ (1 - (T)) || 10))
-1-17 (1-
(KL(z((+1) || |()))+ + (1 17T (T) AKL(F(1--+ 7 (((1))
+ 2-27772a dmax ||
With the lemma above in mind, we can continue to bound (74) by
KL (T;; (++)))
$ (1 (T) (L( || (0)) + 2(1 1 dmax ||
1-1
Σ (1 (1-m))² 7 (KL( - + (1 - 177) KL ( (T(1)))
4=
+2(7 1)² ndmma |All Σ (1 - (1-17))0- 1/ (KL(T(((+2) || ((bb + (1 m7T
( (Tm))K((---0
|| 1nl11)))
1==
I (1 (1- (1--7)++1LL (T;; || (0)) + (1 - -))))++1
Bounding KL( [T || (1())))) By definition of KL divergence, we have
KL(TT; || 11)
= =KL (++1] + (m,,, log (t+1) - (tggo(t-++1))
+ (TT - Λ (1+1), (log (1+1) - -log (t-)((-) (75) remains to control the term ( - ((++1), log (1++1) - log 7(1-,+1)3. By following a similar argument in (73), we have
= <KL(T; [[ + (1(((++11 || [
( n (++1), ((t1)),og π ((+1) - -log=((>++1)
(1 nT) ( - x. (1+1), (1-22)) - x(1-)-1+1))) 
iEV 1=0
< <n||A|ls
Σ
Σ
(1 m7))
|| - कं
|| إلا |
-((- 1|
(1 t=u
<n
Σ
Σ
(1 )
Σ
-
- x |+11 (! n-th" |11 + || ( 23 111)))
(M)E t=0
=
Σ
Σ
|I ((احاا>)) m. (1>3)]| + -|- m. 111"))1)))
(1)) 1=0
31

---

Published as a conference paper at ICLR 2023
S 1ddmax |x
2(7 + 1)2KL (((1))
+ KL ( || | ].
Σ Ea-
|| ( ( (KL(T((L)
4-t-y 2m
Substitution of the above inequality into (75) yields
KL | + 177 KL ((((((+++))) mす))
| | - + lyyii ( ( 11 || (
= (1 + ++ + 1) mmdmax JLL [m क 1 + KL
(L(TT(()) (t+t] ||
ال -لبا |) || )
Σ (1-m7) [L(()())] | + KL KL اللي
+ md ||
$ 2 KL ( (xद 1|+(( + KL (L(((((()))) ( || x(() +  اللااايااا
11
1=
|| | )
( (
+ 2(7 + 1)ddmaax ||Al| Σ (1 11-110 (1--r))~ (KL (K((T(++)) 
|| ا| -
+ (1 - 17 )k]
|| || ((1iii)
1=
|| -ل - = (1 - 1--117 k ا Celiiiil
(n)
(KL( (Kا(اi)i)) (ل(اااا ||
|| || (((11)
I 2(11 -
(m+ (11) - Σ (1 - m in (
1=
+ +4(7 + 1)ax | Σ (1 - 17r) )r 11 KLL (1) || || ((1111+11 
11
+ 11 Menminnn (1-17)) 11 (KL( ( || (
Litt i
(للاار (
+ +6(7 + 1)2ad |A Σ
1=
21(1 (r)) (T: || n1))
+ + (1 - Lall- (7) KL M اiب
|| )( ;
+ +6(7 + 1)dmm |A Σ
- 177- ( | || / )(1)
1=
where (i) results from
Σ (1 (1-)))
(1i)) ||
+ KL ( || ((1iii
||
1=0
Σ (1 (() 177)~
11
2-4
(1- (KL( ا (لاا
| + + KL ( ||
|| [| )
11=1-y
1=0
 || || (((1))) )
1) 17) m7)) (KL(T(")) | + KL (
< Σ (1 - m77
+
||
4==1-
< 2(7 + 1) (1-m7) 11 (KL (KL( 11)+ || 1)) + (1 - ( || o x(()))
1=
and (ii) is due to the bound established in (74). Finally, applying Lemma 6 yields
KL (m; || D) + 17 (L((" TT,))
2(1 m7) KL
(KLK,L (T || (0)) + 4(1 myr) ) ++1 1 2d ||A
1-1
+ - kL] (T (
- 2 Σ (1 - ) 11 (KL(7((++)) |
|| / )(11))
4=
7-1
mL) KL ( - ( || || ((111)
+ +6(7 1)mm |A
E
(KL((T(1++t)) || || ((bー + (1 (11-))) (1-17))-11
(1-mm) -
11
4=
32

---

Published as a conference paper at ICLR 2023
2 - 17)* 1 11 +(11- - -))))+1->
(76)
Bounding the QRE gap.
With Lemma 3, we have
QRE-Gap, (x
max
||||
(L(
((-)))) + -KL (AKL(TT' ( m??)
I max
max
||
1
KKL [KL || ( + ) ( m-²)
17
{
d
Lmxx
||A11
+ (11 (1- 0 + (1 - ny m7) -
- 2 max
T
where the last step results from (76).
D.2 PROOF OF THEOREM 4
Bounding the term KL KL(TT; (T; x()). Recall that the update rule of o. x²((()) (1) is given by
T (k) x mi
(t- " (k) exp(n|A,77()) [c).
(77)
We introduce an auxiliary variable 7!
(k) x m. 1 ( (k) exp (T (1
(78)
which can be viewed as a conceptual alternative update of ni with a different step size n7!") satisfying
>
(1 (1- (1-7/-7)C 7) -1)r)² -777)) =1 fJ
or equivalently
1 - 17 T = (1 - mT) ()) (1)
It directly follows that (() 2 Since Ki S t. we have 1 -
-1- JnT 2
1 (7 + 1)yr, which implies i7." S 1)n. For notational convenience, we set a(()) T1) (1)) 1) and x!() 0 when 1. < 0. The following lemma establishes a one-step analysis, with the proof postponed to Appendix E.7.
Lemma 7. When 2 holds that
KL(Tİ, (1 + nT (T) (N x
(1 - kT) (OCK((T)) ( || nz ((-11) (T (1()))
-;,)) (T(((n -;;)-- - (1) (log ,. (m(()) log n, (1) (n((t)
a!!)),
(79)
where
16(00= = (1
17 (L(((())
(t) || (((-1))
[1)
1/:
(1 np T)KL (n!"))
|| (| 1) + (L(T!")
[ (1 ) + KL (0
(T!
+
We proceed to control the term (log म; (1((1) - log
(n(²)
- - (1)) By definition, we have
log प.
(t) 1 (1 -7( r) log n. (t-1) (1)
17
A (m (1))
1 (1 -1((70 )- '-x (? log n (n -1)
33

---

Published as a conference paper at ICLR 2023
1-1
+ 1h (A
Σ
(1 (1- 1/ 7) - 177 -1
+
L= (
and
log (n( 1 (1 T/r) log r (x(" MA,T(M -1))
when K 2 1. Subtracting the two equations yields
log ;i (1)) -log 77!0) _ 7//")
(A((T( )) )1
+ Σ (1 7 -17)"-1-11
A -, (10)
) -
1=x
(80)
where the log x -1) terms cancel out due to (1 - 7/6 7)( - -7) = 11 F7. follows that
(log n. ) - -log क.
. - - -,") (7 ! 1) --(["(())) }){
(
( (
n
1-1
Σ
(1 v
(1 - 1/-) -
;
A
x(((0))
1=n!
S TH(h) ||ll
T(( + 111
Σ JEN:
Σ t=x
(81)
(afe (e-
The next lemma establishes an upper bound on the term Ei (0) ||==(//)) proof postponed Appendix E.8.
with the
Lemma 8. Let (t))) denote the time index when agent j receives the payoff from the t-th iteration, (u)(t)) = I. For I = O, we set (0) to an arbitrary index that satisfies Ki = 0. When
(v)(0)
ie., K
t 2 27 + 1, holds that
(+7
V)2 wllssin? (af (
(
$4v2(r+
+1)
Σ 1=t-27
V0 + 2222(7 + 1)2
Plugging Lemma 8 into (81) gives
(log ..
(1) log (t) कo
(1(
m!!!))
M -=11=11 -,101,, Σ [V +1)
( + 2/2(1 - 1)2V wol (ag (2--)-)))
$ 5/
|lAllbo 20
|| |
(k0
Σ
V
JEN,
1=t-27
@
1 1_(()
14dmax(( + 1)3/2 (m((1) =,(0112
||A
2
1/ + 1(7 + 1)512 m"
+ Σ
[8(7 + 1)3/22
Σ 1=1-29
JENr
w +2(7+ + 1)8/2 (os (aff
( -(1) I 176
||Al|
14dmax +
+4dmax(y+1)5572) (1)0)+//1/)))// ((() + Σ
4 1)3/+1)3/2 1)3/2
Σ
JEN;
27
(82)
34

---

Published as a conference paper at ICLR 2023
where (i) results from Young's inequality
(1)
1
1 1p+ + V2(7 + +))1/20(0)
v2(r + 1)2/2
2
and (ii) follows from
(1)
S 2KL 2KL(T! (+t!1)
|
- 2(7 + 1) Plugging (82) into
(79) and summing over i V yields
(L || ( + m
KL KL(T TT.
m
iEV
$ < - (1177))K((()) [T; || (|-1)- rj
)it))² T (m()((=()) T7;))
sEV
wffesaafe my
- (1 - 14rydmax || (7 + 1)8/2)
u/ + +2/11Al1 (7+1)8/2 (KJ)ER
Σ
iEV
+ 4vydmax a1 (7 + 1)/02
1600
(83)
1-
where we denote Eiey w0th by (i(h) for notation simplicity. We then seek to sum the above equation over 1 = 27 + 1, T. Before proceeding, we note that
T
T 1422
T T+7
Σ
S
w0 S
11)
+ 1)
(= 1=t-2y 2n
1=1
t=l-
1=1
and that
T
T+y-1
T+7-1
Σ
Σ (1,)EE
Σ
S
dmax
(= (LJEE
(n. (1
where the first step is due to the mapping i + 2y (n:
being injective when 2 2y + 1 (cf. Assumptions 2, 3). Note that w = 0 when t I 0 and hence can be safely discarded. Taken together, we arrive at
T
T
TJT
Σ
KL( (t)) + ę
Σ
Σ
KL
(TT
(1)0) 1
2=
1
12
T
$ (1 - np (LL))KTTTT ((1) 7
Σ
TTT) T As (T((aT) -xx)
LiEV
T+y
- (1 - 11-14ydmmxx |lAl (7 + 11)/22
(7+
( + 12ndmax ||Alloo (7 + 1)5/2
1=2++1
1=1
T=g-11
+ 21dmmax ||Alloc (x+
(b(()
T
< (1 - (I=: -1 Σ
TT
T A, ( x;))
t=
+iEV
(I - 28ydmax ||A (7
(7+ + 1))/2)
(1 + 14ndmax 11Alloo (7 + 1)5/2
Σ ler
()
1=2++1
35

---

Published as a conference paper at ICLR 2023
T
$ (1 - ())))K(((T)) [|,,;|111 ||
Σ
Tip) TA (T(TT
xx,)
Σ Ler
500 (84)
+iV
where I {1. 27 U (T + 1.... T + 7). The last step results from the choice of learn-
ing rate 17 S 28dmo All 2o 17+1)-72 now remains to bound the terms Σi=2++ (T (44))
T T A A,(T() ) π;) (L(TT π ( and Ever s0 In view of Lemma 1, we have
T
) AT(T( m
12y+
T
Σ
T A,(T() - -+)
E
(cl
-m,).
1E
1
We remark that each (T - T Ax(T((4) - m;) term will cancel out due to the mapping
1 ++ Kig (t) being injective when 2 7. In addition, we have a crude bound
) A (T() イ
-(,)) (T)) Tj,7) S 4dmax ||All
jEA
for every E V,t 2 0. Applying the bound to the remaining ny terms gives
T
Σ
A.( π;₂) S 4nrydmax loo
(85)
1= BEV
The remaining terms KL(T; क ((21) and 40 can be bounded with the following lemma, with the proof postponed to Appendix E.9.
Lemma 9, It holds for all E and 2 that
V (fdmax || (27 + 11) + 37 log [S.().
(86)
In addition, we have
KL | || प ((2))) < ( || |l ) + 4rydmax ||A 7.
(87)
Putting all pieces together, we continue from (84) and show that
KL( [1==)==00)
T Σ
< (1 - (T) (21))
- ((( -
+
1 Σ 20(0)
2= 1 VEV
leT
< KL ( || |, (,:0) + mmax A1 + (ndmaxx || (27 + +11) + Σ log |Sa1]
iEV
< (L || ( + 87m 7mmax || + r (mmex |Alloc (27 + 11) + 3r log Smas }
< [KL(TT || प3 (0)) + n + 24mrny log Smax.
Bounding the term KL (m; (((- By definition of KL divergence, we have
(Li,,, || || (())
= -K |l ب 1) + ( log -
((+1) log 7! ((1-
= KL(Ti, (| KL ([( || -, (1+1)) + ( n (1-7+1) log mi ((+1)
loog म. (1-x-1)) 1)).
(88)
36

---

Published as a conference paper at ICLR 2023
It follows directly from the update rules that
log ? ++) (1 Tjア) log mi (t-2) + (7
1+1
logm; ;
(1+1)
1 (1 175 175 7 log x3 (1-7) + 1
Σ
(1 (1-175)(-(t) A,t(
1=t 1
which enables us to control the term (क - प. (+) log
(1+1)
- 1 (1 as
;
(mir
क. 11-++1) log i (1+1) - log /. (
4+
Σ (1-177)
1+1 ( /
A, (7<h/ (1(
- -(((")))
|=1-
Sn /n||A|l>o |Tū
11
Σ JEN, 1=1-7+1
j
(nc
(1(5)) ]
(89)
In the same vein as Lemma 8, we can bound the term - as detailed in the following lemma. The proof omitted due to its similarity with that of Lemma 8. Lemma 10. When 1 2 27, it holds that
with (w."),
Σ
(2) 1I 54 +1)
M+++
Σ
11 + 22226 + 18V (ofeant-7))
1=1-7+1
1-1-27+1
Plugging the above lemma into (89), we have
(Ti, - न.. (1) log ; (++1)
log ; (
147+1
Vo,TD V0,0+225 ++22(2 + 118 /ososs my))
$ 17 /11lllo0 |! - 7( +2 111 Σ
(v2((++1
Σ
JEN.
1-1-29+1
1 17 11 11 [1dmax(7 + 1)5/2
-i, ((- 1|2
2
647-1
+ Σ
18(7 + 1)3//2
Σ
1500) 1(7 + 1) 13 (lss((l(
JEM
1-t-2
(1) S 11
14dmax ( + 1)133/22L(
(T. | (11-)
4-7-1
+
Σ JEN:
(47++)33/2
Σ
(1) 2(7 + 1)5/2 10 gistee p>
1=t-2++1
where (i) results from similar arguments in (82) and (ii) invokes Pinsker's inequality. Substitution of the above inequality into (88) and summing over i E V leads to
(1 14ydmax ||All (7 1) 1K2 (T (1)+++)
Mo++ Σ
< (L (1((11) + 17 1|All 0a
Σ (iJER
4(7 +
+ +( + 1) (o (m))
1-1-2
My++1
(c+1)) < (1 + 4rydmax |1 (7 + 1)3/2
Σ
(1 + 21ydmax ||Alloo (x + 1)5/2 1)+1) (20 (nfe mh)
1 2
Summing the above inequality over I
27 1,.., , 1 and adding
Σt Eiev (L( (n((+t) || [
to the both sides,
Σ 3 ( (1))) 2
Σ KL m
(
37

---

Published as a conference paper at ICLR 2023
T-1 $
T-1
Σ
+
Σ Σ
(L
KL
1| mtte))
2=
T-1
+ 47ddmax ||Al + 11 1)
( + 21dmax ||All (7 + 11)//2
Σ
2=
1-t-2y+1
1=27
@ 1
(1 kT) [| 11
T(.T) (((( mT,))
1/T
t=2 +iE
- (1 28mdmaa ||A (7 +
(7+1)8//2 1)5/2)
v + 14mddmax | (7 + 1)6/2
Σ 26()))
2=
T+7
T+7-1
+ 121jdmax || (7 1++1) ())/)
( + 21dmmxx
|A (7 (7+1))/73
v0(1)
1=1
k=
1 { (1 (T))K( x(27)) 11 Σ T7T
Σ
mi,)) T A -
n1;))
2- +LEV
T
- -11-28( 28(1 + q
)ndmax || (7+ + 1)5/2)
(11))/22
100 + 14(1 + 17) 1| (1 + 1)6/2
Σ
(5(0))
2
2=
lET
Here, (i) invokes the bound established in (84). We remark that our choice of learning rate
1
1
7 min
2T(T + 1)' 42dmax || (7 + 1)5/2
guarantees 1 - -28(1 27 Mddaax
|| (7 + 1)5/2 2 0. This taken together with (85) and Lemma
9 gives
2 KL (== || (1))--)) + Σ
KL (L(
m
3
27
EVV
T
(1 - (() || ((1))
Σ
-i,))² A,(7(N(0) xイ)) + 1
2510)
2 lET
t= iEV
37
KL || (1=) + Smm Tdmaxx ||A +
dmax || (2 + 11) + 37 log Smax
1/7
2
KL || (0) + n + 361TTT log Smax
(90)
1/
Bounding the QRE gap. With Lemma we have
T T-y-1
|1
Σ
(F(1))
max
KL( || 1(++1) + TKL( || x;;))
3r2 max
|
T-y-1 Σ
2 LKL (T+
([(((()) + KL (1( || (T:)) )
< max
0o
2r
Since the mapping/ 1 + vi(l) is injective, we have
T-
T T-4-1
T-1
Σ
Σ KL(T (t+1)
((,))
Σ
Σ
KL
(T
(n
|| |
S Σ Σ KL
KL ( (
27
iEV
2 NEV
2 sEV
Combining the above two equalities gives
T-
Σ
CRE-Gap, Gap,(T(+11) (+11)
2=
38

---

Published as a conference paper at ICLR 2023
fdd max
|
7 T-7-1
I-1 +
S max
Σ
KL (((+1
KL
Σ
KL (=(x((+1)
||
|
2T
1=
1=
3d
||All
T-1
< max
Σ
KL न [(0
Σ
(L
|| m
2T
2
EV
3ddmax
|
S
max
KL
(
|| ( + n + 36mrny log Smax)
2T
where the last step results from (90).
E PROOF OF AUXILIARY LEMMAS
E. PROOF OF LEMMA
To prove this lemma, we recall key observation in Cai et (2016) that allows one transform a zero-sum polymatrix game G = {(V, E), (Sthevv (Ashe,)))) into pairwise constant-sum polymatrix game Ç ((V,)) (St (Anee))))) such that
(1) For every player i V, it has the same payoff in G and
g:
w.(s) = (s),
vs E
(2) For each pair (i,j) E E.i j. the two-player game ف is constant-sum, i.c., there exist constants aij = O'js such that
A1g(s1,83) Ago 8i) Oaj
(91)
holds for all E Sg E Sj.
We are now place prove Lemma Let I be the pairwise constant-sum polymatrix game associated with G after the above payoff preserving transformation. We have
Tu mL.) + un (T m
VVV
üū (Tay (T xL,) + -i
VV
Σ
Ay s3)
A
E
+
Σ
(rg((1n
oij - A5i(
E senme
+ Sunteiaju
(KJ)E
Σ Oni
O,
(JJER
where the penultimate line uses (91), and the last line uses the fact that ς is also a zero-sum poly- matrix game, which satisfies
Σ ai Σ (UEE
Aus(s, 83) + Ax((s,,
Eū((s) (s)
(N.))E
iEV
JEV
for any arbitrary E S.
E.2 PROOF LEMMA
In view of the update rule (7), we have
log n ((+1)
(1- log q (1)
(++1) +c
39

---

Published as a conference paper at ICLR 2023
for some constant C₃- On the other hand, it follows from the expression of QRE in (4) that
TyT log nA + c
(92)
for some constant c,. By combining the above two equalities and taking the inner product with : (1+1) Ti.,, we have
; (!) (logm; (1+1) (1 777 T
nf log T -((+1) - mx,5) n( mT,) A, (T(
(++1)
x,,
(93)
Summing the above equality over i E V gives
(log π (++1) (1 - 177) log x (1) T5T log प,, T(++) x+-) -
11+1) x;. 1 A (x(1+++)) -
7)
(T:: ((+1)) T A₂ (++1) + ( T AsTi]
11 Σ
(x (m(((11)) A + (Tt,)) T (
")
iEV
iEV
Σ
(+( + u,((T?) 0,
&EV
where the last line follows from Σiev (T((t)))) A,T; + (m,,)) (A,((+))) = 0 due to Lemma 1, as well as that the game is zero-sum.
E.3 PROOF OF LEMMA
Recalling the definition
(RE-Gap,(T) = max VV
max Ui, (T T-1) u, (T)) (x(EA(S.)
(i Ti) - u1 (T))
max (EAA(S))
iEV
max NEV (
[1,r (5. 24,5 (TT,, T-]
iEV
where the inequality holds since max Ui (T. - (i) u4, for all E V. We now proceed to decompose
Σ iev
|u4 (T.. (T, -i])
[uir (Thy π -)) - u4 (Ti π --]]]] - Σ (H((T.)) - -((Ti,))
REV
iEV
Uiir (THy -1)) - Ui (TT T m(),) - Ui (Tii πI -i) :) + U (Ti π m
REV
U4,7 ( σI T1 - U (
TI _ (H((TT)) - H(
iEV
+
W (T/s IT mrir)) Wirr (Mi T
(94)
iEV
where the first line follows from Σiev (u,,((T) - H(())) = Σiev (ui,-(=)) -H(m(,)) by the definition of zero-sum games. It boils down control the terms the RHS of (94).
=
To control the first term, by the definition of u,,- in (5) (see also (3)), it follows that
Uirr (TT T-)) U4 U1, x.)))) us (mi --)) + us,r (T n". ( -i) (u m.r)) ( m- us ( m
40

---

Published as a conference paper at ICLR 2023
(T// x A1( n,)
Σ ( -[,) Aij(TT T}r))
JEN;
which each summand can be further bounded by Young's inequality and Pinsker's inequality as (mé ( A - rj.))= - || || - -miiii Jr -J.-
|| T(. 11 dmax ||All I| Fं. 112)
- 2 All dmax |All
+[] + dmax ||A KL KL(TiT |1 (T3))
- ||||l
s0 dmax ||A| x
Summing the inequality over j gives
Σ
[u.r (T, TT-) U4 (T TT T-i,)) ( u1, ( m=,,)]
iEV
S <TLL(T || m²) Laxx |1 KL (L(TT:11))
(95)
Regarding the second term, we have
1I U4.7 (Tir. T-4) u4, (Tir;
(H((T:) H(T).)))
NEV
Σ (mT),)) T AiiTT -T²) - T(T, log ग. (T(,)) log [
EV
Σ ((TT,)) T AA( オT)) - ((TT, log - log (or) + ( n.. log x ,1,
EVV
Σ (mT))))
(T, A,(T m;) = (T; x T A 7KL (T: [T,r
rKL( ,;)
(96)
where the penultimate step follows from (92) and the last step invokes Lemma 1.
Moving to the last term, we have
Ui (TT,, m_e,)) ui,r (1/s me, (#T - T/) A T(xt,r) log thr + T(TT) log कं
= =T(Ti, T() log -े, - T(tt,)) log ,,, + T(T() T log
=TKL(TT ((,)).
(97)
where the second line follows again from (92). Plugging (95), (96) and (97) into (94) gives
Leax ||A|
Σ [uir (T -) - ui (Ti T-:)] S TKL( ( TT)
KL (T T).
KEV
Taking maximum over n' finishes the proof.
E.4 PROOF OF LEMMA
Let ((T)
T4I E ((+1), then ((T) E A(S). The proof is completed if we can show
Regret, (1+1)2
Σ Regret,
(T( T + 1) N
(98)
iEV
where the first inequality holds trivially since Regret, (T 11) Regret (egret..(TT?!) boils down to show the second inequality of the above relation. From the definition of zero-sum polymatrix games, it holds that
(T) It then
N: (1+1), A
Ax((+1)
n
41

---

Published as a conference paper at ICLR 2023
T
Σ
A
Σ
π x(+1)
iEV
t=0
= (T 1)
(I(T) A -0.
iEV
In addition, applying Jensen's inequality gives
Σ
- (T -T=
Σ
H(m
0
Combining the ahove two relations yields
T
(T(T) Σ Regret, ,, ( , T +)
(m)
(1+1)
A.((+1)) + +H((?!²) - +7((7((+))) 2 0,
NEV
BEV t=
which concludes the proof.
E.5
PROOF OF LEMMA 5
Taking logarithm on the both sides of (7), we have
1,
((+1) _ (1 - 177) log : + 1A,
(99)
On the other hand, the definition QRE in (4) gives
TyT log म,, nATT
Subtracting the two equalities and taking inner product with -| (1--++1 Ti we get
(log n. (++1) (1 - 17) log Ti" 77t log ni,,, m. (1-77+1) x
1 (1-++1] N4. A, (1( m
Summing the above equality over V leads
(log ( ((+1) (1 175) log (1) npt log ni x(( (1- -x²))
( - A: (τ(())+1) - xス²) = 0,
SEV
where the final step results from Lemma
E.6 PROOF OF LEMMA
Recall from (71) that
KL (m; || [ (++)) = (1- KKL (9) - (1 - (T))KK || (0) KL (L(
|| [((
+ (log (11-++1) - log π (1+1), #(1-++1) - -x((=x(]]]] (((+1) nT WTKKL(((ca ( T;))
(100)
When < 7, we have n(( (1-++1) (0) It follows that
log Doga!-77 (1-++1) log x. (0) 1 0,
and that
(t+1) 1 (1 - 177 log n. (0) +n Σ (1 AA,
log n.
1=0
42

---

Published as a conference paper at ICLR 2023
n7) !,
1)
Therefore, we can bound the term (log (1- log (((])) x(1- - x((+1) as
(log7 x+1) - -log ( )(/ - x((+1)/ = (1 Σ (1 A,T x(0) - x((+1))
1=0
S (t 1)dmaax || | 20 x00) - -00 (1+11)
S 2n(( + 1)d
||A||
(101)
Plugging the above inequality into (100) leads to KL(T; || ((+1)) s (1 <TT; π (9)
(1 7T) (K( || (L(x((+1) (((-)+1))
+ 2yy(1 + 1)dmax ||
Applying the above inequality recursively to the iterates 0, 1,...... - 1, we arrive at
KL (++))
2-1 (1--7)77-11 (11 17 (1-17)KLL(THM))) (K( (11))))))) + (L(x ((l=+=t11 |
$ (1 - (m [1=(0]
4=
7-1
2n
Σ (1 111-17
1-11 -1 (4 + 1)dmax ||
4=0
Σ (11-)))--111 (1 (77 (T 11 (((1i)) + KL ( ((l |
$ (1 (TT) (TT (01)
4=
+ 2077? dmax ||Alloo
E.7 PROOF OF LEMMA
Taking logarithm on the both sides of (77) and (78), we get
7 (log a(t) log ग.
11 1 17:
(t) (log म.
100-1 -log म. ((-11)).
equivalently
log π.
(t)
log (1)
n
+ +1-
17
log I.: (t-1)
(2)
(1)
m
7
Taking inner product with -
(log n (t)
" log π. 14--(1
-1
17
log ग. 11-1) , x((1)) 0.
(1))
m
By definition of KL divergence, we have
(log m(" (8)
( (t) log
- -(1- log m (t-1) -
[t)
1)
((log क.
(
(log 7.( log (ogmtt)))
) -(1
17
(log n. (t-1) - log m,r) TT,)
[
17:
1
KKL 11 (0( + (1
17
KL ( |1 m| (1((1111 (1-1))
KL ( (1()),
+
(t)
(t)
and
(log n,
(t)
7
log (t)
log प.
11-1)
()
((t)
1
17
43

---

Published as a conference paper at ICLR 2023
1 KL (T: (m:
(1)
|
(0)
+ (1
7
KL aT: (t) || m 1))
(0)
1/1
Taken together, we get
KL KL
( 11
||
(0)
+
KL (2) |l
+ (1- (1- 17
KL (TT
(2) m| (1
[1)
7i
T//
= 1 (3)
KL ( || || 11
+
" KL (,े |1 (7()).
(102)
[()
M
On the other hand, taking logarithm of (78) and making inner product with (n(()) x;
Tip gives
(log 7( (1 -1-77 7//77) log "τ; (t-1) - -7,"77 T log ,,,: 7/ (((45")
m,,))
= = 10
- T A((7(((") -.,).
Following a similar discussion in (19) gives
KL 1..,1 (7( (1 77( TKKL Th, || T.
(t- 1) - (1 - mp T) 7)KL( (1
(|1,((11)
TKL ( )
( - (L(T(() || (1(
+ (log7
न (((55)) log म.
((:2)) (()) - 17: (क.
( (n(
Tir) T A (7((11
- x;)-
(103)
Plugging the above equation into (102),
(L (t) || ( + (1
KL KL (Mi |1 b. ) +
7
17
KL (L(T(() (0) (11((-111
(11
1/
(1- (111) {> (1!"))) -,,,) T A(( -x,))
(1 - (1-m(r))e (Tr))K((T (,, || ,
"
(1 ا/! r JKL (ाه ( (1(--) + / KL (,ج (r(")) || . KL(T |
(1)
1/1
+ " (log
न. (0) log ((0,, न. ,(aee)) -(!) )-
Rearranging the terms finishes the proof.
E.8 PROOF OF LEMMA
For notational convenience, we set
((()
(1
n,: 1111
17;
1]
(x((0)
x 1|, (((1->)]| + ||
(n
||1 + +||T(( (2) - (111
+
[()
T
ग.
1
for all i V,L 2 0. By triangular inequality, we have /!
(11") T, (1-1)
In addition, we
denote by 41 A l2 = min (2) and 4 v 12 = max max(41, (2, For 0 < 4 < l2. it holds that (2))
7 (1))))) ||
(1s ()))))
||, + (-((")))))
n (osc(( + | n, (n) (216
||
Σ
| (1) ; || + -
(((ي(n || + +1
x,
44

---

Published as a conference paper at ICLR 2023
+ |||7) |1m/0/00) )
+ || (
(1s (ng (1
3 )
800 
Σ
(1s((lt1)))
Fi
((s((((2)))
n
1
(o (2)
E
6 + (7 + 1)0z 1100 (os(((
+ (7 + 1)00 10000(1//00))
(104)
(=(1s(H) ( HAMM ++1)
Therefore, we have
Amm!!
My My(Ne (o
0f" +1+ + 1)olssnnn 110f0raa0 1
Σ
+ + + 1) (
k=e! (t)
(105)
Since 0 V (t S (2()) S s(su(() st forall i E V, t 2 0, the first term can be bounded by
ry(a call ((osgin(
(++ ()(kt)
Σ
8/0 S
2(---))((-11
1=t- 24
(x
In addition, the mapping k + Us (tt) is injective when A 2 7 (ef. Assumption 2 and 3). It follows that
(l
of t=x(0 -7
k=x(
1=
Plugging the above inequalities into (105) yields
Amma (2)
(+7
0f + (1+1-x(0) + De ")
S s(1+ xx) (0))
+(++1)
Σ 0000
1=t-2
1=t-27
b+y
+ (7+ + + (ogfestnnt Loff 11)))
< 2(7 + 1)
Σ
2
Finally, we control the term
(00)) with (1)
as:
(o) = (11
17
1/2
17
1/2
(1-1) ||
[
1
1//
(1)
17
(1
M1
(1))
(t)
7)
1/2
7
(1 - (/( )/) 1/2
[n (1))
-.
(1-1)
17:
11
1/2
77
1/2
(11=(()
|| + || - x,-
(
1/
17
1)
1
(2 + (1 - n. )))))))))))))))))))
[11- /ا )
- - ক. (t- 1
1
(t)
(t)
7/2
45

---

Published as a conference paper at ICLR 2023
{t) (1 s/( +) || ( n; 1 + ||
-
| 2 + || - -7, 1//111)
?
(1)
(2 + (1 7) -)- (
KL प )-)1)
$
{{t)
(1 / )K ( || || ( + (L (|
+ (KL (
(1)
7
8 (1)
(106)
where (i) applies Cauchy-Schwarz inequality, (ii) invokes Pinsker's inequality and (iii) is due to
(7 + 1)m S 1/2. Combining the above two inequalities finishes the proof.
E.9 PROOF OF LEMMA
We start with verifying the claim (86). Recall that
15(0) = (1
7
KL(TT) (t) (|/m(-1))
[(t)
+ (1 7 r TLL (T. (m(5))
|| 1) + (L
|| ( (n40)) + (L || (
We introduce the following standard Lemma (see e.g., (Cen et al., 2020, Appendix A.2)), which allows us bound control KL [Ts || m!) properly:
Lemma 11. Given n. T/ E (S:)) and w E RIS with log n, log T/ + w, we have
KL (T: || T() S
llo म, - log 1l/ s 22|1wolls
Therefore, it suffices to figure out the terms log n.!" - log o. (t-1), log n!!) log =11) (t-1)
log a(()
(m) log ;
and log R; (m(()) log mi
Bounding (L(T? (8) || TT 11) and (L(T)²) || (1)). The following equations follow directly from (77) and (78):
log mT()) - log n. (t-1) 1 1 [1 (n.") - -log 1logm;""1! ((-)
(107)
log :. (t) log (t) 1 (1) // [[A log -: (1-1))
In addition, we have the following bound w.r.t. the order of ||log m. ||0 which we shall establish momentarily.
|| log प. "::"""!! 11| 1l. log [S.] + 2dmax ||A||
(108)
This taken together with Lemma 11 yields
KL (e) || m| ( 11) S (33dmax ||A|| + T log (S:
(109)
KL (L(TT() (t) ([ S (7) 1) (3dmax || + 7 log (S,
Bounding KL KL(T.()) || [| (1(""))) When R ( z 1, we recall from (80) that:
(n: log म.
log π.
(t) 1 x())
111
A (=(
cn -1) (())))
t-1
A (o(0-1)
-(((())) ) (110)
Σ
(1 (1-1) 7/ T/ --1
46

---

Published as a conference paper at ICLR 2023
which leads to crude bound
KL( (nd")) m S 8/ dmaxx |1 (t Ki (0) n 11 S m7 dmax 11 (7 + 1).
When Ki (0) 0, we have
log (n(")) log q.
(t)
- - log (1))
_ -(1 (1) r) - 11) r- 1- logT!") (0)
(/1)) 1 A
(1 - 1l r) - 1/1) 1,7(1 --
(1))
L=x +1
1-1
1 - //10 ( +
Σ
(1- -1 -)
t=x
91 +1
(111)
which yields
KL KL(T!!" ) (1( S 17
dmax |1A1100 t S 17 dmax 11 (7 + 1).
Bounding KL (LT
(TT (n: (1)
|| | (t- 1)) Note that
log " - log n. 11 = (log ; (n:
log ((())) + (log 7(( log x(()) + (log [lggT!") (1) - llo ` (11)
This yields, by equations (107), (110), (111) and associated bounds,
KL
)) S m (t)
dmax |1 (7 (7+ 1) + 77 (3dmax ||All -log (S:().
Putting all pieces together, we conclude that
(1())
7
KL TT || T
11)
r) KL ( (r(!")) || (1) + KKLTT! | - + (L. =,!
+
(1
- :
{)
11:
S 31 m3
||
log |S,() 2nddmax || (r+1) 1)
= 7ddmax || (27 + 11) + 37 log (s:().
remains to prove the claim (87):
KL KL( |1 m (1)) KL || (0)) + ( log n. (0) log n. (27))
< (KLLLT) || (00)) + |log :i (0) - loo : (27) 11
27
< KL (| + 2
71 Σ (1 - 1/T 2x 2/- 2
1=1
< KL |l (0))) + 4ndmax
|| 7
where the third step results from log n. (2x) (1 177) 27 log n. (0) and Lemma II.
27 + 17 (1-77) --- (x,)
27
Proof of the claim (108). First, we prove by induction that for any k, Sr,
log म. (4) (k) log म. (4) (t) < 2dmmxx ||
V1 0.
(112)
Note that the claim trivially holds for t 0 with the uniform initialization a:(0) = - Vi V.
Assume that (112) holds for all t' < t - 1. Note that log T. 1 (1 10g T.
(t-1) ::: + (1(
we have
log (k) log (1) (1) = (1 - -)7) (10y m. (k) log म.
(1)) + (1)1)()))) (IA,T(o!")) - [A.
47

---

Published as a conference paper at ICLR 2023
2dmax ||All + 21ydmax ||Al
I (1 1/T)
max |
where the second line follows from the induction hypothesis (112). This completes the induction at the t-th iteration. It follows that for all i E V and t 2 0,
2dmax ||Al|be
2 - log |S:] 2dmax || loc
log T (1) 2 log
max TT KES;
(1) (k)
(113)
48


Reviews:
[{"review_id": "i1CITS5vwg_", "reviewer": "Reviewer_ukoW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 studies zero-sum polymatrix games where there are several kinds of delayed feedbacks. One such type is random delay, and another type is fixed delay. The paper gives new analyses for single-timescale and two-timescale OMWU proving last iterate convergence for the former and finite-time convergence for the latter.\n\nThe main conttribution is to systematically study the impact of having delays, when each player plays according to the entropy-regularized OMWU. Formally, for the case of synchronous updates single-timescale OMWU needs 1/epsilon iterations to reach an epsilon-Nash, and they extend it to the asynchronous setting with required number of iterations 1/epsilon^2. Furthermore, this requires several mild assumptions on the delays (roughly the delays are not completely adversarial, but are random). Moreover, if delays are constant and known, the authors obtain a 1/\\epsilong guarantee to \\epsilon Nash by adopting two-timescale OMWU. ", "summary_of_the_review": "Overall, this paper builds upon prior works and studies NE of standard algorithms, with the twist that there are delays, either random or fixed. The algorithms have been used before, which is both good and bad. Good because the algorithms are natural, bad in terms of the novelty. In some sense, the paper's main message is that delays can be handled and nothing goes too wrong with them, even using prior algorithms. My main concern has to do with the technical aspects of the paper: I am not too convinced that this is not an incremental set of results, given the extensive analyses for the setting without the delays. Perhaps the authors can address this concern.", "strength_and_weaknesses": "+ interesting setting for 0-sum polymatrix games with delays\n+ delays are studied in several contexts and so this paper extends prior knowledge but in the case of random or fixed delays, under some assumptions\n\nweaknesses:\n- lack of comparison to previous works without delays in terms of technical details and novelty: I am not sure how technically challenging this \"delays\" setting is, given all prior works that have significantly studied the problem. Can the authors provide a comparison or an insight for how their analysis significantly differs from previous analyses? What do the authors perceive as their main technical contribution? ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IJ5vDwX6I3", "reviewer": "Reviewer_RvDc", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 designs variants of the Multiplicative Weights Update algorithm to find epsilon-approximate equilibria (Nash and Quantal response) for zero-sum (multiplayer) polymatrix games. The main algorithm is called OMWU (optimistic multiplicative weight updates) and comes in two variants: single-timescale and two-timescale. The analysis shows that single-timescale OMWU converges linearly if feedback is instantaneous or delays come from a distribution that vanishes exponentially. two-timescale OMWU achieves last-iterate eps-Nash convergence and average-iterate eps-QRE convergence when there are bounded adversarial delays. Convergence rates are generally linear.", "summary_of_the_review": "The paper starts the journey towards understanding asynchronous MWU convergence for multiplayer games. The general direction seems promising. I am not sure how compelling the motivation is though, and it is hard to evaluate how difficult the results are to obtain / how interesting they are technically in the context of previous results.\n\nThe \"Correctness\" question below is hard to answer since there are no proofs in the paper. There are some experiments that seem to support the claims however. The theorems may well be true, I just don't see any proofs in the paper.", "strength_and_weaknesses": "Strengths:\n(1) the problem seems fairly natural, and this is the first paper that is moving beyond the two-player regimes while studying asynchronous (delayed) dynamic.\n\n(2) the introduction of the two-timescale algorithm that achieves better convergence rates under bounded adversarial delays adds some novelty to the paper.\n\nNeither here, nor there\n(1) the theorems are supported by some empirical experiments. On the other hand, the experiments seem to be on synthetic data that is created to meet the hypotheses of the theorem, rather than being experiments on real data.\n\nWeaknesses:\n(1) I feel the introduction and motivation of the paper could have been written better. While I don't directly work in this field, I am conversant in it, yet I was not able to identify *exactly* why this problem is of interest (beyond it being a, generally speaking, \"natural question\"). Even starting at the second sentence \"While conventional wisdom leans towards the paradigm of centralized learning,\" I did not understand what this 'conventional wisdom' was or where it was coming from.\n\n(2) The main technical body of the paper is mostly a listing of theorems. I did not find any proofs or intuitions about how the theorems are proved; and I do not know how technically difficult or interesting the theorems are. On the positive side, sometimes these theorems are followed by some examples of scenarios that meet the hypotheses of the theorems. However, at the end of the paper, I am not entirely sure where these results are relevant and whether they are difficult to obtain. (Once again, I don't work specifically in this area, but I have some familiarity with the general area of TML+economics and computation and these flavors of results.)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DyBYOmIRAm-", "reviewer": "Reviewer_VVFX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 asynchronous gradient plays in zero-sum polymatrix games under delayed feedbacks, while significant efforts have been made to understand zero-sum two-player matrix games. They first establish that the last iterate of the entropy-regularized optimistic multiplicative weight updates (OMWU) method converges linearly to the quantal response equilibrium (QRE), the solution concept under bounded rationality, in the absence of delays or under the randomly delayed feedbacks with some assumptions. They further demonstrate that entropy-regularized OMWU with two-timescale learning rates enjoys faster last-iterate convergence under fixed delays and continues to converge provably even when the delays are arbitrarily bounded.", "summary_of_the_review": "This paper seems to propose a new problem and then use some technique to solve it, but the property of the proposed problem and the intuition behind the technique is unclear.", "strength_and_weaknesses": "This paper seems to propose a new problem and then use some technique to solve it, but the property of the proposed problem and intuition behind the technique is unclear:\n\nWhy are the zero-sum polymatrix games under delay feedback important? What does ‘delay feedback’ mean in zero-sum polymatrix games? What are real-world scenarios that can be modeled by zero-sum polymatrix games under delay feedback? Why do we need to care about NE and QRE in these games?\n\nWhat is the challenge (e.g., complexity) for computing the Nash equilibrium and Quantal response equilibrium in zero-sum polymatrix games under delay feedback?\n\nWhy does synchronous optimization not work in zero-sum polymatrix games under delay feedback?\n\nAre there any existing algorithms that can solve the new problem? \n\nHow to obtain Eq.(8)? \\pi in QRE and NE may not be the same due to Eq.(5). Is it possible to show the result for NE instead of using this formula and the results of QRE?\n\nHow to remove t in the rate, i.e., O, before Remark 1?\n\nWhat is the intuition of Assumptions 1, 2, and 3? Are they realistic in real-world scenarios?\n\nWhy do we need to consider a two-timescale problem?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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