mlsanityData to 7 Oct 2026

Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomness

arXiv 2402.13182 ↗First posted 20 Feb 2024cs.LG cs.DC stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We consider distributed kernel bandits where N agents aim to collaboratively maximize an unknown reward function that lies in a reproducing kernel Hilbert space. Each agent sequentially queries the function to obtain noisy observations at the query points. Agents can share information through a central server, with the objective of minimizing regret that is accumulating over time T and aggregating over agents. We develop the first algorithm that achieves the optimal regret order (as defined by centralized learning) with a communication cost that is sublinear in both N and T. The key features of the proposed algorithm are the uniform exploration at the local agents and shared randomness with the central server. Working together with the sparse approximation of the GP model, these two key components make it possible to preserve the learning rate of the centralized setting at a diminishing rate of communication.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 29 of its 36 references that are in the map. First posted on arXiv 20 Feb 2024.

Builds on

29 of 36 references.

References · 29

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2017On Kernelized Multi-armed Banditscited by 348
  3. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  4. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  5. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
  6. 2020Federated Bayesian Optimization via Thompson Samplingcited by 77
  7. 2021Federated Multi-armed Bandits with Personalizationcited by 62
  8. 2021Federated Linear Contextual Banditscited by 61
  9. 2021Federated Multi-Armed Banditscited by 59
  10. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  11. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  12. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
17 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. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 38
  4. 2020The Gossiping Insert-Eliminate Algorithm for Multi-Agent Banditscited by 37
  5. 2015On Distributed Cooperative Decision-Making in Multiarmed Banditscited by 33
  6. 2020Kernel Methods for Cooperative Multi-Agent Contextual Banditscited by 21
  7. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  8. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  9. 2021Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processescited by 17
  10. 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 16
  11. 2022Communication Efficient Distributed Learning for Kernelized Contextual Banditscited by 15
  12. 2021Collaborative Pure Exploration in Kernel Banditcited by 13
  13. 2022Distributed Contextual Linear Bandits with Minimax Optimal Communication Costcited by 13
  14. 2022Linear Stochastic Bandits over a Bit-Constrained Channelcited by 9
  15. 2022Distributed Linear Bandits under Communication Constraintscited by 8
  16. 2022Collaborative Learning in Kernel-based Bandits for Distributed Userscited by 6
  17. 2021Adaptive Clustering and Personalization in Multi-Agent Stochastic Linear Banditscited by 4

Built on by

Not cited yet.