Learning from Delayed Feedback in Games via Extra Prediction
Authors: Yuma Fujimoto
Kenshi Abe
Kaito Ariu
Venue: NeurIPS 2025 poster ()
Keywords: Learning in Games
Delayed Feedback
Regret Analysis
Primary area: theory
TL;DR: This study raises and addresses the problem of time-delayed feedback in learning in games.

Abstract: This study raises and addresses the problem of time-delayed feedback in learning in games. Because learning in games assumes that multiple agents independently learn their strategies, a discrepancy in optimization often emerges among the agents. To overcome this discrepancy, the prediction of the future reward is incorporated into algorithms, typically known as Optimistic Follow-the-Regularized-Leader (OFTRL). However, the time delay in observing the past rewards hinders the prediction. Indeed, this study firstly proves that even a single-step delay worsens the performance of OFTRL from the aspects of social regret and convergence. This study proposes the weighted OFTRL (WOFTRL), where the prediction vector of the next reward in OFTRL is weighted $n$ times. We further capture an intuition that the optimistic weight cancels out this time delay. We prove that when the optimistic weight exceeds the time delay, our WOFTRL recovers the good performances that social regret is constant in general-sum normal-form games, and the strategies last-iterate converge to the Nash equilibrium in poly-matrix zero-sum games. The theoretical results are supported and strengthened by our experiments.

Learning from Delayed Feedback in Games via Extra Prediction
Yuma Fujimoto CyberAgent fuj imoto. wtm.mtmmmmmmmee......mmm w0w.yyymm11911mmmmmm @gmail..m....... com
Kenshi Abe
CyberAgent
abe wwe.kksss@@yyybrreeeee co.
Kaito Ariu
CyberAgent kaito k www.arrcrebrrrgettc...
Abstract
This study raises and addresses the problem of time-delayed feedback in learning in games. Because learning in games assumes that multiple agents independently learn their strategies, discrepancy in optimization often emerges among the agents. To overcome this discrepancy, the prediction of the future reward is incorporated into algorithms, typically known as Optimistic Follow-the-Re -ee-ttth-RR Leader (OFTRL). However, the time delay in observing the past rewards hinders the prediction. Indeed, this study firstly proves that even a single-step delay worsens the performance of OFTRL from the aspects of social regret and convergence. This study proposes the weighted OFTRL (WOFTRL), where the prediction vector the next reward in OFTRL is weighted times. We further capture intuition that the optimistic weight cancels out this time delay. We prove that when the optimistic WOFTRL recovers the good performances that
weight exceeds the time delay, social regret constant in general-sum normal-form games, and the strategies last-iterate converge to the Nash equilibrium in poly-matric zero-sum games. The theoretical results are supported and strengthened by our experiments.
Introduction
Normal-form games involve multiple agents who independently choose their actions from a finite set of options, while their rewards depend on the joint actions of all agents. Thus, when they learn their strategies, it matters to take into account the temporal change in the others' strategies. One of the representative methods in such aulti-agent learning is "optimistic" algorithms, where an agent not only updates its strategy naively by the current rewards, such Follow the Regularized Leader (FTRL) 2 and Mirror Descent (MD) 3 but also predicts its future reward. These algorithms are called optimistic FTRL (OFTRI) 5 and MD (OMD) [ and are known to achieve good performance in two metrics. The first metric is regret, which evaluates how close to the optimum the time series of their strategies is. When all agents adopt OFTRL or OMD, their social regret is constant regardless of the final time T 66. (5. which outperforms the regret of O(VT) by vanilla FTRL and MD 7 8). The second metric is convergence, which judges whether or not their strategies converge to the Nash equilibrium. OFTRL and OMD also known converge to the Nash cquilibrium in poly-ma aaltriatrix zero-sum games 99 I0 [2), whereas vanilla FTRL and MD frequently exhibit cycling and fail to converge 1
14
5 Therefore, the prediction of future reward plays
key role in multi-agent learning.
In such optimistic algorithms, the prediction of future reward is based on observed previous rewards. In the real world, however, various factors can hinder the observation of previous rewards. One the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

most likely causes of this unobservability is time delay (or latency) to observe the previous rewards. typical situation where such time delays in learning games matter is market (i.e., the Cournot competition 16 17 [8 where each firm determines the amount of its products as its strategy, but sales of the products can be observed with some time lags. In addition, multi-agent recommender systems are often used and analyzed [19 20), where multiple recommenders equipped with different perspectives cooperatively introduce an item to buyers. Such recommender systems also face the problem of time-delayed feedback [21] because some delays occur until the buyers actually purchase the item. Such delayed feedback perhaps makes it difficult to predict future rewards and worsens the performance of multi-agen learning.
This study proposes and addresses the problem that time-delayed feedback significantly impacts both social regret and convergence in learning in games. Our contributions are summarized as follows.
An example is provided where any small time delay worsens both social regret and convergence. This example is Matching Pennies under the unconstrained setting with the Euclidean regularizer. In detail, Thm. shows that OFTRL suffers from O( -reTreregret corresponding to the worst-case regret obtained in the adversarial setting. In addition, Thm. 7 shows that OFTRL cannot converge to the equilibrium but rather diverges.
An algorithm tolerant to time delay is proposed and interpreted. We formulate weighted OFTRL (WOFTRL), which weights the optimism in OFTRL by times. Based on the Taylor expansion, we find that the time delay m and the optimistic weight n cancel each other out. This cancel-out is also confirmed in Thms. Gand
Our algorithm is proved to achieve the constant social regret and last-iterate conver- gence. In Cor. IT we prove that when the optimistic weight one-step exceeds the time delay (n = m - 1), the regret is ( Furthermore, Cor. 13 shows that the strategies converge to the Nash equilibrium in any poly-matrix zero-sum games. Our experiments (Figs. also support and reinforce these corollaries.
Related works: Delayed feedback has been frequently studied in the context of online learning. The
delays are known to worsen regret in the full feedback 122 23 24
25 26 and bandit feedback 27 settings. In the context of learning in games, abnormal feedback has
28
29
30
31 32
recently attracted attention and been studied. A representative example is time-varying games, where
a gap between the true reward and feedback always exists as the game changes over time. Such gap
affects the properties of regret [35] 36 37 38
and convergence 39 40
2 Setting
We consider N players which is labeled by i [1,... .N.. Let A, denote the set of player i's actions. Each player i's payoff depends on its own action and the actions of the other players. Each player i's strategy is in what probabilities the player chooses its actions and given by the probability distribution 2; E X; == Aldi The expected payoff is defined as U,(21, xN). Here, U4 is multi-linear; in other words, the following equation holds
U,( "",, + a'x' ... .N) aU.(x1,. Ty. .NN) + +'U'( ",
a,, xN),
for all Ky, 2'j E X, and all a, d' e R and all j jE (1, (1...... .J..
We define the gradient of the expected payoff as u, (x (æ...... .NN) OU, ..N) /2x (Here,
we remark that u; u;(xx, (x ZNN is independent of x; because of the multi-lineeartty of U..) We use the concatenation of the strategies and rewards as x == (z)..... IN) E X (X).... , xxx) and
u(x)) = (un (æ),... , uy (.)) respectively. Based on the multi-linearity of U. the L-Lipschitz continuity satisfied with = max(1.)) [x)( as
[[ u(x')ll S L||e0 x 2'112.
(2)
2.1 Online Learning with Time Delay
Every round / E [1,..., ,T) each player sequentially determines its strategy a E X, As a result, the player observes the rewards for each action, i.c., uf u.( ,xy) (called full feedback

---

setting). Here, uij indicates player i's reward by choosing action aj. Thus, in online learning, each player determines the next strategy + by using the algorithm f. of the past rewards {u; Isest which is denoted as
x x- = filu,
(3)
Let us further define a time delay in the observation of past rewards. When the time delay of m E N steps occurs, only the rewards of "u]"""ss Iisee are observable in Eq. 33. Here, assumed that rewards before the initial time give no information, i.e., ut = for all S 0. Thus, the time delay modifies online learning algorithms follows.
Definition (Online learning with time delay). With the time delay of N steps, online learning modified as
t = [i(su"""ssssh),
where ui 0.for all
2.2 Follow the Regularized Leader
Under the full feedback setting, one of the most successful algorithms is Follow the Regularized Leader (FTRL). The generalization of this FTRL formulated as follows.
Definition (Generalized FTRL with time delay). With the time delay of m steps, generalized FTRL 5 is formulated as follows
1+1 arg max !J &,EX
Fi m
U
h(a:))
Here, h(xx)) is 1-strongly convex and is called regularizer.
Here, R is learning rate, and h is regularizer. m depends on the details of FTRL variants, typically, vanilla 22) and optimistic FTRL [5].
Algorithm (Vanilla FTRL with time delay). When m = 0, generalized FTRL corresponds to vanilla FTRL.
Algorithm 4 (Optimistic FTRL with time delay). When m uu ut-" generalized FTRL corresponds to optimistic FTRL (OFTRI).
3 Issue by Time Delay
In this section, we introduce an example in which any small time delay worsens the performance of OFTRL. As an example, we define Matching Pennies as follows. This is the simplest game that provides eycling behavior by vanilla FTRL.
Example 5 (Matching Pennies). Matching Pennies considers two players (N 2) with their rewards;
+1
-1
u1 +A2
u2 AT A
+1
(6)
Let us focus on two aspects: regret and convergence. First, individual (REG;) and social (REGTOT)
regret are defined as
T
(T) = max E.E.
Σ (z.
x ui), REGToT(T)) = Σ (T).
(7)
It has already been known that without any time delay, achives achieves constant social regret (called "fast convergence" (5). However, if a slight time delay exists, OFTRL suffers from the social regret of Q(VT) least even in such simple game (see Appendix for the full proof). This regret also obtained under an adversarial environment [5] and thus is worst-case for OFTRL.

---

Theorem 6 (Social regret of (V(TT) by time delay). Suppose that the strategy space is unconstrained (æ; [Rl:d)) in Exm. 5 with the Euclidean regularizer (h(x;;) = 12221122). Then, when both players use OFTRL (n = 1) with any time delay (m 2 1), their social regret is no less than S(VT) (T), which is achieved with 1) L/VT.
Proof Sketch. In the proof, we consider an extended class of OFTRL, where the weight of the optimistic prediction of the future is generalized. By direct calculations, we obtain the recurrence formula of the dynamics of both players' strategies. We prove lemma that this recurrence formula is approximately solved by circular functions, whose radius varies with time depending on the time delay m and optimistic weight n. Here, we emphasize that the rate of the radius change ea with = m - n + 1/2. Thus, if the players use OFTRL (n 1), the radius always grows (a >> 0) for any time delay 2 In conclusion, OFTRL performs the same as vanilla FTRL and suffers from the social regret of (2(TT) at least.
Second, the Nash equilibrium defined as x== = (zf 1. ,,,,,, xx) which satisfies
x. E arg max (z m.ER2
(8)
for all i 1,... .N. We also denote the set of Nash equilibria as X', In poly- zero-sum games, where the payoff U, is divided into the zero-sum matrix games, it has been known that OFTRL achieves convergence the Nash equilibrium. This convergence is measured by the distance from the Nash equilibria, which is formulated as
DIs(T)
min x E-
Under the existence of any small time delay (m 2 1), the distance (DIs(T)) does not converge but rather diverges follows (see Appendix [oror the full proof).
Theorem 7 (Divergence by time delay). Suppose that the strategy space is unconstrained (x; E (lA:I) in Exm. S with the Euclidean regularizer (h(xx)= = || 12/2). Then, when both the players OFTRL (n 1) with any time delay (m 2 1), their strategies diverge from the equilibrium (limy-soe DIs + oo).
Proof Sketch. We reuse the lemma in the proof of Thm. 6 showing that the dynamics of the strategies of both players are approximately solved by circular functions, whose radius varies with the exponential rate of a = m n + 2. In OFTRL (n = 1) with some delay (m 2 1), the rate is positive (a > 0), meaning that the radius is amplified with time. Because the equilibrium is the center of the circular function, the divergence from the equilibrium is proven.
Interpretation of Thms. 6 and 7 The crux of their proofss is that the exponential rate of the radius change (a:) is divided into three terms: 1) expansion by the time delay (+m),, 2) contraction by optimism (-n), and 3) expansion by the accumulation of the discretization errors. These terms intuitively explain the previous and present results. First, in the case of vanilla FTRL (m n 0), the radius grows with the exponential rate of a 1/2. This means that the strategies diverge from the Nash equilibrium over time, and social regret converges only slowly. Second, in the case of OFTRL (m = 0, n 1), the radius shrinks with the exponential rate a = 1122. This means that the strategies converge to the equilibrium over time, and social regret becomes constant. Finally, if OFTRL accompanied by a time delay (m 2 1, n = 1), the radius grows with the exponential rate of a 2 1/2, resulting in the social regret of Q(VT) again.
Remark on unconstrained setting: Note that Thm. 6 considers the unconstrained setting. In other words, the dynamics assume no boundary condition in the strategy space. This unconstrained setting necessary to analyze the global behavior of the dynamics, which differs on the boundary of the strategy space in the constrained setting. However, this unconstrained setting is sufficient to capture the worsening of the performance of OFTRL. At least, our experiments observe the same results as Thms. 6 and 7 even in the constrained setting.

---

Algorithm
So far, we understand an issue that OFTRL becomes useless due to the effect of time delay. The next question is how the property of constant social regret is recovered, even under time delay. In the following, we propose an extension of OFTRL, where the optimistic prediction of the future reward added E N times.
Algorithm 8 (Weighted Optimistic Follow the Regularized Leader). Weighted Optimistic Follow The Regularized Leader (WOFTRL) is given by m = nu, for n. E N in generalized FTRL.
Interpretation of WOFTRL: WOFTRL can be rewritten as
/ arg max 1/ ( Ø.) h(,;)
/ Σ u
nu,
(10)
EX;
For arbitrary time series {v'} ht, we define the finite difference the time series as
8o' e u - et, 8ōv' de - 80
(11)
In Eq. 1O the following relation is satisfied;
نz u t-m + nōu! m-m
(12)
By definition, we evaluate the time-delayer terms
1-1 (-1
u t u -mmu, Σ
Σ
5dn7,
=8u;
5ōu..
(13)
------1
By substituting these into Eq.
12
we obtain
1-1 [-1 sōu +
t-1 Σ
8 = u + (n m)ou
Σ
(14)
In the RHS, the first term corresponds the vanilla FTRL without time delay and is O(). Here, is known that predicting future rewards enhances performance in terms of social regret and convergence. Since du; in the second term shows the time derivative of rewards and O11). pushes ahead the time in u. Thus, if its coefficient is positive (n m 0), the second term contributes to predicting future reward and is expected to improve performance. weight n and time delay m conflict with each other. Finally, the third term is a prediction error which consists of the accumulation of only dōu! and O1r)). Thus, this term is negligible if sufficiently small.
addition, we remark that an optimistic
Constant Social Regret
This section shows that our WOFTRL can achieve constant social regret. For the regret analysis, let us introduce the following Regret bounded by Variation in Utilities (RVU) property [5].
Definition (RVU property). The time series of {a! is defined to satisfy the RVU property if there exists and 0 < B < y such that
T
T
REG; (T) < a + 3
|
! 11-1 x
1
(15)
1=1
We can prove that WOFTRL satisfies this property as follows (see Appendix D for the full proof). Theorem 10 (RVU property when + 1). When n m + 1, WOFTRL using learning rate ni satisfies the RVU property with constraints a hmaxx //,, X2 and 7 = 1/((n). Here, we defined X = (m + 1)(m 2).
5

---

Proof sketch. The basic procedure of the proof is the same as the previous study [5]. We show that when n m + 1, the cumulative payoff (øf in Eq. (TO)) well upproximates the gold reward until time 1, defined as
g
(16)
Here, note that is X times larger (worse) than without the time delay. À is interpreted accumulated errors in predicting the gold reward. Indeed, the difference between the gold and predicted rewards is described as
ui (m +1)2 m-1
(17)
5 m
where the total time gap in its RHS is evaluated Ee {8 (1 1)} (m++ 1) +2 X.
Corollary 11 (Constant social regret with time delay). When m 11 WOFTRL using the learning rate of = 1/22LL achieves the social regret of ((m²), ie,, (T) = (mm?).
Proof. Sum up for i E {1. , N the RVU property in Thm. 10 then the second term of the payoff lower-bounded by the I--Lipschitz continuity as
| u - S L2 x' 11.
(18)
By directly applying 1/(2)L), the second and third terms canceled out, and obtain
REGToT(T) < Lh O(m²).
(19)
Remark on Cor. 11:
An important remark that the time delay m worsens social regret. One
demerit is that must use Á (m + 1) 2)/2 times smaller learning rate. This leads to
another demerit that the social regret becomes X = (m + 1)(m + 2)/2 times larger, too. addition,
remark that if no time delay exists (m 0), the previous result (Cor. 6 in (5) is restored as
A = 1. We also obtain the individual regret of (m33/211/1) by utilizing Thm. 10 (see Appendix
for details).
5.1 Experiment for Matching Pennies
We consider Matching Pennies defined in Exm. Now Fig. provides the experiments for WOFTRL with the Euclidean regularizer, i.c., h(x,) x 12
Constant social regret when > m: First, see the upper left triangle region of Panel A. This region corresponds to >> m, where the optimistic weight is greater than the time delay. It shows that the regret is sufficiently small. In detail, Panel B shows the time series of the regrets for various optimistic weights n with a fixed time delay (m = 10). In the cases of n > m (i.e., n 11, 13, 15). we see that the regrets converge to sufficiently small values. Finally, Panel shows the two ways to take the learning rate 7). When we keep 7) constant, the regret is also constant (O(1)), independent of the final time T. This is completely different from the case of n 1/VT where the regret grows with O(VT).
-socill regret when n < m: Next, see the lower right triangle region of Panel A. This region corresponds S m, where the optimistic weight smaller than the time delay. shows that the regret takes various values and is relatively large. In detail, Panel B shows that the regret oscillates and large the case of n S m (i.e., 1,3, 5, 7, against m 10). also shows that transition in the behavior of the regret occurs

---

A
Phase diagram of regret
B
Convergence of regret
C
Scale of regret
40
2.0
2,0
n: Optimistio weight
24
10 RegTot
1.5
log 1 RegTod
14
O(VT)
l08 000
13
0(1)
10
-0.5
m Time delay
log
log T
Figure I: Regret analysis for Matching Pennies (Exm. 5). A. The phase diagram of social regrets for various time delays m (horizontal) and optimistic weights n (vertical). The deep blue color indicates that the regret is small (reg))regret, while the green and yellow ones indicate that the regret is large (O(vT)) rregret). A transition is clearly shown between ((1)- and D(vT)-regret We set the parameters as 10 and v = 10-2 B. The convergence of social regrets for various optimistic weights n and a fixed time-delay the regret oscillates and is relatively large for n 1,3, 5, 7,9 (O(vT)-regret) but converges to small value for n = 11, 13, 15 (Oeerrrr)) A transition clearly observed again in m = n. We set the parameters (corresponding to the red star in Panel A). We plot the two ways to take learning rate: 1) = 1/vT (blue dots) and 77 O()) (orange ones). The regrets for 7 (1/VVT) follow the broken blue line, which has slope of 1/2 (meaning that the regrets are O()T)). On the other hand, the regrets for ((1) follow the broken orange line, which has a slope of 0 (meaning that the regrets are (1))).
10 (corresponding to the red broken line in Panel A). We see
10-2 C. The scale of social regrets in the case of m 10 and
11
We set 1/ V for the blue dots and 17 = 10-2 for the orange ones.
regret when > Finally, see the particular region where m is large but 7 m is sufficiently small (e.g., m and ni = 35) in Panel A. Note that the regret O(vT) even though this region satisfies n >> m. This -regreregret due to the finiteness of the learning rate n, When there is sufficiently large time delay (e.g., = 30) against finite learning rate (c.g., = 10-2 in Panel A), it becomes difficult to estimate the current status from the time-delayed rewards. This difficulty is related to the accumulation of estimation errors following A = (m + (m + 2)/2 2 in Cor. I1 If we take sufficiently small 77. the fast convergence occurs the wider region of > m.
Exceptional
5.2 Experiment for Sato's Game
4 We further discuss an example of a nonzero-sum game. We pick up Sato's game Rock-Paper-Seiisoor but some scores are also generated in draw cases, as follows.
which is
-1
-1
0
0
1
= +(A+ D)æ2, U2 - A
A =
+1
0 -2
D
0
0
+2
10
0
0
2
(20)
In such nonzero-sum Sato's games, heteroclinic cycles with complex oscillations that diverge from the Nash equilibrium observed [5]
From our experiments (Fig. we obtain similar results to those in Fig. 0 (i) Constant social regret when n > m, (ii) ((VT)-((Cc))) social regret when n S m, and (iii) Exceptional O( ((vT)-socia regret
when n > m.
6 Convergence in Poly-Matrix Zero-Sum Games
We also show that WOFTRL convergences to the Nash equilibrium in poly-matrix zero-sum games, which are separable into zero-sum games between couple of players, as defined below.
7

---

Phase diagram regret
B
Convergence of regret
C
Scale regret
40
3.5
dttry
Optimistie weight
150
log Reg Tt
3.-
Reg Tot
y- OC1
125
O(V T
2.0
10 10ggoReg
10g
10-
2.0-
0(1
10-
200
15.
m1 Time delay
1og
log T
Figure 2: Regret analysis for a Sato's game (Eqs. 20 with the entropic regularizer, i... h(x)
(x, log x). The results and parameter settings for all the panels are the same those in Fig. | A. The phase diagram of social regrets for various time delays m (horizontal) and optimistic weights n (vertical). B. The convergence social regrets for various optimistic weights n and fixed time-delay m = 10 (corresponding to the red broken line in Panel A). C. The scale of social regrets in the case (corresponding the red star Panel A).
of 10 and
Definition 12 (Poly- matrrxx zero-sum games), Poly- Poly-matrix zero-sum games are
A Awryay
A
- (at)
(21)
Matching Pennies is special case of poly-matrix games. In poly-matrix zero-sum games, the strategy converges to the Nash equilibrium for a sufficiently small learning rate (see Appendix for the full proof).
E
Corollary 13 (Last-Iterate Convergence). Suppose h is a convex function of Legendre type H4 45
When n = m - 1, WOFTRL using the learning rate of r <
1/(v/n²² L) converges to the Nash
equilibrium, i.e., there exists x² X such that lim || T
x
Proof Sketch. We follow but extend the method by the prior study [T] First, we prove that when the regularizer is Legendre type, generalized FTRL is equivalent to its MD (mirror descent) variant [6]. (We remark that this is an extension of the already- -nownn equivalence between vanilla FTRL and MD [46] (5).) We thereafter show the last-iterate convergence via this MD variant. Furthermore, for each Nash equilibrium x E 2", we find a divergence V V'(x") defined as
v'(x") = D(x" x') { DD( x' 1
Σ n (D(x'"", ,x""")"") D(E""" "(x'-r11))
(22)
which monotonically decreases with time f. We prove that this divergence decreases to 0 for one equilibrium x=, meaning that WOFTRL converges to the equilibrium.
6.1 Experiment for Rock-Paper-Seissors
Now, Fig. shows the simulations for weighted Rock-Paper the nonzero-sum term D eliminated.
Scissors, Sack--appr-Seiissors,, formulated as Eqs. 20 with
Last-iterate convergence when n > m: See the two right panels, where the optimistic weight (n 5, 6) dominates the time delay (m 4). Thus, the trajectories converge the Nash equilibrium, meaning last-iterate convergence. Here, we also observe that when the optimistic weight is larger (n than 5), convergence is faster.
non-convergence when < m: See the two left panels, where the optimistic weight (n = 3, 4) does not dominate the time delay = 4. Thus, the trajectories fail to converge but rather diverge from the equilibrium. Here, we also see that when the optimistic weight smaller (n 3 than 4), the divergence is faster.
8

---

= 3
π1 4
= 5
6
Initial
Final
Nash
n < m Non-Convergence
n > m Last-Iterate Convergence
Figure 3: Convergence analysis for weighted Rock- Kock-Paper-Scissone with the entropic regularizer, ie.. h(x;)) (z,, 1o) We the parameters as 7) = 10 and
The colored lines are the trajectories of learning. The black dot, black star, and white star indicate the initial state, final state, and Nash equilibrium, respectively. From left to right, optimistic weights are n = 3, 4, 5, 6. In the left two panels (n & m), the black star does not overlap the white one, meaning non-convergence. On the other hand, the right two panels (n m), the black star overlaps the white one, indicating last-iterate convergence.
7 Conclusion
This study tackled the problem of time-delayed full feedback in learning in games. First, demonstrated, in a simple example of Matching Pennies with the unconstrained setting, that any slight time delay makes the performance of OFTRL worse from the perspectives of social regret (Thm. ()) and convergence (Thm. Z To overcome these impossibility theorems, we introduced WOFTRL, which weights the optimism of OFTRL times. The Taylor expansion for the learning rate revealed that the optimistic weight n cancels the time delay m out (Eq. (14)). We proved that when the optimistic weight even slightly dominates the time delay regret (Cor. TT and last-iterate convergence (Cor. 13) hold. Our experiments (Figs. strengthened the results of these corollaries.
+ 1), both constant social
One future direction is to consider other types of time delay. Although this study only considered that the delay is constant value, real-world delays are often more complicated. For example, previous studies on online learning have discussed situations where m is given stochastically [31 32
extent applicable to such stochastic delays; It is sufficient to take a larger n than the possible delays and use the reward before n 1 steps every time, i.e., use GFTRL with m = na. n++ Another direction is to obtain the convergence rate for WOFTRL. This study opens the door to time-delay problems and offers various straightforward open questions the field of algorithmic game theory.
adversarially 24 25 26] We remark that the theory of this study is
Acknowledgments and Disclosure of Funding
Kaito Ariu was supported by JSPS KAKENHI Grant Numbers 23K19986 and 1291.
References
[1] Shai Shalev-Shwartz and Yoram Singer. Convex repeated games and fenchel duality. In NeurIPS, 2006.
[2] Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In COLT, 2008.
[3] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley-Interseieen 1983.
[4] Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.

---

[5] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. In NewrIPS, 2015.
[6] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In NeurIPS, 2013.
[7] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, 2003.
[8] Shai Trends@ in Machine Learning, 4(2):107-194, 2012.
et al. Online learning and online convex optimization. Foundations and
[9] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In ICLR, 2018.
[10] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Shema Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-poim problems: Going the extra (gradient) mile. In ICLR, 2019.
[1]] Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in
games. In NeurlPS, 2020.
[12] Yang Cai, Argyris Oikonomou, and Weigiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. In NeurlPS, 2022.
[13] Panayotis Mertikopoulos and William Sandholm. Learning in games via reinforcement and regularization. Mathematics of Operations Research, 41(4):1297-1324 2016.
[14] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In SODA, 2018.
[15] James P Bailey and Georgios Piliouras. Multi-agent learning in network zero-sum games is hamiltonian system. In AAMAS, 2019.
[16] Ludo Waltman and Uzay Kaymak. Q-learning agents a cournot oligopoly model. Journal of Economic Dynamics and Control, 32(10):3275-3292 2008.
[17] Emilio Calvano, Giacomo Calzolari, Vincenzo Denicolo, and Sergio Pastorello. Artificial intelligence, algorithmic pricing, and collusion. American Economic Review, 110(10):3267- 3297, 2020.
[18] Jason D Hartline, Sheng Long, and Chenhao Zhang. Regulation of algorithmic collusion. In CSLAW, 2024.
[19] Joaquim Neto, A Jorge Morais, Ramiro Gonçalves, and António Leça Coelho. Multi-agent- based recommender systems: a literature review. ICICT, 2022.
[20] Afef Selmi, Zaki Brahmi, and M Gammoudi. Multi-agent recommender system: State of the art. In ICICS, 2014.
[21] Jiaqi Yang and De-Chuan Zhan. Generalized delayed feedback model with post-click informa- tion in recommender systems. In NeurlPS, 2022.
[22] Marcelo J Weinberger and Erik Ordentlich. On delayed prediction of individual sequences. IEEE Transactions on Information Theory, 48(7): 190:11999999 2002.
[23] Martin Zinkevich, John Langford, and Alex Smola. Slow learners are fast. In NeurlPS, 2009.
[24] Kent Quanrud and Daniel Khashabi. Online learning with adversarial delays. In NeurIPS, 2015.
[25] Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Delay-tolerant online convex optimiza- tion: Unified analysis and adaptive-gradicn algorithms. AAAI, 2016.
[26) Ohad Shamir and Liran Szlak. Online learning with local permutations and delayed feedback. In ICML, 2017.
10

---

[27] Gergely Neu, Andras Antos, András György, and Csaba Szepesvári. Online markov decision processes under bandit feedback. In NeurIPS, 2010.
[28] Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Online learning under delayed feedback. In ICML, 2013.
[29] Thomas Desautels, Andreas Krause, and Joel W Burdick. Parallelizing exploration-exploitaiio tradeoffs gaussian process bandit optimization. J. Mach. Learn. Res., 15(1):3873-333 2014.
[30] Nicol'o Cesa-Bianchi, Claudio Gentile, Yishay Mansour, and Alberto Minora. Delay and cooperation in nonstochastic bandits. In COLT, 2016.
[31] Claire Vernade, Olivier Cappé, and Vianney Perchet. Stochastic bandit models for delayed conversions. In UAI, 2017.
[32] Ciara Pike-Burke, Shipra Agrawal, Csaba Szepesvari, and Steffen Grunewalder. Bandits with delayed, aggregated anonymous feedback. ICML, 2018.
[33] Nicolo Cesa- cisa-Bianchi, Claudio Gentile, and Yishay Mansour. Nonstochastic bandits with composite anonymous feedback. In COLT, 2018.
[34] Bingcong Li, Tianyi Chen, and Georgios Giannakis. Bandit online learning with unknown delays. In AISTATS, 2019.
[35] Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time- varying zero-sum games. In ICML, 2022.
[36] Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On the convergence of no-regret learning dynamics in time-varying games. In Neur/PS, 2023.
[37] Benoit Duvocelle, Panayotis Mertikopoulos, Mathias Staudigl, and Dries Vermeulen. Multiagent online learning in time-narying games. Mathematics of Operations Research, 48(2):914-99) 2023.
[38] Yu-Hu Yan, Peng Zhao, and Zhi-Hua Zhou. Fast rates in time-varying strongly monotone games. In ICML, 2023.
[39] Tanner Fiez, Ryann Sim, Stratis Skoulakis, Georgios Piliouras, and Lillian Ratliff. Online learning in periodic zero-sum games. In NeurlPS, 2021.
[40] Yi Feng, Hu Fu, Qun Hu, Ping Li, Ioannis Panageas, Xiao Wang, et al. the last-iterate convergence in time-varying zero-sum games: Extra gradient succeeds where optimism fails. In NeurlPS, 2023.
[41] Yi Feng, Ping Li, loannis Panageas, and Xiao Wang. Last-iterate convergence separation between extra-gradient and optimism in constrained periodic games. In UAI, 2024.
[42] Yuma Fujimoto, Kaito Ariu, and Kenshi Abe. Synchronization in learning in periodic zero-sum games triggers divergence from nash equilibrium. In AAAI, 2025.
[43] Yuzuru Sato, Eizo Akiyama, and J Doyne Farmer. Chaos in learning simple two-person game. Proceedings of the National Academy of Sciences, (9(7))4748-4755 2002.
[44] Tyrrell R Rockafellar. Convex analysis. Princeton University Press, 1970.
[45] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[46] Brendan McMahan. Follow-iee-rgulaizeedeeaae and mirror descent: Equivalence theorems and 11 regularization. In AISTATS, 2011.
11

---

Appendix
A Dynamics in Unconstrained, Euclidean, Matching Pennies
Suppose the unconstrained setting for the Euclidean regularizer h(x;)) = ||x,11/2,, then the convex- conjugate
x arg max 17 (z #i) h(xx))
(A1)
R.ER
is trivially solved as
x
(A2)
We further consider Matching Pennies, where the payoff matrix is
1 +1] cc
A
(A3)
-1
By substituting Eq. (A2) into Eq. (12 the dynamics of the strategies are described as
xt + ma m mnn(u, 2 -m--)
(A4)
To simplify Eq. A4 let define
A = (2)
(A5)
Then, ut is calculated as Finally, the following recurrence formulas obtained;
ui Ax² +rree ub = - -Azie.
(A6)
Arttl Ar$ 2(n 1mmaa 2nn 2 Ar Ax² - 2(n + 1)mAa + 2n mm
(A7)
(A8)
These recurrence formulas are approximately solved as follows.
Lemma A1 (Solution of recurrence formulas). Eqs. (77 and A8 are solved as
Ari eA 0, Arly -e²1 sin O.:
(A9)
A411 d m 2 (2n)² + O(n*), 0c+1 = 0, + 2n O(T)²)
(A10)
Proof. For readability, we scale the learning rate in Eqs.
(A7 and A88
as 2n + 7,, we obtain
Aut+1 Az + (n + 1m mnAz t-m-1
(A11)
An [+1 Ari (n + Am (- + nn An 1-m-1
(A12)
By using the relation of Eqs. A9
obtain
A +i0,+1
Ax
(A13)
= [Aat + (n + 1) 1)m fm mm mm11
i1A2z - (n + 1) + mn mndxt-m-1) mm11
(A14)
(Azf idai) +i(n + 1)m (Ari i m
inn (Ar (A m--m-1
in m
(A15)
Acti0 i(n + 1)me> A +:00-
inme
(A16)
Let us prove Eq. A10 evaluated as
by induction. Assume Eqs.
A10 up to (A,, 0²), and then the time delay is
A ti0
(A17)
= (1 (1+11+00 (1 (1 - imn + 0 + i0()))
(A18)
= -ditile (1 imm +
(A19)
12

---

Using this, we obtain the LHS of Eq. (A16) from the RHS as
ex--1ti0++1 = e + i(n + 1) - -00 + -
(A20)
= + i(n 1)me 10
+ +
-inne t::00 (1 i(m + + +
(A21)
editiol (1 + in +
- (m +0(r)))))))))))))))))))))))))))) + 0(7"))
(A22)
(A23)
(m 000)) ((0)))((0000
(A24)
By comparing the real and imaginary parts in Eq. A24 we obtain
A441 = d m n +
- 1/ 12 - 0(1)), - 0
- +1==+++++(r)))
(A25)
corresponding Eq. (A10) by rescaling the learning rate 7) t 21j. Because we derived Eq. (AIO) for time t+1 1 under the assumption of Eq. (A10) until time t, we have proved the lemma by induction.
B Proof of Thm. 6
Proof. To introduce meaningful regret in the unconstrained setting, we assume that x; E Rd is bounded as
1
|
||
a
(A26)
T
However, this bound is not essential in the following discussion. Now, social regret is lower-bounded
as
T
REGTOT(T)
max
at a/i un)
(A27)
1=1,2 t=1
T
max
11 un)
+ max
12 ub
ui)
(A28)
[=1
Am1
1m 1,2
T
r
=max (0),
Az + max (222 c)
Aaf
(A29)
[=1
|
Σ
Art
|
Art
(A30)
1=1
1=1
T
2 Σ
Σ
Ari
(A31)
11
1=1
2 D
Σ
f
(A32)
Here, we define the scale of their strategy space D = min |211111
By Lem. Al we immediately obtain
d A m - n + 2
1)), 0, + () -1)).
(A33)
13

---

Using this, we obtain
T
T
Σ
1
A
e Actio
(A34)
t=1
[=1
1=1
e - -
(A35)
Aiti0 1 - lelann +on)
(A36)
Here, used
e - e
c Actiio - ((etitilee11
(A37)
Act10 (1 en (on+tann+t001))++000
(A38)
u (1
+
Act30
(A39)
Finally, we evaluate
Σ
Σ
Arf
i Σ
And
Σ
Auf
+
(A40)
1,2
t=1
exiti0 e +10
e 10,
00+1
(A41)
1 eintan + (1))) 1 (00
- 1 - (bp+aan (T
X A A-10 1 -
(A42)
e --
22 26 T+0(w cos + 2 2an
(A43)
1 - 2ear + 0 + caar++))))
2A, 1 + a( T+0 + 2an
(A44)
01)*)
max can
(A45)
172
2 (TT).
(A46)
Here, we used
- 2c ar " +0(n') cos(n) + O(r²)) + 201²+0
(A47)
1 11-ク" 00(1)) + (1 + 20n2 + +
1
1-2 21-2(1arm + +(n"))
(A48)
n + +(n²).
(A49)
The equality holds when and only when 7) ((1/VT). In conclusion, obtain the lower bound of social regret RECTOT(T) R(DVT), leading RECTOT(T) ((VT) by ignoring the scale of the strategy space.
C Proof of Thm.
Proof. In Matching Pennies, the Nash equilibrium (æi, x;)) satisfies
Ax; ATx; 0 Ari = Arg = 0.
(A50)
14

---

We discuss the distance from the Nash equilibria, which is formulated
(TS min x²" 1,1,2
Σ -
1
Σ
|c13
1
Σ
|
(A51)
2 1=122
b 1 e²
(A52)
In (a), we used the nearest Nash equilibrium from (01, 22)
1 Aryc.
arg min || 2.12
(A53)
2
In (b), we applied Lem. A1 For OFTRL with time delay m 2 1, a n m holds. For sufficiently small 77, the term of (17 is negligible, and DJ diverges with the final time T.. We have proved Thm. 7
D Proof of Thm. 10
Proof. First, for all f Rd, we define f and F as
= arg max ExEx
(<,,, f) h(xx)) F:= max (/zx,f) -(xx)) m,EX;
(A54)
In this notation, we define
1-m-1
Σ
u
E
Σ
u + (m + 1)u 1-m-1
(A55)
Here, gf represents i's cumulative rewards until time t. Also, कं is prediction of g by delayed feedback because all the unobservable rewards u, ft-m ,..., un are replaced by the latest observable reward " 1 According to g and E/. we use (g), G.) and (xt X Note that æf corresponds to the WOFTRL algorithm for the case of m +.
Now, between different f, f' E TRd, the following lemma holds.
Lemma A2 (First-order optimality condition). For all f TRd and their corresponding (f, F), F'), the following inequalities hold
|f flß -F' +F+ 7/ ( f),
(FO1)
||f' - f < (f' - f,p f),
(FO2)
||f' f|22 r/|l -1122-
(FO3)
Now, the payoff at time can be divided as follows;
- (ai, ut) = (g) x of x!)) - (x. at.
0!-1) (g), g z!)
(A56)
15

---

The first term is upper- bounded as
(g) a..06 at()
(A57)
T
lgg
2:112110
2ill2
(A58)
T
Σ
| 2112
(A59)
1=1
Σ
Σ u -mm + 1)
(A60)
1=1
T
2
Σ
Σ (t - 1)(2 - u
(A61)
s=t-m
2
Σ (1 8 + 1)]|u - uu 2122
(A62)
Am
/e t- m
Σ (t- s ++1 1)
Σ (t s' + 1) "12211211 us -
(A63)
8=
s'=t-m
T
Σ (t (1-
Σ (1 - s + 11 (Iue) - un - 11 ue -12)
(A64)
1= 8=t-m
s'=lm
1
(t +
Σ (t s + 1) 1) -u
(A65)
s'=t-m
T
X
Σ (1 (1- - 112
(A66)
[=] s=t-m
S x2
1 u 112-
(A67)
In the final two lines, we twice used
Σ (+- (m 1) + + A.
(A68)
2
Furthermore, the second and third terms are also upper- bounded as
x! -9g Σ
(g) gf
x!)
(A69)
t=1
1
-Xi G b ||ا| g:-1113 11 + Σ
G
+ X
1 -/1s: 2
(A70)
t=1 1
t=1
Gf Go
1
T
(|
9 - + |1 xB11
(A71)
7
21
T
Amax
1 T
max a:EA:
Wig
u
(11æ)
g 1 $12 + |1 xr(13)
(A72)
17
2n
1=1
T
Amax
1 T
max E.
2
Σ
|00
x -
(A73)
17
4n
tm
t=1
16

---

In (a), we used Eq. (FOI) for (f) = ( ") and (g) æ)). In (b), we used
G
maxx
0 S G
<
max E.t.
u
+
Mmax = max h(xx))
(A74)
n
17
a.Ed:
1=1
In (c), we used
11 2
Σ (12]
g
11-
119 113)
(A75)
T
Σ
(1 g 112 |19 x0(13)).
(A76)
Finally, obtain the upper bound of the individual regret REG,(T)
REG;(T)
aa
ari, u!)
(A77)
a;EA:
T
T
max mxEei
Di. Σ us!
ut
(A78)
Umax
T
T
+ 22
u
1-1
11
Σ
|
12.
(A79)
4n
1=1
Thus, we have proven that the regret satisfies the RVU property with a = /max /n, 3 = 2² and
7 == 1/((4).
D.1
Proof of Lem. A2
Proof.
F (F, h(f)
(A80)
1 || fll2
2 (P f) 1((') +
(A81)
= (f', f - h((²) - -n( -f)+ + ff' fl
(A82)
F' (f' F' f) || -
(A83)
2
In the inequality, we used 1-strict convexity of h. This corresponds Eq. (FOT). Furthermore, by summing up
(2 | fll2 - FF' F + ( P' -P)
1 - 1'1 < -F F' F'+ (F, f(()
P))
2
(A84)
| f < { P, i' f). This corresponds Eq.
(A85)
FO2).
Finally, by the Cauchy-Schwarn Schwarz incquality. we obtain
||[' f < (f - f - 1) s n/|l'
f|]2|[i' F1|2
(A86)
+ | f|]2 S v/ - Fll2-
(A87)
This corresponds Eq. FO3).
E
Proof of Cor.
13
Proof. We prove the last-iterate convergence by the following five steps.
17

---

Step 1: Equivalence between generalized FTRL and generalized MD When h is Legendre function, the strategies always exist in the interior of the strategy space, i.e. x' int(X) for all t. Furthermore, the dynamics of generalized FTRL become equivalent to those of generalized MD as follows.
Definition A3 (Generalized Mirror Descent), With the time delay of m E N steps, generalized Mirror Descent is formalated based on the prox-mapping P follows
x+41
P( m++1
m m
a g++ P(t', u'), P( :- arg max Ty u) - D(x,, Øt, DEX
(A88)
where D(æ, x') is the Bregman divergence between a, x' E X, defined as D( x')= == h(x) (x- - x', Vh(a²)) - h(æ²).
(A89)
Lemma A4 (Equivalence between generalized FTRL and generalized MD). Suppose that h is Legendre function, then the time series of (æ' /t-,... are equivalent between Defs. and A3
Step 2: Existence of Lyapunov function In accordance with WOFTRL, suppose m nu"
for n = m + 1 in generalized MD, then there exists a Lyapunov function, which is defined for all xx E X as
V'(x") == D(x", + / D(
"D(E''T, + D(#""" n
(A90)
For 7 S <1/(V8n"L). we see that this Va(') monotonically decreases for all x" E Xx, as follows.
Lemma A5 (Lyapunov function under time delay). Suppose generalized MD with n = m + 1 and S 1/(V/n2L) L), then all x² E Xx, V*(x") is monotonic decreasing as 1 V'x") D(*'+1 x²) D(x', ,²)..
vi+l (x
(A91)
By summing up Eq.
A91 for all x² E X", we derive
T
VT(x") + E xx)) + ,a))
V ('('))
(x))
lim T-000
(A92)
2
1=1
1
20
D(a++) ,00) + ((xt",a")
(A93)
2
(1 2:1 + || - 4²1l3)
(A94)
4
1=1
20
(| xt 111))
(A95)
By Eqs. (944) and (A95).
obtain
lim
a ++1
x0 ||2
lim | - -0'122 = 0. 100
(A96)
1-+0
Step 3: Existence of subsequence converging equilibrium Since X' is a compact space, the Bolzano- Weiersssssssss theorem can be applied, and there exists a subsequence {æ" Jı=1.... equipped with its limit. In other words, there exists X such that
lim x" æ.
(A97)
By using Eqs. (A96), we further obtain
lim 44+1
lim 4. æ.
(A98)
1
1
Thus, by substituting Eqs. (A97 and (A98) into the prox-mapping (the second one in Eqs. (A88).
we show that this satisfies the fixed point condition of the prox-mapping, i.e.,
के lim t 14+1 lim P(t", u(x")) .P.
lim x" lim u(a²)) 1.000
P(a,u()))
(A99)
1000
1-000
14000
In (a), we used the continuity of prox-mapping P. as the following lemma shows.
18

---

Lemma A6 (Continuity of prox mapping), The prox-mapping P(e, u) is continuous for ø E int(A)) and u E Rdd.
By the first-order optimality condition, this fixed point satisfies the Nash equilibrium condition [00, i.e. & E X In conclusion, we obtain subsequence [==")= which converges to one Nash equilibrium x' E X
Step Convergence guarantee by Lyapunov function Let x. denote the specific Nash equilib- rium, to which the subsequence [=,... converges. Because v*(x") is both lower-bounded by 0 and monotonic decreasing, there exists limits which corresponds its limit inferior, and we obtain
lim (x(") 10000
lim inf V'(x") lim V4 (xx")) = 0.
(A100)
1-000
t-500
This trivially leads to
lim D(x", .²) S lim V'(x") + lim a' = x² 10000
(A101)
10000
1000
By further using li | x² 2|2 = 0, we ultimately obtain
lim x² = x=" t1000
(A102)
indicating the last-iterate convergence one of the Nash equilibria.
E.1
Proof of Lem.
A4
Proof. First, GFTRL is obviously rewritten as
x (+1 arg max m') F g #eX
(A103)
Here, F(x,g) is the Fenchel coupling between i E X' and ğ E Rd, which is defined as
F(x, -x.))(x=))))))) hh' (g),
max (x. g) h(x))
(A104)
=
Hence, it sufficient to see the equivalence between ((x, a²) and F(x, which is proven as
D(x, x') = h(x) xx a' Vh(t*)) + h(t*)
(A105)
h(()) (a -  v²) h(())
(A106)
h(())) (a,ğ²) (6".0')) l((())
(A107)
1 h(xx) - (x, (g")
(A108)
= =F(x, g').
(A109)
In (a), we applied the first-order optimality condition for #1+1 in Eq. (888)
(mu' vh(at+)) + Vh(a'), x²) * Vh( x x¹) = (Vh(a') + rppu', , x¹)
(A110)
(A111)
(Vh(*(+1), x¹) = -(ght1, 1 x¹) x²) ) (g", x =²),, (Vh()') x
(A112)
(A113)
for all x, x'' X. This means that the projection Vh(**+1) on X' equal that of g++1, In (b), we considered that *++1 satisfies the first-order optimality condition for hi (g++1) as
h" (y') max (x, y²) h(x))
(A114)
(&' v²) h((').
(A115)
Thus, has been proven that the dynamies of r. are equivalent between generalized FTRL and generalized MD.
19

---

E.2
Proof of Lem. A5
Proof. We prove that (*(*)) monotonically decreases as
n-1
Vi+l (x*) = , { D( 220)
(D(x ( D( x }
2
n
(A116)
12 1
D(0", ,,")
- (D(x'-r+)) , + D(#'-rt),00 x²'"))
+
(Vh(att)) Vh(x²), x - -x²)
gl+1
D( ,x²) - -D(x', a²)
(A117)
2
1 (D( r+1 , (ttrt) + D(at ,aat
((a""a")
1 ((a"11=x)) - -D(x', a²))
+ 2n
(D( rrl , + x²-1))
2
(A118)
=(x", + 1
D( x 11 +
n - (D(x'T,8'')) + D(t' x
2
==1
- ,0²) 2 D 2²))
1
(A119)
- 2
V'(x*) D( ,,²) D(a', t¹).
(A120)
2
In (a), we used
D(*", 0(*",a"t) (2t1)+ + D(# D(a","" - D(x",=')) + (Vh(att))- Vh(x='),
x²),
(A121)
which is obtained by summing up the following generalized law of cosines
D(=",a*+)) = D(x", ,²*) D( .+) + (Vi(a*+)) - Vh(a"), (+*+) - -x*),
(A122)
D(a+t), ,,²)= = D( ++ (a") D( x²) + (Vh(=*)) - Vi((a"), x." -1*
(A123)
and using the Nash equilibrium condition
(Vh(E++1- - Vh(t"), x= - -x²) n uu,", x - =x')= =0
(A124)
20

---

In (b), for - 1/(8/2n2 we used
(V/( - V/((==), 1 ( - a²
(A (A125)
< [h( v/(a")11
(A126)
= = Σ u xr-r+1 - ne nn
(A127)
S 1,
Σ a [-++
nax"==
(A128)
= 1
{r(x Σ
m----r r+ 11+ + r(a rrt - x² x1
(A129)
r=1
$ 2nn L
(1(( 1-++1 11-r+113 + | x1-113))
(A130)
S 22
2 (rr 11- + | x(-r113)
(A131)
S 1 L²
(D( , x + D(# x(-r))
(A132)
$ 2n (D(x'rrt1 (2-rtz + D(#'-++11 xz(-)))
(A133)
In the first inequality, twice used
c ++1 x 1/ $ (Vh(*tt)) - Vh(x'), , g141 x²)
(A134)
< Vh( - Vh(x')) |22||//11 x 22112.
(A135)
Here, we used the 1-strong convexity of and the Cauchy-S -Shwwrz inequality.
E.3
Proof of Lem. A6
Proof. For all é, a' E int(A() and all u, u' E Rd, we define
x == P( u), o' P('',u).
(A136)
We obtain
| x' 13 (Vh(a)) Vh(w'), - x¹)
(A137)
(Vh(T) Vh(a'), x x¹) n7( u u', x¹)
(A138)
w (I)h($)) Vh(E')ll2 + n||u u u'|l2)]l x' 2'112.
(A139)
In (a), we used 1-strong convexity of h. In (b), summed up both the first-order optimality conditions for æ and x', i.c.
(nu Vh(w) Vh(i), x¹) 0, (na' ( Vh(z') Vh(i'), - x) -0. (A140)
In (c), we used the Sauchy-Schward inequality. conclusion, we obtain
||= x 2'1|2 < Vh(T)) - Vh(#')]22 + v/Ilu u'll2.
(A141)
Here, Vh is continuous on in'( By the definition convex and differentiable. Moreover, int( is an open convex set, and h(()) is finite in & E int( Thus, Cor. 2 in the study (44 is applicable, and h is continuously differentiable, meaning that Vh is continuous on int(X'. Thus, Eq. (A141) shows that P is continuous int(X') x Rdd D
convex function of Legendre type, is
21

---

Analysis for Individual Regret
By using Eq. F03 for (f', f) = (#) )) we obtain the "stability" property as
| x 1|2 S //| 1e:'11a
(A142)
mm + 2))'-m-1 (m + 1--))mmm--- mm 2112
(A143)
S (m + 1)1lu* mm ri' 2m- + 1| 1|paa-m-1100 112)
(A (A144)
S (m + L.
(A145)
This leads to the upper bound of individual regret as
Amma
T
(T) S
2211
1-1
11
a
x. 1112
(A146)
7
4n
1=1
1max
2²n
|2e "01111
112
(A147)
1)
t=1
hmax
T 1
||00
(A148)
hmax
(m 2)
(A149)
7
If we = 1/(1 (m 1)A71/44 there, we derive REG, (T) S (Amax + NN (m + 2)XT 1/4 (m13/271/1).
G Computational Environment
The codes are available
The simulations presented in this paper were conducted using the following computational environ- ment.
Operating System: macOS Monterey (version 12.4)
Programming Language: Python 3.1
Processor: Apple MI Pro (10 cores)
Memory: 32 GB
22

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We stated our contribution in the abstract and introduction (by itemizing).
Guidelines:
The answer NA means that Abstract and Introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We stated the limitations in Conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
All the proof' are in the main text or appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We show the (hyper-)parameet) to reproduce the experiments in their captions.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer:
[Yes]
Justification:
The code is available at the URL in Appendix.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
cessionnPoccyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//uuiiu wwwiicccguie//eeeeeeeeeis CoodeSubeiiieeeec ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We show the Jparametrs to reproduce the experiments in their captions.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
Our experiments are deterministic and thus do not require statistical tests.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
25

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We clarify our computer resources in Appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
This paper confirms the NeurIPS Code Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The positive societal impacts are stated in Conclusion, while there are no negative ones.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
26

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
27

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The new assets are attached in the supplement.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
28

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
29


Reviews:
[{"review_id": "qMH5iii6Q2", "reviewer": "Reviewer_wW5Q", "summary": "This paper analyzes learning dynamics in multiplayer general-sum games where each player only observes a gradient delayed feedback. The authors first show that when using optimistic follow-the-regularized-leader (OFTRL), which is one of the most standard algorithms in the absence of delay in learning in normal-form games, even a small amount of delay prevents the algorithm from achieving fast rates.\nIn particular, the sum of all players’ regrets (social regret) is lower bounded by $\\sqrt{T}$ under a specific setting.\nMotivated by this, the authors propose a new algorithm based on a weighted version of OFTRL. This algorithm repeatedly reuses the most recent feedback (more than the constant delay length), and they prove that this technique allows the social regret to be bounded by a constant.\nThey further support these theoretical findings with numerical experiments and also investigate the case of polymatrix zero-sum games.", "questions": "The reviewer expects the authors to respond to the questions in the Strengths and Weaknesses section.", "limitations": "The negative social impact does not appear to be relevant to this paper.", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper is well-written and easy to follow the contents. The writing is generally well-organized, and the problem of learning in games with delayed feedback is an important setting to study. Moreover, the proposed algorithm that achieves the regret upper bound appears sound, and the authors validate its effectiveness through numerical experiments.\n\nThat said, I believe there are several points the paper could be improved.\n\nThe first weakness of this paper is that the entire analysis focuses solely on the social regret, the sum of the individual regrets of all players. It is unclear why the authors do not consider individual regret bounds for each player.\nRelated to this, the paper often fails to clearly distinguish whether a statement refers to social regret or individual regret, which leads to confusion. For example:\n- In the abstract, it says \"regret is constant in general-sum normal-form game\", but it is hard to interpret \"regret\" here as \"social regret\".\n- In Theorem 6, the phrase “they suffer from the regret $\\Omega(\\sqrt{T})$” gives the misleading impression that each player suffers this regret, whereas the actual lower bound seems to be on the social regret only, as can be seen from the proof.\n- For the same reason, the sentence in line 111 is also confusing.\n- The definition of the RVU property in Definition 9 is somewhat unnatural. In [5] and many related works, the RVU property is typically defined with respect to each player's regret, and it is not standard to define it directly for social regret.\n\n\nThe second major weakness of this paper is that the the interpretation of the lower bounds in Section 3 is unclear. In Theorem 6, the authors analyze OFTRL under a learning rate of $\\eta \\simeq 1/\\sqrt{T}$, whereas [5] and related works typically use constant learning rates.\nSuffering $\\sqrt{T}$ regret under this choice of $\\eta$ seem natural. Why do authors analyze OFTRL under this particular learning rate?\n\nAnother issue with the lower bound is that it assumes an unconstrained setting. In studies like [5], fast convergence results are usually established under bounded feasible sets (such as the probability simplex). However, this paper does not justify why an unconstrained setting is appropriate. Can the authors provide a justification?\n\nThe third weakness of this paper is that the regret upper bound derived in this paper does not discuss whether its dependence on the delay parameter $m$ is optimal. Can this dependence be improved? Or can the authors provide a matching lower bound to show the upper bound is tight?\n\nSome of the terminology used in the paper could be more precise. In Algorithm 4, the authors call the algorithm \"optimistic FTRL\" under the choice $m_i^t = u_i^{t-m}$, but in the literature, \"optimistic FTRL\" usually refers to the more general case with arbitrary $m_i^t$. Referring to the general case (Definition 2) as \"generalized FTRL\" is also not appropriate.\n\nMinor comments:\n- Line 126: $\\mathcal{X}^*$ is undefined.\n- Eq. (10): the notation $\\tilde{x}_i^t$ is very close in appearance to the notation of actions $x$, which is confusing. The notation used in (A58) also suffers from the same issue.\n- The proof has so many typos that needs to be fixed.\n- Line 422: \"1-convexity\" should be corrected to \"1-strong convexity.\"", "was_revised": true, "final_justification": "The most concerning aspect of this paper is its dependence on the delay time $m$, which is the most critical parameter in the study.\nThe upper bound provided is $O(m^2)$, which appears to be far from the optimal dependence.\nDue to this weakness, it is difficult to recommend this paper for acceptance for now.", "rebuttal": "Thank you for your effort and comments. As far as we see, **your comments (W1, 2, 4) mainly concern presentation issues** and do not challenge our core contributions:\n- Identifying that a finite delay $m$ significantly degrades performance in terms of regret and convergence.\n- Proving that an additional prediction restores the good performance.\n\nYour comments are constructive to improve our presentation, and we can **immediately reflect your comments in the next version**. If you have any other concerns, please let us know. The following is our one-by-one responses.\n\n---\n\n**Weakness 1)** Distinction between individual and social regret:\n\nWe appreciate your support. To avoid confusing readers, we will clarify that the regret is social regret. Because prior work in learning in games typically focuses on social regret (e.g., Refs. [5, 6, 35–38]), limiting our **analysis to social regret is not a weakness**.\n\nFor the RVU property, we will revise it based on individual regret. This revision does not affect our contribution at all.\n\n---\n\n**Weakness 2)** For other choices of $\\eta$ in Thm. 6\n\nSorry for our statement confusing you. **$\\eta=O(1/\\sqrt{T})$ achieves the smallest regret lower bound $\\Omega(\\sqrt{T})$ among all possible $\\eta$**. Indeed, other choices of $\\eta$ enlarges the regret lower bound because ${\\rm RegTot}^{2}$ is decomposed into the two terms of $\\Omega(1/\\eta^2)$ and $\\Omega(e^{\\eta^2 T}/\\eta^{2})$ as shown in the proof.\n\nFor justification of the unconstrained setting, please reread our remark (Lines 151-156). The unconstrained setting is useful for analyzing the dynamics of the algorithm and for obtaining the regret lower bound because we can avoid considering dynamics on the boundary of the strategy space. Here, the boundary dynamics is no more than an exceptional case for the whole dynamics, and the regret bound is not expected to differ significantly between constrained and unconstrained settings. Indeed, previous works showed that the same phenomenon occurs independently of the constrained or unconstrained setting. For example, convergence in zero-sum games similarly occurs (Refs. [9] (unconstrained) and [10] (constrained)), and convergence in time-varying zero-sum games does (Refs. [40] (unconstrained) and [41] (constrained)). Our simulations also justify this expectation (see Fig. 3). There are **many reasons why the unconstrained setting cannot be a weakness**.\n\n---\n\n**Weakness 3)** For regret dependence on $m$:\n\nThank you for the good point. When $n=m+1$, WOFTRL incurs the regret of $O(m^2)$. This $m^2$ arises because we evaluate $m$ true rewards (from time $t-m$ to $t$) using the reward before $m$ steps (see Eq. (A69)-(A73) in the Appendix). Unfortunately, we cannot prove that this dependency is tight.\n\n---\n\n**Weakness 4)** Terminology of optimistic/generalized FTRL:\n\nFor convenience, we name the specific case $m^t = u^{t-m}$ as Optimistic FTRL, following recent literature (e.g., Refs. [12, 40]). To distinguish it from the generalized form of $m^t$, we continue to use \"Generalized FTRL\" in our paper. However, we will add a footnote noting that this “Generalized” FTRL is often called Optimistic FTRL in several prior works (e.g., Refs. [5, 6])."}, {"review_id": "V43hmevfBj", "reviewer": "Reviewer_E3gP", "summary": "This paper studies the problem of learning in games with time-delayed feedback. In this setting, a learner must choose their next strategy $x_i^{t+1}$ based only on rewards received from rounds $1$ to $t - m$; the rewards from the most recent $m$ rounds are not yet available. The authors focus on variants of Optimistic Follow-The-Regularized-Leader (OFTRL) and analyze both regret and convergence to Nash equilibrium when all players adopt the same learning algorithm.\n\nThe paper begins by showing that in matching pennies, if both players use OFTRL and there is a delay of $m \\geq 1$, each player suffers a regret of $\\Omega(\\sqrt{T})$, and their strategies diverge from the equilibrium. To address this, the authors propose a new variant called **Weighted OFTRL (WOFTRL)**. They prove that WOFTRL satisfies the **RVU property** (Regret bounded by Variation in Utilities), which allows them to upper bound total regret by $O(1)$. These theoretical results are supported by experiments on matching pennies and Sato's game.\n\nThe paper then extends the analysis to polymatrix games, showing **best-iterate convergence** of WOFTRL to the Nash equilibrium. Additional experiments on weighted Rock-Paper-Scissors demonstrate **last-iterate convergence** when $n > m$, and non-convergence when $n \\leq m$.", "questions": "1. How robust do you believe the approach of scaling the optimistic term by $m+1$ is? For instance, if the value of $m$ varies from round to round, do you think your method can be generalized to handle such a setting?\n2. From a theoretical standpoint, what happens when $n$ is significantly larger than $m+1$? Your experiments show promising results in this regime, but is there any trade-off that may not be immediately apparent?", "limitations": "No such limitation.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper addresses an important time-delayed feedback model and presents a compelling set of results, as outlined in the summary. I particularly appreciate the insightful interpretation of why OFTRL fails to achieve strong guarantees in this setting, and how WOFTRL succeeds. Specifically, the authors frame the behavior of OFTRL and WOFTRL in terms of expansion due to time delay, contraction from optimism, and expansion from accumulated discretization errors. While scaling the optimistic term by $m+1$ may seem like a simple modification, it leads to meaningful new insights into the algorithm’s behavior and is a contribution worthy of recognition. \n\nI did not identify any significant weaknesses. However, there is a small typo on line 69 that should be corrected.\n\n-----\n\nI went through the discussion between the reviewer wW5Q and the authors and found the response unsatisfactory. I had initially assumed that a social regret of $O(1)$ would naturally imply an individual regret of $O(1)$ as well. However, due to certain nuances in the definition, the $O(1)$ social regret only translates to an individual regret of $O(T^{1/4})$, which now seems less compelling in hindsight.\n\nWhile I appreciate other aspects of the paper, these concerns have led me to downgrade my score to **\"4: Borderline Accept.\"**", "was_revised": true, "final_justification": "I went through the discussion between the reviewer wW5Q and the authors and found the response unsatisfactory. I had initially assumed that a social regret of $O(1)$ would naturally imply an individual regret of $O(1)$ as well. However, due to certain nuances in the definition, the $O(1)$ social regret only translates to an individual regret of $O(T^{1/4})$, which now seems less compelling in hindsight.\n\nWhile I appreciate other aspects of the paper, these concerns have led me to downgrade my score to **\"4: Borderline Accept.\"**", "rebuttal": "Thank you for your review and positive evaluation. We further appreciate your insightful questions that advance our research. The following is our answer.\n\n---\n\n**Question 1)** For stochastic delay $m$:\n\nThank you for the good point. We have a **simple idea for dealing with stochastic delay**. If we use a larger $n$ than all the possible delays $m$ and refer to the reward $n-1$ steps before (not $m$ steps before), both the $O(1)$-regret and the last-iterate convergence can still be achieved. We will briefly discuss this idea in the Conclusion.\n\n---\n\n**Question 2)** For trade-off due to significantly larger $n$ than $m+1$:\n\nIf you enlarge $n$ while keeping the learning rate $\\eta$ fixed, a tradeoff problem arises. Indeed, Eq. (14) shows the pros and cons of taking excessively large $n$. A larger $n$ accelerates convergence via the second term ($O(\\eta)$), but also increases prediction error via the third term ($O(\\eta^2)$). **If $\\eta$ is too large, the prediction error dominates and impedes convergence** (see Lines 217–223). Unfortunately, we have not succeeded in reflecting this tradeoff in regret or convergence rate."}, {"review_id": "ijRtlggjtR", "reviewer": "Reviewer_ebu8", "summary": "This paper tackles the challenge of learning in multi‐agent games when there is a delay in observing past rewards. It first shows that even a single‐step feedback delay degrades the performance of the standard Optimistic Follow‐the‐Regularized‐Leader (OFTRL) algorithm, in both regret and convergence. To counteract this, the authors introduce Weighted OFTRL (WOFTRL), which amplifies the optimism in the predicted next‐round reward by a tunable weight. They prove that if this optimistic weight exceeds the length of the delay, WOFTRL restores the desirable properties of OFTRL: it achieves constant (O(1)) regret in general‐sum normal‐form games and ensures best‐iterate convergence to a Nash equilibrium in polymatrix zero‐sum games. Finally, empirical experiments corroborate the theoretical findings, demonstrating that WOFTRL effectively neutralizes the adverse effects of delayed feedback.", "questions": "(Q1) Is multi-linear utility common in literature? Can the authors provide examples of pre-existing work that also uses such utility/expected payoff?\n\n(Q2) What if the game has multiple Nash Equilibrium, does the algorithm still holds? \n\n(Q3) For Theorem 6, could there be any other choice of learning rate that improves the regret? How does the regret depend on $\\eta$? - I would like to see some discussion about this following Theorem 6.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\nThe paper is in general well written, empirical experiments are provided to demonstrate the effectiveness of the algorithms. \n\nWeaknesses:\n\n(W1) In related literature, the authors mention that \"The delays are known to worsen the regret in the full feedback and bandit feedback\", but didn't provide detailed discussion about how the regret is worsened. And similarly for the time-varying games literature, how regret and convergence are affected is not sufficiently discussed. \n\n(W2) Some notations are a little confusing, e.g. what's the definition of $h_{\\max}$ on line 182? \n\n(W3) The definition 9 introduces RVU property defined from [5], what's the full name of 'RVU', is there any constraint on the $\\alpha, \\beta, \\gamma$ for this definition? --- I'd appreciate it if the authors could include more discussions when introduce this new term. \n\n(W4) Is there any other algorithm in pre-existing work that also shows O(1) regret? If so how does this algorithm compare to them? How do their regret results depend on parameters like $T, m$?\n\nI'm willing to raise my score if my concerns and questions can be addressed.", "was_revised": true, "final_justification": "The authors have addressed my concerns so I raised my score.", "rebuttal": "Thank you for carefully reading our paper. Your comments are related to the fundamental (background) knowledge for our contributions. We believe we can address all of them below. In particular, if you recognize the **commonality (Q1), novelty (W4), and strength (Q2, 3) of this work**, we will take you up on your kind offer\n\n- “I'm willing to raise my score if my concerns and questions can be addressed”,\n\nand we hope that you will reassess our paper.\n\n---\n\n**Weakness 1)** Detailed relation to previous literature:\n\nWe just cite Refs. [22-42] to strengthen motivation to consider the problem of delayed feedback in multi-agent learning. In fact, Refs. [22-34] treats **single-agent** learning, which is meaningless to be compared with this study. For example, a delay $m$ is known to worsen regret by $O(\\sqrt{mT})$ in Ref. [30], but the baseline regret $O(\\sqrt{T})$ is different from ours $O(1)$. The same applies to works on time-varying games—their assumptions differ incomparably from ours.\n\n---\n\n**Weakness 2)** Definition of $h_{\\max}$:\n\nWe will note $h_{max} = \\sum_{i}\\max{x_{i}} h(x_{i})$, thank you.\n\n---\n\n**Weakness 3)** For the RVU property:\n\nIts full name is the Regret bounded by Variation in Utilities (RVU) property. Its constraint is $\\alpha, \\beta, \\gamma>0$. We will reflect these in the next paper.\n\n---\n\n**Weakness 4)** For other works showing $O(1)$ regret:\n\nAs far as we know, there is **no existing work showing $O(1)$ regret in delayed multi-agent learning**. We believe that in multi-agent learning, delayed full feedback was first proposed by us and solved by weighted prediction. Fortunately, **no other reviewers denied our novelty**.\n\n---\n\n**Question 1)** For commonality of multi-linear utility function:\n\nThe multi-linear utility is **commonly seen in the field of learning in games**. Normal-form games, represented by multi-linear utility functions, are one of the standard research subjects. In fact, many of our references (Refs. [1, 5, 6, 10-15, 35-44]) consider normal-form games and suppose multi-linear utility functions.\n\n---\n\n**Question 2)** For multiple Nash equilibria:\n\nThis study does not assume the uniqueness of the Nash equilibrium, and thus **all the results hold for games with multiple Nash equilibria**.\n\n---\n\n**Question 3)** For other choices of $\\eta$ in Thm. 6:\n\nSorry for our statement confusing you. **$\\eta=O(1/\\sqrt{T})$ achieves the smallest regret lower bound $\\Omega(\\sqrt{T})$ among all possible $\\eta$**. Indeed, other choices of $\\eta$ enlarges the regret lower bound because ${\\rm RegTot}^{2}$ is decomposed into the two terms of $\\Omega(1/\\eta^2)$ and $\\Omega(e^{\\eta^2 T}/\\eta^{2})$ as shown in the proof."}, {"review_id": "xdzXxPsDXl", "reviewer": "Reviewer_tkVS", "summary": "This paper studies the problem of online learning in games in a deterministic setting. It especially considers a case where the feedback is delayed by a number $m$ of steps at each iteration. In this setting, the constant regret that can be achieved by the Optimistic Follow The Regularized Leader (OFTRL)algorithm is shown theoretically to not be obtainable anymore.\n\nFor this reason, the paper proposes the Weighted Optimistic Follow The Regularized Leader (WOFTRL) algorithm that builds on the idea of OFTRL, but with a different weight for the last iterate. The algorithm recovers the constant regret and demonstrates good empirical results.", "questions": "What makes obtaining last-iterate convergence hard in this setting? Do you think last-iterate convergence could also be obtained in a stochastic setting (e.g. with each player sampling from their policy instead of the average reward)?", "limitations": "Not applicable.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- The article is well written and well structured, the theoretical motivations are clear.\n\n- It proposes an (although not extremely novel) algorithm that succeeds where the current literature fails.\n\n- All theoretical findings are proven with some intuitions given in the main paper. The experiments corroborate nicely with the theorem.\n\nWeaknesses:\n\n- The theoretical applications of the result are not obvious, while the practical applications may require a more flexible setting (as especially mentioned in the conclusion).\n\n- A small summary of the contributions could be nice.", "was_revised": true, "final_justification": "I think the paper is rigorous, the contributions are interesting and the authors mention potential improvement to the results, hence my final grade.", "rebuttal": "Thank you for your review and positive evaluation. We are also grateful for your insightful comments, leading our research to the next level. We address your comments one by one in the following.\n\n---\n\n**Weakness 1)** Theoretical applications:\n\nAlthough we do not provide a formal proof, our study suggests a potential theoretical application. This study, for the first time, demonstrates the merit of taking the extra ($n$ times) prediction in the aspects of regret and convergence. It provides an idea that increasing the optimistic weight $n$ (with decreasing learning rate $\\eta$) may enhance the accuracy of future predictions. This idea could be valuable not only in delayed settings but also in delay-free ones.\n\n---\n\n**Weakness 2)** Small summary of the contributions:\n\nWe will shorten Lines 46-59 as well as possible.\n\n---\n\n**Question 1)** Extension to last-iterate convergence:\n\nFortunately, **by further research, we could improve best-iterate convergence to last-iterate convergence**. It was very challenging to find a Lyapunov function. Indeed, the naive idea that the distance from the Nash equilibrium can be a Lyapunov function fails. As shown in Fig.3, due to delayed feedback, the distance from the Nash equilibrium may increase initially. Our manuscript will be updated to last-iterate convergence in the camera-ready phase.\n\n---\n\n**Question 2)** Extension to stochastic setting:\n\nSeveral papers have recently been published on such stochastic (e.g., bandit) feedback in learning in games ([a1, a2]), but it seems very difficult to obtain the regret lower bound even if no feedback delay exists. Because bandit feedback requires a different kind of discussion from our full feedback, we leave it as future work.\n\n---\n\n[a1] Ito, S., Luo, H., Tsuchiya, T., & Wu, Y. (2025). Instance-dependent regret bounds for learning two-player zero-sum games with bandit feedback. arXiv preprint arXiv:2502.17625.\n\n[a2] Fiegel, C., Menard, P., Kozuno, T., Valko, M., & Perchet, V. (2025). The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback. In ICML."}]

Author rebuttal:

Meta-review: This paper discusses “the problem of time-delayed feedback in learning in games.”  For the most part, the reviewers found the paper to address an important time-delayed feedback model that is rigorous, well-written, and easy to follow.  The results are compelling.  However, there were some concerns, in particular with the paper’s “dependence on the delay time $m$” (Reviewer wW5Q).  

In reviewing the discussion about this concern, reviewer E3gP being dissatisfied with the authors’ response (so they dropped their score from accept to borderline accept — see their final justification).  On the other hand, reviewer ebu8 was satisfied with the authors’ response, so they raised their score to 4.  Overall, the reviewers were happy with the paper.

I encourage the authors to thoroughly consider the the concern expressed by reviewer wW5Q in their revision of the paper.
Decision: Accept (poster)