# Doubly Adversarial Federated Bandits

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 34 references that are in the map.
- First posted on arXiv 22 Jan 2023.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [Cooperative Online Learning: Keeping your Neighbors Updated](https://mlsanity.com/paper/1901.08082/) (2019)
- [Efficient-FedRec: Efficient Federated Learning Framework for Privacy-Preserving News Recommendation](https://mlsanity.com/paper/2109.05446/) (2021)
- [Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits](https://mlsanity.com/paper/1907.03346/) (2019)
- [A Contextual-bandit-based Approach for Informed Decision-making in Clinical Trials](https://mlsanity.com/paper/1809.00258/) (2018)
- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits](https://mlsanity.com/paper/2211.17154/) (2022)

## Built on by (most cited first, 7 of 7)

- [Regret Lower Bounds in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2308.08046/) (2023)
- [Multitask Online Learning: Listen to the Neighborhood Buzz](https://mlsanity.com/paper/2310.17385/) (2023)
- [Harnessing the Power of Federated Learning in Federated Contextual Bandits](https://mlsanity.com/paper/2312.16341/) (2023)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Regret-Minimization Algorithms for Multi-Agent Cooperative Learning Systems](https://mlsanity.com/paper/2310.19468/) (2023)
- [Distributed Multi-Agent Bandits Over ErdHos-R'enyi Random Networks](https://mlsanity.com/paper/2510.22811/) (2025)
- [Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach](https://mlsanity.com/paper/2602.06404/) (2026)

## Abstract (arXiv)

We study a new non-stochastic federated multi-armed bandit problem with multiple agents collaborating via a communication network. The losses of the arms are assigned by an oblivious adversary that specifies the loss of each arm not only for each time step but also for each agent, which we call ``doubly adversarial". In this setting, different agents may choose the same arm in the same time step but observe different feedback. The goal of each agent is to find a globally best arm in hindsight that has the lowest cumulative loss averaged over all agents, which necessities the communication among agents. We provide regret lower bounds for any federated bandit algorithm under different settings, when agents have access to full-information feedback, or the bandit feedback. For the bandit feedback setting, we propose a near-optimal federated bandit algorithm called FEDEXP3. Our algorithm gives a positive answer to an open question proposed in Cesa-Bianchi et al. (2016): FEDEXP3 can guarantee a sub-linear regret without exchanging sequences of selected arm identities or loss sequences among agents. We also provide numerical evaluations of our algorithm to validate our theoretical results and demonstrate its effectiveness on synthetic and real-world datasets