# Collaborative Pure Exploration in Kernel Bandit

arXiv: https://arxiv.org/abs/2110.15771 · HTML: https://mlsanity.com/paper/2110.15771/

## 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 (most cited first, 29 of 29)

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [NAS-FPN: Learning Scalable Feature Pyramid Architecture for Object Detection](https://mlsanity.com/paper/1904.07392/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [LightTrack: Finding Lightweight Neural Networks for Object Tracking via One-Shot Architecture Search](https://mlsanity.com/paper/2104.14545/) (2021)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [MTL-NAS: Task-Agnostic Neural Architecture Search towards General-Purpose Multi-Task Learning](https://mlsanity.com/paper/2003.14058/) (2020)
- [Multi-Task Learning for Contextual Bandits](https://mlsanity.com/paper/1705.08618/) (2017)
- [Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1311.0800/) (2013)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1904.03293/) (2019)
- [Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits](https://mlsanity.com/paper/2110.01463/) (2021)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [Collaborative Top Distribution Identifications with Limited Interaction](https://mlsanity.com/paper/2004.09454/) (2020)
- [Kernel Methods for Cooperative Multi-Agent Contextual Bandits](https://mlsanity.com/paper/2008.06220/) (2020)
- [Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach](https://mlsanity.com/paper/1711.05174/) (2017)
- [Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions](https://mlsanity.com/paper/2011.03896/) (2020)
- [Pure Exploration in Kernel and Neural Bandits](https://mlsanity.com/paper/2106.12034/) (2021)
- [Coordination without communication: optimal regret in two players multi-armed bandits](https://mlsanity.com/paper/2002.07596/) (2020)

## Built on by (most cited first, 13 of 13)

- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [Communication Efficient Distributed Learning for Kernelized Contextual Bandits](https://mlsanity.com/paper/2206.04835/) (2022)
- [Strategic Scaling of Test-Time Compute: A Bandit Learning Approach](https://mlsanity.com/paper/2506.12721/) (2025)
- [Collaborative Learning in Kernel-based Bandits for Distributed Users](https://mlsanity.com/paper/2207.07948/) (2022)
- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [(Private) Kernelized Bandits with Distributed Biased Feedback](https://mlsanity.com/paper/2301.12061/) (2023)
- [Incentivized Communication for Federated Bandits](https://mlsanity.com/paper/2309.11702/) (2023)
- [Communication-Efficient Federated Non-Linear Bandit Optimization](https://mlsanity.com/paper/2311.01695/) (2023)
- [Laplacian Kernelized Bandit](https://mlsanity.com/paper/2601.00461/) (2026)
- [Distributed Optimization via Kernelized Multi-armed Bandits](https://mlsanity.com/paper/2312.04719/) (2023)
- [Optimal Regret Bounds for Collaborative Learning in Bandits](https://mlsanity.com/paper/2312.09674/) (2023)
- [Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomness](https://mlsanity.com/paper/2402.13182/) (2024)
- [Multi-Agent Best Arm Identification in Stochastic Linear Bandits](https://mlsanity.com/paper/2411.13690/) (2024)

## 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.