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

Hao Qiu, Mengxiao Zhang, Nicolò Cesa-Bianchi
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5465-5517, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-qiu26a, title = {Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach}, author = {Qiu, Hao and Zhang, Mengxiao and Cesa-Bianchi, Nicol{\`o}}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {5465--5517}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/qiu26a/qiu26a.pdf}, url = {https://proceedings.mlr.press/v336/qiu26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach %A Hao Qiu %A Mengxiao Zhang %A Nicolò Cesa-Bianchi %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-qiu26a %I PMLR %P 5465--5517 %U https://proceedings.mlr.press/v336/qiu26a.html %V 336 %X 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.
APA
Qiu, H., Zhang, M. & Cesa-Bianchi, N.. (2026). Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:5465-5517 Available from https://proceedings.mlr.press/v336/qiu26a.html.

Related Material