Collaborative Pure Exploration in Kernel Bandit
  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.
