---
title: "Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.07773v1"
permalink: "https://feed.astralor.com/items/itm_93073d7c490498d34a507991"
published: "2026-11-05T10:11:38.000Z"
score: 56
channel: "ai"
tags: ["Optimal Learning","Games","Arbitrary Delays","Best-of-Both-Worlds","Self-Play","Adversarial Opponents","Multi-Anchor Optimistic Online","Mirror Descent"]
---

# 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 si…

## 关键点

- 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…
- 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…

## 全文

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.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_93073d7c490498d34a507991