Conference proceeding
Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach
Proceedings of 39th Conference on Learning Theory, Vol.336
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 [formula omitted] where T is the horizon, K is the number of actions, and ρ 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 [formula omitted] of Yi et al. We complement this result with a matching lower bound, showing that the problem’s difficulty decomposes into a communication cost [formula omitted] and a bandit cost [formula omitted]. 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 Rd, obtaining a regret bound of [formula omitted], achieved with only [formula omitted] communication cost per agent and per round via a volumetric spanner.
Details
- Title: Subtitle
- Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach
- Creators
- Hao Qiu - University of MilanMengxiao Zhang - University of IowaNicolò Cesa-Bianchi - University of Milan
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of 39th Conference on Learning Theory, Vol.336
- ISSN
- 2640-3498
- eISSN
- 2640-3498
- Language
- English
- Date published
- 2026
- Academic Unit
- Business Analytics
- Record Identifier
- 9985214919102771
Metrics
1 Record Views