Learning Kernelized Contextual Bandits in a Distributed and Asynchronous Environment
Authors: Chuanhao Li
Huazheng Wang
Mengdi Wang
Hongning Wang
Venue: ICLR 2023 poster (2023)
Keywords: contextual bandit
kernelized method
asynchronous distributed learning
communication efficiency

Abstract: Despite the recent advances in communication-efficient distributed bandit learning, most existing solutions are restricted to parametric models, e.g., linear bandits and generalized linear bandits (GLB). In comparison, kernel bandits, which search for non-parametric functions in a reproducing kernel Hilbert space (RKHS), offer higher modeling capacity. But the only existing work in distributed kernel bandits adopts a synchronous communication protocol, which greatly limits its practical use (e.g., every synchronization step requires all clients to participate and wait for data exchange).
In this paper, in order to improve the robustness against delays and unavailability of clients that are common in practice, we propose the first asynchronous solution based on approximated kernel regression for distributed kernel bandit learning. A set of effective treatments are developed to ensure approximation quality and communication efficiency. Rigorous theoretical analysis about the regret and communication cost is provided; and extensive empirical evaluations demonstrate the effectiveness of our solution.

Published as a conference paper at ICLR 2023
LEARNING KERNELIZED CONTEXTUAL BANDITS IN A DISTRIBUTED AND ASYNCHRONOUS ENVIRONMENT
Chuanhao Li'
Huazheng Wang
Mengdi Wang" Hongning Wang'
Universitty of Virginia Oregon State University
Princeton University
{c15ev, htwp://wwwiiiiiiee edu huazheng. wangeoregonstate..e
mengddw@@rrnneeoon.ee
ABSTRACT
Despite the recent advances communication-efiiiennn distributed bandit learn- ing, most existing solutions are restricted to parametric models, e.g., linear bandits and generalized linear bandits (GLB). In comparison, kernel bandits, which search for non-pann con-paramttric functions in reproducing kernel Hilbert space (RKHS), of- fer higher modeling capacity. But the only existing work in distributed kernel bandits adopts synchronous communication protocol, which greatly limits its practical use (e.g., every synchronization step requires all clients to participate and wait for data exchange). In this paper, in order to improve the robustness against delays and unavailability of clients that are common in practice, we pro- pose the first asynchronous solution based on approximated kernel regression for distributed kernel bandit learning. A set of effective treatments are developed to ensure approximation quality and communication efficiency. Rigorous theoreti- cal analysis about the regret and communication cost is provided; and extensive empirical evaluations demonstrate the effectiveness of our solution.
INTRODUCTION
There are many application scenarios where an environment repeatedly provides a learner with set of candidate actions to choose from, and possibly some side information (aka., context) (Li et al.) 20100 bJ Durand al. 2018); and the learner, whose goal to maximize cumulative reward over time, can only observe the reward corresponding to the chosen action. This is often modeled as bandit learning problem (Abbasi- Yadkori et al., 2011 Krause & Ong 201T), which exemplifies the well-known apploiatiioneepplratttee
dilemma (Auer 2002). Various modeling assumptions have been made about the relation between the context for each action and its expected reward. Com- pared with parametric bandits, such as linear and generalized linear bandits (Abbasi- Yadkori et al. 2011 Filippi et al.) 2010), kernel/Gaussian process bandits (Valko et al.) 2013) Srinivas et al. 2009) offer greater flexibility as they find non-parametric functions lying become a powerful tool for optimizing black box functions based on noisy observations in vari- ous applications, such recommender systems (Vanchinathan et al.) 2014), mobile health (Tewari & Murphy| 2017). environment monitoring (Srinivas et al. 2009). automatic machine learning al. 2017). cyber-physical systems (Lizotte al. 2007 Li et al. 2016). etc. etc.
RKHS And thus they have
Motivated by the rapid growth in affordability and availability of hardware resources, e.g., computer clusters 1oT devices, there is increasing interest in distributing the learning tasks, which gives rise to the recent research efforts in distributed bandits (Wang et al. 2019 Huang et al. 2021 Li & Wang 2022aa b) [i et al. 2022 He al. 2022). where N clients collaboratively maximize the over- all cumulative rewards over time T". As communication bandwidth is the key bottleneck in many distributed applications (Huang et al., (013)), these studies emphasize communication efficiency, i.e., incur sub-linear communication cost with respect to time T, while attaining near-optimal re- gret. However, most of these works are restricted to simple parametric models, like linear bandits (Wagg et al., 2019 Huang et al.) 202 1 Li & Wang 2022a He et al. 2022) or GLB (Li & Wang. 2022b). The only exception is Li et al. 2022), who proposed the first algorithm for distributed ker- nel bandit that has sub-linear communication cost. They achieved this via a Nyström embedding function (Nyström 1930) shared among all the clients, such that the clients only need to transfer the embedded statistics for joint kernelized estimation. Nevertheless, in their algorithm, the update of

---

Published as a conference paper at ICLR 2023
the Nyström embedding function, as well as the communication of the embedded statisties, relies on a synchronization round that requires participation of all the clients. As is widely recognized in
distributed optimization (Low et al. 2012 Xie et al. 2019 Lian et al. 2018 Chen et al. 2020 Lim let al. 2020) and distributed bandit learning (Li & Wang 2022a] He et al. 2022), this design is vul- nerable to stragglers (i.e., slower clients) in the system, i.e., the update procedure of et al. (2022)
is paused until the slowest client responds. Due to device heterogeneity and network unreliability, this situation unfortunately is common especially at the scale of hundreds of devices/clients. Thus, asynchronous communication is preferred, as the server can readily perform model update when communication from a client received, which more robust against stragglers.
The main bottleneck in addressing this limitation of Li et al. (2022) lies in computing Nyström approximation under asynchronous communication. Specifically, during synchronization step, their algorithm first samples small set of representative data points (i.e., the dictionary) from all clients, and then lets each client project their local data to the subspace spanned by this dictionary and share statistics about the projected data with others. However, new challenges arise in both algorithmic design and theoretical analysis when extending their solution to asynchronous communication, since 'fresh' re-sample from the data of all clients is no longer possible, and each client has different copy of the dictionary due to the asynchronous communication with the server, such that their local data will be projected different subspaces, and thus causes difficulty in joint kernel estimation.
In this paper, we address these challenges and propose the first asynchronous algorithm for dis- tributed kemnelized contextual bandits. Compared with prior works in distributed bandits, our al- gorithm simultancously enjoys the modeling capacity of non-parametric models and the improved robustness against delays and unavailability of clients, making it suitable for wider range of ap- plications. To ensure the approximation quality and compactness of the constructed dictionary in asynchronous communications, we design an incremental update procedure tailored our prob- lem setting with variant of Ridge leverage score (RLS) sampling. Compared with the sampling procedure prior works (Li et al., 2022 Calandriello et al., 2020), this requires specialized treat- ments in analysis, since the quality of the current dictionary now relies on all previous asynchronous communications. Morcover, to enable joint kernel estimation, we perform transformations on the server side to convert statistics from different clients to common subspace, which to the best of our ledgl is also new in bandit literature. We rigorously proved that the proposed algorithm in- curs an Ö (2) communication cost, matching that Li et al. (2022), where Yr is the maximum information gain, while still attaining the optimal O(VTrr regret.
2 RELATED WORKS
There have been increasing research efforts in distributed bandit learning in recent years, i.e., mul- tiple agents collaborate in pure exploration (Hillel et al. 2013 Tao et al. 2019 Du et al. 2021), or regret minimization (Wang et al. 2019 Li & Wang/ 2022a bj. 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). However, most of these works assume linear reward functions, and the clients communicate by transferring the O sufficient statistics. For example, Korda et al.] (2016) considered a peer-to-peer (P2P) communication net- work and assumes that the clients form clusters, i.e., each cluster is associated with a unique bandit problem. Huang et al. (2021) considered a star-shaped communication network as in our paper, but their proposed basse elimination algorithm only works the fixed arm set setting. The closest works to ours are WWagg et al. (211)); Dubey & Pentland ()020) Li & Wang 2022a); ; He al. (2022), which propose event- triggered communication protocols to obtain sub-linea commu- nication cost over time for distributed linear bandits with a time-varying arm set. In particular, Li Wang (2022a) first considered the asynchronous communication setting for distributed bandit learning. Though their proposed algorithm avoids global synchronization (Wang et al. 2019). it still involves download to inactive clients. He et al. (2022) further improved their algorithm design and analysis, such that only the active client in each round needs to participate in communication.
In comparison, distributed kernelized contextual bandits still remain under-explored. Prior work in this direction assumes local communication setting (Dubey et al., 22020), where the agent im- mediately shares the new raw data point to its neighbors after each interaction, and thus the com- munication cost is still linear over time. A recent work by Li et al. (2022) addresses this issue by
2

---

Published as a conference paper at ICLR 2023
letting clients communicate via statistics computed using shared Nyström embedding function (Calandriello et al.) 2019: 2020). However, though their proposed algorithm attains sub-linear com- munication cost over time, relies on global synchronization operation similar to that of Wang et al. (2019) to update the embedding function and share the embedded statistics. In comparison, our proposed method in this paper effectively addresses this issue using novel asynchronous update procedure for the embedding function, making asynchronous kernel bandit learning possible.
3 PRELIMINARIES
3.1 PROBLEM FORMULATION
We consider learning system consisting of (1) N clients that directly interact with the environment by taking actions and receiving the corresponding rewards, and (2) a central server that coordinates the communication among the clients facilitate their learning. The clients cannot directly commu- nicate with each other. but only with the central server, i.e., a star-shaped communication network. At each time step E [T], an arbitrary client & E [N] becomes active and chooses an arm x; from candidate set A, S R" and then receives the corresponding reward feedback = fxx)) + 7), E R. Note that Ae time-varying and assumed be chosen by an oblivious adversary, denotes the unknown reward function shared by all clients, and f/2 denotes the noise. Moreover, under the asyn- chronous communication scheme considered in this paper, only the active client ét is allowed to communicate with the server, c.g., to send or receive updates, after its interaction at time step t.
Kernelized Reward Function Following Valko et al. (013), we assume the unknown reward function lies in the RKHS, denoted as H. such that the reward can be equivalently written as y/ = =_ o(x;) + Mr, where 0, E H. is an unknown parameter vector and ø R - H is a known feature map associated with H. We assume that `e is zero-mean R-suub-aaussian conditioned ((i,,,,, (1s)), 4,, x.). i.e., the o-algebra generated by previous clients, their pulled arms, and the corresponding noises. addition, there exists positive definite kernel k(-,)) associated with H. and we assume Vx E A = U4 that, ||x||A L and || S S for some L, 0.
Regret and Communication Cost The learning system's goal to minimize the cumulative (pseudo) regret for all N clients, i.e., RT = Et= Tt, where T2 = maXxe e(x) 0, - ( O... Meanwhile, the system also needs to keep the communication cost Or low, which is measured by the total number of scalars being transferred across the system up to time T.
3.2 KERNEL RIDGE REGRESSION & NYSTRÖM APPROXIMATION
Throughout the paper, we use D S [T] to denote set of time steps and [D] as its size. The design matrix and reward vector constructed using data collected at these time steps, i.e., (Xs, Jeee denoted as X [x.]TED R|PIxd and yD [y.]TED IPI, Applying feature map e(-) to each row of XD. we have &D |2lPix, where p denotes the dimension of H. and is possibly infinite.
Kernel Ridge Regression Since the reward function f is linear in H. one can construct the Ridge regression estimator for 0, as,
i ( AI) DDDD
where À > 0 the regularization parameter. This gives us the following estimated mean reward and standard deviation in the primal form for any arm x E A:
x(x) (x)
( 2D + +AI)
(Ø (DDYD)
(xx) v T
T P + AI) x(x).
Note that directly working with the possibly
I E IR" is impractical. Instead, using
the kernel trick (Valko al. 2013 Li al. 2022), we can obtain an equivalent dual form that only involves entries of the kernel matrix:
x(x)= (x(x)T (KDD + AT) yD
(1)
6(x) X 1 k(xxx) Ko(x) (KD,D XI) (x)(x)
3

---

Published as a conference paper at ICLR 2023
where (x) Φxd(x) [x(x,, x)].ED E PRII and KD = $ [k(X,, Xe )a, R/D x/PI
Nyström Approximation Though equation 1 avoids directly working in H. it requires computing the inverse of K D.D. which is expensive in terms of both computation cost (Calandriello et al. 2019).
i.e., O(T²) as [D] O(T), and communication cost (Li et al., 2022), i.e., O(T) {xx,, M/ SED needs to be transferred across the clients. Therefore, Nyström method is used to approximate equa- tion I so clients can share embedded statistics, which improves communication efficiency.
As Calandriello et al. y0 Li et al. (2022). we project the original dataset z to the subspace defined by small representative subset 8 C D, i.e., the dictionary, and the orthogonal projection matrix is defined as
Ps ( ( D = =B K5 E R
Taking cigen-decompositton of Ksss = UAUT E ||Six|S|, we can rewrite the orthogonal projec- tion Ps $ DUAA A A -1/2U dss and define the Nyström embedding function
=xx; = P/ ((xxxx)> = A U 1 sØ(x) K5 1/2 Ks(x),
5,5
which maps the data point x from R.d to R |1 Therefore, we can approximate the Ridge regression estimator on dataset DD as θ (Ps I
+ AII TyD), and equation as
-1
i(x) = S) (Zb + 21) -1 DDDDDD
(2)
((x) 1/2 x(x,x) xxx; S) ( Z Z ZD:s
ZDS + AI -
where ZD,S RID x|8| obtained by applying 2(: to each row of Xp, i.e. ZD; 1// Note that the computation of xi(x) and (xx) only requires the embedded statistics, i.e., matrix Zp ZD,s E R (| and vector Z LDDsyD Isl which makes joint kernelized estimation among N clients much more efficient in communication compared with equation I
METHODOLOGY
In this section, propose and analyze the first asynchronous algorithm for distributed kernelized contextual bandit problem that addresses the challenges mentioned in Section and name the re- sulting algorithm Seyne-KernelUCBB with its description given in Algorithm
4.1 ALGORITHM
We denote the embedded statistics used in the computation of equation by A(D; = ZD. ZD:s and b(D;S) == LDD to explicitly emphasize they are computed by projecting the data points from dataset D to the subspace spanned by dictionary S. We denote the sequence of time steps corresponding to the interactions between client and the environment up to time t as Ni(1) {1 S t ig = i} for E [7]. Throughout the paper, we reserve A as the index for communication, and use tę E [T'] to denote the time step when the k-th communication happens. Moreover, each client has a different copy of the embedding function and embedded statistics due to asynchronous communication, we use k(()) to denote the index of client i's latest communication with the server, up the k-th one: if client triggers the k-th communication, then k(i) k.
Arm Selection At each round t E [T]. client é, E [NV] selects arm x, from the candidate set Ae by maximizing the following upper confidence bound (line 5)
arg max (i(()) (x) + adg(t) (x)
xE.A,
where ( (x) and (g (x) are approximated mean and standard deviation of arm x's reward, computed using statistics Á ((DM())) Suúi)) and b(DA(G): Su(i)) that client received from the server during the k(i,) communication. Proper choice of a is given in Lemma 4.4
Throughout this paper, will often the set of indices D (or S) to refer to the actual dataset (x,, Us teep (or dictionary (x,, Vs hses) for simplicity.
4

---

Published as a conference paper at ICLR 2023
Algorithm 1 Asynchronous KernelUCB (Async-KernelUCh)
1: Input: a, q. communication threshold D > O, regularization parameter À > 0, (0, 1) and kernel function k):-))
2: Initialize approximated mean and variance jx) 0, (x) X-1/2 v fxx, x). dataset Do
0. dictionary So = 0, index of communication k = 0, and No(1) = for each client i E [N]
3: for = 1, 2, .... T do
4: Client & E [N] becomes active, and observes arm set Ar
5: [Client i,] Choose arm X A, according equation 3 and observe reward y/1
6:
// Set (4) = 1 U {t), and (i) = - for r
7:
if (E. (6)) of ((G)) (x,) > then
Denote AD; = (i.).) (o)g,,)()) and set k = +
8:
[Server >> Client i,] Send (X,, Velaes 1 Sk-1),
to client &
9:
[Client i,] Select ASk C AD2 via RLS sampling with probability -1)
// Set Sy = Sk-1 U AS
10:
[Client i,] Compute A Sk), b(AD(;
11:
(Client i, + Server] Send (x.: NEESS,, A(ADE; and b(A);; to server
Set D = D V AD2 [Server] Compute (Dxx Sk), (DD) ( St)) according to equation 5
12:
13:
[Server > Client i Send A (Dx; Sx), b(D;; S to client is
14:
[Client i,] Update B& (-) and ōx (-) using A (DE; Si,), b(Dz; according to equation
end if
16: end for
Event-triggered Asynchronous Communication After the interaction at time step f, (g(i)() and (-) (-) of active client in will only be updated if the following event is true (line 7):
22 B(L)) (x,) > D,
(4)
where D O denotes the communication threshold. This measures whether sufficient amount of new information has been collected by client i, since its lastest (the k(i,)-th) communication with the server. true, communication between client and the server is triggered (line 8-14), where the update procedure described in the following paragraphs will be performed. And this procedure also illustrated in Figure [
Dictionary and Embedded Statistics Update During the k-th communication, the server first sends its latest dictionary Sk-1, as well as its latest embedded statistics ( and b(Da-1; Sk-1), client (line 8), which is illustrated the blue lines in Figure 1 Then client in selects a subset AS₁ from the data it has collected since its lastest communication (line 9), i.c., ADR, which will be used to incrementally update dictionary Sc-1. This is done by sampling De.s ~ B(ūx.s) for each data point with time index E ADR, where Pk.. == go? (x,). - This can be considered
variant of Ridge leverage score (RL.S) sampling (Calandriello et al. 2020 Li
al. 2022). It worth noting that the only purpose of sending A (Dx-1; Sa-1) and b(Dx - Sk-1) is to enable RLS sampling with the latest (-). Otherwise, client ig whose lastest communica- tion with the server can be long time ago, would include unnecessary data points into AS₁ due to its unawareness of server's current status. We will demonstrate in the proof of Lemma 4.3 that our design here is necessary to obtain a compact dictionary under asynchronous communication. With the dictionary updated, client & computes the embeddings of its new local data, i.e., (AD+:S)) and b(AD;; Sx). and sends them, as well as AS₁, to the server (the yellow lines in Figure 1).
(-).
As shown in Figure [ the server stores: 1) the last received embedded statistics from each client i [N]. i.e., (NNey Sg()) E Rl X and b(N (i); Sg()) E [S ; 2) their corre- sponding dictionary Sgin- As mentioned earlier, due to asynchronous communication, the statistics from different clients are based on different dictionaries. which means they have different dimen- sions and thus cannot be directly aggregated as Li et al. (2022). We propose to transform the statistics from each client i [N] using the latest dictionary Sk. This based the fact that
5

---

Published as a conference paper at ICLR 2023
Dx
(Ninco (g))) (NVecc (g)))
(Messa (1)) b(Nigga Skro)
(Miwayy (M),) ((Nigan (N),
Server
Sk-1
Sp-1 U.SkK
5(Dx-118x-1)
A(D
S(N ((OV)()))
1(Dx-1.8k-1)
A5K
6(DR. 5k)
Client 4
Figure Illustration of asynchronous update of dictionary and embedded statistics
Nio (1):& = + N 2 (1) Su
P 1/2 D. (6)
1/2
P
1/2p1/2
1/2
ZNimco (6): TE(S). where the
SkO
Sum
S.
linear transformation Tk(O), pose. Hence, we have
Sc())
1112p1/2
1/2
Sk
A
1/2
U
Sg(
P $3 US.
1/2 serves the pur-
(N (i);8x) Te(), A (Ni Migio (g) TE()).
(5)
b(No (i); - -TTo),. (1); Sg()),
which makes the statistics received from all clients have the same dimension |S Then we compute Á(DA: Sk) Σ ( (i); Sk) and Sa) Σ b(N (i); (line 12), and send them to client i to update its UCB (line 13-14), which illustrated as the green line in Figure
4.2 ANALYSIS OF DICTIONARY ACCURACY AND SIZE
As mentioned earlier, the key low regret and low communication cost, is to have dictionary Sa that can accurately approximate the dataset Dj, while having compact size |S In this section, we show that this is possible with our update procedure in Section 4.1 First, we need some additional notations. We denote the total number of times up to time T that communication is triggered, i.e.,
the number of times equation 4 is true, as B, where E [0. TJ. Following Following(Calandriee Calandriello et al. (2020);
Li et al. 2022). the approximation quality is formally defined using c-accuracy: if the event
{(1 (1-+)( D. DD. + AI) < D.S.S S. + AI (1 + () dD. + +X)]
(6)
true, then we say the dictionary S₁ is e-accurate w.r.t. dataset DR. for some e E (0, 1), where
S IXPail denotes diagonal matrix, with s-th diagonal entry equal Ik.s / VvP Pk.s. where
Ib.. if Sg. and qk = 0, otherwise. Based on this notion, we prove Lemma 4.1 below.
Lemma 4.1 (Dictionary Accuracy and Size). With q 1nn2222T/))5
c/3)/e², where B = (1 + c) (1]--,), c). and S k(xx, x), Vx E A, we have with probability at least 1 that dictionary Se is e-accurate w.r.t datase! Di. and its size [S&] < 12 + 3 (YT Vk: where d E (0, 1).
This shows that our incremental update procedure under asynchronous communication still matches the results in prior works that perform synchronous re-sampling over the whole dataset for dictionary update (Li et al.) 2022 Calandriello et al., 2222)). We provide a proof sketch for Lemma 4.1 below highlight our technical novelty and provide the detailed proof in appendix.
Let's define the unfavorable event H₁ A U Ex. where A₃ is the event that the dictionary Sy is not e-aceurate w.r.t. DE. and Eg is the event that the size of dictionary |Sx| > 123(1 + 3D) Therefore, the probability of Hy can be decomposed as
Proof Sketch of Lemma 4.1
IP (( As) + IP (PU
n (b)))
Bounding the first term: In Calandriello et al. (2019 2020 Li et al. (2022), the first term is further decomposed as PP P & Σe P(Ar n A because dietionary Sg. is constructed by

---

Published as a conference paper at ICLR 2023
fresh re-sampling over Dj: using the latest approximated variance o (-), and thus they only need guarantee (-) is a good approximation to - In our case, St is incrementally updated in each communication, i.e., S = where each ASμ is sampled using ( The accuracy of Sy depends on the accuracy of every Sk. i.e., - Ag. Therefore, we decompose A = - - ((A m A I
-( using Bayes theorem and Weierstrass product inequality, and bound each conditional probability separately, which leads to Lemma 4.2
AG)
Lemma 4.2 (Bounding Ee PP PAAx AG)). By setting q 41 we
have E P(A 0g AG) 6/2, for 5 E (0.1).
Bounding the second term: The second term can be decomposed as PUU s
Σ P(Ea n (n (1)) Note that the size of dictionary |S E.ED. Ih by the definition of ae... and its analysis relies on upper bounding E.ED, Pk., (Calandriello et al. 2020). Again, due to asynchronous communication, for data point s that was added during the -'thh communication,
i.e., E AD=, we have 9k.s .s' Pk.. Pk',s and thus EeED, Pk.s Σ =k'=1 ErEAD. PW... Compared with Li et al. - (Xg), we use a different approximated variance function for each ASpr Nevertheless, with our design in Section 4.1 i... Pk - (Xx). show in Lemma
2 Calandriello et al. (2020) that re-sample all DA using Pk.s =
4.3 that we can still ensure |Sx| = (+T), as long proper threshold D is chosen to avoid any AD being too large.
Lemma 4.3 (Bounding Ei (E& (n -())()))))))))))))))))))) By setting q = 4 4222(2222//000)) and À < k(x, x), Vx E A. we have Ek= P (En n (n R ( - 6/2. 8 E (0.
e/3)/e.
Putting everything together, we have Pl H&) S 6, for 5 E (0, 1), which finishes the proof.
4.3 ANALYSIS OF REGRET AND COMMUNICATION COST
Lemma guarantees a compact and accurate dictionary for Nyström approximation throughout the learning process. Based on it, we establish the upper bounds for the cumulative regret and com- munication cost of Asyne- KernelUCB. First, motivated by the confidence ellipsoid for asynchronous linear bandits (He et al. 2022). construct the following confidence ellipsoid for our approximated estimator for kernel bandit defined in Section 3.2 (proof is provided in appendix).
Lemma 4.4 (Confidence ellipsoid for approximated estimator). Under the same condition as with probability at least 26. for (0,1), we have Vk that
Lemma 4.1
100 0-llv, S (1/V11 1)VAS 2R(VI++ND) N 2D3)
(1(118)) + 7T a.
where V = Ps the maximum information gain after T interactions (Chowdhury & Gopalan 2017 Li et al. 2022
P $ TD DD. + +I and "r == max - log det D D (DSA)= I
(
Then based on Lemma 4.4 we establish Theorem 4.5
below (proof is provided in appendix).
Theorem 4.5. Under the same condition as Lemma
4.1
we have
Rr < 4S + AV - 1)vAs NDD N 2D3) / (n(8/) + +
T3 NB(22/A Dihr
with probability at least 1 - 25, and
Cr S 2rr(N + ( (Sa)) + d[Sæl].
where the dictionary size [Sal < 128 3D) due Lemma 4.1 By setting D 1/N2, have Rr = OSNTLS + VT(S + YT)), and CT = Ö 7.)).
2 As discussed in Li et al. (2022), Pr is problem-dependeee showing how fast kernel's eigenvalues de- cay. For kemels with exponentially decaying cigenvalues, i.c., Am = O(exp(-m*=) for Be > 0, "r = Oloo'++111100 1+18/ (T)), which includes Gaussian kernel that is widely used for GPs and SVMs. For kernels with polynomially decaying eigenvalues, i.c., An O(m [0()) for Bp > 1, TT O(T 1/g
7

---

Published as a conference paper at ICLR 2023
5 EXPERIMENTS
To validate Async- KerneUUCB'e s in reducing communication cost, we performed exten- sive empirical evaluations on both synthetic and real-world datasets, and reported the results (over 10 runs) in Figure 2 The baselines included in our comparisons are: 1) OneKernelUCB (Valko et al. 2013). it learns shared kernel bandit model across all clients' aggregated data where data aggregation happens immediately after each new data point becomes available: 2) NKernelUBB.
learns a separate kernel bandit model for each client with no communication: 3) FedGLBUCB (Li & Wang 2022b), is synchronous distributed GLB algorithm; 4) DCs (Wang al. 2019).
it is synchronous distributed linear bandit algorithm; 5) FedLinUCB (He et al.) 2022). it is an asynchronous distributed linear bandit algorithm: and 6) Approx- DisKernelUCB (Li et al. 2022). is synchronous distributed kernel bandit algorithm. For all the kernel bandit algorithms, we used the Gaussian kernel (a 2) - exp(-7||ı - y/l²), where we did a grid search of 7 E {0.1, 1, 4). and for FedGLBUCB, all algorithms, instead of using their theoretically derived exploration coefficient a, we followed the convention Li et al. (2010a); Zhou al. (2020) to grid search for in {0.1, 1,4].
used Sigmoid function μ=(=) (1 +1++ exp(-2))
link function. For
5.1 EXPERIMENT SETUP
Synthetic dataset We simulated the distributed bandit setting in Section 3.1 with d = 20,7 = 10 .N- 102. At each time step f [T], client in E [N] selects an arm from candidate set Ar (with [Ai = -00), which is uniformly sampled from & unit ball. Then the reward is generated using one of the following reward functions: 1) fi (x) = cos(3x' 0.), and 2) (x( = (x 0,)3 3(x 0,
(x 0.) 33 where the parameter 0, is uniformly sampled from a &2 unit ball and fixed.
UCI Datasets We also performed experiments using MagicTTelescope and Mushroom from the UCI Machine Learning Repository (Dua & Graff] 2017), which are converted to bandit problem follow- ing Filippi et al. (2010). Specifically, we partitioned the dataset into 20 clusters using k-means, and used the centroid of each cluster as the context for the arms and used the averaged response as mean reward (the response is binarized by setting one class as 1, and all the others as 0). Then we simulated the distributed bandit setting in Section 3.1 with |,, = 20, T 10 and N 102.
MovieLens and Yelp dataset Yelp dataset is released by the Yelp dataset challenge, and consists of 4.7 million rating entries for 157 thousand restaurants by 1.18 million users. Movielens consists of 25 million ratings between 160 thousand users and 60 thousand movies (Harper & Konstan 2015). Following the pre-processing steps in Ban et al. (022)), we built the rating matrix by choosing the top 2,000 users and top 10,000 restaurants/movine extract a 10-dimension feature vector for each user and restaurant/movve. We treated ratings greater than 2 as positive, and simulated the distributed bandit setting in Section 3.1 with T = 10 and N = 10?. The candidate set Ar (with Ael = 20) is constructed by sampling an arm with positive reward and nineteen arms with negative reward from the arm pool, and the concatenation of user and restaurant/movie feature vector is used as the context vector for the arm (thus d = 20).
and used singular-value decomposition to
5.2 EXPERIMENT RESULTS
OneKemelUCB and NKernelUCB correspond the two extreme cases where the clients either com- municate in every time step to learn a shared model, or they learn their own models independently with no communication. As shown in Figure 2 OneKernelUCB achieved the smallest cumulative regret in almost all experiments. but also incurred the highest communication cost, i.e., O(T due to sending each new data point all clients every round, which demonstrates the necessity of communication efficient bandit algorithms. On the other hand, distributed linear bandit algo- rithms, e.g., DisLinUCB and FedLinUCB, incurred very low communication cost as they directly communicate via the d x d statistics, but fail to capture the complicated reward mappings in most of these datasets, e.g., in Figure 2(d) they even had much worse regret than NKernelUCB that requries no communication. Equipped with logistic function, distributed GLB algorithm FedGLBUCB at- tained both low regret and low communication cost on the two classification datasets, i.c., Figure 2(c)am and Figure 2(d) but required many iterations of distributed gradient updates to converge on the other four datasets where logistic function may not fit, and led to huge communication costs. In comparison, Kesroe- and our proposed Asyne-KerneIUCC had consistently smaller
8

---

Published as a conference paper at ICLR 2023
OneKerneliia
NKKrnelucaa
FadGLBUcE
DisLintiC
FedLinUCB
ApproxBiiSKrrellucc
AsyncKemelUCaa
1000
Regret
Regret
Rogret
500
1e6
1e6
1e6
Communicatan
Communicataan
4
2
5000
10000
5000
10000
(a) fi (x)
(b) fx(x)
(c) MagicTelescope
2000
500
Regret
Regeet
Hogret
500
1000
1e6
1e6
1e6
Communication
Commu unicatiu
Commmicction
2
2
5000
10000
5000
10000
5000
10000
(d) Mushroom
(c) Moviel.ens
(f) Yelp
Figure Experiment results on synthetic and real-world datasets.
regret than their linear counterparts, while requiring relatively lower communication cost for joint kernel estimation. It is also worth noting that despite having the same ((N2)²) theoretical scaling communication cost, while having comparable or even better regret than Approx-DisKermelUCB..
incurs much smaller communication cost empirically,
CONCLUSIONS
In this paper, we proposed the first asynchronous algorithm for distributed kernel bandit, which relaxes the limitation prior work that requires impractical global synchronization update the Nyström embedding function and share the embedded statistics across all clients. To ensure approx- imation quality and compactness the constructed dictionary asynchronous communications, designed an incremental update procedure tailored to this communication scheme, and transfor- mation operation on the server side to enable joint kernel estimation using statisties with different embeddings. With the improved robustness against delays and unavailability of clients by having asynchronous communication, we show that to attain near-optimal regret, the proposed algorithm still only incurs an Ö(N2)3) communication cost, matching that of the prior work.
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 appli- cable lower bound states that, in order have smaller regret than the trivial O(vNT) result, i.e., run N instances of optimal bandit algorithm with no communication, ?((N) communications is neces- sary (He et al. 2022). In comparison, bound is in order to attain the optimal O(VT) regret. Moreover, motivated by the differential private (DP) version of DisLinUCB by Dubey & Pentland (2020). i.c., apply randomized mechanisms the shared sufficient statistics, another interesting direction a DP version of our Asyne- KernelUCB, in which case, the main focus is prreeecvigeeeiiigggg construction of the shared embedding function.
more interesting to know what the communication lower

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
Hongning Wang acknowledges the support by NSF grants IIS-2213700, IIS-2128019 and IIS- 1838615, Mengdi Wang acknowledges the support by NSF grants DMS-1953686, IIS-2107304, CMM11653435, ONR grant 1006977, and http://C3.AI.
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24:2312- 2222200, 2011.
Peter Auer. Using confidence bounds for exploitaiion-exploraiion trade-offs. Journal of Machine Learning Research, 3(Nov):397-43) 422, 2002.
Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Ec-net: Exploiationneexplration neural networks in contextual bandits. arXiv preprint arXiv:2110.03111 2021.
Daniele Calandriello, Alessandro Lazaric, and Michal Valko. Second-order kernel online convex optimization with adaptive sketching. In International Conference on Machine Learning, pp- 645-653. PMLR, 2017.
Daniele Calandriello, Luigi Carratino, Alessandro Lazarie, Michal Valko, and Lorenzo Rosasco. Gaussian process optimization with adaptive sketching: Scalable and no regret. In Conference on Learning Theory, pp. 533-557. PMLR, 2019.
Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco. Near-linear time gaussian process optimization with adaptive batching and resparsification. In International Conference on Machine Learning, pp. 1295-1305. PMLR, 2020.
Yujing Chen, Yue Ning, Martin Slawski, and Huzefa Rangwala. Asynchronous online federated learning for edge devices with non-iid data. In 2020 IEEE International Conference on Big Data (Big Data), pp. 15-24. IEEE, 2020.
Sayak Ray Chowdhury and Aditya Gopalan. On kemelized multi-armed bandits. In International Conference on Machine Learning, pp. 844 853. PMLR, 2017.
Yihan Du, Wei Chen, Yuko Yuroki, and Longbo Huang. Collaborative pure exploration in kernel bandit. arXiv preprint arXiv:21 2021.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URLattp://archivee ics. wci.ccicc edu/m
Abhimanyu Dubey and AlexSandy' Pentland. Differentialll--riivee federated linear bandits. Ad- vances Neural Information Processing Systems, 33, 2020.
Abhimanyu Dubey et al. Kernel methods for cooperative multi-agent contextual bandits. In Inter- national Conference Machine Learning, pp. 2740-2750. PMLR, 2020.
Audrey Durand, Charis Achilleos, Demetris lacovides, Katerina Strati, Georgios D Mitsis, and Joelle Pineau. Contextual bandits for adapting treatment in a mouse model of de novo carcino- genesis. Machine learning for healthcure conference, pp. 67-82. PMLR, 2018.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In NIPS, volume 23, pp. 586-594, 2010.
F Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis) 5(4):1-19, 2015.
Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu. A simple and provably efficient algorithm for asynchronous federated contextual linear bandits. arXiv preprint vrXiv:2207.03106 2022.
Eshear Hillel, Zohar S Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. Distributed explo- ration in multi-armed bandits. Advances in Neural Information Processing Systems, 26, 2013.
10

---

Published as a conference paper at ICLR 2023
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Junxian Huang, Feng Qian, Yihua Guo, Yuanyuan Zhou, Qiang Xu, Z Morley Mao, Subhabrata Sen, and Oliver Spatscheck. An in-depth study of Ite: Effect network protocol and application behavior on performance. ACM SIGCOMM Computer Communication Review, 43(4))363-374 2013.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. Advances in Neural Information Processing Systems, 34, 2021.
Nathan Korda, Balazs Szorenyi, and Shuai Li. Distributed clustering of linear bandits in peer to peer networks. In International conference on machine learning, pp. 1301-1309 PMLR, 2016.
Andreas Krause and Cheng Ong. Contextual gaussian process bandit optimization. Advances in neural information processing systems, 24, 2011.
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, 2022a.
Chuanhao Li and Hongning Wang. Communication efficient federated learning for generalized linear bandits. arXiv preprint arXiv:2202.01087 2022b.
Chuanhao Li, Huazheng Wang. Mengdi Wang, and Hongning Wang. Communication efficient dis-
tributed learning for kernelized contextual bandits. arXiv preprint arXiv:2206.0483) 2022.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bande approach to personalized news article recommendation. In Proceedings of the 19th international conference World wide web, pp. 661-670, 2010a.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel hunditt-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1):6765-681 2017.
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, pp. 27-36, 2010b.
Xinbin Li, Jiajia Liu, Lei Yan, Song Han, and Xinping Guan. Relay selection in underwater acoustic cooperative networks: A contextual bandit approach. IEEE Communications Letters, 21(2):382- 385, 2016.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, pp. 3052-3052. PMLR, 2018.
Wei Yang Bryan Lim, Nguyen Cong Luong, Dinh Thai Hoang, Yutao Jiao, Ying-Chang Liang, Qiang Yang, Dusit Niyato, and Chunyan Miao. Federated learning in mobile edge networks: A comprehensive survey. IEEE Communications Surveys Tutorials, 22(3):2031-2063 2020.
Daniel Lizotte, Tao Wang, Michael H Bowling, Dale Schuurmans, et al. Automatic gait optimiza- tion with gaussian process regression. In IJCAI, volume 7, pp. 944-949, 2007.
Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrin, and Joseph M Hellerstein. Distributed graphlab: A framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment, 5(8), 2012.
Event Nyström. Über die praktische auflösung von integralgleichungen mit anwendungen auf randwertaufgaben. Acta Mathematica, 54:185-204, 1930.
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:09/2.3995, 2009.
11

---

Published as a conference paper at ICLR 2023
Chao Tao, Qin Zhang, and Yuan Zhou. Collaborative learning with limited interaction: Tight bounds for distributed exploration multi-armed bandits. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 126-146. IEEE, 2019.
Ambuj Tewari and Susan A Murphy, From ads interventions: Contextual bandits in mobile health. In Mobile Health, pp. 495-517. Springer, 2017.
Lin Tie, Yui-Yuan Cai, and Yan Lin. Rearrangement inequalities for hermitian matrices. Linear algebra and applications, 434(2):443 456, 2011.
Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time
analysis of kernelised contextual bandits. arXiv preprint arXiv: (30.66690966699 2013.
Hastagiri P Vanchinathan, Isidor Nikolic, Fabio De Bona, and Andreas Krause. Explore-exploit in top-n recommender systems via gaussian processes. In Proceedings of the 8th ACM Conference on Recommender systems, pp. 225-232, 2014.
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near- optimal regret with efficient communication. In International Conference Learning Represen- tations, 2019.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. arXiv preprint arXiv:1903.03394, 2019.
Houssam Zenati, Alberto Bietti, Eustache Diemert, Julien Mairal, Matthieu Martin, and Pierre Gail- lard. Efficient kernel ucb for contextual bandits. arXiv preprint arXiv:2202.056388 2022.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pp. 11492-11502, PMLR, 2020.
12

---

Published as a conference paper at ICLR 2023
A
TECHNICAL LEMMAS
Lemma A.I (Lemma 11 of Abbasi-Yadkori al. (201 ) Let {x)]i=1 be a sequence RRd V
Rdxd a positive definite matrix, and define Vi2 = + E.=1 == X,X J. Then we have that
de dct
In
x S L, Vt, and Amiu (V) max(1, 1, )2 then
Σ x [ s 21n det Vn))
(V)
Lemma A.2 (Lemma 12 of Abbasi- Yadkori al. (2011)). Let A, and C be positive semi-definite matrices such that A = B + C. Then, we have that:
Ax
det(A)
sup x=0 X
Bx
det(B)
Lemma A.3 (Lemma A.2 of Li et al.
(2022)) ). Define positive definite matrices A = =I $ Φ1 +
1 22 and = AI + $ 4,, where 4b 11, 42 D2 E TRPx and p is possibly infinite. Then, we have that:
Φ T AA
det (
sup
Ø BΦ
det [I + k=
0=2
{ 42
where K
4 and KB 2
Lemma A.4 (Eq (26) and Eq (27) of Zenati et al. 2022 ). Let { be a sequence in RP, V E RexP a positive definite matrix, where p is possibly infinite, and define V V E 2.07 Then we have that
Emin(1 (1 S 2l
where Kv, the kernel matrix corresponding to V, as defined in Lemma A.3 Lemma A.5 (Lemma 4 of Calandriello et al. (0200). For 1. > I', we have for any E Rd
xx) S oz < (1 +
Σ (x.))
Lemma A.6 (Lemma 6 of Calandriello et al. (2019)) ). Sp is c-accurate w.r.t. DR. then
1-6 (x(x) < mi) < + x²(x)
1
for all x E Rdd
Lemma A.7 (Proposition of Calandriello et al.
2019
Let GI.... Gr be sequence of inde-
pendent adioind random operators such that G. have
0 and |G S R. Then for any we
2/2
P(I P(I G.
22
< 4t exp
E|G || + Re/3
Lemma A.8 (Proposition of (Calandriello et al. random variables, each with success probability p..
2019 Let {gots-n be independent Bernoulli Then we have
P
9
Pe) S exp( Σ Pa). Pp))
Lemma A.9 (Corollary 7.7.4. (a) of Horn & Johnson (2012)). such that A > B, then we have
Let A, B be positive definite matrices,
A-1 < B-1
Lemma A.10 (Lemmaa 2.2 of lie et al. C, holds that det(A + B C) det A) det(A + B) det A CC).
(011T). For any positive semi semi-definite matrices A, B and
13

---

Published as a conference paper at ICLR 2023
B PROOF OF LEMMAS IN SECTION 4.2
Let's define the unfavorable event H = A₂ U Ex. where A is the event that the dictionary Sş is not c-accurate w.r.t. Du, and Eg is the event that the size of dictionary |Sx| is large, i.e., | > 123(1 + 3D)Trr. Therefore, we want to bound the probability of U o Hk. which can be decomposed as
H() = P( U Ex)) =
-P
P(UR=O Fx) P( (o)
= =P(UR 4x) + +P(LUL Ex) (4)
Note that, as in Calandriello et al. (017)) we bound the second term as P( n (UR Ax) P E&) n (N 45) P(ug_olEe n ( I En P(Ex On ( For the first term P Az)) we need decomposition different from prior works Calandriello et al.) 2017 (011), since our dictionary is incremenially updated with batch of sam- ples at each communication round (line 9 in Algorithm D Specifically, when bounding the probabil- ity of having inaccurate dictionary at the k-th commumication, i.e., event Ag. need to condition on the event that dictionaries all previous communications are e-accurate, i.c., event Mi - -
k- AC
Hence, we decompose P As) = (nn 4g) = P(A)) I P(4 I AG)
A |AAc -===0 A S E P(Ax) n AC). where the second equality is due to Bayes theorem, the third equality is because Do P P(4)) = and the inequality is due Weierstrass product inequality. Putting everything together,
0 is well-approximated by So = 0, and thus
have
B P(UR HB) EP(AA
A
Σ E(
Then we can upper bound these two terms using Lemma 4.2 and Lemma 4.3 given in Section 4.2 which leads to H I 6, for 5 E (0, and thus finishes the proof of Lemma 4.1
Proof of Lemma 4.2 bounding Σk= P(AsI n AG). As Calandriello al. (0119) we can rewrite the event Ag, based on the definition of 6-accuracy given equation 6 as
A = 011
Gk.e >c
SED
where Gk.s (P..
1,, and tik.. ( DD PD. + AI) -1)_1/2((xs). Then let's define
F& := (9k..r Masheee DoDD,, for E [B], which contains all randomness in the construction of S₃ during the k-tth communication. With conditioning, we have
P(AR n (A)) = =P([I Σ
GR.ell > e n
A = EF [1ll Σ
GR.ell > {} i A
SED
SED
= Ex, BA [1(1] Σ
GR > Fk 1 A
sED
=Ex, 1ntt' Ag. EA [1(1l Σ
Gk > FF
sED
-B AC. [PAAFLL
(
1) V. > e Fx-1)]]
Pk.s
sED
where the third equality holds because when conditioned on the event nf AG, the outcomes asso- ciated with the complement of this event have zero probability, and thus we can restrict the expecta- tion to the outcomes where the event nf- AC holds.
Consider the k-th communication for A E [B]. We denote the client who triggers the k-th com- munication as C₁ E [N], and the time step when the k-th communication happens as tx E [T). In addition, recall that we denote the sequence of time steps in-between client c₁ last communication (whose index is denoted as k((x.) E [0, 1)) and the current (the k-th) communication when client
Ck's is is active as AD, Nr. (cx) /Nixcas (cx) (1u(cw) < & le = cx).
14

---

Published as a conference paper at ICLR 2023
Note that due to incremental update procedure, for some data point with time index 8, that was added into D during the k' communication (sent to the server in the form of embedded statistics), L.., 8 E ADK, for k' = I.....k, k, we have Is,s .s's and Pk.. ,s. When conditioned on Fk-1, fK.s for all E Dx are independent Bernoulli random variable with mean jk.,s, because they only correlate via the approximated variance function(s) that were used for arm selection and RL.S sampling to the k-th communication, which are deterministic conditioned on Fk-1, and thus both a and t are deterministic as well.
9he $ 1 e(FR-1) using Lemma A.7 Therefore, we can bound FEE (IIE Pu.. First, we need to show that each term the summation has zero mean and bounded norm, I.C., Ex.iee, (Gx, [F 0 and ||GR,sl| || S R for some constant It:
UK.. 1) oT. = BRAFi [ 1) 0,
BAA [(
Pk.
Ph,s
and
xx(x))
||GK,oll ||
|1( Te,
1 S
2e.0
1)llek,,
Pk.s
pkia
Pk.s
where the last inequality is because Is.s S. and 1 VTTall = Wh Vhe =x)(xx) As mentioned
earlier, for 8 E ADx, k' = I,...,k, k. we have Pk.s DM = (x.)- i.e. during the k'- th communication, client e-' first receives server's latest statistics to compute (.) for RLS sampling. Conditioned on =0 and by Lemma A.6 we have (xx) 0 (x.)333
where / := (1 e) - c). Hence,
(xx))
(x))) -0%
3 (x))))
8
||GR,all
R.
Pk.s
q o (x))
9
where the last inequality is because the variance is non-increasing over time. Then by Lemma A.7
2/2
P PAA (11 Σ GA,oll > c(Fx-1) s 4/4x | |EEED. B G2 ki F + Re/3'
sED*
Now we need to further upper bound the term
1EEDD, E IG FF i|ll. First, note that
BAA 1 EFA,F
_1 [hi
1) 1/
1h w/. Wh [a
Pk.s
=ExA/F [(
1h Vx Uk 12.00 1)
Pk,s
and EF (F-
[x2 =
E (0 )[FFs1)) - 2E /
F + Pk.
We.
Ex. [e-1
[k-1]]
1-1
1
Substituting this to the RHS, we have pe.a"
pe.
1
1 1
GAAA-,lRR... kio
3
th 2o Th TT
W..l 3 Rubn.atb.e Ph.s
Pk,s
and thus,
||
Σ
< R|| Σ
tha
sED
R||
+ D.
PD. + +II 1/2
+ Dr
PD. + AI) 11/2
R|[ T D2
4DD + AT)
1/2 TT,
4D,
+ D2 DD. + XI) - 1/211 < R
D2
where the first equality is by definition of thk.s- Putting everything together, we have
2/2 9
PAAFFL (1) Σ
Gk > c(Fx1)) < 4 exp(
1 c/3 3
SED
15

---

Published as a conference paper at ICLR 2023
and thus PAAc | 10 A&) S 4/2x) exp(-
2//2
().
Summing over terms, we have
I++/3
Σ P [(x) k'=0 A S eepp
22/2
9
Σ
B
D2l
S 2T exp(
2/2
1+ c/3
B
1 1 e/3 3
O
Am
In order to make sure Σx IP P(As)
k-1 A < 1. we need to set g = 43
In( (2
Proof of Lemma 4.3 bounding Ci (n First, note that P(E n (n k= 10) 0, because So = 0. and by definition of gk.s for E Dx. the size of dictionary |S = LEED. Gh We formally define unfavorable event Ex as
Ex Σ Th > 123(1 + 3D) BEDμ
where = - c). Similar to Calandriello et al. 20117 2019). we will use a stochastic
dominance argument to upper bound the probability of event Ex. First, use conditioning again to rewrite P(Ee n (n 1)) as
P(E& n (n 40) = P(E I0 B F( s P(E, 1
R=1
= Σ Th. 2 ( A()
=
= EE,, 1 1f [PAAFLL (E Ta. 2 12 + BD) | [Fx-1)]- BED2
As discussed earlier, when conditioned on Fk-1. &s for s E D3 becomes independent Bernoulli random variable, with mean Pk... In addition, (line 9 in Algorithm D]. the partition in D3 that were added during the k'-th communication for k' E 1, ,,....,,, k which is denoted by ADK, is sampled using - (x,) for E ADR. Hence,
result of our incremental dictionary update
BywFi Σ Ok [F = Σ
pk.s
sED
SED
Pwis = Σ Σ
t (xxs)
#=1 sEAD
=== BEADU
k
S 3q Σ
Σ
Th (X,) = 3q Σ
Σ
0 1xs))
Tf 1 (Xx)
k= BEAD
#= BEAD
S 0
Σ
T (x.)
Σ
Th (xx'))
W == SEAD
BEAD Sa-1
$ 89
Σ
-
(2, .1
Σ
W= B=DD
o DEADHIS'S
$ 9q
Σ
Σ
oh
1.--111( (x.) -1 9
22 (x,z) s' S'AAD Ss-1
W= SEAD
s 811 + BD)q
Σ .
6 1 Σ
where the imaginary variance function of -. is constructed using dataset (U (U ADx) U {s' E AD : ss' << - 1} (not computed in the actual algorithm); the first and forth inequality is due to Lemma A.6 as we conditioned on 46; the second is due to Lemma A.5) the third is because 1/ (((ck) I k'' -- and the variance is non-increasing over time; and the fifth is due to our event-trigger design in equation 4 i.e., ExEAD o oiley) (x.) D.
16

---

Published as a conference paper at ICLR 2023
Now for each term in the summation the RHS of the inequality above, introduce an inde-
pendent Bernoulli random variable ÿk.s ~ [3 + 3D) (x,)). Since 9k.s stochastically dominates ak i.e., E[gn, Fx-1] =Pk,.
Pk,. S 3(1 + 3D) -..-11 (x.) =B B[ we have
P Σ gk.s > 12 + BD) (Fk-1) & ( Σ
ak. > 12 + +DD)gr))
SED
sED
Then further upper bound the RHS
P
ax.s 12 + (D)
P
t > 38(1+ BDDG E
E
ok -
SED, D
k==1 SEADY
S exp (-23(1 + BD
k= SEAD
where the first incquality is because second inequality is due to Lemma A.8
Σ
E EVEAD, -101 - 4yr, and the By substituting $ =
48 4 In 2v@r)
we have To ensure Ex= EMEAD 1 2 1, we can set < x(x,x),, Vx E A. Finally, by summing over B terms, we have
and under the condition that Σx= EVEAD, -
2
exp(-2.(1 + BD) EOEAD o 1,-11,-100 (x.)) S (oo--I(872/5))
B P < T exp(ppppppp (n(8T216)) ST. 8
87 2
k=0
where the last inequality is because T 2 1.
C PROOF OF LEMMA 4.4 IN SECTION 4.3
Recall from Section 3.2 that the approximated kernel Ridge regression estimator for O, is defined as
0% = VE Ps. 2 DD DDD
where V& = Ps. + T
1 D. Ps. + AI. Then we can decompose
D.
||0 0.13 Vx
= (0:: 0.) V (
0.)
=(0) - 0.) VA E Ps.. 2
D.D. - -0,)
=(0= -0.) V& V Pss. $ Lb. PD. mDD.) -0.]
=(0+ 0.) V Ps. 1 D.
LD. 0, - 0+) + (0) - 00)) ( TPs, TT 1DD
A
Aa
Since V.(VE k Pss. TT. 4D, 0, - 0.) = Ps. 4 Dr DD, 02 Pss. Dr LD,
Dj. Pss 0. - 202
Ps. $ D.
4 D. (I Ps, )0. 10., we have
A (0% P.s
Ps. S. TT, DD. (I 1- Ps, 100 -0.)
(0 0.) /2 1/2 Ps. LD
P (I - Ps,0.. - 2(0x - 0.) VV V. 1/29.
< 10 1lv. (IVV 1/2 Pss. + D2
$ D (I PPs )0 + Al00llvE')
10 0. 1l,, (IV, 1/2 1/2Ps, $ D2
D [I I-Ps. M1111111 v\llee_1)
10 0.llv. (1 (I-Ps.) Ps..)
|__||
17

---

Published as a conference paper at ICLR 2023
where the first inequality is due to Cauchy Schwartz, and the last inequality is because V
1/2 Ps. Db V PD,,Ps (Ps. D, Ps, + PPs Do. S 1. Then by definition of the spectral norm I|, and the properties of the orthogonal projection matrix Psa, we have
1 (I Ps.) Amaxx (DD, (I Ps.) 2 V Amax D2 (I Ps (D))
Moreover, due to Lemma 4.1 Sk is 6-accurate w.r.t. DR. for all k. so we have Ps.. I-c ( LD. + A by the property c-accuracy (Proposition 10 of Calandriello et al. (019
A
Substituting this RHS of the equality above, we have
A 1-e Amax DD
1DDD (I -1- Pss)
V 1-6 DD. + 1 D. 2 DD
Therefore, A S 100 0.llv, (V T_e +1)VX10-11
Similarly, by applying
inequality on term A2, we have
A = (0p 0.) V 1/2 1/2
S. Dr 11,, S 1 0,1lv, VV 1/2 Ps. Pp.m
D T
= =10g 0.llv. VV
1/2
D. nD,1l
< 0 - -0.1lv, VV
1/2
Pss.
S.
V
1/2 T
Dr TD,
where V2 = Φ Di LD. + AI. Note that Ps. VA, Ps.
Ps. ( LD. +AI)Ps -V++
I) and Ps. = I, so we have
1/2 v1/²1 VIV 1/2 V1/2v1/2 PP, V-1/111 S /
X(Ps. I))
AVV (Ps. I 1/2 1 / VI Ps. -I
s -11 11
and thus A2 S 22100 0.1 v. IV 1/2 TT TP.1-
As mentioned by He et al. (2022). the standard self-normalized bound for vector-valued martingales cannot be directly applied to bound the term |V D. "/,,,, since Da is constructed by the data that each client has uploaded so far during the event-triggered communications. Therefore, in the following paragraphs, we bound this term by extending their results to the kernel bandit problem considered in our paper.
We first need to establish the following lemma.
Lemma C.1. Let's denote V&(1)= = E.EN goo (1) ((xx)((xx)) such that V === V&(1), and then denote the covariance matrix for client i's data that hasn' been uploaded to server by time step t AV ExEN,,0WW ((xx) (xxx))(x))) for foric [N]. Then we have
(0)
1 AV
V
(8)
3D
and Vx IRd,
o(x) T (xx)
5 31+N3D.
(xx) ( [x] [w + -10x)
1/-11/27 / mp. Recall that Dr contains data points that N clients have uploaded up to the k-th communication, i.e., Dj UN N (i), where (2()) denotes the time step of client i's
Bounding -IV
18

---

Published as a conference paper at ICLR 2023
last communication with the server. Therefore, have the following decomposition
N
V 1/12//. DD, D. 11D
Nigan gg0)) (8) N20 (
N
1/2 +
Nuco (1) (1) + + DN1, (W (1),,, Wigg (0)
1/2 T Nop (e) (1) (t)
Σ
1/2
(t.
No, (1) (8) (W (0)
==1
Then using triangle inequality, we have
1/2 IV=1/=
DD
S V
1/2
mwall Σ V
1/2
No, Wi (1) (a (0)l
We can bound
V 1/2 T [re] Mex] as
IV [ Mt.)l
| Mom S T Momilll *ow -V
||
S 1 VD+ /ONNNDRR//221/ (110//) (m).m I)),
with probability at least 1 8, where the first inequality is due Lemma C.1 and the second inequality is due to the standard self- normalized bound for kernelized contextual bandit, e.g., Lemma B.3. of et al. (2022).
Then we can bound IV No, Wi (1) (0) (0)l as
IV 1/2
Mr. (A) (6) VV,, (OW (9)l
S 22 DBXI + No WW 2m (1) My., (1) (0)
1/2
No, WW (o, (W) (ill
22D + Nr. (1) ge (3) T,, (WW (1) D3AI &, wo (1) 2Nr (orNe co]
S / 2D 2 (1/6 + In(det K [T]. (D3A) +1)
where the first inequality because Vx AI TT PD. = DD $ No. (N
Rco (0) PAa, (o (4)
due to equation
8 in Lemma C.1 so V2 = AI + $ D. dD.
2D3 (D8AI +
T T Nr, (i) (1) self-normalized bound.
T N.,, (WW (9). and the second inequality again obtained using the standard
Putting everything together, we have
||0 8.llv, 1 (V1/(1 1JVA1e. +
-N/223) +r+
where " := maxpc. 1 log det (l.ptKKp +I).
Proof of Lemma C.7 Note that by definition, AV&(C)) = 0. where E [N] is the index of the client who triggers the k-th communication. the following, we first show that
V
BD AVa(1)
19

---

Published as a conference paper at ICLR 2023
for all i E [M]. For client Ck. V& = 0 BD
AV((c)). For client # Ck2 we have
6(x) V k(t)
((x)
( (V&O k00) + AV o(x)
< 11
E
o(x,)
= (x)))
E
of (x,)
N,Ne, WW (1)
NENY, (9) (4)
11+8
(xx) S BD, SEN (OW (1)
E
K(j
where the first inequality is due to Lemma A.6 and the third is due our event-urigger in equation 4
A.5
the second is due to property of e-accuracy in Lemma
This implies V-1 I (1 + (V)( k(())
MO) + +V
Then due to Lemma A.9
we have (1 +
VD) g(s) = Vg (()) + A (t), and thus VgOo+ = 1 (V)(.. In addition, since k(i) < Vi Ck.
3D
we have R ž VR(3) = nD (t)
By averaging equation g over all N clients, we have
V
1
Σ AV
N3D
and thus, we have
+ [b:] +1
+
Σ (
1=1
Using Lemma A.9again agaann finishes the proof.
D PROOF OF THEOREM 4.5 IN SECTION 4.3
D.1 COMMUNICATION COST
that D3 is the set of time indices for the data points that are used to construct the embedded statistics on the server at the k-th communication round, for k I,.... B. We denote the corresponding (exact) covariance matrix as VA XI + Dr PD. RPxp, with Vo AI, and
Recall from Section 1
kernel matrix K Dr. Dr
T DD. D. ER PAIx/|l
Similar to HHe al. 2022), by defining kp minfk E B det A (p. 2 )
have log(det(1 I + K "KD Pep_,)) )/ det(I X KD Dep )) Z 1 for each p 2 0. We call the sequence time steps in-between lx, and 1,,11 an epoch, and denote the total number of epochs as P. Note that since
det + X- A-'KD,, De.) + log det A- A- 'KD, Day
det(I X 'Krup P Pap) det(I + A + log(
log(
det(I)
det X- - Dep
loggdee(( + - - m))m) < 27T,
there can be at most y terms, i.e., P < 2xr. Now that have divided the time horizon [T'] into P epochs using (t&, [P(()). we prove the following lemma that upper bounds the total number of times communication is triggered in each epoch.
Lemma D.1 (Number of communications per epoch). For each epoch, i.e., the sequence of time steps in be-ben th, and tkp+. the number of communications is upper bounded by N + D
43
Since there are at most 2yr epochs, the total number of communications B < 27r (N + 42) More- over, by Lemma4.1 we know that during each communication, the size of data being communicated is O (T) 2T) Hence, with D N Cr 2 log2(T)).
20

---

Published as a conference paper at ICLR 2023
Proof of Lemma D.1 Consider the epoch [tx,, fkp1 1] for some p 0, .......: P. We denote the total number of communications in this epoch as Qp. and the total number of communications in this epoch that are triggered by client i as Qp.i for i E [ i... 2p = - Qp.i-
Let's denote the indices associated with the communications triggered by some client as K1, K2,...., KQp.. E [kpp kp+1 - 1]. Then for each first communication in this epoch, due to our event- event-trigger design in equation 4 we have
..... .... Pp.i. i.e., excluding client i's
Σ READ.,
oh (x,) 2
E ,x,, 2 SEADNy
Σ 0 (x,) D.
SEADAy
where the first inequality is because by definition of Rj-1, we have Ri-1 kpp so o2 - (x) oh, (x), Vx, and the second inequality is due to Lemma A.6 Therefore, have Eve ESEADN, of (xx)
) 2 D/3. Since oz (x) [xx(()] Vn we have
det(I + "DD, UAD DAp UADIN det(I+ A KDD Dup
DIB s Σ
[ 1 <4log(
sEADIt
<-4+ det X - KD, UADa, Du, UADAy
det((I + + D Dey,)
where the second inequality is by definition of epoch, i.e. det (I+ Depti 1:D .)/ det "D,,,,,,DD D.,) 2, combined with Lemma A.4 and the third is because log(x) < x for 0.
Hence, we have
det(I + - KDD, '''K,,, UAD. USD,,
21+ 43'
det(I + - --1KK Dxp Dep
and thus, we have det(I + A 1 Dzy UADr, Pap uAD det(I + 1 K-i,,,, ) for all j = 2,3. Qp.i and all client i [N].
-o-KKon KD Dap 2
D det +
Denote the indices associated with the communications of all clients in this epoch as Ni, "i.",,...,, E kpt1 - 1}. Then for each j E [Qpl. if client cut has already communi- cated with the server ealier in this epoch, we have
det(I + X KD.g.2 p.g) det(I + A K
D/ 1 Payy
det(I A K 4 UAD,Y Paj_, uDD - det(I + ---
K.D, 1 Pog
2 det(II + A D UAD Dap USD,y) det(I+ + A-'K
D det + - K KD., ) 43
where the first inequality is obtained via matrix determinant lemma and Lemma 1. and the second due to the inequality we derived above. Summing over all communications in this epoch, we have det(I+ DD -1Pp111) det([I + - A-KK DKD,,
2 Σ det (I + x - "-KK "KD.y det(I++ - 2 Pagun
=
D
>
Σ (Qp.s - 1)
det I+ x K KD De,):
43
and since det + K DDpp1 Di, det(( I+ KDD De, S 2 by our definition of epoch,
we have
D
+
-' (Qp.i - 1) S det - K - )) det(I+ + X KD., Pr,) ) 5 2,
43
8o
O Σ
Qp N
18 2. which finishes the proof.
21

---

Published as a conference paper at ICLR 2023
D.2 CUMULATIVE REGRET
To facilitate regret analysis of Async-KernelUCBB we need to introduce some additional notations. First, let's denote the client who triggers the k-th communication ca [N]. the index of its next communicaation as ((c)), and the time step when the k(c))-th communication happens is (((c)) ((b(()) = T if & is client G 's final communication with the server). Then we denote the set of time steps in- between (but not including) the current (the k-th) communication and client Ck 's next communication when client Ck is active as Pk {tx < (((e)) is cx), and thus by Niscory (c*) Nr, (c*) Pk (L(e)))) We also define Po the union over the set of time steps before the first communication each client E [M] Therefore, we have (uf Pk) U (4]NE(BB = [T]. Since Algorithm 1 the approximated mean and variance of each client only get updated when it triggers communication, and then remain fixed until after
definition k(ex)
its next communication, we have that all the interactions Ps U {f((cw) are based on the same
(+x(.), (.). for & = 0, 0.1..... ......,.. B.
In addition, an important observation is that, based on our
event-trigger in equation 4 we have
Σ (x.) S D, 8ЕP사
(x.)) [
+ (x > D.
Now we are ready to upper bound the cumulative regret. Consider some time step Pk U (t((ow) }. Due to our arm selection rule (line 5 of Algorithm T.. we have x; = arg maxxE Ma (x) + aō (x). Combining this with Lemma 4.4 with probability least 1 6, we have
f fx;)) S (x(x + x (xt) S (x,)). + (x,).
f(x:) 2 (x,)
(X:),
where x = arg max f(x) = arg xEA, (0,) 0, the optimal arm time step 1, and
thus Ftt f(xt) f(x:) S (a0xxxxx (x:). The cumulative regret Rr can be rewritten
1
B
RT Σ Σ +
Σ Ttk Σ
Σ
min(2LS, (xx, + Σ min 200 (xt,) }
1=1
K= SEP
Bounding first term: To bound the first term, we introduce an imaginary variance function oZ. (.) (not computed in the actual algorithm) for Ps and = 0, 1,..., B, which is constructed using dataset
Pw)) U fs' E Px: S 13-18 1). In the following paragraph, we will bound the first term by showing that ER EeEp, (x(x)) ) is not too much larger than Σk= ExEP, (x.))
This requires bound the ratio of(x)) (x,) for Pk. and k 0, B. Recall that
(.) constructed using data points that N clients have uploaded to the server up to the k- th communication, i.e., DA = W (t&), which is a subset of Dj (UN D& U (UNY U {tR(g)). However, as shown in equation 9 the event-trigger cannot be directly used to upper bound the summation of approximated variances in PR(S) U (tR(s)) }. but can be used to upper bound that in Pacs, which is why we construct the imaginary variance function without using data points with time indices [t)) Specifically, using the notations we just introduced, we can rewrite the variance as
xx(x = o(x) (op, dD + XI) +((x)
[x) = o(x)) T ( (Dorleeleeaa & PRAMWMee + Σ
2 PE())
izck
2 @(VEPA (11EP
(xx)
2 o(x) 1 p. SD,
+I
"ew (x(()
p PP
P&t)
The following lemma provides upper bound for this ratio.
22

---

Published as a conference paper at ICLR 2023
Lemma D.2 (Bounding of (f(x))/of,.- (Xg)). Under the same condition as Lemma 4.1 with com- munication threshold D, we have vk, 8 that
(8.) NBDD
With Lemma D.2
we can bound the first term as
B TB
Σ min(2LS,2ao 2a,
T TE Σ
[(((,)) 2a,
Σ
o
xz(xx)
O=EEP
O=OEEP
k= sEP
B
o2(x,)
B
2a, =2a
TB
h (x,)
S 2a
TB(1 NBD)
22 (x,))
1x,)1((x)) (X,)
PE
km
4a 4a 13yT3((+
<4 2R( DR(VI+NDD N 2VB)B) vin(1/6)+ + TT33++N3D
with probability at least 25, where the first inequality due to Cauchy-Schwarz, and second is due to the property of e-accuracy in Lemma A.6 the third is due to Lemma D.2] the forth is by definition of maximum information gain "r, and the last is by substituting a defined in Lemma 4.4
Bounding second ferm: For the second term Ek= m2LS, 2 (Xt,)) ). we should note that (+) is the approximated variance function that client o received during its last communica- tion with the server, instead (x) as in our proof of Lemma 4.3 when bounding the size of dictionary. Ideally, we want to relate each (b(c)) (-) to (+(+) and then apply the elliptical potential argument, but as we do not make any assumption on how frequent client arrives, it is possible that for clients who show up infrequently, these two functions are very different.
However, by using the epoch argument as in the proof for communication cost, we can show that this undesirable situation only occurs at most 2yr times. Specifically, recall that Va AI + Lb. D with Vo ΛI, and kernel matrix as KD..D, DD. Lb. E [DD,/x|De We define kp min [B] det + K > 2)) such that log(det(T
Dey det
Dr,)) )) > 1 for each p 2 0. We call the sequence of time steps in- in-between l2, and l2 an epoch, and denote the total number of epochs as P. As shown in the proof for communication cost, we have P 27T.
Consider the epoch [(,,: 1] for some p 0..,..., P. We denote the total number of communications in this epoch that are triggered by client as Qp.i for i E [N], and the indices associated with these communications triggered by client as K1, K2, ....... KQp.. [kp. kpt1 1].
As mentioned above, the approximated variance used during arm selection at txg. i.c, 02 (e (-) could be from a very long time ago. Therefore, we simply bound regret by 2T.S, and total, there can be at most 2 N such terms for all N clients, leading upper bound of 4N LS.
Now we only need to be concerned about the communications at j = 2, 3, ...,, Qp.i and show that o2 (e(,)) (x) is close to of, (x) for all x. Specifically, we have
(x)
02 Felce,) = 0z (x) = oz (x)
$ 200 (x), (x)
where the first equality because by definition Ny (y(C,,)) = Kj-1. the first inequality is because // det(1 + X --, P.y)) S 2 due to Lemma Lemma A.9 and the definition of epoch. Therefore, further applying Cauchy-Schwarz and the
X o2 (x)/o², (x) < det(I - .+1 -D.......... I. p, Dr
23

---

Published as a conference paper at ICLR 2023
e-accuracy property in Lemma A.6 the second term can be bounded by
B
min(21.5, 2c0
S 4N + 20,
2B3
Σ o
(xx)
k=1
B
B
S 4N 20,
2B3
o 1 (xx,) < +S 22x,
2B3
Σ k=1
Σ
of -
k=1
S 4S + 4 BYT
where the imaginary variance function - is constructed using dataset (U+-) ADx) {s' E AD& o' S s 1], the second inequality is because variance is non-increasing over time, the third is because variances are positive, and the last is due to definition of maximum information gain Yr and that B < T.
Putting upper bounds for the first and second term together, we have RT S 4N + 4v2 (1/VI- 1)VĀS 2R( + Nv2DB (m(1/0) YT NBD
Proof of Lemma D.2 We denote V = XI + $b. DD AV A (1) 1xpce $ Paio for i + ch (cx))
and A k.a-i AV
. T (PEPP'''S-1) $ (d'EPese'so-11
In the following, we first show that
1 AV h, (1) V =
(10)
3D
for all i E [N]. Note that for any client i + Ck. we have
1(1)* x
x_ E() AV V.Ro-((1)) (i)) -I 51+ Σ x V x(i)
sEPE(t)
=1+ Σ
E (x,) 51+3 Σ
E(e (1))))))
(x,)
dEP
sEP
1 + 3D,
where the first inequality is due to Lemma A.5 the second inequality is due to Lemma 4.1 and Lemma A.6 and the last inequality is due to equation 9
This implies V k())
(1 (V) 200 AV - (i)
Then due to Lemma A.9 have
(1 + VD) 2(1) ž (O) + AV, ( and thus V (()) Z TD - Moreover, since
k(1) < k. Vi & Cg. we have V 2 Vgo) 2 AV.. (1). Similarly for client cj. we have
x
11
Σ
x xT + AV (ck))
S'EPes'Sa-1
BD Again, this implies V₁ ł 1 AV which finishes the proof of equation 10
By averaging equation over all N clients, we have
V 7 N3D
AV AVA. (1))
and thus, we have
V& +
AV k.s 3 (1+
24

---

Published as a conference paper at ICLR 2023
Using Lemma A.9 again, we have N3 + E AV = V Therefore,
have
(x) o(x) [xx)[²;> o(xx)
11+ NBD
(x) d(x)T(V, + +Σ AV AVi,a-1(3)) (i) (i)) 0(xx)
25


Reviews:
[{"review_id": "jvlQkBhYmG", "reviewer": "Reviewer_yaEL", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 studies distributed kernelized contextual bandits problem, where the reward function lies in a reproducing kernel Hilbert space. New asynchronous approach that does not require all clients to participate and wait for data exchange was proposed by the author(s). The suggested approach is shown to have near-optimal regret and sub-linear communication cost.", "summary_of_the_review": "A new asynchronous approach for the distributed kernelized contextual bandits problem is proposed in this paper, which seems novel. Although it allows for more widespread application, the underlying premise is the same. Above all, I recommend weak accept.", "strength_and_weaknesses": "Strength\n* The newly proposed algorithm is asynchronous, allowing for larger practical applications since it does not require all clients to participate and wait for data transmission.\n* The proposed algorithm is validated using both synthetic and real-world data.\n\nWeaknesses\n* Despite the author(s)' comprehensive trials demonstrating the newly proposed algorithm's superior communication cost compared to the synchrous one in Li et al. (2022), both of them have the same upper bound on regret and communication cost.\n* The algorithms are only tested in three trials, and no variance information is given.", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "jblz9BrR-OJ", "reviewer": "Reviewer_fUPj", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This work focused on kernelized contextual bandits with distributed computation and asynchronous communication. The author proposed the Async-KernelUCB algorithm with $\\tilde O(\\sqrt(T))$ regret and only $O(N^2)$ communication complexity. In addition, both the Synthetic and real-world experiments show that Async-KernelUCB outperforms other algorithms, which supports the efficiency of the Async-KernelUCB algorithm.", "summary_of_the_review": "In summary, this paper provided the first analyses of asynchronous kernelized contextual bandits and proposed a novel algorithm, Async-KernelUCB with a theoretical guarantee, which makes a solid contribution to asynchronous kernelized contextual bandits. Unfortunately, due to the time limitation, I do not have enough time to check the proof in the appendix. Thus I choose a low confidence level.", "strength_and_weaknesses": "Strength:\n\n1. The author provided the first analyses of asynchronous kernelized contextual bandits and proposed a novel algorithm, Async-KernelUCB, with a theoretical guarantee.\n\n2. Both the Synthetic and real-world experiments show that Async-KernelUCB outperforms other algorithms, which supports the efficiency of the Async-KernelUCB algorithm.\n\n3. Compared with previous studies on kernelized contextual bandits, the Async-KernelUCB algorithm further solves the problem of different dictionary copies in an asynchronous environment, providing enough technique novelty.\n\nWeakness:\n\nIn section 3.2, the author mentions that Nystrom approximation can help reduce computation and communication costs. However, it is better if the author directly indicates the computation complexity for equations (1) and (2) to show how Nystrom approximation improves efficiency.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "j-EN46t90h", "reviewer": "Reviewer_iavx", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 is the first to learn kernelized contextual bandits in a distributed and asynchronous environment, which stems from the fact that it is hard to get feedback from all clients at the same time. It applies the idea of Nystrom approximation to help reduce communication cost.", "summary_of_the_review": "This work focuses on the asynchronous setting. It claims to be the first to study this setting and provides both theoretical and numerical findings. However, except for the upper bound, it would be nice to provide a matching lower bound to convince the efficacy of the proposed Async-KernelUCB algorithm.\n\n\n=============\n\nAfter rebuttal:\nThanks for authors’ response. I would like to keep the score.", "strength_and_weaknesses": "Strength:\n1. The work is well-organized and generally easy to follow. The motivation is clear.\n1. One key among the algorithm design is that the communication threshold ensures that little rewards are not involved in the calculation and the communication cost is saved.\n1. In Section 4.3, the author(s) clarifies that the key challenge --- to achieve low regret and low communication cost --- is overcome with a dictionary.\n1. Experiment results look reasonable.\n\nWeaknesses:\n1. Is there a matching lower bound?", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Mi_LutZ0up", "reviewer": "Reviewer_6Kat", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper proposes a new setting of distributed kerneled contextual bandits: an asynchronous environment. For this setting, they propose an algorithm and show both theoretical and practical results. For the empirical results, they show the results on both synthetic and real-world data.", "summary_of_the_review": "This paper that proposes a new setting and an algorithm to achieve near-optimal performance. The empirical results are well laid out. The main issues is with novelty and motivation for the asynchronous setting.", "strength_and_weaknesses": "The paper presents a new setting and propose an algorithm that achieves near-optimal regret. Their empirical results are thorough and they have both synthetic data and real-world data.\n\nMy main weaknesses are:\n1) If there is a new setting that is presenting, it needs to be backed up by stronger motivation as to where such a problem would occur\n2) The algorithm contribution itself seems like a small improvement on current work when taking 1 into consideration", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster