# A Gang of Bandits

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2013.

## Built on by (most cited first, 30 of 49)

- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits](https://mlsanity.com/paper/2110.01463/) (2021)
- [A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits](https://mlsanity.com/paper/2207.03106/) (2022)
- [Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models](https://mlsanity.com/paper/2108.06422/) (2021)
- [Graph Neural Bandits](https://mlsanity.com/paper/2308.10808/) (2023)
- [Learning Neural Contextual Bandits Through Perturbed Rewards](https://mlsanity.com/paper/2201.09910/) (2022)
- [Communication Efficient Federated Learning for Generalized Linear Bandits](https://mlsanity.com/paper/2202.01087/) (2022)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Private and Byzantine-Proof Cooperative Decision-Making](https://mlsanity.com/paper/2205.14174/) (2022)
- [HyperBandit: Contextual Bandit with Hypernewtork for Time-Varying User Preferences in Streaming Recommendation](https://mlsanity.com/paper/2308.08497/) (2023)
- [Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity](https://mlsanity.com/paper/2306.06291/) (2023)
- [Multitask Online Mirror Descent](https://mlsanity.com/paper/2106.02393/) (2021)
- [Spectral bandits for smooth graph functions with applications in recommender systems](https://mlsanity.com/paper/2605.20552/) (2026)
- [Dynamic Global Sensitivity for Differentially Private Contextual Bandits](https://mlsanity.com/paper/2208.14555/) (2022)
- [RoME: A Robust Mixed-Effects Bandit Algorithm for Optimizing Mobile Health Interventions](https://mlsanity.com/paper/2312.06403/) (2023)
- [Adaptive Clustering and Personalization in Multi-Agent Stochastic Linear Bandits](https://mlsanity.com/paper/2106.08902/) (2021)
- [Semi-Parametric Contextual Bandits with Graph-Laplacian Regularization](https://mlsanity.com/paper/2205.08295/) (2022)
- [Multitask Learning with No Regret: from Improved Confidence Bounds to Active Learning](https://mlsanity.com/paper/2308.01744/) (2023)
- [Federated Linear Contextual Bandits with Heterogeneous Clients](https://mlsanity.com/paper/2403.00116/) (2024)
- [Generalized Low-Rank Matrix Contextual Bandits with Graph Information](https://mlsanity.com/paper/2507.17528/) (2025)
- [Thompson Sampling for Robust Transfer in Multi-Task Bandits](https://mlsanity.com/paper/2206.08556/) (2022)
- [Incentivized Communication for Federated Bandits](https://mlsanity.com/paper/2309.11702/) (2023)
- [Federated Linear Bandits with Finite Adversarial Actions](https://mlsanity.com/paper/2311.00973/) (2023)
- [Bandits with Abstention under Expert Advice](https://mlsanity.com/paper/2402.14585/) (2024)
- [Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts](https://mlsanity.com/paper/2501.00891/) (2025)
- [Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2306.05998/) (2023)
- [Leveraging heterogeneous spillover in maximizing contextual bandit rewards](https://mlsanity.com/paper/2310.10259/) (2023)
- [Revealing graph bandits for maximizing local influence](https://mlsanity.com/paper/2605.00489/) (2026)
- [An α-No-Regret Algorithm For Graphical Bilinear Bandits](https://mlsanity.com/paper/2206.00466/) (2022)
- [Online Network Source Optimization with Graph-Kernel MAB](https://mlsanity.com/paper/2307.03641/) (2023)

## Abstract (arXiv)

Multi-armed bandit problems are receiving a great deal of attention because they adequately formalize the exploration-exploitation trade-offs arising in several industrially relevant applications, such as online advertisement and, more generally, recommendation systems. In many cases, however, these applications have a strong social component, whose integration in the bandit algorithm could lead to a dramatic performance increase. For instance, we may want to serve content to a group of users by taking advantage of an underlying network of social relationships among them. In this paper, we introduce novel algorithmic approaches to the solution of such networked bandit problems. More specifically, we design and analyze a global strategy which allocates a bandit algorithm to each network node (user) and allows it to "share" signals (contexts and payoffs) with the neghboring nodes. We then derive two more scalable variants of this strategy based on different ways of clustering the graph nodes. We experimentally compare the algorithm and its variants to state-of-the-art methods for contextual bandits that do not use the relational information. Our experiments, carried out on synthetic and real-world datasets, show a marked increase in prediction performance obtained by exploiting the network structure.