Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents
Abstract
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(√(T+dtot)) individual regret against arbitrary opponents, where dtot 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.
Related
- Brenier Meets Adversarial Training: Optimal Transport Geometry for Robust Learning
- Detection of spiking motifs of arbitrary length in neural activity using bounded synaptic delays
- Optimal Adversarial Testing: Extracting Honest Test Results from Dishonest Test Takers
- Statistical Inference for Adversarial Training: Central Limit Theorems via Optimal Transport
- Robust dimension-free estimation of simple random tensors: optimal guarantees under heavy tails and adversarial contamination
BibTeX
@misc{esposito2026optimal,
title = {{Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents}},
author = {Emmanuel Esposito and Andrew Jacobsen and Hao Qiu and Alexander Ryabchenko and Mengxiao Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07773},
eprint = {2611.07773},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07773},
}
RIS
TY - UNPB
TI - Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents
AU - Emmanuel Esposito
AU - Andrew Jacobsen
AU - Hao Qiu
AU - Alexander Ryabchenko
AU - Mengxiao Zhang
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07773
UR - https://arxiv.org/abs/2611.07773
AB - 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(√(T+d_tot)) individual regret against arbitrary opponents, where d_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.
ER -