A Best-of-Both-Worlds Algorithm for Bandits with Delayed Graph Feedback

We study best-of-both-worlds (BoBW) online learning with delayed graph feedback, where an action reveals the losses of related actions only after a delay. Existing BoBW algorithms handle either feedback graphs or delays, but not both. We present the first BoBW algorithm for this setting. It requires no knowledge of the horizon, the suboptimality gaps, the delays, or the independence number. For undirected graphs, its regret is $O(\sqrt{\alpha T\log (eKT)}+{\Psi }_T+1)$ against an oblivious adversary and $O(H_G(\Delta )\log (eKT)\log (eT)+{\Delta }_{\max }{\sigma }_{\max }+1)$ in the stochastic regime, where $\alpha$ is the independence number, ${\Psi }_T\le \sqrt{D\log K}$ is a delay term in which excessively delayed rounds may be skipped, $D$ is the total delay, $H_G(\Delta )$ is the largest sum of inverse gaps over independent sets of suboptimal arms, and ${\sigma }_{\max }$ is the maximum number of rounds whose feedback is pending at the same time. The delay thus enters only additively, and in the stochastic regime its coefficient is a gap rather than an inverse gap. Under bandit and full-information feedback this coefficient improves to the average gap ${\Delta }_{\mathrm{avg}}$.