Learning from Delayed Feedback in Games via Extra Prediction

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.

Weakness 1) Theoretical applications:

Although 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.

Weakness 2) Small summary of the contributions:

We will shorten Lines 46-59 as well as possible.

Question 1) Extension to last-iterate convergence:

Fortunately, 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.

Question 2) Extension to stochastic setting:

Several 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.

[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.

[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.

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

• “I'm willing to raise my score if my concerns and questions can be addressed”,

and we hope that you will reassess our paper.

Weakness 1) Detailed relation to previous literature:

We 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.

Weakness 2) Definition of $h_{\max}$:

We will note $h_{max} = \sum_{i}\max{x_{i}} h(x_{i})$, thank you.

Weakness 3) For the RVU property:

Its 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.

Weakness 4) For other works showing $O(1)$ regret:

As 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.

Question 1) For commonality of multi-linear utility function:

The 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.

Question 2) For multiple Nash equilibria:

This study does not assume the uniqueness of the Nash equilibrium, and thus all the results hold for games with multiple Nash equilibria.

Question 3) For other choices of $\eta$ in Thm. 6:

Sorry 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.

Thank you for your review and positive evaluation. We further appreciate your insightful questions that advance our research. The following is our answer.

Question 1) For stochastic delay $m$:

Thank 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.

Question 2) For trade-off due to significantly larger $n$ than $m+1$:

If 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.

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:

• Identifying that a finite delay $m$ significantly degrades performance in terms of regret and convergence.
• Proving that an additional prediction restores the good performance.

Your 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.

Weakness 1) Distinction between individual and social regret:

We 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.

For the RVU property, we will revise it based on individual regret. This revision does not affect our contribution at all.

Weakness 2) For other choices of $\eta$ in Thm. 6

Sorry 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.

For 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.

Weakness 3) For regret dependence on $m$:

Thank 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.

Weakness 4) Terminology of optimistic/generalized FTRL:

For 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]).

Further Q1) Individual regret

[Apology for your confusion] First, we are really sorry for confusing you. We referred to the papers because we wanted to show that social regret alone is a sufficient result (indeed, some papers analyze social regret alone) and that social regret is prioritized over individual one. Anyway, our response, “prior work in learning in games typically focuses on social regret,” sounds like an overclaim. We are sorry again.

[Analysis of individual regret] Although we still do not understand why the reviewer is committed to individual regret, we sincerely respect your comments and promise to add the results for individual regret with time delays in the camera-ready phase. We will prove that even under delayed feedback, WOFTRL achieves $O(T^{1/4})$ individual regret, following the methodology of Theorem 11 and Corollary 12 in Ref. [5]. The proof will be very short, and only minor revisions will be required to the manuscript. This is because we have already obtained the RVU property as the main result of this study (but with different $\alpha, \beta, \gamma$), and a similar result to Theorem 11 will be immediately obtained. In fact, Ref. [5] devotes very few sentences to proving Theorem 11 and Corollary 12. Keeping in mind that our paper will include the results for individual regret in the next version, could you reevaluate this paper, please?

Further Q2) Step size of $\eta$

[Difference choice of $\eta$] The different choice of $\eta$ between Thm. 6 and Cor. 11 is no problem. In Thm. 6, we set $\eta=O(1/\sqrt{T})$ in OFTRL, which suffers $\Omega(\sqrt{T})$ regret as the lower bound. In Cor. 11, we set $\eta=O(1)$ in WOFTRL, which achieves $O(1)$ regret as the upper bound. Because Thm. 6 and Cor. 11 have different algorithms and purposes, they do not have to be discussed with the same $\eta$.

[$\eta=O(1)$ in Thm. 6] We can consider the step size of $\eta=O(1)$ in Thm. 6 according to Cor. 11. Then, social regret becomes ${\rm RegTot}=\Omega(\exp(\frac{1}{2}\alpha T))$, unfortunately exceeding $\Omega(\sqrt{T})$ which is obtained by $\eta=O(1/\sqrt{T})$. Thus, the lower bound $\Omega(\sqrt{T})$ by $\eta=O(1/\sqrt{T})$ should be exhibited in our Theorem 6.

Further Q3) For constrained setting

[Difficulty in analyzing constrained setting] In the proof, we have shown that the learning dynamics cycle around the Nash equilibrium with the radius expanding exponentially (Lemma A1). Such divergent dynamics are also observed in FTRL, leading to $O(\sqrt{T})$ regret. In the constrained setting, the divergent dynamics reach the boundary of the strategy space and continue to cycle on the boundary. It is difficult to analyze the regret lower bound in the specific dynamics on such boundaries.

[Justification for similarity between constraint and unconstraint] As explained in the above, the divergent dynamics (seen in FTRL) contribute to $\Omega(\sqrt{T})$-regret. The timing when the dynamics reach the boundary in the constrained setting is after they have deviated sufficiently away from the Nash equilibrium. Thus, the divergent dynamics themselves are similar between the constrained and unconstrained settings. Hence, we conclude that the $\Omega(\sqrt{T})$ is expected to be obtained also in the constrained setting.

Conclusion)

Again, we really appreciate your valuable time and reply. At least, the unconstrained setting is only related to our negative results (Thms. 6 and 7) and irrelevant to our positive contributions (Thm. 10 and Cors. 11 and 13). In addition, analyzing individual regret often provides only a small step forward from social regret (indeed, we could easily add the results for individual regret). Instead of individual regret, we continue to believe that we should highlight the convergence to the equilibrium, which usually requires a different kind of discussion. We would like you to reconsider how serious the technical flaws you raised are in this work.

Thank you to the authors for their response. I understood the clarification regarding Theorem 6.

WOFTRL achieves  $O(T^{1/4})$ individual regret, following the methodology of Theorem 11 and Corollary 12 in Ref. [5].

I feel that an individual regret bound of $O(T^{1/4})$ is quite far from optimal. For example, Farina et al. (2022) show that in the non-delayed setting, the individual external regret can be bounded by $O(\mathrm{poly} \log T)$. It seems like a significant compromise to allow the individual regret to be as large as $O(T^{1/4})$ just because the setting involves delays.

[Farina et al. 2022] Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games, ICML 2022

Furthermore, regarding the dependency on the delay time $m$, which is the most important parameter in this paper, I believe that the $O(m^2)$ dependency is far from optimal, as mentioned in the review.It is quite undesirable that the main results of the paper, specifically Theorem 10 and Corollary 11, exhibit such a suboptimal dependency.If the dependence on such a crucial parameter appears to be highly sub-optimal, then in order to meet the NeurIPS bar, it may be desirable that the paper either establish a matching lower bound for that dependency, or present other compelling extensions such as a generalization to the variable delay setting.

As a minor point, since the delay time $m$ is the most important parameter in this work, the bound in Corollary 11 should be written as $O(m^2)$ rather than simply $O(1)$.

I have no further questions, but I will update my score after discussing with the other reviewers if needed.

We are grateful that your questions were resolved through our discussion. We kindly hope you will reflect this in your next assessment.

This study has yielded several surprising results, independent of the quantitative analysis related to the tight bound. Indeed, we found, for the first time, that OFTRL does not perform well under delayed full feedback. Since OFTRL is one of the most well-known and widely applied algorithms, it is surprising that even a minimal delay of $m = 1$ qualitatively degrades its performance---bringing it down to a level comparable to FTRL. Furthermore, our proposed algorithm, WOFTRL, successfully restores the strong performance in terms of regret and convergence that OFTRL originally possessed. We believe that this qualitatively novel problem and solution meet the NeurIPS standards.

We understand that you believe our regret bounds are far from optimal when compared to previous studies conducted under the non-delayed setting. First, we emphasize that the $O(m^{2})$ social regret is not excessively loose because the accumulated error due to delayed rewards is on the order of $m \times m$, as mentioned earlier. Second, note that results from the non-delayed setting do not necessarily carry over to the delayed feedback setting, as you also acknowledged in your previous reply. A fact is that for delayed feedback, $O(m^{2})$ social regret and $O(T^{1/4})$ individual regret by WOFTRL are the best in the current world.

Anyway, we greatly appreciate your comments and the fruitful discussion. Thanks to your feedback, we could extend our results to include individual regret, which we feel is meaningful to some extent.