cs.LGNov 5, 2026

Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents

Authors: Emmanuel Esposito, Andrew Jacobsen, Hao Qiu, Alexander Ryabchenko, Mengxiao Zhang

Organizations: FairPlay Team, CREST, ENSAE, IP Paris · Universitat Pompeu Fabra · National University of Singapore · University of Toronto, Vector Institute · 

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)O(σ_{\max}+1) social and individual regrets when used by both players, where σmax⁡σ_{\max} denotes the maximum number of outstanding gradients, while also guaranteeing minimax optimal O(T+dtot)O(\sqrt{T+d_{\mathrm{tot}}}) individual regret against arbitrary opponents, where dtotd_{\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.

Explore similar work

CardsList
  1. Multiplicative Optimism for Constant Regret in Games

    Sep 18, 2026Ashkan Soleymani, Georgios PiliourasGeneral-Sum GamesRegret Minimization

  2. Linear Convergence in Games with Delayed Feedback via Extra Prediction

    Feb 19, 2026Yuma Fujimoto, Kenshi Abe, Kaito AriuGame Theory

  3. Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions

    May 10, 2026Soumita Hait, Ping Li, Haipeng Luo +1Last-Iterate ConvergenceImperfect-Information Games