Collaborative Pure Exploration in Kernel Bandit
Authors: Yihan Du
Wei Chen
Yuko Kuroki
Longbo Huang
Venue: ICLR 2023 poster (2023)
Keywords: Collaborative Pure Exploration (CoPE)
kernel bandit
multi-agent bandit
multi-task learning
communication round

Abstract: In this paper, we propose a novel Collaborative Pure Exploration in Kernel Bandit model (CoPE-KB), where multiple agents collaborate to complete different but related tasks with limited communication. Our model generalizes prior CoPE formulation with the single-task and classic MAB setting to allow multiple tasks and general reward structures. We propose a novel communication scheme with an efficient kernelized estimator, and design optimal algorithms CoKernelFC and CoKernelFB for CoPE-KB with fixed-confidence  and fixed-budget objectives, respectively. Nearly matching upper and lower bounds in both sampling and communication complexity are established to demonstrate the optimality of our algorithms. Our theoretical results explicitly quantify how task similarities influence learning speedup, and only depend on the effective dimension of feature space. Our novel techniques including an efficient kernelized estimator and linear structured instance transformation, which overcome the communication difficulty in high-dimensional feature space and derive communication round lower bounds, can be of independent interests. 

Published as a conference paper at ICLR 2023
COLLABORATIVE PURE EXPLORATION IN KERNEL BANDIT
Yihan Du
Wei Chen
Institute for Interdisciplinary Information Sciences
Microsoft Research
Tsinghua University
Beijing, China
Beijing, China
we 1 c0mi croso st..oottcooo com
duyh18@mal ils weeemalsssssinhiiie.. tsinghua. edu. on
Yuko Kuroki
Longbo Huang
The University of Tokyo & RIKEN AIP, Tokyo, Japan CENTAI Institute, Turin, Italy yuko. kuroki @centai.eu
Institute for Interdisciplinary Information Sciences Tsinghua University
Beijing, China Longiochangg@ts inghua. edu. on
ABSTRACT
In this paper, propose novel Collaborative Pure Exploration in Kernel Bandit model (CoPE-KB), where multiple agents collaborate to complete different but related tasks with limited communication. Our model generalizes prior CoPE for- mulation with the single-task and classic MAB setting to allow multiple tasks and general reward structures. We propose novel communication scheme with an ef- ficient kernelized estimator, and design algorithms CoKernelFC and CoKernelFB for CoPE-KB with fixed-confidence and fixed-budget objectives, respectively. Sample and communication complexities are provided to demonstrate the effi- ciency our algorithms. Our theoretical results explicitly quantify how task sim- ilarities influence learning speedup, and only depend on the effective dimension feature space. Our novel techniques, such as an efficient kernelized estimator and decomposition of task similarities and arm features, which overcome the com- munication difficulty in nigh-dimensional feature space and reveal the impacts task similarities sample complexity, can be of independent interests.
INTRODUCTION
Pure exploration (Even-Dar et al., 2006; Kalyanakrishnan et al., 2012: Kaufmann et al., 2016) is a fundamental online learning problem multi-armen aanted bandits (Thompson, 1933; Lai Robbins, 1985; Auer et al., 2002), where an agent chooses options (often called arms) and observes random feedback with the objective of identifying the best arm. This formulation has found many important applications, such as web content optimization (Agarwal et al., 2009) and online advertising (Tang al., 2013). However, traditional pure exploration (Even-Dar al., 2006; Kalyanakrishnan 2012; Kaufiman et al., 2016) only considers single-agent decision making, and cannot be applied to prevailing distributed systems in real world, which often face heavy computation load and require multiple parallel devices to process tasks, e.g., distributed web servers (Zhuo et al., 2003) and data centers (Liu et al., 201
al.,
To handle such distributed applications, prior works (Hillel al., 2013; Tao et al., 2019; Karpov et al., 2020) have developed the Collaborative Pure Exploration (CoPE) model, where multiple agents communicate and cooperate to identify the best arm with learning speedup. Yet, existing results focus only on the classic multi-armed bandit (MAB) setting with single task, i.e., all agents solve common task and the rewards of arms are individual values (rather than generated by ward function). However, in many distributed applications such as multi-task neural architecture search (Gao et al., 2020), different devices can face different but related tasks, and there exists sim- ilar dependency of rewards on option features among different tasks. Therefore, it is important to
"Corresponding author.

---

Published as a conference paper at ICLR 2023
develop more general CoPE model to allow heterogeneous tasks and structured reward depen- dency, and further theoretically understand how task correlation impacts learning.
Motivated by the above fact, we propose novel Collaborative Pure Exploration in Kernel Bandit (CoPE-KB) model. Specifically, in CoPE-KB, each agent is given a set of arms, and the expected reward of each arm is generated by task-dependent reward function in a high and possibly infinite dimensional Reproducing Kernel Hilbert Space (RKHS) (Wahba, 1990; Schölkopf et al., 2002). Each agent sequentially chooses arms to sample and observes random outcomes in order identify the best arm. Agents can broadcast and receive messages to and from others in communication rounds, so that they can collaborate and exploit the task similarity to expedite learning processes.
Our CoPE-KB model is novel generalization of prior CoPE problem (Hillel et al., 2013; Tao et al., 2019; Karpov et al., 2020), which not only extends prior models from the single-task setting to mul- tiple tasks, but also goes beyond classic MAB setting and allows general (linear or nonlinear) reward structures. CoPE-KB is most suitable for applications involving multiple tasks and complicated re- ward structures. For example, in multi-task neural architecture search (Gao et al., 2020), one wants to search for best architectures for different but related tasks on multiple devices, e.g., the object detection (Ghiasi et al., 2019) and object tracking (Yan et al., 2021) tasks in computer vision, which often use similar neural architectures. Instead of individually evaluating each possible architecture, one prefers to directly learn the relationship (reward function) between the accuracy results achieved and the features of used architectures (e.g., the type of neural networks), and exploit the similarity of reward functions among tasks accelerate the search.
Our CoPE-KB generalization faces a unique challenge on communication. Specifically, in prior CoPE works with classic MAB setting (Hillel et al., 2013; Tao al., 2019; Karpov et al., 2020), agents only need to learn scalar rewards, which are easy to transmit. However, under the ker- nel model, agents need to estimate high or even infinite dimensional reward parameter, which is inefficient to directly transmit. Also, if one naively adapts existing reward estimators for kernel bandits (Srinivas et al., 2010: Camilleri al., 2021) to learn this high-dimensional reward parame- ter, he/she will suffer an expensive communication cost dependent on the number of samples N(r,, since the reward estimators there need all raw sample outcomes to be transmitted. To tackle this challenge, we develop an efficient kernelized estimator, which only needs average outcomes on nV arms and reduces the required transmitted messages from O(N(r)) O(nV). Here V is the number of agents, and n is the number of arms for each agent. The number of samples NO) depends on the inverse of the minimum reward gap, and is often far larger than the number of arms n..
Under the CoPE-KB model, we study two popular objectives, i.e., Coeed-Confidence (FC), where we aim to minimize the number of samples used under a given confidence, and Fixed-Budget (FB), where the goal is minimize the eиror probability under given sample budget. We design two algorithms CoKernelFC and CoKernelFB, which adopt an efficient kernelized estimator to simplify the required data transmission and enjoy a OnnV) communication cost, instead of O(N(r)) as in adaptions of existing kernel bandit algorithms (Srinivas al., 2010; Camilleri et al., 2021). We pro- vide sampling and communication guarantees, and also interpret them by standard kernel measures, e.g., maximum information gain and effective dimension. Our results rigorously quantify the influ- ences of task similarities on learning acceleration, and hold for both finite and infinite dimensional feature space.
The contributions of this paper are summarized as follows:
We formulate collaborative pure exploration in kernel bandit (CoPE-KB) model, which generalizes prior single-task CoPE formulation to allow multiple tasks and general reward structures, and consider two objectives, i.c., fixed-confidence (FC) and fixed-budget (FB).
For the FC objective, we propose algorithm CoKernelFC, which adopts an efficient kernel- ized estimator to simplify the required data transmission and enjoys only a ((nV) commu- nication cost. We derive sample complexity Ö ((5"(5) log 8 8-1) and communication rounds Olog A a. Here & is the regularization parameter, and pE( is the problem hardness (sce Section 4.3).
For the FB objective, we design novel algorithm CoKernelFB with error probability ((exp( TV
(=()) V) and communication rounds O(log(w(E, (())) Here T is the sample
2

---

Published as a conference paper at ICLR 2023
budget, X' is the set of task-arm feature pairs, and ((, is the principle dimension of data projections in X' RKHS (see Section 5.1).
* Our algorithms offer an efficient communication scheme for information exchange in high dimensional feature space. Our results explicitly quantify how task similarities impact learning acceleration, and only depend on the effective dimension of feature space.
Due to the space limit, we defer all proof' to the appendix.
RELATED WORK
Below we review the most related works, and defer a complete literature review to Appendix B.
Collaborative Pure Exploration (CoPE). Hillel et al. (2013); Tao et al. (2019) initiate the CoPE literature with the single-task and classic MAB setting, where all agents solve a common classic best arm identification problem (without reward structures). Karpov et al. (2020) further extend the formulation in (Hillel et al., 2013; Tao et al., 2019) to best m arm identification. Our CoPE-KB generalizes prior CoPE works to allow multiple tasks and general reward structures, and faces unique challenge on communication due to the high-dimensional feature space. Recently. Wang et al. (2019) study distributed multi-armed and linear bandit problems, and Hc et al. (2022) inves- tigate federated linear bandits with asynchronous communication. Their algorithms directly com- municate the estimated reward parameters and cannot be applied to solve our problem, since under kernel representation, the reward parameter is nigh-dimensional and expensive to explicitly transmit.
Kernel Bandits. Srinivas et al. (2010); Valko et al. (2013); Scarlett al. (2017); Li & Scarlett (2022) investigate the single-agent kernel bandit problem and establish regret bounds dependent on maximum information gain. Krause & Ong (2011); Deshmukh al. (2017) study multi-task kernel bandits based on composite kernel functions. Dubey et al. (2020); Li et al. (2022) consider multi- agent kernel bandits with local-broadeast and client-server communication protocols, respectively. Camilleri et al. (2021); Zhu et al. (2021) investigate single-agent pure exploration in kernel space. The above kernel bandit works consider either regret minimization or single-agent formulation, which cannot be applied to resolve our challenges on round-speedup analysis and communication.
3 COLLABORATIVE PURE EXPLORATION IN KERNEL BANDIT (CoPE-KB)
In this section, we define the Collaborative Pure Exploration in Kernel Bandit (CoPE-KB) problem.
Agents and Rewards. There are V agents indexed by [V] == (1...., V). who collaborate solve different but possibly related instances (tasks) of the Pure Exploration in Kernel Bandit (PE-KB) problem. For each agent e [V], she is given a set of n arms X ffe,1..... Fumn C 12xx where Zu.i (i E [n)) describes the arm feature, and dx is the dimension of arm feature vectors. The expected reward of each arm x E X, is far),, where fo X, + is an unknown reward function. Let X == Ve. At each timestep t, each agent pulls an arm x E X, and observes a random reward v [x(x + n Here v/द is zero-mean and 1 I-sub-Gaussian noise, and it is independent among different and u. We assume that the best arms x,,, == argmax,ext fo(x) are unique for all E [V], which is a common assumption in the pure exploration literature (Even-Dar Audibert et al., 2010; Kaufmann et al., 2016).
-Dar et al., 2006;
Multi-Task Kernel Composition. We assume that the functions fu are parametric functionals of global function F Z x X' + I. which satisfies that, for each agent e E [V], there exists a task feature vector E Z such that
fe(x) = F'z,, x), Vr XT.
(1)
Here 2 and X' denote the task feature space and arm feature space, respectively. Note that Eq. (1)
allows tasks to be different for agents (by having different task features), whereas prior CoPE works (Hillel et al., 2013; Tao et al., 2019; Karpov et al., 2020) restrict the tasks (Ze and f.) to be the same for all agents [V].
We denote a task-arm feature pair (i.e., overall input of function F) by 5 == (Zur x). and denote the space of task-arm feature pairs (i.c., overall input space of function F) by X == Z x X. As a standard assumption in kernel bandits (Krause & Ong, 2011; Deshmukh al., 2017; Dubey al.,
3

---

Published as a conference paper at ICLR 2023
2020), assume that F has a bounded norm in high (possibly infinite) dimensional Reproducing Kernel Hilbert Space (RKHS) H. specified by the kernel k: X' x X + R, and there exists a feature mapping Φ X H and unknown parameter 0* E H such that' F F(2) = (()) T 0r, Vi E X, k( x') = o(3) ((F), Vi, E X. Here k(.,-) is product composite kernel, which satisfies that for any 2, E Z and x, E X, k((2, (z', - (z z') kx(x,
where kz : 2 x + is the task feature kernel which measures the similarity of functions se- and hx X' x X' + R is the arm feature kernel which depicts the feature structure of arms. The computation of kernel function ((;,)) operates only on cow-dimensional input data. By expressing all calculations via k(,,). +), it enables us avoid maintaining high-dimensional Φ(-) and attain com- putation efficiency. In addition, the composite structure of k).,,) allows us to model the similarity among tasks.
Let K == (Zx, z. Du.eee de- note the kernel matrix of task fea- tures. rank (2) characterizes how much the tasks among agents are sim- ilar. For example, if agents solve a common task, i.e., the arm set X, and reward function fo are the same for all agents, we have that the task fea- ture 2, is the same for all v E [V]. and rank(K, (x²) = 1; If all tasks are totally different, rank(Kz)
113 = F11 1]
d( =(==) 1.1.0.22
F(hz) =
Ttem with roward 4 2,2
Tiem reward VT
reward 5 3,7
S111 = [1.
F2. - (0, 1,
Tank
Task2
M (111000,01 F(iaa) 55
F(Fra) =3+1)
Task feature: in = by =
Vi E Z, Vr [ "ro""" E a. Reward function:
F(3) f'),,)) (-(h), +201 +aal)) + + +2V -2 (372
Festure mapging:
((2) = o(s. (4. /asay-V//e V2nn) vann /aagl
V.
Reward parameter: g" 1,
To better illustrate the model, we pro- vide a 2-agent example in Figure 1. There are Items 1,2.3 with expected rewards 3 + 22, 4 2,2, 3v2 respectively. Agent 1 is given Items 2, denoted by X1 (1111 and Agent 2 is given Items 2,3, denoted by X2_ = {
Kernal function:
A(², = (((s,))) )(...)) (f, (aay//) meplte + x
Figure 1: Illustrating example for CoPE-KB.
where both 11,2 and 22,1 refer to Item 2. The task feature 21 22 = 1, which means that the expected rewards of all items are generated by common function. The reward function F' is nonlinear with respect to x, but can be represented in a linear form in higher-dimensional feature space, i.e., (()) = x)) d(ī) T 0 with ã := (2,z) for any 2 E 2 and x X. Here d(ā) is the feature embedding, and H* is the reward parameter. The computation of kernel function k( .²) only involves -indesesioonal input data ž and 8', rather than higher-dimen dimensional feature embedding ((-). 6.6.0 4" and is are specified in Figure 1. The two agents can share the learned information on 0" to accelerate learning.
Communication. Following the popular communication protocol in the CoPE literature (Hillel et al., 2013; Tao et al., 2019; Karpov et al., 2020), we allow these V agents to exchange information via communication rounds, in which each agent can broadcast and receive messages from others. Following existing CoPE works (Hillel et al., 2013; Tao et al., 2019; Karpov et al., 2020), we restrict the length of each message within (n)) bits for practicability, where is the number of arms for each agent, and we consider the number of bits for representing a real number as a constant, We want agents to cooperate and complete all tasks using few communication rounds as possible.
Objectives. We consider two objectives of the CoPE-KB problem, one with Creef-CConieence (FC) and the other with Fixed-Budget (FB). In the FC setting, given a confidence parameter ó E (0, 1), the agents aim to identify F,,, for all v E [V] with probability at least - 6, and minimize the average number of samples used per agent. In the FB setting, the agents are given an overall TV sample budget (T average samples per agent), and aim to use at most TV samples to identify Iv,, for all E [V] and minimize the error probability. In both FC and FB settings, the agents are requested to minimize the number of communication rounds and control the length of each message within ((n) bits, as in the CoPE literature (Hillel et al., 2013; Tao et al., 2019; Karpov et al., 2020).
For any I h E H. we denote their inner-product by TT = (1e,h") ft')xx N and denote norm of by vATh h. For any h. H and matrix M, we denote [| == Wh T M th.
|h]|
4

---

Published as a conference paper at ICLR 2023
Algorithm Collaborative Multi-agent Algorithm CokernelFC: for Agent E [V]
Input: 6, &, k(.,)) & x X I, regularization parameter Ç. rounding procedure ROUND, rounding approximation parameter = To
2: Initialization: 6, == Σy for all 2 1. B + R. for all v' E [V].
3: for round 1, 2, ... do
4: Let X and pf be the optimal solution and optimal value of [lo(ā;) o ( -=)
min max
// compute the optimal
xEA "..
sample allocation
5: N max (2 + p) log (2n (/n21/ r(E, 17, where T(E, s) is the
number of samples needed by ROUND
6: "5I....5yyo.
7: Extract a sub-sequence 5(() from ($1,..., No)) which only contains the arms in X.
Sample the arms in a(?) and observe random rewards y!")
8:
9: Let N!. and o be the number samples and the average sample outcome on arm To.4
Broadcast {(NV)T) sit)) and receive {(NS)) ol (eem from all other agents vf + v
10:
(T) + IV N (1,, ......V.KK k(z =nv]]T for any I E X. KO) +
11:
N/ (T k(T,, ā Meseen g(r) + Iv N1 11 1... V N (
I/ organiie overall
sample information
12:
for all v' [V] do
(K (=') Á, .') (#) h
+ ()) (()))((K))))))))))))))))))))))<)
Vi, B(O)
// use
kernelized estimator (described in Section 4.2) to estimate reward gaps
B(++)) (((r) ((# B EN E B Á 2-r) // discard sub-optimal arms
14:
15: end for
if Vvo [V], (V],18((+2)
return ((r+1) ,..., (+)
17: end for
Different from prior CoPE-KB works (Tao et al., 2019; Karpov et al., 2020) which consider mini- mizing the maximum number of samples used by individual agents, aim to minimize the average (total) number of samples used. Our objective is motivated by the fact that in many applications, obtaining sample is expansive, e.g., clinical trials (Weninger al., 2019), and thus it is important to minimize the average (total) number of samples required. For example, consider that medical institution wants to conduct multiple clinical trials identify the best treatments for different age groups of patients (different tasks), and share the obtained data to accelerate the development. Since conducting a trial can consume significant medical resources and funds (c.g., organ transplant surg- eries and convalescent plasma treatments for COVID-19), the institution wants to minimize the total number trials required. Our CoPE-KB model is most suitable for such scenarios.
To sum up. in CoPE-KB, let agents collaborate simultancously complete multiple related best arm identification tasks using few communication rounds. In particular, when all agents solve the same task and X' is the canonical basis, CoPE-KB reduces existing CoPE with classic MAB setting (Hillel et al., 2013; Tao et al., 2019).
4 FiXED-CONFIDENCE COPE-KB
We start with the fixed-confidence setting. We present algorithm CoKerne1FC equipped with an efficient kernelized estimator, and provide theoretical guarantees in sampling and communication.
4.1 ALGORITHM CoKernelFC
CoKernelFC (Algorithm 1) is an elimination- multi-agent algorithm. The procedure for each
agent is follows. Agent maintains candidate arm sets B²(r) for all v' E [V]. In each round T. agent e solves a global min-max optimization (Line 4) to find the optimal sample allocation x A g. which achieves the minimum estimation error. Here Ag denotes the collection of all dis-
5

---

Published as a conference paper at ICLR 2023
tributions on X, and p. is the factor of optimal estimation error. In practice, the high- disensinnsi feature embedding σ(ā) is only implicitly maintained, and this optimization can be efficiently solved by kernelized gradient descent (Camilleri et al., 2021) (see Appendix C.2). After solving this opti- mization, agent v uses pr to compute the number of samples ((r) to ensure the estimation error of reward gaps to be smaller than 2 (-(++] (Line 5).
Next, we call rounding procedure ROUND(E, X Nr)), E) (Allen-Zhh et al., 2021; Camilleri et al., 2021), which rounds weighted sample allocation X E 4x into a discrete sample sequence (f1,...,&xco) E X and ensures the rounding error within (Line 6). This rounding pro- 0 ( (Line 5). Here T(E. X;, E)
cedure requires the number of samples (²) 2 T(,,,,,,, is the number of samples needed by ROUND. d(E, X²) is the number of the eigenvalues of matrix ExER (+)))))))())) which are greater than f. It stands for the effective dimension of feature space (see Appendix C.1 for details of this rounding procedure).
Obtaining sample sequence ; agent extracts a sub-sequence s(") which only con- tains the arms in her arm set &, Then, she sample the arms in x!r) and observe sample outcomes yo (r)) After sampling, she only communicates the number of samples N(C and average sample out- come o.% on each arm že,s with other agents (Line 10). Receiving overall sample information, she uses a kernelized estimator (discussed shortly) to estimate the reward gap Á, (ū,,ā') ,') between any two arms ē, E' E B for all v' E [V], and discards sub-optimal arms (Lines 13,14). In Line 11, for any i E [nV]. we use 7t, ((()) and N7(") with single subscript to denote the i-th arm in X, the average sample outcome on this arm and the number of samples allocated to this arm, respectively.
4.2 KERNELIZED ESTIMATOR, COMMUNICATION AND COMPUTATION
Now we introduce the kernelized estimator (Line 13), which boosts communication and computation efficiency of CoKerne1FC. First note that, our CoPE-KB generalization faces unique challenge on communication, i.c., how let agents efficiently share their learned information on the high- dimensional reward parameter 6* Naively adapting existing federated linear bandit or kernel bandit algorithms (Dubey & Pentland, 2020; Huang al., 2021; Dubey al., 2020), which transmit the whole estimated reward parameter or all raw sample outcomes, will suffer a (dim (d)m or O(N(r) communication cost, respectively. Here, the number of samples (7 Ödeat/ 2ii.) where dar the effective dimension of feature space and Amin is the minimum reward gap. Thus, ((()) is far larger than the number of arms v/V when Amin is small.
Kernelized Estimator. To handle the communication challenge, we develop a novel kernelized estimator (Eq. (3)) to significantly simplify the required transmitted data. Specifically, we make a key observation: since the sample sequence (ø), Nvt:) ) are constituted by arms TI,..., Tnv. one can merge repetitive compulations for same arms Then, for all E [nv]. we merge the repetitive feature embeddings ((z;) for same arms ž, and condense the (r) raw sample outcomes to average outcome y! on each arm ã;, As a result, we express Ó, a simplified kernelized form, and use to estimate the reward gap Å (i, F') between any two arms ã, ø' as
0, = T (r( &T + k(r) -lg((),
(2)
Á, .3) = (x(T)) - ((31)) 0, = (kr(T) - (,')) (NW + -70
(3)
Here &, = IV N ((tt) ((Ti) T ( K6) = WN k(T,, (illsetv))
( V VNNDA(T, ānv) and g(r)
(T) = 2)δ(ā)
IV W ( D / NN stand for the feature embeddings, kernel matrix, correlations and average outcomes of the nV arms, respectively, which merge repetitive information on same arms We refer interested reader to Appendix C.2, C.3 for a detailed derivation of our kernelized estimator and comparison with existing estimators (Dubey et al., 2020; Camilleri et al., 2021).

---

Published as a conference paper at ICLR 2023
Communication. Thanks to the kerneiieed estimator, only need transmit the nV average outcomes of",.... V federated linear bandit or kernel bandit algorithms (Dubey & Pentland, 2020; Dubey et al., 2020). This significantly reduces the number of transmission bits from O(dim(H() or O(N(r) to only OnnV). ). and satisfies the (ii) per message requirement.
(Line 10), instead of the whole 6, or N(r) raw outcomes as in existing
Computation. In CoKernelFC, ((Ø) and 0, are maintained implicitly, and steps (e.g., g., Lines 4, 13) can be implemented efficiently by only querying kernel function k(:,-) (see Appendix C.2 for implementation details). Thus, the computation complexity for reward estimation is only Poly(nV), instead of Poly(dim(() (d)) as in prior kernel bandit algorithms (Zhou al., 2020; Zhu al., 2021).
4.3 THEORETICAL PERFORMANCE OF CoKernelFC
To formally state our results, we define the speedup and hardness as in the literature (Hillel et al., 2013; Tao et al., 2019; Fiez et al., 2019).
For a CoPE-KB instance I, let TAM. denote the average number of samples used per agent in multi-agent algorithm Aas to identify all best arms. Let TAg.I denote the average number of samples used per agent, by replicating V copies of single-agent algorithm As to complete all tasks (without communication). Then, the speedup of AM on instance I is defined as
BAN inf TAsII As TAM.I
holds that S BAM.I S V. When all tasks are the same, AAN.I can approach V. When all tasks are totally different, communication brings no benefit and AAN II 1. This speedup can be similarly defined for error probability results (see Section 5.2), by taking TAI and TA as the smallest numbers of samples needed meet the confidence constraint.
The hardness for CoPE-KB is defined as
-
(5) where ç 2 O regularization parameter, and A(C, == +I+ (=)()))(E) This defini-
(E) min
max
XEAR & ((a..) JoE[V]
tion of p" (E) is adapted from prior linear bandit work (Fiez et al., 2019). Here F(ū.,)) F(ž) is the reward gap between the best arm or,- and suboptimal a dimension-related factor of estimation error. Intuitively, p (E) indicates how many samples
5, and (I)(,.,.) (f
takes to make the estimation error smaller than the reward gap under regularization parameter &.
Let Amin == mingee J ".V]v] best arm and suboptimal arms among all tasks. Let S denote the average number samples used by each agent, i.e.. per-agent sample complexity. Below we present the performance of CoKernelFC.
(F(,,,))
F()) denote the minimum reward gap between the
Theorem
Upper Bound). Suppose that & satisfies 32(1+=]|l=-TI With probability at least 1 - 8, CoKernelFC returns the best arms for all v E [V], with per-agent sample complexity
TFixed-Coffidecce VE max max;, "E llo(ē:) Φ(ē,) (AASA))) I
s=0(p² (0((6) log Amin
[log
(nV)
+ log log Amla)
d(s,>7) X7)
loog Amin
8
V
and communication rounds Ollog A )
Remark 1. The condition on regularization parameter & implies that CoKernelFG needs a small regularization parameter such that the bias due regularization is smaller than Ayia, Such condi- tions are similarly needed in prior kernel bandit work (Camilleri et al., 2021), and can be dropped in the extended PAC setting (allowing gap between the identified best arm and true best arm). The d(G. X)) log( A )/V term cost for using rounding procedure ROUND. This is a second order term when the reward gaps Ap, == F(ū..-) ) F(r.,) < for all Ey, E X. \ } and E [V], in pure exploration (Fiez et al., 2019; Zhu et al., 2021).
which is the common
When all tasks are the same, Theorem achieves a V-speedup, since replicating V copies of single- agent algorithms (Camilleri et al., 2021; Zhu et al., 2021) to complete all tasks without communica-

---

Published as a conference paper at ICLR 2023
tion will cost (E)" samples per agent. When tasks are totally different, there is no speedup in Theorem 1, since each copy of single-agent algorithm solves a task in her own sub-dimension and costs (()"(E) samples (p" (E) stands for the effective dimension of all tasks). This result matches the restriction of speedup.
Interpretation. Now, we interpret Theorem 1 by standard measures in kernel bandits and a decom- position with respect to task similarities and task features. Below we first introduce the definitions of maximum information gain and effective dimension, which are adapted from kernel bandits with regret minimization (Srinivas et al., 2010; Valko et al., 2013) to the pure exploration setting.
We define the maximum information gain T == m log det (1 (1x)-) where Kx == (vA,2 ăy ky)]k, denotes the kernel matrix under sample allocation x. Y stands for the maximum information gain obtained from the samples generated according to sample allocation A.
Let X = a log det (I -x) denote the sample allocation which achieves the maximum information gain, and let on ... 2 Onv denote the eigenvalues of Kx-. Then, we define the effective dimension as derr == min E [nV] : jE log(nV)) 2 Dis++1 0z}- der stands for the number of principle directions that data projections in RKHS spread.
Recall that K2 [liz (Zus For V[V] denotes the kernel matrix of task similarities. Let Kx [v
[k(ee)(( denote the kernel matrix of arm features under sample allocation X". Corollary 1. The per-agent sample complexity S of algorithm CoKernelFC can be bounded by delt
r
(c) == Trank( Kz) rank Kx,x-)
(a) 5=S=Ch A2
(b) S =
A2.. (A
A
min
min
where Ō() omits the rounding cost term d(c X1) log( / and logarithmic factors.
Remark 2. Corollaries (b)). show that, our sample complexity can be bounded by the maximum information gain, and only depends on the effective dimension of kernel representation. Corol- lary I(c) reveals that the more tasks are similar (i.e., the smaller rank K 2) is), the fewer samples agents need. For example, when all tasks are the same, i.e., rank(K2 [2) = 1, each agent only needs & fraction of the samples required by single-agent algorithms (Camilleri et al., 2021; Zhu et al.,
2021) (which need ((ran((Kx (x, Ami.) samples). Conversely, when all tasks are totally differ- ent, i.e., rank K ) = V. no advantage can be obtained from communication, since the information from other agents useless for solving local tasks. Our experimental results also reflect this rela- tionship between task similarities and speedup, which match our theoretical bounds (see Section 6). We note that these theoretical results hold for both finite and infinite RKHS.
5 FIXED-BUDGET COPE-KB
For the fixed-bude bredetudget objective, we propose algorithm CoKernelFB and error probability guarantees. Due to space limit, we defer the pseudo-code and detailed description to Appendix C.4.
5.1 ALGORITHM CoKernelFB
CoKernelFB pre-determines the number of rounds and the number of samples according to the principle dimension of arms, and successively down candidate arms to half based principle dimension. CoKernelFB also adopts the efficient kernelized estimator (in Section 4.2) to estimate the rewards of arms, that agents only need to transmit average outcomes rather than all raw sample outcomes or the whole estimated reward parameter. Thus, CoKernelFB only requires a (nn) communication cost, instead of (()(r) or O(dim(H)) as in adaptions of prior single-agent and fixed-budget algorithm (Katz-Samuels et al., 2020).
5.2 THEORETICAL PERFORMANCE CoKernelFB
Define the principle dimension of & as ((, == minxe max a,,,,,,, ( where A(E, == {1 + Eie * w(E, X) represents the principle dimension of data projections in X to RKHS. Now we provide the error probability guarantee for CoKernelFB
8

---

Published as a conference paper at ICLR 2023
CofommeFCC (eurs)
CofiemaFFC (ours)
CafemmlFC (ours)
Semple Compleilly
InSRACE
Sammppe Complnsiiy
IndRAcE Crraeiatt.
Samppe Compleiity
CrsamallC-Anddaee InSRACE
IndRAGEIV
InSALBA
(a) FC, rank K2) =
(b) FC, rank K2) ( E (1,V)
(c) FC, rank K2) =
Figure 2: Experimental results for CoPE-KB in the FC setting.
Theorem (Fixed-Budget Upper Bound). Suppose that & satisfies (5))))111 Algo- rithm CokernelFF uses at most T samples per agent, and returns the best arms Lt,, for all v E [V] with error probability
o exp (-
pr(E) (-pr(t) log(w x7)) n22 (E ({.
TV
and ((log(w(ss X))) communication rounds.
To guarantee an enror probability 8. CoKernelFB only requires Ö (2(() which attains full speedup when all tasks are the same. Theorem 2 can be decomposed into compo- nents related to task similarities and arm features in Corollary 1 (see Appendix E.2).
V log log 8-1) sample budget,
6 EXPERIMENTS
In this section, we provide the experimental results. Here we set = 5, 6, 0.005, H Rd, d E [4,8, 20), l" = 10.1, 0.1 + Ami..... 0.1 + (d - 1) Amin E |0.1, 0.8] and rank(K=] E V]. We run 50 independent simulations and plot the average sample complexity with 95% confidence intervals (see Appendix A for a complete setup description and more results).
We compare our algorithm CoKernelFC with five baselines, i.e., CoKernel-IndAllo,, IndRAGE, IndRAGE/V, IndALBA and IndPolyALBA. CoKernel-IndAlloo is an ablation variant of CoKerne1FC, where agents use locally optimal sample allocations. IndRAGE, IndALBA and IndPolyALBA are adaptions of cxisting single-agent algorithms RAGE (Fiez et al., 2019), ALBA (Tao et al., 2018) and PolyALBA (Du et al., 2021), respectively. IndRAGE/V is a V-speedup baseline, which divides the sample complexity of the best single-agent adaption IndRAGE by V.
Figures 2(a), 2(b) show that CoKernelFC achieves the best sample complexity, which demonstrates the effectiveness of our sample allocation and cooperation schemes. Moreover, the empirical results reflect that the more tasks are similar, the higher learning speedup agents attain, which matches our theoretical analysis. Specifically, the rank(Kz) 1 case (Figure 2(a)). i.c. tasks are the same, CoKerne1FC matches the V-speedup baseline IndRAGE-V. In the (ank(K2) E V1) case (Figure 2(b)), i.c. tasks are similar, the sample complexity of CoKerne1FC lies between IndRAGE/V and IndRAGE, which indicates that CoKernelFC achieves a speedup lower than V. In the rank(Kz z) V case (Figure 2(c)), i.e., tasks are totally different, CoKernelFC performs similar to IndRAGE, since information sharing brings no advantage in this case.
CONCLUSION
In this paper, we propose a collaborative pure exploration in kernel bandit (CoPE-KB) model with fixed-confidence and fixed-budget objectives. CoPE-KB generalizes prior CoPE formulation from the single-task and classic MAB setting allow multiple tasks and general reward structures. We propose novel algorithms with an efficient kernelized estimator and a novel communication scheme. Sample and communication complexities are provided to corroborate the efficiency of our algo- rithms. Our results explicitly quantify the influences of task similarities on learning speedup, and only depend the effective dimension of feature space.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
The work of Yihan Du and Longbo Huang is supported by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grant 2020AAA0108400 and 2020AA40108403, the Tsinghua University Initiative Scientific Research Program, and Tsinghua Precision Medicine Foundation 10001020109. Yuko Kuroki was supported by Microsoft Research Asia and IST ACT-X JPMJAX200E.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24:2312-232)) 2011.
Deepak Agarwal, Bee-Chung Chen, and Pradheep Elango. Explore/exploit schemes for web content optimization. In IEEE International Conference on Data Mining, pp. 1-10. IEEF, 2009.
Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang. Near-optimal discrete optimization for experimental design: A regret minimization approach. Mathematical Programming, 186(1): 439-478, 2021.
Jean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In Conference on Learning Theory, pp. 41-53, Citeseer, 2010.
Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer. Finite-time analysis of the multi-armed bandit problem. Machine Learning, 47(2-3):235-256, 2002.
Romain Camilleri, Kevin Jamieson, and Julian Katz-Samuels. High-dimensional experimental de- sign and kernel bandits. In International Conference on Machine Learning, pp. 1227-1237. PMLR, 2021.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference Machine Learning, pp. 844 853. PMLR, 2017.
Aniket Anand Deshmukh, Urun Dogan, and Clayton Scott. Multi-task learning for contextual ban- dits. Advances in Neural Information Processing Systems, pp. 4851-4859, 2017.
Yihan Du, Yuko Kuroki, and Wei Chen. Combinatorial pure exploration with full-bandit or partial linear feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7262-7270, 2021.
Abhimanyu Dubey and AlexSandy' Pentland. Differretially--rrivte federated linear bandits. Ad- vances in Neural Information Processing Systems, 33:6003-6011 2020.
Abhimanyu Dubey et al. Kernel methods for cooperative multi-agent contextual bandits. In Inter- national Conference on Machine Learning, pp. 2740-2750 2020.
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 10) 2006.
Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. Advances in Neural Information Processing Systems, 32:10667- 10677, 2019.
Yuan Gao, Haoping Bai, Zequn Jie, Jiayi Ma, Kui Jia, and Wei Liu. Mtl-nas: Task-agnostic neural architecture search towards ceneral-purpose multi- task learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11543-11552, 2020.
Golnaz Ghiasi, Tsung- Yi Lin, and Quoc V Le. Nas-fpn: Learning scalable feature pyramid architec- ture for object detection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Patlern Recognition, pp. 7036-7045, 2019.
10

---

Published as a conference paper at ICLR 2023
Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu. A simple and provably efficient algorithm for asynchronous federated contextual linear bandits. Advances in Neural Information Processing Systems, 2022.
Eshcar Hillel, Zohar S Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. Distributed explo- ration in multi-armed bandits. In Advances in Neural Information Processing Systems, volume 26, pp. 854-862, 2013.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. Advances in Neural Information Processing Systems, 34, 2021.
Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. PAC subset selection in stochastic multi-armed bandits. In International Conference on Machine Learning, volume 12, pp. 655-662, 2012.
Nikolai Karpov, Qin Zhang, and Yuan Zhou. Collaborative top distribution identifications with limited interaction. In IEEE Annual Symposium on Foundations of Computer Science, pp. 160- 171, 2020.
Julian Katz-Samuels, Lalit Jain, Kevin G Jamieson, et al. An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits. In Advances in Neural Information Processing Systems, volume 33, pp. 10371-10382, 2020.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identifica- tion in multi-armed bandit models. Journal of Machine Learning Research, 17(1):1-42, 2016.
Andreas Krause and Cheng Soon Ong. Contextual gaussian process bandit optimization. In Ad- vances Neural Information Processing Systems, pp. 2447-2455 2011.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics, 6(1):4-22, 1985.
Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. In International Conference on Artificial Intelligence and Statistics, pp. 6529- 6553. PMLR, 2022.
Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Communication efficient dis- tributed learning for kemeliizd contextual bandits. arXiv preprint arXiv:2206.0483 2022.
Zihan Li and Jonathan Scarlett. Gaussian process bandit optimization with few batches. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 92-107. PMLR, 2022.
Zhenhua Liu, Minghong Lin, Adam Wierman, Steven H Low, and Lachlan LH Andrew. Geographi- load balancing with renewables. ACM SIGMETRICS Performance Evaluation Review, 39(3): 62-66, 2011.
Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distribu- tions: A survey. Foundations of Computational Mathematics, 19(5): 1et:11145-1999 1190, 2019.
Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy gaussian process bandit optimization. In Conference on Learning Theory, pp. 1723-1742. PMLR, 2017.
Bernhard Schölkopf, Alexander Smola, Francis Bach, al. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning. 2010.
Liang Tang, Romer Rosales, Ajit Singh. and Deepak Agarwal. Automatic ad format selection via contextual bandits. Proceedings of the ACM International Conference on Information & Knowledge Management, pp. 1587-1594, 2013.

---

Published as a conference paper at ICLR 2023
Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification in linear bandits with linear di- mension dependency. In International Conference on Machine Learning, pp. 4p.7487-4888 PMLR, 2018.
Chao Tao, Qin Zhang, and Yuan Zhou, Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In IEEE Annual Symposium on Foundations of Computer Science, pp. 246, 2019.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294 1933.
Sattar Vakili, Nacime Bouziani, Sepehr Jalali, Alberto Bernacchia, and Da-shan Shiu. Optimal order simple regret for gaussian process bandits. Advances in Neural Information Processing Systems, 34:21202-2133 2021.
Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time analy- sis of kernelised contextual bandits. In Uncertainty in Artificial Intelligence, pp. 654-663, 2013.
Grace Wahba. Spline models for observational data. SIAM, 1990.
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near- optimal regret with efficient communication. In International Conference on Learning Represen- tations, 2019.
Leon Weninger, Qianyu Liu, and Dorit Merhof. Multi-task learning for brain tumor segmentation. In International MICCAI Brainlesion Workshop, pp. 327-337. Springer, 2019.
Bin Yan, Houwen Peng, Kan Wu, Dong Wang, Jianlong Fu, and Huchuan Lu. Lighttrack: Finding lightweight neural networks for object tracking via one-shot architecture search. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 15180-15189, 2021.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-based explo- ration. In International Conference Machine Learning, pp- 11492-11502. PMLR, 2020.
Yinglun Zhu, Dongruo Zhou, Ruoxi Jiang. Quanquan Gu, Rebecca Willett, and Robert Nowak. Pure exploration in kernel and neural bandits. Advances in Neural Information Processing Systems, 34, 2021.
Ling Zhuo Cho-Li Wang, and Francis C.M. Lau. Document replication and distribution in exten- sible geographically distributed web servers. Journal of Parallel and Distributed Computing, 63 (10):927-944, 2003.
12

---

Published as a conference paper at ICLR 2023
A APPENDIX
A MORE EXPERIMENTS
In this section, we give complete description of experimental setup, and present the results for the FB setting.
Experimental Setup. Our experiments are run on Intel Xeon E5-2660 v3 CPU at 2.60GHz. We set V 5, = 6, = 0.005 and 7 RR. where is a dimension parameter that will be specified later. We consider three different cases of task similarities, i..., rank = 1 (tasks are the same), tank(Kz). E (1, v) (tasks are similar), and rank Kz) = (tasks are totally different), to show how task similarities impact learning performance in practice.
For the rank(K2) = 11 case, we set d = 4. For any v E [V], {ő(T)) is the set of all (2) vectors in R where each vector has two entries 0 and two entries 1. For the rank(K2) E (1,V) case, we set d = 8. For any v E {1,2} and E {3, 4, 5). (Ø(i))aex. and (o(i)) are the two sets of all (*) vectors in the first and second subspaces R$ of the whole space FS, respectively, V case, we set
where each vector has two entries 0 and two entries 1. For the rank (z) d 20. For any v [V], {ő(ī))=E,, is the set of all (t) vectors in the v-th subspace IR of
the whole space TR:20, where each vector has two entries and two entries 1. For all cases, we set 0- = [0.1, 0.1 + Amin.... 0.1 + (d m)nmn] E Rd, where Amin is reward gap parameter that will be tuned in the experiments.
In the FC setting, we change the reward gap Amin E 0.81 to generate different instances, and run 50 independent simulations to plot the average sample complexity with 95% confidence intervals. In the FB setting, change the sample budget T [7000, 300000] obtain different instances, and perform 100 independent runs to report the average error probability across runs.
Results for the Fixed- Setting. In the FB setting (Figure 3), compare algorithm IndPeaceFB (Katz-Samuels et al., CoXernee1B-IndAlloo is ablation variant of CoKernelFB, where
CoKernelFB with three baselines, i.e., Cow.eneeFF-InnAlleeeee 2020) and IndUniformPi agents use locally optimal sample allocations, instead of a globally optimal sample allocation. IndPeaceFB and Samuels et al., 2020) and the uniform sampling strategy, to independently complete the V tasks, respectively.
formBB run V copies of existing single-agent algorithms, PeaceFB (Katz-
Figures 3(a), 3(b) show that, our CoKernelFB enjoys a lower error probability than the baselines. Moreover, the experimental results also reflect the influences of task similarities on learning speedup, and match our theoretical bounds. Specifically, from Figures 3(a) to 3(c), the error probability of CoKernelFB gets closer and closer to that the single-agent adaption IndPeaceFB, which shows that the learning speedup of CoKernelFB slows down as the task similarity decreases.
B RELATED WORK
In this section, we present complete review of related works.
Collaborative Pure Exploration (CoPE). The collaborative pure exploration literature is initiated by (Hillel et al., 2013). where all agents solve a common classic best arm identification problem. Hillel et al. (2013) design exed-coofidence algorithms based on majority vote and provides upper bound analysis. Tao et al. (2019) further develop a fixed-budget algorithm and complete the analysis of communication round-speedup lower bounds. Karpov et al. (2020) extend the best arm identifi- cation formulation of (Hillel et al., 2013; Tao et al., 2019) to best m arm identification, and show complexity separations between these two formulations. Our CoPE-KB generalizes prior CoPE works (Hillel et al., 2013; Tao et al., 2019; Karpov al., 2020) from single-task and classic MAB setting to allow multiple tasks and general reward structures, and faces unique challenges on com- munication and computation due to high (possibly infinite) dimensional feature space.
Kernel Bandits. For kernel bandits with the regret minimization objective, Srinivas et al. (2010)
and Valko al. (2013) design algorithms from Bayesian and frequentist perspectives, respectively.
13

---

Published as a conference paper at ICLR 2023
ColicmaiF (ours)
ColomaaFB (ouns)
Cotemmirt--ralee IndPeaceli
Codemaitt-irddllo IndReaceFa
Error Probabiitt
Error Probaliiity
Probabiiit
Coliomeiae lours)
induniformss
indhifforFa
Cokomelfa Indilioc
Indasacers
Insil Iedltere
23s 250 als
Budget
(a) FB, rank (K2) =1
(b) FB, rank K2) E (1,
(c) FB, rank K2) = V
Figure 3: Experimental results for CoPE-KB in the FB setting.
Chowdhury & Gopalan (2017) improve the regret bound in (Srinivas et al., 2010) by building new self-normalized concentration inequality for kernel bandits. Scarlett et al. (2017) develop re- gret lower bounds for the squared-exponential kernel and Matérn kernel, and Li & Scarlett (2022) establish a near-optimal regret upper bound. Krause Ong (2011); Deshmukh et al. (2017) study multi-task kernel bandits, which consider composite kernel constituted by two sub-kernels with respect to tasks and items. Dubey et al. (2020) investigate aulti-agent kernel bandits with a local communication protocol, where agents can immediately share the observed data with their neighbors in a network. Li et al. (2022) study distributed kernel bandits with a client-server communication protocol, where agents only communicate with central server. The communication costs in (Dubey et al., 2020; Li et al., 2022) depend on the total number of timesteps '" in the regret minimization game, while our communication costs depend only the number of arms in the pure exploration setting.
For kernel bandits with the pure exploration objective, there are only a few related works (Scarlett et al., 2017: Vakili et al., 2021; Camilleri et al., 2021; Zhu et al., 2021), and all of them study the single-agent formulation. Scarlett et (2017); Vakili al. (2021) consider the simple regret setting in pure exploration, where an agent reports an arm at each timestep and aims to minimize the suboptimality of the reported arm (simple regret) after timesteps. In contrast, Camilleri et al. (2021); Zhu et al. (2021) investigate the best arm identification setting in pure exploration, where an agent aims to identify the best arm and minimizes the number of samples used (our work also falls in the best arm identification line). Camilleri et al. (2021) propose robust inverse propensity score estimator to save the samples needed for rounding procedures. Zhu et al. (2021) use neural networks approximate nonlinear reward functions. The above kernel bandit works consider either the regret minimization or single-agent setting, which is different from our CoPE-KB problem and does not involve our challenges on round-speedup trade-off analysis and communication. Thus, these works cannot be applied to solve our problem.
Recently, there are several works which study dedtriated/distribueee bandits with the regret mini- mization objective. Wang et al. (2019) study distributed multi-armed and linear bandit problems, and He et al. (2022) investigate federated linear bandits with asynchronous communication. Wang et al. (2019): He et al. (2022); Dubey & Pentland (2020); Huang et al. (2021); Li & Wang (2022) de- velop algorithms for (low-dimensiona) federated linear bandits, where agents directly communicate the whole vectors of reward parameters. These works cannot be adapted to resolve our challenges, because under kernel representation, the reward parameter is high-dimensional and expensive to explicitly calculate or transmit.
C OMITTED DISCUSSION FOR ALGORITHM
C.1 ROUNDING PROCEDURE
In algorithms CoKernelFC and CoKerne1FB, we use a rounding procedure ROUND(E, X, N,e) (AI- gorithm 2 in (Camilleri al., 2021)). For any weighted sample allocation X E A Ag. regular-
ization parameter & and approximation parameter e, with N 2 7(S,A,8) 0 d(s.))
samples,
14

---

Published as a conference paper at ICLR 2023
ROUND(Ç. A, E) returns discrete sample allocation ($1....,,3N) E X such that 1 o(ē;) (NEII))
max R. E.
22 +6)
max X.
[ (6t (Aad(B)o(()T)) 1-
(6)
This rounding procedure requires the number of samples N to satisfy that N 2 =(E,
O O(" Here d(c, A) is the number of the eigenvalues of matrix Σiee (z) which are greater than ç. d({,, A) stands for the effective dimension of the feature space spanned by data projections of under regularization parameter, Ç.
C.2 KERNELIZED COMPUTATION ALGORITIM CoKernelFC
Kernelized Estimator. Below present derivation of our kernelized estimator (Eq. (3)), which plays an important role in boosting the communication and computation efficiency.
Let 0, denote the minimizer of the following regularized least square loss function:
(r
(())
51001 + Σ (U (68))
==1
Letting the derivative of [()) equal to zero, we have
N(r)
N
N + Σ (()))
Σ o(z))us
Merging repetitive computations for the same arms, we can obtain
aV N N( 0 N.
g +
where !,!r) is the number of samples and "!") is the average observation on arm 2, for any i E [nV].
Let D, 1V N (( V V ((Tv)) J. k = 2, = -V/N NY" k(ū,,
A and g(() = IV (0 (r) (rr) (T) Then, we can write Eq. (7)
(NTI)TT क. 8, 0, -..
Since (N(1) T.7 x.) x 0 and (NT()) + 2,0,)) > 0.
0, = (NiM)E + 2, 2, (1y
= (N 2, (())
क. (NNM)T+ y(())
Let kū) (,)(ū) = IV N k(1, (I,, VN (Z, for any I E X. Then, for any arms ž,, ē, X, we obtain the efficient kernelized estimators of the expected reward F(ā.) and expected reward gap F(ū;) - F(ū;) as
f.(ā.) ((.)) = kx)) (v g(r))
Á, = (k, (2,, k, k,,)))
(ym))I++K0 g((t)
Kernelized Optimization Solver. Following (Camilleri al.. 2021). we kernelized optimiza- tion solver for the min-max optimization in Line 4 of Algorithm 1. The optimization problem is as follows.
min x
max
[Ø(ā,) o(t,) ((
(8)
B .E[[]]
15

---

Published as a conference paper at ICLR 2023
where A(S, := &I + EBer (z)()))(2) for any 2 0 and X E Ax- Define function h(A) optimal solution of h()). Then, the gradient of h()) with respect to is
max
l ((ē, (( 1I and define (1), (2) as the
"; .ME[V]
<V)((A]== = ((((( ((2
A(C.A) "0()) vB E X.
(9)
Next, we show how to efficiently compute gradient [V x/(()]2 with kernel function k(--)). Since (EI + bx) o(z)
= (0(8)
any ă X, we have
<(z) = (5T (()) (ET + + xx) $ (2) ((
= ( + x (5I + k,))~
Multiplying (A) - o(z3(A))) on both sides, we have
-1)6((A)))(((((0)) 6()) =E(((E((A) - -(E)(A))) (EI + 2T4x)) 6(σ)
(A)((E((A) RA(E((A)) (EI +K)
Then,
(o(E)(A)) - (A)) (51 ((1+0) xxxx - o(F)
-E- (o(E((A) 6(8) -E- (kx (A)) - (x((()))
T (EI KX) (x)
-
- (bx(E - (((((()))) (E/ KA)+
(10)
Therefore, we can compute gradient (A) (Eq. (9)) using the equivalent kernelized expression Eq. (10), and then the optimization (Eq. (8)) can be efficiently solved by projected gradient descent.
C.3 COMPARISON OF ESTIMATORS
In the following, we compare our kemeliizd estimator (Eq. (3)) those in prior kernel bandit works (Zhou et al., 2020; Zhu et al., 2021; Dubey et al., 2020; Camilleri et al., 2021) and adaptions of federated linear bandits (Dubey & Pentland, 2020; Huang et al., 2021: & Wang. 2022).
First, prior kernel bandit works (Zhou et al., 2020; Zhu et al., 2021) or adaptions of federated linear bandits (Dubey & Pentland, 2020; Huang al., 2021; Li Wang, 2022) explicitly maintain the regularized least square estimator of reward parameter 6* as
((r
A(r)
0, (N(()) Σ (0(3))033
Σ
(11)
Since both O, and (3,)) lie in the high-dimensional feature space H. this estimator will incur (dim(H)) computation and communication costs.
Second, (Dubey et al., 2020) and Algorithm 6 in (Camilleri et al., 2021) use a redundant kernelized form of 0, as
0, (v T -
where V = [T; :(3 (() )
E R xdim(()) xddim(1)) Y = [yl..... UNce] E RX and
.1.... VNG. are the observed raw outcomes of sample sequence (31,..., 8N0) ). This estimator
needs all (r) raw sample outcomes y1,..-: My(rr inputs, rather than only nV average outcomes o(" ....,.., V as our estimator (Eq. (2)). which will incur a O(N(r)) communication cost. Here the number of samples (rr) is often far larger than the number of arms nVV.
Finally, Algorithm 4 in (Camilleri et al., 2021) adopts a robust inverse propensity score estimator as (o(2.) - ((2x)) Wi
0, = arginin
max
By EB!" v
[ ((xr) A[(
16

---

Published as a conference paper at ICLR 2023
Algorithm 2 Collaborative Multi-agent Algorithm CokernelFB: for Agent E [V]
1: Input: regularization parameter
S 18(149)((((())11 per-agent budget T 2 max(p" (()(() d(G.AT)) log(w({, arm set X' which satisfies w(S, ( Ø}) 2 for all i e
X { and [V] k((,,) X X + R. rounding procedure ROUND, rounding approxi-
mation parameter 10
2: Initialization: R (wogg(((E, ) N < [TV/R]. B < Ry for all o' &..r "
pre-determine the number rounds and samples
3: while S R and Be' E [V], > do
4: Let X, and Pr be the optimal solution and optimal value of [|o(ā;) Φ(T;) ((2)))le )=
max XEAx ",,
min
// compute the optimal
sample allocation
5:
52) ($1....,
< ROUND(E, Xr =)
6: Extract a sub-sequence 5(r) from ($1,..., By) which only contains arms in X
7: Sample a(*) and observe random rewards yo
8: Broadcast {(N()) v, glr)) hie(a) and receive {(v(r) o F. ( from all other agents o' e
\ {v}
9:
for all u [V] do
10:
8 (.) + (,) + -( for all E B // estimate the rewards of alive
Sort all ā E B by (T) in decreasing order, and denote the sorted sequence by ((I) (()).....((1())))) (1B7))
11:
Let i1 be the largest index such that w(E, ( w(E, B g(++1) {ă().--. {
13:
// cut down the alive arm to half dimension
14: end for
15: r +1
16:
end while
return B ...... B47)
Whs =
((o(tt)) ( b(xx)) (( (:) (,,))))))(()))))))))) -6 f=1
N00)
for any 2 0 and À E A X is the optimal sample allocation defined in Line 4 of algorithm CoKernelFC (Algorithm 1). ji(-) is the median-of-means estimator Catoni's estimator (Lugosi & Mendelson, 2019). This estimator also requires all (r)) raw sample outcomes V/1 . Mytr), and will cause O(N()) communication cost.
Here := = =T + (T EEE \ed())(()
C.4 PSEUDO-CODE AND DESCRIPTION OF ALGORITIIM CoKernelFB
In this section, present the algorithm pseudo-code of CoKerne1FB (in Algorithm 2), and give detailed algorithm description.
The procedure of CoKernelFB is follows. During initialization (Line 2), pre-determine the number of rounds and the number of samples for each round according to data dimension ((5.A)) which is formally defined as
w(E, S) = min max XE E.EE
0( -
VŠC
where A(E,A) == 51 + + EeEe A w(E, 5) represents the principle dimension of data projections in S the RKHS under regularization parameter ç. Each agent v maintains alive sets B(7) for all agents E [V], and calculates a global optimal sample allocation X; (Line 4). Then, she generates sample sequence (5(*) s(t)) according A;, and selects the sub-sequence s(r) that only contains her available arms to perform sampling (Lines 5,6). Similar to CoKernelFC, she only communicates the number of samples ((() and average observed reward y.(r) for each arm S.,
17

---

Published as a conference paper at ICLR 2023
with other agents (Line 8). With the shared information, she estimates rewards of alive arms and only keeps the best half of them in the dimension sense (Lines 10-13).
Regarding the conditions the input parameters (Line 1), the condition regularization param- eter & implies that CoKernelFC needs a small regularization parameter such that the bias due to regularization is small. Such conditions et al., 2021), and can be dropped in the extended PAC setting (allowing a gap between the identi- fied best arm and true best arm). The condition T to ensure that the given sample budget is larger than the number of samples required by rounding procedure ROUND. In addition, the condi- tion on w(: -) is to guarantee that the number of rounds is bounded by O(log(w({, X))) rather than an uncontrollable variable. Such conditions are also needed by prior fixed-budget pure exploration algorithm (Katz-Samuels et al., 2020).
similarly needed in prior kernel bandit work (Camilleri
Communication and Computation. CoKernelFB also adopts the kemeliizd estimator in Sec- tion 4.2 to estimate the rewards of alive arms (Line 10). Specifically, using Eq. (2), we can estimate the reward for arm ă by
- - = = - (NTW)T k((1) "00))
(12)
where g(r) = IV NI Vi
k(T By Masejar and N NIVVVV K(r) = WN A
(b) = [v N k(,,
N M(S (!V are the average outcomes, kernel matrix and arms.
correlations of the nV arms, respectively, which merge repetitive information
Using the kernelized estimator (Eq. (12)), CoKernelFB only requires a (nV) communication cost, instead of ((N()) or ((dim(H)) as in adaptions of existing single-agent algorithm -Katz-Samuels et al., 2020).
D PROOFS FOR THE FIXED-CONFIDENCE SETTING
D.1 PROOF OF THBOREM 1
Our proof of Theorem adapts the analytical procedure of (Fiez et al., 2019; Katz-Samuels al., 2020) to the multi aulti-agent setting.
Let r* [log2 Amin algorithm CoKernelFC. For any E A let ox := [V))1 ;...; V denotes the weight allocated to arm 2; for any E [n.]] For any & 0 and X E g, A(5,
21+ 1++ 1. Intuitively, r" is the upper bound of the number of rounds used by where A
ÇT Exeg (=d(T)o(E)T ET T T
The regularization parameter in algorithm CoKernelFG satisfies V max a, e [lő(T;) Amin ((E)))a((A>))- I 32(1+e]]001I Since max, "5.,,,B!" ee(vv] llo(2.) (( is non-
increasing with respect to (from Line 4 in algorithm CoKerne1FC), we have 2(1 + e) max, ",a, " [lœ(ū:) ( [|0*|] < Amin S श for any S S r. 16
.v[[v] In order to prove Theorem first introduce several important lemmas.
Lemma (Concentration). Defining event
|lØ(ū,) - -((;)) -( g { (f)(t)))P(((3) Fr(2,) - -F(,)) < < -
/220gg (2o (2n2V/8p) + VE100112 22" Vū, E B,), Vo [V], 1A vIsrSr ((r)
have
Pr[g] 1 8-8.
18

---

Published as a conference paper at ICLR 2023
Proof of Lemma 1. Let 7r N Recall that 0, (7. + Φ Φ.)
$ g(() v,
Iv [/N]] N ((01) ; NaV NnVo(EnV)] and أا = N yl.) 1..11 N UT.... Let 17(r) I
N nnv where Th v. o(T.) l denotes the average
noise the n!!) samples on arm Σ; for any E [na].
Then, for any fixed round 1 1 G. E B and [V] we have
(fr(2:)) (2)) -
= =(((f) - ((,))) 0,-00)
= (d(T)) - o(;)))
((7 + 21 -1
4 g() 00)
(0(#:) ((,)))
1, T 0 + -((-²) -0-)
(Ó(T:) o(E,))
0, 0,000 + (n + 4, 0,) -1 0 0, -0))
(o(3)) o(t,)) (6 0, 2,)
(0. + +x1) 0r (7 2.) 2,) -1 1,111111
0r 7 (7 + D (,) (000))00)) 0r)
-(((i)) - )( T (7/1 + 2 2,)
11 yr (b(ā.) ((ā,)) T (711 + 22) 1 0 0r (13)
Tomm
In Eq. (13), the expectation of Term is zero, and the variance of Term is bounded by
(Ó(ī.) o(ū,)) + (,,1+0, 2.) $, dr (7ed + $- 2.) (Ø(T.) c(ī,))
s (6(G.) o(;,)) (7, - 0, (7, + क, (7, I + Φ Φ,)) -1 (o(7.) - (((,)))((7,))
= -(( )(t,)) (7pl + +,,
-
=11o(0,) <(2,) 1+0,7 ( o,))
Using the Hoeffding inequality, we have that with probability at least 1 6
n²
2n?V
( ((ū,)) (7/1 + 2,) 2. ,,
< |lo((,) (1T log
6,
(14)
Thus, taking the absolute value on both sides of Eq. (13) and using Eq. (14) and the Cauchy-Schwarz inequality, have that for any fixed round S S r" 3o, 3. BB(") and u E [V], with probability least 1 V (f.( f.(1,) - (F(ã.) (F((, -
F(i,)) -F(,))
2n²V
<[(o(ā;) - c(T,), (l (7.14000 2 2og
8,
+xrll((a;) - (( (0 |10
2n
<11Ø(z:) - o( (7
2
) + (1ā(ā))
8r
2(1 + e) ||((;:) - (5 (6 0x))
1nnV
2log
(N)
5,
2(1 +) ((((a)) o(2 -(E)))ler+ P1
110
VN
19

---

Published as a conference paper at ICLR 2023
=2(1 - 0x:) /
2 log (2n2V/6,)
N(r)
+1(1 E) /Elo((E)) ((3, ((8)))l(7+003 )xp) 1100|1
2 log (2n2V/8,)
<2 6)
max
||+(;:) -( ox:)
N(r)
EB .e(V)
+ 2(1 B\
max eE(V]
|Ó(ā,) - cb
| 1|2
where (a) follows from the guarantee of rounding procedure (Eq. (6)) and y= N(r)g.
According to the condition of ç. holds that
2(1 + E)VE
max l1ó(ã.)) - -((2 (2HHTT,.::) -110011 S 2r+1 [
Thus, with probability at least
6,
niV-
(o)) - F,
2 log (2n² V/6))
1
2( +
R. C.. ME[V]
max
[(((²)) - ( -( 011)
N(r)
2
8(1 + <)²p; pt log (\n)
+ 2
N(r)
+
2r+1
2r+1
1
2"
By a union bound over arms ā,, Ty. agent and round r, we have that
Pr [ 2 6.
For any 1 < S and v E [et, s(" E F( F()) 24.2"
Lemma 2. Assume that event occurs. Then, for any round 1 < r" and agent u E [V. have that T.,+ E B(r)) and Blx)) s!r
Proof of Lemma 2. We prove the first statement by induction.
To begin, for any u E [V], T..-- E EB. trivially holds.
Suppose that Te,x B!r)) (1 < S rT) holds for any u E [V), and there exists some v' E [V] such that 2 & g(r+1), According to the elimination rule of algorithm CoKernelFC, we have that these y exists some E B(()) such that
(x(3') F,,
Using Lemma 1, we have
((G))-((E))) -. - 0,
which contradicts the definition of ボ.., Thus, we have that for any v E [V). Sr.a E B(++1), which completes the proof of the first statement.
Now, we prove the second statement also by induction.
To begin, we prove that for any E [V], B(?) C cs! Suppose that there exists some v' E [V] such that B(2) Ç s(2) Then, there exists some 7' E B(2) such that F( F (3') 2 Using
Lemma 1, we have that at the round r = 1,
(,(,,)) F,(3') Z F(ī;) F(F) 2 1- -
which implies that 3' should have been eliminated in round 1 and gives contradiction.
20

---

Published as a conference paper at ICLR 2023
Suppose that D.d
(1) (1 <rrr)) holds for any v [V], and there exists some v' [V]
such that (+++) & of
s(++1) Then, there exists some E of
B such that F( F( >
4 2-2- (r+1) = --.2 Using Lemma 1, we have that at the round r, ( - (,)) F( F(7') - 2- -2"
which implies that H' should have been eliminated round r and gives contradiction. Thus, we complete the proof of Lemma 2.
Now prove Theorem 1.
Proof of Theorem I. Assume that event G occurs.
We first prove the correctness.
Recall that r* == [log2( ( Ami. 21 + 1. According to Lemma 2, for any 17 E [V] and I E B
+1)
we mino and thus B 411' = (T.,.). ). Therefore, algorithm CoKernelFC will return the correct answer Tn,. for all e E [V] and use at most r* == [logo( --m + rounds.
have F( Fă) 4 2-22-00 (1*+1) 2 ((1o82(22m) 11+1) 2 2 loga (
+1)
Next, we prove the sample complexity.
In algorithm CoKernelFC, the computation of X, P7 and N(r) is the same for agents, and each agent v just generates partial samples that belong to her arm set & from the total N(r) samples. Thus, to bound the overall sample complexity, it suffices to bound Σ N(r, and then we can obtain the per-agent sample complexity by dividing V.
1 Let E 10. Then, we have
N6)
2nn²V
32(2")²(1 (1++1)))2) (1("")((++))) log
+1 +1 +1+ (5,)))
5,
32(2")² (4.271) (1 s) minxeA, max m
2, EB we([] (1)(#.) - (((;)) (((e
(4.2-))²
2
log
+ + 2T,E,, xi
8
minxEA& max, 2, EB NE(V] (1(().) ((T,)) ((
log (4
512(1 + +
(-r2-))²
8
+ Ni + +T E)
minxe max se Man. J.veLy [1o(Te,)) ( - ((
2048(1 + E)²
2-r2-
1 (Vn2(19))))
log
+ Ni + 27(E,
8
- (I (1
log 4V
2048(1 E)²
min x
max
(a..
(F(t F()))2
8
+ N2 + 27(5, x1.5) .
[|0(ār,)) - - log (F( F(ū))²
4Vn2(r+))
2048(1 + min
max xE Be M............. MEE
Nj + 27(E, 1)
21

---

Published as a conference paper at ICLR 2023
Sr' (2048(1 + =)²² (E) log (4Vn + N1 + E) .r
=0 -0 (5) log Ami
log
Vn 8
+ log log Amin
+ dd(ss log A min
Thus, the per-agent sample complexity is bounded by
p pS(() (5)
Vn 8
dis, Ai)
o
A..
log
+ log log
A-1 min
log min
V
V
Since algorithm CoKernelFC has at most r" = [log2( Amin nication rounds is bounded by (log Amia)
) + 1 rounds, the number of commu-
D.2 INTERPRETATION OF THEOREM
Proof of Corollary 1. Recall that for any A E x. Q2 iVTi((n)) ;...; (nvo(Env) and
Ky = IA,zjk((;, [e)[]] argmaxXEa log det (T + 5- {1) For any 2 O and a E Ax- A(S,)) = ET + EieX (2)())0(;) ET T
DxØX. Let X = argmax log det (I + Kx) =
Then, have
[T( - x(T) 12
(5 A, ((
(²(() min
xEA & A (
(F(te,) -
[(( - -03)
(e1+ (( dg (((())))))))
< min max x VVV...EEV]
A2 min
A2 min
max A DE
min
10(TT,,) - Eewaatattr
<
min
2 max || (E1+ Erex-EEex>>eee we BER
A2
min
x
min max [0(2)11
A
min
x &E
4
max [|{ #EX
2
(Er EEER (F3))11))
4
Σ {1 (g1+
A2 min
BEA
where (b) is due to Lemma 3.
Since {1
S for any X,
(EI+) Eslex X3 ((
Σ {=
<2 Σ log (1+
(
(ETH 1)
(e)
det (CT+EBeA {;
52
det (E!)
-2g det
I+5-1 Σ {
REA
=2 det (1+ 22)
=2 log det
(1+
22

---

Published as a conference paper at ICLR 2023
=2 log det (I + 5- (I+
where (c) comes from Lemma Thus, we have
8
(E(
S
log det (xx)-
(15)
A min
In the following, interpret the term log det (T Kx-) by maximum information gain and effective dimension, and then decompose it into components from task similarities and arm features.
Maximum Information Gain, Recall that the maximum information is defined
T = max log det (I + (-1 = log det (I + +x=x-xx) x
Then, using Eq. (15), we have
8
(5) S
r.
(16)
A2 min
Combining the bound in Theorem 1 and Eq. (16), the per-agent sample complexity is bounded by
s=0
p
(E)
log A
mia
log
Vn
+ log log A A-1
+
d(c, Ai)
loog A
-1 min
min
r
Vn
d(s, A1)
=0
log A
log
log log A min
log A Amin
A min
min
V
Effective Dimension. Recall that 01 2 ... 2 enV denote the eigenvalues of Kx- in decreasing order, and the effective dimension is defined
nV Σ ai i=jt1
dar = min j jE (flog(nV) 2
Then, it holds that deng (og(n))> > 2i=dort1 ag.
EnV
Let = deng log(nV) Ei=da+1 Oi and thus S detr log(nV). Then, we have Ede 0i Trace(Kx-) 2izda+1 a4 Trace(Kx-) log(nV) and Eav
Li=da+1 dene log(nV)-
log det (1+5- Kx-)
llog (112 (1 (1+
=log
(TT/er (1 + tas)) m (1 +1+5 (1+5
(1+5-1 Trace(Kx-) dont log(n1 v + day
donE log(nV) - -V- nV dest
s log
1 1
der
1 Trace(Kx-) done log(n)) +
+ +log (1+ derr log(nV)
Edet log
dell
nV - dell
1 Trace(Kx-) dont log(nV) +E
ddlr log
dell
1 der log(nV det dott) nV - dell
dd
log
(d)
1 Trace(Kx-) dont (og(())) +
+ log (1 (1 der log(nV + dea) av nV
<dee log
dell
1+ Trace(Kx.) done log(nV) +
+ nV log (I+ deet log( + doft)
deff log
dem
nV
1 Trace(Kx.) + detr log(nV den)
<det log
Edent
23

---

Published as a conference paper at ICLR 2023
Sdet log 2nV (1+ Trace(Kx.)
))
Edem
where inequality (d) due to that (1 dar log(x+
is monotonically increasing with respect to
2 1.
Then, using Eq. (15), we have
8 denr log 2nV (1+
Trace(Kx-)
p (5) S
(17)
A min
Eden
Combining the bound in Theorem I and Eq. (17), the per-agent sample complexity is bounded by
p (E(()
(Igg
Vn
d(s. Ai)
S =0
V
log
A Amia
+ log log A
+
V
log A
min
detf
log nV (1+
Trace(Kx-)) ))
[log
Vn
log A
log log A min
A
V
Edem
min
ä(C, x1) V
+
llog A
I/AAz3h(T "y)a,,,)) Kz = [kiz (e. and Kx AxXxtxx (. ky]lkse[nv]- Let K2 = [kz (Ze,s Zu, II..E[mV]. where for any E [nV]] 2 denotes the index of the task for the i-th arm ã; in the arm set X and zuz denotes its task feature. It holds that rank(K2)
Decomposition. Recall that Kx-
rank(Kz).
Since Kx- is Hadamard composition of K and Kx we have that rank ( rank(Kz)
rank Kx,x-) = rank rank(Kz) rank(Kxx,y
log det (1+5- k
log
(1 (1 + 5 f=a=):))
[T (x+) (1 + 5-5
log
Drank((xx )
(1 (1 (1+5-ta))
rank(Kx-)
2i=1
<
log
rank rank(Kx.)
Li=l Drank(Kx) (xx))
(1+5-
-rank(Kx² log
rank rank(Kx.)
Trace (I + 5-1
Srank(K2) rank(Kxx))log
rank Kx.)
Then, using Eq. (15), we have
8
Trace (I+5-1KA) rank Kx-)
0² (E) <
rrak (Kz) rank rank(Kx,x-) log
(18)
2
min
Combining the bound in Theorem 1 and Eq. (18), the per-agent sample complexity is bounded by
p (E)
Vn )
d(E, Ai) log A
o
log Ami log
+ log log Ami
rank K2) rank K xx
Trace (I + + ---KKxx)
log
12 V
rank rank(Kx.)
24

---

Published as a conference paper at ICLR 2023
Vn
d(E, At)
log A
log
log log A1 min
llog
A1 min
min
8
V
Hence, we complete the proof of Corollary 1.
E PROOFS FOR THE FIXED-BUDGET SETTING
E. PROOF THEOREM
Proof of Theorem 2. Our proof of Theorem 2 adaptt the error probability analysis in (Katz-Samuels et al., 2020) to the multi-agent setting.
Since the number of samples used over agents in each round is N [TV/R]. the total number of samples used by algorithm CoKernelFB is at most TV and the total number of samples used per agent at most T.
Now we prove the error probability upper bound.
Recall that for any ç 2 and A. A(E, == EI +I+EEER {ao()) EI 8x For any E xx X = Ivii((ā)) T ;...: : (nvvl(āv)"] The regularization parameter & in algorithm CoKernelFB satisfies & & 160+))2(00 11)
For any r E [R], L R. E B and [V], define reward gap [Ø(ū,) ((8, )|/g) 0xp)-1 S 88p'(E) )
A A,a,, inf A>0
and event
Jr. = -f(((())))((())))))) (F( F(i,)) < Areuzi)
the following, we prove Pr [-, S 2exp 32(1+))0'(E)
Similar to the analysis for Eq. (13) in the proof of Lemma have that for any r E [R] 5r, 3j
B and E [V], (Fr())) - Fr(ā,)) (F(6.) F(2)))
-((,)))(āū))) (NET 8. 2,) TTT,7'
EN (ó(G,) (i,))) (NET +0, 0,)) 0"
Term
Term 2
(19)
Here, the expectation of Term in Eq. (19) is zero, and the variance of Term is bounded by 2(1 e) (| -6 xxp)
( o(;;)11 ([N
0.)
where (a) comes from the guarantee of rounding procedure (Eq. (6)).
Using the Hoeffding incquality, have
Pr (o(EE) o(t,))) (NEI + $7 (,)
$ (())))
2 A Ar
1
A <2exp -2 2(1+)). (0(.)) 0 (EE 0A=)~
N 2(1+e))((0()))013
<2exp
(cr+ 222)=1
25

---

Published as a conference paper at ICLR 2023
N 32(11 + s)p² (5)
exp
Thus, with probability at least 2exp
N
have
33((1+))p'G (5)
(d(T))) -(ī,)) _ (NEI D,- 2r)
< 2 -
(20)
Since satisfies S (6(14))((()))]11)) p we have 4(1 (E) S 1. Then, for any
r E [10] T., T. E B and v E [V], we have
|o(ā;)) ((ā,)) ([ ||0 s 1,
4(1 4(1+E)
Aniin
and thus,
2(1 (1++)\Ello(a))) (( -0
5 D 2,
Then, bound the bias term (Term 2 in Eq (19))
EN (Ó(E.) - o(,,)) (NE + 11))
SENIlO(E,)
(NCI+
SVEN |1o(#.) - (N())))) 1100
2(1 c) 10(6,) ( T4p 4x21
SVEN-
110*11
VN
-2(1 + +)) - Abs 0x;) =100|12
2 -5
(21)
Plugging Eqs. (20) and (21) into Eq. (19). we have that with probability at least
2 exp 32(1+z)) (E) for any E [R], D., T. E Blr)) and v E [V]
(B.) P. (F(i:) ( F(ž,))
< (M(1:) - ((;,)) (NET + 0. (,) -1 क, m/( + EN (d(a.) - o(ū,))) (NET + 0,) '00
<A T,
which completes the proof of Pr [-Jr, s 2exp
(2cxp(-001t N Drrund Vē, B Ye e Vr [R]]
33(1++)00
Define event
J
-F())
By union bound over ā;, 3; E BB"), E [V] and r E [/]]. we have
Let To
N
Pr(-J] Von"V 8)) exp
32(1 E))*t)
(-
TV
=o 1 (og(((((E))) exp
(*(E) log(w(E, x))
In order to prove Theorem 2, it suffices to prove that conditioning event J, algorithm CoKernelFB returns the correct answers ž,, for all v E [V].
Suppose that there exist some [R]] and some [V] such that ã.,. is eliminated in round Define
B((r)= = (6 B(rr) (. F((,.))),
26

---

Published as a conference paper at ICLR 2023
which denotes the set of arms in B which are ranked before T.., according the estimated rewards. According to the elimination rule (Line 12 in Algorithm 2), we have
w(E, [Te,+) 1)
2 w(,, B 2 E.
max (lØ(#,) -( 0xx+)
(22)
Define Øp = argmax B As. We have
|6 <(
(E1+ )xp))
1
xp
A
20
((((3,) (T,)
(EI
1 #xp)
max
A
kg
(5. (r(") 1 U (Tv,+))
A
((((;,) 6(;,))1 ((HH))T)TTT)) (61+0T0.)
113
max XEAX &, EE
min
20
( (())11 (ET4.0
(0) min max Y S
A -0(i)|?
[
(cI+0T
<4 min xEAR ae Me..M...
max
A
(E),
where (a) follows from Eq. (22), (b) comes from the definition of w(: and (c) due to the definition of žo- According to the definition
[1((ū),)) - -( (E400) (xp)- S (8)
Ar.
inf A5D
A
we have .5 S Azo-
Conditioning on J, we have ( (fr()))))) (((((,,,)-P((()))) (F(ā...) F(To))
Ar Aão
Then, we have
- > (F(āu.)) - F(žo)) - A.o =0,
which contradicts the definition of To that satisfies (io)) > (Z,,..)) Thus. for any round r E [R] and task v [V]. S.... will never be eliminated.
for any E & \ ( E [V] and R (wg 8))1 Z (wg. for any E [V], we have that conditioning on J. algorithm CoKernelFB will return the correct answers ã., for all [V] using most R rounds. Therefore, we complete the proof of the error probability guarantee.
Since w(E, { +)
For communication rounds, since algorithm CoKernelFB has at most R = (wog)(w(E, rounds, the number of communication rounds is bounded by ((l)(w(({.)))).
E.2 INTERPRETATION OF THEOREM 2
In the following, we interpret the error probability for algorithm CoKerne1FB with maximum infor- mation gain and effective dimension, and decompose it into two parts with respect to task similarities and arm features.
27

---

Published as a conference paper at ICLR 2023
Corollary 2. The error probability of algorithhm CoKerne1FC, denoted by Err, also be bounded as follows:
(a) Err =0 -(exp)
TVA
min
n log(w((,
where T is the maximum information gain.
TVA2 min
(b) Err =0 exp
n nn²V InV1og((w((
dett log nV (1+
Trace Kx+) Şdat
log(w((,:))
where dent the effective dimension.
o exp
TV TVA: min
(c) Err
rank((z)) rank (x,x)) log Trace(--g-1KK- log(w(s, ())
rank( Rx-)
n n'Viog(w((,, (2)1
Corollaries (bb bound the error probability by maximum information gain and effective dimen- sion, respectively, which capture essential structures tasks and arm features and only depend on the effective dimension of kernel space.
Corollary 2(c) reveals how task similarities impact the error probability performance. Specifically, when tasks the same, i.c., rank(Kz) L, the error probability enjoys exponential decay fac- tor of compared to single-agent algorithm (Katz-Sama Saatz-ss et al., 2020), and achieves the maximum V V-speedup. Conversely, when tasks totally different, i.e., rank K V, the error probability similar to single-agent results (Katz-Samuels et al., 2020), since in this case information sharing brings no benefit.
Proof of Corollary 2. Recall that X == argmaxXed,
det (T+ (+---1K))
Recalling Eq. (15), we have
8 log det (1+5-
(E)
<
A min
Maximum Information Gain. Recall that the maximum information gain over all sample allocation E Ag is defined as
r max log det (I + ++(-kk)) log det (I (-+--1
AEA
Recall Eq (16), we have
8
p² (E) S
r.
2
min
Combining the bound in Theorem 2 and the above equation, the error probability is bounded by
TV
Err =0 n log(wW(, R)) exp
(²(E) log(w(E, (E)
TVA2 T Iog(w(E,
-0 n' log R)) exp
Effective Dimension. Recall that an ... anv denote the eigenvalues of Kx- in decreasing order. The effective dimension of K2- is defined as
dett min { log(n))) >
vV
Σ a 1=1+1
28

---

Published as a conference paper at ICLR 2023
Recalling Eq. (17), we have
8
(1+
Trace(Kx-))
(c)
derr log 2nV
A
Edea
Combining the bound Theorem 2 and the above equation, the error probability bounded by Err =0 2 Vogg(w((,))) exp
TV
x2))
(E) log(w((,
TVA min
n² noVlog(w(E,))) exp =0
dett log nVV. (1+
Trace(
log((W(s
Eder
Decomposition. Recall that Kx- (x, Hylasttu K2 [kz(zes Zet (o, and Kx,x- [VAA25 (B, By JE)])) Let K = [Rz (Zn. Ze, Me.ee/nr. where for any E [nV], U denotes the index of the task for the i-th arm ã; in the arm set and zu; denotes its task feature. holds that rank K 2) = rank(K2)
Since Xx- is Hadamard composition of K2 and Kx,,, we have that rank(Kx-) S rank(K2) rank( xx rank (z) rank(Kx xx,x)..
Recalling Eq. (18), we have
8 AZ rank(K rank(Kx,x) log
Trace (1 1
p (5) S
rank(Kx-)
Combining the bound in Theorem 2 and the above equation, the error probability bounded by Err =0
n² n (o exp (-
p*(E) log(w(E, )
TV
n 2 VVog(w((.
TVA2 min
exp
rank(K3) rank (a,,(Kxx..) log
Trace(I+E -Kx-)) rank(K
log((w(( (E))
Therefore, we complete the proof of Corollary 2.
F TECHNICAL TOOLS
In this section, we provide some useful technical tools.
(Camilleri al., argmaxxea x log det ( Ever (z we have
Lemma 3 (Lemma 15
2021)). For x
max 1 BEX
(EIt (22))))()) = Σ (bllo())
(er+ Exee (ere (22100E))))
SEA
Lemma 4. For X+ argmax X log det (I ( EEEE de 0z ((2")(((')) we have
det (5T ++++Een ΣEER {= det (ET)
Σ RE
log (+ Xgllo(t))]1 (c1- ((
Exve (c-E (200116777)))
log
Proof of Lemma 4. This proof is inspired by Lemma 11 in Labbasi-Yadkood et al., 2011), and uses a similar analytical procedure as that of Lemma 16 in (Camilleri et al., 2021). However, different from the analysis of Lemma 16 (Camilleri et al., 2021), do not include the number of samples NO) in the det(-) operator in this proof.
29

---

Published as a conference paper at ICLR 2023
For any j [nV], let Ad, = det ($1 EiErl (=o(E))((a))))
del
+I Σ 130(8)((3))
REd
Σ No(aE))(EE) + Nivellnn)llénn
= det {1
iE(nV-11
(1+ 1 (MTt
det (Mnv-1) det
dde (Mnv det
Nhiv ((ānv) M
det (M (1 + ( .)
aV
dde (EI)
II (1+77
i=1
Thus,
det (ET E Ezet (
aV
II 1 (11110(()))33
del (E!)
i=1
Taking logarithm on both sides, we have
det (E1 Lãee {zo(z)o(i) T)
log
det (E!)
nV
log (1 + (1
1=1
nV
log (1 + 111
3m1
which completes the proof of Lemma
30


Reviews:
[{"review_id": "N9UKCHyONMB", "reviewer": "Reviewer_D4Wd", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper the authors study collaborative exploration in kernel bandits. This problem is very general, and it generalizes a lot of works done in collaborative exploration. Due to the use of kernel, which allows non-linear structure of arms, it generalizes the works done on collaborative exploration in MAB and in linear bandits. Moreover, this work allows agents to collaborate on different tasks: the set of arms and the best arm are not necessary the same for each agent, as well as the features of arms.\nThe authors study the both exploration problems: fixed confidence and fixed budget. They propose and analyze an algorithm for each problem setting. They notably prove near optimal sample complexity and a near optimal number of communication rounds in the fixed confidence setting. Last but not least for the confidence setting, they provide a lower bound of the near optimal number of communication rounds that generalizes (Tao et al 2019) to structured rewards. Finally the same job is done for the fixed budget setting.\n", "summary_of_the_review": "It is a theoretical paper that generalizes some well-known problems and results. The paper is quite hard to read. The authors could help a little bit more the reader. That being said, I clearly vote for its acceptance.\n\n________________________\nI read the rebuttal and I thank the authors for their answers.", "strength_and_weaknesses": "The studied problem is very general. The paper is technically sound. The analytical results are convincing.\n\nThe paper is quite difficult to read. This is largely due to the complexity of the studied problem. \nHowever, sometimes some notations are not well introduced. This complicates the task of the reader. For instance at the end of page 2 \\tilde{X} is the set of arms, while in page 3 X_v is also the set of arms for agent v. The reader learns at the end of page 3, what is the difference between \\tilde{X} and X, \\tilde{X} = Z x X, where Z is the task feature space…\nIn Algorithm 1, the authors should emphasizes that t is not the standard time index, but the index of communication rounds. May be by simply writing line 3, for round r = 1,2,… do, could help the reader to understand the algorithm.\n\nThis paper has a lot of results, including some experiments, but only the analysis of fixed confidence exploration problem is in the main paper, without any experiment. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ISZ-jesDm7V", "reviewer": "Reviewer_3Dpt", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work focuses on a new problem: collaboration pure exploration with multiple tasks and general reward structures. It explores both fixed-confidence and fixed-budget settings. Nearly-matching upper and lower bounds on sampling and communication complexity are derived.", "summary_of_the_review": "This work clarifies its motivation and formulation in the beginning. After that, it studies the pure exploration problem for both fixed-confidence and fixed-budget settings. The nearly-matching bounds convince the efficacy of the proposed algorithms. However, numerical results are appreciated to even improve the work.\n\n========================\n\nAfter rebuttal: thanks for your reply. You may consider to involve the experiment results in the first version next time.", "strength_and_weaknesses": "Strength:\n1. The paper is easy to follow and provides a thorough overview of existing works.\n2. The motivation of this work is convincing: some tasks such as objective detection and object tracking are related but different, and they can be viewed as a possible application of the proposed model.\n3. The explanation and analysis of the proposed algorithm are detailed.\n\nWeaknesses:\n1. Is it possible to provide some numerical results?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "8_10DG4Cxy", "reviewer": "Reviewer_cGaa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors prefer a new kernel bandit model where multiple agents collaborate to complete different but related tasks with limited communication. The authors devise a novel communication scheme and design algorithms for fixed-confidence and fixed-budget objectives. ", "summary_of_the_review": "This paper provides novel algorithms for a well-founded and novel problem setting, which provide a clear contribution. While experiments are not the primary focus of the paper, it would be nice to see more experimental evaluation in the main paper. ", "strength_and_weaknesses": "Strengths\n- Model is useful for neural architecture search problems. \n- Algorithms achieve communication optimality. \n\nWeaknesses\n- Lack of experiments for this model in the main paper. Would be great to see applications in the main work. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3RgzetN3di", "reviewer": "Reviewer_j71S", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper looks into the problem of cooperatively determining the best arm in kernel bandits. The study builds on the prior CoPE formulation, which emphasizes the conventional MAB model, while retaining the fundamental communication concept. This paper makes two contributions: 1) it generalizes earlier work to the kernel bandit problem space, and 2) it produces nearly-optimal algorithms for both fixed-confidence and fixed-budget scenarios.\n\nMinor:\n\nIt is better if the author(s) could provide line numbers in the manuscript.", "summary_of_the_review": "This paper is a valuable extention of the previous work CoPE and it is the first one trying to identify the best arm in kernel bandits collaboratively using the communicaiton model formulated in CoPE. Additionally, it provides nearly-optimal algorithms. Overall I think it is a nice paper. However, I am a little bit worried about the goal of the problem, which tries to optimize the average number of samples per agent instead of the maximum one. I am happy to raise my score if the author(s) could provide practical examples to motivate this goal.\n\nAfter rebuttal\n--------------------------\nThe author(s) have promised to include the discussions regarding the difference between the goal of this paper and that of CoPE, hence I would like to increase my score.", "strength_and_weaknesses": "Strength\n*  This paper is a valuable extention of previous CoPE formulation. Each agent may experience a varied environment (reward functions) because of the characteristics of kernel bandits.\n* Strong and comprehensive theoretical analysis is provided.\n\nWeaknesses\n* In contrast to CoPE, where the sample complexity is defined as the greatest number of samples used per agent, the purpose specified in this study is a little bit different. The sample complexity is defined in this study as the average number of samples across all agents, which makes the speed-up definition less strong than that in CoPE. Since the running duration is determined by the one running the longest, I believe the definition in CoPE is more reasonable practically.\n* It is better if the authors could put the experiment results in the main paper", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster