Federated Linear Bandits with Finite Adversarial Actions
Authors: Li Fan
Ruida Zhou
Chao Tian
Cong Shen
Venue: NeurIPS 2023 poster (2023)
Keywords: Federated bandits
contextual bandits
regret analysis
TL;DR: We propose new federated linear bandits algorithms that achieve minimax lower bound with sublinear communication cost with finite adversarial action sets that may be different across clients.

Abstract: We study a federated linear bandits model, where $M$ clients communicate with a central server to solve a linear contextual bandits problem with finite adversarial action sets that may be different across clients. To address the unique challenges of **adversarial finite** action sets, we propose the FedSupLinUCB algorithm, which extends the principles of SupLinUCB and OFUL algorithms in linear contextual bandits. We prove that FedSupLinUCB achieves a total regret of $\tilde{O}(\sqrt{d T})$, where $T$ is the total number of arm pulls from all clients, and $d$ is the ambient dimension of the linear model. This matches the minimax lower bound and thus is order-optimal (up to polylog terms). We study both asynchronous and synchronous cases and show that the communication cost can be controlled as $O(d M^2 \log(d)\log(T))$ and $O(\sqrt{d^3 M^3} \log(d))$, respectively. The FedSupLinUCB design is further extended to two scenarios: (1) variance-adaptive, where a total regret of $\tilde{O} (\sqrt{d \sum \nolimits_{t=1}^{T} \sigma_t^2})$ can be achieved with $\sigma_t^2$ being the noise variance of round $t$; and (2) adversarial corruption, where a total regret of $\tilde{O}(\sqrt{dT} + d C_p)$ can be achieved with $C_p$ being the total corruption budget. Experiment results corroborate the theoretical analysis and demonstrate the effectiveness of \alg on both synthetic and real-world datasets.

Federated Linear Bandits with Finite Adversarial Actions
Li Fan University of Virginia Lf2by@virginia. edu
Ruida Zhou Texas A&M University ruida@tamu, edu
Chao Tian
Cong Shen
Texas A&M University chao. t tian@tamu. edu
University of Virginia cong@virginia.cmm edu
Abstract
We study federated linear bandits model, where M clients communicate with central server to solve a linear contextual bandits problem with finite adversarial action sets that may be different across clients. To address the unique challenges of adversarial finite action sets, we propose the FedSupLinUCE algorithm, which extends the principles of SupLinUCB and OFUL algorithms in linear contextual bandits. We prove that FedSupLinUCE achieves a total regret of D(VTT), where is the total number of arm pulls from all clients, and d is the ambient dimension of the linear model. This matches the minimax lower bound and thus order-optimal (up to polylog terms). We study both asynchronous and synchronous cases and show that the communication cost can be controlled as (dM2 log(d) log(T)) and O de M log(d)), respectively. The FedSupLinUCB design is further extended to two scenarios: (1) variance- where total regret of Ö( d d o3) can be achieved with of being the noise variance of round f; and (2) adversarial corruption, where a total regret of Ô + dC,)) can be achieved with C, being the total corruption budget. Experiment results corroborate the theoretical analysis and demonstrate the effectiveness of FedSupLinUCB on both synthetic and real- world datasets.
Introduction
In the canonical formulation of contextual bandits, single player would repeatedly make arm-pulling decisions based on contextual information with the goal of maximizing the long-term reward. With the emerging federated learning paradigm (MeMahan al.) 2017) where multiple clients and server jointly learn a global model with each client locally updating the model with its own data and server only aggregating the local models periodically, researchers have started exploring contextual bandits algorithms in such federated learning setting (Dubey and Pentland] 2020 Huang et al. 202T Li and Wang 2022a b). This federated contextual bandits framework broadens the applicability of contextual bandits to practical scenarios such as recommender systems, clinical trials, and cognitive radio. In these applications, although the goal is still to maximize the cumulative reward for the overall system, decision decision-making and observations are naturally distributed at the participating clients.
Several intrinsic challenges arise with the federated contextual bandit formulation. One important issue is that besides regret, we should also take into account the communication cost, which is usually the system bottleneck. To reduce the communication guarantee, the clients should transmit the necessary information to the server only when the local
while maintaining the same regret
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

information has accumulated to the extent that it would affect the decision- decision-making. Compared with the centralized contextual bandits, which have a linearly growing communication cost, algorithms for federated contextual bandits attempt to achieve comparable regret with sub-linear communication cost.
Second, most existing studies on federated contextual bandits focus on the synchronous commu- nication scenario (Huang al. 202 Li and Wang 2022b), in which all participating clients first upload local information and then download updated global information from the server in each communication round. This stringent communication requirement is often not met practice. A recent work of Li and Wang (2022a) studies the asynchronous federated linear bandit problem. However, communications for different clients are not independent in their approach because the upload from one client may trigger the server to perform downloads for all clients. To address this issue, He et al. (2022a) proposes Fedl .inUCB, which enables independent synchronizations between clients and the server.
Third, the majority of prior studies on federated linear bandits focused on the infinite-arm setting (i and Wang, 2022b at He et al. (2022a) (see Section 2 for a detailed literature review). From a methodology point of view, these papers largely build on the OFUL principle (Abbasi- Yadkori et al.
201T). One notable exception is Huang et al. (202T), which studies synchronous communication with fixed contexts and proposes the Fed-PE algorithm based on the phased elimination G-optimal design
(Lattimore and Szepesvári 2020). To the best of our knowledge, no prior result exists for federated
linear bandits with finite arms and time-evolving adversarial contexts, which is the focus of our work.
Table I: Comparison of this paper with related works
System
Action
Algorithm
Regret
Communication N/A
Single-player
infinite arm
OFUL (Abaasi- Yadkori et al. PE G-optimal
2011:
dyTlog
Single-player
finite fixed arm
(Lattimore and Szepesvári
2020
O(villogg))
N/A
Single-player
finite adversarial arm
SupLinUCB Chu al.
2011
OlyaTlog" T)
NIA
Federated (Asyne)
infinite arm
FedLinUCB He al.
2022a
OldvTlog 7")
OldM- log T)
Federated (Async)
infinite am
Asyne-LinUCB and Wang
2022a
OldvTT Tug
OldM' log T)
Federated (Sync)
infinite arm
DisLinUCB Wang et al. 2019
OldyT log"
O(dM(42)
Federated (Sync)
finite fixed arm
Fed-PF: (Huang ol al. 2002
O(V2rlogg] Tog
Old K log 7')
Federated (Async)
finite adversarial arm
FedSupLinUCB (This work)
Oly log" T)
OlaM? log d d T)
Federated (Syne)
finite adversarial arm
FedSupl (This work)
O(y d'''og" T")
O645/2 wa/2 log(d))
d: the dimeasion of the unknown parameter, M: the number of clients, K: the number of tinite actions, T:: the total arm pulls from all clients.
Main contributions. Our main contributions are summarized as follows.
We develop a general federated bandits framework, termed FedSupLinUCE, for solving the problem of federated linear contextual bandits with finite adversarial actions. FedSupLinUCB extends SupLinUCB (Chu et al.) [001 Ruan et al., (02T) and OFUL (Abbasi- Yadkori et al.) (201I), two important principles in (single-player centralized) linear bandits, to the federated bandits setting with carefully designed layered successive screening.
We instantiate FedSupLinUCB with both asynchronous and synchronous client activities. For the former setting, we propose Async-FedSupLintue where communication is triggered only when the cumulative local information impacts the exploration uncertainty to a certain extent. We prove that Async-FedSupLiinUCa achieves Ö(VdT) regret with Odd log d log T') communication
cost, which not only reduces the regret by vd compared with previous results on asynchronous federated linear bandits with infinite arms, but also matches the minimax lower bound up to polylog terms, indicating that Asyne-Feddsse redSupLinUCe achieves order-optimal regret.
For synchronous communications, we propose Seine-FeSSuLLinUCC which has a refined communi- cation design where only certain layers communicated, opposed to the complete information. Syne-FedSupLinnCC achieves order-optimal regret of Ö(VdT) with horizon-independent com- munication cost O ( M3 log d). Compared with the best previous result (Huang et al. 2021) which achieves the same order-optimal regret but only for fixed actions, we show that it is the finite actions that fundamentally determines the regret behavior in the federated linear bandits setting.
We further develop two extensions of FedSupLinUCB: (1) Variance-adaptive FedSupLinUCB, for
which total regret of δ(v ( of) is achieved, where of is the noise variance at round 1. (2)
2

---

Adversarial corruption FedSupLinUCE, for which total regret of Ó(VAT + dCp) is achieved, where Cp is the total corruption budget.
2 Related Works
The linear bandit model, as a generalization of finite armed bandits with linear contextual information. has been extensively studied. The setting of infinite arm sets solved by LinUCB was analyzed in (Dani et al. 2008 Abbasi-Yadkon et al. 2011), which achieves regret (dd'T) with appropriate confidence width (Abbasi- et al., 2011) and matches the lower bound (Dani et al. 2008 up to logarithmic factors. In contrast, algorithms like SupLinRel (Auer 2002) and SupLin (Chu et al. 2011 achieve ((VdT) in the setting of finite time-varying adversarial arm sets under K < 2d
with lower bound ((vdT) (Chu et al. 2011). The SupLinUCB algorithm was later optimized and matches the lower bound up to iterated logarithmic factors in et et al. (019)). As a special case of the finite arm setting, if the arm set is time-ine -nvaiiirii,n,, an climination based algorithm (Lattimore and Szepesvári 2020) via G-optimal design can be applied to achieve similar optimal performance.
The federated linear bandits problems were studied under the settings of infinite arm set (Dubey and Pentland 2020 [i et al. 2020, Li and Wang 2022a) and time-invariant finite arm set (Huang et al. [021]. while the varyyngg finite arm set setting has not been well explored. A finite time-varying arm set has many meaningful practical applications such as recommendation system (Li et al. 2010 Chu et al. 2 and the distributed (federated) nature of the applications naturally falls in the federated linear bandits problem with finite time-varyinn varying arms. The paper fills this gap by generalizing the SupLinUCB algorithm to the federated setting.
We study both the asynchronous setting (Li and Wang, (022a) (He et al., (022a), where clients are active on their own and full participation is not required. and the synchronous setting (Shi et al. 202T]
Dubey and Pentland 22000), where all the clients make decisions at each round and the communication round requires all the clients to upload new information to the server and download the updated information. We design algorithms so as to reduce the communication cost while maintaining optimal regret. Technically, the communication cost is associated with the algorithmic adaptivity, since less adaptivity requires fewer updates and thus fewer communication rounds. The algorithmic adaptivity of linear bandits algorithms was studied in the single-player setting (Han et al. (2020) (Ruan et al.
202T). It was also considered in the federated setting (Wang et al. 2019 Huang et al. 202 Salgia
and Zhao 2023).
3 System Model and Preliminaries
3.1 Problem Formulation
We consider federated linear contextual bandits model with K finite but possibly time-varying arms. The model consists of M clients and one server in star-shaped communication network. Clients jointly solve lincar bandit problem by collecting local information and communicating with the central server through the star-shaped network in a federated manner, with no direct communications among clients. The only function of the server is to aggregate received client information and to send back updated information clients. It cannot directly play the bandits game.
Specifically, some clients I, S [M] are active at round t. Client E I, receives K arms (actions to take) associated with contexts ) (s(]]] C Rd with ||=ttalle < Here we adopt the oblivious adversarial setting, where all contexts are chosen beforehand, and not dependent on previous game observation. Client then pulls an arm of E [K] based on the information collected locally well as previously communicated from the server. A reward rr. 0 x² t,a] ce is revealed privately
to client i, where 0 E Rd is an unknown weight vector with |01| < and e; is an independent u-sub-Gaussian noise. At the end of round f, depending on the communication protocol, client may exchange the collected local information with the server that it can update the global information.
We aim to design algorithms to guide the clients' decision-making and overall communication behaviors. We analyze two patterns of client activity. 1) Synchronous: all M clients are active at each round. 2) Asynchronous: one client is active at each round. For the latter case, we further assume that client activity is independent of data and history. Denote by T, the number of times client
3

---

i is active. In the former case, T; = Vi,j E [M.] while in the latter case, T may be different among clients. We define T -'=-> -E T; as the total number of arm pulls from all clients.
The performance measured under two metrics total regret and communication cost, which concern the decision-maie Pj = {t E [T] E I the set of time indices at which client is active, with Pr = T.. The total regret is defined as
effectiveness and the communication efficiency respectively. Denote by
M
M Σ
RT
(I)
where a. arg m xi.a- communication rounds between clients and the server.
We define the communication cost as the total number of
3.2 Preliminaries
Information encoding. In the linear bandits setting (federated not), the information client acquires is usually encoded by the gram matrix and the action-reward vector. Specifically, when the client has observed action-reward pairs {(Ir, rt) the information is encoded by matrix A, 1= FzZ, and vector bn E retg. Denote by Encoder(-) this encoding function, i.e., An, bn Encodcr( (e rele
Communication criterion. Communication in our proposed framework is data-dependent, in the same spirit as the "doubling trick" introduced in in(bbasi-- Yadkori et al. (2011) to reduce the compu- tation complexity in single-player linear bandits. The key idea is that communication is triggered only when the cumulative local information, represented by the determinant of the gram matrix An, affects the exploration uncertainty great extent and hence the client needs communicate with the server. Detailed communication protocols will be presented in each algorithm design.
Synchronization procedure. Denote by Sync() routine that clients (client I. client n) first communicate their local gram matrices and action-reward vectors to the server, and the server then ag- gregates the matrices (and vectors) into one gram matrix (and action-reward vector) and transmits them back to the n clients. Specifically, each client holds newly observed local information (AA', Ab"), which is the difference between the client's 's current information (A', 6') and the information after the last synchronization. In other words, (AA', At') is the information that has not been commu- nicated to the server. The server, after receiving the local information {(AA', Ab) 1 updates the server-side information (A*er, beer) by A see + A + >i= AA', . < baer + 21=1 Ab' and sends them back to each of the n clients. Each client i will then update the local information by A' + Aee l + beer_ The procedure is formally presented in Algorithm
Algorithm 1 Sync(s, server, client 1, client n)
b Client-side local information upload 2: Client i sends the local new layer information (AA', Ab;) to the server
for = 2...... n do
3: end for
4: Update server's layer information:
Server-side information aggregation and distribution
A Aser
A4 beer
ser
A
5: Send server information Ager, Dger back all clients
6: for i = 1,2, ..., do
7: A < Ager bi f- bger, AAAA + 0, Ab 0
Client updates the local information
8: end for
The FedSupLinUCE Framework
In this section, we present general framework of federated bandits for linear bandits with finite obliv- ious adversarial actions. Two instances (asynchronous and synchronous) this general framework will be discussed in subsequent sections.

---

Building block: SupLinUCB. As the name suggests, the proposed FedSupLinUCE framework built upon the principle of SupLinUCB (Chu al., 2011 Ruan et al. 2021). The information b) is useful in the sense that the reward corresponding to an action x can be estimated within confidence interval x T = a |=|=,||-- where 0 = A It is shown in Abbasi-Yadkori et al. 2011) that in linear bandits (even with an infinite number of actions) with within the confidence interval with high probability. Moreover, if the rewards in the rewaod vector are mutually independent, can be reduced to O(1). The former choice of a naturally guarantees (dd/T) regret. However, to achieve regret Ō Ö(vdT), it is critical to keep a = O(1). This is fulfilled by the SupL.nnCCB algorithm (Chu et al., 2011) and then recently improved by Ruan al. (02TD. The key intuition to successively refine an action set that contains the optimal action, where the estimation precision of sets is geometrically strengthened. Specifically, the algorithm maintains (S + layers of information pairs {(Ag, ba) 1=-p= and the rewards in the action-reware vectors are mutually independent, except for layer O. The confidence radius for each layer is W, = d-. /V....
O(vd). the true reward is
Algorithm 2 S-LUCB
1: Initialization: = [log wo /// u. + wo Vs [1:
2: =1+ -1+ (d + 1 +
Vs [1:
3: Input: Client i (with local information A A',b', AA', Ab'), contexts set f......... oi,
4: Ai,a A AA',
Ai by, bú Ab',
Ai.s Ai, bi, by for lazy update
5: 0g + 1b t,a,0 = 0_ ah wi t asllziall(At..) Vs E 10: S], Va E [K]
6: 8 +-- 0: Ao < {a E [K] fl.0a + whoa 2 max
w o b Initial screening
7: repeat
D Layered successive screening
8:
if = then
9:
Choose action ot arbitrarily from As else wi. S W. for all a E A, then
10:
11:
Ast1 + fa A. fi 2 ea (f) (fh,,,ar 2w.}: s s+1
12:
else
13:
at t arg max (aEA,.EA.. >w,} wi,0
14:
end
15:
until action at is found
Take action af and and receive reward ri.0
AA + AA' + "r,o "t Ab', + Ab, + 1, ot
Update local information
t,a)
18:
Return layer index
FedSupLinUCB. S-LUCB, presented in Algorithm combines the principles of SupLinUCB and OFUL Abbasi-Yadkon et al.) 2011) and is the core subroutine for FedSupLinUCB. We maintain s == [log d] information layers, and the estimation accuracy starts from d=.5 /VT of layer 0 and halves as the layer index increases. Finally, takes O (log d) layers to reach the sufficient accuracy of /d/T and achieves the minimax-optimal regret.
When client is active, the input parameters (A'', 6¹) contain information received from the server at the last communication round, and (AA', "''''b'' Ab") is the new local information collected between two consecutive communication rounds. {ai,1...., , is the set of contexts observed in this round. Client can estimate the unknown parameter either with all available information or just making a lazy update. This choice depends on the communication protocol and will be elaborated later. During the decision making process, client first makes arm climination at layer 0 to help bootstrap the accuracy parameters. Then, it goes into the layered successive screening in the same manner as the SupLinUCB algorithm, where we sequentially climinate suboptimal arms depending on their empirical means and confidence widths. After taking action of and receiving the corresponding reward r " client updates its local information set (AA', Ab;)) ) by aggregating the context into
layer in which we take the action, before returning layer
5

---

Asynchronous FedSupLinUCB
In the asynchronous setting, only one client is active in each round. Note that global synchronization and coordination are not required, and all inactive clients idle.
5.1 Algorithm
We first initialize the information for all clients and the server (gram matrix and action-reward vector) in each layer [0 .).. We assume only client 8 is active round (. It without loss of generality since if multiple clients are active. we can queue them and activate them in turn. More discussion of this equivalence can be found in He al. (2022a): Li and Wang (2022a). The active client chooses the action, receives a reward, updates local information matrices of layer s with lazy update according to S-LUCB, and decides whether communication with the server is needed by the criterion in Line 7 of Algorithm 3 server by Algorithm
If communication is triggered, we synchronize client in with the
Algorithm 3 Async-FedSupLiinuCB
Initialization: T, C, S [logd]
2: [Aser + Ia. beer +- 0| [0: S]}
Server initialization
3: {Ar - Ia, AA by, Ab; 0 o0sse [0: $) [M]]
Clients initialization
4: fort= = 1,2, ... . do
5:
Client = is active, and observes K contexts fa; 22.2."...
6:
+ S-LUCB (client i, { "ं.; . x with lazy update
7: if det (a)+4)) > (1 + C) then
det(AA)
8:
Sync(s, server, clients i) for each [0]
9: end
end for
5.2 Performance Analysis
Theorem 5.1. For any < 8 1, if we Algorithm with C 1/M2, then with probability
at least 1 - 8, the regret of the algorithm is bounded as Rr I Ō (
= Ō (VaT))
Moreover, the corresponding communication cost is bounded by (dd log log T)-
Remark 1. The minimax lower bound of the expected regret for linear contextual bandits with K adversarial actions is ((VdT), given in Chu et al. (001)). Theorem 5.1 indicates that Asyne- FedSupLinUCB achieves order-optimal regret (up to polylog term) with O ( log d log 7) commu- nication cost. To the best of our knowledge, this is the first algorithm that achieves the (near) optimal regret in federated linear bandits with finite adversarial actions.
Remark 2. Without any communication, each client would execute SupLinUCB (Chu et al. 2011 for T; rounds locally, and each client can achieve regret of order Ö(VTT). Therefore, the total regret of
M M clients is upper bound by Rr EM Vdl, polylog (T) $ v dM E E T, polylog(T), where the last inequality becomes equality when T; = T3 Vi,j E [M]. Compared with conducting independent SupLinUCB algorithms locally, Async-FedSupLindee of 1/ I/MM, demonstrating that communications in the federated system speed up local linear
yields an average per-client gain
bandits decision decision-making at clients.
Most previous federated linear bandits consider the infinite action setting, based on the LinUCB principle OobasiiYadkoot et al., 201T). Async-FedSupLinnCcs considers a finite adversarial action setting and has a Vd reduction on the regret bound. Fed-PE proposed Huang er 2021) also considers the finite action setting. However, their action sets are fixed. We generalize their formulation and take into account more challenging scenario, where the finite action set can be chosen adversarially. The regret order is the same Fed-PE (ignoring the ploylog term), indicating
Remark 3.

---

that it is the finite actions as opposed to fixed actions that fundamentally leads to the v regret improvement the federated linear bandits setting.
Communication cost analysis of FedSupLinUCE. We sketch the proof for the communication cost bound in Theorem 5.1 in the following, while deferring the detailed proofs for the regret and the communication cost to Appendix
We first study the communication cost triggered by some layer 8. Denote by A the gram matrix in the server aggregated by the gram matrices uploaded by all clients up to round L. Define Ta, - min E det (A 2 )",, for each n 2 We then divide rounds into epochs {T Tw. 1, mmin(T++1... - 3 for each n 2 The number of communications triggered by layer within any epoch can be upper bounded by 2(M + 11/C) (see Lemma C.I and the number of non-empty epochs at most log(1 + T/dd) by Lemma Since there are S [log d) layers and synchronization among all layers is performed once communication is triggered by any layer (Line 8 in Algorithm 3. the total communication cost is thus upper-bounded by O(d(M + 1/C) log log T). Plugging C 1/M² proves the result.
We note that although choosing a larger C' would trigger fewer communications, the final choice of 1/M² takes into consideration both the regret and the communication cost, i.e., to achieve
1 C== small communication cost while maintaining an order-optimal regret.
6 Synchronous FedSupLinUCE
In the synchronous setting, all clients are active and make decisions at each round. Though it can be viewed special case of the asynchronous scenario (clients active and pulling arms in a round-robin manner), the information update is broadcast to all clients. In other words, the key difference from the asynchronous scenario besides that all clients are active at each round is that when a client meets the communication criterion, all clients will upload local information to the server and download the updated matrices. This leads a higher communication cost per communication round, but in this synchronous scenario, knowing all clients are participating allows the communicated information be well utilized by other clients. This is in sharp contrast the asynchronous setting, where if many other clients are active in the current round, uploading local information to the clients seems unworthy. To mitigate the total communication cost, we use a more refined communication criterion to enable time- time-indepenee independent communication cost.
6.1 The Algorithm
The FenupPedSu algorithm allows each client to make decisions by the S-LUCB subroutine. Note that the decision decision-making is based on all available local information instead of the lazy update in the FedSupLinSUs algorithm. The communication criterion involves the count of rounds since the last communication, which forces the communication to prevent the local data from being obsolete. Some layers may trigger the communication criterion either because the local client has gathered enough new data or due to having no communication with the server for too long. We categorize these layers in the CommLayers and synchronize all the clients with the server.
6.2 Performance Analysis
Theorem 6.1. For any 0 < 8 L, we run Algorithm with D = Te To To
d with probability at least 1 - 5, the regret of the algorithm is bounded RT O(VdMT..) where T, is the total per-client arm pulls. Moreover, the corresponding communication cost is bounded by O(y M3 log d).
Remark 4. Theorem 6. demonstrates Sync-FedSupLinnUCB also achieves the minimax regret lower bound while the communication cost is independent of Te. It is particularly beneficial for large T.. Especially, the number of total rounds in the synchronous scenario asynchronous setting, we have = ΣM1 T; rounds.
MT,, while in the
Communication cost analysis of Sync-FedSupLinUCe We sketch the proof for the communi- cation cost bound in Theorem 6. below, while deferring the detailed proofs for the regret and the communication cost to Appendix D
7

---

Algorithm 4 Sync-FedSupLinuce
Initialization: Te. S. [log d). lisst V,Vs E [0: S). CommLayers 0.
2: [Ager t Ia. beer +- 0 0|ss s |0: S]]
> Server initialization
3: {A, 6 Ia. AA by. Ab;, 0 -O|sEl [0: s) [M
Clients initialization
4: fort=1,2
_Tc do
5:
for iori= 1,2, .M do
6:
Client it = i is active, and observes K contexts (01,11 :
7:
+ S-LCB (client -i,2 xx,xx)
if (t Murt) log det( (et(A)AAA)) D then
8:
del(4])
9:
Add to CommLayers
10: end if
end for
12: end for
13: for s E CommLayers do
14: Sync(s, server, clients [M]); Hast +- t, CommLayers 0
15: end for
We call the chunk of consecutive rounds without communicating information in layer (except the last round) an epoch. Information layer is collected locally by each client and synchronized at the end of the epoch, following which the next epoch starts. Denoted by A the synchronized gram matrix at the end of the p-th epoch. For any value >> O, there are at most
I epochs 8
that contain more than 3 rounds by pigeonhole principle. If the p-th epoch contains less than
det( (Ay))) det( Ael!
rounds, then log
D based on the communication criterion and the fact that
B
p1 log det (Agi) det (pp1..)
Ep rounds fewer than 3 is at most O(T R,
< R. = (dd log (T.)) (see Equation (6)) The number of epochs containing
1). Noting that D log(T.)) the total number of epochs
p/B
d
for layer is at most Te 1 2 O TT
M) by taking @
DT.
The total
R,
communication cost is thus upper bounded by O(SM (log
Extensions of FedSupLinUCB
In this section, we extend the FedSupLinUCB algorithm to address two distinct settings in federated systems: scenarios characterized by heterogeneous variances, and those affected by adversarial corruptions.
7.1 Federated Heteroscedastic Linear Bandits
We have far focused the federated linear bandits with section, we adapt Pennc-PedSupLinnCC to the case where the reward noises have heterogeneous variances, which extends the heleroscedastic linear bandits studied in Zhou et al. (2021): Zhou and Gu (0022) to the asynchronous federated setting, where one client is active at time. Specifically, the reward noises {er (er)et are independent with |er < R, Elee] 0 and B[e?] S of where a, is known to the active client.
reward noises. In this
We propose variance-adaptin Asyc-FedSupLinUCe and analyze its regret and the communication cost in the theorem below, with the algorithm and the proof details Appendix E due to space constraint. The regret is significantly less than that of the Async-FedSupL.e when the variances {a?) are small.
Theorem 7.1. For any 0 < 8 < 1, we run the variance-adaptivs Asyne- FedSupLinUCh algorithm in Appendix with = 1/M2, with probability at least 8, the regret is bounded as R S d
Ōly d 1 of), and the communication cost is bounded by O log2 T).

---

7.2 Federated Linear Bandits with Corruption
We further explore asynchronous federated linear bandits with adversarial corruptions, where an adversary inserts corruption C₁ to the reward of the active client round t. The total commuption bounded by > l < Cp. We incorporate the idea of linear bandits with adversarial corruption studied in He et al. (2022b) to the proposed FedSupLinUCB framework and propose the Robust Async-FedSupl. FedSupLinUCE algorithm, with details in Appendix [F] Robust Ponyn--FdSupL.nnCcc can achieve the optimal minimax regret (matching the lower bound in He et al. (2022b)) while incurring a low communication cost.
Theorem 7.2. For any 0 < 1, if we run the Robust Async-FedSupLindGG algorithm in Appendix F with C 1/M2, with probability at least - 6, the regret is bounded as Ry S Ó(VaT + dCp), and the communication cost is bounded by (d log dlog T).
8 Experiments
We have experimentally evaluated FedSupLinUCB in the asynchronous and synchronous settings on both synthetic and real-world datasets. We report the results in this section.
8.1 Experiment Results Using Synthetic Dataset
We simulate the federated linear bandits environment specified in Section 3 With = 40000, M = 20, d 25, A 20, contexts are uniformly randomly sampled from l2 unit sphere, and reward rt,o = 8 It.a + Ct, where & is Gaussian distributed with zero mean and variance o = 0.01. It should be noted that while M clients participate in each round in the synchronous scenario, only one client is active the asynchronous case. the plots, the r-axis coordinate denotes the number of arm pulls, which flattens the actions in the synchronous setting.
(a) Regret: arrival pallerns.
(b)
Communicatiin:
arrival pul- (c) Regret: client numbers.
(d)
Regret vs communications.
tems
Figure 1: Experimental results with the synthetic dataset.
Arrival pattern. We first investigate the impact of different arrival patterns (the sequence of activating clients): (1) Random, which randomly allocates T/M arm pulls in [T] for each client. (2) Round-robin, i.e. 2,. ...., M, 1, 2, 3, M, .... (3) Click-leave, i.e. M,, M,.... The regret and the communication cost of these three arrival patterns in the synthetic experiment are reported in Figure [(a] and Figure [bb] respectively. We note that although the upper bound analysis in our proof is for the worst-case instance, the numerical results suggest that different arrival patterns result in diverse regret performances. Round-robin and random patterns are more challenging since both local bandit learning and each client's policy updates happen relatively slowly. The click-leave pattern, which is the closest to the centralized setting, achieves the best regret. In addition, compared with achieves better cumulative regrets with a higher communication cost.
1,, 2, ........
Sync- Fenn-FeeSupLnnCc
Amount of clients. The per-client cumulative regret as function of T. T/M with dif- ferent amounts of clients is plotted in Figure [(c) In comparison to the baseline SupLinUCB, FedSupLinUCB algorithms achieve better regret via communication between clients and the server. We can see from the experiment that FedSupLinUCB significantly reduces the per-client regret com- pared with SupLinnCCB and achieves a better regret as M increases in both asynchronous and synchronous settings.

---

Trade-off between regrets and communications. evaluate the tradeoff between communication and regret by running FedSupLinUCB with different communication threshold values and D in asynchronous and synchronous settings respectively. The results are reported in Figure l(d) where each scattered dot represents the communication cost and the cumulative regret that FedSupLinUCB has achieved with a given threshold value at round T = 40000. We see clear tradeoff between the regret and the communication. More importantl, Sync-FedSupLinCCB achieves a better tradeoff' than Asyne-FedSupL.nnUG.
8.2 Experiment Results Using Real-world Dataset
We further investigate how efficiently the federated linear bandits algorithm performs in a more realistic and difficult environment. We have carried out experiments utilizing the real-world recom- mendation dataset MovielLens 20M (Harper and Konstan 2015). Following the steps in [i and Wang (2022b), we first filter the data by maintaining users with above 2500 movie ratings and treating rating points greater than as positive, ending up with interactions. Then, we follow the process described in [esa-Bianch et al. (2013) to generate the contexts set, using the TF-IDF feature = 25 and the arm set K = 20. plot the per-client normalized rewards of the FedSupLinUCBB algorithm with different client numbers M in synchronous and asynchronous cases respectively. Note that the per-client cumulative rewards here are normalized by random strategy. From Figure 2(a) and Figure 2(b] asynchronous experiments, FedSupLinUCB has better rewards than SupLinUCB, and the advantage becomes more significant the number of users increases.
37 users and 121934 total movie rating
that in both synchronous and
2.0
Noma tendtttddde reaard
3.8
Susi sgync
14
syn
2009
5000
(a) Async-Feddie FeC...
(b) Sync-FadSupLinlCCa
Figure 2: Experimental results with the real- world MovieLens dataset.
9 Conclusion
We studied federated linear bandits with finite adversarial actions, a model that has not been investi- gated before. We proposed FedSupLinUCB that extends the SupLinUCB and OFUL principles to the federated setting both asynchronous and synchronous scenarios, and analyzed their regret and communication cost, respectively. The theoretical results proved that FedSupLinUCh is capable of approaching the minimal regret lower bound (up to polylog terms) while only incurring sublinear communication costs, suggesting that it is the finite actions that fundamentally determines the regret behavior in the federated linear bandits setting. Furthermore, we examined the extensions of the algorithm design the arriace-aadaptive and adversarial corruption scenarios.
Acknowledgments and Disclosure of Funding
The work of LF and CS was supported in part by the U.S. National Science Foundation (NSF) under grants 2143559, 2029978, and 2132700.
10

---

References
Abbasi- Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24.
Auer, P. (2002). Using confidence bounds for exploitation-exxplrraiin trade-offs. Journal Machine Learning Research, 3(Nov):397-422.
Cesa- Dasa-Bianchi, N., Gentile, C., and Zappella, G. (2013). A gang of bandits. Advances in neural information processing systems, 26.
Chu, W., Li, L., Reyzin, L.,, and Schapire, R. (201 Contextual bandits with linear payoff functions. In Proceedings of the Fourleenth International Conference Artificial Intelligence and Statistics, pages 208-214. JMLR Workshop and Conference Proceedings.
Dani, V., Hayes, T. P., and Kakade, S. M. (2008). Stochastic linear optimization under bandit feedback. 21 Annual Conference on Learning Theory, pages 355-366.
Dubey, A. and Pentland, A. (2020). Differentially-private federated linear bandits. Advances in Neural Information Processing Systems, 33:6003-6014,
Han, Y., Zhou, Z., Zhou, Z., Blanchet, J., Glynn, P. W., and Ye. Y. (2020). Sequential batch learning linear contextual bandits. arXiv preprint arXiv:2004.06321.
in
Harper, F. M. and Konstan, J. A. (2015). The MovieLens datasets: History and context. ACM Trans. Interact. Intell. Syst. 5-4):1-19.
He, J., Wang, T., Min, Y., and Gu, Q. (2022a). A simple and provably efficient algorithm for asynchronous federated contextual linear bandits. arXiv preprint arXiv:2207.03 0006
He, J., Zhou, D., Zhang, T., and Gu, Q. (2022b). Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. Advances in neural information processing systems.
Huang. R., Wu, W. Yang. J., and Shen, C. (2021). Federated linear contextual bandits. Advances in Neural Information Processing Systems, 34:27057-27068.
Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
Li, C. and Wang. H. (2022a). Asynchronous upper confidence bound algorithms for federated linear bandits. International Conference on Artificial Intelligence and Statistics, pages 6529-6553. PMLR.
Li, C. and Wang, H. (2022b). Communication efficient federated learning for generalized linear bandits. arXiv preprint arXiv:2202.01087.
Li, L., Chu, W., Langford, J., and Schapire, R. E. (2010). A contextual -ondextual-bandit approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670.
Li, T., Song, L., and Fragouli, C. (2020). Federated recommendation system via differential privacy. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2592-2597. IEBE.
Li, Y., Wang, Y., and Zhou, Y. (2019). Nearly minimax-optimal regret for linearly parameterized bandits. In Conference Learning Theory, pages
PMLR.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. (2017). Communication- efficient learning of deep networks from decentralized data. In Proc. AISTATS, pages 1273-1282, Fort Lauderdale, FL, USA.
Ruan, Y., Yang. J., and Zhou, Y. (2021). Linear bandits with limited adaptivity and learning distributional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 87.
Salgia, S. and Zhao, Q (2023). Distributed linear bandits under communication constraints. In International Conference Machine Learning, pages 29845-29875. PMLR.

---

Shi, C., Shen, C., and Yang, J. (2021). Federated multi- armed bandits with personalization. In International Conference on Artificial Intelligence and Statistics, pages 2917-2925, PMLR.
Wang, Y., Hu, J., Chen, X., and Wang, L. (2019). Distributed bandit learning: Near-optimal regret with efficient communication. In International Conference on Learning Representations.
Zhou, D. and Gu, Q. (2022). Computationally efficient horizon-free reinforcement learning for linear mixture mdps. arXiv preprint 2rxiv:2205.11500
Zhou, D., Gu, Q. and Szepesvari, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576. PMLR.
12


Reviews:
[{"review_id": "KCLkpldAOQ", "reviewer": "Reviewer_5B2X", "summary": "This paper addresses the linear bandits problem in the context of federated learning. It proposes a general algorithm called FedSupLinUCB that solves a linear contextual bandit problem with finite adversarial action sets that may vary across clients. The paper also considers practical challenges in federated settings such as synchrony, communication efficiency, and time-evolving scenarios.", "questions": "- What are the specific challenges in the federated linear bandit problem? Federated learning was originally proposed to address data-sharing issues. Does the federated linear bandit problem face similar challenges related to system efficiency and heterogeneity?\n- What unique solutions or methods does the paper contribute? It appears that some challenges have already been addressed by previous works.", "limitations": "No limitations are discussed in the main paper.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper explores the linear contextual bandit problem with finite adversarial action sets in the federated learning setting. Additionally, it addresses several practical challenges in federated settings, such as synchrony, communication efficiency, and time-evolving scenarios.", "weaknesses": "Background and challenge:\n\n- The introduction and preliminaries do not provide a detailed definition of the time-evolving and adversarial arm. To improve comprehension, it would be helpful to explain the impact of these factors on the federated linear bandit problem.\n- Although the paper discusses the main challenges of federated linear bandits, it should emphasize the key differences from traditional linear bandit problems, such as single-player bandits or distributed bandits.\n- The paper lacks strong motivation due to the vague background and challenge.\n\nNovelty:\n\n- The main theoretical contributions of the paper extend previous work on linear bandit problems to the federated setting. For example, FedSumLinUCB is an extension of SupLinUCB and OFUL. Robust Async-FedSupLinUCB incorporates ideas from He et al. (2020b).\n- The theory and methodology employed in the paper appear to be borrowed from the literature.\n\nExperiment setting:\n\n- The reward function utilized in the experiments, where $r_{t, a}=\\theta^{\\top} x_{t, a}+\\epsilon_t$ , does not align with the settings described in the paper. To my knowledge, it is more general to let the reward function different across clients with certain variances according to the environments.\n- The experiments conducted in the paper are limited. Only a classic algorithm proposed in 2011 by Chu et al. is used as a baseline, and not all proposed algorithms are fully evaluated.\n\nWriting:\n\n- It is unusual for a conference paper to have 10 sections.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the interesting questions regarding the proposed FedSupLinUCB algorithm.\n\n**Q1**: \"The introduction and preliminaries do not provide a detailed definition of the time-evolving and adversarial arm. To improve comprehension, it would be helpful to explain the impact of these factors on the federated linear bandit problem.\"\n\n**Response**: We appreciate the reviewer's attention to the setting of the contexts set. In Section 3.1 (line 110), we have provided a clear definition of the time-evolving context sets, indicating that the context sets change over time and are different among clients. The inclusion of both finite and adversarial context sets in our problem formulation presents a more challenging scenario compared to the Fed-PE algorithm, which specifically handles finite and fixed contexts. For that situation, techniques like G-optimal design are applicable, though do not apply in our formulation. To address the challenges posed by time-evolving contexts, we have introduced the FedSupLinUCB framework. We will highlight the distinctiveness when presenting the results and comparisons.\n\n**Q2**: \"Although the paper discusses the main challenges of federated linear bandits, it should emphasize the key differences from traditional linear bandit problems, such as single-player bandits or distributed bandits.\"\n\n**Response**: In our study, we concentrate on a federated linear bandit model. In comparison to single-player bandit and distributed bandit approaches, we leverage the benefit of data sharing through communication between the clients and the central server. Our main focus is on achieving optimal regret while keeping communication costs low. Specifically, in our model, we consider a star-shaped structure, where M clients interact with a central server to expedite the decision-making process. Additionally, we highlight the benefits of the federated linear bandit framework in the remarks following the theorem in our paper. \n\nIt's worth noting that there does not appear to be a clean separation between \"distributed bandits\" and \"federated bandits\". Nevertheless, we contend that the \"federated bandits\" setting enables a more comprehensive modeling of the communication and computation, and can be viewed as focusing more on the impact of different communication and computation modes, which is indeed the perspective we take in this work.\n\n**Q3**: \"The paper lacks strong motivation due to the vague background and challenge.\"\n\n**Response**: Linear bandits with adversarial and finite actions find numerous applications, including recommendation systems [R1]. The distributed nature of these applications naturally aligns with the setting we have studied in this paper, as we have also mentioned in the introduction section of our paper.\n \n**Q4**: \"The main theoretical contributions of the paper extend previous work on linear bandit problems to the federated setting...The theory and methodology employed in the paper appear to be borrowed from the literature.\"\n \n**Response**: Similar to most of the previous works on federated bandits, whose technical aspects resemble the counterparts of single-player bandits, we also utilize techniques in single-player bandits as analysis tools for this specific federated linear bandit problem. However, we believe that the study of the federated bandit problem is important and valuable, particularly due to the recent trend of invoking more edge computing resources. To address the specific challenges in the federated setting, we proposed the FedSupLinUCB framework, where the Async-FedSupLinUCB and Sync-FedSupLinUCB both achieve near-optimal regrets while significantly reducing communication costs.\n\n**Q5**: \"The reward function utilized in the experiments, where $r_{t,a_t} = \\theta^{\\top} x_{t,a_t}^i + \\epsilon_t$, does not align with the settings described in the paper. The experiments conducted in the paper are limited...\"\n \n**Response**: We conducted our experiment to elaborate on the theoretical analysis and indeed aligned it with the problem formulation presented in Section 3.1. We made the assumption that all clients share the same underlying parameter $\\theta$. This assumption allows us to leverage the sharing of information among clients, thereby benefiting the decision-making process of each individual client, and this is the fundamental reason that federated learning is able to gain performance improvement over learning by individual agents. Considering our assumptions regarding finite and adversarial context sets, we conduct a comparison with the order-optimal benchmark, SupLinUCB, to showcase the advantages of our federated framework.\n\n**Q6**: \"What are the specific challenges in the federated linear bandit problem? Federated learning was originally proposed to address data-sharing issues. Does the federated linear bandit problem face similar challenges related to system efficiency and heterogeneity? What unique solutions or methods does the paper contribute? It appears that some challenges have already been addressed by previous works.\"\n\n**Response**: The major technical challenges (also for almost all the federated bandits works) are to incorporate the techniques in the single-player algorithms into the federated scenario while explicitly considering the impact of communication cost. Yet the focus on the communication cost under different update and computation modes led us to the proposed new algorithms in this work. We believe the study of such federated contextual bandits problem is important and valuable, and the proposed algorithms and their analysis advance our understanding and provide insights into the problem in terms of maintaining the near-optimal regret while significantly mitigating the communication costs.\n\n[R1] Ruan, Yufei, Jiaqi Yang, and Yuan Zhou. ”Linear bandits with limited adaptivity and learning distributional optimal design.” Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021."}, {"review_id": "Snnx1Akwli", "reviewer": "Reviewer_xbXb", "summary": "In this work, the authors consider the problem of Federated linear bandits with finite adversarial actions. This is the first time investigating a setting where federated clients are faced with a set of actions to choose from that changes over time in an oblivious adversarial manner, and the authors of this paper do so for  both synchronous and asynchronous versions of the problem.\nTo handle this problem, the authors propose two algorithms that are based on SupLinUCB (Chen et al. 2011), which is a standard approach for linear bandits and adapted to federated bandits. Then, they combine this S-LUCB approach with two different protocols to tackle both the asynchronous and the synchronous version of the problem.One of the challenges of federated learning comes with the cost of the communication between the clients and the server. \nIn the asynchronous setting, only one client is active at the time and the the synchronization rate depends on each individual client. For this problem, the authors prove that the proposed algorithm achieves an order optimal (up to log factors) high probability bound of order $O(\\sqrt{dT})$ while ensuring that their total communication cost is logarithmic in T. \nIn the synchronous case, layers of clients work simultaneously which allows for the server to take advantage of the various information provided by the clients. This means that these clients don't just synchronize when the information that they have has changed, but they also do so periodically to ensure that their information is up to date. This extra information provided by the  server to the clients allows to actually lower the total number of communications and obtain a $\\tilde O(\\sqrt{dMT_c})$ regret bound while keeping a time independent bound on the number of communication.\n\nThe authors provide detailed proofs of their results in the appendices and experiments, both on generated and real life datasets to highlight how the regret and the communication costs evolve in terms of arrival patterns and number of clients.\n\n\n", "questions": "The problems studied in federated learning are very close to these of multiplayer multiarmed bandits. Have you thought of whether there are results that could bridge the two settings?\n\n", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This works studies a new variant of the federated linear bandits problem where the clients are facing finite adversarial arm sets instead of either finite fixed armed sets or infinite arm sets. \nTo do so, they build upon existing algorithms for linear bandits with an adversarial arm set, SupLinUCB (Chu et al. 2011) and for asyncronous federated learning FedLinUCB (He et al. 2022a). The novelty of their approach mainly resides in the improved communication protocol, in particular in the synchronous setting, where they take advantage of a layer structure to limit the communication cost while still synchronizing regularly. \nIn both the asynchronous and the synchronous settings, they recover the regret of  SupLinUCB in the single player setting (Chu et al. 2011), and are within a log T factor of the state of the art results for federated synchronous and asynchronous learning, both in terms of regret and communication costs. \n\nOverall, this is a well presented paper that provides some interesting results for a new variation of the federated learning problem, which might be more relevant in practice, which is reinforced by the fact that they also run experiments on real worlds datasets.\nPresenting results for the corrupted setting is also a nice generalization of their results.\n", "weaknesses": "In the experiments section, it would be interesting to see the proposed algorithms compared with other results for federated learning: The results in Appendix H are promising and could benefit from being extended. \nIt  would also be nice if the legends on the plot could be larger so it is a bit easier to read.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate that the reviewer liked our federated linear bandit model, as well as for providing a thoughtful summary of our paper.\n\n**Q1**: \"In the experiments section, it would be interesting to see the proposed algorithms compared with other results for federated learning...\"\n\n**Response**: We thank the reviewer for the suggestion. In the main paper, we proposed algorithms that provably achieve nearly minimax optimal regret while maintaining a small amount of communication cost. In the experiments section, we aim to have a better interpretation of the proposed algorithms by empirically studying the impact of the arrival pattern, the number of clients, and the trade-off between regrets and communication costs. In other words, gaining intuition and bringing the interpretation of the proposed algorithm is our goal in the setup of the experiments. \nTo this end, we did not conduct the experiments for other existing algorithms, which as far as we know are not minimax optimal in our setting.\n\n**Q2**: \"The problems studied in federated learning are very close to these of multiplayer multiarmed bandits. Have you thought of whether there are results that could bridge the two settings?\"\n\n**Response**: A majority of the multiplayer multi-armed bandits settings focus on handling the collision caused by multiple players pulling the same arm, while in the federated bandits settings, the multiple players communicate with a central server to better solve their own local decision-making problem by the information acquired from other players. We thank the reviewer for the insightful observation regarding the existing research in the domain of multi-player and multi-armed bandit problems, we are not aware of any work combining the study of the communication costs and the collisions. "}, {"review_id": "wYBrc0lBNB", "reviewer": "Reviewer_EJUn", "summary": "This paper studies a federated linear bandits model, where M clients communicate with a central server to solve a linear contextual bandits problem with finite adversarial action sets and proposes the FedSupLinUCB algorithm, which extends the SupLinUCB and OFUL principles in linear contextual bandits. Both asynchronous and synchronous cases are considered. Experiment results corroborate the theoretical analysis and demonstrate the effectiveness of FedSupLinUCB on both synthetic and real-world datasets.\n\n", "questions": "1. Do the adversarial corruption actios only exist in the setting of asynchronous case? \n2. Are there differences in intensity for adversarial actions? If so, do different intensities have different effects on the experimental scene? \n3. Is Robust Async-FedSupLinUCB a general robust method or can only be used against a specific adversarial setting？", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method description, theoretical derivation and complexity analysis of the article are very detailed and well organized.\n\n\n", "weaknesses": "See Questions part.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the interesting questions regarding the proposed FedSupLinUCB algorithm. \n\n**Q1**: \"Do the adversarial corruption actions only exist in the setting of the asynchronous case?\"\n\n**Response**: The asynchronous case contains the synchronous case as a special case. We thus designed the robust async-FedSupLinUCB algorithm that handles the adversarial corrupted actions in this general asynchronous case, which thus can be directly applied to the synchronous case. Note that in the study without corruption, we treat the synchronous setting separately and designed a more communication-efficient scheme without time horizon dependence.\n\n**Q2**: \"Are there differences in intensity for adversarial actions? If so, do different intensities have different effects on the experimental scene?\"\n\n**Response**: We measure the total intensity of the adversarial actions by $C_p$ as shown in Lines 281-283, and its impact on the regret is represented by an additional additive term of $d C_p$ in Theorem 8.1. Please correct us if your remark is misunderstood by us. We have made a general assumption on the context set, considering it to be both finite and adversarial. This assumption enhances the practicality of our algorithm, making it applicable to a wide range of real-world scenarios.\n\n**Q3**: \"Is Robust Async-FedSupLinUCB a general robust method or can only be used against a specific adversarial setting?\"\n\n**Response**: Robust Async-FedSupLinUCB is a general robust method that is capable of handling any additive corruption on the reward function, as long as the total corruption budget is constrained."}, {"review_id": "jaoqTb9ZTY", "reviewer": "Reviewer_64z5", "summary": "This paper studies the linear contextual bandits problem with federated learning of $M$ clients communicating with a central sever. In particular, the paper assumes adversarial finite action, and considers two cases of the communication: asynchronous and synchronous. \n\nFollowing the idea of OFUL, this work extends the previous SupLinUCB in linear contextual bandits to deal with the federated learning scenario, and proposes the algoirthm FedSupLinUCB which achieves $\\widetilde{O}(\\sqrt{dT})$ where $T$ is the total number of pulls (the summation of cumulative pulls over $M$ clients together), and $d$ is the dimension. More importantly, this result is attained with limited communication cost $\\mathcal{O}(\\sqrt{d^3M^3}\\log(d))$ for synchronous case, and $\\mathcal{O}(dM^2\\log(d)\\log(T))$ for asynchronous case. \n\nIn addition, the FedSupLinUCB further extends to the variance-adaptive and adversarial corruption scenarios. ", "questions": "1. Any lower bound of the communication cost in the synchronous case or the asynchronous case? \n2. Any idea to improve the regret bounds to the optimal regret bound $\\mathcal{O}(\\sqrt{dT\\log T})$, which can be obtained by Fed-PE? \n\n", "limitations": "This work is pure theoretical, and does not have any negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is clearly-written and well-organized. The notations are well-defined and the meanings are explained clearly prior to their usages.  \n\n1. Combining online learning and federated learning is an interesting direction. The proposed algorithm attains the optimal regret bound of such problem up to some $\\log T$ factors, and further ensures limited communication cost, which could be dominating in the distributed systems. Among these results, the most interesting one is that for the synchronous case, which is independent with the horizon $T$. \n\n2. The instance-dependent regret bounds for the variance-adaptive and adversarial corruption scenarios are also very interesting. The worst case regret bound is not meaningful in most real world applications. \n", "weaknesses": "This paper does not have any specific weakness. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the clear summary and for finding our paper interesting. Please see our response below with respect to your specific comments.\n\n**Q1**: \"Any lower bound of the communication cost in the synchronous case or the asynchronous case?\"\n\n**Response**: There are some most recent works, which appeared after the submission of our manuscript, focusing on analyzing the communication cost complexity in federated bandit problems. E.g., in [R2], the communication cost is measured in bits in the federated linear bandits setting with a simple unit ball action. \n\n**Q2**: \"Any idea to improve the regret bounds to the optimal regret bound $O(\\sqrt{dT\\log(T)})$, which can be obtained by Fed-PE?\"\n\n**Response**: It is important to note that our study differs from Fed-PE, which primarily focuses on finite and fixed context sets. In contrast, we address a finite and time-evolving context setting, presenting new challenges. As such, the G-optimal design method utilized in Fed-PE is not applicable to our context. To the best of our knowledge, our regret is order-optimal in this scenario.\n\n[R2] Salgia, Sudeep, and Qing Zhao. \"Distributed linear bandits under communication constraints.\" International Conference on Machine Learning. PMLR, 2023.\n"}]

Author rebuttal:

Meta-review: This paper studies the problem of Federated linear bandits with finite adversarial actions. They adapt the classical SupLinUCB algorithm to work in the federated learning setup.

There is a general consensus among reviewers that this is a correct and solid work, however, the overall novelty is limited (contribution score between 2 and 3). The main strength mentioned is that the regret bounds are close to optimal, but neither the algorithm nor the analysis are seen as being especially challenging.
Additionally, this work provides several minor contributions such as the variance-adaptive and the corruption setting.
Overall, this paper is a complete package with several contributions, though none of its own of high impact. Three of four reviewers see this above the acceptance threshold. 
The final reviewer is expressing a concern that the studied setting misses subtleties of the original federated learning framework and is more closely related to distributed bandits. However, there is a long record of FL work that uses the assumptions of this paper.
Decision: Accept (poster)