mlsanityData to 7 Oct 2026

Multi-Agent Multi-Armed Bandits with Limited Communication

arXiv 2102.08462 ↗First posted 10 Feb 2021cs.LG cs.AI cs.MAcited by 29

Not on the map. Why?

Abstract (arXiv)

We consider the problem where N agents collaboratively interact with an instance of a stochastic K arm bandit problem for K gg N. The agents aim to simultaneously minimize the cumulative regret over all the agents for a total of T time steps, the number of communication rounds, and the number of bits in each communication round. We present Limited Communication Collaboration - Upper Confidence Bound (LCC-UCB), a doubling-epoch based algorithm where each agent communicates only after the end of the epoch and shares the index of the best arm it knows. With our algorithm, LCC-UCB, each agent enjoys a regret of tildeOleft(√(K/N+ N)Tright), communicates for O(log T) steps and broadcasts O(log K) bits in each communication step. We extend the work to sparse graphs with maximum degree KG, and diameter D and propose LCC-UCB-GRAPH which enjoys a regret bound of tildeOleft(D√(K/N+ KG)DTright). Finally, we empirically show that the LCC-UCB and the LCC-UCB-GRAPH algorithm perform well and outperform strategies that communicate through a central node

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). Builds on 8 of its 30 references that are in the map. First posted on arXiv 10 Feb 2021.

Builds on

8 of 30 references.

References · 8

  1. 2020Differentially-Private Federated Linear Banditscited by 83
  2. 2020Impact of Representation Learning in Linear Banditscited by 51
  3. 2016Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithmscited by 48
  4. 2019Social Learning in Multi Agent Multi Armed Banditscited by 48
  5. 2013Distributed Exploration in Multi-Armed Banditscited by 46
  6. 2020The Gossiping Insert-Eliminate Algorithm for Multi-Agent Banditscited by 37
  7. 2018TopRank: A practical algorithm for online stochastic rankingcited by 30
  8. 2019Stochastic Linear Bandits with Hidden Low Rank Structurecited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 7; 2023: 5; 2024: 5; 2025: 2; 2026: 6.

29 papers.

Sort:

  1. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  2. 2021Pervasive AI for IoT applications: A Survey on Resource-efficient Distributed Artificial Intelligencecited by 18
  3. 2021Privacy-Preserving Communication-Efficient Federated Multi-Armed Banditscited by 11
  4. 2023Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewardscited by 11
  5. 2024Federated Combinatorial Multi-Agent Multi-Armed Banditscited by 11
  6. 2022Linear Stochastic Bandits over a Bit-Constrained Channelcited by 9
  7. 2022Differentially Private Linear Bandits with Partial Distributed Feedbackcited by 8
  8. 2022Distributed Linear Bandits under Communication Constraintscited by 8
  9. 2023On-Demand Communication for Asynchronous Multi-Agent Banditscited by 6
  10. 2022Rate-Constrained Remote Contextual Banditscited by 5
  11. 2022Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Boundscited by 4
  12. 2022Remote Contextual Banditscited by 3
17 more
  1. 2021Asymptotic Optimality for Decentralised Banditscited by 2
  2. 2023Multi-Agent Bandit Learning through Heterogeneous Action Erasure Channelscited by 2
  3. 2023Regret Lower Bounds in Multi-agent Multi-armed Banditcited by 1
  4. 2023Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphscited by 1
  5. 2024Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysiscited by 1
  6. 2024Decentralized Blockchain-based Robust Multi-agent Multi-armed Banditcited by 1
  7. 2024Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Boundscited by 1
  8. 2026Communication-Corruption Coupling and Verification in Cooperative Multi-Objective Banditscited by 1
  9. 2022Modelling Cournot Games as Multi-agent Multi-armed Banditscited by 0
  10. 2024Distributed No-Regret Learning for Multi-Stage Systems with End-to-End Bandit Feedbackcited by 0
  11. 2025Learning with Limited Shared Information in Multi-agent Multi-armed Banditcited by 0
  12. 2025Distributed Multi-Agent Bandits Over ErdHos-R'enyi Random Networkscited by 0
  13. 2026Logic-Driven Semantic Communication for Resilient Multi-Agent Systemscited by 0
  14. 2026Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedbackcited by 0
  15. 2026Bandit Learning in General Open Multi-agent Systemscited by 0
  16. 2026Cost of Structural Learning Under Censored Feedback: A Threshold-Bandit Approachcited by 0
  17. 2026The Price of Decentralization in Top-K Arm Identificationcited by 0