Federated Linear Contextual Bandits
Authors: Ruiquan Huang
Weiqiang Wu
Jing Yang
Cong Shen
Venue: NeurIPS 2021 Poster (2021)
Keywords: Federated Bandits
Linear Contextual Bandits
G-optimal Design

Abstract: This paper presents a novel federated linear contextual bandits model, where individual clients face different $K$-armed stochastic bandits coupled through common global parameters. By leveraging the geometric structure of the linear rewards, a collaborative algorithm called Fed-PE is proposed to cope with the heterogeneity across clients without exchanging local feature vectors or raw data. Fed-PE relies on a novel multi-client G-optimal design, and achieves near-optimal regrets for both disjoint and shared parameter cases with logarithmic communication costs. In addition, a new concept called collinearly-dependent policies is introduced, based on which a tight minimax regret lower bound for the disjoint parameter case is derived. Experiments demonstrate the effectiveness of the proposed algorithms on both synthetic and real-world datasets. 

Federated Linear Contextual Bandits
Ruiquan Huang
Weiqiang Wu Facebook weiqiang. wwu@gmail. com
The Pennsylvania State University rzh55140psu. edu
Jing Yang
Cong Shen
The Pennsylvania State University yangj ing@gung edu
University of Virginia cong@virginia edu
Abstract
This paper presents novel federated linear contextual bandits model, where indi- vidual clients face different K K-armed stochastic bandits coupled through common global parameters. By leveraging the geometric structure of the linear rewards, a collaborative algorithm called Fed-PE proposed to cope with the heterogeneity across clients without exchanging local feature vectors or raw data. Fed-Pi PE relies on a novel multi-client G-optimal design, and achieves near-optimal regrets for both disjoint and shared parameter cases with logarithmic communication costs. In addition, a new concept called polliearry-dependderr which a tight minimax regret lower bound for the disjoint parameter case is derived. Experiments demonstrate the effectiveness of the proposed algorithms on both synthetic and real-world datasets.
policies introduced, based
Introduction
Federated learning (FL. (McMahan et al. 2017) is an emerging distributed machine learning (ML) paradigm where massive number clients collaboratively learn shared prediction model while keeping all the training data on local devices. Compared with standard centralized machine learning, FL has the following characteristics (Kairouz et al. 202I):
Heterogeneous local datasets. The local datasets, which are often generated at edge devices, are likely drawn from non-independent and identically distributed (non-lID) distributions.
Communication efliciency. The communication cost scales with the number of clients, which is one of the primary bottlenecks of FL.. is critical to minimize the communication cost while maintaining the learning accuracy.
Privacy. FL protects local data privacy by only sharing model updates instead of the raw data.
While the main focus of the state-of-the- art FL is the supervised learning setting, recently, few researchers begin to extend FL to the multi-armed bandits (MAB) framework (Lai and Robbins 1985 Auer al. 2002 Bubeck and Cesa-Bianche 2012 Agrawal and Goyal 2012 (213a)). In the canonical setting of MAB, a player chooses to play one arm from a set of arms at each time slot. An arm, if played, will offer reward that drawn from its distribution which is unknown to the player. With all previous observations, the player needs to decide which arm to pull each time in order maximize the cumulative reward. MAB thus represents an online learning model that naturally captures the intrinsic sxplorationeexplotaaii tradeoff in many sequential decision-making problems.
Extending FL to the MAB framework is naturally motivated by corpus of applications, such as recommender systems, clinical trials, and cognitive radio. those applications, the sequential decision making involves multiple clients and is distributed by nature. While classical MAB models assume immediate access to the sequentially generated data at the learning agent, under the new
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

realm of FL, local datasets can be stored and analyzed at the clients, thus reducing the communication load and potentially protecting the data privacy.
Despite the potential benefits of FI., the sequential decision making and bandit feedback bring new challenges to the design of FL. algorithms in the MAB setting. Different from the supervised learning setting where static datasets are collected beforehand, under the MAB setting, data is generated sequentially decisions are made, actions are taken, and observations are collected. In order to maximize the cumulative reward and minimize the corresponding learning regret, it thus requires sophisticated coordination of the actions of the clients. The heterogeneous reward distributions across clients make the coordination process even more convoluted and challenging. Besides, the data privacy and communication efficiency requirements result in significant challenges for efficient information exchange and aggregation between local clients and the central server.
In this work, attempt address those challenges in federated linear contextual bandits framework. This particular problem is motivated by the following exemplary applications.
Personalized content recommendation. For content (arm) recommendation in web-services, user engagement (reward) depends on the profile of user (context). The central server may deploy a recommender system on each user' local device (client) in order to personalize recommendations without knowing the personal profile or behavior of the user.
Personalized online education. In order to maximize students performances (reward) in online learning, the education platform (central server) needs to personalize teaching methods (arms) based on the characteristics of individual students (context). With the online learning software installed at local devices (client), it is desirable to personalize the learning experiences without allowing the platform to access students' characteristics or scores.
In those examples, the reward of pulling the same arm at different clients follows different distributions dependent on the context as in contextual bandits (Auer 2003 Langford and Zhang, 2008). We note that conventional contextual bandits is defined with respect to a single player, where the time-varying context can be interpreted as different incoming user profiles. In contrast, we consider a multi-client model, where each client is associated with a fixed user profile. The variation of contexts is captured over clients as opposed to over time. Although the set of clients remains fixed through the lcarning process, the reward of pulling the same arm still varies across clients. Such a model naturally takes data heterogeneity into consideration. Besides, we adopt a linear reward model, which has been widely studied in contextual bandits (Li al. 2010 Aggawal and Goyal 2013b).
Main contributions. Our main contributions are summarized as follows.
First, we propose a new federated linear contextual bandits model that takes the diverse user pref- erences and data heterogeneity into consideration. Such a model naturally bridges local stochastic bandits with linear contextual bandits, and is well poised to capture the tradeoffs between communi- cation efficiency and learning performances in the federated bandits setting.
Second, we design a novel algorithm named Fed-PE and further develop its variants to solve the federated linear contextual bandits problem. Under Fed-PE, clients only upload their local estimates of the global parameters without sharing their local feature vectors or raw observations. It not only keeps the personal information private, but also reduces the upload cost. We explicitly show that Fed-PE and its variants achieve near-optimal regret performances for both disjoint and shared parameter cases with logarithmic communication costs.
Third, we generalize the G-optimal design from the single-play player setting (Lattimore and Szepesvári 2020) the multi-client setting. We develop a block coordinate ascent algorithm to solve the generalized G-optimal design efficiently with convergence guarantees. Such a multi-client G-optimal design plays a vital role in Fed-PE, and may find broad applications in related multi-agent setups.
Finally, we introduce a novel concept called brated LinUCB type of policies (Li et al. 2010)) Thompson sampling based policies with Gaussian priors (Agrawal and Goyal| 2013b), and least squared estimation based policies, such as Fed-PE, are all in this category. By utilizing the property of aelinearly-depeneerd policies, we are able to characterize a tight minimax regret lower bound in the disjoint parameter setting. We believe that this concept may be of independent interest for the study of bandits with linear rewards.
policy and show that the cele-

---

Table 1: Performance comparison
Model
Algorithm
Regret
Communication cost
Linear
DELB
O(dy Mld(TT)oggT)))
O( + dlog d) log
FedUCE
O(vaMT log
O log T) O(Mid + dK) log
Linear contextual (shared parameter)
Fed-PE (this work)
Ol dMT log (
Lower bound
10 ((VTMT)
N/A
Centralized
O MKMTloo log' (KMT))
((M&KT)
Linear contextual (disjoint parameter)
Fed-PE (this work)
O wakkM log (MT)) Q(VaKM))
( log
Lower bound (this work)
N/A
number of clients; K: number arms; T: time borizon; ambient dimension of the feature vectors.
Notations, Throughout this paper, we use ||>|| to denote Vz The range of a matrix A, denoted
by range(A) A), is the subspace spanned by the column vectors of A. We use At and (et(A) )) to denote the pseudo-inverse and pscudo-determinant of square matrix A, respectively. The specific definitions can be found in Appendix B of the supplementary material.
2 Related Works
Collaborative and distributed bandits. Our model is closely related the collaborative and distributed bandits when action collision is not considered. [Landgeen et al. (2016) 2018) and Martinez-Rubio et al. (2019) study distributed bandits in which multiple agents face the same MAB instance, and the agents collaboratively share their estimates over fixed communication graph in order design consensus- based distributed estimation algorithms to estimate the mean of rewards at each arm. Szorenyi et al. (2013) considers a similar setup where in each round an agent is able to communicate with a few random peers. Korda et al. (0116) considers the case where clients in different unknown clusters face independent bandit problems, and every agent can communicate with only one other agent per round. The communication and coordination among the clients in those works are fundamentally different from our work.
Wang al. (2020) investigates communication-effice
distributed linear bandits, where the agents can communicate with a server by sending and receiving packets. It proposes two algorithms, namely, DELB and DisLinUCB, for fixed and time-varying action sets, respectively. The fixed action set setting is similar to our setup, except that it assumes that all agents face the same bandits model, which does not take data heterogeneity into consideration.
Federated bandits. A few recent works have touched upon the concept of federated bandits. With heterogeneous reward distributions at local clients, [Shi and Shen (202T) and [Shi et al., (2021) investigate efficient client-server communication and coordination protocols for federated MAB without and with personalization, respectively. [Agawwal et al.) (2020) studies regression based contextual bandits as an example of the federated residual learning framework, where the reward of client depends on both global model and local model. Li et (2020) and Zhu al. (2021) focus on differential privacy based local data privacy protection in federated bandits. While the linear contextual bandit model considered in Dubey and Pentland (2020) similar this work, it focuses on federated differential privacy and proposes a LinUCB based FedUCB algorithm, which incurs a higher regret compared with our result for the shared parameter case. A regret and communication cost comparison between Fed-PE and other baseline algorithms is provided in Table
3 Problem Formulation
Clients and local bandits model. We consider a federated linear contextual bandits setting where there are M clients pulling the same set of K items (arms) denoted as [K] := {1, ......K. K}. At each time f, each client E [M] pulls an arm ai,, E [K] based on locally available information. The incurred reward Vi.t is given by yi. Ti,as, + T).,, where Th,t is random noise, and ri,a,, is
Results adapted from Dubey Pentland 2020 by letting the privacy budget 1/c go go t. 'Results adapted from the single-player linear contextual bandits studied in Dimakopoulou et al. 2017) by assuming instantancous information exchange and sequential decision making at the central server.
3

---

the unknown expected reward by pulling arm d,,t. We note that without additional assumptions or interaction among the clients, each local model is standard single-player stochastic MAB, where classic algorithms such as UCB (Auer and Ortner] 2010) and Thompson sampling (Agrawal and Goyal 2012) are known to achieve order-optimal regret.
Linear reward structure with global parameters. In order to capture the inherent correlation between rewards of pulling the same arm by different clients, we assume Ti, has a linear structure, L... ri,a xiaa Oa, where Zi,a E Rd is the feature vector associated with client and arm a, and 0a E IR is a fixed but unknown parameter vector for each a E [K]. Here we use x to denote the transpose of vector 2. The same arm a may have different reward distributions for different clients, due to potentially varying Zi,a across clients. Such a linear model naturally captures the heterogeneous data distributions at the clients, yet admits possible collaborations among clients due to the common parameters {0a [a(K]]- When O₂ varies for different arm a, it is called the disjoint parameter case; when 0g is known to be a constant across the arms, it is the shared parameter case. We investigate both cases in Sections 4 and ||| respectively.
Communication model. We assume there exists a central server in the system, and similar to FL, the clients can communicate with the server periodically with zero latency. Specifically, the clients can send "local model updates" to the central server, which then aggregates and broadcasts the updated "global model" to the clients. (We will specify these components later.) Note that just as in FL, communication is one of the major bottlenecks and the algorithm has to be conscious about its usage. Similar to Wang et al.] (2020), we define the communication cost of an algorithm as the number of scalars (integers real numbers) communicated between server and clients. We also make the assumption that clients and server are fully synchronized (McMahan et al. (017).
Data privacy concerns. Similar to Dubey and Pentland 2022)), our contextual bandit problem involves two sets of information that are desirable to be kept private to client i; the feature vectors (Ziaa and the observed rewards { he Different from the differential privacy mechanism adopted in Dubey and Pentland (2020). in this work, we aim to communicate estimated global model parameters 1 la between the clients and the server. This is consistent with the FL framework, where only model updates are communicated instead of the raw data.
Assumption We make the following assumptions throughout the paper:
1) Bounded parameters: For any i E [M], a E [K]. we have [|0al12 S s, 0 1.005- & S L. 2) Independent I-subgaussian noise: Th, is a I-subgaussian noise parameter sampled indepen- dently at each time for each client with E nr.] = 0, EE(exp(>xx::)] S exp( for any X >> 0.
Assumption 1.1 is standard assumption in the bandit literature, which ensures that the maximum regret at any step is bounded. We emphasize that our work does not make any assumption on the knowledge of suboptimality gaps, nor do we assume the existence of a unique optimal arm at each client.
Our objective is to minimize the expected cumulative regret among all clients, defined as:
M T
2To0;00; 0o; - -xTa oo..) xlo.,0o..))
E [[ = E
(1)
(=1
where of E [K] is an optimal arm for client i: Vb a 0j 2. ala;00; 0nz x1, 2 0.
4
Federated Linear Contextual Bandits: Disjoint Parameter Case
4.1
Challenges
Solving the federated linear contextual bandits model faces several new challenges. The first challenge is due to the constraint that only locally estimated parameters (0. Jae[K] are uploaded to the central server. While this is not an issue for stochastic MAB where the {0, {Oa)aE[K] are scalars (Shi and Shen 2021 Shi et al.] (021), this brings significant challenges for the aggregation of the local estimates into a "global m in our setup. This is because under the linear reward structure, the locally received rewards (vr, herry only contain the projection of 0, along the direction of zi while the

---

portion of information lying outside range( is not captured in {Vr, herr) Thus, by utilizing (e())) the locally estimated Pu denoted as aa cannot provide any information of 6a beyond rango((ti,.). Since ( [e[M] are different for the same arm a, the locally estimated (6 [E[M] are essentially lying in different subspaces. The central server thus needs to take such geometric structure into account when aggregating { to construct the global estimate of a.
The geometric structure of the local rewards also brings another challenge for the coordination of actions local clients. Intuitively, in order help client accurately estimate the expected reward by pulling arm it suffices to obtain an accurate projection of 0a on range(Fi,a)) any part of 0a lying outside this subspace irrelevant. Therefore, if two clients i and j have Tú and 2j, orthogonal to each other, exchanging the local estimates 0,. and _ does not help the other client improve her own local estimation. On the other hand, if ii and Fj are completely aligned with each other, 6r,, and j.n can be aggregated directly improve the local estimation accuracy both. With M possible subspaces spanned by {#i,a s. it is highly likely that different clients receive different amounts of relevant information (i.e., information lying in range(x;;a) through information exchange facilitated by the central server. Therefore, in order to reduce the overall regret, it is necessary to coordinate the actions of clients in a sophisticated fashion.
Third, since the exact knowledge of the local feature vectors {=r,a) } are kept from the central server, the server may not have an accurate estimation of the uncertainty level of the local estimates each client, or how much the coordination would help individual clients. This would make efficient and effective coordination even more challenging.
4.2 Federated Phased Elimination (Fed-PE) (Ed--P)) Algorithm
To address the aforementioned challenges, we propose the Federated Phased Elimination (Fed-PE) algorithm. The Fed-PE algorithm works in phases, where the length phase p is f + K. It contains client side subroutine (Algorithm[] [T) and server side subroutine (Algorithm 2 Throughout the paper we use superscript to indicate phase barring explicit explanation. We use A C [K] to denote the subset of active arms at client i phase p. AA" := I R == {i a E AP). and define TPP as the time indices which client pulls arm during the collaborative exploration step in phase p. Then, the algorithm works as follows.
Algorithm Fed-PE. client i
Input: T, M,, K, a, f² f
I: Initialization: Pull each arm E [K] and receive reward ye,o; 0% Mi.eRi.a a. Send (0%, Jo to the server;
A -[]] <- 1.
2: while not reaching the time horizon do
Receive [(0g, V.') ( from the server.
b Arm elimination
4: for Ap-1 do
1,a f 0
uhaa |siallyz /R.
5: end for
6:
ap + arg max GEAR- fla
Ad faE AP-1
Ap p + uh
up Lap
7:
Send A² to the central server.
b Active arm set updating
8: Receive fT, for all E A?
9:
for a E A" do
b Collaborative exploration
10:
Pull arm for fla times and receive rewards (y.therT
8%
fh.
Vi.t
Fi,0 |
12
(3)
TE
11:
end for
12:
Send [0 loEA to the server; Pull à until phase length equals f + K.
13: p < p
14: end while
5

---

At the initialization phase, each client pulls every amm E [K] once and receives reward Vi,a. based on which it obtains an estimate of the projection of 0a. These estimates are sent to the server to construct preliminary global estimate of 0, for each a. The global estimates {01), and the potential matrices {Va ja are then broadcast to all clients, after which phase receiving {0) Ji,a. the central server will keep unit vector 6i,a S. /.../110,, @.,. for all E [M], [K]. Since 0% is scaled version of Ti,as 6i,a lies in range(zita). and will be utilized to coordinate the arm pulling process (coined as collaborative exploration), as elaborated in Section
1 begins. Note that after
At the beginning of phase p, after receiving the broadcast {dg) and {V2)e from the server, each client i will utilize the (0%, V?²) pair to estimate the expected rewards ri,o and obtain the confidence level according to Eqn. 2 for each a E AA Based on the constructed confidence interval, client i then eliminates some arms in A, and obtains Af.
Next, each client sends the newly constructed active arm set A", to the server. The server then decides fi..- the number of times client pulling arm a during the collaborative exploration step in phase p for each i E [M] and a E A.. The specific mechanism to decide R. is elaborated in Section
After the collaborative exploration step, client i performs least-square estimation (LSE) for each arm E A₁ based on local observations collected in the current phase according to Eqn. 3 and then sends to the server for global aggregation. Note that although 6% lies in range( the exact value of Fi is not revealed to the server, thus preserving the privacy to certain extent.
Algorithm 2 Fed-PE: Central server
Input: T, M,, K, a, f
8 I: Initialization: Receive ] 6,,a 1
(I (Eiejan
#e ( )T 1162
for all [M] a E [K]: V2
0 + V.l (Exejay (9,0) for all a E [K]: Broadcast (0), Vol ha
2: while not reaching the time horizon T do
3: Receive (AAe) hetar: Set A"
A": Set (i:a E?). 4: Solve the multi-clien G-optimal design (6) and obtain solution (TT
For every client send (ff.. == [=e.a ("1 Daeap.
6: Receive [(a, Daeap from each client i.
7: for a A² do
b Global aggregation
( (
ve+1
Σ
S.P
00t + 1
Σ PLa EER2
(4)
BERR
8: end for
9:
Broadcast ((00+), vppp)) VPtt)) to all clients.
10: < p 1.
11:
end while
4.3 Multi-client G-optimal Design
In this subsection, we elaborate the core design of Fed-PE, the collaborative exploration step. There are three main design objectives we aim to achieve: 1) As explained in Section 4.1 one of the main challenges in our federated linear contextual bandits setting is that, each client may benefit differently from the information exchange through the central server. To minimize the overall regret, for each arm AP, it is desirable to ensure that after the global aggregation following the collaboration exploration in phase p. the uncertainty in pP+1 across the clients is balanced. 2) For each client i, in order to eliminate the sub-optimal arms efficiently, it is also important to guarantee that the uncertainty in ap+1 across the arms in Al is balanced. 3) Finally, in order to ensure synchronized s model updating. we aim have each client perform the same number of arm pulling in each phase.
Motivated by those objectives, we propose a multi-client G-optimal design to coordinate the explo- ration of all clients. Specifically, we define xς. Al - [0, as a distribution on the active arm set

---

Af for each i, and denote T" := (mf..... ...) as a vector in Ri |A! Let Ei, == Li,a/ /lla//laall We note that ai equals to either Ei,a or -i Then, we define a feasible set C' C RR LAll follows:
as
Tia 2 2, E M
C
T
ExEr th. = e [M], rank( [T. Cia = rank((etaabee))) Va E A²
(5)
We can verify that CD is convex set. The first two conditions ensure that { la form a valid distribution for each client We name the last condition as the "rank-prexerving" condition. We note that the subspace spanned by the LHS of the rank-preserving condition is always a subset of that spanned by the RHS. Thus, once the rank preserved, the subspaces spanned by the LHS and the RHS the same. Thus, this condition ensures that every dimension of 6, lying in range( {æ heRz) will be explored under the collaborative exploration. Any violation of the Trank-preserving condition will lead to information missing along the unexplored dimensions, which shall be prevented in order to reduce the uncertainty level regarding arm a at every client R.
Then, we formulate the so called multi-client G-optimal design problem as follows:
T T.aaaaaC ) Ci,a s.t. T" E CP.
minimize G(T)
max eT Σ
Σ JERE
aEA
We note that e/ (aaEE) EjERa T. (,a)) ei.o can be interpreted as an approximate measure of the uncertainty level along dimension Fi,a if the arms explored locally according to distributions {=[); Thus, the objective function is an approximate measure of the total uncertainties in the least explored arms at each of the clients. By solving (6). the aforementioned three design objectives can be met. We point out that although the server does not known éi,e, the objective function remains the same when e is replaced by éi Thus, the server can simply use εi,a solve (6)
After solving (6) and obtaining ) the server would set {ff.a = "f DEEAF and send it to client i. Note that after taking the ceiling function, Eas f.P may be greater than f². To ensure synchronized updating, each client would keep pulling the estimated best arm af until the phase length equals f + K.
We note that the multi-client G-optimal design formulated in (6) is related to the G-optimal design for the single-player linear bandits problem discussed in Lattimore and Szepesváril (2020), and the DELB algorithm for the distributed linear bandits in Wang al. 2020). However, for such cases, the player(s) faces single bandit problem, thus the objective is to simply obtain a distribution over so-called core of arms in order to minimize the maximum uncertainty across the arms. In contrast, due to the multiple clients involved in the federated bandits setting and the heterogeneous reward distributions, we are essentially solving M coupled G-design problems, one associated with each client. Such coupling effect fundamentally changes the nature of the problem. leading to very different characterization of the problem and numerical approaches.
In Appendix C of the supplementary material, we analyze an equivalent problem of the multi-client G-optimal design. We note that such equivalence essentially generalizes the equivalence between the original G-optimal design and D-optimal design in Lattimore and Szepesvári (2020) to the coupled design case. While the original G-design problem can be approximately solved through the Frank- Wolfe algorithm under an appropriate initialization (Todd (0166), solving the multi-client G-optimal design problem numerically non- non-trivial. In Appendix C.2, we propose a block coordinate ascent algorithm to solve the equivalent problem of (6) efficiently with guaranteed convergence.
4.4 Theoretical Analysis of Fed-PE
We now characterize the performance of the Fed-PE algorithm.
Theorem Under Assumption 1 with probability at least 1 8, the cumulative regret under Fed-PE scales in O ( Vak MT( (log 7)/6) + min(d, log M)) and the communication cost scales in O(M dl K log T).
7

---

The complete version of Theorem [ and its proof can be found in Appendix Djin the supplementary material. For the communication cost, at each phase p. client i uploads at most K local estimates with dimension d and downloads at most K global estimates and potential matrices with dimension d and d², respectively. Thus, the upload cost is O(MdK log T) and the download cost is O(M K log T).
Remark When we set 8 O( (KKK//r)) the overall regret scales in O(y MT log (Mg(M) and the per-client regret scales in O ( /dKT (oKKToggMMTT) for slandard stochastic MAB scales in
While the minimax lower bound the collaborative learning induced by Fed-PE leads vd/M-fold reduction of the per-client regret. We also note that for single-player linear contextual bandits with disjoint parameters, the best known upper bound scales ÓV MT) (Dinakopoulou et al. (017)) over MT arm pulls, which indicates that the regret of Fed-PE is close to the state-of- -oite--f-thheart centralized algorithms at a communication cost in (log T).
4.5 Enhanced Fed-PE
The original Fed-PE algorithm requires exponentially increasing fe in order to achieve the regret upper bound in Theorem ! This is because in each phase p. we only utilize the rewards collected in phase 1 to estimate 8a. While this simplifies the analysis, the measurements collected in carlier phases cannot be utilized. In order to overcome this limitation, we propose an Enhanced Fed-PE algorithm by leveraging all historical information. Enhanced Fed-PE achieves different tradeoffs between communication cost and regret performance by adjusting f". The detailed description and analysis of Enhanced Fed-PE for different selection of f can be found in Appendix E in the supplementary material.
4.6 Lower Bound
To derive a tight lower bound, we focus on a set of representative policies defined follows.
policy) Two clients i and j are called collinear if there exist an arm a E [K] and a subset S C [M] such that the following conditions are satisfied: 1) vi. & spant (paan[[mmaa (Tm m E S)); and 2) Fiaa E (opan((malle E S} U {Iza)). For any two clients i and that are not collinear, if the action of client is independent of the action of j under a policy n, then, cellinearll-dependdee policy.
Definition 1 Collinearly-dependeee
the policy is called
We note that the definition of ceppeeerlyyddeeendent policies is actually quite natural. Intuitively, for two clients that are not collinear, their local observations on any arm a cannot be utilized to improve each other's knowledge of their own local models. As result, they should not affect each other's s Docision-making process. As shown in the supplementary material, we can verify that the most celebrated ridge regression based LinUCB type of policies (Li et al. 2010), Thompson sampling based polices with Gaussian priors (Agrawal and Goyal 2013b), and least-square estimation based policies, including Fed-PE, all fall in this category.
Theorem 2
For any contextual bandits such that the regret is lower bounded as R(T) (TT
policy, there exists an instance of the federated linear
Remark 2 Theorem 2 essentially shows that, even if raw data transmission and instantaneous com- munication allowed and other cellinearry-dependeen policies are adopted, cannot improve the order of the regret sunmarized in Theorem much, i.e. Fed-PE is order-optimal up /Tog K MT).
The proof of Theorem relies the construction of special instance of the federated linear contextual bandits where the clients can be divided into d groups. Clients in each group face the same K K-armed stochastic bandits model locally, while clients from two distinct groups are not collinear. Analyzing the regret bound in each individual group, we can show that it is lower bounded by ((VK(M KMT/d) Then, by utilizing the property of collinearly-dependeer policies, we can show that the overall regret is lower bounded by @(v BBVdkKM MT) for this scenario. More discussions on the pellinearly-dependee policies and the complete proof of Theorem 2 can be found in Appendix F in the supplementary material.
8

---

Federated Linear Contextual Bandits: Shared Parameter Case
The Fed-PE algorithm can be slightly modified for the shared parameter case where 0, = 8, va E [K] While the client side operation stays the same, the global aggregation step at the server side in ( can be changed by letting the "potential matrix" VP be (E (V "f, and the global estimator OP
be VP [Ei[[N] ErEAr ) Below, we present the main result for this case and leave the detailed algorithm description and regret analysis in the supplementary material.
Theorem Under Assumption 7 with probability at least - 8, the regret of the adapted Fed- Fe the shared parameter case is upper bounded by O (VdMT(log(loo ( and the communication cost scales in O((KdM + di M) log
T)/8) + min [d, log, M MK))
Remark 3 By setting (o/aMTlogMMTRR We note that this bound improves the regret bound for the no differen- tial privacy guarantee case in Dubey and Pentland (2020) by a factor of vlog T, although our settings slightly different. By assuming all clients face the same linear bandits in this shared parameter setting, the regret in the federated setting over horizon T must be worse than the linear bandits over horizon MT. Since the latter is lowered bounded by 2(vdM1 (Chu et al. 2011]. the minimax regret for the shared parameter setting is bounded by O( dMT) as well. Thus, the modified Fed- PE near-optimal for this case.
8 OMV/)T), we can show that the overall regret scales in
In terms of the communication cost, the uploading cost stays the same as in the disjoint parameter case, while the broadcast cost is reduced by a factor of K, since only one potential matrix needs to be broadcast for the shared parameter case.
6 Experiments
Experiment results using both synthetic and real-world datasets are reported in this section to evaluate Fed-PE and the proposed enhancement. Additional experimental details and more experimental results can be found in the supplementary material. We consider four different algorithms, namely, Fed-PE, Enhanced Fed-PE, local UCB without communication, and modified Fed-PE algorithm with full information exchange after collaborative exploration in each phase (coined as 'Collaborative' in Figure D... For all experiments, we set T = 217, f = 2", E {1, 2....... 16), and run 10 trials. For Fed-PE and its variants, choose 8 0.1. Note that other values of 5 may further improve the regret. We evaluate the algorithms on both synthetic and MovieLens- 100K datasets.
Synthetic Dataset:
We first set M 100, K = 10, and d = 3. We set {0a} the canonical basis of RR3, The feature vectors Fi.a are generated randomly ensuring that the suboptimality reward gaps lie in [0.2, 0.4] and f. = 0.5, I, = 1. The per-client cumulative regret
function of T is plotted in Figure [a). We see that Enhanced Fed-PE outperforms Fed-PE while being slightly worse than "Collaborative". This indicates that keeping feature vectors Ii,a private clients does not impact the learning performance significantly. All Fed-PE related algorithms outperform local UCB when T is sufficiently large, demonstrating the effectiveness of communication in improving learning locally, We also set K = 10, = 4, and vary the number of clients M. The performance of Enhanced Fed-PE is plotted in Figure b)). We note that the per-client regret monotonically decreases M increases, corroborating the theoretical results.
Movielens Dataset:
We then use the Moviel.ens- 100K dataset (Harper and Konstan 2015) to
evaluate the performances. Motivated by /Bogunovic et al. (202T) we first complete the rating matrix R = [rraa] E 1992 through collaborative filtering (Morabia 2019), and then use non-negan negative matrix factorization with 3 latent factors to get R WH, where W E 943333 H E R3x 1682, Let Fi be the ith row vector of W. We apply the k-maans algorithm to the row vectors of to produce K = 30 groups (arms), and let 6g be the center of the a-th group. Finally, we randomly choose M = 100 users' feature vectors. We observe that 0.4 < I 1| < 0.8, and the suboptimality gaps lie in [0.01, 0.8). The regret performances of the algorithms are plotted in Figure [[c. The curves show similar characteristics as in Figure a[.. These results demonstrate the effectiveness of collaborative learning in the federated bandits setting.

---

Hi 100 10
K- K=110,d4
Hi 100 6 30,
2100
2000
R177
3000
Fol-2
Tob
109
100
keni UCB
kuni
UCB
2000
4078
1800
40.00
20000
Utive 11000
(a) Synthetic regret.
(b) Regret with varying M.
(c) MovieLens regret.
Figure 1: Pseudo-regret over T.. Shaded area indicates the standard deviation.
Discussion and Conclusion
In this work, have considered novel federated linear contextual bandits model, which naturally connects local stochastic MAB models with linear contextual bandits through common global parameters. While each client only observe projection of each global parameter in its subspace, Fed-PE utilizes the geometric structure the local estimates to reconstruct the global parameters and guide efficient collaborative exploration. Theoretical analysis indicates that Fed-PE achieves near-optimal regret for both disjoint and shared parameter cases with a communication cost in the order of (log T)
An interesting open question is whether we can further reduce the communication cost without downgrading the regret performance. In particular, note the the original single-player G-optimal design allows for sparse solution whose support is of size d(d + 1)/2. Our numerical results indicate that such sparse solutions exist for the multi-client G-optimal design as well. Utilizing the sparsity of the solution may reduce the communication cost significantly. Theoretical characterization of the existence of such sparse solutions is our next step.
Another possible direction to explore is incorporate the differential privaey mechanism to Fed-PE framework. Although local feature vectors {zi,a} are kept private under Fed-PE, local estimate 0g lies in range(Zira.). thus revealing the direction of æi,e the central server. We aim add certain perturbation on 0 in order to obfuscate the direction information without significantly affecting the regret performance.
Acknowledgments and Disclosure of Funding
The work of RH and JY was supported by the US National Science Foundation under Grants CNS-1956276, CNS-2003131, CNS-2114542. and support by the US National Science Foundation under Grants ECCS-2029978, ECCS- CCCC-2003671, and CNS-2002902. WW's work was done before he joined Facebook.
CS acknowledges the funding
References
Agarwal, A., Langford, J., and Wei, C.-Y. (2020). Federated residual learning. arXiv 2003. 12880.
Agrawal, S. and Goyal, N. (2012). Analysis of Thompson sampling for the multi-armed bandit problem. In Conference on Learning Theory, pages 39-1.
Agrawal, S. and Goyal, N. (2013a). Further optimal regret bounds for Thompson sampling. In Artificial Intelligence and Statistics, pages 99-107.
Agrawal, S. and Goyal, N. (2013b). Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th International Conference on International Conference on Machine Learning, pages 1228..
Auer, (2003). Using confidence bounds for exploitation-exxloraaiion trade-offs. J. Mach. Learn. Res., 3:397-422.
Auer, P., Cesa-Bianchi, N., and Fischer, (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-56.
10

---

Auer, P. and Ortner, R. (2010). UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica, 61(1):55-65.
Bogunovic, I,, Losalka, A., Krause, A., and Scarlett, J. (2021). Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 991-999. PMLR.
Bubeck, S. and Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122.
Chu, W., Li, L., Reyzin, L., and Schapire, R. (2011), Contextual bandits with linear payoff functions. In Gordon, G., Dunson, D., and Dudík, M., editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 208-214 214, Fort Lauderdale, FL. USA. PMLR.
Dimakopoulou, M., Zhou, Z., Athey, S., and Imbens, G. (2017). Estimation considerations in contextual bandits. arXiv preprint arXiv:1711.07077.
Dubey, A. and Pentland, A. (2020). Differentially-prisn federated linear bandits. Advances in Neural Information Processing Systems, 33.
Harper, F. M. and Konstan, A. (2015). The MovieLens Datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4).
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., D'Oliveira, R. G. L., Eichner, H., Rouayheb, S. E., Evans, D., Gardner, J., Garrett, Z.., Gascón, A., Ghazi, B., Gibbons, P. B., Gruteser, M., Harchaoui, Z., He, C., He. L.., Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Konečný, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M., Nock, R., Özgür, A., Pagh, R., Raykova, M., Qi, H., Ramage, D., Raskar, R., Song, D., Song, W., Stich, S. U., Sun, Z., Suresh, A. T., Tramèr, F., Vepakomma, P., Wang, J., Xiong. L.,, Xu, Z., Yang, Q. Yu, F. X., Yu, H., and Zhao, S. (2021). Advances and open problems in federated learning. Foundations and Trends0 in Machine Learning. 14(1).
Korda, N., Szorenyi, B., and Li, (2016). Distributed clustering of linear bandits in peer to peer networks. In Balcan, M. F. and Weinberger, K. Q.. editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1301-1309, New York, New York, USA. PMLR.
Lai, T. L. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22.
Landgren, P., Srivastava, V., and Leonard, N. E. (2016). On distributed cooperative decision-makee maaking in multiarmed bandits. In 2016 European Control Conference (ECC), pages 243-248. IEEE
Landgren, P., Srivastava, V., and Leonard, N. E. (2018). Social imitation in cooperative multiarmed bandits: partition-based algorithms with strictly local information. In 2018 IEEE Conference on Decision and Control (CDC), pages 5239-5244. IEEE.
Langford, J. and Zhang, T. (2008). The epoch-greedy algorithm for multi-armed bandits with side information. In Advances in Neural Information Processing Systems, pages 817-824.
Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.
Li, L., Chu, W., Langford, J., and Schapire, R. (2010). A contextual-bamie approach personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, pages 661-670
Li, T., Song, I.., and Fragouli, C. (2020). Federated recommendation system via differential privacy. In IEEE International Symposium on Information Theory (ISIT), pages 2592-2597.
Martinez-Rubio, D., Kanade, V., and Rebeschini, (2019). Decentralized cooperative stochastic bandits. In Advances in Neural Information Processing Systems, pages 4529-4540.
11

---

McMahan, B., Moore. E., Ramage, D., Hampson, S., and y Arcas, B. A. (2017). Communication efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference Artificial Intelligence and Statistics (AISTATS), pages 1273-1282, Fort Lauderdale, FL., USA.
Morabia, K. (2019). Collaborative-fiterine
Shi, C. and Shen, C. (2021). Federated multi-armed bandits. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI).
Shi, C., Shen, C.. and Yang. J. (2021). Federated multi-armed bandits with personalization. In Pro- ceedings of the 24rd International Conference on Artificial Intelligence and Statistics (AISTATS).
Szorenyi, B., Makeee R., Hegedus, I., Ormandi, R., Jelasity, M., and Kegl, B. (2013). Gossip- based distributed stochastic bandit algorithms. In Proceedings of the 30th International Conference on Machine Learning, pages 19-27.
Todd, M. J. (2016). Siiinuum-Volune Ellipsoids. Society for Industrial and Applied Mathematics, Philadelphia, PA.
Wang, Y., Hu, J., Chen, X., and Wang. L. (2020). Distributed bandit learning: Near-optimal regret with efficient communication. In International Conference on Learming Representations.
Zhu, Z., Zhu, J., Liu, J., and Liu, Y. (2021), Federated bandit: A gossiping approach. Proceedings of the ACM Measurement and Analysis of Computing Systems, 5(1):1-29.
12


Reviews:
[{"review_id": "n9B0jYMjibP", "reviewer": "Reviewer_MvqL", "summary": "This paper discusses the federated multi-armed bandit problem with linear reward functions. The formulation utilizes a linear structure with agent-dependent contexts to model differences between agent reward functions. The authors propose an algorithm based on a multi-agent G-optimal design with competitive theoretical performance under heterogeneity. The authors additionally establish minimax rates under a reasonable collinearity assumption. The algorithms FedPE and Enhanced FedPE additionally provide competitive experimental performance on both simulated and real-world benchmarks. In summary, the paper is a good contribution, however, there are some issues that I would like to see addressed as well.", "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": "Originality: I believe the primary novelty of the paper is to present a linear formulation of heterogeneity across agents for the federated multi-armed bandit problem and then proposing a variant of G-optimal design. Currently, the paper is positioned (and compared against) federated contextual bandit algorithms (where the decision set changes with each iteration), whereas IMHO the paper is more suitable as a context-free formulation that essentially uses this linear formulation to account for heterogeneity within the different agents. The subsequent contributions (algorithm design, minimax rates with collinearity) all follow more smoothly from a conceptual POV if viewed from this lens, instead of a \"contextual\" premise. I have discussed the \"contextual\" aspect more in the \"Issues/Concerns\" section below as well.\n\nGiven the above consideration, I believe the paper has a good set of contributions from an algorithmic perspective with accompanying theoretical guarantees (based on a skim of the appendix, the proof technique is primarily a modification of the existing G-optimal route). I believe that a log T-style regret bound can also be derived by assuming a minimum gap of $\\Delta$ between the rewards of the best and second-best arms for all agents, allowing us to compare more directly with multi-armed algorithms. Furthermore, the current analysis provides a worst-case regret bound, which incurs a factor of $O(\\sqrt{K})$ regardless of the parameters $\\theta$, but it would be interesting if the authors proposed a hybrid \"smooth\" model, where one can interpolate between \"shared\" parameters and distinct parameters with an interpolating regret bound.\n\nClarity: The paper is well-written and easy to understand, although I would recommend proofreading to iron out typos and some grammatical issues (minor).\n\nSignificance: There is a lot of interest in the federated/distributed bandit case, and this paper will be relevant to that sub-community.\n\nIssues/Concerns:\n- \"Contextual\" bandits setting: The authors incorrectly describe their setting as \"contextual\" whereas their setting is clearly the stochastic linear bandit setting. This is not \"contextual\" as the set of contexts are fixed and do not vary with time (Lattimore and Szepesvari, 2020, Chapter 20 clearly makes this distinction by calling it \"Stochastic Linear Bandits\" instead of \"contextual\"). This may seem like a nitpick, but it makes the setting considered in the paper much clearer.\n\n- Comparison with Dubey and Pentland (2020): The regret bound presented in the former paper (Theorem 1 and Corollary 1) involves an $\\mathcal O(M\\sqrt{T}/\\varepsilon)$ term that arises due to the $(\\varepsilon, \\delta)$-DP privacy guarantee, and not because of inefficiency in communication. A fair comparison would therefore be to set their FedUCB algorithm to work with no DP guarantee, i.e., $\\varepsilon \\rightarrow \\infty$, in which case the bound is $\\widetilde{\\mathcal O}(\\sqrt{dMT})$. Furthermore, I do not see any comparisons with FedUCB in the experiments?\n\n- Multi-armed bandit baselines/literature review: I feel that the federated (context-free) bandit literature is also relevant as both baselines (say federated UCB1 without contexts) and part of the related work.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One limitation that the authors have to be clear about is that while this setting is indeed linear, it assumes a multi-armed environment with a fixed set of arms, which makes it inapplicable for many real-world federated learning settings such as federated recommendation systems, where the set of contexts changes with time and G-optimal design is not applicable. The authors should address this in their paper.\n\nI do not foresee any direct societal consequences from this paper, but the authors do not discuss this either.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "W5egKqrOUsX", "reviewer": "Reviewer_N57f", "summary": "The paper studies a federated setup where each client faces a stochastic contextual bandit.  The parameters of the bandits are coupled across the clientsm. The clients share their local estimates with the server which aggregate them and share back with the clients. The client are hetogenous and the server leverages the geomereic structure of the linear rewars to facilitates the clients learn the optimal arms.  Authors propose a collaborative algorithm called Fed-PE that do not require the nodes to exchange the local feature vectors thus preserving the privacy of the nodes. The authors consider the cases where the paramers are disjoint across the arms or coupled. The performance of the algorithms are valued on both synthetic and real datasets. ", "questions": "", "limitations": "", "rating": 5, "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": "The problem of contextual bandits in a federated setup is interesting. The authors' attempt to model this problem and analysis is appreciable. \nHowever, the way the problem is motivated and it is modeled is not consistent. \n\n--In the motivational applications of personalized content recommendation and personalized online education, the contexts are dervied from the user profile, and for different users, the context can be different. But in the model, contexts are fixed. Should not the context be allowed to change in each round? \n\n--Is $f^p$ input to the algorithm? How is it set?\n\n--Line 198:  It is unlcear why $\\overline{e}_{i,a}$ in range$(x_{i,a})$\n\n----\n\nPost rebuttal:\n\nThe authors said \"we consider a multi-client model, where each client is associated with a fixed user profile. The variation of contexts is captured over clients as opposed to overtime. we consider a multi-client model, where each client is associated with a fixed user profile.\"\n\nThis part of the motivation to model is not satisfying. If there is one learner for each profile, one has to consider a large number of learners as the number of profiles can be arbitrarily large. Also, in practice, I do not anticipate there will be one learner for each profile in applications like personalized content recommendations. The whole point of learning in personalized content recommendations is to figure out optimal action for (possibly) unseen profiles. This motivation of one learner per profile does not sound unsatisfying.\n\nI keep my score unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Uz9kS1DTEth", "reviewer": "Reviewer_ZDt5", "summary": "This paper considers a linear contextual bandits problem in a federated setting where different users have different contexts but the rewards are generated through common global parameters. The goal is to minimise the regret for each user while sharing the exploration across users. The paper proposes an algorithm termed Fed-PE with regret bounded as O(\\sqrt{dMT}), where d is the dimension of contexts, M is the number of users and T is the time-horizon. A matching lower bound is also presented showing that this regret is tight. The main challenge in this setting is to \\emph{balance} the exploration across users as contexts might be very diverse. In order to address this challenge the paper proposes a new G-optimal design which optimises for balanced exploration across users. ", "questions": "", "limitations": "", "rating": 7, "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": "Even though there is a burgeoning literature on federated/distributed settings for linear bandits, the setting considered in this paper is new, interesting and well motivated. I think the technical contributions of this paper are also sound. I like the idea of G-optimal design and its integration with a policy that only updates O(log T) times.  \n\nAdditional comments:\n\n1. Arm Elimination: The current algorithm successively eliminates arms over time for each user. Is it possible to design an algorithm in this setting that does not eliminate arms over time similar to the UCB algorithm for non-contextual bandits?  \n\n2. Shared contexts across users: The current algorithm does not take advantage of the fact that some contexts across users might be similar. For example, there might be just m different \"generic types\" of users and each user might be from one of these types. In this case the dependence on M may be replaced with the dependence on m. Is it possible to do this in a more data dependent way, i.e. by designing an algorithm that automatically detects shared contexts?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper argues that their algorithm is \"private to some extent\" as the context vectors are not sent to server, but I am not quite satisfied with this claim as a simple transformation of the context vectors is anyways sent to the server. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "FWdzWt3Oi9m", "reviewer": "Reviewer_LC6L", "summary": "I think the paper sufficiently characterizes the federated linear contextual bandits problem (i) it proposes an algorithm for both the shared parameter and disjoint parameter setting (ii) proves regret guarantees and (iii) characterizes a reasonable class of policies for which a lower bound holds; this lower bound shows that the achieved regret guarantees are near optimal. The communication cost of the algorithm is also reasonable w.r.t to prior work. I think the writing of the paper can be improved in some areas and some technical points need to be explained more, but over all I think this is a good paper. ", "questions": "", "limitations": "", "rating": 7, "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": "Pros.\n\n1. The paper characterizes the problem almost completely providing algorithms, regret upper bounds and lower bounds for a class of policies.\n2. The algorithm uses the well known D-optimal design phased algorithm from Lattimore and Szepesvari, however I think several small innovations are required to make it work in the federated setting where the context vectors are different for each agent and can potentially span different subspaces of R^d. I find the discussion in section 4.1 useful.\n3. It seems that the paper also develops a new block coordinate ascent algorithm to solve the multi-agent G-optimal design problem (it is a quite natural extension to G-optimal design). Unfortunately I did not check the derivation as it has been pushed to the appendix, but this also seems like a good contribution.\n4. I am quite intrigued by the class of policies in the lower bound. It seems that if we stay within this class the regret bounds are almost tight. I would still need to gain more intuition for this result (see below).\n\nCons and Clarification needed.\n\n1. In the introduction it would be better if the authors choose one of the applications for example the content recommendation one and maps each of the problem details like thetas, x's and rewards to real world objects in that problem. In my experience this always makes it easier to understand the relation of the problem to the applications.\n\n2. The model is listed as one of the contributions. Is the model in the FedUCB paper different from the shared parameter setting? -- please clarify this. I know that they are interested in DP but my question is wrt the model alone.\n\n3. It seems that because of the differential privacy constraint the FedUCB paper achieves a worse dependency of d^{3/4} but table 1 lists a sqrt{d} dependence for this paper. Am I misunderstanding the result of the FedUCB paper?\n\n4.  I am not an expert in federated learning so this might be a naive question. In line 139 it says that the communication cost is measured in terms of number of scalars communicated. But it seems that if the size of each such scalar is unlimited one might be able to encode a lot of information in each of them using a coding scheme. Should this not be restricted?\n\n5. I understand from context what f_p is but can you please point me to where this is first defined in the paper? I seem to have missed it.\n\n6.  In the original G-optimal design based algorithm if the elimination criterion is in terms of optimality gap being larger than 2^{-l} in phase l. However, here it is changed to UCB < LCB kind of a condition. What is the intuition or reason behind this? Is this mentioned in the paper?\n\n7.  I think a little more discussion is needed about the \"rank-preserving\" condition. To me it seems that we are just ensuring that the rank is same, however can the subspace spanned by the LHS and the RHS be completely different?\n\n8. I am not being able to gain a lot of intuition about collinearly-dependent policies from the text description. I think it is really important to explain this part well. I am confused by the fact that in def 1 we require this to hold for just \"an arm a\" and also one specific subset \"S\". However, in the next paragraph it is claimed that \"Intuitively, for\ntwo clients that are not collinear, their local observations on \"\"any\"\" arm a cannot be utilized to improve\neach other’s knowledge of their own local models\". Please add more details about why this follows.\n\n9. Each client initially starts by pulling each arm once. This might be reasonable for the disjoint parameter case. For the shared parameter setting this is not a good idea when K is very large. For instance the original G-optimal algorithm starts by pulling a set of arms of size only d(d+1)/2. I think this needs to be incorporated in the shared param setting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors have adequately addressed the limitations and societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns regarding this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: During discussion, all reviewers agreed that though the motivation for the precise setting is unclear, the paper makes good technical contributions and so I am recommending the paper for acceptance. However, I ask the authors to incorporate a discussion on the assumptions of each client serving one user and possible extension to potential new users entering the system.
Decision: Accept (Poster)