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 · University of Iowa
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.