mlsanityData to 7 Oct 2026

Distributed Linear Bandits under Communication Constraints

arXiv 2211.02212 ↗First posted 4 Nov 2022cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

We consider distributed linear bandits where M agents learn collaboratively to minimize the overall cumulative regret incurred by all agents. Information exchange is facilitated by a central server, and both the uplink and downlink communications are carried over channels with fixed capacity, which limits the amount of information that can be transmitted in each use of the channels. We investigate the regret-communication trade-off by (i) establishing information-theoretic lower bounds on the required communications (in terms of bits) for achieving a sublinear regret order; (ii) developing an efficient algorithm that achieves the minimum sublinear regret order offered by centralized learning using the minimum order of communications dictated by the information-theoretic lower bounds. For sparse linear bandits, we show a variant of the proposed algorithm offers better regret-communication trade-off by leveraging the sparsity of the problem.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 33 of its 67 references that are in the map. First posted on arXiv 4 Nov 2022.

Builds on

33 of 67 references.

References · 33

  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. 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 349
  4. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 159
  5. 2016Distributed Mean Estimation with Limited Communicationcited by 134
  6. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 105
  7. 2021Federated Multi-armed Bandits with Personalizationcited by 62
  8. 2020High-Dimensional Sparse Linear Banditscited by 61
  9. 2021Federated Linear Contextual Banditscited by 61
  10. 2021Adaptive Quantization of Model Updates for Communication-Efficient Federated Learningcited by 60
  11. 2020Federated Bandit: A Gossiping Approachcited by 55
  12. 2020Impact of Representation Learning in Linear Banditscited by 51
21 more
  1. 2016Distributed Clustering of Linear Bandits in Peer to Peer Networkscited by 50
  2. 2019Social Learning in Multi Agent Multi Armed Banditscited by 48
  3. 2013Distributed Exploration in Multi-Armed Banditscited by 46
  4. 2019Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Banditscited by 40
  5. 2021DAdaQuant: Doubly-adaptive quantization for communication-efficient Federated Learningcited by 40
  6. 2020The Gossiping Insert-Eliminate Algorithm for Multi-Agent Banditscited by 37
  7. 2015On Distributed Cooperative Decision-Making in Multiarmed Banditscited by 33
  8. 2019Communication-Efficient Distributed Learning via Lazily Aggregated Quantized Gradientscited by 32
  9. 2021Multi-Agent Multi-Armed Bandits with Limited Communicationcited by 29
  10. 2020Communication-Efficient Distributed Deep Learning: A Comprehensive Surveycited by 25
  11. 2022Towards Efficient Communications in Federated Learning: A Contemporary Surveycited by 24
  12. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  13. 2021Solving Multi-Arm Bandit Using a Few Bits of Communicationcited by 16
  14. 2022Distributed Contextual Linear Bandits with Minimax Optimal Communication Costcited by 13
  15. 2018Game of Thrones: Fully Distributed Learning for Multi-Player Banditscited by 12
  16. 2020Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selectioncited by 12
  17. 2014Optimality guarantees for distributed statistical estimationcited by 9
  18. 2022Linear Stochastic Bandits over a Bit-Constrained Channelcited by 9
  19. 2020Multi-Agent Low-Dimensional Linear Banditscited by 8
  20. 2022The Role of Interactivity in Structured Estimationcited by 7
  21. 2021Adaptive Clustering and Personalization in Multi-Agent Stochastic Linear Banditscited by 4

Built on by

Cited by year (2026 to 7 Oct)

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

8 papers.

  1. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  2. 2023A Communication-Efficient Adaptive Algorithm for Federated Learning under Cumulative Regretcited by 7
  3. 2023Federated Linear Bandits with Finite Adversarial Actionscited by 3
  4. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1
  5. 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1
  6. 2026Batched Stochastic Linear Bandits with 1-Bit Communication Constraintscited by 1
  7. 2024Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomnesscited by 0
  8. 2026Remote Action Generation: Remote Control with Minimal Communicationcited by 0