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

arXiv: https://arxiv.org/abs/2602.06404 · HTML: https://mlsanity.com/paper/2602.06404/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 45 references that are in the map.
- First posted on arXiv 6 Feb 2026.

## Builds on (most cited first, 20 of 20)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Heterogeneous Federated Learning: State-of-the-art and Research Challenges](https://mlsanity.com/paper/2307.10616/) (2023)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [Nonstochastic Multiarmed Bandits with Unrestricted Delays](https://mlsanity.com/paper/1906.00670/) (2019)
- [Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs](https://mlsanity.com/paper/1901.08460/) (2019)
- [Adapting to Delays and Data in Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2010.06022/) (2020)
- [Volumetric Spanners: an Efficient Exploration Basis for Learning](https://mlsanity.com/paper/1312.6214/) (2013)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [A Closer Look at Small-loss Bounds for Bandits with Graph Feedback](https://mlsanity.com/paper/2002.00315/) (2020)
- [Multi-consensus Decentralized Accelerated Gradient Descent](https://mlsanity.com/paper/2005.00797/) (2020)
- [Nonstochastic Bandits and Experts with Arm-Dependent Delays](https://mlsanity.com/paper/2111.01589/) (2021)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards](https://mlsanity.com/paper/2306.05579/) (2023)
- [Doubly Adversarial Federated Bandits](https://mlsanity.com/paper/2301.09223/) (2023)
- [Tight Bounds for Volumetric Spanners and Applications](https://mlsanity.com/paper/2310.00175/) (2023)
- [Federated Linear Contextual Bandits with Heterogeneous Clients](https://mlsanity.com/paper/2403.00116/) (2024)

## Abstract (arXiv)

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 tildeTheta(√(ρ-1/2+K/N)T), 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 tildeO(ρ-1/3(KT)2/3) of Yi and Vojnovic (2023). We complement this result with a matching lower bound, showing that the problem's difficulty decomposes into a communication cost ρ-1/4√T and a bandit cost √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 Rd, obtaining a regret bound of tildeO(√(ρ-1/2+1/N)dT), achieved with only O(d) communication cost per agent and per round via a volumetric spanner.