Federated Neural Bandits
Authors: Zhongxiang Dai
Yao Shu
Arun Verma
Flint Xiaofeng Fan
Bryan Kian Hsiang Low
Patrick Jaillet
Venue: ICLR 2023 poster (2023)
Keywords: neural contextual bandits
federated bandits

Abstract: Recent works on neural contextual bandits have achieved compelling performances due to their ability to leverage the strong representation power of neural networks (NNs) for reward prediction. Many applications of contextual bandits involve multiple agents who collaborate without sharing raw observations, thus giving rise to the setting of federated contextual bandits}. Existing works on federated contextual bandits rely on linear or kernelized bandits, which may fall short when modeling complex real-world reward functions. So, this paper introduces the federated neural-upper confidence bound (FN-UCB) algorithm. To better exploit the federated setting, FN-UCB adopts a weighted combination of two UCBs: $\text{UCB}^{a}$ allows every agent to additionally use the observations from the other agents to accelerate exploration (without sharing raw observations), while $\text{UCB}^{b}$ uses an NN with aggregated parameters for reward prediction in a similar way to federated averaging for supervised learning. Notably, the weight between the two UCBs required by our theoretical analysis is amenable to an interesting interpretation, which emphasizes $\text{UCB}^{a}$ initially for accelerated exploration and relies more on $\text{UCB}^{b}$ later after enough observations have been collected to train the NNs for accurate reward prediction (i.e., reliable exploitation). We prove sub-linear upper bounds on both the cumulative regret and the number of communication rounds of FN-UCB, and empirically demonstrate its competitive performance.

Published as a conference paper at ICLR 2023
FEDERATED NEURAL BANDITS
Zhongxiang Dai, Yao Shu, Arun Verma, Flint Xiaofeng Fan & Bryan Kian Hsiang Low Department of Computer Science, National University of Singapore (dai zhongxi ang, shuyao, arun, xiaofeng, lowkh) (owwh)ecooo @comp. nus www.udu.uu..uueuu...........u... edu. .gg
Patrick Jaillet
Department of Electrical Engineering and Computer Science, MIT ja Wailletton @mit.edu edu
ABSTRACT
Recent works neural contextual bandits have achieved compelling performances due to their ability to leverage the strong representation power of neural networks (NNs) for reward prediction. Many applications of contextual bandits involve multiple agents who collaborate without sharing raw observations, thus giving rise to the setting of federated contextual bandits. Existing works on federated contextual bandits rely on linear or kernelized bandits, which may fall short when modeling complex real-world reward functions. So, this paper introduces the federated neural-upper confidence bound (FN-UC3) algorithm. To better exploit the federated setting, FN UCB adopts a weighted combination of two UCBs: UCB" allows every agent to additionally use the observations from the other agents accelerate exploration (without sharing raw observations), while UCB uses NN with aggregated parameters for reward prediction in a similar way to federated averaging for supervised learning. Notably, the weight between the two UCBs required by our theoretical analysis is amenable to an interesting interpretation, which emphasizes UCB" initially for accelerated exploration and relies more on UCB" later after enough observations have been collected train the NNs for accurate reward prediction (i.c., reliable exploitation). We prove sub-linear upper bounds on both the cumulative regret and the number of communication rounds of FN-UCB, and empirically demonstrate its competitive performance.
INTRODUCTION
The stochastic multi-armer bandit is prominent method for sequential Decision-makinn problems due to its principled ability to handle the pmplooatiionexploiaatiiie trade-off (Auer) 2002] [Bbbeck & Cesa-Bianchi] [0122] Lattimore & Szepesvári 2020). In particular, the stochastic contextual bandit problem has received enormous attention due to its widespread real-world applications such as recommender systems (Li et al. 2010a), advertising (Li al. 2010b). and healthcare (Greenewald et al. 2017). In each iteration of stochastic contextual bandit problem, an agent receives context (i.c., d-dimensional feature vector) for each of the K arms, selects one of the K contexts/arms, and observes the corresponding reward. The goal of the agent is to sequentially pull the arms in order to maximize the cumulative reward (or equivalently, minimize the cumulative regret) in iterations.
To minimize the cumulative regret, linear contextual bandit algorithms assume that the rewards can be modeled as linear function of the input contexts (Dani et al. (2088) and select the arms via classic methods such as upper confidence bound (UCB) (Auer) 2002) or Thompson sampling (TS) [Thompson 1933), consequently yielding the Linear UCB (Abbasi- Yadkori et al. [011T) and Linear TS (Agrawal & Goyal 2013) algorithms. The potentially restrictive assumption of a linear model was later relaxed by kernelized contextual bandit algorithms (Chowdhury & Gopalan 2017 Valko et al. 2013), which assume that the reward function belongs to a reproducing kernel Hilbert space (RKHS) and hence model the reward function using kernel ridge regression or Gaussian process (GP) regression. However, this assumption may still be restrictive (Zhou et al. 2020) and the kernelized
"Corresponding author.

---

Published as a conference paper at ICLR 2023
model may fall short when the reward function is very complex and difficult to model. To this end, neural networks (NNs), which excel at modeling complex real-world functions, have been adopted to model the reward function in contextual bandits, thereby leading to neural contextual bandit algorithms such as Neural UCB (Zhou et al. 2020) and Neural TS (Zhang et al.) 2021). Due to their ability use the highly expressive NNs for better reward prediction (i.e., exploitation). Neural UCB and Neural TS have been shown to outperform both linear and kernelized contextual bandit algorithms in practice. Moreover, the cumulative regrets of Neural UCB and Neural TS have been analyzed by leveraging the theory of the neural tangent kernel (NTK) (Jacot et al., 2018), hence making these algorithms both provably efficient and practically effective. We give comprehensive review of the related works on neural bandits in App.
The contextual bandit al algorithms discussed above are only applicable to problems with single agent. However, many modern applications of contextual bandits involve multiple agents who (a) collaborate with each other for better performances and yet (b) are unwilling to share their raw observations (i.c., the contexts and rewards). For example, companies may collaborate to improve their contextual bandits-based recommendation algorithms without sharing their sensitive user data (Huang et al. 2021b), while hospitals deploying contextual bandits for personalized treatment may collaborate to improve their treatment strategies without sharing their sensitive patient information (Dai et al. 2020).
These applications naturally fall under the setting of federated learning (FL) (Kairouz et al.
2019
Li et al. 202T) which facilitates collaborative learning of supervised learning models (e.g.. NNs)
without sharing the raw data. In this regard, a number of federated contextual bandit al algorithms have
been developed to allow bandit agents to collaborate in the federated setting (Shi & Shen (021). We
present a thorough discussion of the related works on federated contextual bandits in App. A] Notably, Wang et al. (2020) have adopted the Linear UCB policy and developed a mechanism to allow every agent to additionally use the observations from the other agents to accelerate exploration, while only requiring the agents to exchange some sufficient statistics instead of their raw observations. However, these previous works have only relied on either linear (Dubey & Pentland 2020 Huang
et al. 2021b) or kernelized (Dai et al., 2020; 2021) methods which, as discussed above, may lack the expressive power to model complex real- world reward functions (Zhou et al., (222)). Therefore, this naturally brings up the need to use NNs for better exploitation (i.e., reward prediction) in federated
contextual bandits, therehy motivating the need for federated neural contextual bandit algorithm.
To develop federated neural contextual bandit algorithm, important technical challenge is how to leverage the federated setting to simultaneously (a) accelerate exploration by allowing every agent to additionally use the observations from the other agents without requiring the exchange of raw observations (in a similar way to that of Wang et al. (2020)) and (b) improve exploitation by further enhancing the quality of the NN for reward prediction through the federated setting (i.e., without requiring centralized training using the observations from all agents). In this work, we provide a theoretically grounded solution to tackle this challenge by deploying weighted combination of two upper confidence bounds (UCBs). The first UCB, denoted by UCB", incorporates the neural tangent features (i.c., the random features embedding of NTK) into the Linear
mechanism adopted by Wang et al. (2020), which achieves the first goal of accelerating exploration. The second UCB, denoted by UCB", adopts an aggregated NN whose parameters are the average of the parameters of the NNs trained by all agents using their local observations for better reward prediction (i.e., better exploitation in the second goal). Hence, UCB" improves the quality of the NN for reward prediction in similar way to the most classic FL method of federated averaging (FedAvg) for supervised learning (McMahan et al. 2017). Notably, our choice of the weight between the two UCBs, which naturally arises during our theoretical analysis, has interesting practical interpretation (Sec. (.3): More weight is given to UCB" in earlier iterations, which allows us to use the observations from the other agents to accelerate the exploration in the early stage; more weight is assigned to UCB* only in later iterations after every agent has collected enough local observations to train its NN for accurate reward prediction (i.c.. reliable exploitation). Of note, our novel design of the weight (Sec. (.3) is crucial for our theoretical analysis and may be of broader interest for future works on related topics.
This paper introduces the first federated neural contextual bandit algorithm which we call federated neural-UCA (FN-UCB) (Sec. 3. We derive an upper bound on its total cumulative regret from all N agents: Ry Ö(dVTN + N where d is the effective dimension of the contexts from all N agents and dmaax represents the maximum among the N individual effective dimensions
'The ① ignores all logarithmic factors.
2

---

Published as a conference paper at ICLR 2023
The communication complexity (i.e., total number of communication rounds in T iterations) of FN-UCB can be upper-bounded by CT (dvVN). Finally, we use both synthetic and real-world contextual bandit experiments to explore the interesting insights about our FN-UCB and demonstrate its effective practical performance (Sec. 5
of the contexts from the N agents (Sec. 2
BACKGROUND AND PROBLEM SETTING
} for positive integer k. O₁: represent k-dimensional vector of 0's, and x denote all-zero matrix with dimension k x k. Our setting involves N agents with the same reward function h defined on a domain X' C R We consider centralized and synchronous communication: The communication is coordinated by a central server and every agent exchanges information with the central server during a communication round. In each iteration t E [T. every agent i E [A] receives a set Li, & (=(, of K context vectors and selects one of them Fz, Ny, to be queried to observe noisy output ye, _ h(22,x) + where is an R-sub-GGussian noise. We will analyze the total cumulative regret from all N agents in T iterations:
Let [R] denote the set
RT. A -E Ei= Tt, where rt,i - h( - h((z,;)) and x7,; -
arg max
Let fxx; 0) denote the output of a fully connected NN for input with parameters 0 (of dimension Po) and g(:; 8) denote the corresponding (column) gradient vector. We focus on NNs with ReLU activations, and use L 2 and m to denote its depth and width (of every layer), respectively. We follow the initialization technique from Zhang et al. (202T): Zhou et al. (2020) to initialize the NN common ground for collaboration, we let all N agents share
parameters Og ~ init(.). Of note, the same initial parameters 9g when training their NNs and computing their neural tangent features: gla; 0n)/ // (i.e., the random features embedding of NTK (Zhang et al. (022)). Also, let H denote the (TK. () x (TKN)) - NTK matrix on the set of all received 7'K N contexts {Zhang al., 2021 Zhou et al. 2020). Similarly, let H. denote the (TK) x (TK) diimensiion NTK matrix on the set of TK contexts received by agent i. We defer the details on the definitions of H and H,'S 's, the NN (z; 0), and the initialization scheme Og init(-) to App. B due to limited space.
Next, let h & [h(2f,, (elef,))letr)
denote the dimmeniiiia column vector of reward
function values all received contexts and B be absolute constant s.t. V2h H < B. This is related to the commonly adopted assumption in kernelized bandits that h lies in the RKHS H induced by the NTK (Chowdhury & Gopalan| 2017: Srinivas et al. 2010) (or, equivalently. that
the RKHS norm || of upper-bounded by constant) because vh h H S || (Zhou et al. 2020). Following the works of ofanha et al. (2021); Zhou et al. (2020), we define the effective dimension of H as d det(/ (H/2) with regularization parameter À > 0. Similarly, define the +T(1+TKK/N)
effective dimension for agent as d, A deul and also detine dmmux - mmax d. Note that the effective dimension related to the maximum information gain 7 which is a commonly adopted notion in kernelized bandits (Zhang et al. 2021 y d S 2/TKNN/ /lg(11 + TTKN/A) and d, < 2TTK/ / log(1 + TK/A), Vi [... Consistent with the works on neural contextual bandits /Zhang et al. 2021 Zhou et al. 2020), our only assumption on the reward function ht is its boundedness: [hxx) S I, Vr E X. We also make the following assumptions for our theoretical analysis, all of which are mild and easily achievable, as discussed in (Zhang et al.) [021]] Zhou et al., 2020):
Tog(I+TK/A)
Assumption There exists Ao > s.f. H > dol and H; > Xol, Vi E [N]. Also, all contexts satisfy ||0||| =1 and [x]]] = [xls+d/2 Vx E Xr,,, Vt E (T) E [N].
FEDERATED NEURAL-UPPER CONFIDENCE BOUND (FN-UCB)
Our FN-UCE algorithm is described in Algo. | (agents' part) and Algo. 2 (central server's part).
3.1
OVERVIEW OF FN-UCB ALGORITHM
Before the beginning of the algorithm, we sample the initial parameters Op and share with all agents (Sec. 2). In each iteration /. E [T], every agent i E [N] receives a set X = (=f of K contexts (line of Algo. and then uses a weighted combination of UCB,, and UCB to select a context 21,; Xx, to be queried (lines 4-7 of Algo. D. Next, each agent observes noisy output Yt.; (line 8 of Algo. [T] and then updates its local information (lines 9-10 of Algo. [.. After that, every agent checks if it has collected enough information since the last communication round (i.e., checks
3

---

Published as a conference paper at ICLR 2023
Algorithm 1 FN- (Agent
1: inputs: À 1 2/T, 0g ~ init(:), Wyne = Opo Wnew, = 0 Pp xpxx Beyne = 0, Bnew,i Pp-
a = 0, Vlocal = XL, V VoyaG.NN = A Visst = MI, Elast = 0, Osync.NN = 80.
2: for t = 1, .., do
3: Receive a set Xx,, { of K contexts
4: Compute Vei AI Wayne + Wnewi De, = =V,1 (Bayne Buew,.)
5: Compute UCB,, (x) (g(2;; 00)/ /m, 0e.s) ) + UTKN (1((2;00)) hmml)//mllll
6: a * compute UCB (2) - (1;; Boync.NN) VTK VAN-! ΣS /mlll
7:
Select 24 - arg m (1 a) UCB,, (x) UCB
8:
Query Ft,; to observe Vt
9:
Update W new,, t- W Wnew, +g( 80) ( 000 /m, Bnew, x Beew, t Ur g 0n)/ Vm Update Valcaal = -V ( 0o) ( 00) /mm
10:
11:
if (1 Itaa) log (det(>T + synn + W Weew.;) (eew:))det(((r (eeaa) > D then
12:
Send synchronisation signal to the central server to start a communication round if a communication round is started then
13:
14:
Train NN with gradient descent using all agent i's local observations Di, { Vr, brree based on initial parameters 0g learning rate 7,, number J iterations,
and Equation as loss function to obtain 0f
Compute a = Glocal /Glocal (Sec. 3.3
t,i,min// t,i,max
16:
send| { Wnow,s: Bnew,i: 8i, Oig (V2,t
to the central server
17:
receive W B Bayne; OsyDC,N,, O,, {VVloca)) hE(N] } from the central server
18:
Set Viast Wsyne + Al, bast = t, W new,i Ope x Bnew,
Algorithm 2 Central Server
1: if synchronization signal is received from any agent then
2: Send a signal to all agents to start communication round
3: receive { W Wnew,i, Brew,i, Oi Ott,i, (Vi hE(NN
4: Compute 0yynC.NN = N ΣN 0f a = minte[N] 04,5 let (V/ocal)-1 (V/local) Vi [N]
Wayne sync + EE W Weew,i Bayne Bayne Ei=1 Brew,i 6: Broadcast W WWayne, Bayne, Ooyne,NN a, ((Vlocal)-1) [NE(N) } to all agents
5: Update W sync &- W.
the criterion in line 11 of Algo. I if so, it sends synchronization signal to the central server (line 12 of Algo. ( who then tells all agents start communication round (line Algo. 2 During communication round, every agent i uses its current history of local observations to train an NN (line 14 of Algo. [ and sends updated local information the central server (line 16 of Algo. TD: the central server then aggregates these information from all agents (lines 4-5 of Algo. 2 and broadcasts the aggregated information back to all agents (line 6 of Algo. to start the next iteration. We refer to those iterations between two communication rounds as an epoch So, our UCB algorithm consists of a number of epochs which are separated by communication rounds.
Note that every agent only needs train NN in every communication round, i.e., only after the change in the log determinant of the covariance matrix any agent exceeds a threshold (line 11 of Algo. D. This has the additional benefit of reducing the computational cost due to the training of NNs. Interestingly, this is in a similar spirit as the adaptive batch size scheme in Gu et al. (2021) which only retrains the NN in Neural UCB after the change in the determinant of the covariance matrix exceeds a threshold and is shown to only slightly degrade the performance of Neural UCB.
3.2 THE TWo UPPER CONFIDENCE BOUNDS (UCBs)
Firstly, UCB,, can be interpreted as the Linear UCB policy (Abbasi- Yadkori et al. 2011) using the neural tangent features (x; 0o) h//m /m
the input features. In iteration t, let p denote the index of the
"The first (last) epoch is hetween communication round and the heginning (end) of #N-UCH algorithm.
4

---

Published as a conference paper at ICLR 2023
current epoch. Then, computing UCB,,, (line 5 of Algo. 1 makes use of two types of information. The first type of information, which uses the observations from all N agents before epoch p. is used for computing UCB;, via W syn: and Bayne (line 4 of Algo. D. Specifically,
can be seen from line 5 of Algo. [] W Wsyne and Bayne are computed by the central server by summing up the Wnew,''s 's and Beew,''s 's from all agents (i.e., by aggregating the information from all agents) where Wnew, and Brew, are computed using the local observations of agent (line 9 of Algo. []. The second type of information used by UCB;, (via W ne and Bnew, utilized in line 4 of Algo. exploits the newly collected local observations of agent i in epoch p. As a result, UCB;, allows to utilize the observations from all agents via the federated setting for accelerated exploration without requiring the agents to share their raw observations. UCB,, is computed with the defined parameter
PTKN B + (l1g())(330)) + 1) + d (1 + TKN/A) 1/2 where 5 E (0, 1).
Secondly, UCB leverages the federated setting to improve the quality of NN for reward prediction (to achieve better exploitation) in a similar way to FedAvg, i.e., by averaging the parameters of the NNs trained by all agents using their local observations (McMahan et al. 2017). Specifically, when communication round is started, every agent i E [N] uses its local observations Di, e ((T+, Vr,s)) rele to train an NN (line 14 of Algo. [1. It uses initial parameters On (i.e., shared among all agents (Sec. 2)) and trains the NN using gradient descent with learning rate 1) for J training iterations (see Theorem [ for the choices of 17 and J) to minimize the following loss function:
(0) - 0.5 Et
v+,a)² + 0.5m - 0oll
The resulting NN parameters Of's from all N agents are sent to the central server (line 16 of Algo.
I
who averages them (line of Algo. 2 and broadcasts the aggregated Osync.NN _ -N-1 Σ of back to all agents to be used in the next epoch. In addition, to compute the second term of UCB E, every agent needs to compute the matrix Vilccal using its local inputs (line 10 of Algo. 11 and send its inverse to the central server (line 16 of Algo. D during a communication round; after that, the central server broadcasts these matrices {(V/loma)) Ne([] received from each agent back to all agents to be used in the second term of UCB (line of Algo. Refer to Sec. 4.2 for a detailed explanation on the validity of UCB", high-probabiliity upper bound on h (up to additive error terms). UCB", is computed with the defined parameter μTK- _ B + (1 + +1 + dmax log(1 + TK/A)
N
3.3 WEIGIT BETWEEN THE TWO UCBS
Our choice of the weight between the two UCBs, which naturally arises during our theoretical analysis (Sec. 4. has an interesting interpretation in terms of the relative strengths of the two UCBs
and the explorationn-exllitttio trade-off. Specifically, (x)) & VA [|((;; 0o) /mll (V):-))- (
intuitively represents our uncertainty about the reward at x after conditioning on the local observations llocal
of agent i up to iteration Kassraie & Krause 2022) Next, tii,min
- min glocaal (I) and
glocal tiimax - max 2t, بloca (2)) represent our smallest and largest uncertainties across the entire domain, /olocal /oocal
respectively. Then, we choose a A minGE[N] oer (line 4 of Algo. 2 where (t.. _ Glocal L.i.min//
(line 15 of Algo. [Ip. In other words, C4,s is the ratio between the smallest and largest uncertainty across the entire domain for agent i, and a is the smallest such ratio at,, among all agents. Therefore, a is expected to be generally increasing with the number of iterations/epochs: Glocal t,i,min is already small after the first few iterations since the uncertainty at the queried contexts is very small; the other hand, T gloca m.i.max is expected to be very large in early iterations and become smaller in later iterations only after a large number of contexts has been queried to sufficiently reduce the overall uncertainty in the entire domain. This implies that we give more weight to UCB,, t in earlier iterations and assign more weight to UCB in later iterations. This, interestingly, turns out to have an intriguing practical interpretation: Relying more on UCB", in earlier iterations is reasonable because UCB,, ; is able to utilize the observations from all agents to accelerate exploration in the early stage (Sec. (.2 it is also sensible to give more emphasis to UCB/ ; only in later iterations because the NN trained by every agent is only able to accurately model the reward function (for reliable exploitation) after it has collected enough observations to train its NN. In our practical implementation (Sec. 55) we will use the analysis here as an inspiration to design an increasing sequence of a.
'Formally, aleel (xr is the Gaussian process posterior standard deviation at æ conditioned the local observations of agent till iteration and computed using the kernel k(x, x') g(>; 0o) o(x':00)/m)
5

---

Published as a conference paper at ICLR 2023
3.4 COMMUNICATION COST
To achieve a better communication efficiency, we propose here variant of our main UCB algorithm called FN-UCB (Less Comm.) which differs from FN-UCB (Algos. [ and 2 in two aspects. Firstly, the central server averages the matrices - [e([N) received from all agents to
produce a single matrix V = N E (V/ and hence only broadcasts the single matrix symc.NN instead of all N received matrices ((V2,) ( KEEN to all agents (see line of Algo. 2
Secondly, the UCB,, of every agent i (line 6 of Algo. is modified to use the matrix V V Ny UCB (x)) (1;; NNymeNN) + VTK v [gx;; 00) vm
To further reduce the communication
cost of both FN-UCB and UN-UCB (Less Comm.) especially when the NN is large (i.e., its total number Pa of parameters is large), we can follow the practice of previous works Zhang et al. 202T Zhou et al. 2020) to diagonalize the Po x Po matrices, i.e., by only keeping the diagonal elements of the matrices. Specifically,
can diagonalize Wnew.i (line 9 of Algo. 1 and V. (line 10 of Algo. D. and let the central server aggregate only the diagonal elements of the corresponding matrices to obtain W snc and V Vynnc,NN. This reduces both the communication and computational costs.
As result, during a communication round, the parameters that an agent sends to the central server in- clude [W W.eee,,eeew. 0f, Ott.i, [V( (line 16 of Algo. which constitute po Po 1+ = Oppo) parameters and are the same for FN-UCB and FN-UCB (Less Comm )) The parameters that the central server broadcasts to the agents include [Wsyae> Bsyne SyyaCNN, a, {(V be for FN-UCB (line 6 of Algo. 2 which amount to Po + Po + Po + Noo (NN parameters. Meanwhile, FN- (Less Comm.) only needs to broadcast O(po) parameters because the N matrices (
are now replaced by a single matrix ViJic.NN. Therefore, the total number of exchanged parameters by FN-UCB (Less Comm.) ) is (po) which is comparable to the number of exchanged parameters in standard FL for supervised learning (e.g.. FedAvg) (e.g..FedAvg) where the parameters (or gradients) of the NN are exchanged (McMahan et al. 2017). We will also analyze the total number of required communication rounds by FN-UCB, as well as by FN-UCB (Less Comm, ), in Sec. 4.1
As we will discuss in Sec. the variant FN-UCB (Less Comm.) has looser regret upper bound than our main FN-UCB algorithm (Algos. D and 2). However, in practice, FN-UCB (Less Comm.) ) is recommended over FN-UCB because it achieves very similar empirical performance as FN-UCB (which we have verified in Sec. 5.1 I and yet incurs less communication cost.
4
THEORETICAL ANALYSIS
4.1 THEORETICAL RESULTS
Regret Upper Bound. For simplicity, we analyze the regret of a simpler version of our algorithm where we only choose the weight using the method described in Sec. 3.3 in the first iteration after every communication round (i.c., first iteration of every epuch) and set a = 0 in all other itcrations. Note that when communication occurs after each iteration (i.c., when D is sufficiently small), this version coincides with our original FN-UCB described in Algos. I and (Sec.3) 3}. The regret upper bound of FN-UCB is given by the following result (proof in Appendix
Theorem 1. Let 8 E (0, 1), À + 2/T, and D OTT/ d)). Suppose that the NN width m grows polynomially: m 2 poly(A, T, K, N, L, (1/8), For the gradient descent training (line 14 of Algo. J. let 17 Ca + m m) -1 for some constant C4 > 0 and J = Ō (TL/ Then, with probability of at least 1 - 5, Rī = Ô (āvTN + d NVT).
Refer to Appendix C.I for the detailed conditions on the NN width m as well as the learning rate n and number of iterations for the gradient descent training (line 14 of Algo. DT. Intuitively, the effective dimension d measures the actual underlying dimension of the set of all TKN contexts for all agents Zhang et al. 2021). ). and dmax A ma d, is the maximum among the underlying dimensions the set of TK contexts for each of the N agents. Zhang al, (2021) showed that if
all contexts lie in d' -d-mennsional subspace of the RKHS induced by the NTK, then the effective dimension of these contexts can be
by the constant d'.
The first term d TN in the regret upper bound (Theorem 1 arises due to UCB3, and reflects the benefit of the federated setting. In particular, this term matches the regret upper bound of standard Neural UCB (hhou et al. 2020) running for TN iterations and so, the average regret dl d//T/N

---

Published as a conference paper at ICLR 2023
across all agents decreases with a larger number N of agents. The second term dmaax- results from UCB which involves two major components of our algorithm: the use of NNs for reward prediction and the aggregation of the NN parameters. Although not reflecting the benefit of larger N in the regret bound, both components
important to our algorithm. Firstly, the use of NNs for reward prediction is a crucial component in neural contextual bandits in order to exploit the strong representation power of NNs. This is similar in spirit the works on neural contextual bandits (Zhang iet al. 2021; Zhou et al. 2020 in which the use of NNs for reward prediction does not improve the regret upper bound (compared with using the linear prediction given by the first term of UCB;,) and yet significantly improves the practical performance. Secondly, the aggregation of the NN parameters also important for the performance of our FN-UCB since it allows us exploit the federated setting in similar way to FL for supervised learning which has been repeatedly shown to improve the performance (Kairouz et al., 2019). We have also empirically verified (Sec. that both components (i.e., the use of NNs for reward prediction and the aggregation of NN parameters) are important to the practical performance of our algorithm. The work of Huang et al. al. (202 has leveraged the NTK to analyze the convergence of FedAvg for supervised learning (McMahan et al. 2017) which also averages the NN parameters in a similar way to our algorithm. Note that their convergence results also do not improve with a larger number N of agents but in fact become worse with a larger N.
Of note, in the single-agent setting where N- 1, we have that d== -max (Sec. 2 Therefore, our regret upper bound from Theorem 1 reduces to Rr = (dv/T), which, interestingly, matches the regret upper bounds of standard neural bandit algorithms including Neural UCB (Zhou et al.. 20200 and Neural TS (Zhang et al., (202]) We also prove (App. C.7) that FN-UCB (Less Comm ), which a variant of our FN UCB with better communication efficiency (Sec. 3.4). enjoys regret upper bound of Ri
OddTNN + dimax NTTN,, whose second term is worse than that of FN-UCB (Theorem 1 by a factor of VN. In addition, we have also analyzed our general algorithm which does not set a = 0 in any iteration (results and analysis in Appendix [F) which requires an additional assumption and only introduces an additional multiplicative constant to the regret bound.
Communication Complexity. The following result (proof in App. D gives a theoretical guarantee on the communication complexity of FN-UCB, including its variant FN-UCR (Less Comm
Theorem 2. With the same parameters as Theorem ? if the NN width m satisfies m 2 PTly(T, K, N, T,, log(1/5)), then with probubility of at least 1 - 8, the total number of commu- nication rounds for FN-UCB satisfies CT = N).
The specific condition on m required by Theorem 2 corresponds to condition listed in App. (see App. D for details) which is a subset of the conditions required by Theorem [ Following the same discussion on the effective dimension d presented above, if all contexts lie in d' -dmmeennioa subspace of the RKHS induced by the NTK, then d can be upper-bounded by the constant d', consequently leading to a communication complexity of Cr Ö(VN).
4.2 PROOF SKETCH
We give a brief sketch of our regret analysis for Theorem | (detailed proof in Appendix (). To begin with, we need to prove that both UCB,, and UCB,, are valid gigh-probbbility upper bounds on the reward function h (App. C.3) given that the conditions on m, 7/, and J in App. C.1 are satisfied.
Since UCB,, can be viewed as Linear UCB using the neural tangent features g(x; 6o) / as the input features (Sec. 3). its validity as high-probability upper bound on h can be proven following similar steps as that of standard linear and kernelized bandits (Chowdhury & Gopalan| (017)) (see Lemma in App. C.3 Next, to prove that UCB is also a high-probability upper bound on h (up to additive error terms), let Obocal
(Zr,;; Vm) which is defined in the same way as or, (line 4 of Algo. except that Glocal only uses the local observations of agent i. Firstly, we show that (xx; Osyne.NN) (i.e., the NN prediction using the aggregated parameters) is close to -- "> (9(2; 0o)/ Oloual) which is the linear prediction using Oloxal averaged over all agents. This is achieved by showing that the linear approximation of the NN at Og is close to both terms. Secondly, we show that the absolute difference between the linear prediction (g(2; 0o)/ /mm Ologa)) by VTK (Z] 0o) (0l//m/// /0//mll((ze)) 1. This can be done following similar steps as the proof for UCB; mentioned above. Thirdly, using the
(Vi, (1
of agent and the reward function (() can be
7

---

Published as a conference paper at ICLR 2023
averaged linear prediction NN - (1(;;; Poo//m/ () intermediate term, the difference between f(; NN) and h(x) can be upper-bounded. This implies the validity of UCB as a high-probability upper bound on h (up additive error terms which are small given the conditions on vn, 1,, and J presented in App. C.T. as formalized by Lemma 4 in App.
N
C.3
Next, following similar footsteps the analysis in Wang et al. (2020), we separate all epochs into "good" epochs (intuitively, those epochs during which the amount of newly collected information from all agents not too large) and "bad" epochs (details in App. C.2), and then separately upper-bound the regrets incurred in these two types of epochs. For good epochs (App. C.4 we are able to derive a tight upper bound on the regret rr.i h(rr;,)) )) (xx,;) ) in each iteration by making use of the fact that the change of information in good epoch is bounded, and consequently obtain tight upper bound on the total regrets in all good epochs. For bad epochs (App. C.5). we make use of the result from App. C.2 which guarantees that the total number of bad epochs can be upper-bounded. As result, with an appropriate choice of D = O(T/(Nd)) (NVd), the growth rate of the total regret incurred in bad epochs is smaller than that in good epochs. Lastly, the final regret upper bound follows from adding up the total regrets from good and bad epochs App..C.6).
5 EXPERIMENTS
All figures in this section plot the average cumulative regret across all N agents up to an iteration, which allows us to inspect the benefit that the federated setting brings an agent (on average). In all presented results, unless specified otherwise (by specifying a value of D), a communication round happens after each iteration. All curves stand for the mean and standard error from independent runs. Some experimental details and results are deferred to App. due to space limitation.
5.1 SYNTHETIC EXPERIMENTS
We firstly use synthetic experiments to illustrate some interesting insights about our algorithm. Similar to that of Zhou et al. (2020), we adopt the synthetic functions of h(x) = c3, (aaa,, and h(x) 10 x² which are referred to as the cosins and square functions, respectively. We add a Gaussian observation noise with a standard deviation of 0.01. The parameter a is a 10- dimensional vector randomly sampled from the unit hypersphere. In each iteration, every agent receives K = 4 contexts (arms) which are randomly sampled from the unit hypersphere. For fair comparisons, for all methods (including our FN-UCB, Neural UCB, and Neural TS), we the same set of parameters of = VNKN = 1/K = 0.1 and use an NN with hidden layer and a width of m 20. As suggested by our theoretical analysis (Sec. (.3), select an increasing sequence of a which is linearly increasing (to 1) in the first 700 iterations, and let a = afterwards. To begin with, we compare our main FN-UCC algorithm and its variant FN-UC? (Less Comm. .) (Sec. B.4). The results (Figs. 3 and 3b in App. show that their empirical performances are very similar. So, for practical deployment, we recommend the use of FN-UCB (Less Comm.) ) as communication-effici efficiien and achieves similar performance. Accordingly, we will use the variant FN-UCB (Less Comm. .) in all our subsequent experiments and refer to as FN-UCB for simplicity.
more
Fig. presents the results. Figs. Ta and Th show that our FN-UCB with N = 1 agent performs comparably with Neural UCB and Neural TS, and that the federation of a larger number N of agents consistently improves the performance of our FN-UCB. Note that the federation of N = 2 agents can already provide significant improvements over non-federated algorithms. Fig. I gives an illustration of the importance of different components in our FN-UCB. The red curve is obtained by removing UCBÉ, (i.e., letting a 0) and the green curve corresponds to removing UCB,, The red curve shows that relying solely on UCB,, leads to significantly larger regrets in the long run due to its inability to utilize NNs to model the reward functions. On the other hand, the green curve incurs larger regrets than the red curve initially; however, after more observations are collected (i.e., after the NNs are trained with enough data to accurately model the reward function), it quickly learns to achieve much smaller regrets. These results provide empirical justifications for our discussion on the weight between the two UCBs (Sec. 3.3): that more weight is given to UCB", initially and then to UCB later. The yellow curve is obtained by removing the step of aggregating (i.e., averaging) the NN parameters (in line 4 of Algo. D. i.e., when calculating UCB (line 6 of Algo. [ we use 0 to replace 8ymc.MN. The results show that the aggregation of the NN parameters significantly improves the performance of FN-UCB (i.c., the blue curve has much smaller regrets than the yellow one) and is hence an indispensable part of our
: It is reasonable to use an increasing sequence of a such
8

---

Published as a conference paper at ICLR 2023
Word Ai
200
100
2.00
Rices 21
55
10
03
5
40
63:
:00
93
20
10
1800
2000
3000
4000
5020
2000
2003 3003
4220
5003
1052
2200 3000 Lerul Mtt
4002
5200
%
2000
2020
3600
4000
5000
Mautara
(a) cosine
(b) square
(c) cosine
(d) cosine
Figure 1: Cumulative regret with varying number of agents for the (a) cosine function and (b) square function. (c) Illustration of the importance of different components of our FN-UCB algorithm (cosine function). (d) Performances with different values of D (cosine function). The average number of rounds of communications are 348.0, 380.0, 456.7 for = 5, 4, 2.5, respectively.
620
020
Cumu ve Riggre
600
203
420
-33
150
400
183
1003
2000 Ecoosrr
1003
3006 herations
4:00
1626
2002
5000
3:00 4000
Rantoon
(a) shuttle (b) magic telescope (c) shuttle (diag. (d) shuttle (diag.)
Figure 2: Results (m 20) for (a) shuttle and (b) magic. (c) Results for shuttle with
diagonal approximation (m = 50). (d) Results for shuttle with different values of D. The average number of communication rounds are 3850.7, 4442.7, 4906.3 for D 0.05, 0.03, 0.01, respectively.
FN-UCB. Lastly, Fig. Tdt shows that more frequent communications (i.e., smaller values of D which make it easier to initiate a communication round; see line 11 of Algo. T lead to smaller regrets.
5.2
REAL-WORLLD EXPERIMENTS
We adopt the shutt e and magic telescope datasets from the UCI machine learning repos- itory (Dua & Graff] 2017) and construct the experiments following a widely used protocol in previous works (Li et al. 2010a| Zhang et al. [021 Zhou et al. 2020).. A K K-class classification problem can be converted into K-armed contextual bandit problem. In each iteration, an input x is randomly drawn from the dataset and is then used to construct K context feature vectors X, = [x; Og:..................... : 0z), X2 = xO.:;;0.:: .......... XK- = [0,; 10.:.... :0,; x] which correspond to the K classes. The reward is 1 if the arm with the correct class is pulled, and 0 otherwise. For fair compar- isons, we use the same set parameters of A = 10, LTKN 0.1, and uTK = 0.01 for all methods. Figs. and 2p present the results for the two datasets (1 hidden layer, = 20) and show that our FN-UCB with N = 2 agents consistently outperforms standard Neural UCB and Neural TS, and its performance also improves with the federation of more agents. Fig. 2 shows the results for shutt when diagonal approximation (Sec. 3.4 is applied to the NNs (1 hidden layer, m = 50); the corresponding results are consistent with those Fig. 2. Moreover, the regrets in Fig. 2 are in general smaller than those in Fig. p This may suggest that in practice, a wider NN with diagonal approximation may be preferable to narrower NN without diagonal approximation since it not only improves the performance but also reduces the computational and communication costs (Sec. 3.4). Fig. 21 plots the regrets of shuttle (with diagonal approximation) for different values of and shows that more frequent communications lead to better performances and are hence consistent with that in Fig. [d.. For completeness, we also compare their performance with that of linear and kernelized contextual bandit algorithms (for the experiments in both Secs. and and 5.2) and the results
(Fig. App. E) show that they are outperformed by neural contextual bandit algorithms.
6 CONCLUSION
This paper describes the first federated neural contextual bandit algorithm called weighted combination of two UCBs and the choice of this weight required by our theoretical analysis has an interesting interpretation emphasizing accelerated exploration initially and accurate prediction of the aggregated NN later. We derive upper bounds on the regret and communication complexity of FN-UCB, and verify its effectiveness using empirical experiments. Our algorithm is not equipped with privacy guarantees, which may be a potential limitation and will be tackled in future work.
We use
"Since diagonalization increases the scale of the first term in UCB we use heuristic rescale the values of this term for all contexts such that the max and min values (among all contexts) are O and after rescaling.
9

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We have included the necessary details to ensure the reproducibility of our theoretical and empirical results, For our theoretical results, we have stated all our assumptions Sec. _ added a proof sketch in Sec. 4.2 and included the complete proofs in App. C and App. D Our detailed experimental settings have been described in Sec. 5.1 Sec. 5.2 and App. Our code has been submitted as supplementary material.
ACKNOWLEDGMENTS
This research/project is supported by A*STAR under its RIF2020 Advanced Manufacturing and Engineering (AME) Industry Alignment Fund Pre Positioning (IAF-PP) (Award A19E4a0101).
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Proc. NIPS, 2011.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff's. In Proc. ICML, pp. 127-135, 2013.
Peter Auer. Using confidence bounds for exploitation-exploraiin trade-offs. JMLR, 3(Nov):397-422 2002.
Yikun Ban and Jingrui He. Convolutional neural bandit: Provable algorithm for visual-aware advertising. arXiv:2107.07438, 2021.
Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Fe-net: Exploitation-exxploraaionn neural networks in contextual bandits. In Proc. ICLR, 2022.
Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proc. ICML, pp. 844-853, 2017.
Radu Ciucanu, Pascal Lafourcade, Gael Marcadet, and Marta Soare. SAMBA: A generic framework for secure federated multi-armed bandits. JAIR, 73:737-765, 2022.
Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated Bayesian optimization via Thompson sampling. In Proc. NeurlPS, 2020.
Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Differentially private federated Bayesian optimization with distributed exploration. In Proc. NewrIPS, 2021.
Zhongxiang Dai, Yao Shu, Bryan Kian Hsiang Low, and Patrick Jaillet. thapol--ten-optimize batch neural Thompson sampling. In Proc. NeurIPS, 2022.
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Proc. COLT, pp. 355-366, 2008
Ilker Demirel. Yigit Yildirim, and Cem Tekin. Federated multi-armed bandits under byzantine attacks. arXiv:2205.04133. 2022.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:://accciveee ics. uci. edu/mI
Abhimanyu Dubey and Alex Pentland. Differeentially-riival federated linear bandits. In Proc. NeurIPS, pp. 6003-6014, 2020.
Xiaofeng Fan, Yining Ma, Zhongxiang Dai, Wei Jing, Cheston Tan, and Bryan Kian Hsiang Low. Fault-tolerant federated reinforcement learning with theoretical guarantee. In Proc. NeurIPS, 2021.
10

---

Published as a conference paper at ICLR 2023
Kristjan Greenewald, Ambuj Tewari, Susan Murphy, and Predag Klasnja. Action centered contextual bandits. In Proc. NIPS, 2017.
Quanquan Gu, Amin Karbasi, Khashayar Khosravi, Vahab Mirrokni, and Dongruo Zhou. Batched neural bandits. arXiv:2102.13023 2021.
Stephanie Holly, Thomas Hiessl, Safoura Rezapour Lakani, Daniel Schall, Clemens Heitzinger, and Jana Kemnitz. Evaluation of pyperparameeer-oiimizattt approaches in an industrial federated learning system. arXiv:21 10.08202, 2021.
Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang. FL-NTT: neural tangent kernel-based framework for federated learning analysis. In Proc. ICMI, pp. 4423-4434 2021a.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. In Proc. NeurlPS, 2021b.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Proc. NeurlPS, 2018.
Ali Jadbabaie, Haochuan Li, Jian Qian, and Yi Tian. Byzantine-robust federated linear bandits. arXiv:2204.01155,, 2022.
Yiling Jia, Weitong Zhang, Dongruo Zhou, Quanquan Gu, and Hongning Wang. Learning neural contextual bandits through perturbed rewards. In Proc. ICLR, 2021.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv:1912.04977, 2019.
Parnian Kassraie and Andreas Krause. Neural contextual bandits without regret. Proc. AISTATS, 2022.
Parnian Kassraie, Andreas Krause, and Ilija Bogunovic. Graph neural network bandits. In Proc. NeurIPS, 2022.
Mikhail Khodak, Renbo Tu, Tian Li, Liam Li, Maria-Florina Balcan, Virginia Smith, and Ameet Talwalkar. Federated hyperparameter tuning: Challenges, baselines, and connections to weight- sharing. arXiv:2106.045002 2021.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. Proc. AISTATS, 2022a.
Chuanhao Li and Hongning Wang. Communication efficient federated learning for generalized linear bandits. In Proc. NeurlPS, 2022b.
Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Communication efficient distributed learning for kernelized contextual bandits. In Proc. NeurlPS, 2022.
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bane approach to personalized news article recommendation. In Proc. WWW, pp. 661-670, 2010a.
Qinbin Li, Zeyi Wen, Zhaomin Wu, Sixu Hu, Naibo Wang, Yuan Li, Xu Liu, and Bingsheng He. A survey on federated learning systems: vision, hype and reality for data privacy and protection. IEEE Transactions on Knowledge and Data Engineering, 2021.
Tan Li and Linqi Song.
communication-efiiee federated multi-ane bandits. IEEE Journal on Selected Areas in Communications, 2022.
Tan Li. Linqi Song, and Christina Fragouli. Federated recommendation system via differential privacy. In Proc. IEEE ISIT, pp. 2592-2597, 2020.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions.
2014.

---

Published as a conference paper at ICLR 2023
Wei Li, Xuerui Wang. Ruofei Zhang, Ying Cui, Jianchang Mao, and Rong Jin. Exploitation and exploration in a performance based contextual advertising system. In Proc. KDD, pp. 27-36, 2010b.
Michal Lisicki, Arash Afkanpour, and Graham W Taylor. An empirical study of neural kernel bandits. In NeurlPS Workshop on Bayesian Deep Learning, 2021.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication-effcceentt learning of deep networks from decentralized data. Proc. AISTATS, 2017.
Ofir Nabati, Tom Zahavy, and Shie Mannor. Online limited memory neural- bandits with likelihood matching. In Proc. ICML,, 2021.
Thanh Nguyen-Tang. Sunil Gupta, A Tuan Nguyen, and Svetha Venkatesh. Offline neural contextual bandits: Pessimism, optimization and generalization. In Proc. ICLR, 2022.
Sudeep Salgia, Sattar Vakili,, and Qing Zhao. Provably and practically efficient neural contextual bandits. arXiv:2206.00099 2022.
Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In Proc. AAAI, 2021.
Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armed bandits with personalization. In Proc. AISTATS, pp. 2917-2925, 2021.
Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. ICML, pp. 1015- 1022, 2010.
William R Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285-29) 1933.
Sattar Vakili, Michael Bromberg, Jezabel Garcia, Da-shan Shiu, and Alberto Bernacchia. Uniform generalization bounds for overparameterizze neural networks. trXiv:2109.06099 2021.
Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time
analysis of kernelised contextual bandits. In Proc. UAI, 2013.
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optimal regret with efficient communication. In Proc. ICLR, 2020.
Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. arXiv:2012.01780, 2020.
Zirui Yan, Quan Xiao, Tianyi Chen, and Ali Tajer. Federated multi-armed bandit via uncoordinated exploration. Proc. ICASSP, pp.
2022.
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural Thompson sampling. In Proc. ICLR, 2021.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-based exploration. In Proc. ICML, pp. 1142--1 11502, 2020.
Yi Zhou, Parikshit Ram, Theodoros Salonidis, Nathalie Baracaldo, Horst Samulowitz, and Heiko Ludwig. Flora: Single-shot hyper-parameter optimization for federated learning. arXiv:2112.08524, 2021.
Yinglun Zhu, Dongruo Zhou, Ruoxi Jiang, Quanquan Gu, Rebecca Willett, and Robert Nowak. Pure exploration in kernel and neural bandits. In Proc. NeurIPS, volume 34, pp. 11618-11630 2021a.
Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. Proc. ACM Meas. Anal. Comput. Syst., 5(1):1-29, 2021b.
Hankz Hankui Zhuo Wenfeng Feng, Yufeng Lin, Qian Xu, and Qiang Yang. Federated deep reinforcement learning. arXiv:1901.08277, 2019.
12

---

Published as a conference paper at ICLR 2023
A RELATED WORKS
Federated Bandits. Federated learning (FL) has received enormous attention in recent years (Kairouz et al. 2019; Li al. 2021 2014, McMahan al.] 2017). A number of recent works have extended the classic K armmdd bandits (i.e., the arms are not associated with feature vectors) to the federated setting. & Song (2022) and Li et al. (2020) focused on incorporating privacy guarantees into federated K Karmed bandits in both centralized and decentralized settings. (Shi & Shen (202T) proposed setting where the goal is minimize the regret of a global bandit whose reward of arm is the average of the rewards of the corresponding arm from all agents, which was later extended by adding personalization such that every agent aims to maximize a weighted combination between the global and local rewards (Shi et al., 2021). Subsequent works federated K Kaareed bandits have focused on other important aspects such as decentralized communication via the gossip algorithm (Zhu et al. 2021b), b), the security aspect via cryptographic techniques (Ciucanu et al. 2022) uncoordinated exploration Yan et al. (022), and robustness against Byzantine attacks (Demirel al. 2022). Regarding federated linear contextual bandits, |Wang al. (2020) proposed distributed linear contextual bandit algorithm which allows every agent to use the observations from the other agents by only exchanging the sufficient statistics to calculate the Linear UCB policy. Subsequently,
Dubey & Pentland (2020) extended the method from Wang et al. (2020) to consider differential privacy and decentralized communication, Huang et al. (2021b) considered a setting where every agent is associated with unique context vector, [i & Wang (2022a) focused asynchronous communication, and [Jadbbaie al. (2022) considered the robustness against Byzantine attacks. Federated kernelized/GP bandits (also named federated Bayesian optimization) have been explored by Dai et al. (2020) 2021), which focused on the practical problem of hyperparameter tuning in the federated setting. The recent works of of et al. (2022); Li & Wang (2022b) have, respectively, focused on deriving connmunicaiion-effcieee.. algorithms for federated kernelized and generalized linear bandits. In addition to federated bandits, other similar sequential decision-making problems have also been extended to the federated setting, such as federated reinforcement learning (Fan et al.
202T Zhuo et al. 2019) and federated hyperparameter tuning (Holly al. 2021 Khodak et al. 202
Zhou et al. 2021
Neural Bandits. Since the pioneering works of Zhou et al. (2020) and Zhang et al. (2021) which, respectively, introduced Neural UCB and Neural TS, number of recent works have focused on different aspects of neural contextual bandits. Xu et al. (2020) reduced the computational cost of Neural UCB by using an NN as feature extractor and applying Linear UCB only to the last layer of the learned NN. Kassraie& Krause (2022) analyzed the maximum information gain of the NTK and hence derived no-regret algorithms, Gu et al. (2021) focused on the batch setting in which the policy is only updated at a small number of time steps, Nabati et al. (202T) aimed to reduce the memory requirement of Neural UCB, Lisicki et al. (2021) performed
empirical investigation of neural bandit algorithms to verify their practical effectiveness, Ban et al. (2022) adopted a separate NN for exploration in neural contextual bandits, Ban & He (2021) applied the convolutional NTK, Jia et al. (202T) used perturbed rewards to train the NN to remove the need for explicit exploration, Nguyen- Tang al. (2022) incorporated offline policy learning into neural contextual bandits, (hu ct al. 2221aa) studied pure exploration in kernel and neural bandits, Kassraie et al.) (2022) applied
graph NNs in neural bandits to handle graph-structured data, (Salgia et al. (2022) extended neural bandits beyond the ReLU activation to consider smoother activation functions. and Dai et al. (2022)
introduced a scalable batch Neural TS algorithm through sumple-thenooptimize optimization.
B MORE BACKGROUND
In this section, we give more details some of the technical background mentioned in Sec. 2 The details in this section all follow the works of Zhang et al. (202I); Zhou et al. (2020), and we present them here for completeness.
13

---

Published as a conference paper at ICLR 2023
Definition of the NN f(;; 0). Let W1 E Rmxd Rmx1 then the NN f(z; 8) is defined as
W, E Rmxm 1I = ...... L and WL
fi WIx.
Ji W 22.., L.,
[(:; 0) - Vmfl,
in which RzLU(=) max(=, 0) denotes the rectified linear unit (ReLU) activation function and is applied to each element of fi-1- With this definition the NN, 0 denotes the collection of all parameters of the NN: 0 (vee(Wi),.... vec vec(WL)) L)) RR
Details of the Initialization Scheme Oo init(.). To obtain the initial parameters Og. for each
W
0
== 1= - 1, let Wt =
where each entry of W is independently sampled from
0
W
(000 4/m), and let W. = (w
) where each entry of w is independently sampled from
(0, 2/m). This initialization scheme is the same that used by the works of Zhang et al. (202) Zhou et al. (2020).
Definitions of the NTK Matrices H and H;'s To simplify the exposition here, {> brl..=I... to denote the set of all contexts from all iterations, all arms and all agents: (eT.eeeTTTAAAAAEI..E. We can then define
H 2 = (6',
= 2E (u.))~N10. (1) max(u, uu 0) max(u, 0),
H! 2H ( (9) 1(u 0)1 > 0) + 2/
(++1)
With these definitions, the NTK matrix is defined as H + Σ )/2) Similarly, H, can be obtained in the same way by only using all contexts from agent i the definitions above, i.e., now we use {2r) } jj.1....TKK TK to denote (=f, hejTTtt))))) and plug these TK contexts into the definitions above to obtain H.
C PROOF OF REGRET UPPER BOUND (THEOREM
We use p to index different epochs and denote by the total number of epochs. We use tp to denote the first iteration of epoch p. and use Ep to represent the length (i.c., number of iterations) of epoch Throughout our theoretical analysis, we will denote different error probabilities as .1.... ., Åg. which we will combine via union bound at the end of the proof to ensure that our final regret upper bound holds with probability of at least
C.I CONDITIONS ON THE WIDTH m. OF THE NEURAL. NETWORKS
We list here the detailed conditions the width of the NN that are needed by theoretical analysis. These include two types of conditions, some of them (conditions 1-4) are required for our regret upper bound to hold (i.e., they are used during the proof to derive the regret upper bound), whereas the others (conditions 5-6) are used after the final regret upper bound is derived to ensure that the final regret upper bound small (see App. C.6).
When presenting our detailed proofs starting from the next subsection, we will refer to each of these conditions whenever they are used by the corresponding lemmas. Different lemmas may use different leading constants in their required condition (i.c.. lower bound) on m. but here we use the same constant C > 0 for all lower bounds for simplicity, which can be considered as simply taking the maximum among all these different leading constants for different lemmas.
m 2 C 6 logee/oooTTTTNAAA. (TKN)))),
2. 2 CTTK*N4T log l
14

---

Published as a conference paper at ICLR 2023
3. 2 CVAL 3/2 (
4. m (loogm) -
-7 VT/A).
5. m(log 2
6. mllogm)
T
Some of these conditions above can be combined, but we leave them as separate conditions to make easier refer the corresponding place the proof where particular condition is needed.
Furthermore, to achieve a small upper bound on the cumulative regret, we also need to place some conditions on the learning rate 7) and number of iterations for the gradient descent training (line 14 of Algo. Db. Specifically, we need to choose the learning rate as
7 = C1(mA + mT
(2)
in which C4 is absolute constant such that C4 I 1 + TL, and choose
1 J= = C4
1
log 3C2N T&T. = (TLL(AAC))
(3)
C.2 DEFINITION OF GOOD AND BAD EPOCHS
Denote the matrix Via (see line 18 of Algo. D after epoch p as Vp- As a result, the matrix Vp is calculated using all selected inputs from all agents: Vpp =p=-i Σi= Ei= (0))(,;;))) 0o) //m AL. Define Vo AL. Imagine that we have a hypothetical agent which chooses all T x N sequentially
round-robin fashion (i.e., the hypothetical agent chooses 11,1, 11, ........ 22,1,,,,,121....... F2. NT,N), and denote the corresponding hypothetical covariance matrix as V = Σ Σj= gi (Zr. 0o) /mm + Ej=1 1 (olt),0000g(( 00) fm + AL. We represent the indices of this hypothetical agent by t' E [TN] to distinguish from our original multi-agent setting. Define JIN - [g(#;; 0o) (o)] which a x (TN) matrix, and define KIN A JIN /m, which is (TN) (TN) matrix. According thes definitions, have that Lemma (Lemma B.7 of Zhang et al. (202I)). Let 8
queries (Jr,s)
(0, 1). CT N K Iog(TNKL//55 we have with probability of least 81 that
If m 2
let --*KK,) s det - + +1, E [TN].
The condition m given in Lemma used here instead of in App. C.I
corresponds to condition listed in App. C.I except that 8₃ is Lemma allows us to derive the following equation, which we will use (at the end of this section) to justify that the total number of "bad" epochs is not too large.
detV p+l log detV,
detVp (a) log det (JINJTN/m + AL)
log detV,
detV,
det (* (2 JTN''JNNJTN +1)
log
detV
( Aed JT/J
log
APo
log det
(X- JINJJNNJ/
(c) log det
(x JTT//N//mmm
(x (X-*Kng 'KN +1
log det
log det
(A-1
(c) d (1 + //N) + R..
15

---

Published as a conference paper at ICLR 2023
Step (a) is because Vp JINNJNNmm + XI according to definition of JIN above. Step (b) follows from our definition of Vo = >I above, as well as some standard properties of matrix determinant. Step (c) follows because: det(AA + I) det(A A + I). Step (d) has made use of Commmaaabovee which suggests that equation 4 holds with probability of at least 1 - 01. Step (e) follows from the definition of d A log detec/+H//M (Sec. 2 In the last step, we have defined KN/A1+7KN/AJ
R' - d TKK/A) + 1. We further define R - [R]], in which [-] denotes the ceiling operator.
Now we define all epochs p's which satisfy the following condition as "good epochs":
1 detV, detV,
S
(5)
and define all other epochs "bad epochs". The first incquality trivially holds for all epochs according to the way in which the matrices are constructed.
easy to verify that the second inequality holds for least R epochs (with probability of at least 1 - 61). This is because if the detV,
second inequality is violated for more than R epochs (i.e., if log deVV,-
for more than R epochs),
detV, then Ep= log delV, > R. which violates equation 4 This suggests that there are no more than R bad epochs (with probability of at least - 52). From here onwards, we will denote the set of good epochs by goood and the set of bad epochs by Eaad
C.3 VALIDITY OF THE UPPER CONFIDENCE BOUND
In this section, we prove that the upper confidence bound used in our algorithm, (1 o2) ox)UCBB ag ,UCBB), (used in line 7 of Algo. I.. is a valid high-probability upper bound on the reward function h. We will achieve this by separately proving that UCB,, and UCB probability upper bounds on h in the next two sections. Note that for both UCBs, unlike Neural UCB (Zhou et al., 2020) and Neural TS (Zhang al., 2021) which use 0g (the parameters of trained NNs) calculate the exploration term (the second terms of UCB,, and UCB instead use 6g- This is consistent with Kassraie & Krause (022) who have shown that the use of On gives accurate uncertainty estimation.
valid high-
C.3.1 VALIDITY OF UCB,, AS A HIGH-PROBABILITY UPPER BOUND ON h:
To begin with, will need the following lemma from Zhang et al. 2021
Lemma 2 (Lemma B.3 of Zhang et al. (2021)). Let d2 E (0, There exists a constant C >> such that if
m 2 CT K-
then with probability of 1 - 82 over random initializations of 0g there exists a 8" E TRPo such that
M(x:) (g(2;; 0n), 0" 0o): vmll0r 00ll2 < 22hTH-11 S B,V E Ny,, [T], E (N). (6)
The condition on m required by Lemma ò2 is used here instead of 8 as in App. C The following lemma formally guarantees the validity of UCB as a high-proc biab-rrbbability upper-boure bound on h.
corresponds to condition listed in App. C.I except that
Lemma 3. Let d3 E 10, and WTKN B+ + Ry 2(log(1/6g) + 1) + dogg(1 + TKKNAA). We all E [T] [NV] that
have with probability of at least 1 8₁ -8-
[h(z) - (g(x; 00)/ / m, [
0o)/ v Vo E Xe,
Proof. Lemma can be proved by following similar steps as the proof of Lemma 4.3 in the work of Zhang et al. (2021). Specifically, the proof of Lemma 3 requires Lemmas B.3, B.6 and B.7 of Zhang et al. (2021) (after being adapted for our setting). The adapted versions of Lemmas B.3 and B.7 of Zhang al. (2021) have been presented in Lemma 2 Lemma[ respectively. Of note, Lemma I and Lemma require some conditions on the width m of the NN, which have been listed conditions 1 and 2 in Appendix C.T Lastly, Lemma B.6 of Zhang al. (202T), which makes
16

---

Published as a conference paper at ICLR 2023
of Theorem 1 of Chowdhury & Gopalan (017). can be directly applied in setting and introduces an error probability of d3 (which appears in the expression of VI KN). As a result, Lemmal 3 holds with probability of at least 1 61 62 6g, in which the error probabilities come from Lemmal (61), Lemma 2 (d2) and the application Lemma B.6 of Zhang et al. (202T) (6z).
C.3.2 VALIDITY OF UCB AS A HIGH--PROBABILITY UPPER BOUND ON h:
Note that UCB is updated only in every communication round. We denote the set of iterations after which UCB is updated (i.e., the last iteration in every epoch) as T-1 _ ftz 1 P-1, which immediately implies that T-1 C [T] and hence IT-1 < T.
Lemma 4. Let o4, 8g E (0, and VTK = B + R 2(log(N/5A) + +) 1)+ + Imax log(1 + TK/A)
for some constant C> O, as well condition 4 in Appendix C.I Suppose the learning rate n and number of iterations of the gradient descent training satisfy the conditions in equation P and equation 3 (App. C.T).
Suppose the width m of the NN satisfies m > CVAL 3/2 (
respectively. We have with probability of least 84 ôō for all t T-1, [N), that
N
[h(x) - fxx; sync,,N) S VTKVA
19(2; 00)/ (V/ood) + Einear (m, (m, Vx E Ne.
N
Proof. Note that the condition on m listed the lemma, m 2 CVAL 3/2 (og corresponds condition 3 listed in App. C.I except that 85 used here instead of 5. Therefore. the validity of Lemma requires conditions 3 and on m (App. C.T to be satisfied. For ease of requirres
exposition, separate proof into three steps.
Step 1: NN Output (a; ( Is Close to (Averaged) Linear Prediction
Based on Lemma C.2 of Zhang al. (2021), if the conditions listed in Lemma is satisfied, then for any 0 such that 0 0u
S 2 2/t/(mA), there exists constant C₁ > 0 such that we have
with probability of at least 1 85 over random initializations 0g that
(f(=;)) - (g(2; 0o)1 < 2// 1/ 2/3 L llooog m
2/3 1, V < 2/ 11/6 2/3
log
Elincar, (m,
which holds Vr E Xx,,, / i E [N].
Also note that according to Lemma C.1 of /Zhang et al. (021). if conditions 3 and 4 on m listed in App. [C.T, as well as the condition on 17 equation 2 are satisfied, then we have with probability of
at least 1 - ô5 over random initializations On that 00; 0p 01l2 < 2 ///mm,, Vi E [N]. An immediate implication is that the aggregated NN parameters Osyno,NN = + N iml Of also satisfies:
1 N
0|0yDc..N 80l12
1 N
0
8
Σ
0
80 8011
5 22/t/m/.
N
This implies that equation Tholds for OwynENN with probability of at least 205:
[s Oyyne.NN) - (g(2; 0o), OyBC.NN - 0u) S Siiner, (m, T).
(8)
Next, note that the 0f is obtained by training only using agent i's local observations (line 14 of Algo. Define Ølocal (V/lgcl)--1 ( (r, 0o) /m). Note that Glocal is calculated in the same way as B,, (line 4 of Algo. D. except that its calculation only involves agent i's local observations. Next, making use of Lemmas C.1 and C.4 of Zhang al. (202T), we can follow similar
17

---

Published as a conference paper at ICLR 2023
steps equation C.3 of Zhang et al. (2021) (in Appendix C.2 of Zhang et al. (202 to show that
there exists constants C2 and C3 such that we have Vo E d,,s, E E M that
(g 0o), 02 0n) (g(a;; 0a)/ //m, 0
v C2 - vymA)' VLL.A++ + Cym - 1/6 /logm..* X-133111111111111111111 + v1/A)
(9)
< C2(1 - mymA)' VTL/A+ Cam 1166 VllgmL m (1 VT/A)
A En + Siiearr (m, T).
We refer to (g(x; Bo)l /m, @local) as the linear prediction because it is the prediction of the linear model with the neural tangent features (2; 0o)/ /m as the input features, conditioned on the local observations of agent i. Note that similar to equation [ which also relies on Lemma C. of Zhang et al. (202T), equation / also requires conditions 3 and 4 on m, well the condition on r/. in App. C. to be satisfied. equation 9 come from the use of Lemmas C.I and C.4 of Zhang al. (2021).
holds with probability of at least 1 - 285. where the error probabilities
Next, we can bound the difference between (a; NN)) (i.e., the prediction of the NN with the aggregated parameters) and the averaged linear predictions of all agents calculated using their local observations:
(2; Osyno.NN)
Σ (g(2;; 00) //m 0bocal)1 S (a;; OsynENNN)
ig(a; 0o), Of 0o)
N
N
N
Σ La(o;; 0o), 02 -0o)
1
Σ
Lola; 0o)/ m ا
N
N
2=1
$ 1f (2; bYNNNN) - (g(2;00), Oaync.NN - Bo}
(10)
(o(2;00), - -0o) - -(((;; 0o) /mm o
1 N
Elineur, 1 (m, T)
Σ (En. + Elineur, (m, I))
N
Elinerr, (m, T) + Enp + Stinear, (m,,
Elincar (m, T).
In the second inequality, plugged in the definition of A syn..N N E 0f. In the third inequality, we have made use of equation and equation 9 equation holds with probability of at least -8%- where the error probabilities come from equation & (205) and equation (2(ss) respectively. Now we replace 6, by 6c/4, which ensures that equation 10 holds with probability of at least 1 ōg. This will only introduce factor of 4 within the log of condition 3 on m (App. C.I, which ignored since can be absorbed by the constant C.
Step Linear Prediction Close to the Reward Function h(x)
In the proof in this section, we will also need a "local" variant of the confidence bound of Lemma 3 i.e., the confidence bound of Lemma calculated only using the local observations of an agent d:
Lemma 5 (Zhang et al. 2021 [N], that
We have with probability of least 1 - foror all T-1 [T]
[h(x)) (g(x; 0o)/ / Omaal UTK VTKKV\11(25000)) m (V Ve Xe,--
Proof. Similar to the proof of Lemma 3 (App. C.3.I the proof of Lemma allso requires Lemmas B.3, B.6 and B.7 from Zhang et al. (2021), which, in this case, can be directly applied to our setting
(except that we need an additional union bound over all N agents). The implication of the additional union bound on the error probabilities is taken care of by the additional term of N within the log in the expression of V' (Lemma and conditions and 2 on m (see App. C.I and also Lemmas] [] and T). The required lower bounds on m by the local variants of Lemmas B.3 and B.7 (required in
18

---

Published as a conference paper at ICLR 2023
the proof here) smaller than those given in Lemmas and and hence do not need to appear in the conditions in Appendix [C.]] By letting the sum of the three error probabilities (resulting from the applications of Lemmas B.3, B.6 and B.7 of Zhang al. (2021) be 64,
ensure that Lemma [ holds with probability of at least 84 For simplicity, we let the error probability for Lemma B.6 be 54. which leads to the cleaner expression of MTK in Lemma This means that the error probabilities for Lemmas B.3 and B.7 are very small, which can be accounted for by simply increasing the value of the absolute constant C' in conditions and on (App. C.I and hence does affect our main theoretical analysis.
Step Combining Results from Step and Step
Next, we are ready prove the validity of UCB by using the averaged linear prediction N (9 00)/ /m, o an intermediate term:
(I::0Oy)NNN) h(x))l
N
N Σ
= (f; NNym
Σ N
[g(x; 00)/ glocaly
(g( 0/0/ m, 0 - k(x))
N
Kg(æ; 00)/ Vm, oloysa)) - h1(z)] + Elinear (m, T)
N
PTK [l19((2000//// (Virr)) Elinear ( (m, T)
N
VTKV VTKVAllo(<;; 00)/
(V + Elincar (me T)
(11)
The second inequality has made of equation 10 and the third inequality follows from Lemma
In the last inequality, we have made the substitution of (V:local-11 (V/local) This is because in
the proof of Lemma 4 here, only consider the iterations of T-1 2 {t, - 1) 2 P- last iteration of every epoch. As result, this ensures that (V/local) (V/ Vi [N] (line of Algo. 2
i.e. the
1,1 because every time
the central server obtains (V/loaa)= - through (V/loca)-
we have that the current iteration ł is the last iteration of the previous epoch. As results, equation
holds with probability at least 1 - 54 65. in which the error probabilities come from equation 10
(8s) and Lemma 5 (61). other words, Lemma 4 (i.c., the validity of UCB holds with probability of at least 64 85.
C.4 REGRET UPPER BOUND FOR GOOD EPOCHS
In this section, we derive an upper bound on the total regrets incurred in all good epochs goood (defined in App. C
C.4.1 AUXILIARY INEQUALITY
We firstly derive auxiliary result which will be used in the proofs later.
19

---

Published as a conference paper at ICLR 2023
For agent i and iteration & in good epoch p E goord we have that
Vallg(2; (olda:00ommmmmm Vi.
>a(e; TV g(
c, 00)/m
detVe. detV 1,
As(e; 00) (Q,)VV Vi ((2; 00)/m
detV,
(12)
< >g(2; 80) VV, g(:; 00)/m
detVp-1
< edg(2; 0o) 4, g(x; 80)/m
ge 0n)
Recall that V., (line of Algo. is used by agent in iteration select ž (via UCB;,)) and that the matrix Ve, is defined for the hypothetical agent which sequentially chooses all TN queries (T) in a round-robin fashion (App. C.2). The first inequality in equation 12 above follows from Lemma 12 of Abbasi- Yadkori al. (201T). The second inequality is because Vp contains more information than Vr, (since V is calculated using all the inputs selected after epoch p). and V contains less information than V.s (because compared with V--1. V.,, additionally contains the local inputs selected by agent i in the current epoch p). In the last inequality, we have made use of the definition of good epochs, i.e., (detVp)/ (ett)//deV//)))) S e (App. C.2
C.4.2 UPPER BOUND ON THE INSTANTANEOUS REGRET Trç
Here assume that both UCB and UCB,,, hold (hence we ignore the error probabilities here), which we have proved in App. C,3 We now derive an upper bound on the instantaneous regret Te, h(tt,) - h(z,,;) for agent and iteration in a good epoch p goood.
Tz.s = Mx(1,) - h(*1,))
= ah(aī,)) + (1 - a))((ri,)) h(x1,))
s aUCB", (zi,,) + at ae (m, T) + (1 Q)UCCBi M(x,.)
S aUCB,, (F).)) + (1 ( + ae (m, T) M(F(,))
(UCB)) (1r,)) (1.s)) -((ss) + a1-a) (UC - M(rr)) + arstinear (m, T)
s a (2VTK VAlg(ar 000/ vmll (yyooe) + Elincar (m, T")
(1 -
) + ae (m, T)
(13)
(1)00))- 5 2VTK Alggann (00( (1 + Elincar (m, T)
(1 - (2TTRNVeellllee.. v
ml v ae (m, I')
a2VTK VAll m (1 +
(1 a) 00)/ Vm
22e (m, T')
N
P (1 2)2UTKN + a2vTK
glocal ( + 20 (m, (m,T). T).
N 1=1
The first inequality makes use of Lemma (i.e., the validity of UCB and Lemma (i.e.,
the validity of UCB(,). The second inequality follows from the way in which dn is selected
20

---

Published as a conference paper at ICLR 2023
(line 7 of Algo. 1:: Ft,a arg m (1 ())C + aUCB (z). The third inequal- ity again makes use of Lemma g and Lemma 4 as well the expressions of UCB,, and UCB In the fourth inequality, we have made used of the auxiliary inequality of equation 12 we derived in the last section. Recall that we have discussed that (V/local)-1 = (Viocal)
for all t = 1p at the end of App. C.3.2 Therefore, in the last step, we have defined سل 1. (TA
V 0o) ///////lll / which repre- sents the GP posterior standard deviation (using the kernel of k(x, x²) = g(z; ( :(x:: conditioned on all agent j's local observations before iteration Ey. Note that oliml 1p-1.j (Zt,s) the same as the one defined in Sec. of the main text where we explain the weight between the two UCBs. Similarly, we have also defined (zr,)) VAllg(Zr.:: (o)/ /ml v which represents the GP posterior standard deviation conditioned on the observations of the hypothetical agent before Z2,i is selected (App.
( 0n)/ /m/l
Next, will separately derive upper bounds the summation (across all good epochs and all agents) of the first and second terms of the upper bound from equation 13
C.4.3 UPPER BOUND ON THE SUM OF THE FIRST TERM OF EQUATION 13
Here, similar to Kassraie & Krause 2022), we denote as Ko an upper bound on the value of
the NTK function for any input: (g(;;; Oo)/ Vmm g(x; 0o)/ /m) < Ko, Va E Ne,, E [7], i
[N]. As a result, we can use it to show that both (z,i(z) and اlgaal
(,-11,(x) (2) can be upper-bounded:
(x,(())= I Vno and @loccll 1 (x) S /no. To show this, following the notations of Appendix C.2 we
denote Vr,, Je + Al where J,,; [9(0n 0o)] rele- rE(c-11.EENN) [1.EEN) [g( 0o)] se14] which is Po x [[t - 1)NV + i[] matrix. Then we have
(x) Al|g(1; 00)/ / /mll m b
>g(=;00)) (Je,J + 2 00)/m
=>g(a; TT) T ( - (T+ JT. (1as)) JT. g((); 0m)
1
=g(=;00) g(:; 00)/m - 0o) T/ // Je, (N + JT.Jes) (Ts -T. (14)
-(<;00) 0o) g(:; 0o) m (o(=;00)' m) (AI+J).dh.))
g(:; 0n) g(;; 00) N0
where we used the matrix inversion lemma in the third equality. Using similar derivations also allows us show that (اlيجق (2:))² & Köp- Therefore, have that (2r) S /Kg and glocal "
(x) S /Ro-
21

---

Published as a conference paper at ICLR 2023
Denoting the set of iterations from all good epochs as T we can derive upper bound the first term equation 13 summed across all agents E [N] and all iteration in good epochs T
T
Σ (1 Vo S 2VETTKN
(
i=1 EET
N T
(b)
min /
(0) 2EETTKN
min ( V
$ 22VETKKNV K50
min (2e,))
(15)
"2 3 2VVTKN
T
TN
min (2,,))
12 VEUTKN NO - + 1)
(
< 2VZEVTKN TNAllog 1) +
2 TNA Tlog(1 + +TNK/A)+11 +1]
Step (a) follows from a S 1, and summing across all iterations [T] instead of only those iterations Toood in good epochs. Step (b) follows because (x) S /No discussed above. In step (c), we have assumed that Ko 2 1; however, if Ko < 1, the proof still goes through since we can directly upper-bound min(ō,,4 (zt,)), /Ko} by (2,,)), 1), after which the only modification we need to make to the equation above to remove the dependency on multiplicative term of /Ko- Step (dl results from the SScchy-Schwarz inequality. Step (c) be derived following the proof of Lemma 4.8 of Zhang et al. 2021) (in Appendix B.7 of Zhang et al. (2021)). ). Step (f) follows from Lemma I and hence holds with probability of at least I 01- The last equality simply plugs in the definition of the effective dimension d (Sec. 2).
C.4.4 UPPER BOUND ON THE SUM OF THE SECOND TERM EQUATION 13
In this subsection, we derive an upper bound on the sum of the second term in equation equation 13 across all good epochs and all agents.
For the proof here, we need "local" version of Lemma T i.e., a version of Lemma D which only makes use of the contexts of an agent i. Define K,,, the local counterpart to Ky (from Lemma [ ie., K is the t x matrix calculated using only agent j's local contexts up to (and including) iteration t. Specifically, define Je,s [g( 0o)l-ete which is a Po X f matrix, then K,, is defined
K2, A JT,.J.../mm which is & x & matrix. Also recall that in the main text, have defined H; as the local counterpart of H for agent i (Sec. 2). The next lemma gives our desired local version of Lemma
If 2 CT log Lemma 6 (Lemma B.7 of Zhang al. 2021
have with
probability of at least 1 de that
log det (T / + K.s) & log det (1 + - + 1,
for all t [
We needed to take a union bound over all N agents, which explains the factor N within the log in the lower bound is smaller than that of Lemma (by a factor of N8), therefore, the condition on m in Lemma 18 ignored in the conditions listed App. C.1
given in Lemma 6 Note that the required lower bound by Lemma
22

---

Published as a conference paper at ICLR 2023
Of note, throughout the entire epoch p. O, (.; is calculated conditioned on all the local observations of agent before iteration tp- Denote by T(2) the iteration indices in epoch T(p)
(1p:.....p 1p + Ep 1]. In the proof in this section, as we have discussed in the first paragraph of
Sec. |.1 we analyze a simpler variant of our algorithm where we only set a >> 0 in the first iteration
after a communication round, i.e., a > 0, Vt E (tptpe[r] and a Vt E [7] \ ppp] Now we are ready to derive an upper bound on the second term in equation
13 summed over all agents and all
good epochs:
Σ
Σ PEEPS BET
a2vTK
1 N
Jocal
1--1,
(a) (11,))
S
20TK
a
N
1,j
(
[P[P) (ET())
j=1
(6)
N
N
2VTK N
aō bo ر.ا (نن
Incal
==1
j=1 [E[P]
N
N
20TK N
0 tp
local
(21p.))
1=
PE[P]
N
N
T
20TK N
Σ
local 1.j (Tt5)
(16)
The inequality in step (a) results from summing across all epoch p E [P] instead of only good epochs p E ggood_ Step (b) follows since at = 0, Vt E [T] (pphetpp) as we discussed above, therefore, for every epoch p. we only need to keep the first term of t to in the summation of t T(p), To understand step (c). recall that in the main text (Sec. 3.3 we have defined: glocal tii.min A minngxx Glocal (x)) and Glocal A maxxex glocal (loca((x)) Vi E [M] Next, note that our t,i.mxx algorithm selects a by: a = minge[N] 04,s (line of Algo. 2 where ag, = gloca /olocal /
t.t.min// 1,i,max (line 15 of Algo.[] [T) and tp - 1 since at is calculated only in the last iteration of every epoch. As result, we have that
local Tocal 1 m,i,ax
aaccal
Glocal Up 1.j (Jtppt)
Limmin
1p--1.11 1.j.min
a min 0tg [E[N]
min (E(N]
local
Tocal 1 1. (z))))s)
J.j.ax
which tells us that aotp 1. (I,,.)) S Glocal
1.j (2) and hence leads to step (c). Step (d) results from summing across all iterations [7] instead of only the first iteration of every epoch.
Next, we can derive an upper bound on the inner summation over t t= 1,..., T from equation 16
T
(a)
local
(wts)
S
VRo
min m (Xt.)), 1}
Ioocall
VRON
T
min
(o .1
(17)
Roo
T(2A log det(A 'K, + I)]
(6)
/2
T Dog det((- H, + I) 1]
V2VKO
TA [ā, log(1 1og(1++7g) TK/A)) + +1]
Step (a) is obtained in the same way as steps (b) and (c) in equation 15 (App. C.4.3 i.c., we have made use of glocal " S VRo and assumed that Ko 2 1. Again note that if Ko < 1, then the proof still goes through since aloma (X),) I min (ol (21,)) / /Ro] < min(o)eeal 1 (Fa.) 1), after which the only modification we need to make to the equation above is to remove the dependency on multiplicative term of /kg- Step (b) makes use of the Cauchy-Schwar inequality. Step (c).
23

---

Published as a conference paper at ICLR 2023
similar to step (e) of equation I5 is derived following the proof of Lemma 4.8 of Zhang al. (2021) l
(in Appendix B.7 of Zhang et a.. (2021)) )) Step (d) follows from Lemma and hence holds with
probability of at least 0g. In the last equality, we have simply plugged in the definition of dj
(Sec.2) 2
Now we can plug equation 17 into equation 16 to obtain
N
1
Σ
a2uT K
t 1,g (ste,)
local
N
i=1 pEgmo (E)())
S 2VTK N
/2 2//oo Koy TX dy log(1 1 +K/AA) (K/A)) +1
(18)
= =2V2VTK K5
TA Jg log(1 + TK/A))+
C.4.5 PUTTING THINGS TOGETHER
Finally, recall that our derived upper bound on rt,; in equation 13 contains three terms (the third term simply error term), and now make of derived upper bound the first term (App. C.4.3) and the second term (A4.. summed over all agents and all good epochs, to obtain upper bound the total regrets incurred in all good epochs:
Repood
Tt.i (ETio
< 2/VVTKN /ID
TNX dlog(1 + TNK/A) + +1]+
(19)
202TKK KSD
T\ J log(1 (loog(++TKKT TTK/A)) + +1] + T Sincar (m, 2")
= =ō( Vāv TNd + Vinaee N V Támax + TNN NEtincur 7))
(iVTN + amave NvT + TN (m, 7))
In the second last equality, have used PTKN Ō(Vá) and VTK (f)x)
24

---

Published as a conference paper at ICLR 2023
C.5 REGRET UPPER BOUND FOR BAD EPOCHS
In this section, we derive an upper bound on the total regrets from all bad epochs. To begin with, we firstly derive an upper bound on the total regrets of any bad epoch denoted as Rlel;
Ep-Ep-1
plol
2 +
Σ
rt,b
Ep
2
4
Σ
(UCB), - -((o))))
1
B
1=
IA
N
E -
2VTKN W v.
11
4x+ Epp-
4 + 2NTKN K0
min [ 00) m v 13)
Ep
IAS
4 4 21TKNN FON
min 00)/ !.! .1)
(20)
Step (a) follows from simply upper-bounding the regrets of the first and last iteration within this
epoch by 2. Step (6) makes use of the validity of UCB;, (Lemma B). Step (c) follows because a except for the first iteration of all epochs), which implies that after the first iteration of an epoch, 2t,; is selected by only maximizing UCB,, (line 7 of Algo. [ 3 as well as the expression of UCB,, Step (e) is obtained in the same way as steps (b) and (c) in equation 15 (App. C.4.3). Specifically, since (g(æ;; 0o), g(; 0o)) S Ko (App. C.4.3). therefore, v Vxl|g(Zz,,;; 60) m V /Ro. which can be proved by following the
0, Vi [T') \ ppppp (i.e., set
Step (d) again uses Lemma]
same steps as equation 14 As a result, if we assume that 2 1, then V 0o)/ h10l///l////// ||
min 0 case where Kg < 1, then ( 0o)/ vm /mll = min ( 0o)/ m V Ro] <
vno} S min v g( 0n)/ vml v 1); in the other
V. min VX | 06) V ||] 1}. Here have assumed Ko 2 for simplicity, since when
Ki < 1, the equation above still holds except that remove the dependency / Step (f) follows because > = 1 + 2/T > 1.
Next, we derive an upper bound on the inner summation in equation 20
Ep-2 -2
min min[ v.
(a)
1x Ep
EEp - 1)
min Bo)/ Vm 1}
t=tp
(21)
13B
detV Ex
1
(Ep - 1)2
detV Ap
detV,,+E,-2 detVest
[1((p + Epp - 2) tmm) log
V2D.
25

---

Published as a conference paper at ICLR 2023
Step (a) follows from the Sanchy-SchwarZZ inequality. Step (b) makes of Lemma 11 of Abbasi Yadkori et al. (2111). In step (c), used the notations of tlast by 1, V (,.. Vist (this is because the first iteration ip of an epoch, Wnew.s 0po and hence V E,2 + g(Z (z)g (0) /m, and also To understand step (d), note that the term in step (c):
Vast = Wsyne + Al), and Vpp+E--2.
used detV B, I d,
delV, pp is exactly the criterion we use to check whether to start ((tp + Ep -- 2) fust) log deiVine communication round in iteration = Ep -2 (line 11 of Algo. [T. Since t = + 2 is not the last iteration in this epoch (i.e., we did start communication round after checking this criterion in iteration = ip + Ep 2). therefore, this criterion is not satisfied in iteration t = ip Ep 2, i.e.
((tp + Ep 2) - ) log
de +2 S
D, which explains step (d).
detVial
Next, we can plug equation 21 into equation 20 to obtain:
4 V =(1 (4+ 20TEN 2xaAD) N, (22)
Thy
which gives an upper bound on the total regret from any bad epoch. Now recall that as we have discussed in App. C.2 there are no more than R bad epochs (with probability of least - 81).
Therefore, the total regret of all bad epochs can be upper-bounded by:
phad 1 R [++ 2VTKN 220DD)
(ālog(1 + TKN/A) + +1) (4 20TKN 2 2ROAD) N
(23)
=((TNNDN
= =Ō((G)RVDD))
In the second last equality, have used WTKN Ō(Vā). By choosing D 0 I (line 1 of Algo. D. we can further express the above upper bound on the total regrets from all bad epochs as:
Na
Rd 0
N (ā83/2
T
Nd
(24)
= (dvIN).
C.6 FINAL REGRET UPPER BOUND
Here derive an upper bound the total cumulative regret by adding up the regrets resulting from all good epochs (App. C.44 and all bad epochs (App. C.5):
RT Rgoo Rhnd
Einen (OTTTN Jaas N NVT TN innea (m, T) TvTN
(25)
=ō(īTTN -mmxx NTT + TN Tinear (m, T))
This regret upper bound holds with probability of at least 81 62 - 83 - 54 85 gg. We let
5y 84 5/3, which leads to the expressions of MIKN and PYk given in the main paper (Sec. 3)
We let 51 = 82 = 53 = ōg = 6/12, and this will only introduce an additional factor of log 12 in the first three conditions on m in App. C.1 which can be absorbed by the constant C.
Next, the last term from the upper bound in equation 25 can be further written as:
Etnner (m, T) = TN Elincar, (m, T) + Elinaar, 2 (m, T)) + Eq.
TTC,T2/3 1/6 2/3 2/3 2 Vlog m TNC 1/6 4/5333 55/ VT/A)
+ +TNC X
(26)
26

---

Published as a conference paper at ICLR 2023
It can be easily verified that long as m(log () 2 N' and m m) 3 C No - then the first and second terms in equation 26 can both be upper-bounded by 1/3. Moreover, if the conditions on 7) and J presented App. C.I are satisfied, i.c., if we choose the learning rate as 17 = (m + mT in which C₁ > 0 is an absolute constant such that C2 S 1 + T', and
/T/A) (which are ensured by conditions and 6 on m in App. C.1
choose J c. [1 log 3C2N V T (TLL/AA))) then the third term in equation 26
can also be upper-bounded by 1/3.
As result, the last term from the upper bound in equation 25 can be upper-bounded by and hence the regret upper bound becomes:
RT = Ö(TTN + Tmaxz NVT).
(27)
Worst-Case Regret Upper Bound in Terms of the Maximum Information Gain y. Next, we
perform some further analysis of the final regret upper bound derived above, which allows us to inspect
the order of growth of our regret upper bound in the worst-case scenario (i.e., without assuming that the effective dimensions are upper-bounded by constants). We have defined See. that
S / log(1 + TKN/A), A), de S 2YTK/ /ogg11 + A)) Vi E [N] and dmax = m [N] As result, in our derivations equation 19 and equation 23 we can replace dolog(1 + T A/A) by 2 and replace d, log(1 + TK/A) by 2 after which the regret upper bound becomes
RT (TT +TKKNVT)
(28)
The growth rate of the maximum information gain of NTK has been characterized by previous works: 'T -("= Kasssaie Krause 2022 Vakili al. 2021 This implies that our regret upper bound can be further expressed as
R7 = =KKK
3d (TN)
+
K
"
2d N) T
=ō -- T
C.7 REGRET UPPER BOUND FOR FN-UCB (LESS COMM.)
Here we explain how the proof above can be modified to derive regret upper bound FN FN-UCB (Less Comm.). To begin with, note that terms of the regret analysis, the only difference between FN-UCB (Less Comm and FN-UCB is that UCB), of every agent is now modified to be: UC)),(() = f(x O (yyn + PrK A g( 0o) mm/l Vomiee in which the matrix Syne,N is
obtained by: synn,NN = 1 EN (V/ocll) Note that every time the matrix Vonl.NN is calculated, we have that f tp
Firstly, we prove that the modified UCB,, is also a valid probabbiyyy upper bound on the reward function f. To achieve this, all need do is to add few steps equation 11 in Step 3 of the
27

---

Published as a conference paper at ICLR 2023
proof of. Specifically, can further analyze equation 11 by:
(2 - h(xx)l
N
1
VrR V (o; (yqoaaal) + Elinear (m, T)
N
V >g((;; 0o) (VV g(;; (ar; /m + Elineur (m, 7)
VTK
N
S VTK
(Vo 00)/m Etinear (m, T)
(29)
N
VTK
>g(x;00)
-
g(x; 0o)/ mm + Elincar (m, T)
N
F=1
Ag(=;00)T
(Venne, g(:; 00)/ m + Elinear (m, T")
PTKK
PTKVV|llo(es 0o)/ h///m// v-1 Elincur (m, T)).
The first inequality directly follows from equation 11 and the second inequality results from the concavity of the square root function. In the second last equality, we have plugged in the definition of V 'sync.NN N E (Vlocal)= As result, Lemma 4 which guarantees the validity of UCB, can be modified to be:
[M(x) - f2x; ONynNNN) S UTK UTT ( 00)/
+ Elinear (m, (), Vo E X,
(30)
v- syneNN
Secondly, we will need the following auxiliary inequality for agent i and iteration t in a good epoch p E ggood
Villg(ar, 00)/ vmll
>g( ( Vewne.NN 0o)/m
grewe
)o( 00)
(( (Vilcal) g( 00)
- 0n) (31)
N
V (o) 00)m
VN
N
The first inequality is because V
Va + Vb.
Thirdly, we need to modify the proof the regret upper bound for good epochs (App. C.4)
Specifically, can derive upper bound on the instantaneous regret rt. h(xī,)) -((x..)) for
28

---

Published as a conference paper at ICLR 2023
agent i and iteration t in good epoch p E goood (in similar way to equation 13
Ft,s h(z;,)) h((,s)
- a 2UTK v Allgg 0o)/ /mll
Slieur (m, (T,,T))
(1 a) 22TKN A
a (m, T)
S Sa 2VTK o 0o)/ //ml///ll (ygaon + Elinear (m, (),
(1 - a) (2-O)(2TT (( 80)/ v / ) + Minieuurr T)
(32)
c2vTK
g 00)/ mml (yger) 1 +
(1 VeX 00)/ /mm i. + 20 (m, T)
2 (1 - a.).TTKN + a2VTK
Local 1-1 (I),;) + 2 (m, T).
In the first inequality, we have made of equation 30 which ensures the validity of the modified UCB,, as a high probability upper bound on h. The second inequality follows from equation 31 In the last equality, we have defined glocaal (
the same way as equation 13 The steps regarding
the term involving (1 a are the same as those from equation 13 As a result, the only change we have made to instantaneous regret upper bound from equation 13 that in the second term, we have replaced N by VN Further propagating this change through the proof for the regret upper bound for all good epochs (App. C.4.4 and C.4.5). we have that:
Raoood Σ
Σ TEoo
Tr Tr, = δ (dvTN= + dmax 3/2 VT + TN Elinear (m, TT),
(33)
Lastly, also note that the regret upper bound for the bad epochs (i.e., the proof in App. unchanged. Therefore, the final regret upper bound for FN-UCB (Less Comm.) is
C.5
remains
RT R Rbnd
Ō N NT/
TNE linear (m, T) + d. TvTN
(34)
=Ō(TVTN dmaxx N3/2 + +NNe (m, T))
=Ō(āVTN + N
3/2
D PROOF OF UPPER BOUND ON COMMUNICATION COMPLEXITY (THEOREM 2
In this section, we derive an upper bound on the communication complexity (i.c., the total number of communication rounds) of our FN-UCB algorithm (including its variant FN-UCB (Less Comm. )). Define Ç / DD/R.. R. An immediate implication is that there can be at most [T/5] epochs whose length is larger than Ç. Next, we try to derive an upper bound on the number of epochs whose length is smaller than Ç.
Note that if an epoch p contains less than Ç iterations, then because of our criterion to start communi- detV,
cation round (line 10 of Algo. 11, we have that log deiV <
D. Also recall that equation equation
(Appendix
C tells us that:
Σ log detVp+1 detV,
< Rl R,
(35)
29

---

Published as a conference paper at ICLR 2023
with probability of at least 1 61 2 Therefore, there can be at most epochs whose length is smaller than ç. As result, the total number of epochs can be upper- by:
D such
Rc
D
upper-bounded bounded
RC D 1
TR D
[T/|
(36)
Recall that R = O(d) (App- Therefore, with probability of at least 1 - 61 2 - 5, the total number of epochs be upper-bounded by O(y Tz)
Since have chosen D Ö Na) (line of Algo. D. therefore, the total number of epochs can be upper-bounded by Ö( Td (dv/N) Now we can further make use the relationship between
d and NTKN: d /TTKN/ / log(1 T/), which allows us to show that the worst-case commu- nication complexity is upper-bounded by: ((d/N) Ö (TTKNVN) Ô = =
Ö N 2 which is still sub-linear in T even in the worst case.
The proof here, and hence Theorem 2 makes use of Lemma Therefore, we only need condition 1 on m listed in App. C.1 to hold, and do not require any condition on 1) and J.
E MORE EXPERIMENTAL DETAILS
Our
code
can be found
at:
http::///tthb..com wttp:///cccc/aaiaiaaaae
Federated-Neural
Some of the experimental details (e.g., the number of layers and the width m of the NN used in every experiment) are already described the main text (Sec. 5). Following the works of Zhang et al. (202T); Zhou et al. (2020), when training the NN (line 14 of Algo. D for agent i, we use the NN parameters resulting from the last gradient descent training of agent (instead of 0o) as the initial parameters, in order to accelerate the training procedure. Every time we train an NN, stochastic gradient descent to train the NN for 30 itcrations with learning rate of 0.01. To save computational cost, stop training the NNs after 2000 iterations, i.e., after 2000 iterations, all NN parameters are no longer updated. Also to reduce the computational cost, when checking the criterion in line 11 of Algo. [ we diagonalize (i.e., only keep the diagonal elements of) the two matrices for which we need to calculate the determinant. Our experiments are run on a server with 96 CPUs, an NVIDIA A100 GPU with a memory of 40GB, RAM of 256GB, running the Ubuntu system.
The shuttle dataset is publicly available at datasets SSSttttooogs (Shuttle) and contains no personally identifiable information of- fensive content. It includes 58000 instances, has an input dimension of d = 9 and contains K = 7 classes/arms. As result, according to the way in which the contexts are constructed (Sec. [5.2). every context feature vector has a dimension of 9 x 7 = 63. The magic telescope dataset is publicly available at /htpps: /ww.h/ieeeveeeeeeeeeeeeeeaaaaeee ics uci edu/ /dtaaatttt/saaaaaeeeeeeeas aatagictttaaaaa tel telescope and contains personally identifiable information or offensive content. The dataset contains 19020 instances, has an input dimension of = 10 and K = 2 classes/arms. As a result, every context feature vector has dimension of 10 x 2 = 20.
www.iccs.ccc edu/mJ ml/
When comparing with Linear- UCB, Linear TS, Kernelized UCB and Kernelized TS, we follow the work of Zhang et al. (2221) to set À and perform grid search within E {1, 0.1, 0.01). The results showing comparisons with these algorithms, for both the synthetic experiments (Sec.5.1 and real-world experiments (Sec. 5.2), are presented in Fig. 4 The figures show that both linear and kernelized contextual bandit algorithms are outperformed by neural contextual bandit algorithms,
which is consistent with the observations from Zhang et al. (202T) Zhou et al. 2002
30

---

Published as a conference paper at ICLR 2023
MoUKs (f'm3)
MiUKs w1
Th- (K--2) 20
Tl-JC3 1M 20
Curulaaiven lalivee Regret
Ph-uca (K 50
Cumulative Regret
150
FN-UCS 1k m5
FA-IKR 18t
Fh-ikS Comm 29
Phafce Nosu
100
80
0
4000
5000
Iterations
(a) cos mrsiine
(b) square
Figure Cumulative regret of FN-UCB and FN-UCB (Less Comm.) for the cosine and square functions. Their performances very similar for both functions.
200
250
Cumulative Regret
Cumulative Regret
200
150
Naz
150
hard T5
100
my UCB A -
100
Pauck
50
ovmel lin
KindlTS
Ramd 15
Lneer
0
3000
lterations
Iterations
(a) COS ine
(b) square
1000
Heuaa
Cumulative Regret
Cumulative Regret
PAACS
800
FNUCS
Keanllac
600
UCB
Rense
400
Narnal
200
Uneer JCa
LiverTS
0
1000
2000
3000
4000
5000
1000
2000
3000 4000 Iterationn
5000
Iterations
(c) shuttle
(d) magic telescope
Figure 4: Cumulative regrets for the (a) cosine, (b) square, (c) shuttle (with diagonalization),
and (d) magic telescope experiments, with additional comparisons with Linear UCB, Linear TS, Kernel UCB and Kernel TS.
31

---

Published as a conference paper at ICLR 2023
FN-UCH (W 5)
FN-UGD 5. diag)
Cumulative Regret
200
150
100
50
1000
2000
3000
4000
5000
Iterations
shuttle
Figure 5: Comparison between the performances without (yellow) and with (red) diagonalization, using 20 with the shuttle dataset. The results show that using an NN with the same width m 20, diagonalization indeed deteriorates the performances.
Average Cumulative Regret
80
Average Cumulative Regret
150
60
125
100
40
75
20
10
6
8
10
N
(a) cosine
(b) square
Figure 6: The scaling of the final average cumulative regret after 5000 iterations (averaged across all N agents) in terms of the number N of agents, using the cos inn and square experiments. The results correspond to Fig. a and Fig. [.. respectively.
We have additionally evaluated the empirical impact of the technique of diagonalization of the matrices (Sec. (Sec.3.44) using the shuttle dataset and a fixed width of 20 for the NN. The results (Fig. () show that for the same width of the NN, the technique of diagonalization indeed results in worse performances. However, also note that diagonalization allows us to afford larger value of m in computationally feasible way, which can lead to better performances than using a smaller m without diagonalization. This is corroborated by our empirical results in Fig. 2p and because the regrets in Fig. 2 (m=500 with diagonalization) are in general smaller than the regrets in Fig. 2 (m=20, without diagonalization) and the computational cost Fig. 2 (244.9 seconds) is smaller than that of Fig. 2 (361.8 seconds). Furthermore, using 50 without diagonalization would incur a significantly larger computational cost (3134.3 seconds). These results demonstrate the practical usefulness of diagonalization.
We have also visualized the empirical scaling of the final average cumulative regret (after 5000 iterations) in terms of the number N of agents, using the cosine onnene and square experiments. The results (Fig. (6) demonstrate that the average cumulative regret (averaged across all N agents) is indeed decreasing the number N of agents increases.
F EXTENDED ANALYSIS FOR THE GENERAL ALGORITHM
Recall that it has been mentioned at the beginning of Sec. 4.1 that our main regret analysis (Theorem [ has focused on simpler version of our FN-UCB algorithm, in which only choose the value of a using the method described Sec. 3.3 in the first iteration of every epoch and set = 0 in the other iterations. Here, show how regret analysis can be extended to derive regret upper bound
32

---

Published as a conference paper at ICLR 2023
for the general FN-UCB algorithm, in which choose using the method described in Sec. 3.3 in every iteration, i.c., we do not set a 0 in any iteration. To achieve this, we need an additional assumption of an upper bound the amount of new information collected by every agent i in every epoch p. Specifically, we assume that
detV t., -2, detV/local fp-
D.
(37)
for constant D 2 1. This can in fact be viewed as an additional property of the sequence of contexts for each agent. Intuitively, if the contexts for each agent are received in such an order that similar contexts also arrive in similar iterations, then the constant D is likely to be small. This can be seen as a "stationarity" property of the sequence of contexts, which reasonable in many practical scenarios. For example, in healthcare application, the patients arriving within the same time period are likely to have similar characteristics due to factors such as the local transmission of a seasonal flu. addition, another scenario where D is likely to be small is when every agent has some previously observed offline contexts before running our algorithm. If these offline contexts have good coverage of the space of contexts, then conditioned these offline contexts, the newly collected information by every agent in every epoch is highly likely to be small.
With this additional assumption, the most important step in the proof that need to modify is the proof in Appendix [C..4] in which we proved an upper bound on the sum of the second term of equation 13 To begin with, Vt 1p......p Epp we have that
glocal
1, (11,))
(a) v Allg(Ze, 0o)/ / (1ehen -
1,
Ag(ar,5 0o) T(V g(a,, 0m)/m
detV/local
(o - -Ig( 00)
detl lucal
Ep
(38)
det
((0),,:))TT((22)) g( 00)/m
t 1-11-
detV/local f,
Ag( 0o) (V/loal)) -1g(zr,;; (0)m
Dateal (x),))-
Step (a) has made use of the definition of G]occl -1,-11; (2x,) (xt,,) (see the paragraph below equation 13 step (b) results from Lemma of Abbasi- Yadkori et al. (011)) ). step (c) follows because Vlocal tp E, 1-1.j
contains more information than Vina, Vt = fp.............. ....... + Ep - 1, step (d) follows from equation 37 and step (e) has again made of the definition of 1 (2r,))
33

---

Published as a conference paper at ICLR 2023
Using equation 38
modify the proof in equation 16
(Appendix C.4.4).
N
a2vTK
local 1p-1. 1. (1),a)
S
20TK
1
Σ
local
1p 1n (1),)
N
N
i=1 pe gaod (E)(M)
PE (1) (ET(M)
j=1
S 20TK N
a0 1-11,11 1, (31
j=1 pE[1]
N
N
Ep
2VTK N
local
1g 1, (ft..)
(39)
t=1 j=1
PE[P]
1
(6)
I 20TK N
1
N
Σ
b B
Σ
Do t-1 (1)
pE(P)
D2VTK
ΣΣΣ
O I,j (x+
glocal
Step (a) follows from the same reasoning as step (c) of equation step (b) has made use of equation 38 and all other steps follow the same corresponding steps of equation 16
As a result, by comparing the modified equation 39 with the original equation [6] the only modification to the result in equation 16 is the additional multiplicative term of v D. Therefore, after propagating this modification to all the analysis in Appendix C.4.4 we have that multiplicative term of vD will also be introduced into equation [8] Subsequently, the upper bound on the total regrets from all good epochs (i.e., equation 19 will be correspondingly modified to be:
R = Ō (TVTN+ + V Delaax N T + TN (m, T))-
(40)
Next, we also need to modify the proof of the upper bound on the total regrets from all bad epochs (Appendix C.5). Following the roadmap of Appendix C.5) we start by upper-bounding the total regrets from a particular bad epoch p:
N
Ep
N
l E1
RlPl
[ah(at,)) + (1 a))((1,))) - M(x++)))
+ -1
aUCBB (xT,t) + a lineur (1- (oniiii)-((00... (((eN))
1=1
E -1
aaCBB,, (z,,i) + aetinnar (1- (((sa)
t=
Ep
(a(UCB), [ (1- (U) 1(x22,)))
(41)
+ OCE (m, (m,
Epp
(0)
+
1=1
(1y++1
A
N f
((UCB)) h(x+s))) + A ( (m, T))
34

---

Published as a conference paper at ICLR 2023
Step (a) follows from Lemma 3 (i.e., the validity of UCB(,) and Lemma 4 (i.e., the validity of UCB Step (b) results from the way in which ,t, is selected (line 7 Algo. 1 Tt, = arg m (1 axU
(2) + aUCB", For step (c), the term A is obtained by upper- bounding the regrets of the first and last iteration within this epoch by 2 and using the fact that &<L 1.
Next, we can separately analyze the terms A and B in equation 41 Firstly, note that the term A is the same as step (c) of equation 20, therefore, we can follow the same steps of analyses in App. C.5 (i.e., equation 20 equation 21 equation 22] equation 23 and equation 24) to show that after summing the
term A across all bad epochs, we get an upper bound of O (dVTN Secondly, for the term B, we can in fact follow similar steps of analysis in equation 13 show that every term inside the square bracket of the term B is upper-bounded by the last two terms in equation 13 That is,
- +
+ tiEeaa (m, T) S a2VTK N
tg 1. (2) + timer (m, T). (42)
As a result, we can follow the same steps of analysis in App. C.4.4 (after making the modifica- tion using equation 39; note that the analysis in App. C.4.4 is applicable to both good and bad epochs) to show that after summing over all bad epochs, the term B can be upper-bounded by
Ō (VDimmxx T TN Stinear(m, T)) Next, combining the upper bounds both A and B (after summing across all bad epochs), we have that for the general algorithm, the total regrets from all bad epochs can be upper bounded by
Rhad Ō (dVTN Ddd N VT + TN Einear (m, 77).
(43)
which is in fact the same as the upper bound on the total regrets from all good epochs which we have derived in equation 40
show that the final regret upper bound for the general algorithm, in which we do not set a 0 in any iteration, is
Finally, following the same analysis in App. C.6
Pr - Ō + Ddīmax N NVT).
(44)
Note that compared to our regret upper bound from Theorem the regret upper bound for the general algorithm (i.e., when choose the value of a using the method from Sec. 3.3 every iteration) only
includes an additional multiplicative term of / D the second term. Of note, when communication indeed occurs after each iteration (i.e., Ep. = 1 for every epoch p), we have that D = 1 because
detl/beal Fyt R2-11
(equation 37p. In this case, the version of our algorithm analyzed in Theorem becomes the same as our general algorithm (Sec. 4.1). and interestingly, the regret upper bound of our general algorithm (equation 44h also becomes the same Theorem because D 1.
det V I,
35


Reviews:
[{"review_id": "xmIrU-nWok", "reviewer": "Reviewer_cGE9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the federated bandits with neural networks under the NTK regime. Theoretical regret analysis and experimental results are provided to show that the proposed algorithm could fully leverage the neural networks in the federated bandit setting.", "summary_of_the_review": "This paper is overall interesting and well-written. My major concern is the technical novelty of this paper as discussed above. Given this, I am on the borderline of rejection. \n\n\n***\n\nThe author's response addressed some of my questions. Thus I raise my score accordingly", "strength_and_weaknesses": "### Strength\n\n- This paper is well-written and easy to follow. The experiment is adequate and the proof is mathematically correct\n\n### Weakness\n\n- It seems that the major contribution made in this paper is combining the neural UCB and neural TS [1, 2] with federated bandits. The author might want to highlight their contributions and difficulties in this combination\n- The claim on communication cost is somehow ambiguous. The authors suggest that by using the *Less Comm.* version of the algorithm, the communication cost could reduce to $O(p)$. However, the performance impact by 1) using the averaged covariance matrix $V$ instead of $V_i$ and 2) using the diagonal elements to approximate the matrix $V$, is not well studied either from a theoretical perceptive or empirical perceptive. \n\n[1] Zhou, Dongruo, Lihong Li, and Quanquan Gu. \"Neural contextual bandits with ucb-based exploration.\" International Conference on Machine Learning. PMLR, 2020.\n[2] ZHANG, Weitong, et al. \"Neural Thompson Sampling.\" International Conference on Learning Representations. 2020.", "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": "tPCTXdBG0xi", "reviewer": "Reviewer_H38q", "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 paper develops a federated neural contextual bandit algorithm FN-UCB which extends existing neural contextual bandits to the federated setting. The key idea of FN-UCB is that it adopts a weighted combination of two UCBs, where the first UCB allows every agent to additionally use the observations from the other agents to accelerate exploration, while the second UCB uses an NN for reward prediction. In theory, the regret bound of the proposed method is proved and its superior advantages are compared in extensive experiments.  \n", "summary_of_the_review": "The considered federated neural bandit is a natural combination of neural bandit and federated learning. The idea is very natural and the technical novelty is OK but not strong. Moreover, the current theoretical results only hold for a simpler version of the proposed FN-UCB (require communication in each iteration). \n\nIn the rebuttal stage, I would like to see more justifications on the technical novelty beyond existing neural bandit and federated learning, as well as an improved analysis for the general FN-UCB algorithm.\n\n", "strength_and_weaknesses": "Strength:\n\n1. The paper is well written and is very easy to follow.\n\n2. The considered federated neural bandit problem is interesting.\n\n3. Extensive experiments demonstrate the practical usefulness of the proposed algorithm. \n\n\nWeaknesses:\n\n1. Technical novelty: My major concern is its technical contribution beyond existing literature. The proposed federated neural bandit is a natural combination of neural bandit (Zhou et al., 2020; Zhang et al., 2021; Kassraie & Krause, 2022) and federated learning (Wang et al., 2020). Because of this nature, the algorithmic development and theoretical analysis were largely based on these two areas. In particular, a large part of the proof is to verify conditions used in Zhou et al. (2020) and Zhang et al. (2021). Based on my personal opinion, the technical novelty of this paper beyond these references is not strong. \n\n\n2. Limitation in the current theory: There is a major gap in the theoretical results. The derived main theorems is not for the proposed FN-UCB, but for a simpler version where they only choose the weight $\\alpha$ using the proposed method in the first iteration after every communication round and set $\\alpha = 0$ in all other iterations. This simpler version requires communication to occur after each iteration, which clearly contradicts with the communication complexity shown in Theorem 2. Since the balance of $\\alpha$ is a key novelty of the considered problem, it would be more convincing to derive the theoretical results for the proposed FN-UCB directly. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "rwjWbpzU1I", "reviewer": "Reviewer_oNap", "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 authors propose a novel federated neural contextual bandit algorithm to tackle the richer structure of rewards that conventional linear/kernel approaches may not handle. Regret bounds for the proposed algorithms are derived and experimental results show the efficacy of the proposed algorithms on both synthetic and real-world experiments. \n", "summary_of_the_review": "Overall, an interesting extension on the neural contextual bandit setting in the federated context. Some questions remain and I hope to discuss with the authors to clarify my understanding.\n", "strength_and_weaknesses": "Pros: \n     (A) The proposed algorithm is a combination of two UCBs one of which is focused on exploration based on the neural tangent features. This has a higher weight\nduring the initial iterations. The second UCB kicks in once the neural networks are sufficiently trained and this corresponds to the exploitation phase. There is a\n nice explanation between these two phases. Combined with the regret guarantees over the iterations and communication rounds, they provide a good understanding and\n solution of the neural contextual bandit problem. \n     (B) Extensive set of experiments where they switch off one of the UCBs gives us a good understanding of the individual components (ablation study). Also, the\nperformance based on setting of D as well the number of agents is explored. \n\nCons:\n\n   (i) It was not fully clear on how alpha was set in the experiments? Section 3.3 describes the intuition as well as the mathematical formula for it but the experiments talk about a linear function. Any insight into this would be helpful. Also, the regret is analyzed for the setting where alpha=0 after first iteration. However, the experiments use non-zero alpha. \n   (ii) Are there experiments which show the scaling with N or dtilde? It would be interesting to know how tight these bounds bound are and could serve as a proxy for lower-bounds for the setting. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "lqPDjlAbwD", "reviewer": "Reviewer_f21Q", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This research examines contextual bandits in a federated learning environment. This is the first study applying federated learning to neural contextual bandits. The author(s) proposed the FN-UCB algorithm, which is shown to suffer from sub-linear regret and communication rounds. Both synthetic and real-world experiments confirm that the newly proposed algorithm performs competitively against the baselines.", "summary_of_the_review": "This author(s) are the first using neural netorks (NNs) in the setting of federated contextual bandits. Although the proposed algorithm may not be optimal, due to the NNs' powerful representational capabilities, broader real-world applications may be possible. Hence I suggest accept.", "strength_and_weaknesses": "Strength\n* This author(s) are the first to use neural netorks (NNs) in the setting of federated contextual bandits. Given that NNs have high representational capabilities, this opens up the possibility of more extensive real-world applications.\n* The proposed algorithm, FN-UCB, has superior empirical performance that has been confirmed through extensive experiments in addition to theoretical assurance.\n\nWeaknesses\n* Although the author(s) have provided empirical experiments to demonstrate the proposed algorithms with multiple agents outperforms the baselines with single agent in practice, how efficient the suggested algorithm is is still unknown. It might be better if the author(s) could provide the lower bound.", "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": "I0JNjW2XCyX", "reviewer": "Reviewer_D1SJ", "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 analysing a new setting in which a set of multiple Neural Bandits are collaborating to minimize the regret for an online sequential decision problem. The authors provided an algorithm combining the feature of federated learning and neural bandits, with sublinear regret and communication cost. Finally, the authors demonstrate the capabilities of the developed methods with an experimental campaign.", "summary_of_the_review": "The paper is sound and interesting, but some concerns about the experimental part should be addressed by the authors.", "strength_and_weaknesses": "Overall the paper is clear and well-structured. The algorithm is easy to understand and properly analysed.\n\nMy only concerns are the experimental results provided by the authors, which somehow are not feeding each one of the analysed algorithms with the same number of samples at each round.\n\nDetails:\nI would like you to discuss the results you obtained w.r.t. the federated bandit setting and the neural bandit ones. I think this would highlight how the elements of the regret and communication complexity change by the fact that you are using the combination of these two settings.\n\nFor instance, I would like to have the expression of the bound on the regret when you are considering only local information and comparing them with the ones you have in Theorem 2.\n\nWith N=1 agents does the regret of Theorem 2 become the one of Neural Bandits? Overall, you should discuss more on the difference between Neural Bandits and your algorithm with N=1.\n\nIn the first experiment (5.1) I think that the comparison is not fair. In this case, you are receiving two samples, while standard algorithms are receiving only one realization of the reward. However, similar comments are also holding for the second experiment.\n\n\n\n\nMinor:\nPlease move the legend outside the figures, otherwise, they are hard to read.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster