mlsanityData to 14 Oct 2026

Collaborative Pure Exploration in Kernel Bandit

arXiv 2110.15771 ↗First posted 29 Oct 2021cs.LGcited by 13

Not on the map. Why?

Abstract (arXiv)

In this paper, we formulate a Collaborative Pure Exploration in Kernel Bandit problem (CoPE-KB), which provides a novel model for multi-agent multi-task decision making under limited communication and general reward functions, and is applicable to many online learning tasks, e.g., recommendation systems and network scheduling. We consider two settings of CoPE-KB, i.e., Fixed-Confidence (FC) and Fixed-Budget (FB), and design two optimal algorithms CoopKernelFC (for FC) and CoopKernelFB (for FB). Our algorithms are equipped with innovative and efficient kernelized estimators to simultaneously achieve computation and communication efficiency. Matching upper and lower bounds under both the statistical and communication metrics are established to demonstrate the optimality of our algorithms. The theoretical bounds successfully quantify the influences of task similarities on learning acceleration and only depend on the effective dimension of the kernelized feature space. Our analytical techniques, including data dimension decomposition, linear structured instance transformation and (communication) round-speedup induction, are novel and applicable to other bandit problems. Empirical evaluations are provided to validate our theoretical results and demonstrate the performance superiority of our algorithms.

Key facts. Cited by 13 papers in the map (data through 14 Oct 2026). Builds on 29 of its 71 references that are in the map. First posted on arXiv 29 Oct 2021.

Builds on

29 of 71 references.

References · 29

  1. 2017On Kernelized Multi-armed Banditscited by 352
  2. 2019NAS-FPN: Learning Scalable Feature Pyramid Architecture for Object Detectioncited by 291
  3. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  4. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  5. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 136
  6. 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 114
  7. 2014Best-Arm Identification in Linear Banditscited by 100
  8. 2019Sequential Experimental Design for Transductive Linear Banditscited by 91
  9. 2020Differentially-Private Federated Linear Banditscited by 83
  10. 2021LightTrack: Finding Lightweight Neural Networks for Object Tracking via One-Shot Architecture Searchcited by 82
  11. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  12. 2021Federated Linear Contextual Banditscited by 61
17 more
  1. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  2. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  3. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  4. 2016Distributed Clustering of Linear Bandits in Peer to Peer Networkscited by 50
  5. 2020MTL-NAS: Task-Agnostic Neural Architecture Search towards General-Purpose Multi-Task Learningcited by 50
  6. 2017Multi-Task Learning for Contextual Banditscited by 47
  7. 2013Distributed Exploration in Multi-Armed Banditscited by 46
  8. 2020An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Banditscited by 45
  9. 2019Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Banditscited by 40
  10. 2021Asynchronous Upper Confidence Bound Algorithms for Federated Linear Banditscited by 31
  11. 2016Towards Instance Optimal Bounds for Best Arm Identificationcited by 30
  12. 2020Collaborative Top Distribution Identifications with Limited Interactioncited by 21
  13. 2020Kernel Methods for Cooperative Multi-Agent Contextual Banditscited by 21
  14. 2017Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approachcited by 19
  15. 2020Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisionscited by 13
  16. 2021Pure Exploration in Kernel and Neural Banditscited by 13
  17. 2020Coordination without communication: optimal regret in two players multi-armed banditscited by 11

Built on by

Cited by year (2026 to 14 Oct)

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

13 papers.

Sort:

By area:

  1. 2022Near-Optimal Collaborative Learning in Banditscited by 18
  2. 2022Communication Efficient Distributed Learning for Kernelized Contextual Banditscited by 15
  3. 2025Strategic Scaling of Test-Time Compute: A Bandit Learning Approachcited by 8
  4. 2022Collaborative Learning in Kernel-based Bandits for Distributed Userscited by 6
  5. 2023Pure Exploration in Asynchronous Federated Banditscited by 6
  6. 2023(Private) Kernelized Bandits with Distributed Biased Feedbackcited by 3
  7. 2023Incentivized Communication for Federated Banditscited by 3
  8. 2023Communication-Efficient Federated Non-Linear Bandit Optimizationcited by 1
  9. 2026Laplacian Kernelized Banditcited by 1
  10. 2023Distributed Optimization via Kernelized Multi-armed Banditscited by 0
  11. 2023Optimal Regret Bounds for Collaborative Learning in Banditscited by 0
  12. 2024Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomnesscited by 0
1 more
  1. 2024Multi-Agent Best Arm Identification in Stochastic Linear Banditscited by 0