Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach

We study distributed adversarial bandits, where $N$ agents cooperate to minimize the global average loss while observing only their own local losses. We show that the minimax regret for this problem is $\widetilde{\Theta}\Big(\sqrt{\left(\rho^{-1/2} + \frac{K}{N}\right)T}\Big)$, where $T$ is the horizon, $K$ is the number of actions, and $\rho$ is the spectral gap of the communication matrix. Our algorithm, based on a novel black-box reduction to bandits with delayed feedback, requires agents to communicate only through gossip. It achieves an upper bound that significantly improves over the previous best bound $\widetilde{\mathcal{O}}\left(\rho^{-1/3}(KT)^{2/3}\right)$ of Yi et al. We complement this result with a matching lower bound, showing that the problem’s difficulty decomposes into a communication cost $\rho^{-1/4}\sqrt{T}$ and a bandit cost $\sqrt{KT/N}$. We further demonstrate the versatility of our approach by deriving first-order and best-of-both-worlds bounds in the distributed adversarial setting. Finally, we extend our framework to distributed linear bandits in $\mathbb{R}^d$, obtaining a regret bound of $\widetilde{\mathcal{O}}\Big(\sqrt{\left(\rho^{-1/2} + \frac{1}{N}\right)dT}\Big)$, achieved with only $O(d)$ communication cost per agent and per round via a volumetric spanner.