![[2602.17486] Linear Convergence in Games with Delayed Feedback via Extra Prediction](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.17486] Linear Convergence in Games with Delayed Feedback via Extra Prediction
Summary
This paper explores the linear convergence of the Weighted Optimistic Gradient Descent-Ascent algorithm in multi-agent games with delayed feedback, demonstrating that extra optimism can significantly enhance performance.
Why It Matters
Understanding convergence rates in multi-agent systems with delayed feedback is crucial for improving algorithms in real-world applications. This research offers a new perspective on optimizing learning processes, which can lead to more efficient and effective AI systems.
Key Takeaways
- The paper derives the linear convergence rate for WOGDA in bilinear games.
- Extra optimism in predictions can significantly accelerate convergence rates.
- Standard optimism predicts next-step rewards, while extra optimism predicts farther future rewards.
- The findings provide a promising approach to mitigate performance degradation due to feedback delays.
- Experiments validate theoretical results, showing practical implications for multi-agent learning.
Computer Science > Machine Learning arXiv:2602.17486 (cs) [Submitted on 19 Feb 2026] Title:Linear Convergence in Games with Delayed Feedback via Extra Prediction Authors:Yuma Fujimoto, Kenshi Abe, Kaito Ariu View a PDF of the paper titled Linear Convergence in Games with Delayed Feedback via Extra Prediction, by Yuma Fujimoto and 2 other authors View PDF HTML (experimental) Abstract:Feedback delays are inevitable in real-world multi-agent learning. They are known to severely degrade performance, and the convergence rate under delayed feedback is still unclear, even for bilinear games. This paper derives the rate of linear convergence of Weighted Optimistic Gradient Descent-Ascent (WOGDA), which predicts future rewards with extra optimism, in unconstrained bilinear games. To analyze the algorithm, we interpret it as an approximation of the Extra Proximal Point (EPP), which is updated based on farther future rewards than the classical Proximal Point (PP). Our theorems show that standard optimism (predicting the next-step reward) achieves linear convergence to the equilibrium at a rate $\exp(-\Theta(t/m^{5}))$ after $t$ iterations for delay $m$. Moreover, employing extra optimism (predicting farther future reward) tolerates a larger step size and significantly accelerates the rate to $\exp(-\Theta(t/(m^{2}\log m)))$. Our experiments also show accelerated convergence driven by the extra optimism and are qualitatively consistent with our theorems. In summary, this paper validat...
