mlsanityData to 7 Oct 2026

Federated Multi-Armed Bandits Under Byzantine Attacks

arXiv 2205.04134 ↗First posted 9 May 2022cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

Multi-armed bandits (MAB) is a sequential decision-making model in which the learner controls the trade-off between exploration and exploitation to maximize its cumulative reward. Federated multi-armed bandits (FMAB) is an emerging framework where a cohort of learners with heterogeneous local models play an MAB game and communicate their aggregated feedback to a server to learn a globally optimal arm. Two key hurdles in FMAB are communication-efficient learning and resilience to adversarial attacks. To address these issues, we study the FMAB problem in the presence of Byzantine clients who can send false model updates threatening the learning process. We analyze the sample complexity and the regret of β-optimal arm identification. We borrow tools from robust statistics and propose a median-of-means (MoM)-based online algorithm, Fed-MoM-UCB, to cope with Byzantine clients. In particular, we show that if the Byzantine clients constitute less than half of the cohort, the cumulative regret with respect to β-optimal arms is bounded over time with high probability, showcasing both communication efficiency and Byzantine resilience. We analyze the interplay between the algorithm parameters, a discernibility margin, regret, communication cost, and the arms' suboptimality gaps. We demonstrate Fed-MoM-UCB's effectiveness against the baselines in the presence of Byzantine attacks via experiments.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 45 of its 113 references that are in the map. First posted on arXiv 9 May 2022.

Builds on

45 of 113 references.

References · 45

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2013Intriguing properties of neural networkscited by 5,114
  3. 2019Advances and Open Problems in Federated Learningcited by 3,021
  4. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
  5. 2019Towards Federated Learning at Scale: System Designcited by 826
  6. 2018How To Backdoor Federated Learningcited by 745
  7. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 698
  8. 2019Local Model Poisoning Attacks to Byzantine-Robust Federated Learningcited by 479
  9. 2018Analyzing Federated Learning through an Adversarial Lenscited by 346
  10. 2018The Hidden Vulnerability of Distributed Learning in Byzantiumcited by 324
  11. 2019Robust Aggregation for Federated Learningcited by 314
  12. 2019Federated Learning over Wireless Fading Channelscited by 178
33 more
  1. 2020Privacy and Robustness in Federated Learning: Attacks and Defensescited by 163
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  3. 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 113
  4. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  5. 2020Differentially-Private Federated Linear Banditscited by 83
  6. 2019Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attackscited by 79
  7. 2015Cascading Bandits: Learning to Rank in the Cascade Modelcited by 75
  8. 2020Over-the-Air Federated Learning from Heterogeneous Datacited by 72
  9. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  10. 2021Federated Multi-armed Bandits with Personalizationcited by 62
  11. 2021Federated Linear Contextual Banditscited by 61
  12. 2021Federated Multi-Armed Banditscited by 59
  13. 2018Adversarial Attacks on Stochastic Banditscited by 56
  14. 2020Federated Bandit: A Gossiping Approachcited by 55
  15. 2019Data Poisoning Attacks on Stochastic Banditscited by 52
  16. 2020Adversarial Attacks on Linear Contextual Banditscited by 34
  17. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
  18. 2015On Distributed Cooperative Decision-Making in Multiarmed Banditscited by 33
  19. 2018Best Arm Identification for Contaminated Banditscited by 23
  20. 2016Risk-Averse Multi-Armed Bandit Problems under Mean-Variance Measurecited by 20
  21. 2020Robust Multi-Agent Multi-Armed Banditscited by 20
  22. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  23. 2022Shielding Federated Learning: Robust Aggregation with Adaptive Client Selectioncited by 18
  24. 2020Learning for Dose Allocation in Adaptive Clinical Trials with Safety Constraintscited by 13
  25. 2021Privacy-Preserving Communication-Efficient Federated Multi-Armed Banditscited by 11
  26. 2018The Internet of Things: Secure Distributed Inferencecited by 9
  27. 2021Federated Learning over Noisy Channels: Convergence Analysis and Design Examplescited by 8
  28. 2022Byzantine-Robust Federated Linear Banditscited by 7
  29. 2021Mean-based Best Arm Identification in Stochastic Bandits under Reward Contaminationcited by 6
  30. 2017Context-Aware Hierarchical Online Learning for Performance Maximization in Mobile Crowdsourcingcited by 5
  31. 2020Faster Activity and Data Detection in Massive Random Access: A Multi-armed Bandit Approachcited by 3
  32. 2018Resilient Distributed Parameter Estimation with Heterogeneous Datacited by 2
  33. 2020Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholdingcited by 2

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 4; 2024: 0; 2025: 1.

6 papers.

  1. 2022Federated Neural Banditscited by 17
  2. 2023Byzantine-Robust Distributed Online Learning: Taming Adversarial Participants in An Adversarial Environmentcited by 8
  3. 2023Adversarial Attacks on Adversarial Banditscited by 6
  4. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1
  5. 2023Reward Teaching for Federated Multi-armed Banditscited by 0
  6. 2025Near Optimal Best Arm Identification for Clustered Banditscited by 0