Communication Efficient Distributed Learning for Kernelized Contextual Bandits
Authors: Chuanhao Li
Huazheng Wang
Mengdi Wang
Hongning Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: contextual bandit
kernelized method
distributed learning
communication efficiency

Abstract: We tackle the communication efficiency challenge of learning kernelized contextual bandits in a distributed setting. Despite the recent advances in communication-efficient distributed bandit learning, existing solutions are restricted to simple models like multi-armed bandits and linear bandits, which hamper their practical utility. 
In this paper, instead of assuming the existence of a linear reward mapping from the features to the expected rewards, we consider non-linear reward mappings, by letting agents collaboratively search in a reproducing kernel Hilbert space (RKHS). This introduces significant challenges in communication efficiency as distributed kernel learning requires the transfer of raw data, leading to a communication cost that grows linearly w.r.t. time horizon $T$. We addresses this issue by equipping all agents to communicate via a common Nystr\"{o}m embedding that gets updated adaptively as more data points are collected. We rigorously proved that our algorithm can attain sub-linear rate in both regret and communication cost.

Communication Efficient Distributed Learning for Kernelized Contextual Bandits
Chuanhao Li' Huazheng Wang" Mengdi Wang" Hongning Wang'
University of Virginia
2reegn State University Sprinceton University
{c15ev, (wbxx/vvrrgini edu
huazheng.. wangeoregonstate. edu mengdiweprinceton.cer
Abstract
We tackle the communication efficiency challenge of learning kernelized contextual bandits in distributed setting. Despite the recent advances in communication- efficient distributed bandit learning, existing solutions are restricted to simple models like multi-armed bandits and linear bandits, which hamper their practical utility. In this paper, instead of assuming the existence of linear reward mapping consider non-linear reward map-
from the features to the expected rewards, pings, by letting agents collaboratively search in a reproducing kernel Hilbert space (RKHS). This introduces significant challenges in communication efficiency distributed kernel learning requires the transfer of raw data, leading to a commu- nication cost that grows linearly w.r.t time horizon T. We address this issue by equipping all agents to communicate via common Nyström embedding that gets updated adaptively as more data points are collected. We rigorously proved that our algorithm can attain sub-linear rate in both regret and communication cost.
Introduction
Contextual bandit algorithms have been widely used for a variety of real-world applications, including recommender systems (20). display advertisement [21) and clinical trials [11]. While most existing bandit solutions assume centralized setting (i.e., all the data reside in and all the actions are taken by central server), there is increasing research effort distributed bandit learning lately where N clients, under the coordination of a central server, collaborate to minimize the overall cumulative regret incurred over finite time horizon T. In many distributed application scenarios, communication is the main bottleneck, e.g., communication in a network of mobile devices be slower than local computation by several orders of magnitude [16]. Therefore, it is vital for distributed bandit learning algorithms to attain sub-linear rate (w.r.t. time horizon T') in both cumulative regret and communication cost.
30
10
24 17
However, prior works this line of research are restricted to linear models 30 which could oversim- plify the problem and thus leads to inferior performance in practice. In centralized setting, kernelized bandit algorithms,, e.g., KernelUCB 229 and IGP-UCB [6). are proposed to address this issue by modeling the unknown reward mapping Hilbert space (RKHS), i.e., the expected reward is linear w.r.t. an action feature map of possibly infinite dimensions. Despite the strong modeling capability of kernel method, collaborative explo- ration in the RKHS gives rise to additional challenges in designing a communication efficient handit algorithm. Specifically, unlike distributed linear bandit where the clients can simply communicate the d x d sufficient statistics [30], where is the dimension of the input feature vector, the joint kernelized estimation of the unknown reward function requires communicating either 1) the p x p sufficient statistics in the RKHS, where is the dimension of the RKHS that is possibly infinite, or 2) the set of input feature vectors that grows linearly w.r.t. T. Neither of them practical due the huge communication cost.
non- non-parametric function lying in reproducing kernel
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper, we propose the first communication efficient algorithm for distributed kernel bandits, which tackles the aforementioned challenge via low-rank approximation of the empirical kernel matrix. In particular, we extended the Nyström method [22] to distributed learning for kerneiized contextual bandits. In this solution, all clients first project their local data to finite RKHS spanned by common dictionary, i.e., a small subset of the original dataset, and then they only need to communicate the embedded statistics for collaborative exploration. To ensure effective regret reduction after each communication round, well ensuring the dictionary remains representative for the entire distributed dataset throughout the learning process, the frequency of dictionary update and synchronization of embedded statistics is controlled by measuring the amount of new information each client has gained since last communication. We rigorously prove that the proposed algorithm incurs an 2 (T) communication cost, where 7NT is the maximum information gain that is known to be O (log(NT)) for kernels with exponentially decaying eigenvalues, which includes the most commonly used Gaussian kernel, while attaining the optimal D(VNTTNT) cumulative regret.
2 Related Works
To balance exploration and exploitation in stochastic linear contextual bandits, LinUCB algorithm [20 M is commonly used, which selects arm optimistically w.r.t. a constructed confidence set on the unknown linear reward function. By using kernels and Gaussian processes, studies in [26] 29 6 further extend UCB algorithms to non-parametrie reward functions in RKHS, ie.. the feature map associated with each arm is possibly infinite.
Recent years have witnessed increasing research efforts in distributed bandit learning, i.e., multiple agents collaborate in pure exploration [15 27 77, or regret minimization 24 30 19.. They mainly differ in the relations of learning problems solved by the agents (i.e., homogeneous vs., heterogeneous) and the type of communication network (i.e., peer-to-peer (P2P) vs., star-shaped). Most of these works assume linear reward functions, and the clients communicate by transferring the O(d)) sufficient statistics. Korda et al. [18] considered a peer-to-peer (P2P) communication network and assumed that the clients form clusters, i... each cluster is associated with a unique bandit problem. Huang et al. [17] considered a star-shaped communication network in our paper, but their proposed phase-based climination algorithm only works in the fixed arm set setting. The closest works to ours are 30 10 19), which proposed event-triggered communication protocols to obtain sub- linear communication cost over time for distributed linear bandits with a time-varying arm set. In comparison, distributed kernelized contextual bandits still remain under-explored. The only existing work in this direction [9] considered heterogeneous agents, where each agent is associated with an additional feature describing the task similarity between agents. However, they assumed local communication setting, where the agent immediately shares the new raw data point to its neighbors after each interaction, and thus the communication cost still linear over time.
Another closely related line of works is kernelized bandits with approximation, where Nyström method is adopted to improve computation efficiency in centralized setting. Calandriello al. B proposed an algorithm named BKB, which uses Ridge Leverage Score sampling (RLS) to re-sample new dictionary from the updated dataset after each interaction with the environment. A recent work by Zenati et al. [1I further improved the computation efficiency of BKB by adopting an online sampling method update the dictionary. However, both of them updated the dictionary at each time step to ensure the dictionary remains representative w.r.t. the growing dataset, and therefore are not applicable to our problem. This is because the dataset is stored cross clients in distributed manner, and projecting the dataset to the space spanned by the new dictionary requires communication with all clients, which is prohibitively expensive in terms of communication. Calandriello al. [4] also proposed a variant of BKB, named BBKB, for batched Gaussian process optimization. BBKB only needs to update the dictionary occasionally according to an adaptive schedule, and thus partially addresses the issue mentioned above. However, as BBKB works in centralized setting, their adaptive schedule can be computed based on the whole batch of data, while in our decentralized setting, each client can only make the update decision according to the data that is locally available. Moreover, in BBKB, all the interactions are based on a fixed model estimation over the whole batch, which is mentioned in their Appendix A.4 as a result of an inherent technical difficulty. In comparison, our proposed method effectively addresses this difficulty with improved analysis, and thus allows each client to utilize newly collected data to update its model estimation on the fly.

---

3 Preliminaries
In this section, we first formulate the problem distributed kernelized contextual bandits. Then, as a starting point, we propose and analyze a naive UCB-type algorithm for distributed kernelized contextual bandit problem, named DisKerneIUCB. This demonstrates the challenges designing a communication efficient algorithm for this problem, and also lays down the foundation for further improvement on communication efficiency in Section 4
3.1 Distributed Kernelized Contextual Bandit Problem
Consider a learning system with 1) .V clients that are responsible for taking actions and receiving feedback from the environment, and 2) central server that coordinates the communication among the clients. The clients cannot directly communicate with each other, but only with the central server, i.e., star-shaped communication network. Following prior works (30 10,, we assume the N clients interact with the environment in a round-robin manner for total number of T rounds.
Specifically, at round [T', each client [N] chooses arm X, from a candidate Ar, and then receives the corresponding reward feedback Y/ = fxx,) + E R, where the subscript t == (V 1) +i indicates this the f-th interaction between the learning system and the environment, and we refer to it as time step | Note that A, is time-varying subset of A C Rd that is possibly infinite, f denotes the unknown reward function shared by all the clients, and 1): denotes the noise.
Denote the sequence of indices corresponding to the interactions between client and the environment up to time / as N2(1) = (1 < a S L: =i (if 8 mod N O, then is N; otherwise i, = mod N) for / = 1, 2...., NT. By definition, [Wx((()) = 1, vI [T]. i.e., the clients have equal number interactions at the end of each round 1.
Kernelized Reward Function We consider unknown reward function f that lies in RKHS, denoted as H. such that the reward can be equivalently written as
yt = 0. ((x)) + T/--
where 0, E H. is an unknown parameter, and à Rd + 7. is known feature map associated with H. We assume T7 is zero-mean R-sub-Gaussian conditioned on o ((x,: (i)))) Vt, which denotes the n-algebra generated by client i 's previously pulled arms and the corresponding noise. In addition, there exists a positive definite kernel (.).,) associated with H. and we assume Vx E A that, ||x|| & L and || < S for some L,S 0.
The goal the learning system minimize the cumulative (pseudo) regret for all N clients, i.., Rvr = Σ It, where r; = maxxEA. x(x) 8, ((x,) 0,. Meanwhile, the learning system also wants keep the communication cost CNT low, which is measured by the total number of sealars being transferred across the system up to time step NT.
Regret and Communication Cost
3.2 Distributed Kernel UCB
As starting point to studying the communication efficient algorithm in Section 4 and demonstrate the challenges in designing a communication efficient distributed kernelized contextual bandit algorithm, here we first introduce and analyze a naive algorithm where the N clients collaborate on learning the exact parameters of kernel bandit, i.e., the mean and variance of estimated reward. We name this algorithm Distributed Kernel UCB, DisKernelUCB for short, and its description is given in Algorithm
For each round 1 (T), when client [N] interacts with the environment, i.e., the t-th interaction between the learning system and the environment where = N - 1) + i, it chooses arm X, A based the UCB of the mean estimator (line 5):
Arm Selection
X arg max fi (,x) + xEAA,
'The meaning of index f is slightly different from prior works, e.g. DisLinUCB in 30 but this is only to simplify the use of notation and does not affect the theoretical results
3

---

Algorithm Distributed Kernel UCB (DisKerneUUCB)
1: Input threshold D > 0
2: Initialize last = 0, Do(i) = (D)(() = vi e
3: for round = 1,2,
do
4: for client = ........ .N do
5: Client i chooses arm X, A, according to Eq ( and observes reward y/, where t N(1 (01-1)=a 1)+
6:
Client i updates K (..)),,. (1), (D) where (i (i) U (1); and its upload buffer (D,(i) AD) {t}
// Global Synchronization
7:
if the event 44 (D) defined in Eq 2 is true then
Clients v/j E [N]: send {(x,, Bn) h.EAD.() to server, and reset (J. = 9: Server: aggregates and sends back {(x., ya) selt sets tast = t
8:
Clients j/j [N] update Kp.G).D.)) Y.. (D) where Dz(j)
where (x) and 0f2 (x) denote client i's local estimated mean reward for arm x E A and its variance, and Ct- is a carefully chosen scaling factor balance exploration and exploitation (see Lemma 3.1 for proper choice).
To facilitate further discussion, for time step E [NT], denote the sequence of time indices for the data points that have been used to update client i's local estimate as (i).,, which include both data points collected locally and those shared by the other clients. If the clients never communicate, (i) = (G),,, Vl, i; otherwise, (i) C Dz(i) C [4. with (i) = [4] recovering the centralized setting, i.e., each new data point collected from the environment immediately becomes available to all the clients in the learning system. The design matrix and reward vector for client i at time step t are denoted by Xp,(i) = Xxl E TR (P]] xd
yy., = (olTT E &R/P(00,, respectively. By
applying the feature map Φ(-) to each row of X D.)), we obtain + P.)() E <RI,,0)Xp,, where p is the dimension of H. and is possibly infinite. Since the reward function is linear in H. client can construct the Ridge regression estimator 0,,, ( (D.00 PD.(1) + - D,ii where À > 0 is the regularization coefficient. This gives the estimated mean reward and variance in primal form for any arm x E A, i.c. (x) = T A br. and (x, / /o(x)) A Φ(x), where A + (. (.(()) + AI and b + (.. Then using the kernel trick,
obtain their equivalence the dual form that only involves entries of the kernel matrix, and avoids directly working on H which is possibly infinite:
(x) K (D((0) (KD(0....)) + AT) YD(()
(x, 112 xxxx) (x) T (KD,0,,,.0) + A1) - (x) R PP()))), and (D.
where (D (x) (())) [k(x,, XITE
( 2 PD.(1) = [k(x,, X,y (l. E (IP(()))P(())
Communication Protocol To reduce the regret in future interactions with the environment, the N clients need collaborate via communication, and carefully designed communication pro- tocol is essential in ensuring the communication efficiency. In prior works like DisLinUCB 30). after each round of interaction with the environment, client i checks whether the event [((D(()) - (Pr.. (i)l) log( det(A.
det(AA.)). > D} is true, where tast denotes the time step of last
global synchronization. If true, a new global synchronization is triggered, such that the server will require all clients to upload their sufficient statistics since tlstt aggregate them to com- pute (A,, by). and then synchronize the aggregated sufficient statistics with all clients, ie.. set (Ar,s, br, = (A,, b.), Vi E [N].
Using kernel trick, we can obtain equivalent event-trigger in terms of the kernel matrix, det(I + X (D.()))
D)
U((D) (ID)(1.) IDr.. (1+))) log det X K (...G)AA
(2)

---

where D > 0 denotes the predefined threshold value. If event (D) is true (line 7), global synchronization is triggered (line 7-10). where the local datasets of all N clients are synchronized to {(x,, >E]() We should note that the transfer of raw data (Xx; ys) is necessary for the update of the kernel matrix and reward vector in line and line 10, which will be used for arm selection at line 5. This is an inherent disadvantage of kernelized estimation in distributed settings, which, as we mentioned in Section 2 is also true for the existing distributed kernelized bandit algorithm [9]. Lemma 3.1 below shows that in order to obtain the optimal order of regret, DisKernelUCB incurs a communication cost linear in T (proof given in the appendix), which is expensive for an online learning problem.
Lemma 3.1 (Regret and Communication Cost of DisKemelUCB). With threshold D NYNT' or. 0- + R/4 N 8 + 2 2 + (D. AJ, we have RNT = O(VNNT(Ielll (NT)),
T
with probability at least 1 5, and
-NT=O(TN2d)
where "NT == maxDC DI=NT 1 log de + 1) is the maximum information gain after NT interactions (σ)) It is problem-depenlent and can be bounded for specific arm set A and kernel function ).. For example, "NT = O(dlog(NT)) for linear kernel and NNT = Ologg (NT)+())) for Gaussian kernel.
Remark 1. In the distributed linear bandit problem, to attain D(V/NT (n(N)) regret, DisLinUCB 30 requires a total number of ( (og(N)) synchronizations, and DisKernelUCB matches this result under linear kernel, as it requires ((N.57NT) synchronizations, We should note that the communication cost for each synchronization in DisLinUCB is fixed, i.e., ONd)) to synchronize the sufficient statistics with all the clients, so in total ONT (N5 In(NT)) However, this is not the case for DisKernelUCB that needs to send raw data, because the communication cost for each synchronization in DisKemelUCCB is not fixed, but depends on the number of unshared data points on each client. Even if the total number of synchronizations is small. DisKernelUCC could still incur CNT O d) in the worse case. Consider the extreme case where synchronization only happens once, but it happens near NT, then we still have CNT = OTT22 dd.. The time when synchronization gets triggered depends on {Ai) [NT]) which is out of the control of the algorithm. Therefore, in the following section, to improve the communication efficiency of DisKernelUCCt we propose to let each client communicate embedded statistics in some small subspace during each global synchronization.
4 Approximated Distributed Kernel UCB
In this section, we propose and analyze a new algorithm that improves the communication efficiency of DisKemelUCB using the Nyström approximation, such that the clients only communicate the embedded statistics during event-triggered synchronizations. We name this algorithm Approximated Distributed Kernel UCB, or Approx-DisKernelUGG for short. Its description is given in Algorithm 2
4.1 Algorithm
Arm selection For each round I [T), when client i [N] interacts with the environment, i.e., the t-th interaction between the learning system and the environment where t := [[ 1) + i, instead of using the UCB for the exact estimator in Eq (T). client chooses arm x; E A, that maximizes the UCB for the approximated estimator (line 5):
X arg max (xx), + (1-1,ō0-1,(x) xEAr,
where (x) and Ōz-1,; (x) are approximated using Nyeström method, and the statisties used to compute these approximations are much more efficient to communicate as they scale with the maximum information gain 7NT instead of T.
Specifically, Nyström method works by projecting some original dataset 'D to the subspace defined by small representative subset S C D. which is called the dictionary. The orthogonal projection matrix is defined as
Ps- = 33 (
Φs = $5 K-1
S.S T3 E Px
5

---

Algorithm 2 Approximated Distributed Kernel UCB (Aprrox-DiskernlUUch)
Input: threshold D > regularization parameter À > 0, (0, 1) and kernll function k(=;)) -).
2: Initialize (x,x(x) (x) 0, (x.:(x) 1ll:=/<iiii vk(xx N6, = (i( 0. Vi E [N]:S = 0, Mase
3: for round = 1, 1, .... T do
4: for client = 1, ...: .N do
5: [Client selects arm X, E A, according to Eq 3 and observes reward ye. where & := N 1) +i
6:
[Client i] updates ZD, (i):s) (1)5 and Z (1) (D.()) using (z(x;: Stan): ). ye): sets {t}, and (i = (
= // Global Synchronization
7:
if the event (4 (D) defined in Eq is true then [Clients Vi] sample S = ( q. Rm and send {(x., ya)loes.. to server [Server] aggregates and sends {xx,, Us) Ms)sssssssss ses, back to all clients, where St = Uti to server
8:
9:
10:
[Clients Vi] compute and send {Z (1):s S)) Z (.
[Server] aggregates Σ N... 2N.() Σ Z Ni VNG(i) and sends it back [Clients Vij updates ZD.()): (D) and D.); (D.(,))) sets Dz(1) = (i(())
11:
12:
[1] and Ias =
We then take eigen-decomposiitinn of Ks,s = UAUT to rewrite the orthogonal projection as Ps = 2 UA A U Øs. and define the Nyström embedding function
2(x; S) = P' (xx) A u $so(x) K5 (x())
which maps the data point x from ddd to Rl
Therefore, we can approximate the Ridge regression estimator in Section 3.2 as o..; A b where A = P (1) 2 (.) Ps + AI, and b.,; = Ps P (D) and thus the approximated mean reward and variance in Eq B can be expressed as (x),(x) = x(x) A and ,x,((x)
V (xxx) A (x)), and their kernelized representation are (see appendix for detailed derivation)
(xx(()) S) (z) + AI) ZZ (.).sS.)
,c,((x) = 1-12//
1/2 v /(x,x) - =(x; T Z D..iss 2 D.n:
Z (.))) + -
where (D)(s [|D(() is obtained by applying <(: each row of XD, i... (1):
D..()) D We see that the computation of (x) and (x, only requires the embedded statistics: matrix Z.. (D)) E S| and vector (D..)) (D())) E ERS $1, which, as we will show later, makes joint kernelized estimation among N clients much more efficient communication.
After obtaining the new data point (x,, vt), client immediately updates both (x) and (xx) using the newly collected data point (x,, Mt), i.e., by projecting x, to the finite dimensional RKHS spanned by & S (line 6). Recall that, we use (i) to denote the sequence of indices for data collected by client i, and denote by (i) the sequence of indices for data that has been used to update client i's model estimation ft, Therefore, both of them need to be updated to include time step t.
Communication Protocol With the approximated estimator, the size of message being commu- nicated across the learning system is reduced. However, a carefully designed event-trigger is still required minimize the total number of global synchronizations up to time NT. Since the clients can no longer evaluate the exact kernel matrices in Eq (2). we instead use the event-trigger in Eq 4 which can be computed using the approximated variance from last global synchronization as,
U(DD)
Σ
S (H) (

---

Similar to Algorithm if Eq 4 is true, global synchronization is triggered, where both the dictionary and the embedded statistics get updated. During synchronization, each client first samples a subset (i) from (i) (line 8) using Ridge Leverage Score sampling (RI.)) 3 which is given in Algorithm 3 and then sends ((x,, ys)) vs)) to the server. The server aggregates the received local subsets to construct a new dictionary {(x,. Va)] where S; = - (t), and then sends it back to all N clients (line 9). Finally, the N clients this updated dictionary to re-compute the embedded statistics of their local data, and then synchronize it with all other clients via the server (line 10-12).
Algorithm 3
Ridge Leverage Score Sampling (RLS)
1: Input: dataset D, scaling factor q. (possibly delayed and approximated) variance function a-)
2: Initialize new dictionary S 0
3: for E D do
4: Set Ps = (x.)
5: Draw q, ~ (ernoulli(p.)
6: g, = 1, add 8 into S
7: Output: S
Intuitively, in Algorithm 2 the clients first agree upon a common dictionary St that serves as a good representation of the whole dataset at the current time i, and then project their local data to the subspace spanned by this dictionary before communication, in order to avoid directly sending the raw data as in Algorithm [ Then using the event-trigger, each client monitors the amount of new knowledge it has gained through interactions with the environment from last synchronization. When there is sufficient amount of new knowledge, it will inform all the other clients to perform synchronization. As we will show in the following section, the size of S, scales linearly w.r.t. the maximum information gain "NT, and therefore it improves both the local computation efficiency on each client, and the communication efficiency during the global synchronization.
4.2 Theoretical Analysis
Denote the sequence of time steps when global synchronization is performed, i.e., the event 24, (D) in Eq (4) is true, as {tp 1p 1p where B E [NT] denotes the total number of global synchronizations. Note that in Algorithm [ the dictionary is only updated during global synchronization, e.g.. at time lp. the dictionary {(x,, yd) }.)],es,, is sampled from the whole dataset {(x,, W.) in distributed manner, and remains fixed for all the interactions happened at & E [4p + 1, 12411 Moreover, at time tp. all the clients synchronize their embedded statistics, so that Dr, (1) [t Vi [N].
Since Algorithm 2 enables local update on each client, for time step E [4 + 1, 4p). new data points are collected and added into Di),, such that (i) 2 [tp]. This decreases the approximation accuracy of St new data points may not be well approximated by S,,. For example, in extreme cases, the new data could be orthogonal to the dictionary. To formally analyze the accuracy of the dictionary, we adopt the definition of e-accuracy from (5). Denote by S,,; E (l) a diagonal matrix, with its s-th diagonal entry equal to vp.
if 8 E S., and 0 otherwise. Then
(1 ex, :) ( (.) (.()) + AI) T (,))) ST,.S., P.(0) + AI 3 (1 (1+ ( (00 PD.00 + AI),
we say the dictionary {(x., sES,, is accurrae w.r.t. dataset {(x., y.))
As shown below, the accuracy of the dictionary for Nyström approximation is essential as it affects the width of the confidence ellipsoid, and thus affects the cumulative regret. Intuitively, in order to ensure its accuracy throughout the learning process, we need to 1) make sure the RLS procedure in line 8 of Algorithm 2 that happens at each global synchronization produces a representative set of data samples, and 2) monitor the extent to which the dictionary obtained in previous global synchronization has degraded over time, and when necessary, trigger new global synchronization to update it. Compared with prior work that freezes the model in in-between consecutive communications [4], the analysis of c-accuracy for Approx-DisKemellU
is unique to our paper and the result is presented below.
Lemma 4.1. With q = t log(4NT/6)/é², for some E [0, 1), and threshold D > 0, Algorithm guarantees that the dictionary is accurate with constant fz.s = (e +
1 1+ D) ). and its size
[el O(TNT) for all t [NT].
7

---

Based on Lemma 4.1 we can construct the following confidence ellipsoid for unknown parameter u.. Lemma 4.2 (Confidence Ellipsoid of Approximated Estimator). Under the condition that = 6 1og(4NT/6)/c for some c E [0, 1), and threshold D > O, with probability at least 1 5, we huve VI, that
110. 0.I.A..
- 1/(+/(EED) (V-++))(E +1) vAl10.11 CAR//NNT// 7NT au,
1
Using Lemma we obtain the regret and communication cost upper bound of Approx- DisKemelUCCB, which is given in Theorem 4.3 below.
Theorem 4.3 (Regret and Communication Cost of Approx- (ppro--DisKermeUUCBB) Under the same condi- tion as Lemma 4.2 and by setting D = N, <
3. we have
RNT 0 NT ll INT + +NNT)
with probability at least - 6, and
- ONT=O
Here we provide proof sketch for Theorem and the complete proof can be found appendix.
Proof Sketch. Similar to the analysis of DisKernelUCB in Section 3.2 and DisLinUCB from [30], the cumulative regret incurred by Approx-Diis DisKernnlUCB can be decomposed in terms of 'good' and 'bad' epochs, and bounded separately. Here an epoch refers to the time period in-hetween two consecutive global synchronizations, e.g., the p-th epoch refers to [l--1 + 1, Ap). Now consider an imaginary centralized agent that has immediate access to each data point in the learning system,
and denote by A. Ei= d. for [NT] the matrix constructed by this centralized agent.
det(I+A (K(,lppp
We call the p-th epoch good epoch if In( det(I+> "Kit--llitpp)) S 1, otherwise
bad "KiT---A""K
epoch. Note that In( deu(L+>'' ( ) +et(2et
det[[+AX'"Kiglllie ((gg.. +..... + In( det(I-A 'Kgg)tt))
det(I)
det(I+> "K())-(t
In(det(I+> "KAA-KK(ja (KNT),NT S 2YNT, where the last equality is due to the matrix determinant lemma. and the last inequality is by the definition of the maximum information gain 7NT in Lemma 3.1
Then based the pigeonhole principle, there can be at most 2YNT bad epochs.
By combining Lemma E.I and Lemma 4.2 curred during all good epochs, i.e., Ryood regret attained by the KemnlUCC algorithm in centralized setting. Our analysis devi- ates from that of DisKernelUCB in the bad epochs, because of the difference in the event-trigger. Previously, the event-trigger of DisKernelUCB directly bounds the cumu- lative regret each client incurs during bad epoch, i.e., LIEP,,,0V,,,. (x.))(x)) S
we can bound the cumulative regret in- O(NNTTwT), which matches the optimal
V (0)
- (D (i)l log (det(I + (D...)) det(II + Betp://eeett--KKKaaaaaaaaaaa D.N.KKKAAAAAAA.....A.AAAAA
VD. However, the event trigger of Approx-DisKemellCcB only bounds part of it, ie., EIDD, (ID,,, (1) Ōx-1,1(x))
((),, IDi,_ (i)) which leads to Road = O(VTYNTNVD) that is slightly worse than that of DisKemelUCBB ie.. a VT factor in place of the VINT factor. By setting E [0, 1) is still well-defined, we can set < 1/3.
D = 1/N, we have Ryz = O(VNTyNT). Note
that, to make sure 6,, (e 1+ I
For communication cost analysis, we bound the total number of epochs B by upper bounding the total number of summations like > Σ o7, (x.), over the time horizon NT. Using Lemma
E our event-trigger in Eq ( provides lower bound ΣSr 1+1 o? (xx) 2 1-c DD. Then in order to apply the pigeonhole principle, we continue to upper bound the summation over all epochs, Σ Ei
o2 (x.)
02 (Xx) = p= E' 02 (x.)
by deriving a uniform bound
03 (x.)
(x.) 0 (x.)
for the ratio (x,)
E'e
1+ 07 (x,) 1 Itc E.e 1+1 0? (x,)
82 (x.)
I-c
in terms of the communication threshold D on each client. This leads to the following upper bound 1 +N + L ([DD))] and with D = 1/N,
about the total number of epochs B < 1-el [ + 1t
we have ONT B NN 2 which completes the proof.
8

---

Remark 2. Compared with DisKereeUUCB's d( communication cost. Approx- Dipro--DsKKereeUUCBBB removes the linear dependence on T, but introduces an additional YNT dependence due to the communication of the embedded statistics. In situations where "NT < T//3///3 DisKernelUCH is preferable. As mentioned in Lemmaa3.1 the value of "NT, which affects how much the data can be compressed, depends on the specific arm set of the problem and the kernel function of the choice. By Mercer's Theorem, one can represent the kernel using its eigenvalues, and "NT characterizes how fast its eigenvalues decay. Vakili et al. [28] showed that for kernels whose eigenvalues decay exponentially, ie., Am (cxp(-mm' }), for some 3e > O, "NTT = OOlo - (NT)). In this case, approx-Diskernelle which is widely used for GPs and SVMs. For kernels that have polynomially decaying eigenvalues, i.e. Am = O -p)) for some Bp > 1, 7NT = O(T log" log--=; (NT)). Then as long as Bp > 3. Approx-DisKemelUCC still enjoys reduced communication cost.
is far more efficient than DisKemelUCCB. This includes Gaussian kernel,
5 Experiments
In order to evaluate Approx-DisKermelUCCB'ss effectiveness in reducing communication cost, we performed extensive empirical evaluations on both synthetic and real-world datasets, and the results (averaged over 3 runs) are reported in Figure [ 2 and 3, respectively. We included DisKemelUCBB, DisLinUCB [30], OneKemelUCB, and WKernelUCH 6 as baselines, where One-Kernell learns shared bandit model across all clients' aggregated data where data aggregation happens immediately after each new data point becomes available, and N-KemnlUUCB learns separated bandit model for each client with no communication. For all the kernelized algorithms, we used the Gaussian kernel (xx, y) exp( ->>1>> y. We did grid search of 7 E {0.1, 1, for kernelized algorithms. and set D = 20 for DisLinUCB and DisKernelUCB, D- = 5 for Approx-DisKernelule
For all algorithms, instead of using their theoretically derived exploration coefficient a, we followed the convention [20 (32 to use grid search for in (0.1, 1, 4). Due to space limit, here we only present the experiment results and discussions. Details about the experiment setup are presented in appendix.
When examining the experiment results presented in Figure cumulative regret and communication cost of OneKemelUCB and NKerelUCB. which correspond to the two extreme cases where the clients communicate in every time step to learn a shared model, and each client learns its own model independently with no communication, respectively. OneKer- neIUCB achieves the smallest cumulative regret in all experiments, while also incurring the highest communication cost, i.e., N2d. This demonstrates the need efficient data aggregation across clients for reducing regret. Second, we can observe that DisKernelUCB incurs the second highest communication cost in all experiments due to the transfer of raw data, as we have discussed Remark I which makes it prohibitively expensive for distributed setting. On the other extreme, we see that DiSLinUCB incurs very small communication cost thanks to its closed-fone forsed-fommma solution, but fails to capture the complicated reward mappings in most of these datasets, e.g. in Figure [(a] 2 and 3(a] it leads to even worse regret than NKemelUCB that learns a kernelized bandit model independently for each client. In comparison, the proposed Approx- Approx-DisKereelll Den algorithm enjoys the best of both worlds in most cases, i.e., can take advantage of the superior modeling power of kernels to reduce regret, while only requiring a relatively low communication cost for clients to collaborate.
and 3 we can first look at the
367
Axed
hazd
2.0
Onelerne UCD
2200
Orakgmwl
Soed
hond
(a) cos cos(3x (3x
0.)
(b) (x
0.) 3
3(x
0.)²
(x 0.)+3
Figure 1: Experiment results on synthetic datasets with different reward function f(x).

---

1060
0.00
faun
Toudd
2.30
NS SOUNTTAL
130
180
(a) MagicTelescope
(b) Mushroom
(c) Shuttle
Figure 2: Experiment results on UCI datasets.
5200
367
220-
Ondiumee 3C3
100
Axed
(a) MovieLens
(b) Yelp
Figure 3: Experiment results on MovieLens & Yelp datasets.
On all the datasets, Approx-Dre Dismeel achieved comparable regret with DisKernelUCB that maintains exact kernelized estimators, and sometimes getting very close to OneKernlUCBB, c.g.. in Figure T(b) and 2(a) but its communication cost is only slightly higher than that of DisLinUCB.
Conclusion
In this paper, we proposed the first communication efficient algorithm for distributed kernel bandits using Nyström approximation. Clients in the learning system project their local data a finite RKHS spanned by shared dictionary, and then communicate the embedded statisties for collaborative exploration. To ensure communication efficiency, the frequency of dictionary update and synchro- nization of embedded statisties controlled by event wvent-trigger The algorithm is proved to incur 2 communication cost, while attaining the optimal O O(VNTTNr) cumulative regret.
We should note that the total number of synchronizations required by Approx-Dis DisKernelUCB is NYNT, which is VN worse than DisKernelUCB, An important future direction this work is to investigate whether this part can be further improved. The lower bound analysis for the communication cost of distributed contextual bandits still remains an open problem, and is an important future direction. To the best of our knowledge, the only applicable lower bound states that, in order to have smaller regret than the trivial O(NvT) result, i.e., run N instances of optimal bandit algorithm with no communication, ?(N) communications is necessary [4]] comparison, it more interesting to know what the communication lower bound is in order to attain the optimal (VVNT) regret. is also interesting extend algorithm P2P setting, i.e., central server to coordinate the update of the shared dictionary and the exchange embedded statistics, which may require utilizing local structures in the network of clients, to approximate each block of the kernel matrix separately (5
Acknowledgement
This work is supported by NSF grants IIS-2213700, I1S-2128019, IIS- 1838615, IIS-2107304, CMMI- 1653435, DMS-1953686, and ONR grant 1006977.
10

---

References
[1] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 14:2312-2320) 2011.
[2] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Ec-net: Exploitation-cxplorie neural networks in contextual bandits. arXiv preprint arXiv:21 2021.
[3] Daniele Calandricllo, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco. Gaussian process optimization with adaptive sketching: Scalable and regret. In Conference on Learning Theory, pages 533-557. PMLR, 2019.
[4] Daniele Calandriello, Luigi Carratino, Alessandro I Lazaric, Michal Valko, and Lorenzo Rosasco. Near-linear time gaussian process optimization with adaptive batching and resparsification, In International Conference on Machine Learning, pages 1295-1305, PMLR, 2020.
[5] Daniele Calandriello, Alessandro Lazaric, and Michal Valko. Second-order kernel online convex optimization with adaptive sketching. In International Conference on Machine Learning, pages 645-65 653, PMLR, 2017.
[6] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pages
PMLR, 2017.
[7] Yihan Du, Wei Chen, Yuko Yuroki, and Longbo Huang. Collaborative pure exploration in kernel bandit. arXiv preprint arXiv:2110.15771 2021.
[8] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[9] Abhimanyu Dubey al. Kernel methods for cooperative multi-agent contextual bandits. In International Conference on Machine Learning, pages 2740-2750, PMLR, 2020.
[10] Abhimanyu Dubey and AlexSandy' Pentland. Differentially-privea federated linear bandits. Advances Neural Information Processing Systems, 33, 2020.
[11] Audrey Durand, Charis Achilleos, Demetris lacovides, Katerina Strati, Georgios D Mitsis, and Joelle Pineau, Contextual bandits for adapting treatment a mouse model of novo carcinogenesis. In Machine learning for healthcure conference, pages 67-82. PMLR, 2018.
[12] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In NIPS, volume 23, pages 586-594, 2010.
[13] F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis) 194 2015.
[14] Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu. A simple and provably efficient algo- rithm for asynchronous federated contextual linear bandits. arXiv preprint urXiv:2207.03100 2022.
[15] Eshcar Hillel, Zohar S Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. Distributed exploration in multi-armed bandits. Advances in Neural Information Processing Systems, 26, 2013.
[16] Junxian Huang. Feng Qian, Yihua Guo, Yuanyuan Zhou, Qiang Xu, Z Morley Mao, Subhabrata Sen, and Oliver Spatscheck. An in-depth study of lte: Effect of network protocol and application behavior performance. ACM SIGCOMM Computer Communication Review, 43(4):363-374, 2013.
[17] Ruiquan Huang. Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. Advances in Neural Information Processing Systems, 34, 2021.
[18] Nathan Korda, Balazs Szorenyi, and Shuai Li. Distributed clustering of linear bandits in peer to peer networks. International conference on machine learning, pages 1301-1309. PMIR, 2016.
11

---

[19] Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. In International Conference on Artificial Intelligence and Statisties, pages 6529-6553. PMLR, 2022.
[20] Lihong Li. Wei Chu, John Langford, and Robert E Schapire. A caatextual-bandiee approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[21] Wei Li, Xuerui Wang, Ruofei Zhang, Ying Cui, Jianchang Mao, and Rong Jin. Exploitation and exploration in performance based contextual advertising system. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 27-36, 2010.
[22] Evert J Nyström. Über die praktische auflösung von integralgleichuunee mit anwendungen auf randwertaufgaben. Acta Mathematica, 54:185-204, 1930.
[23] Jonathan Scarlett, Iliaa Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy gaussian process bandit optimization. In Conference Learning Theory, pages 1723-1742. PMLR, 2017.
[24] Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021.
[25] Si Si, Cho-Jui Hsich, and Inderjit Dhillon. Memory efficient kernel approximation. In Interna- tional Conference on Machine Learning, pages 701-709. PMLR, 2014.
[26] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian pro- cess optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009.
[27] Chao Tao, Qin Zhang, and Yuan Zhou. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In 2019 JEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 126-146. IEFE, 2019.
[28] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference Artificial Intelligence and Statistics, pages 82-90. PMLR, 2021.
[29] Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv: 30696869,.9666 2013.
[30] Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optimal regret with efficient communication. In International Conference on Learning Representations, 2019.
[31] Houssam Zenati, Alberto Bietti, Eustache Diemert, Julien Mairal, Matthieu Martin, and Pierre Gaillard. Efficient kernel ucb for contextual bandits. arXiv preprint arXiv:2202.05638, 2022.
[32] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 11492-11502. PMLR, 2020.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes], see Remark 2
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
12

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]. in Section 3.1
(b) Did you include complete proofs of all theoretical results? [Yes], the complete proof given in appendix
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you's 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "i1fM5yUQHEp", "reviewer": "Reviewer_fUXs", "summary": "The paper studies the problem of distributed bandits when the reward function lies in an RKHS. The paper proposes algorithms to enable clients to make a decision at each round. The regret and communication cost of proposed algorithms are studied.", "questions": "What is the relations between the regret bound of Approx-DisKernelUCB and the Nystrom method to map $x$? How the approximation affect the regret bound? I think it is useful if authors can elaborate more on this in the paper.", "limitations": "The paper assumes that the rewards are generated using a kernel function belongs to an RKHS. Furthermore, privacy of clients cannot be protected using the proposed algorithms.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The paper proposes an algorithm based on Nystrom approximation which can achieve sub-linear regret of $\\mathcal{O}(\\sqrt{NT})$ which is proved to require communication cost of $\\mathcal{O}(N^2)$.\n\nWeaknesses:\n1. Clients needs to send their data samples to the server. Therefore, the proposed algorithms cannot protect the privacy of clients.\n2. The novelty of the proposed algorithm DisKernelUCB seems to be limited. Since the communication cost of the algorithm should be $\\mathcal{O}(TN^2d)$ to achieve regret of $\\mathcal{O}(\\sqrt{NT})$, it seems that DisKernelUCB is a simple extension of centralized algorithm where each client locally learns to take an action. In fact, it seems that making minor changes in the centralized algorithm can lead to this result.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fI-WFmTDRC", "reviewer": "Reviewer_h26a", "summary": "This paper studies the distributed kernel bandit problems in a decentralized setting. As a first observation, they consider Distributed-Kernel UCB, which is naturally derived from the one for distributed linear bandits, and prove that its communication cost suffers from the linear dependence of time horizon T. To remedy this, they propose Approximated Distributed Kernel UCB that uses the Nyström approximation techniques. The resulting communication depends on the term on maximum information gain $\\gamma_{NT}^3$, removing the linear dependence of T. They also conducted a series of experiments using real-world dataset.\n", "questions": "Some may say that the key techniques are essentially imported from the work of [2,3] and combining these with distributed Kernel bandits seems to be a straightforward approach. It would be appreciated if the authors explain what difficulties arise when applying them to distributed kernel bandits.", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThe idea of Nyström approximation techniques enables the improved Dist Kernel UCB to have a better communication cost than the naive Kernel UCB. Approximated Kernel UCB maintains the good representation of the whole dataset, which is used to escape the sending of all unshared raw data.\nIn order to deal with such an approximated estimator, the event-trigger in Eq (4) is derived for determining when to incur the global synchronization.\n\nThe size of the dictionary $S_t$ scales linearly w.r.t. the maximum information gain $\\gamma_{NT}$, which therefore improves the communication efficiency. \nAll of the parameters such as threshold D in the event-trigger and how the subroutine of RLS in algorithm 3 is invoked is clearly stated. \n\nThe value of the information gain $\\gamma_{NT}$ is now a key factor in the analysis. They satisfactorily discussed what this factor implies and which affected the factor, when it is sufficiently smaller than $T^{1/3}$. \n\n\nWeakness:\nThe lower bound on communication costs for this problem is not fully discussed. \n\n===Post Rebuttal===\nThank you for author's response and detailed discussion for communication lower bound result with Square Exponential kernels.\nI also read other reviews and keep my score for acceptance.  \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_9XIfNz7j0-", "reviewer": "Reviewer_tP3Z", "summary": "The current paper studies the distributed kernelized bandit, a generalization of the distributed linear bandit. Different from the distributed linear bandit [25], one cannot upload/download sufficient statistics (i.e., Gram matrix) for total $O(\\log T)$ communication rounds, since for later communication rounds, sending either the raw data (size of $dT$ to resume the sufficient statistics) or the original kernelized Gram matrix (size of $p^2$, where p can be infinite) will be prohibitively expensive. The author adopts the idea of sparse approximation, i.e., Nyström embedding, to project the $p\\times p$ kernelized Gram matrix into a new matrix that is of size $O(\\gamma_{NT})$, where $O(\\gamma_{NT}$ is the information gain of order $O(\\log T)$ for some kernel functions. To this end, the authors can prove $O(\\sqrt{NT}\\gamma_{NT})$ regret and $O(N^2\\gamma_{NT}^3)$ communication cost.", "questions": "Can you discuss and explain more about the tightness of your result? This could be comparing with the degenerate case, the lower bound, or the trade-off between the communication cost and the regret. ", "limitations": "The authors adequately addressed the limitations and there is no foreseen potential negative societal impact of the current work", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength.\n\n1. The problem is well-motivated. To the best of my knowledge, there are no previous works studying distributed kernelized bandit, with rigorous sublinear regret and sublinear communication cost guarantee. I enjoy the way how the authors first discuss the straightforward usage of the previous solution [25] as a warm-up and motivate the challenge of the problem.\n\n2. From the technical point of view, though I did not go through all the proofs, the intuition of the current paper is clear and reasonable. I think the authors borrow the batched/delayed kernelized bandit as building blocks to save the communication round and use the sparse approximation to save the per-round data to be uploaded/downloaded. The main contributions of this paper are designing a suitable triggering event with only approximated sufficient statistics at hand and using ridge leverage score sampling to send sampled information. From my perspective, the solution and the analysis should be of independent interest to other related works. \n\nWeakness.\n\n1. Unlike [25], I do not find any discussion about the tightness of the result and the communication and regret trade-off. Also, there are no lower bound results for communication cost, so it is a little bit confusing how tight the communication cost $O(N^2\\gamma_{NT}^3)$ is. Moreover, it is not clear to me why there are no $d$ factors in the regret, I guess the reason is you replace both $d$ and $T$ to $\\gamma_{NT}$ so you can replace the trivial bound (for Algorithm 1) to $O(N^2\\gamma_{NT}^2)$, but this again is one $O(\\gamma_{NT})$ factor less than your current result.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JG4XoteA7I9", "reviewer": "Reviewer_nxdg", "summary": "This paper investigates the communication efficiency challenge of kernelized contextual bandits in a distributed setting. This paper resolves this challenge by equipping all agents to communicate via a common Nyström embedding which is updated adaptively as more data points are collected. This paper proposes an algorithm named Approx-DisKernelUCB and demonstrated that Approx-DisKernelUCB can achieve sub-linear rate in both regret and communication cost.", "questions": "Could you explain the differences of the techniques used to handle communication challenges between this work and prior distributed linear bandit works?\n\nCan the Nyström embedding technique solve the communication challenges of distributed linear bandits?\n\nWhy not directly present algorithm Approx-DisKernelUCB? The algorithm DisKernelUCB seems not satisfactory due to its linear communication cost. \n", "limitations": "See the weakness above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\nThe proposed Nyström embedding technique is very interesting, which makes a solid contribution to the communication challenge of distributed kernelized contextual bandits. The proposed algorithm Approx-DisKernelUCB achieves good performance in terms of both regret and communication costs.\n\nThis paper is well-written and the presented theoretical analysis looks sound and solid. Readers can easily understand the main idea behind algorithm Approx-DisKernelUCB.\n\n**Weaknesses:**\n\nThe structure of this paper could be further improved. I suggest the authors to give more intuition behind the theoretical analysis and put some representative experimental results in the main text.\n\nIt would be better if the authors can comment and discuss the following related works on distributed pure exploration in the literature review part.\n\n1. Distributed exploration in multi-armed bandits. Hillel et al.\n2. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. Tao et al.\n3. Collaborative Pure Exploration in Kernel Bandit. Du et al.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept