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

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

## Key facts

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

## Builds on (most cited first, 30 of 43)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Towards Federated Learning at Scale: System Design](https://mlsanity.com/paper/1902.01046/) (2019)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets](https://mlsanity.com/paper/1811.03761/) (2018)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Generalized Byzantine-tolerant SGD](https://mlsanity.com/paper/1802.10116/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Robust Federated Learning in a Heterogeneous Environment](https://mlsanity.com/paper/1906.06629/) (2019)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Byzantine Stochastic Gradient Descent](https://mlsanity.com/paper/1803.08917/) (2018)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [Data Poisoning Attacks on Stochastic Bandits](https://mlsanity.com/paper/1905.06494/) (2019)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [High-Dimensional Robust Mean Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1811.09380/) (2018)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [Adversarial Attacks on Linear Contextual Bandits](https://mlsanity.com/paper/2002.03839/) (2020)
- [Corruption-Tolerant Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2003.01971/) (2020)
- [Collaborative Learning of Stochastic Bandits over a Social Network](https://mlsanity.com/paper/1602.08886/) (2016)

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

- [Byzantine-Robust Distributed Online Learning: Taming Adversarial Participants in An Adversarial Environment](https://mlsanity.com/paper/2307.07980/) (2023)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [Harnessing the Power of Federated Learning in Federated Contextual Bandits](https://mlsanity.com/paper/2312.16341/) (2023)
- [Robust Federated Q-Learning with Almost No Communication](https://mlsanity.com/paper/2609.20174/) (2026)
- [Learning from Unreliable Trajectories: Adversarially-Robust Federated Q-Learning](https://mlsanity.com/paper/2610.06918/) (2026)

## 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.