mlsanityData to 7 Oct 2026

Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds

arXiv 2206.02834 ↗First posted 6 Jun 2022cs.LG cs.MA cs.SYcited by 4

Not on the map. Why?

Abstract (arXiv)

We consider a linear stochastic bandit problem involving M agents that can collaborate via a central server to minimize regret. A fraction α of these agents are adversarial and can act arbitrarily, leading to the following tension: while collaboration can potentially reduce regret, it can also disrupt the process of learning due to adversaries. In this work, we provide a fundamental understanding of this tension by designing new algorithms that balance the exploration-exploitation trade-off via carefully constructed robust confidence intervals. We also complement our algorithms with tight analyses. First, we develop a robust collaborative phased elimination algorithm that achieves tildeOleft(α+ 1/√Mright) √dT regret for each good agent; here, d is the model-dimension and T is the horizon. For small α, our result thus reveals a clear benefit of collaboration despite adversaries. Using an information-theoretic argument, we then prove a matching lower bound, thereby providing the first set of tight, near-optimal regret bounds for collaborative linear bandits with adversaries. Furthermore, by leveraging recent advances in high-dimensional robust statistics, we significantly extend our algorithmic ideas and results to (i) the generalized linear bandit model that allows for non-linear observation maps; and (ii) the contextual bandit setting that allows for time-varying feature vectors.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 43 of its 78 references that are in the map. First posted on arXiv 6 Jun 2022.

Builds on

43 of 78 references.

References · 43

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  3. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  4. 2019Towards Federated Learning at Scale: System Designcited by 826
  5. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 698
  6. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  7. 2018RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasetscited by 148
  8. 2020Learning from History for Byzantine Robust Optimizationcited by 137
  9. 2016Agnostic Estimation of Mean and Covariancecited by 131
  10. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  11. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  12. 2018Generalized Byzantine-tolerant SGDcited by 94
31 more
  1. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  2. 2019Robust Federated Learning in a Heterogeneous Environmentcited by 88
  3. 2020Differentially-Private Federated Linear Banditscited by 83
  4. 2018Byzantine Stochastic Gradient Descentcited by 81
  5. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  6. 2021Federated Multi-armed Bandits with Personalizationcited by 62
  7. 2018Adversarial Attacks on Stochastic Banditscited by 56
  8. 2020Federated Bandit: A Gossiping Approachcited by 55
  9. 2019Data Poisoning Attacks on Stochastic Banditscited by 52
  10. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  11. 2016Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithmscited by 48
  12. 2019Social Learning in Multi Agent Multi Armed Banditscited by 48
  13. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  14. 2020Distributed Cooperative Decision Making in Multi-agent Multi-armed Banditscited by 38
  15. 2020The Gossiping Insert-Eliminate Algorithm for Multi-Agent Banditscited by 37
  16. 2020Adversarial Attacks on Linear Contextual Banditscited by 34
  17. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
  18. 2016Collaborative Learning of Stochastic Bandits over a Social Networkcited by 29
  19. 2021Multi-Agent Multi-Armed Bandits with Limited Communicationcited by 29
  20. 2020Kernel Methods for Cooperative Multi-Agent Contextual Banditscited by 21
  21. 2020Distributed Newton Can Communicate Less and Resist Byzantine Workerscited by 20
  22. 2020Robust Multi-Agent Multi-Armed Banditscited by 20
  23. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  24. 2016Distributed Optimization Under Adversarial Nodescited by 19
  25. 2020Bayesian Algorithms for Decentralized Stochastic Banditscited by 11
  26. 2013Bounded regret in stochastic multi-armed banditscited by 10
  27. 2020Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptionscited by 9
  28. 2022Private and Byzantine-Proof Cooperative Decision-Makingcited by 9
  29. 2020Byzantine-Resilient Distributed Optimization of Multi-Dimensional Functionscited by 8
  30. 2020Multi-Agent Low-Dimensional Linear Banditscited by 8
  31. 2022Distributed Statistical Min-Max Learning in the Presence of Byzantine Agentscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 0; 2025: 0; 2026: 1.

4 papers.

  1. 2023Byzantine-Robust Distributed Online Learning: Taming Adversarial Participants in An Adversarial Environmentcited by 8
  2. 2023Byzantine-Resilient Decentralized Multi-Armed Banditscited by 3
  3. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1
  4. 2026Robust Federated Q-Learning with Almost No Communicationcited by 0