← 研踪 PaperTrailarXiv:2611.07773 · v1
Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents
首次提交 2026-11-05 18:11
版本更新 2026-11-05 18:11
雷达观测 2026-11-06 11:06
摘要
We study learning in zero-sum games with delayed feedback. We introduce Multi-Anchor Optimistic Online Mirror Descent (MAO-OMD), a single algorithm which obtains optimal fast rates in self-play on smooth games, while simultaneously maintaining minimax optimal guarantees against arbitrary opponents. In particular, in smooth zero-sum games with arbitrary and unknown feedback delays, MAO-OMD obtains $O(σ_{\max}+1)$ social and individual regrets when used by both players, where $σ_{\max}$ denotes the maximum number of outstanding gradients, while also guaranteeing minimax optimal $O(\sqrt{T+d_{\mathrm{tot}}})$ individual regret against arbitrary opponents, where $d_{\mathrm{tot}}$ is the total delay. Moreover, we show that these optimal rates cannot be obtained simultaneously using the standard black-box reduction to the undelayed setting. We also extend our results to multi-player games, and to games with player-dependent delay sequences.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-05 18:11 · 最新观测版本
Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents
We study learning in zero-sum games with delayed feedback. We introduce Multi-Anchor Optimistic Online Mirror Descent (MAO-OMD), a single algorithm which obtains optimal fast rates in self-play on smooth games, while simultaneously maintaining minimax optimal guarantees against arbitrary opponents. In particular, in smooth zero-sum games with arbitrary and unknown feedback delays, MAO-OMD obtains $O(σ_{\max}+1)$ social and individual regrets when used by both players, where $σ_{\max}$ denotes the maximum number of outstanding gradients, while also guaranteeing minimax optimal $O(\sqrt{T+d_{\mathrm{tot}}})$ individual regret against arbitrary opponents, where $d_{\mathrm{tot}}$ is the total delay. Moreover, we show that these optimal rates cannot be obtained simultaneously using the standard black-box reduction to the undelayed setting. We also extend our results to multi-player games, and to games with player-dependent delay sequences.
查看此版本解读 →查看此版本原文 ↗