Optimal Learning in Games under Delayed Feedback

Ruotong Zhuang, Taira Tsuchiya, Shinji Ito
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:5266-5274, 2026.

Abstract

Learning in games is a central topic in both learning theory and game theory, and learning dynamics based on online learning have made significant theoretical and practical advances in recent years. In particular, in two-player zero-sum games, it has been shown that using optimistic follow-the-regularized-leader (OFTRL) as the online learning algorithm allows us to upper bound the individual regret for each player by a constant independent of the time horizon. However, in realistic game scenarios, players are not always able to observe the outcomes of their interactions immediately. Motivated by this, very recently, the problem of learning from delayed feedback in games has been proposed, and it has been shown that by using a variant of OFTRL, one can achieve a social regret upper bound of $\tilde{O}(D^2 + 1)$ for a fixed delay time $D$. This study investigates the optimal dependence on the delay parameter $D$ in the setting of learning from delayed feedback in games. In particular, we show that a simple algorithm that runs $D+1$ independent copies of the standard OFTRL designed for the non-delayed setting achieves social and individual regret upper bounds of $\tilde{O}(D + 1)$, thereby improving the existing bounds by a factor of $D$. Moreover, we provide a matching lower bound: for any learning dynamic, there exists a payoff matrix such that the regret of every player is at least $\Omega(D + 1)$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-zhuang26a, title = { Optimal Learning in Games under Delayed Feedback }, author = {Zhuang, Ruotong and Tsuchiya, Taira and Ito, Shinji}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {5266--5274}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/zhuang26a/zhuang26a.pdf}, url = {https://proceedings.mlr.press/v300/zhuang26a.html}, abstract = { Learning in games is a central topic in both learning theory and game theory, and learning dynamics based on online learning have made significant theoretical and practical advances in recent years. In particular, in two-player zero-sum games, it has been shown that using optimistic follow-the-regularized-leader (OFTRL) as the online learning algorithm allows us to upper bound the individual regret for each player by a constant independent of the time horizon. However, in realistic game scenarios, players are not always able to observe the outcomes of their interactions immediately. Motivated by this, very recently, the problem of learning from delayed feedback in games has been proposed, and it has been shown that by using a variant of OFTRL, one can achieve a social regret upper bound of $\tilde{O}(D^2 + 1)$ for a fixed delay time $D$. This study investigates the optimal dependence on the delay parameter $D$ in the setting of learning from delayed feedback in games. In particular, we show that a simple algorithm that runs $D+1$ independent copies of the standard OFTRL designed for the non-delayed setting achieves social and individual regret upper bounds of $\tilde{O}(D + 1)$, thereby improving the existing bounds by a factor of $D$. Moreover, we provide a matching lower bound: for any learning dynamic, there exists a payoff matrix such that the regret of every player is at least $\Omega(D + 1)$. } }
Endnote
%0 Conference Paper %T Optimal Learning in Games under Delayed Feedback %A Ruotong Zhuang %A Taira Tsuchiya %A Shinji Ito %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-zhuang26a %I PMLR %P 5266--5274 %U https://proceedings.mlr.press/v300/zhuang26a.html %V 300 %X Learning in games is a central topic in both learning theory and game theory, and learning dynamics based on online learning have made significant theoretical and practical advances in recent years. In particular, in two-player zero-sum games, it has been shown that using optimistic follow-the-regularized-leader (OFTRL) as the online learning algorithm allows us to upper bound the individual regret for each player by a constant independent of the time horizon. However, in realistic game scenarios, players are not always able to observe the outcomes of their interactions immediately. Motivated by this, very recently, the problem of learning from delayed feedback in games has been proposed, and it has been shown that by using a variant of OFTRL, one can achieve a social regret upper bound of $\tilde{O}(D^2 + 1)$ for a fixed delay time $D$. This study investigates the optimal dependence on the delay parameter $D$ in the setting of learning from delayed feedback in games. In particular, we show that a simple algorithm that runs $D+1$ independent copies of the standard OFTRL designed for the non-delayed setting achieves social and individual regret upper bounds of $\tilde{O}(D + 1)$, thereby improving the existing bounds by a factor of $D$. Moreover, we provide a matching lower bound: for any learning dynamic, there exists a payoff matrix such that the regret of every player is at least $\Omega(D + 1)$.
APA
Zhuang, R., Tsuchiya, T. & Ito, S.. (2026). Optimal Learning in Games under Delayed Feedback . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:5266-5274 Available from https://proceedings.mlr.press/v300/zhuang26a.html.

Related Material