Harnessing the Power of Federated Learning in Federated Contextual Bandits
Authors: Chengshuai Shi
Ruida Zhou
Kun Yang
Cong Shen
Venue: Accepted by TMLR ()

Abstract: Federated learning (FL) has demonstrated great potential in revolutionizing distributed machine learning, and tremendous efforts have been made to extend it beyond the original focus on supervised learning. Among many directions, federated contextual bandits (FCB), a pivotal integration of FL and sequential decision-making, has garnered significant attention in recent years. Despite substantial progress, existing FCB approaches have largely employed their tailored FL components, often deviating from the canonical FL framework. Consequently, even renowned algorithms like FedAvg remain under-utilized in FCB, let alone other FL advancements. Motivated by this disconnection, this work takes one step towards building a tighter relationship between the canonical FL study and the investigations on FCB. In particular, a novel FCB design, termed FedIGW, is proposed to leverage a regression-based CB algorithm, i.e., inverse gap weighting. Compared with existing FCB approaches, the proposed FedIGW design can better harness the entire spectrum of FL innovations, which is concretely reflected as (1) flexible incorporation of (both existing and forthcoming) FL protocols; (2) modularized plug-in of FL analyses in performance guarantees; (3) seamless integration of FL appendages (such as personalization, robustness, and privacy). We substantiate these claims through rigorous theoretical analyses and empirical evaluations.

Published in Transactions on Machine Learning Research (07/2024)
Harnessing the Power of Federated Learning in Federated Contextual Bandits
Chengshuai Shi
es cs7ymc@@vinginia.edu
Deportment of Electrical and Computer Engineering University of Virginia
Ruida Zhou
ruida &g. ucla edu
Department Electrical and Computer Engineering University of California, Los Angeles
Kun Yang
kySto@virginia. edu
Department of Electrical and Computer Engineering University of Virginia
Cong Shen
Coiggvirginia.c edu
Department of Electrical and Computer Engineering Universily of Virginia
Reviewed on OpenReview: https: // openreview. net/ form?? id= 28wcREe9qV
Abstract
Federated learning (FL) has demonstrated great potential in revolutionizing distributed ma- chine learning, and tremendous efforts have been made extend it beyond the original focus on supervised learning. Among many directions, federated contextual bandits (FCB), a piv- otal integration of FL and sequential decision-make making, has garnered significant attention in recent years. Despite substantial progress, existing FCB approaches have largely employed their tailored FL components, often deviating from the canonical FI. framework. Conse- quently, even renowned algorithms like FedAvg remain under-utilized in FCB, let alone other FL advancements. Motivated by this disconnection, this work takes one step towards build- ing tighter relationship between the canonical FL study and the investigations on FCB. In particular, & novel FCB design, termed FedIGW, is proposed to leverage a regression-basee based CB algorithm, i.e, inverse gap weighting. Compared with existing FCB approaches, the proposed FedIGW design can better harness the entire spectrum of FL innovations, which is concretely reflected as (1) flexible incorporation of (both existing and forthcoming) FL protocols; (2) modularized plug-in of FL analyses in performance guarantees; (3) seam- less integration FL appendages (such as personalization, robustness, and privacy). We substantiate these claims through rigorous theoretical analyses and empirical evaluations.
1 Introduction
Federated learning (FL), initially proposed by McMahan al. (017 Konečný et al. (2016). has garnered significant attention for its effectiveness in enabling distributed machine learning with heterogeneous agents (Li et al.] 2020a Kairouz et al.) 2021). As FL has gained popularity, numerous endcavors have sought to exlend its applicability beyond the original realm of supervised learning, e.g., to unsupervised and semi- supervised learning ZZhang et al. 2020 van Berlo et al. 2020 Zhuang et al. 2022 Lubana et al., 2022) Among these directions, the exploration of federated contextual bandits (FCB) has emerged as a particularly compelling area of research, representing pivotal fusion of FL and sequential Decision-making which has found various practical applications in cognitive radio and recommendation systems, among others.

---

Published in Transactions on Machine Learning Research (07/2024)
Over the past several years, substantial progress has been made in the field of FCB (Wang et al. 2019
Li & Wang; 2022b Li et al. 2022; 2023: Dai et al.) 2023), particularly those involving varying function
approximations (e.g., linear models, as discussed in Huang et al. (2021b): Dubey & Pentland (2020); Li &
Wang (2022a) : He ct al. )0022;; Amani et al. (2022 ;: Fan et al. (022)) ). Despite their different focuses, it
can be observed that these existing designs all employ cerlain FL components to enable the participating
agents to collaboratively update their CB parameterization via locally collected interaction data.
However, these FL components adopted in the previous FCB works are often over-simplified. In particular, the canonical FL framework (traced back to the celebrated FedArg algorithm (McMahan et al. 2017) typically takes an optimization view of incorporating the local data through multi-round aggregation of model porameters (such as gradients). In contrast, the FL protocol in many existing FCB works is one-shol aggregation of some compressed local data per epoch (e.g., combining local estimates and local covariance matrices in the study of federated linear bandits). Admittedly, for some simple cases, such straightforward aggregation is sufficient and allows problem-specific finctuning for tight performance bounds. However, such a deviation from the canonical FL studies prohibits existing FCB designs from leveraging the vast. FL, advances, and thus largely limits the connection between FL and FCB.
Motivated by this disconnection, this work, instead of pursuing tighter performance bounds, aims to utilize the canonical FL. framework as the FL component of FCB to harness the full power of FL studies in FCB. We propose FedIGW - an exploring design that demonstrates the ability to leverage a comprehensive array of FL advancements, encompassing canonical algorithmic approaches (like FedAvg (MeMahan et al. 2017 7 and SCAFFOLD (Karimireddy et al.) 2020)), rigorous convergence analyses, and critical appendages (such as personalization, robustness, and privacy). To the best of our knowledge, this is the first paper that explicitly focuses on the close connection between FL and FCB, which we hope can inspire a new line of FCB studies. The distinctive contributions of FedIGW can be succinetly summarized as follows:
Flexible incorporation of FL protocols. In the FCB setting with stochastic contexts and a realizable reward function, FedIGW employs the inverse gap weighting (IGW) algorithm for CB while versatile FL protocols can be incorporated (e-g- FedAvg and SCAFFOL.D), provided they can solve a standard FT, problem. These two parts iterate according to designed epochs: FL, drawing from previously gathered interaction data, supplies estimated reward functions for the forthcoming IGW intcractions. A pivotal advantage is that the flexible FL component in FedIGW provides substantial adaplability, meaning that existing and future FL protocols can be seamlessly leveraged. Experimental results using real-world data with several different FL choices corroborate the practicability and flexibility of FedIGW.
Modularized plug-in of FL analyses. A general theoretical analysis of FedIGW is developed to demonstrate its provably efficient performance. The influence of the adopted FL protocol is captured through its optimization error, delineating the excess risk of the learned reward function. Notably, any theoretical breakthroughs in FL convergence rates can be immediately integrated into the obtained analysis framework and supply the corresponding guarantees of FedIGW. Concretized results are further provided through the utilization of FedAvg and SCAFFOLD in FedIGW.
Seamless integration of FL appendages. Beyond its inherent generality and efficiency, FedIGW exhibits exceptional extensibility. Various appendages from FL studies can be flexibly integrated without necessitating alterations to the CB component. We explore the extension of FedIGW to personalized lcarning and the incorporation of privacy and robustness guarantees. Similar investigations in prior FCB works would entail substantial algorithmic modifications, while FedIGW can effortlessly leverage corresponding FL advancements to obtain these appcaling attributes.
Key related works. Most of the previous studies on FCB are discussed in Sec. 2.2 and more comprehen- sively reviewed in Appendix B We note that these FCB designs with tailored FL protocols in previous works sometimes can achieve near-optimal performance bounds in specific settings, while our proposed FedIGW is more practical and extendable. We believe these two types of designs are valuable supplements to each other. A high-level comparison between the proposed FedIGW and existing FCB designs is listed in Table T
Here we particularly note a recent paper (Agarwal et al. 2023 that is closely related to this work. It also proposes to decouple the FL components in FCB by leveraging regression segression-based CB designs. However, Agar-
2

---

Published in Transactions on Machine Learning Research (07/2024)
Table 1: A comparison between existing FCB designs and the proposed FedIGW.
Existing FCB designs
FedIGW
Leverage versatile FL protocols, such as FodAvg and SCAFFOLD
FL components
Develop tailored FL protocols
Analyse tailored FL protocols for the focused instance
Plugin FL convergence rates in a modularized fashion Integrate corresponding FL advances directly
Theoretical guarantees
Extensions (c.g., personalization, robustness, privacy)
Require further tailored protocols
wal et al. 2023 mainly focuses on empirical investigations, while our work offers valuable complementary contributions by conducting thorough thcoretical analyses (sce Sec. 4 building modularized connection
between theoretical studies in FL and FCB. Moreover, experiments reported in Sec. 5 provide empirical
results on two datasets that are different than Agarwal et al. [2023]. offering additional practical insights.
2
Federated Contextual Bandits
This section introduces federated contextual bandits (FCB). A concise formulation is first provided. Then, the existing works are re-visited with a focus on revealing the disconnection between FL and FCB.
2.1 Problem Formulation
Agents. In the FCB setting, a lotal of M agents simultaneously participate in solving contextual bandit (CB) problem. For generality, we consider an asynchronous system: each of the M agents has a clock indicating her time step, which is denoted as fm = 1, 2, ... for agent m. For convenience, we also introduce a global time step t. Denote by (t) the agent m's local time step when the global time is t, and t(tm, m) the global time step when the agent m's local time lm-
Agent m each of her local time step fm 1,2, observes a context Tmtt.. selects an action am from action set Am,m. and then receives the associated reward mm.t.. (Am.tm) (possibly depends on both mm,
and (m,t...) as in the standard CB [Tattimore & Szepesvári 2020 Each agent's goal is to collect as many rewards as possible given a time horizon.
Federation. While many efficient single-agent (centralized) algorithms have been proposed for CB (Latti- more & Szepesvári 2020), FCB targets building federation among agents to perform collaborative learning such that the performance can be improved from lcarning independently. Espocially, common interests shared among agents motivade their collaboration. Thus, FCB studies typically assume that the agents environments are either fully (Wang et al. 2019 Huang et al. 2021b Dubey & Pentland 2020 He et al. 2022 Amani et al. 2022 Li et al.) 2022: Li & Wang 2022b
Dai et al. 2023) partially (Li & Wang 2022a
Agarwal et al. 2020 shared in the global lederation.
In federated learning, the following two modes are commonly considered: (1) There exists a central server in the system, and the agents can share information with the server, which can then broadcast aggregatod information back the agents; or (2) There exists a communication graph between agents, who can share information with their neighbors the graph. In the later discussions, mainly consider the first scenario, i.e. collaborating through the server, which is also the main focus in FL, while both modes can be effectively encompassed in the proposed FodIGW design.
2.2
The Current Disconnection Between FCB and FL
The exploration of FCB traces its origins to distributed multi-armed bandits (Wang et al. 2019 Since then, FCB research has predominantly focused on enhancing performance in broader problem domains,
encompassing various types of reward functions, such as linear (Wang et al. 2019 Huang et al. 2021b
Dubey & Pentland 2020 kernelized (Li et al. 2022 2023). generalized linear (Li & Wang 2022b and
neural (Dai et al. 2023) (sce Appendix
B for a comprchensive review).
3

---

Published in Transactions on Machine Learning Research (07/2024)
Table 2: A compact summary of investigations on FCB with their adopted FL and CB components;
more comprchensive review is in Appendix B
Reference
Setting
FL
CB
Globally Shared Full Model (See Section
3
Wang et al. 2019)
Tabular
Mean Averaging
AE
Wang et al. [2019] : Huang et al.
(2021b)
Linear
Linear Regression
AE
Li & Wang [2022a] He et al.
(2022)
Lincar
Ridge Regression
UCB
Li & Wang 2022b
Gen. Linear
Distributed AGD
UCB
Li et al.
2022 2023
Kernel
Nyström Approximation
UCB
Dai et al. 2023
Neural
NTK Approximation Flexible (c.g., FedAvg)
UCB
FedIGW (this work)
Realizable
IGW
Globally Shared Partial Model
(see Section 6.1
Li & Wang (2022a)
Linear
Alternating Minimization
UCB
Agarwal et al. (2020)
Realizable
FedRes.SGD
E-greedy
FedIGW (this work)
Realizable
Flexible (e.g., LSGD-PFL)
IGW
AE: arm elimination; Gen. Linear: generalized linear model; AGD: accelerated gradient descent
Upon holistic review of these works, becomes appar- ent that each of them employs a particular FL protocol update the parameters required by CB. To be more spe- cific, periodically alternating design between CB and FL is commonly adopted as reflected in Fig. 1 CB (col- lects one epoch of data in parallel) - FL (proceeds with CB data together and outputs CB's parameterization) + updated CB (collects another epoch of data parallel) ..... compact summary, including the components of and CB employed in previous FCB works, presented in Table 2
CB
CB
CB
CB
F
CB
F
CB
L
L
Provide data + Update parameterization
Figure The FCB design principle of periodically alternating between the employed
CB and FL components.
However, with a deeper look into the existing works, it is evident that the adopted FL components are not well investigated and even have some mismatches from canonical FL. designs [McMahan et al. 2017 Konečný
let al.
2016). For example, in federated linear bandits (Wang et al. 2019 Dubey Pentland 2020 Li &
Wang
2022a He et al. 2022 Amani et al. 2022 Fan el al.] 2023) and its extensions (Li et al. 2022 2023
2023), the adopted FL protocols typically involve the direct transmission of local reward aggregates and covariance matrices, constituting one-shot aggregation of compressed local data per epoch (albeit with subtle variations, such as synchronous asynchronous communications); concrete example is given in Appendix A.2, Due to both efficiency and privacy concerns, such choices are rare (and even undesirable) in canonical FL studies, where agents typically communicate and aggregate their model parameters (c.g., gradicnts) over multiple rounds, c.g., the renowned FedAvg algorithm (McMahan et al. 2017) (see details Appendix A.2
Li & Wang 2022b Dai
We believe that this disparity represents a significant drawback in current FCB studies, it limits the connection between FL and FCB to merely philosophical, i.e., benefiting individual learning by collaborating through federation, while vast. FI. st studies cannot be leveraged to benefit. FCB as illustrated in Fig. 2 Driven by this gap, this work aims to take one step towards establishing closer relationship between FCB and FL through the introduction of an exploring design, FedIGW, that is detailed in the subsequent sections. This approach provides the flexibility to integrate any FL protocol following the standard FL framework, which allows us effectively harness the progress made FL studios, encompassing canonical algorithmic designs, convergence analyses, and useful appendages.
3 FedIGW: Flexible Incorporation of FL Protocols
In this section, we present FedIGW, novel FCB algorithm proposed in this work. Before delving into the algorithmic details, concrete system model with stochastic contexts and realizable reward
4

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Existing FCB
Canonical FL
FedIGW
FedAvg (see Appendix A.2)
C
C
C
C
C
B
B
B
B
B
B
SCAFFOLD
Tailored FL
FL: Tailored Protocol
FedProx
Canonical FL
one-shot aggregation of compressed local data (see Appendix A.2)
C
B
Future designs
Comparison between the FL components in existing FCB approaches and the FedIGW design proposed in this work, where the former requires tailored FL. protocols while the latter can flexibly leverage both existing and forthcoming protocols in canonical FL studies. Additional comparisons regarding the FL components can be found in Appendix A.2
Figure 2:
function is introduced. Subsequently, outline the specifics of FedIGW, emphasizing its principal strength in seamlessly integrating canonical FL protocols.
3.1 System Model
Built on the formulation Sec. for each agent m [M), denote Xm a context space, and Am finite of Km actions. At each time step 4m of each agent m, the environment samples context 2m,tm E Xm and contexl-dependent reward vector Tm,t... [0, 1 according to fixed but unknown distribution Dm- The agent m, in Sec. 2 then observes the context Zm, picks action am,tm Am, and reccives the reward Fmmtm (Am,tm) The expected reward of playing action om given context 2m is denoted as Pmm (mm, (m) = Elrm,ttn (aom) (.mm [.
With no prior information about the rewards, the agents gradually learn their optimal policies, denoted by Tm (Im) arg max E.A., Pm (Im, an) for agent m with context Fy. Following standard notation (Wang
2019 Huang al. 2021b; Dubey & Pentland
2020
Li & Wang 2022a He al. 2022 Amani al.)
2022
Li & Wang 2022b
Li al. 2022
2023
Dai
al. 2023
the overall regret of M agents in this
environment
Reg(T) E
Σ
Σ
[mm (Immtt Ti (Fmm,t)) Mm (Fm, tm am,
m M tm [Tm]
where Tm = fm (T) is the effective time horizon for agent m given a global horizon T and the expectation is laken over the randomness in contexts and rewards and the agents' algorithms. This overall regret can be interpreted as the sum of each agent m's individual regret with respect to (w.r.t.) her optimal strategy "y Hence, it is ideal to be sub-linear w.r.t. the number of agents M, which indicates the agents' learning processes are accelerated
average due to federation.
Realizablilty. Despite not knowing the true expected reward functions, we consider the scenario that they are the same across agents and are within a function class F, to which the agents have access. This assumption, rigorously stated in the following, is often referred to as the realizability assumption.
Assumption 3.1 (Realizability). There erists f in F such that f (Im, am) = Mm (Zmm am) for all m E [M], Fmn E Xm and am E Am-
This assumption is natural extension from its commonly-adopted single-agent version Agarwal et al. 2012 Sivchi-Levi & Xu 2022 Xu & Zeevi 2020 Sen el al. 2021) to a federated one. Nole that it does not imply that the agents' envirouments are the same since they may face different contexts Xm. arms Am and distributions D.".., where D. is the marginal distribution of the joint distribution D,, on the context space Xn- We study general FCB setting only with this assumption, which incorporates many previously studied FCB scenarios as special cases. For example, the federated linear bandits (Huang al. 2021b Dubey &

---

Published in Transactions on Machine Learning Research (07 (07/2023) /024)
Algorithm FedIGW (Agent m)
Input: epoch mumber 1 = 1, reward function (: O, local dataset S for time step im 1,2, do
2: observe context Tm.t... compute Cn arg max EAmm A (am: Fmmtm) and action selection distribution
CB: IGW
1/ Km + (f Fmaee p (alm Fm.tm)) Σ d'm taa P'm (a (mm,t))
if 4m + 0'
P'm (mmm t
if am am
4: select action am,tm P (m observe reward tm (m))
5: update the local dataset St x Stn U {(Em, Om F Fmmmt (Omy }}}
6: if tm = (T') then
b FL
7: perform FL P+1 <- FLroutine($!.)
8: update dataset S1+1 <- 0; update epoch +- 1 1+1
9: end if
10: end for
Pentland 2020 Li & Wang 2022a He et al. 2022 Amani et al. 2022) are with a linear function class F.
Furthermore, Assumption 3.1 aligns with considerations in the canonical FL studies, where all clients learn one common model (i.e., f*) although their data distributions can be different (i.e., varying distribution Dm). Additional studies on personalization can be found in Sec. 6.1
3.2 Algorithm Design
The FedIGW algorithm proceeds epochs, which are separated at time slots - ,t,72,.. w.r.t the global time step 4, i.e., the 1-th epoch starts from t= ,/-1 + and ends at t ='. The overall number of epochs is denoted ((T). In each epoch that the FL component is decoupled and follows the standard FL framework.
describe the FL and CB components as follows, while emphasizing
CB: inverse gap weighting (IGW). For CB, we use inverse gap weighting (Abe & Long 1999 which has received growing interest in the single-agent setting recently (Foster & Rakhlin 2020 Simchi- Levi & Xu 2022 Krishnamurthy et al.) 2021 Ghosh et al. 2021) but has not been fully investigated in the federated setting. At any time step in epoch I, when encountering the context Xm, agent m first identifies the optimal arm by a = arg max EAA.. ('mm am) from an estimated reward function } (provided by the to-be- discussed FL component). Then, she randomly selects her action an according the following distribution, which is inversely proportional to each action's estimated reward gap from the identified optimal action ";.:
P/m (am (mm) 1/ Km + (MaTi: xm) ( (amms Fm)) Eain Fan (m
Om * an
if am a
where 7 is the learning rate in epoch I that controls the exploration-eexplottaiion tradeoff.
Besides being a valuable supplement to the currently dominating UCB-based studies in FCB, the main merit of leveraging IGW as the CB component is that it only requires an estimated reward function instead of other complicated data analytics, e.g., upper confidence bounds.
FL: flcxible choices. By IGW, cach agent performs local stochastic sampling and collects set of data samples S {(Im.t.. 4m,tm Fm,t. tm E (r'-)) (.'m((7))))))) in epoch l. To enhance the performance of IGW the subsequent epoch 1 1+ 1, an improved estimate fi+ based on all agents' data is desired, This objective aligns precisely with the aim of canonical FL studies, which aggregates local data for better global estimates (McMahan et al. 2017 Konečný al.] 2016). Thus, the agents can target solving

---

Published in Transactions on Machine Learning Research (07 (024))
the following standard FL problem:
min ((f: = Σ fer
(nm/n)- -mm//m)mmmmm (fi
(1)
mE[M]
where nmm = | is the number samples in dataset S n n= E [ Am is the total number of samples, and Em (f: = (1/mm) Eie(n.)) (f om)):))) the empirical local loss of agent m with (m()))
R + R the loss function and (I on vin) the i-th sample in S...
As Equ. exactly follows the standard formulation of FL, the agents and the server can employ any FL protocol to solve this aptimization, such as FedAvg (McMahan et al.] 2017), SCAFFOLD (Karimireddy et al. 2020) and FedProx (Li et al., 2020a]. These wildly-adopted FL protocols typically perform iterative communications of local model parameters (e.g., gradients), instead of one-shot aggregations of compressod local data in previous FCB studies. To highlight. the remarkable flexibility, we denote the adopted FL protocol as FLroutine()). With datasets S(M] (S), m [M]), the output function of this FL process, denoted f+1 FLroutine($/m)) is used the estimated reward function for IGW sampling in the next epoch 1.
The FedIGW algorithm for agent is summarized in Alg. The key, aforementioned, is that the component of FL in FedIGW is highly flexible as it only requires an estimated reward function for later IGW interactions. In particular, any cxisting or forthcoming FL protocol following the standard FL framework in Equ. can be leveraged as the FLroutine()) FedIGW.
Remark 3.2. The main underlying reason for selecting IGW as the CB component is that it is regression- based CB algorithm, i.c., IGW only requires a learned reward function f for the CB interaction one epoch I. The canonical FL framework with an optimization perspective is exactly targeted at learning such a function collaboratively solving Equ. (1) which thus can be integrated with IGW. In contrast, previous FCB designs are predominated by UCB-based CB components as reflected in Table However, obtaining the upper confidence bounds (UCBs) estimates for unknown reward function is not usually the target of the canonical FL framework. Thus, vailored FL components are developed to fulfill this purpose, e.g., sharing covariance matrices to obtain UCBs for linear reward functions. We note that there are also other regression-based based CB algorithms, e.g., greedy and softmax. IGW is adopted here mainly due to its theoretical superiority demonstrated in Sec. while its strong empirical performances have also been observed in Sec.
4 Theoretical Guarantees: Modularized Plug-in of FL Analyses
In this section, we theoretically analyze the performance of the FedIGW algorithm, where the impact of the adopted FL choice is modularized as plug-in component of its optimization error.
4.1 A General Guarantee
Denoting E', := (T)) (7 as the length of epoch | for agent m, EiM] == (E', : m E [M] as the epoch length set, g = [ / E 7 maxme(M] Eym / and c c: z/2. the following global regret guarantee can be established.
Theorem 4.1. Using a learning rate o' = Ov
E. Km/ (E E (MEE(((M)) in epoch 1,
denoting K = EmEjMi FL Km/ Emejan Fin, the regret of FedIGW can be bounded
(
Reg(T) 00
EEE
Σ E. Σ á (RIE(F
Σ E
(2)
MEMM
(E(2)(T)
mE(M]
denotes the excess risk of the output from the adopted FLroutine(S (M) using the datasets Siny whose formal definition is deferred to Desinition C.1
Here E(E)))) (abbreviated from E(F; (
7

---

Published in Transactions on Machine Learning Research (07/2024)
It can be observed that in Eqn. ( the first term bounds the regret in the first epoch. The obtained bounds for the regrets incurred within each later epoch (i.e., the term inside the sum over 1 in the second epoch) can be interpreted as the epoch length times the expected per-step suboptimality, which then relates to the estimation quality of f and thus (M) as f is learned with the interaction data collected from epoch
[- 1 as in the design of FedIGW shown in Alg.
4.2 Some Concretized Discussions
Theorem 4.1 is notably general in the sense that a corresponding regret can be established as long as an upper bound on the excess risk ((E))) can be obtained for certain class of reward functions and the adopted FL protocol. In the following, we provide several more concrete illustrations, and especially, a modularized framework to leverage FL convergence analyscs. To case the notation, we discuss synchronous systems with a shared number of arms in the following, i.e, im = t, Vm E [M], and Km = K, Vm E [M], while noting similar results can be casily obtained for general systems. With this simplification, can unify all E E' and K' as K.
To initiate the concretized discussions, we start with considering a finite function class F, i.e., |F] < o0, which can be extended to a function class F with a finite covering number of the metric space ).o) In particular, the following corollary can be established via establishing {(1()s)) = ((log((Fin/n)) in the considered case as Lemma D.2
< 0o and the adopted FL protocol provides an ex- Corollary 4.2 (A Finite Function Class). If IF
act minimizer for Equ. ① with quadratic losses, with 7' = 2 FedIGW incurs a regret of Reg(T) = Oly K MT log(())MT) and a tolal O()og(T)) calls of the adopted FL protocol.
We note that the obtained regret approaches the optimal regret Ω (My/K KMT log(IF))/loo(t (K) of a single agent playing for MT rounds (Agarwal et al. 2012) up to logarithmic factors, which demonstrates the statistical efficiency of the proposed FedIGW. Moreover, the total (T)) times call of the FL protocol indicates that only a limited number of agents-server information-sharing are required, which further illustrates its communication efficiency.
As the finite function class is not often practically useful, we then focus on the canonical FL setting that each E F is parameterized by d-dimensional parameter facilitate discussions, we abbreviate S == SIM while denoting w/s arg min L( as the empirical optimal parameter given a fixed dataset S and Ws as the output of the adopted FI. protocol. We further assume f* is parameterized by the true model parameter w", and for fixed w, define C(fw) == [s([(fw;8)] as its expected loss w.r.t. the data distribution.
Rd as fwr c.g., a neural network. To
Following standard learning- theoretic analyses, the key task excess risk (M)) can be bounded via a combination of errors stemming from optimization and generalization.
Lemma 4.3. If the loss function (1--)) is sty-strongly conver in its first coordinate for all m E [M], it holds that (FFm)M) s 2 (Fop((F; + Egen (F:rM)) /Pz, where eyen(F; mpn)) == - S)] and (Fpo ((m))) = B.s. ( :5) S)]
-
For the generalization error term Egen (F; n(M),, we can utilize standard results in learning theory (e.g.. uniform convergence). For the sake of simplicity, we here leverage a distrrbuutona-ineeepndndt upper bound on the Rademacher complexity, denotod as ([]]) (rigorously defined in Eqn. (4) which provides that Sgen (Fin) < (MFFF))M) using the classical uniform convergence result (see Lemma D.5h- We do not further particularize this upper bound while noting it can be specified following standard procedures (Mohri
ct al. 2018 Bartlett et al. 2005).
On the other hand, the optimization error term Eape (F; is exactly the standard convergence error in the analysis FL protocols. Thus, once any theoretical breakthrough on the convergence of one FL protocol is reported, the obtained result can be immediately incorporated into our analysis framework to characterize the performance of FedIGW using that FL protocol. In particular, the following corollary is established to demonstrate the modularized plug-in of analyses of different FL protocols, where Fed (McMahan et. al.
8

---

Published in Transactions on Machine Learning Research (07/2024)
2017 and SCAFFOLD Karimireddy et al. 2020) are adopted as further specific instances. To the best of our knowledge, this is the first time that convergence analyses of FL protocols can directly benefit the analysis of FCB designs.
Corollary 4.4 (Modularized Plug-in of FL Analyses; A Simplified Version of Corollary D.6 condition of Lemma 4.3 the regret of FedIGW con be bounded as
Under the
Reg(T) =0 ME + E (
+.--1+6%-0 6'op)) /
(E(J(()
where R¹ :- (EFFFEE' m E [M]) and using of rounds of commuuiications (i.e., global oggregalions) and n rounds of local updates in epoch L, under a few other standard conditions,
with FedAug as the adopted FLroutine(.), it holds that e'opt S (() with SCAFFOLD as the adopted FLroutine(.), it holds that E'opt S (((dk())1))
From this corollary, we can see that FedIGW enables a general analysis framework to seamlessly leverage thcoretical advances in FL, in particular, convergence analyses. Thus, besides FedAvg and SCAFFOLD, when switching the FL component in FedIGW to FedProx (Li et al. 2020a), FedOPT (Reddi et al. 2020 and other existing or forthcoming FL designs, we can effortlessly plug in their optimization errors obtain corresponding performance guarantees of FedIGW. This convenience highlights the theoretically intimate relationship between FedIGW and canonical FL studies.
Morcover, Corollary 4.4 can also guide how to perform the adopted FL protocol. As the generalization error is an inherent property that cannot. be bypassed by betler oplimization results, there is no need to further proceed with the iterative FL. process as long as the optimization error does not dominate the generalization error, which is reflected in a more particularized corollary in Corollary D.7
Remark 4.5 (A Lincar Reward Function Class). As a more specified instance, we consider lincar reward functions as in lederated linear bandits, i.e., [-)()) = (w, æ(-) and (*() = (())), where d(-) E Rd is a known feature mapping. In this case, the FL problem can be formulated as a standard ridge regression with em (f am); mm) == ((w, p( am)) rm)²² + A/|w|12- With properly chosen regularization paramcter A O(1/n), the generalization error same-order optimization error can be achieved by many efficient distributed algorithms (Nesterov 2003)
be bounded as Egen Egea (m()) = Ö(d/n) (Hsu et al. 2012). while
with roughly (vi log(n/d)) rounds of communications. Then, with an exponentially growing epoch length, FedIGW can have a regret of Ö(VdMKT) with at most Ö(VMT) rounds of communications as illustrated in Appendix D.3. both of which are efficient with sublinear dependencies on the number of agents M and time horizon It is worth noting that during this process, no raw or compressed data communicatod only processed model parameters (e.g., gradients) are exchanged. This aligns with FL studies while is
distinctive from previous designs for federated linear bandits (Dubey & Pentland 2020 Li & Wang. 2022a
He et al. 2022 Fan et al. 2023). which often communicate covariance matrices or aggregated rewards.
Remark 4.6 (Beyond Linear Reward Functions). This modularized framework can be further adopted in analyzing other reward functions as long the corresponding excess risks can be provided. For example, the optimization errors of FedAvg (and its variants) with neural networks as the function class can be obtained from many recent works, including Theorem 4.1 in Huang et al. (2021a) and Theorem in in/Son et al. (2023). The corresponding generalization error can also be established following existing results, e.g., Theorem 4.3 in Huang et al. (2021a) and Chapter 11 in ZZangg (2023). Combining these two parts of analyses can lead to bounds on regret and communication rounds that are sublinear in M and T using the analysis framework.
5 Experimental Results
In this section, we report the empirical performances FedIGW on two distinct real-world multi-label classification datasets, Bibtex (Katakis et al., 2008) and Delicious (Tsumaakas et al.] 20088, which are also used in other practical CB investigations such as Cortes (2018). The aim of CB in these experiments is considered to be recommending one of the correct labels at any given time. Especially, in the experiments,
9

---

Published in Transactions on Machine Learning Research (07 (07/2024) /024)
FN-UCB
FN-UCB
0.3
FedIGW (TedAvg)
0.4
FedIGW (PedAvg)
FedICW (FedProx)
FedICW (FedProx)
Average rewarv
0.4
FedIGW (ScafTold)
Average roward
FedIGW (Scaffold)
Greedy (FedAvg)
0.3
Greedy (FedAvg)
0.3
Softmax (FedAvg)
Softmax (FedAvg)
0.2
0.1
0.0
0.0
0.00
0.22
0.50
0.75
7.00
1.25
1.50
1.75
2,00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2,00
Rounds
1ed
Rounds
Ted
Figure 3: The averaged reward collected by each agent via FedIGW (using different FL protocols). the state-of-the-art FN-UCB, and two other naive baselines (i.e., greedy and softmax using FedAvg) with = participating agents on Bibtex (left) and Delicious (right) datasets.
at each time step, a context. is randomly sampled from the dataset while the true labels are concealed from the agents. The agents then determine which label to select (i.e., pull one arm) with their CB algorithms; thus, the number of arms is the number of possible labels in each dataset. Upon pulling is granted if the pulled arm corresponds to one of the true labels, while reward of O is granted otherwise. From Table we can observe that these tasks are challenging given their high-dimensional contexts (> 500) and large numbers arms (> 150). Additional experimental details and results are discussed in Appendix while the codes for the experiments can be found https: //g thub. com/ ShweSShheeeeeeeiiiee
arm, reward of
Varying FL choices. The reported Fig. 3 first compares the averaged rewards collected by each agent with FedIGW using different FL choices, in- cluding FedAvg (McMahan et al. 2017), SCAF. FOLD (Karimireddy et al. 2020), and FedProx (Li et al. 2020a). This is the first time, to the best of our knowledge, that FedAvg practically integrated with FCB experiments, let alone other FL protocols, which largely demonstrate the generality and flexibility of FedIGW. It can be observed that using the more developed SCAFFOLD and FedProx provides improved performance (i.e., collects more rewards) compared with the basic FedAvg, which credits to that FedIGW can flexibly leverage algorithmic advances in FL protocols.
Table 3: The context dimension and number of arms
in Bibtex and Delicious
Task
Context dimension
Number of arms
Bibtex
1835
159
Delicious
500
983
Comparison with basclines. To further evaluate the performance of FedIGW, experiments are conducted to compare it with several baselines as described the following.
FN-UCB (Dai et al., 2023). The federated neural-upper confidence bound (FN-UCB) design proposed in Dai et al. (2023) is adopted strong FCB baseline due to its capability of leveraging neural networks to approximate rewards and the previously reported good performance. Instead of being compatible with canonical FL protocols, FN-UCB requires specifically developed communication design, where local neural tangent features are transmitted to the server for global aggregation in one-shot fashion.
Greedy and softmax. Besides IGW, two other regression- based CB algorithms, greedy selection and softmax selection, are also adopted for empirical validations using FedAvg collaboratively learn the reward function. In particular, the action selocted as am,t... + arg max. e.A.. (am Fm,t..) for greody and am,tm softmax( ( F...t..).. )/C for softmax, where is tempurate parameter.
In Fig, 3, all methods leverage the same-size MLPs to approximate reward functions for fair comparisons. It can be observed that after convergence, FedIGW (even with the basic FedAvg) significantly outperforms FN-UCB with about twice the rewards collected by each agent on average, demonstrating superiority. Also, under the FL protocol (i.e., FedAvg), FedIGW exhibits much stronger performance than greedy and softmax, further illustrating the advantage of using IGW as the CB algorithm.
remarkable
10

---

Published in Transactions on Machine Learning Research (07/2024)
6 Flexible Extensions: Seamless Integration of FL Appendages
Another notable advantage offered by the flexible FL choices is to bring appealing appendages from FL studies to directly benefit. FCB. In the following, we discuss how to leverage techniques of personalization, robustness, and privacy from FL in FedIGW while presenting intriguing avenues for future exploration.
6.1 Personalized Learning
In many cases, each agent's true reward function is not globally realizable as in Assumption 3.1 but instead only locally realizable in her own function class as in the following assumption.
Assumption 6.1 (Local Realizability). For each m E [M], there crists fm in Fm such that fm (Im, aml = (m((mm am) for all I' E Xm and am E Am
Following discussions in Sec. 1.2 we consider that each function / in Fm is parameterized by dimdinensional parameter wm Rd,,, which is denoted as fw... Correspondingly, the true reward function fm. is parameter- ized by wi, and denoted as fw- To still motivate the collaboration and motivated by popular personalized
FL studies (Hanzely et al. 2021 Agarwal et al. 2020); we study a middle case where only partial parameters are globally shared among {fut
: m E [M] while other parameters are potentially heterogeneous among agents, which can formulated via the following assumption.
Assumption 6.2. For all m E [M), the true porameter w can be decomposed as (war whi") with way e T.d and whn" E R,,,, where d" S minme[M] dm and di == dm - dd In other words, there are d' -dimensionnl globally shared parameters among {w m E [M]]
A similar setting is studied in Li & Wang (2022a) for linear reward functions and in Agarwal et al. (2020)
for realizable cases with a naive E-greody design for CB. For FodIGW, we can directly adopt a personalizod FL protocol (such LSGD-PFL in Hanzzly el. al. (2021)) to solve standard personalized FL problem:
min DlSwa we,neonn)
wipn :(M)) =
Σ mE(M]
(nm//)) w
With outputs @ and 0:9 [MP the correspouding M functions (/a p9 : m E [M]} (instead the single one î
in Sec. 3.2 can be used by the M agents, separately, for their CB interactions following the IGW algorithm. Concrete results and more details can be found in Appendix E.I
Remark 6.3 (A Linear Reward Function Class). Similar to Remark 4.5 we also consider linear reward functions for the personalized setting with fm: (.) ;= (Win, ((-) and fwi,. : m E [M]} satisfying Assumption 6.2 Then, FedIGW still can achieve a regret of D(vdM('))) KT) with Ö(VMT) rounds of communications, where
d = dd + Emelan di see more details in Appendix E.1.1
6.2 Robustness, Privacy, and Beyond
Another important direction in FCB studies is to improve robustness against malicious attacks and pro- vide privacy guarantees for local agents. A few progresses have been achieved in attaining these desirable attributes for FCB but they typically require substantial modifications to their base FCB designs, such as robustness in Demirel et al. (2022): Jadbabaie et al. (2022); Mitra et al. (2022) and privacy guarantees in
Dubey Pentland 2020); Zhou Chowdhury (2023 ; Li Song (2022); Huang et al. (2023).
With FedIGW, it more convenient to achieve these attributes as suitable techniques from FL studies can be seamlessly applied. Especially, robustness and privacy protection have been extensively studied for FL in Yin et al. (2018); Pillutla et al. (2022); Fu et al. (2019) and Wei et al. (2020); Yin et al. (2021); Liu et al. (0022), respectively, among other works. As long as such FL protocols can provide an estimated function (which is the default goal of FL,), they can be adopted in FedIGW to achieve additional robustness and
privacy guarantees FCB; see more details in Appendix E.2
Other Possibilities. There have been many studies on fairness guarantees Mohri et al. 2019 Du et al.
2021), client selections (Balakrishnan et al.] 2022 Fraboni al. 2021), and practical communication designs
11

---

Published in Transactions on Machine Learning Research (07/2024)
CCenn et al. 2021 Wei & Shen 2022 Zheng et al. 2020 in FL among many other directions, which all conceivably applicable in FedIGW. In addition, Marfoq et al. (0223) studies FT. with data streams, i.e., data comes sequentially instead of being static, which is a suitable design for FCB as CB essentially provides data streams. If similar ideas can be leveraged in FCB, the two components of CB and FL can truly be parallel.
7 Conclusions
In this work, we studied the problem of federated contextual bandits (FCB). It is first recognized that existing FCB dosigns largely disconnected from canonical FL studics in their adopted FL protocols, which hinders the integration of crucial FL advancements. To bridge this gap, we introduced novel design, FedIGW, capable of accommodating a wide range of FL protocols, provided they address a standard FL problem. A comprchensive thcorctical performance guarantec was provided for FedIGW, highlighting its efficiency and versatility. Notably, we demonstrated the modularized incorporation of convergence analysis from FL by employing examples of the renowned FedAvg (McMahan et al., 2017) and SCAFFOLD (Karimireddy let al.] 2020). Empirical validations on real- wolld datasets further underscored its practicality and flexibility. Moreover, explored how advancements in FL can seamlessly bestow additional desirable attributes upon FedIGW. Specifically, we delved into the incorporation of personalization robust and privacy, presenting intriguing opportunities for future research.
It would be valuable to pursue further exploration alternative CB algorithms within FCB, c.g., Xu & Zeevi 2020 Foster et al. (2020); Wei & Tuo (2021), and investigate whether the FedTGW design can be extended to more general federated RI. (Dubey & Pentland 2021 Min et al., 2023
Acknowledgement
The work of CSs and KY was partially supported by the U.S. National Science Foundation (NSF) under awards ECCS-203366 ECCS-2143559, CPS-2313110, and CNS-2002902, and the Bloomberg Data Science Ph.D. Fellowship.
References
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic concepts. In ICML, pp. 3-11. Citescer, 1999.
Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, and Robert Schapire. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pp. 19-26. PMLRR 2012.
Alckh Agarwal, John Langford, and Chen-Yu Wei. wwXiv:2003.12880 2020.
Federated residual learning. arXiv preprint
Alekh Agarwal, H Brendan McMahan, and Zheng Xu. An empirical evaluation of federated contextual bandit algorithms. arXie preprint arXiv:2303. 12000.102110 10218, 2023.
Sanae Amani, Tor Lattimore, András György, and Lin Yang. Distributed contextual lincar bandits with minimax optimal communication cost. arXiv preprint arXiv:2205.111 2022.
Peter Auer, Nicolo Cesa-Bianchi Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. STAM journal on computing, 32(1):48-77 2002.
Ravikumar Balakrishnan, Tian Li, Tianyi Zhou, Nagcen Himayat, Virginia Smith, and Jeff Bilmes. Di- verse client selection for federated learning via submodular maximization. In International Conference on Learning Representations, 2022.
12

---

Published in Transactions on Machine Learning Research (07/2024)
Peter Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. Annals of Statistics, 33(44:1497-1537, 2005.
Etienne Boursier and Vianney Perchet. Sic-mmab: synchronisation involves communication in multiplayer multi-armed bandits. In Advances in Neural Information Processing Systems, pp. 12071-12080, 2019.
Deepayan Chakrabarti, Ravi Kumar, Filip Radlinski, and Eli Upfal. Mortal multi-armed bandits. Advances neural information processing systems, 21, 2008.
Jeffrey Chan, Aldo Pacchiano, Nilesh Tripuraneni, Yun Song, Peter Bartlett, and Michael I Jordan. Parallelizing contextual bandits. arXiv preprint arXiv:2105. 10590, 2021.
Mingzhe Chen, Deniz Gündüzz, Kaibin Huang, Walid Saad, Mchdi Bennis, Ancta Vulgarakis Feljan, and H. Vincent Poor. Distributed learning in wireless networks: Recent progress and future challenges. IEEE Journal on Selected Areas in Communications, 39(12):3579-3600 2021.
Zhirui Chen, PN Karthik, Vincent YF Tan, and Yeow Meng Chee. Federated best arm identification with heterogencous clients. arXiv preprint arXiv:2210.0770 2022.
Chi-Ning Chou, Juspreet Singh Sandhu, Mien Brabeeba Wang, and Tiancheng Yu. A general framework for analyzing stochastic dynamics in learning algorithms. arxiv preprint orXi::2006.061 2020.
Pedro Cisneros- Velarde, Boxiang Lyu, Sanmi Koyejo, and Mladen Kolar. One policy is enough: Parallel exploration with single policy is ncar-optimal for reward-free reinforcement learning. In International Conference Artificial Intelligence and Stalistics, pp. 1965 2001. PMLR, 2023.
David Cortes. Adapting multi-armed bandits policies to contextual bandits scenarios. arXiv preprint wxXiv:181.04386. 2018.
Zhongxiang Dai, Yao Shu, Arun Verma, Flint Xiaofeng Fan, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated neural bandit. The Eleventh International Conference on Learning Representations, 2023.
Ilker Demirel, Yigit Yildirim, and Cem Tekin. Federated multi-armed bandits under byzantine attacks. arXiv preprint Xrx:222205.044 04134, 2022.
Wei Du, Depeng Xu, Xintao Wu, and Hanghang Tong. Fairness-aware agnostic federated learning. Tn Proceedings of the 2021 SIAM International Conference Data Mining (SDM), pp. 181 189. SIAM, 2021.
Abhimanyu Dubey and Alex Pentland. Differentialll-priiatt federated linear bandits. Advances in Neural Information Processing Systems, 33:6003-600 -6083, 2020.
Abhimanyu Dubey and Alex Pentland. Provably efficient cooperative multi-agent reinforcement learning with function approximation. arXiv preprint arXiv:2103.0409 2021.
Li Fan, Ruida Zhou, Chao Tian, and Cong Shen. Federated linear bandits with finite adversarial actions. arXiv preprint ar orXic:2311.0000 2023.
Xiaofeng Fan, Yining Ma, Zhongxiang Dai, Wei Jing, Cheston Tan, and Bryan Kian Hsiang Low. Fault- tolerant federated reinforeement learning with theoretical guarantee. Advances in Neural Information Processing Systems, 34:1007-1021, 2021.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. International Conference on Machine Learning, pp. 3199 3210. PMLR, 2020.
Dylan Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instanco-dependent complexity of contextual bandits and reinforcement learning: A disagroementtbassel perspective. arXiv preprint arXiv:2010.03100 2020.
13

---

Published in Transactions on Machine Learning Research (07/2024)
Yann Fraboni, Richard Vidal, Lactitia Kameni, and Marco Lorenzi. Clustered sampling: Low-variance and improved representativity for clients selection in federated learning. In International Conference Machine Learning, pp. 3407 3416. PMLR, 2021.
Shuhao Fu, Chulin Xie, Bo Li, and Qifeng Chen. Attack-rosistant federated learning with residual-basee reweighting. arXiv preprint urxiv:1912. 114,1,9911,14 2019.
Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran. Model selection for generic contextual bandits. XrXiv preprint arX:::2107.3345, 2021.
Antonious Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled model of differential privacy in federated learning. In International Conference on Artificial Intelligence and Stalistics, pp. 2521 2529. PMLR, 2021.
Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glymn, and Yinyu Ye. Sequential batch learning finite-action linear contextual bandits. arXiv preprint ar arXiv:204.006321 2020.
Filip Hanzely, Boxin Zhao, and Mladen Kolar. Personalized federated learning: A unified framework and universal optimization techniques. arXie preprint orXiv:2102.0977 09743,. 2021.
Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu. A simple and provably efficient algorithm for asynchronous federated contextual linear bandits. Advances in neural information processing systems, 2022.
Eshcar Hillel, Zohar S Karnin, Tomer Koren, Ronny Lempel, and Oren Somckh. Distributed exploration in multi-armed bandils. Advances in Neural Information Processing Systems, 26, 2013.
Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression. In Conference on learning theory, pp. 9-1. JMLR Workshop and Conference Proceedings, 2012.
Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang. Fl-ntk: A neural tangent kernel-based framework for federated learning analysis. In International Conference on Machine Learning, pp. 4423-4434 PMLR, 2021a.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. Advances in neural information processing systems, 34:27057 27068, 2021b.
Ruiquan Huang, Huanyu Zhang, Luca Melis, Milan Shen, Meisam Hejazinia, and Jing Yang. Federated linear contextual bandits with user-level differential privacy. In International Conference on Machine Learning, pp. 14060-14095, PMLR, 2023.
Ali Jadbabaie, Haochuan Li, Jian Qian, and Yi Tian. Byzantine-robust federated linear bandits. Tn 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 5206 5213. IEEE, 2022.
Hao Jin, Yang Pong, Wenhao Yang, Shusen Wang, and Zhihua Zhang. Federated reinforcement learning with environment heterogeneity. In International Conference on Arlificial Intelligence and Slatistics, pp. 18 37. PMLR, 2022.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurōlien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends0 in Muchine Learning, 2211220,,-00 2021.
Amin Karbasi, Vahab Mirrokui, and Mohammad Shadravan. Parallelizing thompson sampling. Advances in Newral Information Processing Systems, 34:10535-10548, 2021.
Sai Pranceth Karimireddy, Satyen Kale, Mchryar Mohri, Sashank Reddi, Scbastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for foderated learning. In International PML.R 2020.
Conference Machine Learning, pp.
14

---

Published in Transactions on Machine Learning Research (07/2024)
Ioannis Katakis, Grigorios Tsoumakas, and Ioannis Vlahavas. Multilabel text classification for automated tag suggestion. ECML, PKDD discovery challenge, 75:2008, 2008.
Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Dis- tributed machine learning for on-device intelligence. arXic preprint arXiv:1610. (ato:16100222,, 2016.
Sanath Kumar Krishnamurthy, Vitor Hadad, and Susan Athey. Adapting to misspecification in contextual bandits with offline regression oracles. In International Conference on Machine Learning, pp. 5805-5814. PMLR, 2021.
Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. On distributed cooperative docision-making in multiarmed bandits. In 2016 European Control Conference (ECC), pp. 243 248. IEEE, 2016.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. In International Conference on Artificial Intelligence and Statistics, pp. 6529-6553. PMLR, 2022a.
Chuanhao Li and Hongning Wang. Communication efficient federated learning for generalized lincar bandits. Advances in Newral Information Processing Systems, 2022b.
Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Communication efficient. distributed learning for kernelized contextual bandits. Advances in Neural Information Processing Systems, 2022.
Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Learning kernelized contextual bandits in a distributed and asynchronous environment. The Eleventh International Conference on Learning Representations, 2023.
Tan Li and Linqi Song. Privacy-preserving communication-effeeeen federated multi-armed bandits. IEEE Journal on Selected Areas in Communiiatiions, 40(3):773 787, 2022.
Tian Li, Anit Kunar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning; Challenges, methods, and future directions. IEEE signal processing magazine, 37(3):50-66 60, 2020a.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pp. 6357-6368. PMLR, 2021.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learwing Representations, 2020b.
Jiabin Lin and Shana Moothedath. Federated stochastic bandit learning with unobserved context. arXiv preprint arXio:2303.10433 2023.
Keqin Liu and Qing Zhao. Distributed learning in multi-armed bandit with multiple players. IEEE Trans- actions on Signal Processing, 58(11):5667-366,, 2010.
Ziyao Liu, Jiale Guo, Wenzhuo Yang, Jiani Fan, Kwok- Yan Lam, and Jun Zhao. gation in federated learning: A survey. IEEE Transactions on Big Data, 2022.
aggre-
Ekdeep Lubana, Chi Ian Tang, Fahim Kawsar, Robert Dick, and Akhil Mathur. Orchestra: Unsupervised federated learning via globally consistent clustering. In International Conference on Machine Learning, PMLR, 2022.
pp.
Othmane Marfoq, Giovanni Neglia, Laetitia Kameni, and Richard Vidal. Federated learning for data streams. arXiv preprint arXi::2301.0155 2023.
David Martinez Rubio,, Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. Advances in Newral Information Processing Systems, 32, 2019.
15

---

Published in Transactions on Machine Learning Research (07/2024)
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiinn learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273 1282. PMLR, 2017.
Yifci Min, Jiafan He, Tianhao Wang, and Quanquan Gu. Multi-agent reinforcement learning: Asynchronous communication and linear function approximation. orXiv preprint arXiv:2305.06444 2023.
Aritra Mitra, Arman Adibi, George Pappas, and Hamed Hassani. Collaborative linear bandits with adversarial agents: Near-optimal regret bounds. Advances in neural information processing systems, 2022.
Mchryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic lederated learning. In International Conference on Machine Learning, pp.
PMLR, 2019.
Yurii Nesterov. Introductory lectures on concer optimization: basic course, volume 87. Springer Science & Business Media, 2003.
Gergely Neu and Julia Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. In Conference on Learning Theory, pp. 3049-30000 3068. PMLR, 2020.
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. 1EEE Transactions on Signal Processing, 70: 70:1142-1154, 2022.
Clémence Réda, Sattar Vakili, and Emilie Kaufmann. Near-optimal collaborative learning in bandits. In NewrIPS 2022-36th Conference on Neural Information Processing System, 2022.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive foderated optimization. arXiv preprint XrXiu:2033.00200 2020.
Sudeep Salgia and Qing Zhao. Distributed linear bandits under communication constraints. arXiv preprint arXiv:2911002919 2022.
Rajat Sen, Alexander Rakhlin, Lexing Ying, Rahul Kidambi, Dean Foster, Daniel N Hill, and Inderjit. S Dhillon. Top-k extreme contextual bandits with arm hierarchy. In International Conference Machine Learning, pp. 0422-9433 PMLR, 2021.
Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9603-9611 2021.
Chengshuai Shi, Wei Xiong, Cong Shen, and Jing Yang. Decentralized multi-player multi-armed bandits with no collision information. In International Conference on Artificial Intelligence and Statistics, pp. 1519- 1528, PMLR, 2020.
Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armed bandits with personalization. In Inter- national Conference on Artificial Intelligence and Statistics, pp. 2917 2925. PMLR, 2021a.
Chengshuai Shi, Wei Xiong, Cong Shen, and Jing Yang. Heterogencous multi-player multi-armed bandits: Closing the gap and generalization. Advances in neural information processing systems, 34:22392-223 -24044, 2021b.
Chengshuai Shi, Wei Xiong, Cong Shen, and Jing Yang. Reward teaching for federated multiarmed bandits. IEEE Transactions on Signal Processing, 71:4407-4422, 2023.
David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 47(3):1904-1933 2022.
16

---

Published in Transactions on Machine Learning Research (07/2024)
Bingqing Song, Prashant Khanduri, Xinwei Zhang, Jinfeng Yi, and Mingyi Hong. Fodavg converges to zero training loss linearly for overparameterized multi-layer neural networks. In International Conference Machine Learning, pp. 32304 32330. PMLR, 2023.
Balazs Szorenyi, Róbert Busa-Fekete, István Hegedus, Róbert Ormándi, Márk Jelasity, and Balázs Kégl. Gossip-based distributed stochastic bandit algorithms. In International conference on machine learning, pp. 19-27. PMLR, 2013.
Grigorios Tsoumakas, Ioannis Katakis, and Ioannis Vlahavas. Effective and efficient multilabel classification in domains with large number of labels. In Proc. BCML/PKDD 2008 Workshop on Mining Mullidimen- sional Data (MMD'08) 008, volume 21, pp. 53 59, 2008.
Bram van Berlo, Aaqib Saeed, and Tanir Ozcelebi. Towards federated unsupervised representation learning. In Proceedings of the third ACM international workshop on edge systems, analytics and networking, pp. 31-36, 2020.
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit. learning: Near-optimal regret with efficient communication. arXiv preprint arXio:1904.06309 2019.
Chen- Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Conference on Learning Theory, pp. 4300 4354. PMLR, 2021.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Securily, 15:3454-3469 2020.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Hang Su, Bo Zhang, and H Vincent Poor. User-level privacy- preserving federated learning: Analysis and performance optimization. IEEE Transactions on Mobile Computing, (9))333888 3401, 2021.
Xizixiang Wei and Cong Shen. Federated learning over noisy channels: Convergence analysis and design
examples. IEEE Transactions on Cognitive Communécations and Networking, (2)):1253-1265 2022.
Ran Xin, Usman A Khan, and Soummya Kar. Variance-reduced decentralized stochastic optimization with accelcrated convergence. IEEE Transactions on Signal Processing, 68:6255-6271, 2020.
Yunbei Xu and Assaf Zeevi. Upper counterfactual confidence bounds: new optimism principle for contextual bandits. arxiv preprinl arXiv:2007.0787% 2020.
Haishan Ye, Wei Xiong, and Tong Zhang, Pmgt-vr: A decentralized proximal-gradient algorithmic framework with variance reduction. arXiv preprint arXim:2012.1500 2020.
Jialin Yi and Milan Vojnović. Doubly adversarial federated bandits. arXiv preprint orXie:2301.0922 2023.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650-5659. PMLR, 2018.
Xuefei Yin, Yanming Zhu, and Jiankun Hu. A comprehensive survey privacy-preservingg lederated learning: A taxonomy, review, and future directions. ACM Computing Surveys (CSUR), 54(6):1-366 1-36 2021.
Fengda Zhang, Kun Kuang, Zhaoyang You, Tao Shen, Jun Xiao, Yin Zhang, Chao Wu, Yueting Zhuang, and Xiaolin Li. Federated unsupervised representation learning. arXiv preprint arxiv:2010. 08988, 2020.
Tong Zhang. Mathematical Analysis of Machine Learning Algorithms. Cambridge University Press, 2023.
Sihui Zheng, Cong Shen, and Xiang Chen. Design and analysis of uplink and downlink communications for federated learning. IEEE Journal Selected Areas in Communications, 39(7):2150- -1677 2020.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pp. 11492- -1502. PMT.R, 2020.
17

---

Published in Transactions on Machine Learning Research (07/2024)
Xingyu Zhou and Sayak Ray Chowdhury. On differentially private federated linear contextual bandits. arXiv preprinl ar Xiv:23302. 13945, 2023.
Banghua Zhu, Lun Wang, Qi Pang, Shuai Wang, Jiantao Jiao, Dawn Song, and Michael I Jordan. Byzantine- robust federated learning with optimal statistical rates. Tn International Conference on Artificial Intelli- gence and Statistics, pp. 3151-3178. PMLR, 2023.
Yinglun Zhu, Dylan J Foster, John Langford, and Paul Mineiro. Contextual bandits with large action spaces: Made practical. In International Conference on Machine Learning, pp. 27428-27455. PMLR, 2022.
Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. In Abstract Conference on Measurement and Modeling of
Proceedings of the 2021 ACM CCCMETRICS/Inleraalann Computer Systems, pp. 3-4, 2021.
Weiming Zhuang, Yonggang Wen, and Shuai Zhang, Divergence-awarc federated self-supervised learning. arXiv preprint ar.i::2204.00 04385, 2022.
Lukas Zierahn, Dirk van der Hoeven, Nicolo Cesa- Bianchi, and Gergely Neu. Nonstochastic contextual combinatorial bandits. In International Conference on Artificial Intelligence and Statistics, pp. 8771- 8813. PMLR, 2023.
18

---

Published in Transactions on Machine Learning Research (07 2224)
A
Additional Discussions
A.1 Societal Impacts
design for federated contextual bandits (FCB), which establishes close relationship between FCB and FL. We do not foresee major negative societal impacts as FCB is well-cstablished rescarch domain and this work largely investigates its theoretical aspects. Morcover, as discussed in Section 6.2 FedIGW can conveniently incorporate appendages from FL studies to obtain appealing properties of privacy, robustness, fairness, and beyond, which we believe can contribute to a positive societal impact.
This work focuses on providing
A.2 Examples of FL Components in FCB Studies
An example of the FL components adopted in previous FCB studics is provided in the following, together with the renowned FedAvg protocol for comparison. Specifically, as in Remark 4.5 we consider the si stu
of federated linear bandits with a known d-dimensional feature mapping o(.,)) ). Then, Alg, illustrates the
FL component commonly adopted in Wang et al.] (2019) ; Li & Wang (2022a); Dubey & Pentland (2020); He
jet al. [002]: : the agents share compressed local data (e.g., covariance matrices) to the server for aggregation,
which happens in a one-shot fashion. simplified version of FedAvg (McMahan et al.] 2017) presented
in Alg. with client m's local loss function denoted as (m())) following Sec. 3 It can be observed that
FedAvg takes an optimization perspective to perform multi-rounds of gradient descent distributively.
The (simplified) FedAvg algorithm in existing studies on federated lincar bandits: one- an example of the canonical FI framework: multiple-
Algorithm 2 The FL component commonly adopted Algorithm 3
shot aggregation of compressed local data round aggregation of local model parameters
Input: M clients with client m's interaction dataset
Input: M clients with client m's interaction dataset denoted as Sn. = {(Im, am,7m Fm,7m) : Tm E
denoted as Sm (1 Om i Tm. Tm
[mm]]
[m]]]; learning rate !j 1: for == 1,2, do
Client m. with @(Em, amom denoted as
Om,mm compute V. t EImE(emm Tm, 2 Pn..
and
2: Client m: update 2/m +- +@mm 4
V-m (amm Sm)
bm + En E[mm] Tmm.... Pm,5m
3: Client m: send Am f- S - ~mm to the server
Client m: send Vm and bm to the server
4: Server: receive 4m from cach client m
Server: receive Vm and bm from each client 5: Server: with Eme[M]] 7'm denoted as n, send
4: Server: compute V + Eme(M] Vn and b
W f W -n En 2m Am to all clients
EmEIM bm
6: Client m: receive 4 from the server and set
Server: send V and b to all clients
am <
Client m: receive V and from the server
7: end for
A.3 Limitations and Future Works
While this work proposes novel, broadly applicable FCB design, i.e., FedIGW, there are still many inter- esting directions that are worth further exploring.
Paralleling CB and FL. As mentionod Scction 2.2 the current FL studies largely focus on learning from batched and static datasets. To accommodale such protocols, FCB designs typically follow a period- ically alternating scheme shown in Fig. [ which is thus the focus of this work. While such alternating designs are capable of achieving statistical and communication efficiency, there is still room for improvement: (1) the CB interactions need to wait for the completeness of a full FL process, which may be slow when computation resources are limited and communication delays are large; (2) it is desirable to use the CB data in a more timely fashion instead of accumulating to the end of an epoch.
As one variant of periodically alternating, we can have FedIGW interleave CB and FL as shown in Fig. 4(a) This approach provides some buffer to perform FL without agents waiting for its completeness. Especially,
19

---

Published in Transactions on Machine Learning Research (07/2024)
in epoch 1, on one hand, the agents perform FL with datasets from epoch 1 - 1; the other hand, they perform CB interactions following IGW with an estimated function f learned during epoch / - via datasets from epoch 1 1- 2. In other words, there will be one epoch delay compared with the basic form of FedIGW, while this delay is used for the FL process.
Furthermore, a better approach to have FL and CB fully paralleled as shown Fig- 4(b) Then, neither of them needs to wait for the other part, while CB data can be processed more timely. As mentioned in Section 6.2 believe that the framework of FL with data streams proposed in recent work of |arroq et al. (023 could be suitable tool, the sequential CB interactions essentially provide data steams. We believe this direction is not only worth further exploring in FCB but perhaps more importantly, calls for more investigation in FL with data streams, where FCB can also serve as an important motivation application.
CB
CB
CB
CB
CB
CB
CB
CB
CB
FL
FL
FL
FL
Provide data
+ Update parameterization
Provide data
Update parameterization
(a) Interleaving
(b) Fully Paralleling
Figure 4: Different Styles of Connecting FL and CB in FCB.
Incorporating other FL advances. Given the flexible FT. choice in FedIGW, although this work has provided detailed discussions incorporating many aspects of FL advancements (including canonical algorithmic designs, convergence analysis, and useful appendages). there are still many directions worth further exploration. For example, as mentioned in Section 2. this work and most FCB investigations are focused on collaborating through a central server, while the case communicating via a connected graph is less explored, where certain consensus errors commonly appear (Xin al.) 2020: Ye et al. 2020). is worth noting that the design and analysis framework of FedIGW are both applicable in the later setting, Especially, the consensus error can be modeled one part of the optimization further validates the value of the proposed FedIGW design and the general analysis framework while further specifications are left for fulure works.
in Lemma 43 This
Also, it would be great to leverage extra tools to save computations in the adopted FL protocol. Using local updates as in Chou et al. (2020) is one promising direction. These approaches are all feasible in FedIGW as long as the agents can obtain a learned reward function perform IGW interactions. Their specific impacts can be captured via the established analysis framework through their own optimization errors.
Leveraging other CB designs. With previous FCB studies largely focused the CB component, this work is motivated to incorporate more advances from FL. Thus, propose the FedIGW design which can leverage canonical protocols, convergence analyses, and flexible appendages from FL.
However, we also note that there are still many CB algorithms that remain under-explored FCB, where UCB-based designs are dominating. For example, the simple greedy algorithm is shown to be efficient when the context generation contains certain exploration capabilitics in (Han et al. (020). Morcover, varying attempts have been made in Xu & Zeevi (2020); Foster & Rakhlin (2020); Poster et al. (2020); Zhu et al.) (2022) to design generally applicable CB algorithms with tight performance guarantees, e.g., handling infinite arms. It would be interesting to investigate how to bring these designs to the federated setting and whether such connections provide new opportunities and insights.
Complex environments. This work is focused on a stationary environment with stochastic rewards, which is well motivated by practical applications and commonly adopted in FCB studies. To further broaden the applicability of FCB, we believe that it is also important to study adversarial or non-stationary envi- ronments. Many advances have been made in standard single-agent bandits, e.g., Auer et al. (2002) Neu &
20

---

Published in Transactions on Machine Learning Research (07 2024))
Olkhovskaya 2020]; Zierahn et al. (0023) Wei & Luo (2021) A recent work (Yi & Vojnović 2023 investi-
gates the federated adversarial environment in the tabular setting and further investigations are desired to provide further concrete designs and analyses.
Extension to RL. It would also be meaningful to extend the current study of FCB to federated reinforce- ment learning (RI.) as a further step in understanding the combination of FT, and sequential decision-making.
Some results have been reported in Dubey & Pentland (2021); Min et al. (2023) ; Jin et al. (2022); Fan et al.
(2021): |: Cisncros- Velarde et al. (2023). We hope this work can serve as starting point for more principled and generally applicable studies in federated RL.
B Additional Related Works
The studies on federated multi-armed bandits (FMAB) and federated contextual bandits (FCB) can be viewed as a version of the general multi-agent bandits (Liu & Zhao 2010 [Bursserr & Perchet 2019 Shi ct al. 2020 2021b) and parallelizing bandits (Chan et al. 2021 Karbasi et al. 2021] that is more suitable for modern applications. We provide a more detailed review in the following.
Tabular. There have been many studies on cooperative designs in multi-armed bandits (i.e., the tabular setting), e.g.. Hillel et al. (0013): Szorenyi et al. [2013): Landgren et al. (2016); Martinez-Rubal et al. (2019).
focusing on different learning targets and different commmicsttin protocols (e.g., through a communication
graph or with some randomly selected peers). Notably, in [Wag et al. (2019). commuicatiion-cffciontt
designs are proposed via periodically aggregating local estimates and performing arm elimination globally.
We here also discuss another line of works on FMAB (Shi & Shen 2021 Shi et al. 2021a Réda et al.) 2022;
Zhu et al., 2021. Chen et al.] 2002 Shi et al. 2023 In their considered sctting, the global rewards are (weighted) averages of local observations; however the former is not directly observable. With maximizing global rewards the learning target, the agents need to collaboratively perform explorations and aggregate local information. Despite the model differences, the design principle of FedIGW may still be beneficial for studying this setting. Especially, it is worth considering replacing the UCB-based explorations commonly
adopted in Shi & Sheni (2021); Shi et al. (2021a); Réda et al. (2022 Zhu et al. (202T); Chen et al. (2022)
with regression- based ones as in FedIGW to facilitate incorporation of FI. studies.
Linear. The most commonly studied FCB setting is foderatod linear bandits. There have been many investigations in this direction. Especially, different environments have been tackled in different works, e.g., the finite-armed fixed-context setting (Wang et al. 2019
Huang et al., 2021b), the finite-armed stochastic- context setting (Amani et al.) 2022), the finite-armed adversarial context setting (Fan et al., 2023), the dddersarial-contexx setting 2022). Furthermore,, many other settings, c.g., unobscrved context (Lin & Moothedath 2023), and additional properties, e.g., privacy (Dubcy
infiniteaarmed fixed-context setting (Salgia & Zhao
2022). and the infinite-armed
(Wang et al. 2019 Dubey & Pentland| 2020 Li & Wang 2022a: He et al.)
& Pentland 2020: Zhou & Chowdhury] 2023), robustness (Jadbabaie el al. 2022), have been investigaled.
As summarized in the main paper, these works mainly select arm elimination (AE) (Lattimore & Szepesvári 2020) or LinUCB (Abbasi- Yackori et al., [011] their CB dosigns, which require both model estimates and confidence bounds. Thus, in their designed FL protocols, compressed local data (e.g., aggregated local rewards and covariance matrices) are often directly shared to solve a global ridge regression and to construct tighter confidence bounds. Compared with these studies, FedIGW can effectively solve the finite- armed stochastic-context setting without sharing any raw or compressed local data but only communicate processed model parameters (e.g., gradients). More detailed discussions and concrete results are provided in Appendix D.3
A detailed comparison of the obtained regrets and the amounts of communicated real mumbers is provided in Table 4 It can be observed that adapting FedIGW to the specific case of linear bandits does not provide the same ncar-optimal performance as in previous works. This is not surprisc as (singlo-agent) IGW itself has not yet. been shown lo achieve the lower-bound performance of linear bandits, while the previous works are largely built upon the nearly optimal LinUCB design (Abbasi- Yadkori et al. 2011]. However, as noted in Remark 3.2 IGW only requires Icarned reward function, instead of complicated data analytics such as UCB, which grants great flexibility to better incorporate FL advancements and handle more general scenarios beyond the linear setting.
21

---

Published in Transactions on Machine Learning Research (07/2024)
Table 4: A comparison of settings and results of federated linear bandits; note that FedIGW is not specifically designed and optimized to handle linear reward functions as previous designs.
Reference
Arms
Context
Regret
# of Numbers Communicated
Wang ct al.
(0019)
Infinite
Fixed
MT)
O((dM + d log log (T))
He et al. 2022
Infinite
Adversarial
(TV
O(d M2 (Mg()
Huang et al.
2021bb
Finite
Fixed
(VVMT))
Old dK)M log(T))
Amani al.
(2022)
Finite
Stochastic
(VdNT)
O(dM log loT(M
Fed
Finite
Stochastic
O(VdKMT)
O log(T))
FedTGW>
Finite
Stochastic
Ó(VaKMT)
Oldd)) M
t: assuming homogeneous and known context distribution for all agents;
s solving the global ridge regression via directly sharing aggregated local rewards and covariance matrices as in the other listed works;
b: solving the global ridge regression via distributed accelerated gradient descent;
Gencralized Linear and Kernelized. As extensions of the linear reward functions, Li & Wang (022b) considers the generalized-linear class, and et et al. 22022 2023) study the kernelized one. The adopted basic techniques are similar to the aforementioned ones in federated linear bandits, while efforts are focused on fine-tuning communications (e.g., vía Nyström approximation (Li et al.. 2022 2023 ). It is worth noting that Li & Wang (202bb) invokes the distributed accelcratod gradient descent algorithm to solve their considered distributed optimization with generalized linear function class, which can be viewed attempt of involving FL distributed optimization designs in FCB. However, the motivation there is the lack of closed-form solution as in the linear case, while Li & Wang (2022b) additionally needs to share the local covariance matrices to construct better confidence bounds. This work, instead, formally proposed FedIGW which can rely only on canonical FL. framework and accommodate flexible FI. choices.
preliminary
Neural. A recent work of Dai al. (2023) extends the advances on single-agent neural bandits (Zhou et al. 2020) the federated setting, where the neural tangent kernel (NTK) analyses are incorporated. With NTK to "Tinearize" the considered weer-parameterized neural network, Dai al. (2023) still largely follows the designs in the aforementioned federated linear bandits while some additional attempts have been made, e.g., an extra one-round averaging of model parameters besides aggregating NTK. This work, instead, takes a step further to fully leverage FL. protocols, which often perform multiple (instead of one) rounds of model aggregations that are often necossary to guarantec convergence. Also, the optimization and generalization errors of a FedAvg variant with overparamettrrzzed neural networks are provided in HHang el al. (2021a), which is conceivably compatible with FedIGW for the corresponding analyses. Moreover, as shown by the additional experimental results in Sec. 5 FedIGW empirically outperforms FN-UCB (Dai al.) 2023 different tasks and is more computationally efficient.
C Proofs for Section 4.1
C.1 Notations
We first introduce notations that are repeatedly used. For the output function from the adopted FL protocol, characterize its performance via the following definition of its excess risk, which is commonly adopted in
the analysis of IGW-type CB algorithms (Simchi-Levi & Xu 2022 Sen al.
2021 Ghosh et al. 2021
Definition C.I. Let P[M] == {pm m E [M] be set of M arbilrary independent arm selection distributions.
Given an overall dataset Sjls == (Sm m E [M]} where each dataset Sm consists of nm training samples of the form (xm, Omi I'm (am)) independently and identically drawn according to (Im, Tm) ~ Dmn am Pml(-aae (m the federated protocol FLroutine(S(ng) (FLroutine,, (Sm) m E [M] relurns predictor f()), and its
22

---

Published in Transactions on Machine Learning Research (07 (024)
eacess risk is defined
{(Frmaa)= = Es
Rm Σ [M]
x Ditt am pm pm (1mm) (Tems (Imm am)
E
n
where [M)]] == {nmm : m E [M]] and & denotes the random source in the potentially stochastic FL algorithm. We often abbreviate EF;; m(M) as E(m()) to simplify notations.
This definition measures in expectation (w.r.t. the random data generation and the stochastic FL process) how far the output of the adopted FL protocol is from the true reward function on the weighted data distribution of all agents. Note that the excess risk bound E(R(M) would typically rely on some other parameters in the adopted FL protocol (c.g., the step size and the number of iterations in gradient-based approaches), which are currently not specified for generality.
Then, let T' denote the sigma- aggma-lgeeba generated by the history up to epoch I, i.e., {(Im,t. Om Tmm.m m E [ [r))), and the randomness in the adopted FL protocol up to epoch I, i.c., {E : [T]. where & denotes the random source in epoch i. Then, epoch that agent m's Im belongs to. Also, let V.. := Ax denote the set of deterministic functions from Xm [M]]. Furthermore, for any action selection kernel P[M] = {pm m E [M], where Pm (am [mm) is the probability of selecting action Om E A given context Tm, and any policy T[M] = {Tm : m E [M] E V, we define
denote in (lm) == min N In S (7 as the
to Am for agent and PM X V the Cartesian product of (
Vm (Pm: Tm) = E
sm D.
(m (I ( [f (I Tm (2m))],
Rm ( [mm) = am D.
R (Tm [|-1)] ;= E am DD
P (Imm Tm (m(()))) r
Regm (Tmm) Ry (T((TTa))
Rm (Tm);
Reg.. mm r(-1)= = Rymtnn (# r(-1) Rimt... (Tm r'-
where 71, (xm) == arg max am EAm. J (xm, am) for given p (determined by Tl-1).
The following proofs are largely inspired by the single-agent. contextual bandits work Simchi-Levi & Xu 2022), while major changes have been made to accommodate the more complex federated system considered in this work.
C.2 Proofs of Theorem
First, the following lemma characterizes the relation between the excess errors and the selected learning rates.
Lemma C.2. For all > 1, it holds that
Eyi-1
Σ
El-1
xmm D.x Comp ( ( (Plems am) - -0- (I am)) r
E
Em Em'E Fl-1
mE[M]
Eme(ny Et Km
< E(F; ((F)
Emelad Erin (1d)2²
Proof. The first incquality is from the Assumption C.1 while the second is based on the choice of 7 in ie.,
Theorem
Eme[M Et Km
EmErM E {
23

---

Published in Transactions on Machine Learning Research (07 (024)
which leads to the lemma.
Then, the following lemma bounds the estimated rewards R2 and true rewards Rm.
Lemma C.3. For any epoch > 1, for any Tm E mm conditioned on T!-1, holds that
(Tm ( Rm (Tm) S v Vml(pii am (1-1) -
where - = Bimiii oom 2 Amphn ((lem) withi
(F a -f (2 )) |
Proof. For simplicity, we abbreviate E, ~ Dim amm rop'm (11mm))) as and any epoch I 1, we define
am - [t, and for any policy am E V m.
A m
(T (Tm( (Fm)) = P (frm Tmm (Frm) - S (Imy Tem (Fm))
which indicates that
R (Tm T (1--2)- - Rm (mm) Brn A (Te (2m) [T]
and
E
Pm dim 1-1
(A 1)
| Exm p (2mm) (Tm(m(()))))) r--1]
Furthermore, conditioned on T!-1, we can obtain that
Vm Vm 1-1 Tmm T(-1).
(1 rl-1]
vam (-1
Ex.
1
g1-1
Bemaati
(an r
p'm
(T (F (2m))
f-1
| | 1)
B Boy (A (atn (attn)))²
Exn
1-11 1 (m (2m) [2m)
Pm
1
pia (TTm (1m)) (mmm) (Ain (Tm (2m))) |r(1] ))
I- (m (2 (2mm) pm
(Ezm A Am (Tm (Im)) xp 2)-
2
Rym (Tm (1-1)= Rm Rm((Tm) (TTm)
As result, it holds that
Rum Tm p(-1)- Rm (mm) S V Ven(enn Fm ((-1) (
where the last step we use the definition that
(P(Em, (211) - fd (zm) ) p
E sm ain
This concludes the proof.
Furthermore, the following lemma provides characterization of the relation between the virtual loss and the true loss Reg
Reg
24

---

Published in Transactions on Machine Learning Research (07/2024)
Lemma C.4. For any epochs 1 1, for any policies T(M) IM,,, it holds that
Σ
Fm Regm (TTm) 2
Σ Em x
Regm (Tim
r1 + +1/
m
mc(M/
Σ Eyi-
Regm (Tm
(
2 Σ
E Em Regm (Tm) + +1/
mE(M]
ME[M]
with
9c²
n/
Σ
Km
mEIM
Proof. First, we note that for 1 == 1, it holds that
Σ
E Reg. (Tm) I Σ
E S 51 = 9c²
Σ E Km:
mE[M]
mE[AX]
Σ
Em Regm (Tm) = 0 S 1/ = 9c
Σ
E Km
mE[M]]
me[Md]
which means the lemma holds for the first epoch.
We then perform inductive proof and start by assuming that for epoch 1 - 1 and any policies am E W it holds that
Σ mE[Md]
Ey EI-'Ree Regm (Tm) 2 Σ
E
1--
Regm (Tm [ + +11²1
MEIM
Σ D'-'Err-
1 Regm (Tm | 2 Σ
En 'Re (Tm) + +1
ME[M]
mE(M
Then, it can be observed that
( Rogm (Tm 1(1
= Rm ( - Rm (Tm) -
Rin (# (((1))- Rı (Tm |r(-1)
I Rmm (TT)
Rm (mm)
R (mmm x Ri (Tm p(-1))
Rm (mm)
R/ (xm
rl-1) Riy (mm r(-1)- Rm (mm)
Vm (p'm
Tm (' ('-1)
gl- (r--1) + Vm (p'm Fm r(-1) E/h (ri-1)
Vm (p/m Im T 11-1)
Vn (ptt Tm r1-1) 40 e (
<
8cy
8c7
( Km + 1 (T (l-1)
Km +
(Tm rl-1)
+ 407 E (
Sey!
8ey!
where incquality (a) is from Lemma
C.3 and incquality (b) is from Lemma C.10
Then, summing over all M agents, we can obtain that
Ex--1
Σ
Ey (Reg,, (Tm))
Regm (Tm 1
mE(M)]
EmElay
Fy, Km
Σ
Fyy Ey--1
(-/l- Regm ( r(-1)]
4cy!
8e7
me(M]]
25

---

Published in Transactions on Machine Learning Research (07 (27/))
Σ
Em Byi-1
Regm
(Tm
+ 407
Σ
Em Eyi- | (r--1)]
8e7
MEIM
mc(M]
(4) E m
EL Ki
1---1
Σ
En -
Regm
(m
r(-1))
4eyy
807
mE(M]
0-1-1
Σ
E Eri 1 Regm
(Tm | + 407/
Σ
Ex Fyr
[
8cy
mE(M]
mE[M]
(e) Eme[M (M]
Ey Km
Ty--1
Σ
E (mm)
-ny-1
4oy
4071
4cg
mEIM]
+ Acg Σ
Fy Eyi-1
mE[M
(n E EmEIM [M]
E
Km
9c E'Eia (M]
E Km 4c² EmEEmian ar E'm Km
Σ mE(M]
Fy Regm (Tm)
4cy
47d
where inequality (d) is from the definition č = maxxm([M))/IR.KTT) induction assumption that
Em/ E Inequality (e) is from the
Σ mE[M]
Regm 1-1 (I
Σ
P'm By--2
1-1 Regm (m |
me M
2
EL- Regm (TTm) + +1) 1//=1 = 11/
mc(M]
Σ mM(M]
E1-1 Ex--1 Regm (Tm
r = Σ
Ey El-1E -r--E
Regm. (Tm | (1-2)
me [
2
E Regm (Tm) + 111-11
me
Inequality (f) is based on the definition C := minme El E c := a/e and of == 2c.2 Eme(M E Km /T1, also the assumption that nt 2/1 and Lemma C.2 which indicates that
Σ m F Km (gd)²
Ey--1
Σ mE(M]
E (
Thus, we can obtain that
3 Σ
Ey Rog (Tm)
Σ
Ey, Eyi-1
Regm (mm (T r(-1)]
E Eme(an Ey, Km 40y!
4 mc[M]
mE(M]
25c²
EmE(M]
MM]
El Km
+
47
Σ
El Reg (Im))
S
4
Σ
Ey Exy
Regm(
| 1 + Eme(nn (Mn] Ei,, Km
30ny
mE(M]
mE(M]
25c
ΣmE(M
El Km
47
< 2 Σ
Regm (Tm [(-1 +n
mE(M]
26

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Also, it similarly holds that
Regm mT 1 Regm (Tm)
(f 1 Rm
T T(-1)- - (Rm (R((mT) Rm (m (TT))
Rim (#
) - R/n (Tmm
r(-1) ) - (Rm ( Rm (Imm)
Rym (T 1(- Rm (Fmm)
+ Rm (Tm) -Ry, (Tim |
V Vmmlpml Th (T-1) // Em (T--1)+ ( + v V/nllti (ytr Tm (T--1) Et - (T--1)
Km + tn Regm ( 1(-1) Km + +
Regm
(Tm (T--1) 1 (r'-))
807!
8c7
Then, summing over M agents, we can obtain that
(1--)- - Regm (mm))
Ey--1
Σ
F
Regm (T
MEIM
Σ mE [M)
El Km
oy1-1
Σ
Regm (A |(-1)]
4om
80g
mE(M)
/-/-1
+
Σ
Ey L
Regm
(Tm [1 + 407
Σ
Em Bri-1 (
8c7
ME(M]
mE(M]]
EmElM Fy Ki
Σ
E Ery-
Reym ( |(-1)]
4cgy
4en
mE(M)
TH-'Regm (Tm) + cgl-11
Σ
11--1 4e7 Σ
E' (T)-)())
+
4en
4cgd
mE[M]
mE(M]
( Eme(N] [M]
Ey Km
7-1
11) + 4
Ey Regmeg (Tm)
1c7
mE(M]
+ 2-
-7-11 sen'
Σ
Ey Ey [E (T)-))
me(M]]
E
[me(M] Ey Km
20
Eme[M
M
El Km
Σ mE(M]]
Ey, (Tg
Ac71
47'
Emeln EY Km
4o² Emejan Ey, Km
+
4y
where incquality (g) is from the previous derivation that
Σ
E Reg (
[ < 2g Σ
Ey Reg ( (1-1) + enn gi
M
M
Thus, it holds that
Σ ME(M]
ET!
Regm
1-1 /o (
|
S
5
Σ
Ey Reg, (Tm)
mE(M)
Eme(n)] Km 407
17c E
Eme(N)] 27
E Km
27

---

Published in Transactions on Machine Learning Research (07 (274))
Σ
E Eyi
Regm.
(
|(-1
22 Σ
Regm (Tm) +1y.
MEIM]
MEIM
With those two parts, the lemma can be obtained by induction.
Furthermore, the following lemma provides characterization of the per-epoch loss of the federation. Lemma C.5. For every epoch I > 1, conditioned on T it holds that
11c
Ex
Σ E
Σ
Qun (T (l-")Reg (Tm)
Σ
Em
ME[M]
mE
M
where (---((-1) is probability measure on L defined in Lemma
C.7
Proof. For any probability measures 14 m E [M]], where (-)()) is on Mas it holds that
Σ E Σ
Ønn (Tm) (Tm)
mE[Md]
E
(a)
S 21E'T
Σ
('(TIA))
Σ mEIM
Ey Regm (Tm 11-1) +
Mlar [20)
= 2
Σ
Ey m
Σ
D'n (T Regm (Tm ((-1)
+ +n',
mE
M
Wm E. am
where inequality (a) is from Lemma C.4 and @' (TT = IIME (M] O' (Tm)- Thus, we can obtain that
By--1
Σ
E m
Σ
Im (Tm r( Regg (mm)
mE[M]
Kim W
< 2E
Σ
E m
Σ
I'm (Tm -1 Regm (am r + +n
ME[M]
Tye EVm.
(b)
9c
Σ
Ed Km
+
Σ
Ey Km
mE[M]
mE(M]
1
Σ
EL Kmi
ME[M]
where incquality (b) is from Lemma
C.9
With the previous lemmas, can obtain the final Theorem 4.1 which is restated in the following.
Theorem C.6 (Restatement of Theorem 4. Using learning rate
00=
Σ
Σ EL E ((()))
mE[M]
mEIM
in epoch 1, denoting K = Emer Emelan] Ey Km/ EmEJM Ey, the regret of FedIGW can be bounded as
Reg(T) =
Σ E
Σ at V
Σ E
ME
(E(.T()
mE(M]
28

---

Published in Transactions on Machine Learning Research (07 2024)
Proof of Theorem
The expected regret can be bounded
Reg(T)
Σ
Σ
(Fm Tmm (mmmm))) S (Fm,,t am.mm)
mE[M] Em E[2ml
< E2
Σ
E
(f Tim (2 f (2mm ami ))
Σ E
[E(2)((T) mE[M] im El (r' (+-
mE(M
Exi-1
Exm,e ele
Ex
Σ
Em (f* (I The (Fmm) f (I am)) pt-1 T
E
(e(2.(TT)
ME(MM
me(ar]
Byc-1
Σ
E
Σ
Om (Tm
T 1 1R-"Reem (Tm) pi-1
Em
(E(,
ME[M]
me [M]
1 (E(,((T)
Σ
Σ
EmKK Km
Σ Ey
?"
ME(M]
ME(M)
EmEiM Ein E(F; (MM)
Σ (E(2((T)
l
Σ
E Km + Σ
Ey
Eme(M] Em Km
mE[M]
mE(M]
Σ [ERIT
11d² V RE(F; )
Σ mE[M]
El-1 m
Σ El mE[M]
where equality (a) is from Lemma C.8 inequality (b) is from Lemma C.5 and inequality (c) is from the choice of 7/. The proof is then concluded.
C.3
Supporting Lemmas
The following supporting lemmas can be similarly obtained by the corresponding proofs in Simchi- Levi & Xu
2022).
Lemma C.7 (Lemma Simchi-Levi & Xu 2002)). For any epoch I N, conditioned on r there ewists probability measure Qi (-|--1) on V such that
Vam E Am, vam Xm,
p'm (am Wim: rh-)=
Σ (mm((mm) am 3m Qt (Tm) (
Tm E m
Lemma C.8 (Lemma 4, Simchi-Lev Levi & Xu 2022 Fix any epoch E N, we have
B am Dim Mpn (1)m))
[5 (Imy Tt (Fmm) (Trm d'n) r--1]
Σ
Q' r ('-1) Regm
Tem E Vm
Lemma C.9 (Lemma 5, Simchi-Lews & Xu
2022 ). Fix any epoch E N, conditioned on Ti-1, we have
Km 7
e (T
rl
Regm (m |1-1)
Lemma C.10 (Lemma 6, Sinchi-Levi & Xu
2022
Fix any epoch N, for any policy Tm V m,
have
V Vin(pnn Tm rl-1) < Km Regg (Tm rl-1).
29

---

Published in Transactions on Machine Learning Research (07 (07/2024)
D Proofs for Section 4.2
D.1 Proofs of Corollary 4.2
First, with realizabilityy, i.c., Assumption 3.1 the following characterization can be obtained.
Lemma D.1 (Lemma 4.2, Agarwal al. (2012)). Fix a function f E F. Suppose we sample am I'm from the data distribulion Dm, and action om from arbitrary distribution such that Im and om are conditionally independent given Zm. Define the random variable
(m( (I 0m) T' (ma(am))² (f (I am) I'm (m((m)))
Then, we have
Bar mmmmm [m) = Be [U( am) - S (Imm, am))
and
V Rm I'm Om [mm( S 41 4l I' Om [L (f)).
where VH denotes the voriance of random variable.
Then, we establish an upper bound for the excess risk bound required in Definition C.1 via the following lemma
Lemma D.2. Under the setup of Assumption C.1 if the adopted FL protocol provides an eract minimizer for the optimization problem Eqn. with quadrutic losses, i.e.,
arg minginn f=
DEΣ Σ
(f(2'm v -
fEF T
then, with probability at least 5, it holds that
7mm E
(Teem (mm) f (3im: am) am)) )"
25 Log([
am D. am pm (mp(m
n
M
As result, Definition 0.1 holds with
E(,, mMM) (log((Fln)/n).
Proof. For simplicity, abbreviate the quadratic loss associated with fixed function f F as
(n) = lm (x ( (s(#)n a( )
Vm E [M].
Then, with a probability at least 8, for a fixed F, it holds that
Σ
Σ
- - (5*)
Σ Σ
(e) er (f*)
mc [M]
km [rema]
mE [mm]
2
Σ
ae mn 1ein Cg (f log + log (1/8)
4
ME(M] im ((pm))))
Σ E Sr at, (0 - 0r (og) + log 1/5),
M im E(Nm)
where inequality (a) leverages Bernstein's inequality and inequality (b) is based Lemma D.1
30

---

Published in Transactions on Machine Learning Research (07 (07/2024) /024)
With
x(f)
Σ
Σ
Exi Pii (f)(f) - f (f*)];
mE[MI Yom E/mm]
z(f) = Σ
(f) -m,f))mmmi(0 (f)))
C= Vlog(1/0),
ME[M) LE [mm]
applying a union bound the above inequality indicates that with probability [F for all f E F, it holds that
x - z(f) 1 44X( 3 c² - Z(f) - 16 C².
3
Since J satisfies that z(f)= - O, can obtain that
x
In other words, with probability 1- 5, it holds that
[flvtis ain) - rim) ) (5 ain) )²m)
Σ
B rit on
me[M]] i.. E [m.]]
=
Σ
Tem Bug al
(Fraims - - ( a(m))) < 25 [og([FF/O0))
ME(M]
where the equality is from the realizability in Assumption 3.1 The first half of the lemma is then proved. With 5 = 1/n, the second half can be obtained as
nmm Σ
(I(Em: am) - I (a 0m)) )
25 (og(((FF))
ESIM
Ex am
n
11
n
mE[M]
which concludes the proof.
Based on the established excess risk bound, Corollary 4.2 can be obtained as follows.
Corollary D.3 (Restatement of Corollary 4.2
If F and the adopted FL protocol provides eract
minimizer for Egn. (1] with quadralic losses, with r 21, FedIGW incurs regret of
Reg T) 0 (M
and a total O(log(T)) calls of the adopted FL protocol.
Proof of Covollary 42
With Theorem 4.1 and Lemma D.2 under the choice of 7! 2¹, the regret can be
bounded as
Reg (T) 0 ME +
Σ
V KME log( (FIME)))))))
(E(2.((T)
=0
Σ
KM2
[E(2, (T)1
=0 /K/ (M(
and the exponentially growing epoch length naturally leads Olog(T)) calls of the adopted FL protocol, which concludes the proof.
31

---

Published in Transactions on Machine Learning Research (07 (024))
D.2 Proofs of Corollary 4.4 and Additional Results
In the following, first prove Lemma 4.3 while also noting that this result is general and does not rely on the specific parameterization of F, although we presented it with the d-dimensional parameterization considcred in Scction 4.2
Lemma D.4 (Complete Version of Lemma 4.3
If the loss function 4m(3)) is ju strongly convex in its first
coordinate for all m E [M], i..,,
1m (21;:2) Im (21;
dlm (21 22)
(zi - -12
Mí (z1 21) for any 21, and 22;
dæ1
2
and
inf Er Imm (y, I'm (am))) aml = Er [[ (Im, am); ; I'm Tmm(mm) (mn))) Tms aml BER
(3)
for all m [M], (F am) E Xm Am Definition
C.1
holds with
m(F: 2 2 (Eape(F mpn) Egen (F; /pf
where
egen(Fi : Es.e(f(Sag) ((55;:))
Capa Cepe(Fimpo Finna)) = F.../[((f [()=
Proof. First, for any Ws, holds that
((f5))
C(fw-)
Σ
Thm Eur B.m.t..mm...mm..
[e (Imis am,): Fm,s) {( (Dm,is (m,
n2
ME|M]
H1
Σ
I'm
Ezm.i amii (Fos (Fm,s) am,s) - for (Fm,it am.)) )
E
2
n
ME[M]
where the inequality is due to the strong convexity of l(::)) w.r.t. its first coordinate and the optimality of fur assumed in Eqn. (3. Thus, obtain that
nom E aimm (Fas (Im, am,)) - for (Zm, am.))) Σ
2 )
(C(ts)) -((w)))
My
MM[M]
Furthermore, holds that
Es.E (())s)) )] C(fwr)
Es. (C(=>)] )
Es,. [[(Fog: :S]
+ Es. [ :s]
L(Jw-)
E.s. (CW/s))
Es, [Z(lag:
+ Es, [(Ung:
-Es. [[lug:5)]
where the last incquality is due to
C(fa:) = Es [[ 2 Es [[lug
The proof is then concluded.
Then, for the generalization error analyses, the following lemma can be obtained via standard proofs (c.g.. Theorem 6.4 in Zhang (2023); Theorem 3.3 in Mohri et al. (2018)).
32

---

Published in Transactions on Machine Learning Research (07 (07/2024) 2024)
Lemma D.5. It holds that
Egen (e == Es.((((E DWSs ([lis;5)] ; S (PR(F;man))
Here, the distributional- upper bound M(F;n(M) on the Rademacher complerity defined as TE(n..)
R(FFuMM) = sup B
sup
Σ
Om,i en (Sw (w ama)) (mma)
(4)
T2
ME(M]
where the outside supremun is over possible distributions of dataset S defined in Definition C.1 and the expectation is w.r.t. the generation of dataset StM) following fixed distribution and independent Rademacher random variables o = (Om.i: m E [M].i E [mm]]]
The optimization error of FedAvg McMahan et al. 2017 and SCAFFOLD (Karimireddy et al. 2020) are presented Appendices and F.2
Combining the generalization error and optimization error via
Lemma 4.3 into Theorem 4.1 Corollary 4.4 can be obtained, which is restated the following.
Corollary D.6 (Restatement of Corollary can be bounded
4.4
Under the condition of Lemsaa 4.3
the regret of FedIGW
Reg(T)
.ME+
Σ 1E(2J(())
K (R- +ooott)) /PyME!
where R¹ := R(Fi m E [M]}) and using p rounds of agents-server communications (i.e., global aggregations) and xt rounds of local updates in epoch I, under certain assumptions,
with FedAng as FLroutine()) if (aa is Usssonongly conver and Bu-smooth w.r.l. w for all e [M] while the gradients are unbiased, have a of bounded variance and have a Go-bounded dissimilarily, the output for satisfies that e'ogt == (F: S ( + 2), when p 2 S2 pm)
(see Lemma F.1 for the full statement);
with SCAFFOLD as FLroutine(.), if (miJii: is Pu-slrongly conver and Ss-omooth w.r.l. for all m E [M] while the gradients unbiased and have of bbuunddd variance, the output For satisfies that (F; m/ s Ö (p M)) when p p)) (see Lemma F.O the full statement);
c'opt = (F;
By further setting a suitable number of global aggregations for each epoch such that the optimization error is on the same order as the generalization error, the following more specific corollary can obtained for FedAvg and SCAFFOLD, which can be casily extended for other FL designs.
Corollary D.7. Under the conditions of Lemma and Corollary D.6. FedIGW incurs a regret of
Reg (T) O ME'
Σ
V KNN /KNN-1NN /
(E(2.((T)
with the following bounds on the rounds of communications
Sw
Gr 12
Σ
(using FedAAg);
Mu
(E(((T)
Bu
of Mhe
Σ
(using SCAFFOLD),
Mu
JE((Ty
where 3e : R(F[M) (F [M]) and ve is the number of local updates in epoch l.
33

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Proof. From Corollary D.6 when using FedAvg the adopted FL protocol in FedIGW, the optimization error in epoch 1 of form
of Hudd 12(d)
BuGE
when X¹ = (bw) Thus, the communication rounds
o' = (Be
Bw + Hw HW
of
G 1o
are guaranteed to have the optimization error on the order of O(R)).
Then, the regret in Corollary 4.4 is of order
Reg( (7) = ME. +
Σ
(E(2.((T)
while the overall communication rounds can be bounded as
Σ セー ò
Σ
B
of ROREM
Ba B.G p DN!
Mw
I
(EB(T)
(EN(T)
which concludes the proof for FedAvg. The result of using SCAFFOLD can be similarly obtained.
D.3 A Linear Reward Function Class
We here provide a detailed discussion on the linear reward function class considered in Remark 4.5 at the
end of Section 4.2 Especially, following standard assumptions in linear bandits (Abbasi Yadkori et al.,
2011) and federated linear bandits (Li & Wang, 2022a He et al. 2022 Amani et al.) 2022), we consider Pm (Tm, 4m) (0(Im, wm), where <(-) is known d-dimensional mapping and w" is unknown d-
dimensional system parameter. Then, it is sulficient to consider a linear function class F, where f=(() (w, Φ())) and (.) = (w", ((-)). Moreover, for convenience, we assumee that ||ő(Im, am)ll S 1 and ||o*||a S 1.
As mentioned Remark 4.5 the FL problem can be formulated as a standard ridge regression with
em (Ju(Em, am)) rm) = ((w, p( am)) vm)) 2 + AlIwo112.
In other words, Equ.
can be restated as
min [(
E Σ
Σ -
(lla rmm) + Al(w1l
(5)
WER
mE[M] sE(nml]
which has an exact minimizer as
1 Σ Σ
1 Σ Σ
w/s-
af 2' dn + AI
Ll on )rir
(6)
mE(M [M]
iE kE(m...
mE(M] FE RE(D..)
We provide an excess risk bound required in Defimition C.1 through the following decomposition:
nem Ex am ((os, Φ(xm am)) (w",, 6(mm 2))
Ess.
[E(M]
34

---

Published in Transactions on Machine Learning Research (07 (27/))
pkm E Es Rm (f0s, @a am)) - (wSs ((am (m))))mm))) am))
< 2E
mEiMi
Thm E Ex am (WW's (f am)) (wr D( am)))
n
mE(M
|Iās -2Es,E
willis
Imm E Ex am (1r's paams am)) (w, )(Fm;amm)) am)))²
21Es
n
< 2E
Amax (2i) ||0s w
term (A)
2
Tom Ex (1r5s p( am)) (w0 p0(5
mm)))² am)));mm))
term (B)
mE(MF]
where
:= Σ Bym MEIM]
Eer, am [o am (m am)
n
and Amax (2) denotes the maximum eigenvalue E. With [1(( S 1, it can be verified that Amax S 1. In the above decomposition, term (A) can be interpreted as the optimization error, while term (B) is the generalization error.
We can then plug in the aforementioned explicit formula of wt into term (B) and demonstrate that term (B) = (dd/n) with 1/n under the assumption that ||w*||2 I and rm E [0 (e.g., following Theorem 9.35 Zhang 2023 ).
For the ridge regression problem in Eqn. previous designs federated linear bandits typically (Wang ct al. 2019 Dubey & Pentland] 2020 Li & Wang 2022a He et al. 2022 Amani et al. 2022 have agents collaboratively provide the exact minimizer in Equ. 6 via directly communicating their local rewards aggre- gates, i.e., Eigin.)) ((5'm (( "ri and local covariance matrices, i.e., Eiemnn. ((F) o ( )T))T Thus, round of agent-server communication is sufficient, where O(Md?) real numbers are shared. However, directly sharing such compressed data is often undesired in FL studies due to privacy concerns. We refer to this protocol as the "direct method" for simplicity in the following discussions.
With the ficxible FL choice in FedIGW, can accommodate many other efficient optimization algorithms. In particular, a distributed version of accelerated gradient descent (AGD) Nesterov 2003) takes only log(//)))) rounds of communications of gradients to have an optimization error of e', where is the condition number (i.e., the ratio between the smooth and strongly convex parameter in the consid- ered problem). With À 1/n, it holds that O(n); thus O(vni ((Vllo/(//)) rounds of communications of gradients are sufficient to obtain an optimization error of order Ö(d/n), where each agents' gradients are intuitively d-dimensional.
With the above illustration, the following corollary regarding the performance FedIGW with a linear reward function class is then a straightforwar extension from Theorem 4.1
Corollary D.8. In the considered linear reward function class with shared true parameters, using the direct method or distributed AGD as the adopted FL protocol to solve the FL problem in Equ. and 7! = 2¹. FedIGW obtains a regret of
Reg( (T) =
Σ
Kd
M2 =0 -O(MKKTT
M2
IE (E(logg((T))
35

---

Published in Transactions on Machine Learning Research (07 (224))
and the amount of real numbers communicated con be bounded
Σ
Md
(og))
(using the direct method);
(T(]ORg(T))
o
Σ (e()oga(T))
Mdv M2' log d (M2'))
(dglogd M
(using distributed AGD).
E Details of Section 6
E.1 Personalized Learning: Details of Section 6.1
Additional details for the personalized learning setting in Section 6.1 discussed here. In particular, the overall algorithm structure still follows Algorithm ! while the major difference is that personalized FL problem is considered:
;Span) = Σ
1mm mc(M]
Em (Jur Sm), Smm)
min
w wo(an)
n
where
Emllsaaat we: (m) = Dm mm(mm
Σ
lm EmlJwa,aae (I a rmd
Furthermore, bound the generalization error, similar to the Rademacher complexity in Equ. a slightly
different Rademacher complexity is introduced as
((FM) = sup
Es.
sup ( [M
Σ
Σ Omii - em (ml (I a'mi
ME[M]
iE pmml
which suitable for the considered personalized setting with parameters [w (w?,wfar) involved. A similar
notation is also adopted in Mohri et al. (019
The following corollary can then be established for the personalized version of FedIGW with the LSGD-PFL algorithm (Hanzely et al. 2021) adopted solve the personalized FL. task.
Corollary E.1. Under the conditions of Lemmas 4.3 and F.7 FL protocol, FedIGW W incurs regret of
with LSGD-PFL as the adopted personalized
Reg(T) = .ME+ +
E
KR KRV-1/HM
(E(2.(T)
with
Σ max Bus (w') Bwa + 03 (u -1 -1 + ( (E(U(T)
(G2 )
rounds of communications, where 2 P(F(M), (E' m E [M]}) and at is the number of local updates in epoch!
The proof largely follows that of Corollary D.7
dccomposing excess risk to generalization and optimization errors; using Rademacher complexity to characterize the generalization error; using FL convergence analyses to characterize the optimization error; and combining them together such that the optimization error does not dominate the gencralization error. As the LSGD-PFL, protocol (Hanzely et al., (2021) is adopted to solve the personalized FL task as an illustration, corresponding convergence analyses should be incorporated, which is presented in Lemma F.7
36

---

Published in Transactions on Machine Learning Research (07 (024))
E.1.1 A Linear Reward Function Class
As an extension of the linear reward function in Appendix D.3 we consider that
Pm (Tm, am) (mm am). wm)
Vm E [M], (Tims Am) E Xm Am:
and the true model parameters {wn, m [M]} follow Assumption 6.2 i.e., w [W whil with w shared among all agents.
It can be further realized that the above problem setting is identical to d-dimensional linear system, where d = d + Eme[an] dm: the overall true model parameter is
wT
+.9 W M
E
:
and a correspondingly feature mapping o(-) is
@aEm am) = (0(Em Om mmdd) O22, i Oga dh O{Ims am) +1dddml O d2
i.e., an expanded version of the original feature, where p(ām; Om) E Ri++1 denotes the sub-vector containing [i: j]-th elements in @(zm. am) and O E I'' an i-dimensional mull vector.
With this reformulated problem, discussions from Appendix Corollary D.8 indicates the following result.
D.3 can be directly leveraged. Espocially,
Corollary E.2. In the considered linear reward function class with partially brue parameters, using dis- tributed AGD as the adopted FL protocol to solve the FL problem in Equ. ( with reformulated feature mapping ò(-) and 7' = 22, FedIGW incurs a regret of
Reg(T) = (VVVkár
and the amount. of real numbers communicated can be bounded as log(d" /M3T).
E.2 Robustness, Privacy, and Beyond: Details of Section 6.2
We here provide some additional discussions on incorporating appendages in FL studies to provide robustness and privacy guarantees for FedIGW among some other directions, e.g., fairness guarantees (Mohri et al. 2019 Du ct al., 2021), client selections (Balakrishnan
al. 2022 Fraboni et al.) 2021), and practical communication designs (Chen et al.] 2021 Wei & Shen 2022 Zheng el al. 2020). The key is that as long one FL protocol can provide an estimated function f (which is used in 1GW interactions), can be adopted in FedIGW; thus the desirable properties of the selected FL protocol are naturally inherited to FedIGW.
For example, Yin et al. (2018) Pillutla et al. (2022] Fu et al. (201 Li et al. 2021 Zhu et al. (2023) studied how to handle malicious agents, who can deviate arbitrarily from the FL protocol and tamper with their updates, during learning. The commonly adopted approach to invoke certain robust estimators (e.g., median and trimmed mean). Under suitable assumptions, existing approaches have shown that as long as the proportion of malicious agents does not excood a threshold (typically, 1/2), the estimators calculated by federation can still converge within certain amounts of error due to the malicious agents. A recent work (Zhu et al. 2023 provides summary of convergence rates with different robust estimators, which can be leveraged to establish theoretical understandings of FedIGW with robustness.
On the privacy side, many mechanisms have also been studied in FL (Wei et al. 2020 Yin et al. 2021 Liu
et al. 2022), to guarantee differential privacy (DP), where the most common approach is to insert noises of suitable scales. Convergence rates have also been established under suitable assumptions, e.g., in Wei et al.) (2020 Girgis al. (2021): Wei al. (2021). With those analyses, the theoretical behavior of FedIGW with DP can also be similarly established Corollaries D.7 and E.T
37

---

Published in Transactions on Machine Learning Research (07/2024)
F
Algorithm Sketches and Convergence Analyses of FL Designs
F.1 FedAvg
The FedAvg algorithm (McMahan et. al. 2017) is of the most standard and well-adopted FL protocol. Following it, agents perform local stochastic gradient descents (SGD) with their local objective functions for certain steps and then communicate the updated local models to the server; the server aggregates local models to a global one via a weighted average, which is then communicated to the agents to perform further local SGDs.
Many theoretical analyses have been provided for FedAvg (e.g., et al. (020bb)). We adopt the one from Karimireddy et al. (2020) in the following.
Lemma F.1 (Theorem in Karimireddy et al. (2020] without client sampling). For any dalaset S, if
(m(fw Sm) is st-sorlyyly conver w.r.t. w (see Definition F.2 for all m E [M];
(m(wwiSm) is Bw -moothhh w.r.l. w (see Definition F.3) for all m E [M];
the stochastic gradients are unbiased and have of oo-boddde variance (see Definition
F.4
the gradients have Gs-bounded dissinilarily (see Desinition F.5
with FedAvg as the adopled FL prolocol, the oulpul io satisfies that
EelE(fag:S) E(fugi [8]5 (
of MepkM
BuGB 12pp + Mellwo - wōll2 exp (- MwP
16,3 ))
when p 2 88m, where denotes the round of communications (t.e., number of globol aggregations), is the Phe
rumber of local updotes (i.e., SGD) between each communication, and w is the initialization. Note that the last term which decays exponentially w.r.t. p is omitted Corollary D.6 and the following derivations for simplicily.
A few definitions used above are made precise in the following, which are inherited from Karimireddy et al. (202)) and presented here for completeness:
Definition F.2 (Strongly Convex). (Sa:S) is psrronoggly convee w.r.l. for pa if
(fwis) 2 (m( -
(fu w w) + Mu lew - wll2. for any w and w'
2
Definition F.3 (Smooth). (m:(fw:S) is Smooth w.r.t. w for B. > 0 if
- (TT (fu: w)
Bo l|w0 will. for any and w'
Definition F.4 (Stochastic Gradients with Bounded Variances). The stochastic gradients have of bounded
variance if
Σ Vulmifu(sh (id) V (m s soj for any w and m.
Pym
[E(mmn]
Definition F.5 (Gradients with Bounded Dissimilarity). The gradients have a G bounddd dissimilarity if
1
Σ (fa: / G for any w.
M mE(M]
38

---

Published in Transactions on Machine Learning Research (07 2024)
F.2 SCAFFOLD
The SCAFFOLD algorithm is proposed in Karimireddy et al. (2020), which enhances FedAvg via leveraging variance reduction to correct drifts in heterogenous agents' local updates. The following result is established in Karimireddy ct al. (2020) to characterize the convergence of the SCAFFOLD protocol.
Lemma F.6 (TThoorm VII in Karimireddy et al. 20200) without client sampling). For any dataset S, if
(mwissmm is ptrsonyg conver w.r.t. (see Definition F.2) for all [M];
Lm (Jwss Sm) is -moshh w.r.t. (see Definition F.3) for all m E [M];
the stochastic gradients are unblased and have oī bounded variance (see Definition F.4
with SCAFFOLDD as the adopted FL protocol, the output to satisfies that
of ( mw exp (-min Eg [E((( [(fwz: S (Mepee
MwP
30 1623
when p maxx 1628 30), where p denotes the round of communications (i.e., number of global aggregations), Re
is the number of local updates (t.e., SGD) between each communication, D is distant measure w.r.t. the imitialization defined in Karimireddy et al. (2020). Note that the last term which decays exponentially w.r.t. is omitted in Corollary D.6 and the following derivations for simplicity.
F.3 LSGD-PFL
The LSGD-PFL protocol is summarized in Hanzely et al. 22021) b. which is a general design for personalized federated learning problems. It largely follows FedAvg (McMahan el al. 2017), while only the globally shared parameters are communicated and aggregated. The following lemma provided in Hanzely et al. (2021) to characterize the convergence LSGD-PFL.
Lemma F.7 (Theorem in Hanzely et al. (2021)): For any dataset S, if
Lm is uw Mu-strongly conver w.r.t. wm (see Definitionn F.2) for all E [M];
Em( (a Sm) is Bu -smoohh w.r.t. wa and MB-a-smooth smooth w.r.t. w (see Definition E [M];
F.9. for all
the stochastic gradients w.r.t. wa unbiased and have of -bounddd voriance (see Definition F.4
the slochastic gradients w.r.l. {wh m E [M]} is unbiased and have oj-bounded variance (see Definition F.4);
the gradients w.r.t. have Go bounded dissimilarity (see Definition F.5
with LSGD-PPL as the adopted FL protocol, the output w has Eape maa) S e' after
1
Bao (G2 1 02)
δ Pwo
M Mw
rounds of communications, where k is the number of local updates.
G Experiment Details
This section first provides a comprehensive description of the experimental scttings and procodures. The codes and detailed instructions have been uploaded in the supplementary materials so to execute the experiments and reproduce the results.
39

---

Published in Transactions on Machine Learning Research (07/2024)
Experimental details. In the experiments, the system is designed synchronous one, ic., (m((t 1, Vm [M], and for both tasks, two-layer multi-layer perceptrons (MLPss with hidden layer having a constant 256 width are used to approximate the reward functions.
For practical conveniences, instead of selecting a theoretically sound but sophisticated choice y for FedIGW as in Theorem 4.1 we set as a constant hyper-parameter and perform some preliminary manual selections with the final adopted values reported in Table We believe this approach is more practically appealing it does not need to scale y consistently; similar choice of using constant y is also adopted in Agarwal Also, the temperature parameter used in softmax can be found in Table
et al. 2023
Table 5: Hyperparamcter choices for FedIGW in Bibtex and Delicious
Task
Learning Rate
Batch Size
Communications
Parameter 7000
Parameter Ç
Bibtex
0.1
64
100
0.02
Delicious
0.2
64
100
7000
0.02
Multiple standard FL protocols including FedAvg [McMahan et al. 2017 2020) and FodProx (Li al., 2020a) are adopted as the FL component FedIGW. During each FL process, the local batch size, the number of communications, and the local learning rale specified in Table Moreover, the epoch length is designed to be growing exponentially as in Corollaries 4.2 D.8 and E.2 i.c., r' = 2', while culminating at an upper limit of 4096 to maintain timely updates. The same FedAvg setup is also used in experiments with greedy and softmax to ensure fair comparisons.
SCAFFOLD (Karimireddy et al,
Additional comparisons with single-agent baselines. In Fig. comparisons between FedIGW and the state-of-the-art FN-UCB are provided, demonstrating the superiority of FedIGW. Here we further report Fig. containing comparisons between FedIGW and two single-agent baselines:
AGR. The adaptive greedy (AGR) algorithm (Chakrabarti et al. 2008) is selected as one of the single-agent baselines due to its strong empirical performance on Bibtex and Delicious reported
Cortes (0018). The algorithmic details can be found in Cortes 2018 and we also leveraged the
code provided in Cortes (2018) build this baseline.
FALCON. The other single-agent baseline, FALCON, is proposed in Simchi-Levi & Xu (022), which essentially the single-agent version of FedIGW. We still adopt the same algorithmic configurations as FedIGW (i.e., epoch length, parameter 7, local batch size, and local learning rate) except that the MLP is optimized locally instead of federation, i..., there are no communccations.
It can be observed that FedIGW (with M = 10 participating agents and the basic FedAvg) can outperform the two single-agent baselines on both tasks, demonstrating the benefit learning a federation.
0.5
AGR (Single agent)
AGR (Single agent)
(Single agent)
0.35
(Single agent)
0.4
FedIGW (FedAvg)
FedIGW (FedAvg)
Average reward
Average reward
0.30
0.3
0.25
0.20
0.2
0.15
0.1
0.05
0.0
0.00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2,00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2,00
Rounds
1e4
Rounds
1e1
Figure 5: The averaged reward collected by each agent via. FedIGW (with FedAvg and M = 10 participating agents) and two single-agent baselines on Bibtex (left) and Delicious (right) datasets.
40


Reviews:
[{"review_id": "FLXLbb8g5M", "reviewer": "Reviewer_TBHH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I do not have the time to read all the proof details, but I have read this paper thoroughly and the authors have done a nice job presenting their results. I just have the following questions that I hope the authors can help me understand.\n\n  1. I do have some concerns regarding Assumption 3.1, which is basically saying that the reward function is the same across different clients. For example, when it is a linear function, then the parameter is the same across all the clients. I do understand that the authors mention the domain of the contexts could be different, but this seems to be still different from practical FL protocols where the parameter could be different. I think Assumption 6.2 is a partial fix to that, but I'm still wondering whether this assumption can be relaxed into boundedness in the reward functions or something similar.\n\n  2. Since FN-UCB is not designed to properly address this problem, as it is just a non-linear reward fitting algorithm and doesn't really have the ability to be combined with FedAvg/FedProx, how do the authors conduct the experiments with FN-UCB and compare with it? It seems to me that FN-UCB does not improve its performance over time (in e.g., Figure 3).\n\n  3. It seems that all the examples in this paper are linear examples. Can the authors provide some non-linear reward examples, especially for the case where the loss function is strongly convex? (Lemma 4.3 and Corollary 4.4)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a framework named FedIGW that incorporates traditional FL algorithms such as FedAvg into contextual bandit problems, which could be used to combine existing FL analysis with this approach and generate new analysis. I believe this work is important and beneficial to the whole Federated bandit community because as the paper mentions, most of the federated bandit work focuses on a setting where the clients just share their computed Statistics once in a while, and is completely unrelated to the FedAvg line of work. This work somehow fills this gap.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would request the following changes for strengthening the work\n\n1. Add more discussions to the experiments to show how FN-UCB is compared with FedIGW.\n2. Add more examples that are non-linear to show the usefulness of this work.", "broader_impact_concerns": "N.A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5pBDJU4oty", "reviewer": "Reviewer_GHaB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Natural FCB formulation: The paper introduces a novel approach to FCB that ensures compatibility with FedAvg and algorithms based on it, addressing a research gap in the literature.\n- Clarity and Coherence: The proposed idea is presented with clarity.\n- Modularized Analysis: The authors provide a modularized analysis which enhances the understanding of the paper’s contributions and facilitates future research extensions.\n\n\nWeaknesses:\n\n- Limited Novelty Beyond FedAvg Compatibility: Many of advantages mentioned (e.g., privacy, robustness, personalization) largely stem from its compatibility with FedAvg, which might not be seen as a substantial leap forward given prior works (e.g., Agarwal et al., 2023) have proposed similar FCB algorithms with FedAvg compatibility.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript addresses the challenge of integrating contextual bandit problems within the federated learning framework. The authors present a novel formulation of Federated Contextual Bandits (FCB) that naturally supports FedAvg, thereby extending the applicability of existing federated learning literature to able privacy/robustness, etc. Additionally, the authors provide a modularized convergence analysis.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It is difficult to request changes to secure a recommendation for acceptance, as the paper itself is already complete. The main advantage of this FedIGW stems from its compatibility with FedAvg, but algorithms with similar merits have been proposed in previous works, such as by Agarwal et al., 2023. The \"modularized plugin of FL analysis\" in this paper can be considered as extra effort compared to previous work but at the same time not strong enough to secure a clear acceptance. Therefore, I would say this is a borderline paper, and I am okay with it being accepted or rejected.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kK9stssaEz", "reviewer": "Reviewer_LJZ3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The submission provides a framework for federated contextual bandits where it modularizes the federated learning training components and provides unified regret bounds for any FL algorithm.\n* It also considers personalization in federated settings as well as robustness and privacy issues.\n* The regret analysis decreases as the decrease of the excess error of the adopted federated learning algorithm, which is reasonable.\n\nWeaknesses:\n\n* One concern is that there is previous work that explores how to incorporate FL components as a module in federated contextual bandits, e.g.,  An Empirical Evaluation of Federated Contextual Bandit Algorithms (https://arxiv.org/abs/2303.10218), which provides an even more general framework where it also modularizes the selection policies from the bandit literature. I think the submission needs to be revised given this related work, and clearly discusses what is new. For instance, I think the ‘flexible incorporation of FL protocols’ and ‘seamless integration of FL appendages’ aspects may not hold any more. Algorithm frameworks (which is one of the contributions) are similar. The unified regret analysis provided in this paper and the way that it gets plugged into the federated settings are still new.\n\n* The design choice of using inverse gap weighting is not well-justified either empirically or theoretically. The motivation is that it doesn’t need ‘other complicated data analytics, e.g., upper confidence bounds.’, which does not eliminate the possibilities of many other multi-armed bandit algorithms out there (greedy, softmax, etc).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission focuses on contextual bandits in federated learning, where each agent has some context and dataset (from different distributions), and they jointly learn a policy to select from a set of arms (or choices). The framework wraps FL as a black-box procedure which can cover a range of methods and provides regret analyses for the inverse gap weighting bandit algorithm with any FL method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Revise the paper to incorporate that prior work\n\n* Justify the choice of IGW better by comparing with other multi-armed bandit algorithms, or providing regret bounds for other variants of selection strategies. It is better to do both, as the bound would be an upper bound, and it is still not clear how the practical performance is even on the small-scale datasets in the current experiments.", "broader_impact_concerns": "No concerns on this.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers suggested acceptance; one was indifferent. 

Some strengths noticed by the reviewers:

- Natural FCB formulation: The paper introduces a novel approach to FCB that ensures compatibility with FedAvg and algorithms based on it, addressing a research gap in the literature.
- Clarity and Coherence: The proposed idea is presented with clarity.
- Modularized Analysis: The authors provide a modularized analysis which enhances the understanding of the paper’s contributions and facilitates future research extensions.
- The paper itself is already complete.
- The submission provides a framework for federated contextual bandits where it modularizes the federated learning training components and provides unified regret bounds for any FL algorithm.
- It also considers personalization in federated settings as well as robustness and privacy issues.
- The regret analysis decreases as the decrease of the excess error of the adopted federated learning algorithm, which is reasonable.

Several weaknesses were pointed out, a nd most were handled by the authors already.
Decision: Accept (poster)