# The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2020.

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

- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [Multi-Agent Multi-Armed Bandits with Limited Communication](https://mlsanity.com/paper/2102.08462/) (2021)
- [Regret, stability & fairness in matching markets with bandit learners](https://mlsanity.com/paper/2102.06246/) (2021)
- [Exploiting Heterogeneity in Robust Federated Best-Arm Identification](https://mlsanity.com/paper/2109.05700/) (2021)
- [Pervasive AI for IoT applications: A Survey on Resource-efficient Distributed Artificial Intelligence](https://mlsanity.com/paper/2105.01798/) (2021)
- [One More Step Towards Reality: Cooperative Bandits with Imperfect Communication](https://mlsanity.com/paper/2111.12482/) (2021)
- [Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure](https://mlsanity.com/paper/2111.00781/) (2021)
- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [Communication Efficient Parallel Reinforcement Learning](https://mlsanity.com/paper/2102.10740/) (2021)
- [Linear Stochastic Bandits over a Bit-Constrained Channel](https://mlsanity.com/paper/2203.01198/) (2022)
- [Distributed Linear Bandits under Communication Constraints](https://mlsanity.com/paper/2211.02212/) (2022)
- [On-Demand Communication for Asynchronous Multi-Agent Bandits](https://mlsanity.com/paper/2302.07446/) (2023)
- [Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2206.02834/) (2022)
- [Cooperative Online Learning with Feedback Graphs](https://mlsanity.com/paper/2106.04982/) (2021)
- [Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms](https://mlsanity.com/paper/2201.12700/) (2022)
- [Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits](https://mlsanity.com/paper/2305.18784/) (2023)
- [Revisiting Gossip Protocols: A Vision for Emergent Coordination in Agentic Multi-Agent Systems](https://mlsanity.com/paper/2508.01531/) (2025)
- [Decentralized Upper Confidence Bound Algorithms for Homogeneous Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2111.10933/) (2021)
- [Tractable Optimality in Episodic Latent MABs](https://mlsanity.com/paper/2210.03528/) (2022)
- [Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits](https://mlsanity.com/paper/2301.11442/) (2023)
- [Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costs](https://mlsanity.com/paper/2308.04314/) (2023)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [Asymptotic Optimality for Decentralised Bandits](https://mlsanity.com/paper/2109.09427/) (2021)
- [Multi-Player Approaches for Dueling Bandits](https://mlsanity.com/paper/2405.16168/) (2024)
- [Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis](https://mlsanity.com/paper/2401.10383/) (2024)
- [Modelling Cournot Games as Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2201.01182/) (2022)
- [Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networks](https://mlsanity.com/paper/2303.05445/) (2023)
- [Cooperative Thresholded Lasso for Sparse Linear Bandit](https://mlsanity.com/paper/2305.19161/) (2023)
- [Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomness](https://mlsanity.com/paper/2402.13182/) (2024)
- [Distributed No-Regret Learning for Multi-Stage Systems with End-to-End Bandit Feedback](https://mlsanity.com/paper/2404.04509/) (2024)

## Abstract (arXiv)

We consider a decentralized multi-agent Multi Armed Bandit (MAB) setup consisting of N agents, solving the same MAB instance to minimize individual cumulative regret. In our model, agents collaborate by exchanging messages through pairwise gossip style communications on an arbitrary connected graph. We develop two novel algorithms, where each agent only plays from a subset of all the arms. Agents use the communication medium to recommend only arm-IDs (not samples), and thus update the set of arms from which they play. We establish that, if agents communicate Omega(log(T)) times through any connected pairwise gossip mechanism, then every agent's regret is a factor of order N smaller compared to the case of no collaborations. Furthermore, we show that the communication constraints only have a second order effect on the regret of our algorithm. We then analyze this second order term of the regret to derive bounds on the regret-communication tradeoffs. Finally, we empirically evaluate our algorithm and conclude that the insights are fundamental and not artifacts of our bounds. We also show a lower bound which gives that the regret scaling obtained by our algorithm cannot be improved even in the absence of any communication constraints. Our results thus demonstrate that even a minimal level of collaboration among agents greatly reduces regret for all agents.