mlsanityData to 7 Oct 2026

Distributed Optimization via Kernelized Multi-armed Bandits

arXiv 2312.04719 ↗First posted 7 Dec 2023cs.LG cs.MA math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

Multi-armed bandit algorithms provide solutions for sequential decision-making where learning takes place by interacting with the environment. In this work, we model a distributed optimization problem as a multi-agent kernelized multi-armed bandit problem with a heterogeneous reward setting. In this setup, the agents collaboratively aim to maximize a global objective function which is an average of local objective functions. The agents can access only bandit feedback (noisy reward) obtained from the associated unknown local function with a small norm in reproducing kernel Hilbert space (RKHS). We present a fully decentralized algorithm, Multi-agent IGP-UCB (MA-IGP-UCB), which achieves a sub-linear regret bound for popular classes for kernels while preserving privacy. It does not necessitate the agents to share their actions, rewards, or estimates of their local function. In the proposed approach, the agents sample their individual local functions in a way that benefits the whole network by utilizing a running consensus to estimate the upper confidence bound on the global function. Furthermore, we propose an extension, Multi-agent Delayed IGP-UCB (MAD-IGP-UCB) algorithm, which reduces the dependence of the regret bound on the number of agents in the network. It provides improved performance by utilizing a delay in the estimation update step at the cost of more communication.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 38 of its 72 references that are in the map. First posted on arXiv 7 Dec 2023.

Builds on

38 of 72 references.

References · 38

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2017On Kernelized Multi-armed Banditscited by 348
  3. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 188
  4. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  5. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  6. 2015Distributed Gaussian Processescited by 84
  7. 2020Differentially-Private Federated Linear Banditscited by 83
  8. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 81
  9. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
  10. 2020Federated Bayesian Optimization via Thompson Samplingcited by 77
  11. 2021Federated Multi-armed Bandits with Personalizationcited by 62
  12. 2021Federated Linear Contextual Banditscited by 61
26 more
  1. 2021Federated Multi-Armed Banditscited by 59
  2. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  3. 2016Time-Varying Gaussian Process Bandit Optimizationcited by 50
  4. 2016Distributed Clustering of Linear Bandits in Peer to Peer Networkscited by 50
  5. 2016Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithmscited by 48
  6. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  7. 2014Scalable Kernel Methods via Doubly Stochastic Gradientscited by 36
  8. 2015On Distributed Cooperative Decision-Making in Multiarmed Banditscited by 33
  9. 2020Cooperative Multi-Agent Bandits with Heavy Tailscited by 31
  10. 2019A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Playerscited by 25
  11. 2020Kernel Methods for Cooperative Multi-Agent Contextual Banditscited by 21
  12. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  13. 2022Near-Optimal Collaborative Learning in Banditscited by 18
  14. 2022Communication Efficient Distributed Learning for Kernelized Contextual Banditscited by 15
  15. 2015Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimizationcited by 13
  16. 2021Collaborative Pure Exploration in Kernel Banditcited by 13
  17. 2016Linear convergence in optimization over directed graphs with row-stochastic matricescited by 12
  18. 2014Distributed convex optimization via continuous-time coordination algorithms with discrete-time communicationcited by 11
  19. 2016The proximal augmented Lagrangian method for nonsmooth composite optimizationcited by 11
  20. 2015Non-Convex Distributed Optimizationcited by 9
  21. 2022Collaborative Learning in Kernel-based Bandits for Distributed Userscited by 6
  22. 2014An Asynchronous Distributed Proximal Gradient Method for Composite Convex Optimizationcited by 4
  23. 2022Collaborative Multi-agent Stochastic Linear Banditscited by 4
  24. 2015A Distributed Algorithm for Solving a Linear Algebraic Equationcited by 3
  25. 2016Towards Geo-Distributed Machine Learningcited by 2
  26. 2014Dynamic Average Consensus under Limited Control Authority and Privacy Requirementscited by 1

Built on by

Not cited yet.