# Federated Linear Contextual Bandits with Heterogeneous Clients

Ethan Blaser<EMAIL_ADDRESS>
Department of Computer Science
University of Virginia
Charlottesville, VA 22904, USA Chuanhao Li<EMAIL_ADDRESS>
Department of Computer Science
University of Virginia
Charlottesville, VA 22904, USA Hongning Wang<EMAIL_ADDRESS>
Department of Computer Science
University of Virginia
Charlottesville, VA 22904, USA

###### Abstract

The demand for collaborative and private bandit learning across multiple
agents is surging due to the growing quantity of data generated from
distributed systems. Federated bandit learning has emerged as a promising
framework for private, efficient, and decentralized online learning. However,
almost all previous works rely on strong assumptions of client homogeneity,
i.e., all participating clients shall share the same bandit model; otherwise,
they all would suffer linear regret. This greatly restricts the application of
federated bandit learning in practice. In this work, we introduce a new
approach for federated bandits for heterogeneous clients, which clusters
clients for collaborative bandit learning under the federated learning
setting. Our proposed algorithm achieves non-trivial sub-linear regret and
communication cost for all clients, subject to the communication protocol
under federated learning that at anytime only one model can be shared by the
server.

Keywords: Contextual Bandit, Federated Learning, Collaborative Bandit

##  1 Introduction

Bandit learning algorithms (Auer et al., 2002; Chapelle and Li, 2011; Li et
al., 2010a; Abbasi-Yadkori et al., 2011) have become a reference solution to
the problems of online decision optimization in a wide variety of
applications, including recommender systems (Li et al., 2010a), clinical
trials (Durand et al., 2018), and display advertising (Li et al., 2010b).
Typically, these algorithms are operated by a centralized server; but due to
the growing quantity of data generated from distributed systems, there is a
surge in demand for private, efficient, and decentralized bandit learning
across multiple clients. Federated bandit learning has emerged as a promising
solution framework, where multiple clients collaborate to minimize their
cumulative regret under the coordination of a single central server (Wang et
al., 2020; Dubey and Pentland, 2020a; Shi and Shen, 2021; Li and Wang, 2022;
He et al., 2022). The server’s role is limited to facilitating joint model
estimation across clients, without having access to any clients’ arm pulling
or reward history.

Although federated bandit learning has gained increasing interest from the
research community, most existing approaches necessitate that all clients
share the same underlying bandit model in order to achieve near-optimal sub-
linear regret for a population of clients. This strong homogeneity assumption
distills federated bandit learning to a joint estimation of a single global
model across clients, subject to the federated learning communication protocol
(Bonawitz et al., 2019; Kairouz et al., 2021). However, in reality, clients
can have diverse objectives, resulting in different optimal policies. Imposing
a single global model on a heterogeneous client population can easily cost
every client linear regret (Hossain et al., 2021). Consequently, rational
clients should choose not to participate in such a federated learning system,
as they cannot determine if other participating clients share the same bandit
model with them beforehand, and they can already achieve sub-linear regret
independently (albeit inferior to the regret obtained when all clients
genuinely share the same bandit model). This seriously impedes the practical
application of existing federated bandit learning solutions.

In a parallel line of bandit research, studies in collaborative bandits aim to
improve bandit learning in heterogeneous environments by facilitating
collective model estimation among different clients. For example, clustered
bandit algorithms group similar clients and use a shared bandit model for
clients within the same group (Gentile et al., 2014; Li et al., 2016; Gentile
et al., 2017; Cesa-Bianchi et al., 2013; Wu et al., 2016). When the
relatedness among clients are provided, such as through an affinity graph,
joint policy learning can be performed analytically (Cesa-Bianchi et al.,
2013; Wu et al., 2016). However, most of the existing collaborative bandit
learning algorithms operate under a centralized setting, in which data from
all clients is assumed to be directly accessible by a central server. As a
result, these methods cannot address the demand for privacy and communication
efficiency in online learning for distributed systems. Significant efforts are
required to adapt these algorithms to distributed settings Mahadik et al.
(2020).

In this paper, we introduce a novel approach for federated bandit learning
among heterogeneous clients, extending collaborative bandit learning to the
standard federated learning setting. The goal is to ensure that every
participating client achieves regret reduction compared to their independent
learning, thereby motivating all clients to participate. As the first work of
this kind, we focus on estimating a linear contextual bandit model (Li et al.,
2010a; Abbasi-Yadkori et al., 2011) for each client, which is also the most
commonly employed model in federated bandits. Not surprisingly, regret
reduction in a population of heterogeneous clients can be realized by
clustering the clients, where collective model estimation is only performed
within each cluster. But the key challenges lie in the communication protocol
in federated learning. First, the server lacks real-time access to each
client’s data, resulting in delayed inferences of client clusters. Second, the
server can only estimate and broadcast one global model at a time (He et al.,
2020; Foley et al., 2022). This can cause communication congestion and delay
the model updates. Both of them cost regret.

To address these challenges we develop a two-stage federated clustered bandit
algorithm. In the first stage, all clients perform pure exploration to prepare
a non-parametric clustering of clients based on the statistical homogeneity
test (Li et al., 2021). Then in the second stage, a first-in-first-out queue
is maintained on the server side to facilitate event-triggered communication
(Wang et al., 2020) at the cluster level. We rigorously establish the upper
bounds of cumulative regret and communication cost for this algorithm. Then,
we empirically enhance the algorithm by allowing dynamic re-clustering of
clients in the second stage and employ a priority queue to improve regret. We
conduct comprehensive empirical comparisons of the newly proposed federated
bandit algorithm against a set of representative baselines to demonstrate the
effectiveness of our proposed framework.

##  2 Related Work

Our work is closely related to studies in federated bandit learning and
collaborative bandits. In this section, we discuss the most representative
solutions in each area and highlight the relationships between them and our
work.

Federated Linear Contextual Bandits: There have been several works that study
the federated linear contextual bandit setting, where multiple clients work
collaboratively to minimize their cumulative regret with the coordination of a
single central server (Wang et al., 2020; Li and Wang, 2022; Huang et al.,
2021). Wang et al. (2020) introduced DisLinUCB, where a set of homogeneous
clients, each with the same linear bandit parameter, conduct joint model
estimation through sharing sufficient statistics with a central server. Li and
Wang (2022) and He et al. (2022) extended this setting by introducing an
event-triggered asynchronous communication framework to achieve sub-linear
communication cost as well as sub-linear regret in a homogeneous environment.
Additionally, Dubey and Pentland (2020b) considers deferentially private
federated contextual bandits in peer-to-peer communication networks. Fed-PE,
proposed in (Huang et al., 2021), is a federated phase-based elimination
algorithm for linear contextual bandits that handles both homogeneous and
heterogeneous settings. However, in their setting, the client is trying to
learn the fixed context vectors associated with each arm as opposed to the
linear reward parameter (which is known in their setting). With the exception
of Fed-PE, which utilizes a different bandit formulation altogether, all of
these prior works rely on strong assumptions of client homogeneity, while our
work seeks to extend federated linear contextual bandit learning to a
heterogeneous environment.

Collaborative Bandits: Collaborative bandits seek to leverage similarities
between heterogeneous clients to improve bandit learning. Clustered bandit
algorithms are one example, where similar clients are grouped together, and a
shared bandit model is used for all clients in the same group(Gentile et al.,
2014; Li et al., 2016; Gentile et al., 2017; Cesa-Bianchi et al., 2013; Wu et
al., 2016). Gentile et al. (2014) assumed that observations from different
clients in the same cluster are associated with the same underlying bandit
parameter. Gentile et al. (2017) further studied context-dependent clustering
of clients, grouping clients based on their similarity along their bandit
parameter’s projection onto each context vector. Li et al. (2021) unified non-
stationary and clustered bandit by allowing for a time varying bandit
parameter for each client, which requires online estimation of the dynamic
cluster structure at each time. Other works leverage explicit inter-client and
inter-arm relational structures, such as social networks (Buccapatnam et al.,
2013; Cesa-Bianchi et al., 2013; Wu et al., 2016; Hong et al., 2021; Caron et
al., 2012; Mannor and Shamir, 2011) to facilitate collaboration. However, most
existing collaborative bandit solutions are designed under a centralized
setting, where all clients’ observation data is readily available at a central
server. Liu et al. (2022) and Korda et al. (2016) consider online cluster
estimation in a distributed setting. However, their federated learning
architectures do not align with the standard federated learning architecture
and real world implementations where a single central server broadcasts a
single global model at each timestep (McMahan et al., 2016; He et al., 2020;
Foley et al., 2022). Specifically, Liu et al. (2022) utilizes a hierarchical
server configuration that is distinct from the standard single-server FL
setup. On the other hand, Korda et al. (2016) is based on a peer-to-peer (P2P)
communication network, which stands in contrast to the centralized
communication model and also overlooks the potential communication costs
associated with such a decentralized approach.

##  3 Methodology

In this section, we begin by outlining the problem setting investigated in
this work. Then we present our two-stage federated clustered bandit algorithm
designed to serve a population of heterogeneous clients under the standard
communication setup in federated learning. We provide theoretical analysis of
the upper regret bound for our developed solution. Lastly, we introduce a set
of improvements to our proposed algorithm, including dynamic re-clustering of
clients using an adaptive clustering criterion, and the implementation of a
priority queue to enhance online performance, both of which were found
empirically effective.

###  3.1 Problem Setting

A federated bandit learning system consists of two components: 1) $N$ clients,
which take actions and get reward feedback from their environment (e.g., edge
devices in a recommendation system interacting with end users) and 2) a
central server coordinating client communication for collaborative model
estimation. In each time step $t=1,2,...T$, each client $i\in{N}$ chooses an
action $x_{t,i}$ from its action set
$\mathcal{A}_{t,i}=\\{{x}_{t,1},{x}_{t,2}...,x_{t,K}\\}$, where
$x\in\mathbb{R}^{d}$. Adhering to the standard linear reward assumption from
(Li et al., 2010b), the corresponding reward received by client $i$ is
$y_{t,i}=\langle\theta_{i}^{*},{x}_{t,i}\rangle+\eta_{t}$, where noise
$\eta_{t}$ comes from a $\sigma^{2}$ sub-Gaussian distribution, and
$\theta_{i}^{*}$ is the true linear reward parameter for client $i$. Without
loss of generality, we assume $\|x\|_{2}\leq 1$ and $\|\theta_{i}^{*}\|\leq
1$.

The learning system interacts with the environment for $T$ rounds, aiming to
minimize the cumulative pseudo-regret
$R_{T}=\sum_{t=0}^{T}\sum_{i=0}^{N}\max_{x\in\mathcal{A}_{t,i}}\langle\theta_{i}^{*},x\rangle-\langle\theta_{i}^{*},{x}_{t,i}\rangle$.

Following the federated learning setting, we assume a star-shaped
communication network, where the clients cannot directly communicate among
themselves. Instead, they must share the learning algorithm’s parameters
(e.g., gradients, model weights, or sufficient statistics) through the central
server. To preserve data-privacy, raw observations collected by each client
$(x_{t,i},y_{t,i})$ are stored locally and will not be shared with the server.
At every timestep $t=1,...T$, the central server is capable of using the
shared learning algorithm to update and broadcast one model to the selected
clients. The communication cost is defined as the amount of sufficient
statistics communicated across the learning system over the entire time-
horizon.

Unlike existing federated bandit works (Wang et al., 2020; Li and Wang, 2022;
He et al., 2022) which assume homogeneous clients, we adopt the standard
clustered bandit setting to model a heterogeneous learning environment.
Without an underlying cluster structure in the environment, collaboration
between clients would be infeasible. Therefore, we assume that clients sharing
similar reward models form clusters, collectively represented as
$\mathcal{C}=\\{C_{1},C_{2},...,C_{M}\\}$. The composition and quantity of
these clusters, are unknown to the system, necessitating on-the-fly inference.
Consistent with prevalent clustered bandit practices (Gentile et al., 2014,
2017; Liu et al., 2022), we use unknown environmental parameters $\epsilon$
and $\gamma$ to delineate the ground-truth cluster structures:

######  Assumption 1 (Proximity within clusters)

For any two clients $i,j$ within a particular cluster $C_{k}\in\mathcal{C}$,
$\|\theta^{*}_{i}-\theta^{*}_{j}\|\leq\epsilon$ where
$\epsilon=1/(N\sqrt{T})$.

######  Assumption 2 (Separateness among clusters)

For any two clusters $C_{k},C_{l}\in\mathcal{C},\;\forall i\in C_{k},\,j\in
C_{l}$, $\|\theta^{*}_{i}-\theta^{*}_{j}\|\geq\gamma\geq 0\;$ (Gentile et al.,
2014, 2017; Li et al., 2021; Liu et al., 2022).

Contrary to previous clustered bandit assumptions of identical reward models
within a cluster, our Assumption 1 offers more flexibility. It enables similar
clients (represented by $\epsilon$) to collaborate, amplifying the system’s
collaborative benefit. We also adopt a standard context regularity assumption
found in clustered bandits.

######  Assumption 3 (Context regularity)

At each time $t$, $\forall i\in\\{N\\}$ arm set $\mathcal{A}_{t,i}$ is
generated i.i.d. from a sub-Gaussian random vector $x_{t,i}\in\mathbb{R}^{d}$,
such that $\mathbb{E}[x_{t,i}x_{t,i}^{\top}]$ is full-rank with minimum
eigenvalue $\lambda_{c}>0$ (Gentile et al., 2014, 2017; Li et al., 2019).

Notably, our context regularity Assumption 3 is weaker than those in (Gentile
et al., 2014, 2017; Li et al., 2019). Ours only requires the lower bound on
the minimum eigenvalue of $\mathbb{E}[x_{t,i}x_{t,i}^{\top}]$, while others
require the imposition of a variance condition on the stochastic process
generating $x_{t,i}$.

To facilitate our later discussions, we use
$\mathcal{H}_{t,i}=\left\\{(x_{\tau,i},y_{\tau,i})\right\\}_{\tau=1}^{t}$ to
represent the set of $t$ observations from client $i$.
$(\mathbf{X}_{i},\mathbf{y}_{i})$ denote design matrices and feedback vectors
of $\mathcal{H}_{t,i}$ where each row of $\mathbf{X}$ is the context vector of
an arm and the corresponding element in $\mathbf{y}$ is the observed reward
for this arm. Note that $\mathbf{X}_{j}$ only contains the observations made
by client $j$ and does not include aggregated observations from other clients
in the cluster. We also define the weighted norm of a vector
$x\in\mathbb{R}^{d}$ as $\|x\|_{A}=\sqrt{x^{\top}Ax}$, where
$A\in\mathbb{R}^{d\times d}$ is a positive definite matrix.

###  3.2 Algorithm: HetoFedBandit

In this section, we present our two-stage federated clustered bandit
algorithm. As discussed in Section 1, there are two primary challenges
associated with extending clustered bandit learning to the federated learning
setting. The first challenge is to identify the subsets of heterogeneous
clients that can benefit from collaboration among themselves. To achieve this,
in the first stage of our algorithm, all clients conduct random exploration
ahead of a non-parametric clustering of clients based on the statistical
homogeneity test (Li et al., 2021). The second challenge arises from the
communication network setting in federated learning framework, which allows
only one model to be broadcast at each time step (He et al., 2020; Foley et
al., 2022). To accommodate this constraint, a first-in-first-out queue is
utilized on the server side, enabling event-triggered collaboration (Wang et
al., 2020) at the cluster level during our algorithm’s second phase. We
provide an overview of the key components of our algorithm, with the full
details available in Algorithm 3.

Figure 1: Execution of HetoFedBandit after pure exploration phase $T_{0}$.
Each client $i\in N$ is represented by a node in the client graph
$\mathcal{G}$ on the left hand side. Edges between clients indicate potential
collaborators, as defined by the homogeneity test. The colored ellipsoids
represent the estimated clusters
$\hat{\mathcal{C}}=\\{\hat{C}_{1},...,\hat{C}_{5}\\}$, which are the maximal
cliques of $\mathcal{G}$. Clients exceeding their communication threshold are
highlighted in orange. Currently, client $\theta_{6}$ has exceeded the
communication threshold $D_{1}$ for cluster $\hat{C}_{1}$, which causes
cluster $\hat{C}_{1}$ to be added to the queue. The server pops cluster
$\hat{C}_{2}$ from the queue and facilitates collaboration among
$\\{\theta_{1},\theta_{3},\theta_{7}\\}$. In the next timestep, the server
will serve cluster $\hat{C}_{4}$, queued for removal.

##### Pure Exploration Phase

Under our relaxed context regularity assumption, we execute a short
exploration phase of length $T_{0}$ to guarantee the accuracy of our
homogeneity test. Our discussion on the choice of $T_{0}$ is deferred to
Section 3.3. Although our derived theoretical value for $T_{0}$ depends on an
unknown environmental parameter $\gamma$, in practice, $T_{0}$ can be tuned as
a hyperparameter.

During this exploration stage, for each $t\in\\{0...T_{0}\\}$, every client
$i\in[N]$ selects an action $x_{t,i}$ by uniformly sampling from
$\mathcal{A}_{t,i}$ in parallel. After receiving reward $y_{t,i}$, each client
updates their local sufficient statistics
$V_{t,i}=V_{t-1,i}+{x}_{t,i}{x}_{t,i}^{\top}$ and
$b_{t,i}=b_{t-1,i}+x_{t,i}y_{t,i}$. Upon completion of $T_{0}$ rounds of pure
exploration, each client then shares its sufficient statistics ($V_{T_{0},i}$,
$b_{T_{0},i}$) to the central server. We present the details of the
exploration phase in Algorithm 1.

Algorithm 1 Pure Exploration Phase

1: for $t=1,2,...,T_{0}$ do

2: for Agent $i\in N$ do

3: Choose arm $x_{t,i}\in\mathcal{A}_{i,t}$ uniformly at random and observe
reward $y_{t,i}$

4: Update agent $i$:
$\mathcal{H}_{t,i}=\mathcal{H}_{t-1,i}\cup(x_{t,i},y_{t,i})$,
$V_{t,i}\mathrel{+}=x_{t,i}x_{t,i}^{\top}$,
$b_{t,i}\mathrel{+}=x_{t,i}y_{t,i}$,

5: $\Delta V_{t,i}\mathrel{+}=x_{t,i}x_{t,i}^{\top}$, $\Delta
b_{t,i}\mathrel{+}=x_{t,i}y_{t,i},\Delta t_{0,i}\mathrel{+}=1$

6: end for

7: end for

##### Cluster Estimation

The key challenge in online clustering of bandits is to measure the similarity
between different bandit models. Previous works identify whether a set of
clients share exactly the same underlying reward model; while we cluster
similar clients (as defined by $\epsilon$) to widen the radius of beneficial
collaboration. We realize this by testing whether
$\|\theta^{*}_{1}-\theta^{*}_{2}\|\leq\epsilon$ via the homogeneity test
introduced in (Li et al., 2021).

Specifically, we utilize a $\chi^{2}$ test of homogeneity, where the test
statistic $s(\mathcal{H}_{t,1},\mathcal{H}_{t,2})$ follows the non-central
$\chi^{2}$-distribution (Chow, 1960; Cantrell et al., 1991). The test
determines whether the parameters of linear regression models associated with
two datasets are similar, assuming equal variance. Since $\theta_{1}^{*}$ and
$\theta_{2}^{*}$ are unobservable, the test utilizes the maximum likelihood
estimator (MLE) for $\theta$ on a dataset $\mathcal{H}$, which we denote
${\vartheta}=(\mathbf{X}^{\top}\mathbf{X})^{-}\mathbf{X}^{\top}\mathbf{y}$,
where $\left(\cdot\right)^{-}$ denotes the generalized matrix inverse:

$\displaystyle s(\mathcal{H}_{t,1},\mathcal{H}_{t,2})$
$\displaystyle=\frac{||\mathbf{X}_{1}({\vartheta}_{1}-{\vartheta}_{1,2})||^{2}\\!+\\!||\mathbf{X}_{2}({\vartheta}_{2}-{\vartheta}_{1,2})||^{2}}{\sigma^{2}}$
(1)

where ${\vartheta}_{1,2}$ denotes the estimator using data from
$\mathcal{H}_{t,1}$ and $\mathcal{H}_{t,2}$.

When $s(\mathcal{H}_{t,1},\mathcal{H}_{t,2})$ exceeds a chosen threshold
$\upsilon^{c}$, it indicates a deviation between the combined estimator and
the individual estimators on the two datasets. Thus, we conclude
$\|\theta_{1}^{*}-\theta_{2}^{*}\|>\epsilon$; otherwise, we conclude
$\|\theta_{1}^{*}-\theta_{2}^{*}\|\leq\epsilon$. Therefore, to determine the
sets of clients that can collaborate, the central server performs this
pairwise homogeneity test among each pair of clients. If two clients $i,j$
satisfy the homogeneity test
$s(\mathcal{H}_{T_{0},i},\mathcal{H}_{T_{0},j})\geq\upsilon^{c}$, then we add
an undirected edge between them in a client graph $\mathcal{G}$ indicating
they benefit from mutual collaboration.

Next, our algorithm uses $\mathcal{G}$ to determine the clusters of clients
that can benefit from collaboration. Because our algorithm allows
collaboration between non-identical clients, we must ensure every client
within a cluster is sufficiently similar to every other; otherwise, linear
regret can be caused by the incompatible model sharing. For this purpose, we
require each of our estimated clusters be a maximal clique of $\mathcal{G}$
(line 5 in Algorithm 2). We denote the set of resulting clusters as
$\hat{\mathcal{C}}=\\{\hat{C}_{1},\hat{C}_{2},...\hat{C}_{\hat{M}}\\}$ and the
set of cluster indices in $\mathcal{C}$ that client $i$ belongs to as
$\mathcal{K}_{i}$.

Using the maximal cliques of $\mathcal{G}$ as the cluster estimates introduces
a unique challenge that affects our subsequent algorithmic design: the
estimated clusters may not be disjoint. In Figure 1, we can see that client 3,
represented by $\theta_{3}$, is a member of two clusters, $\hat{C}_{2}$ and
$\hat{C}_{4}$. Therefore, $\theta_{3}$ will receive shared model updates from
clients $\\{\theta_{1},\theta_{7},\theta_{4}\\}$. However, the absence of an
edge between $\theta_{1}$ and $\theta_{4}$ implies that simultaneous
collaboration between $\\{\theta_{3},\theta_{1}\\}$ and
$\\{\theta_{3},\theta_{4}\\}$ is not allowed by our algorithm. As a result,
when $\theta_{3}$ is collaborating with $\theta_{1}$, it should only share its
local data, excluding what it has received from the server. Later we describe
our queue-based sequential approach to resolve this.

Algorithm 2 Cluster Estimation

1: for $(i,j)\in N$ do

2: if $s(\mathcal{H}_{T_{0},i},\mathcal{H}_{T_{0},j})\leq\upsilon^{c}$ then
add edge $e(i,j)$ to $\mathcal{G}$

3: end for

4: $\hat{\mathcal{C}}=\\{\hat{C}_{1},\hat{C}_{2},...\hat{C}_{\hat{M}}\\}=$
maximal_cliques($\mathcal{G}$)

5: Set $\mathcal{K}_{i}$ = $\\{k:i\in\hat{C_{k}}\\}$ for each client $i$

##### Optimistic Learning Phase

Upon identifying client clusters suitable for collaboration, we proceed to the
optimistic learning phase of our algorithm. Here, clients optimistically
choose arms, utilizing the collaboration with other similar clients to enhance
their local model estimates. At each time step $t\in\\{T_{0}...T\\}$, each
client $i\in[N]$ optimistically selects an arm $x_{t,i}\in\mathcal{A}_{t,i}$
using the UCB strategy based on its sufficient statistics
$\\{V_{t,i},b_{t,i}\\}$:

$x_{t}=\operatorname*{arg\,max}_{x\in\mathcal{A}_{t,i}}{x^{\top}\hat{\theta}_{t-1,i}+\text{CB}_{t-1,i}(x)}$
(2)

where $\hat{\theta}_{t-1,i}=\overline{V}_{t-1,i}^{-1}b_{t-1,i}$ is the ridge
regression estimator with regularization parameter $\lambda$;
$\overline{V}_{t-1,i}=V_{t-1,i}+\lambda I$; and the confidence bound of reward
estimation for arm $x$ is
$\text{CB}_{t-1,i}(x)=\alpha_{t-1,i}\|x\|_{\overline{V}_{t-1,i}^{-1}}$, where
$\alpha_{t-1,i}=\sigma\sqrt{2\log\biggr{(}\frac{\det(\overline{V}_{t-1,i})^{1/2}}{\delta\det(\lambda
I)^{1/2}}\biggr{)}}+\sqrt{\lambda}$. Note that $V_{t,i}$ is formulated using
data locally collected by client $i$ in conjunction with data from the clients
with whom client $i$ has previously collaborated. After client $i$ observes
reward $y_{t,i}$, it updates its local sufficient statistics to improve the
reward estimates in future rounds.

##### Communication Protocol

Our algorithm integrates the event-triggered communication protocol from Wang
et al. (2020) to efficiently balance communication and regret minimization
within clusters. It uses delayed communication, where clients store
observations and rewards in a local buffer $\Delta V_{t,i}$ and $\Delta
b_{t,i}$. Clients request server collaboration when the informativeness of the
stored updates surpass a certain threshold. Specifically, If $\Delta
t_{t,i}\log(\det(V_{t,i})/\det(V_{t,i}-\Delta V_{t,i}))\geq D_{k}$ for any
$k\in\mathcal{K}_{i}$, with $D_{k}$ as the communication threshold for the
estimated cluster $\hat{C}_{k}$, the client sends a collaboration request for
$\hat{C}_{k}$.

Multiple clients across different clusters can trigger simultaneous
communication requests, and single clients can request collaboration for
multiple clusters because the estimated clusters are not disjoint. In such
cases, the central server uses a first-in-first-out queue (FIFO) $Q$ to manage
the clusters needing collaboration one-by-one. At each timestep
$t\in\\{T_{0}...T\\}$, it serves one cluster from the queue, ensuring no
inter-cluster data contamination by computing $V_{t,sync}$ and $b_{t,sync}$
using only the clients’ upload buffers. Despite the single global-model
restriction in federated learning, our algorithm still helps multiple groups
of similar clients in a pseudo round-robin manner. As a result, a cluster of
clients can resume engaging with the environment without being hindered by the
server’s processing time for unrelated clusters that don’t offer collaborative
advantage.

This queuing strategy enhances the system’s efficiency, allowing clusters to
re-engage with the environment without idling for the server’s processing of
all other clusters. However, before computing and sharing
$\\{V_{t,sync},b_{t,sync}\\}$ for collaboration, our algorithm mandates the
complete upload of local buffers from every client in that cluster. This
signifies that our algorithm employs asynchronous communication at the cluster
level but still requires synchronous communication among clients within the
same cluster. In practical distributed systems, clients often exhibit variable
response times and occasional unavailability. Adapting our algorithm to
support asynchronous communication at the individual client level, such that
they can collaborate without awaiting updates from all other clients within
the cluster, remains an important open research question.

Algorithm 3 HetoFedBandit

1: Input: $T$, $\delta\in(0,1)$, exploration length $T_{0}$, $\lambda>0$,
neighbor identification $\upsilon^{c}$

2: Initialization: Clients: $\forall i\in N$: $V_{0,i}=\textbf{0}_{d\times
d},b_{0,i}=\textbf{0}_{d},\mathcal{H}_{0,i}=\emptyset,\Delta
V_{0,i}=\textbf{0}_{d\times d},\Delta b_{0,i}=\textbf{0}_{d},\Delta
t_{i,0}=0$, $\mathcal{K}_{i}=\emptyset$ ; Server: Client graph $\mathcal{G}$
with $N$ nodes, FIFO queue $Q$;

3: Pure Exploration Phase (Algorithm 1)

4: Cluster Estimation (Algorithm 2)

5: Cluster communication thresholds $\mathcal{D}=[D_{1},...,D_{\hat{M}}]$
where $D_{k}=(T\log|\hat{C}_{k}|T)/(d|\hat{C}_{k}|)$

6: for $t=T_{0}+1,...,T$ do

7: for Client $i\in N$ do

8: Choose arm $x_{t,i}\in\mathcal{A}_{t,i}$ by Eq. 2 observe reward $y_{t,i}$

9: Update client $i$:
$\mathcal{H}_{t,i}=\mathcal{H}_{t-1,i}\cup(x_{t,i},y_{t,i})$,
$V_{t,i}\mathrel{+}=x_{t,i}x_{t,i}^{\top}$,
$b_{t,i}\mathrel{+}=x_{t,i}y_{t,i}$,

10: $\Delta V_{t,i}\mathrel{+}=x_{t,i}x_{t,i}^{\top}$, $\Delta
b_{t,i}\mathrel{+}=x_{t,i}y_{t,i},\Delta t_{t,i}\mathrel{+}=1$

11: for $k\in\mathcal{K}_{i}$ do

12: if $\Delta t_{t,i}\log(\det(V_{t,i})/\det(V_{t,i}-\Delta V_{t,i}))\geq
D_{k}$ then

13: Collaboration Request: Server adds $\hat{C}_{k}$ to $Q$

14: end if

15: end for

16: end for

17: if $Q$ is non-empty then

18: Server pops $\hat{C_{k}}$ from $Q$

19: Every client $i\in\hat{C_{k}}$ sends $\Delta V_{t,j}$, $\Delta b_{t,j}$ to
server

20: Each client in $\hat{C}_{k}$ receives
$V_{t,sync}=\sum_{j\in\hat{C_{k}}}\Delta V_{t,j}$,
$b_{t,sync}=\sum_{j\in\hat{C_{k}}}\Delta b_{t,j}$ from the server

21: Local client updates: $V_{t,i}\mathrel{+}=V_{t,sync}-\Delta V_{t,i}$,
$b_{t,i}\mathrel{+}=b_{t,sync}-\Delta b_{t,i}$, $\Delta V_{t,i}=0$, $\Delta
b_{t,i}=0,\Delta t_{t,i}=0$

22: end if

23: end for

###  3.3 Theoretical Results

As presented in Section 3.2, our algorithm first utilizes a homogeneity test
to cluster similar clients in a heterogeneous environment. We prove that with
our homogeneity test, Algorithm 2 correctly identifies the underlying
clusters.

######  Theorem 1 (Clustering Correctness)

Under the condition that we set the homogeneity test threshold
$\upsilon^{c}\geq F^{-1}(1-\frac{\delta}{N^{2}},df,\psi^{c})$, with
probability at least $1-\delta$, we have $\hat{\mathcal{C}}=\mathcal{C}$.

$F^{-1}(\cdot)$ is the inverse of the CDF of the non-central $\chi^{2}$
distribution, and $\psi^{c}\doteq\frac{1}{\sigma^{2}}$. We provide the
complete proof of Theorem 1 in Appendix B. Moreover, Algorithm 3 adopts a UCB-
based arm selection, which requires the construction of a confidence
ellipsoid.

######  Lemma 2 (Confidence Ellipsoids)

Suppose client $i$ is a member of cluster $\hat{C}_{k}\in\hat{\mathcal{C}}$,
and is therefore collaborating with clients $j\in\hat{C_{k}}$. For any
$\delta>0$, with probability at least $1-\delta$, for all $t\geq 0$ and all
clients $i\in{N}$, $\theta_{i}^{*}$ lies in the set:

$\begin{split}\beta_{t,i}=\biggl{\\{}\theta\in\mathbb{R}^{d}:\big{\|}\hat{\theta}_{t,i}-\theta\big{\|}_{\overline{V}_{t,i}}\leq\sigma\sqrt{2\log\biggr{(}\frac{\det(\overline{V}_{t,i})^{1/2}}{\det(\lambda
I)^{1/2}\delta}\biggr{)}}\\\
+\sqrt{\lambda}+\bigg{\|}\sum_{j\in\hat{C}_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})\bigg{\|}_{\overline{V}_{t,i}^{-1}}\biggr{\\}}\end{split}$

We provide the complete proof of Lemma 2 in Appendix C.

Our algorithm enables collaboration among heterogeneous clients, which
introduces extra biases represented by the term
$H=\|\sum_{j\in\hat{C}_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}-\theta_{i})\|_{\overline{V}_{t,i}^{-1}}$.
With improved analysis compared with Li et al. (2021), we utilize our cluster
estimation procedure Algorithm 2 to control the magnitude of the bias term $H$
by judiciously picking the threshold $\upsilon^{c}$.

Then, based on the constructed confidence ellipsoid, we prove Theorem 3, which
provides upper bounds of the cumulative regret $R_{T}$ and communication cost
$C_{T}$ incurred by HetoFedBandit. While the good/bad epoch decomposition used
in our analysis is first introduced by Wang et al. (2020), additional care
needs to be taken when bounding the extra regret introduced by the delays in
serving clusters before they can be removed from the queue. We present the
complete proof of Theorem 3 in Appendix D.

######  Theorem 3 (Regret and Communication Cost)

With an exploration phase length of
$T_{0}=\frac{16\psi^{d}\sigma^{2}}{\lambda_{c}\gamma^{2}}$, with probability
$1-\delta$ our protocol achieves a cumulative regret of

$\begin{split}R_{T}=O\biggr{(}\frac{N\psi^{d}\sigma^{2}}{\lambda_{c}\gamma^{2}}+\sum_{k=1}^{M}d\sqrt{|C_{k}|T}\log^{2}(|C_{k}|T)\\\
+d|C_{k}|^{2}M\log(|C_{k}|\,T)\biggr{)},\end{split}$ (3)

where $\psi^{d}=F^{-1}\big{(}\frac{\delta}{N^{2}(M-1)};d,\upsilon^{c}\big{)}$,
with communication cost

$C_{T}=O(Nd^{2})+\sum_{k=1}^{M}O(|C_{k}|^{1.5}\cdot d^{3}).$ (4)

###### Remark 4

The regret upper-bound has three components. The first term is our version of
the ”problem hardness” (Li et al., 2021; Gentile et al., 2014) which is
independent of T. This ”hardness” factor is determined by the cluster
separation parameter $\gamma$ from Assumption 2. The second term is the
standard regret upper bound from centralized clustered bandit algorithms (Li
et al., 2021; Gentile et al., 2014). The third term arises from the potential
waiting time clusters may experience in the queue before the server serves
them. Our communication cost matches that of an idealized algorithm executing
DisLinUCB(Wang et al., 2020) within each ground-truth cluster.

We compare our regret and communication upper-bound under three cases. Case 1
- Single cluster: Setting $M=1$ reduces the problem to a nearly homogeneous
setting, where every client is within $\epsilon$ of everyone else. Under this
setting, our regret becomes $\tilde{O}(d\sqrt{NT})$ where logarithmic factors
and factors that do not depend on $T$ (since it is assumed that $T\gg N$) are
omitted in $\tilde{O}$. Additionally communication cost becomes
$O(N^{1.5}d^{3})$. Our algorithm matches the regret and communication cost of
(Wang et al., 2020), which is designed for homogeneous clients. Case 2 - N
clusters: Setting $M=N$ reduces the problem to a completely heterogeneous
setting, where no client can benefit from collaboration as each client is at
least $\epsilon$ away from others. Algorithm 3 has regret
$\tilde{O}(dN\sqrt{T})$, which recovers the regret of running LinUCB (Abbasi-
Yadkori et al., 2011) independently on each client. In this setting our
communication becomes $O(Nd^{3})$. Case 3 - Equal Size Clusters: Setting
$|C_{k}|=N/M,\forall k$ gives us $M$ clusters of equal size. In this setting
our regret becomes $\tilde{O}(d\sqrt{MNT})$, where the first term recovers the
results presented in Gentile et al. (2014); Li et al. (2021). Our
communication becomes $O(d^{3}N^{1.5}/\sqrt{M})$.

###  3.4 Empirical Enhancements: HetoFedBandit-E

In this section, we describe the details of our proposed empirical
enhancements to our HetoFedBandit algorithm, where we perform re-clustering to
improve the quality of estimated clusters of clients and replace the first-in-
first-out queue with a priority queue to help clusters where a shared model
update can most rapidly reduce regret for clients in that cluster. We present
the details of our enhanced algorithm HetoFedBandit-E in Algorithm 5.

####  3.4.1 Data-Dependent Clustering

We propose a data-dependent clustering procedure to enhance collaboration
among clients with similar observational histories. Our homogeneity test for
cluster formation ensures an upper bound on the bias term $H$, as outlined in
Lemma 2. This term depends on the differences in underlying parameters
($\theta_{i}^{*}$ vs., $\theta_{j}^{*}$) and each client’s observation
history. For instance, if client $j$’s observations are in the null space of
$(\theta_{j}^{*}-\theta_{i}^{*})$, collaborating with client $j$ will not
introduce excessive bias to client $i$. But without further assumptions about
the context vector sequence, we must conservatively assume in our original
design that every client $j$’s entire observation history aligns with
$(\theta_{j}^{*}-\theta_{i}^{*})$.

Previously, we used a homogeneity test with threshold
$\epsilon=\frac{1}{N\sqrt{T}}$ to verify clients’ collaboration across all
timesteps. Now, we can relax the homogeneity test threshold to check if two
clients can collaborate at a specific timestep $t$ by examining if
$\|\theta_{i}-\theta_{j}\|\leq\epsilon={1}/\left({N\sqrt{\lambda_{\max}(\mathbf{X}_{j}^{\top}\mathbf{X}_{j})}}\right)$.To
achieve this, we modify our algorithm to forgo single round cluster
estimation. Instead, every time a client requests collaboration, we re-cluster
the clients using the data-dependent thresholds for our pairwise homogeneity
tests. By making these thresholds data-dependent, each client can collaborate
with more neighbors earlier, boosting overall collaborative benefits in our
learning system.

Algorithm 4 Data-Dependent Clustering

1: Re-initialize client graph $\mathcal{G}$ with no edges

2: for $(i,j)\in N$ do

3: Server Computes $\upsilon^{c}=F^{-1}(1-\frac{\delta}{N^{2}},df,\psi^{c})$
where

4:
$\psi^{c}=\frac{\epsilon^{2}}{\sigma^{2}}\lambda_{\text{max}}(\mathbf{X}_{2}^{\top}\mathbf{X}_{2}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1}+\mathbf{X}_{2}^{\top}\mathbf{X}_{2})^{-1}\mathbf{X}_{1}^{\top}\mathbf{X}_{1})$

5: if $s(\mathcal{H}_{t,i},\mathcal{H}_{t,j})\leq\upsilon^{c}$ then

6: Add edge $e(i,j)$ to $\mathcal{G}$

7: end if

8: end for

9: $\hat{\mathcal{C}}=\\{\hat{C}_{1},\hat{C}_{2},...\hat{C}_{\hat{M}}\\}=$
maximal_cliques($\mathcal{G}$)

10: Set $\mathcal{K}_{i}$ = $\\{k:i\in\hat{C_{k}}\\}$ for each client $i$

11: Cluster communication thresholds $\mathcal{D}=[D_{1},...,D_{\hat{M}}]$
where $D_{k}=(T\log|\hat{C}_{k}|T)/(d|\hat{C}_{k}|)$

Algorithm 5 HetoFedBandit-E

1: Input: $T$, $\delta\in(0,1)$, regularization parameter $\lambda>0$

2: Initialize Clients: $\forall i\in N$: $V_{0,i}=\textbf{0}_{d\times
d},b_{0,i}=\textbf{0}_{d},\mathcal{H}_{0,i}=\emptyset,\Delta
V_{0,i}=\textbf{0}_{d\times d},\Delta b_{0,i}=\textbf{0}_{d},\Delta
t_{i,0}=0$, $\mathcal{K}_{i}=\emptyset$

3: Initialize Server: Client graph $\mathcal{G}$ with $N$ nodes;

4: Initialize empty Priority Queue $Q$;

5: for $t=T_{0}+1,...,T$ do

6: for Client $i\in N$ do

7: $\overline{V}_{t-1,i}=V_{t-1,i}+\lambda I$,
$\hat{\theta}_{t-1,i}=\overline{V}_{t-1,i}^{-1}\,b_{t-1,i}$

8: Choose arm $x_{t,i}\in\mathcal{A}_{t,i}$ by Equation 2 observe reward
$y_{t,i}$

9: Update agent $i$:
$\mathcal{H}_{t,i}=\mathcal{H}_{t-1,i}\cup(x_{t,i},y_{t,i})$,
$V_{t,i}\mathrel{+}=x_{t,i}x_{t,i}^{\top}$,
$b_{t,i}\mathrel{+}=x_{t,i}y_{t,i}$,

10: $\Delta V_{t,i}\mathrel{+}=x_{t,i}x_{t,i}^{\top}$, $\Delta
b_{t,i}\mathrel{+}=x_{t,i}y_{t,i},\Delta t_{t,i}\mathrel{+}=1$

11: if $\Delta t_{t,i}\log(\det(V_{t,i})/\det(V_{t,i}-\Delta V_{t,i}))\geq
D_{k}$ then

12: Empty Priority Queue $Q$;

13: Every client $i\in N$ sends $\Delta V_{t,j}$ and $\Delta b_{t,j}$ to
server

14: Data Dependent Cluster Estimation (Algorithm 4)

15: Send collaboration request to server, which then adds $\hat{C}_{k}\forall
k\in\mathcal{K}_{i}$ to $Q$

16: end if

17: end for

18: if Q is non-empty then

19: Server pops cluster
$\hat{C_{k}}=\operatorname*{arg\,max}_{\hat{C}_{k}\in\hat{\mathcal{C}}}\sum_{i\in\hat{C}_{k}}\Delta
t_{t,i}\log(\frac{\det(V_{t,i})}{\det(V_{t,i}-\Delta V_{t,i})})$ from Q

20: Server Computes: $V_{t,sync}=\sum_{j\in\hat{C_{k}}}\Delta V_{t,j}$,
$b_{t,sync}=\sum_{j\in\hat{C_{k}}}\Delta b_{t,j}$

21: Each client in $\hat{C}_{k}$ receives $V_{t,sync}$ and $b_{t,sync}$ from
the server and updates their local model

22: $V_{t,i}\mathrel{+}=V_{t,sync}-\Delta V_{t,i}$,
$b_{t,i}\mathrel{+}=b_{t,sync}-\Delta b_{t,i}$, $\Delta V_{t,i}=0$, $\Delta
b_{t,i}=0,\Delta t_{t,i}=0$

23: end if

24: end for

####  3.4.2 Priority Queue

The second enhancement to HetoFedBandit involves utilizing a priority queue
instead of a FIFO queue to determine the order in which to serve clusters
requesting collaboration. As is demonstrated in (Wang et al., 2020; Li and
Wang, 2022), the cumulative regret incurred by a federated bandit algorithm is
determined by the determinant ratios of the clients within the system: $\Delta
t_{t,i}\log\big{(}\frac{\det(V_{t,i})}{\det(V_{t,i}-\Delta V_{t,i}}\big{)}$.
Since the central server cannot assist all clusters at once, determinant
ratios of awaiting clients can increase as they linger in the queue. In the
original HetoFedBandit, clusters are attended based on their request order.
However, an earlier-joining cluster might have a slower regret accumulation
compared to a later one with a larger and faster growing determinant ratio. By
utilizing a priority queue that serves the clusters based on:
$\operatorname*{arg\,max}_{\hat{C}_{k}\in\hat{\mathcal{C}}}\sum_{i\in\hat{C}_{k}}\Delta
t_{t,i}\log(\frac{\det(V_{t,i})}{\det(V_{t,i}-\Delta V_{t,i}})$ the server
ensures clusters are addressed in an order that minimizes the system-wide
cumulative regret.

##  4 Experiments

In this section, we investigate the empirical performance of HetoFedBandit and
HetoFedBandit-E, by comparing them against several baseline models on both
simulated and real-world datasets.

###  4.1 Baselines

In our evaluation, we compare our proposed HetoFedBandit algorithm with
several representative algorithms from both the clustered and federated bandit
learning domains. We compare against, LinUCB algorithm from (Abbasi-Yadkori et
al., 2011), DisLinUCB (Wang et al., 2020), FCLUB_DC (Liu et al., 2022), and
DyClu (Li et al., 2021). To ensure compatibility with our setting, we set the
number of local servers in FCLUB_DC to be equal to the number of clients.

###  4.2 Synthetic Dataset

We first present the results of our empirical analysis of HetoFedBandit and
HetoFedBandit-E on a synthetic dataset.

##### Synthetic Dataset Generation

In this section, we describe the pre-processing procedure for the synthetic
dataset used in Section 4.2. We first create an action pool
$\\{x_{k}\\}_{k=1}^{K}$ where $x$ is sampled from $N(0_{d},I_{d})$. To create
a set of $N$ clients in accordance with our environment assumptions, we first
sample $M$ cluster centers $\\{\theta_{m}\\}_{m=1}^{M}$ from $N(0_{d},I_{d})$
that are $\gamma+2\epsilon$ away from each other (enforced via rejection
sampling). Then, we randomly assign each client index $i\in N$ to one of the
$M$ clusters. To generate each $\theta_{i}$, we first sample a vector on the
unit d-sphere, then we scale it by a value uniformly sampled from
$[0,\epsilon]$ with $\epsilon=1/N\sqrt{T}$ and add it to the cluster center
$\theta_{k}$ corresponding to the cluster client $i$ was assigned to. At each
time step $t=1,2,...T$ for each client in $[N]$ is presented a subset of $25$
arms are sampled from $\\{x_{k}\\}_{k=1}^{K}$, and shared with the client. The
reward of the selected arm is generated by the linear function governed by the
corresponding bandit parameter and context. In our experiments, we chose
$d=25$, $K=1000$, $N=50$, $M=5$, and $T=3000$. Since we conducted our
experiment in a synthetic environment, we utilized the known values of
$\gamma=0.85$, $\sigma=0.1$, and chose $\lambda=0.1$, $\delta=0.1$ for our
algorithm’s hyper-parameters. Note that while we utilized the known values for
$\sigma$ and $\gamma$ in our experiment, these hyper-parameters can be tuned
in practice using the “doubling-trick”, where the algorithm is repeatedly run
in the same environment with increasing horizons (Auer et al., 1995; Besson
and Kaufmann, 2018). We present additional sensitivity analysis of the
environmental parameters in Appendix F due to the space limit.

##### Results

In Figure 2(a), we compare the accumulated regret of the different bandit
algorithms on the simulated dataset. HetoFedBandit and HetoFedBandit-E
outperform the other decentralized bandit baselines, with HetoFedBandit-E
achieving a regret that is closest to the state-of-the-art centralized
clustering bandit algorithm, DyClu. We observe that DisLinUCB experiences
linear regret in our heterogeneous environment. While N-Independent LinUCB
achieves sublinear regret, its cumulative regret is higher than our
HetoFedBandit due to the absence of collaboration among similar clients.
HetoFedBandit outperforms FCLUB_DC, underscoring the strength of our federated
clustered bandit approach in a heterogeneous setting. FCLUB_DC’s fixed
clustering schedule results in delayed cluster identification, diminishing the
quality of client collaboration. Notably, while FCLUB_DC presumes the central
server aids all local client clusters concurrently at each step, HetoFedBandit
still excels despite adhering to a single model assumption in federated
learning. We further present an ablation study on our empirical enhancements
in Appendix E.

(a) Accumulative Regret

(b) Communication Cost

Figure 2: Experimental Results on Simulated Dataset

In Figure 2(b), we observe that our algorithms exhibit the lowest
communication cost among baselines while achieving encouraging regret. This
demonstrates the communication efficiency of our approach, which is a critical
factor in distributed systems. Notably, HetoFedBandit-E has a higher
communication cost compared to HetoFedBandit, because the dynamic re-
clustering requires the additional sharing of sufficient statistics from
clients outside the cluster that requests collaboration.

###  4.3 LastFM Dataset

In this section, we present the results of our empirical analysis of
HetoFedBandit and HetoFedBandit-E on the LastFM dataset, demonstrating their
effectiveness in distributed recommender systems.

##### LastFM Dataset

The dataset used in this experiment is extracted from the LastFM-2k dataset,
which originally contains 1892 clients (users) and 16632 items (artists)
(Cantador et al., 2011). Each “client” can be considered as an edge device
serving a particular user in a distributed recommender system. The “listened
artists” of each client are treated as positive feedback. To adapt this
dataset for our experiments, we kept clients with over 350 observations,
resulting in a dataset with $N=75$ clients and $T=41284$ interactions. The
dataset was pre-processed following the procedure in (Cesa-Bianchi et al.,
2013) to accommodate the linear bandit setting (with $d=25$ and the action set
$K=25$). Since the environmental parameters $\sigma,\gamma$ are unknown for
this real-world dataset, we directly tuned the values of our test threshold
$\upsilon^{c}=0.01$, $T_{0}=5000$, and $\alpha_{t,i}=\alpha=0.3\ \forall
i\in\left[N\right]$, $\forall t\in T$ using a grid search.

##### Results

We show that our models group users with similar musical preferences for
collaborative model learning, enhancing recommendation quality compared to
other distributed bandit learning methods. In Figure 3, we present the
normalized cumulative rewards and communication costs of the federated bandit
algorithms on the LastFM dataset. We observe that HetoFedBandit-E outperforms
the other decentralized bandit baselines on the real-world dataset, achieving
the highest average normalized reward. In line with observations made using
synthetic datasets, DisLinUCB’s performance is suboptimal in environments with
heterogeneous clients, demonstrated by NIndepLinUCB outperforming DisLinUCB.
Moreover, while the normalized cumulative reward of FCLUB_DC shows an
improving trend over time, its prefixed-clustering schedule delays the
identification of the underlying cluster structure compared to HetoFedBandit
and HetoFedBandit-E.

Notably, our basic algorithm design, HetoFedBandit, falls short of
NIndepLinUCB on real-world data due to its single-timestep cluster estimation.
In a simulated environment, where context vectors adhere closely to Assumption
3, one-time cluster estimation post-exploration is usually sufficient.
However, in real-world datasets, the distribution of context vectors may
evolve over time, leading to potential inaccuracies in the clusters initially
estimated after the exploration phase. This underlines the importance of our
empirical enhancements, which incorporates dynamic data-dependent re-
clustering, demonstrating its ability to adapt to shifts in the observed
context distribution.

In Figure 3(b), we observe that our algorithms once again exhibit the lowest
communication cost among the compared baselines. Similar to our observations
in Section 4.2, HetoFedBandit-E has a higher communication cost compared to
HetoFedBandit.

(a) Normalized Accumulated Reward

(b) Communication Cost

Figure 3: Experimental Results on LastFM Dataset

##  5 Conclusion

In this work, we address the challenge of heterogeneous clients in federated
bandit learning by introducing HetoFedBandit. Our approach combines the
strengths of federated learning and collaborative bandit learning, enabling
efficient communication and learning among clients with diverse objectives. We
demonstrate through rigorous theoretical analysis that participating clients
achieve regret reduction compared to their independent learning across various
environmental settings, thereby motivating all clients to participate in such
a federated learning system. We also empirically demonstrate that our
algorithm achieves encouraging performance compared to existing federated
bandit learning solutions on both simulated and real-world datasets.

Our work not only addresses the limitations of existing federated bandit
learning solutions, but also opens up new possibilities for practical
applications in distributed systems. Our current approach requires that each
client within the federated learning system trusts the central server to only
facilitate collaboration for social good. However, in the real world, this
“trust” is not something that should be naively assumed. To realize a truly
federated model of bandit learning, the power to decide on collaboration
should be transferred to the clients. In this regard, future research should
consider viewing federated learning through the lens of mechanism design, so
that each client perceives participating in the federated learning system as
their best course of action.

Acknowledgments and Disclosure of Funding

We thank the anonymous reviewers for their insightful suggestions and
comments. This material is based upon work supported by the NSF Graduate
Research Fellowship under Grant No. 1842490 and NSF Award IIS-2213700 and
IIS-2128019.

##  Appendix A Technical Lemmas

In this section, we introduce the technical lemmas utilized in the subsequent
proofs in this paper.

######  Lemma 5 (Lemma 11 in Abbasi-Yadkori et al. (2011))

Let $\\{X_{t}\\}_{t=1}^{\infty}$ be a sequence in $\mathbb{R}^{d}$, $V$ is a
$d\times d$ positive definite matrix and define
$\bar{V}_{t}=V+\sum_{s=1}^{t}X_{s}X_{s}^{\top}$, where $V=\lambda I$.
Additionally we have that $\lambda_{\min}(V)\geq\max(1,L^{2})$ and
$\|X_{t}\|_{2}\leq L$ for all $t$, then

$\log\biggr{(}\frac{\det(\bar{V_{n}})}{\det(V)}\biggr{)}\leq\sum_{t=1}^{T}\|X_{t}\|^{2}_{\bar{V}_{t-1}^{-1}}\leq
2\log\biggr{(}\frac{\det(\bar{V_{n}})}{\det(V)}\biggr{)}.$ (5)

######  Lemma 6 (Theorem 1 of Abbasi-Yadkori et al. (2011))

Let $\\{\mathcal{F}_{t}\\}_{t=0}^{\infty}$ be a filtration. Let
$\\{\eta_{t}\\}_{t=1}^{\infty}$ be a real-valued stochastic process such that
$\eta_{t}$ is $\mathcal{F}_{t}$-measurable, and $\eta_{t}$ follows
conditionally zero mean $R$-sub-Gaussian for some $R\geq 0$. Let
$\\{X_{t}\\}_{t=1}^{\infty}$ be an $\mathbb{R}^{d}$-valued stochastic process
such that $X_{t}$ is $\mathcal{F}_{t-1}$-measurable. Assume that $V$ is a
$d\times d$ positive definite matrix. For any $t>0$, define

$\displaystyle
V_{t}=V+\sum_{\tau=1}^{t}X_{\tau}X_{\tau}^{\top}\quad\mathcal{S}_{t}=\sum_{\tau=1}^{t}\eta_{\tau}X_{\tau}.$

Then for any $\delta>0$, with probability at least $1-\delta$,

$\displaystyle||\mathcal{S}_{t}||_{V_{t}^{-1}}\leq
R\sqrt{2\log{\frac{\det(V_{t})^{1/2}}{\det(V)^{1/2}\delta}}},\quad\forall
t\geq 0.$

######  Lemma 7 (Determinant-Trace Inequality)

Suppose $X_{1},X_{2},...,X_{t}\in\mathbb{R}^{d}$ and for any $1\leq\tau\leq
t$, $\|X_{\tau}\|_{2}\leq L$, Let $\overline{V_{t}}=\lambda
I+\sum_{\tau=1}^{t}X_{\tau}X_{\tau}^{\top}$ for some $\lambda>0$. Then,

$\displaystyle\det(\overline{V_{t}})\leq(\lambda+tL^{2}/d)^{d}.$

######  Lemma 8 (Lemma 12 from (Li et al., 2021))

When the underlying bandit parameters $\theta_{i}^{*}$ and $\theta_{j}^{*}$ of
two observation sequence $\mathcal{H}_{t-1,i}$ and $\mathcal{H}_{t-1,j}$ from
client $i$ and $j$ are not the same, the probability that the cluster
identification phase clusters them together corresponds to the type-II error
probability given in Lemma 10, which can be upper bounded by:

$P\left(S(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})\leq\upsilon^{c}\big{|}\|\theta_{i}^{*}-\theta_{j}^{*}\|>\epsilon\right)\leq
F(\upsilon^{c};d,\psi^{d}),$

under the condition that both
$\lambda_{\min}(\sum_{(\mathbf{x}_{k},y_{k})\in\mathcal{H}_{t-1,i}}\mathbf{x}_{k}\mathbf{x}_{k}^{\top})$
and
$\lambda_{\min}(\sum_{(\mathbf{x}_{k},y_{k})\in\mathcal{H}_{t-1,2}}\mathbf{x}_{k}\mathbf{x}_{k}^{\top})$
are at least $\frac{2\psi^{d}\sigma^{2}}{\gamma^{2}}$.

######  Lemma 9 (Lemma B1 from Li and Wang (2022))

Denote the number of observations that have been used to update
$\\{V_{i,t},b_{i,t}\\}$ as $\tau_{i}$, i.e., $V_{i,t}=\lambda
I+\sum_{s=1}^{\tau_{i}}\mathbf{x}_{s}\mathbf{x}_{s}^{\top}$. Then under
Assumption 3, with probability at least $1-\delta$, we have:

$\displaystyle\lambda_{\min}(V_{i,t})\geq\lambda+\frac{\lambda_{c}\tau_{i}}{8},$

$\forall\tau_{i}\in\\{\tau_{min},\tau_{min}+1,\dots,T\\},i\in[N]$, where
$\tau_{min}=\lceil\frac{64}{3\lambda_{c}}\log(\frac{2NTd}{\delta})\rceil$.

###### Lemma 10

Lemma 3 from Li et al. (2021) When $\mathbf{X}_{1}$ and $\mathbf{X}_{2}$ are
rank-sufficient, the type-II error probability can be upper bounded by,

$P\big{(}s(\mathcal{H}_{t-1,1},\mathcal{H}_{t-1,2})\leq\upsilon\,|\,\|\theta_{1}-\theta_{2}\|>\epsilon\big{)}\leq
F\Big{(}\upsilon^{c};d,\frac{||\theta_{1}^{*}-\theta_{2}^{*}||^{2}/\sigma^{2}}{{1}/{\lambda_{min}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1})}+{1}/{\lambda_{min}(\mathbf{X}_{2}^{\top}\mathbf{X}_{2})}}\Big{)}.\\\
$

##  Appendix B Proof of Theorem 1

In this section, we provide the full proof of Theorem 1, which states that
utilizing our homogeneity test with threshold $\upsilon^{c}\geq
F^{-1}(1-\frac{\delta}{N^{2}};df,\psi^{c})$, after the exploration phase of
length $T_{0}=\frac{16\psi^{d}\sigma^{2}}{\lambda_{c}\gamma^{2}}$, the
clusters
$\hat{\mathcal{C}}=\\{\hat{C}_{1},\hat{C}_{2},...,\hat{C}_{\hat{M}}\\}$
estimated by HetoFedBandit match the ground-truth clusters of the environment
$\mathcal{C}=\\{C_{1},C_{2},...,C_{M}\\}$.

The homogeneity test statistic $s(\mathcal{H}_{t-1,1},\mathcal{H}_{t-1,2})$
follows a non-central $\chi^{2}$ distribution
$s(\mathcal{H}_{t-1,1},\mathcal{H}_{t-1,2})\sim\chi^{2}(df,\psi)$, where the
degree of freedom

$df=rank(\mathbf{X}_{1})+rank(\mathbf{X}_{2})-rank\left(\left[\begin{matrix}\mathbf{X}_{1}\mathbf{X}_{2}\end{matrix}\right]\right),$

and the non-centrality parameter

$\psi=\frac{1}{\sigma^{2}}\left[\begin{matrix}\mathbf{X}_{1}\theta_{1}\mathbf{X}_{2}\theta_{2}^{*}\end{matrix}\right]^{\top}\left[\mathbf{I}_{t_{1}+t_{2}}-\left[\begin{matrix}\mathbf{X}_{1}\mathbf{X}_{2}\end{matrix}\right]\left(\mathbf{X}_{1}^{\top}\mathbf{X}_{1}+\mathbf{X}_{2}^{\top}\mathbf{X}_{2}\right)^{-}\left[\begin{matrix}\mathbf{X}_{1}^{\top}&\mathbf{X}_{2}^{\top}\end{matrix}\right]\right]\left[\begin{matrix}\mathbf{X}_{1}\theta_{1}\mathbf{X}_{2}\theta_{2}^{*}\end{matrix}\right]$

(Li et al., 2021).

Based on the definition and properties of the test statistic, we next prove
two corollaries. First we will prove that with high probability
$\mathcal{C}\subseteq\hat{\mathcal{C}}$. Then we will prove that
$\hat{\mathcal{C}}\subseteq\mathcal{C}$. As a result, the conjunction of these
events holding simultaneously demonstrates that
$\hat{\mathcal{C}}=\mathcal{C}$, proving that our estimated clusters are
correct with a high probability.

###  B.1 Lower Bounding $P(\mathcal{C}\subseteq\hat{\mathcal{C}})$

Recall that based on our cluster definition presented in Assumption 1, all
clients that belong to the same cluster are within $\epsilon$ of each other.
We denote the ground-truth client graph $G^{*}$ as the graph where $\exists
e(i,j)\in G^{*}\,\leavevmode\nobreak\ \forall i,j\in N$ where
$\|\theta_{i}^{*}-\theta_{j}^{*}\|\leq\epsilon$. By Assumption 2, we know that
clients that do not belong to the same cluster are separated by $\gamma$, so
that the ground-truth clusters $\mathcal{C}$ are the maximal cliques of
$G^{*}$. Thus, in order to prove that
$P(\mathcal{C}\subseteq\hat{\mathcal{C}})$, we need to show that the set of
edges in the ground-truth client graph $G^{*}$ is a subset of the edges in the
estimated client graph $G$. To achieve this, we need to prove an upper-bound
of the type-I error probability of the homogeneity test, which corresponds to
the probability that our algorithm fails to cluster two clients together when
the underlying bandit parameters
$\|\theta_{i}^{*}-\theta_{j}^{*}\|\leq\epsilon$.

###### Lemma 11

The type-I error probability of the test can be upper bounded by:

$P\big{(}s(\mathcal{H}_{t-1,1},\mathcal{H}_{t-1,2})>\upsilon\,|\,\|\theta_{1}^{*}-\theta_{2}^{*}\|\leq\epsilon\big{)}\leq
1-F(\upsilon;df,\psi^{c}),$

where $F(\upsilon;df,\psi^{c})$ denotes the cumulative density function (CDF)
of distribution $\chi^{2}(df,\psi^{c})$ evaluated at $\upsilon$, and
$\psi^{c}:=\frac{1}{\sigma^{2}}$ denotes its non-centrality parameter.

Proof  Denote $\zeta=\theta_{2}^{*}-\theta_{1}^{*}$. Then
$\theta_{2}^{*}=\theta_{1}^{*}+\zeta$. When $\|\zeta\|\leq\epsilon$, the non-
centrality parameter $\psi$ becomes:

$\begin{split}\psi=\frac{1}{\sigma^{2}}&\left[\begin{matrix}\mathbf{X}_{1}\theta_{1}^{*}\\\
\mathbf{X}_{2}(\theta_{1}^{*}+\zeta)\end{matrix}\right]^{\top}\left[\mathbf{I}_{t_{1}+t_{2}}-\left[\begin{matrix}\mathbf{X}_{1}\\\
\mathbf{X}_{2}\end{matrix}\right]\left(\mathbf{X}_{1}^{\top}\mathbf{X}_{1}+\mathbf{X}_{2}^{\top}\mathbf{X}_{2}\right)^{-1}\left[\begin{matrix}\mathbf{X}_{1}^{\top}&\mathbf{X}_{2}^{\top}\end{matrix}\right]\right]\left[\begin{matrix}\mathbf{X}_{1}\theta_{1}^{*}\\\
\mathbf{X}_{2}(\theta_{1}^{*}+\zeta)\end{matrix}\right],\\\
\sigma^{2}\psi=&\left[\begin{matrix}\mathbf{X}_{1}\theta_{1}^{*}\\\
\mathbf{X}_{2}\theta_{1}^{*}\end{matrix}\right]^{\top}\left[\mathbf{I}_{t_{1}+t_{2}}-\left[\begin{matrix}\mathbf{X}_{1}\\\
\mathbf{X}_{2}\end{matrix}\right]\left(\left[\begin{matrix}\mathbf{X}_{1}^{\top}&\mathbf{X}_{2}^{\top}\end{matrix}\right]\left[\begin{matrix}\mathbf{X}_{1}\\\
\mathbf{X}_{2}\end{matrix}\right]\right)^{-1}\left[\begin{matrix}\mathbf{X}_{1}^{\top}&\mathbf{X}_{2}^{\top}\end{matrix}\right]\right]\left[\begin{matrix}\mathbf{X}_{1}\theta_{1}^{*}\\\
\mathbf{X}_{2}\theta_{1}^{*}\end{matrix}\right]\\\
&+\left[\begin{matrix}\mathbf{X}_{1}\theta_{1}^{*}\\\
\mathbf{X}_{2}\theta_{1}^{*}\end{matrix}\right]^{\top}\left[\mathbf{I}_{t_{1}+t_{2}}-\left[\begin{matrix}\mathbf{X}_{1}\\\
\mathbf{X}_{2}\end{matrix}\right]\left(\left[\begin{matrix}\mathbf{X}_{1}^{\top}&\mathbf{X}_{2}^{\top}\end{matrix}\right]\left[\begin{matrix}\mathbf{X}_{1}\\\
\mathbf{X}_{2}\end{matrix}\right]\right)^{-1}\left[\begin{matrix}\mathbf{X}_{1}^{\top}&\mathbf{X}_{2}^{\top}\end{matrix}\right]\right]\left[\begin{matrix}0\\\
\mathbf{X}_{2}\zeta\end{matrix}\right]\\\ &+\left[\begin{matrix}0\\\
\mathbf{X}_{2}\zeta\end{matrix}\right]^{\top}\left[\mathbf{I}_{t_{1}+t_{2}}-\left[\begin{matrix}\mathbf{X}_{1}\\\
\mathbf{X}_{2}\end{matrix}\right]\left(\left[\begin{matrix}\mathbf{X}_{1}^{\top}&\mathbf{X}_{2}^{\top}\end{matrix}\right]\left[\begin{matrix}\mathbf{X}_{1}\\\
\mathbf{X}_{2}\end{matrix}\right]\right)^{-1}\left[\begin{matrix}\mathbf{X}_{1}^{\top}&\mathbf{X}_{2}^{\top}\end{matrix}\right]\right]\left[\begin{matrix}\mathbf{X}_{1}\theta_{1}^{*}\\\
\mathbf{X}_{2}\theta_{1}^{*}\end{matrix}\right]\\\ &+\left[\begin{matrix}0\\\
\mathbf{X}_{2}\zeta\end{matrix}\right]^{\top}\left[\mathbf{I}_{t_{1}+t_{2}}-\left[\begin{matrix}\mathbf{X}_{1}\\\
\mathbf{X}_{2}\end{matrix}\right]\left(\left[\begin{matrix}\mathbf{X}_{1}^{\top}&\mathbf{X}_{2}^{\top}\end{matrix}\right]\left[\begin{matrix}\mathbf{X}_{1}\\\
\mathbf{X}_{2}\end{matrix}\right]\right)^{-1}\left[\begin{matrix}\mathbf{X}_{1}^{\top}&\mathbf{X}_{2}^{\top}\end{matrix}\right]\right]\left[\begin{matrix}0\\\
\mathbf{X}_{2}\zeta\end{matrix}\right].\\\ \end{split}$

Since $\left[\begin{matrix}\mathbf{X}_{1}\theta_{1}^{*}\\\
\mathbf{X}_{2}\theta_{1}^{*}\end{matrix}\right]$ is in the column space of
$\left[\begin{matrix}\mathbf{X}_{1}\\\ \mathbf{X}_{2}\end{matrix}\right]$, the
first term in the above result is zero. The second and third terms can be
shown equal to zero as well using the property that matrix product is
distributive with respect to matrix addition, which leaves us only the last
term. Therefore, by substituting $\zeta=\theta_{2}^{*}-\theta_{1}^{*}$ back,
we obtain:

$\begin{split}\psi&=\frac{1}{\sigma^{2}}(\theta_{1}^{*}-\theta_{2}^{*})^{\top}\mathbf{X}_{2}^{\top}\mathbf{X}_{2}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1}+\mathbf{X}_{2}^{\top}\mathbf{X}_{2})^{-1}\mathbf{X}_{1}^{\top}\mathbf{X}_{1}(\theta_{1}^{*}-\theta_{2}^{*}),\\\
&\leq\frac{1}{\sigma^{2}}\|\theta_{1}^{*}-\theta_{2}^{*}\|^{2}\lambda_{\text{max}}(\mathbf{X}_{2}^{\top}\mathbf{X}_{2}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1}+\mathbf{X}_{2}^{\top}\mathbf{X}_{2})^{-1}\mathbf{X}_{1}^{\top}\mathbf{X}_{1}),\\\
&\leq\frac{\epsilon^{2}}{\sigma^{2}}\lambda_{\text{max}}(\mathbf{X}_{2}^{\top}\mathbf{X}_{2}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1}+\mathbf{X}_{2}^{\top}\mathbf{X}_{2})^{-1}\mathbf{X}_{1}^{\top}\mathbf{X}_{1}).\\\
\end{split}$

The first inequality uses the Rayleigh-Ritz theorem, and the second inequality
is a result of Assumption 1. Furthermore, we can use the relation
$\mathbf{Y}(\mathbf{X}+\mathbf{Y})^{-1}\mathbf{X}=(\mathbf{X}^{-1}+\mathbf{Y}^{-1})^{-1}$,
where $\mathbf{X}$ and $\mathbf{Y}$ are both invertible matrices, to further
simplify our upper bound for $\psi$. This relation can be derived by taking
inverse on both sides of the equation
$\mathbf{X}^{-1}(\mathbf{X}+\mathbf{Y})\mathbf{Y}^{-1}=\mathbf{X}^{-1}\mathbf{X}\mathbf{Y}^{-1}+\mathbf{X}^{-1}\mathbf{Y}\mathbf{Y}^{-1}=\mathbf{Y}^{-1}+\mathbf{X}^{-1}$.
This gives us the following:

$\displaystyle\psi$
$\displaystyle=\frac{\epsilon^{2}}{\sigma^{2}}\lambda_{\max}\left(\big{(}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1})^{-1}+(\mathbf{X}_{2}^{\top}\mathbf{X}_{2})^{-1}\big{)}^{-1}\right),$
$\displaystyle\leq\frac{\epsilon^{2}}{\sigma^{2}}\frac{1}{\lambda_{\min}((\mathbf{X}_{1}^{\top}\mathbf{X}_{1})^{-1}+(\mathbf{X}_{2}^{\top}\mathbf{X}_{2})^{-1})},$
$\displaystyle\leq\frac{\epsilon^{2}}{\sigma^{2}}\frac{1}{\lambda_{\min}((\mathbf{X}_{1}^{\top}\mathbf{X}_{1})^{-1})+\lambda_{\min}((\mathbf{X}_{2}^{\top}\mathbf{X}_{2})^{-1})},$
$\displaystyle\leq\frac{\epsilon^{2}}{\sigma^{2}}\frac{1}{\frac{1}{\lambda_{\max}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1})}+\frac{1}{\lambda_{\max}(\mathbf{X}_{2}^{\top}\mathbf{X}_{2})}},$
$\displaystyle=\frac{\epsilon^{2}}{\sigma^{2}}\frac{\lambda_{\max}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1})\times\lambda_{\max}(\mathbf{X}_{2}^{\top}\mathbf{X}_{2})}{\lambda_{\max}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1})+\lambda_{\max}(\mathbf{X}_{2}^{\top}\mathbf{X}_{2})},$
$\displaystyle\leq\frac{\epsilon^{2}}{\sigma^{2}}\max\\{\lambda_{\max}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1}),\lambda_{\max}(\mathbf{X}_{2}^{\top}\mathbf{X}_{2})\\}.$

The last inequality holds because

$\displaystyle\frac{\lambda_{\max}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1})}{\lambda_{\max}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1})+\lambda_{\max}(\mathbf{X}_{2}^{\top}\mathbf{X}_{2})}\leq
1\text{ and
}\frac{\lambda_{\max}(\mathbf{X}_{2}^{\top}\mathbf{X}_{2})}{\lambda_{\max}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1})+\lambda_{\max}(\mathbf{X}_{2}^{\top}\mathbf{X}_{2})}\leq
1.$

Denote the number of observations in $\mathbf{X}_{i}$ as $\tau_{i}$.
Furthermore, since $\|x_{t,i}\|\leq 1$, we know that
$\lambda_{\max}(\mathbf{X}_{i}^{\top}\mathbf{X}_{i})\leq\tau_{i}$. Thus we can
further upper bound

$\displaystyle\psi$
$\displaystyle\leq\frac{\epsilon^{2}}{\sigma^{2}}\max\\{\lambda_{\max}(\mathbf{X}_{1}^{\top}\mathbf{X}_{1}),\lambda_{\max}(\mathbf{X}_{2}^{\top}\mathbf{X}_{2})\\},$
$\displaystyle\leq\frac{\epsilon^{2}}{\sigma^{2}}\max\\{\tau_{i},\tau_{j}\\},$
$\displaystyle\leq\frac{\epsilon^{2}}{\sigma^{2}}T.$

Assumption 1 tells us that $\epsilon=\frac{1}{N\sqrt{T}}$ for $(i,j)$ in the
same cluster ${C}_{k}$.

$\displaystyle\psi$
$\displaystyle\leq\frac{T}{\sigma^{2}N^{2}T}\leq\frac{1}{\sigma^{2}}:=\psi^{c}.$

Therefore, when $\|\theta_{1}^{*}-\theta_{2}^{*}\|<\epsilon$, the test
statistic
$s(\mathcal{H}_{t-1,1},\mathcal{H}_{t-1,2})\sim\chi^{2}(df,0,\psi^{c})$. The
type-I error probability can be upper bounded by
$P\big{(}s(\mathcal{H}_{t-1,1},\mathcal{H}_{t-1,2})>\upsilon\,\big{|}\,\|\theta_{1}^{*}-\theta_{2}^{*}\|\big{)}\leq
1-F(\upsilon;df,\psi^{c})$, which concludes the proof of Lemma 11.

###### Corollary 12

Under the condition that we set the threshold $\upsilon$ to $\upsilon^{c}\geq
F^{-1}(1-\frac{\delta}{N^{2}},df,\psi^{c})$, we have
$P(\mathcal{C}\subseteq\hat{\mathcal{C}})\geq 1-\delta$.

Proof  In our setting (Assumption 1), all users who are within
$\epsilon=\frac{1}{N\sqrt{T}}$ of each other belong to the same ground-truth
cluster. Our algorithm uses the pairwise homogeneity test to assess whether
each pair of clients is within $\epsilon$ of each other. As we showed in Lemma
11, the type-I error probability of our pairwise neighbor identification is
upper-bounded by $1-F(\upsilon;df,\psi^{c})$. Therefore, to achieve a type-I
error probability of $\delta/N^{2}$ between two individual clients, we can
solve for the required threshold $\upsilon^{c}$

$\displaystyle\frac{\delta}{N^{2}}$ $\displaystyle\leq
1-F(\upsilon;df,\psi^{c}),$ $\displaystyle\Rightarrow F(\upsilon;df,\psi^{c})\
$ $\displaystyle\leq 1-\frac{\delta}{N^{2}},$ $\displaystyle\Rightarrow
F^{-1}(1-\frac{\delta}{N^{2}},df,\psi^{c})$ $\displaystyle\leq\upsilon^{c}.$

Taking the union bound over all $N^{2}$ pairwise tests proves the that the set
of edges in the ground-truth client graph $G^{*}$ is a subset of the edges
estimated client graph $G$. Therefore the corollary is proven.

###  B.2 Lower Bounding $P(\hat{\mathcal{C}}\subseteq\mathcal{C})$

In this section, we prove that with high probability
$P(\hat{\mathcal{C}}\subseteq\mathcal{C})$. To achieve this, we demonstrate
that the set of edges in the estimated client graph $G$ is a subset of the
ground-truth edges in $G^{*}$. To achieve this, we utilize the type-II error
probability upper-bound to ensure that with high probability clients with
different underlying parameters are not clustered together. Using this type-II
error probability, we follow similar steps in Lemma 13 of (Li et al., 2021) to
prove:

###### Lemma 13

If the cluster identification module clusters observation history
$\mathcal{H}_{t-1,i}$ and $\mathcal{H}_{t-1,j}$ together, the probability that
they actually have the same underlying bandit parameters is denoted as
$P\big{(}\|\theta^{*}_{i}-\theta^{*}_{j}\|\leq\epsilon|s(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})\leq\upsilon^{c}\big{)}$.

$P\big{(}\|\theta^{*}_{i}-\theta^{*}_{j}\|\leq\epsilon|s(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})\leq\upsilon^{c}\big{)}\geq
F(\upsilon^{c};df,\psi^{c}),$

under the condition that both
$\lambda_{\min}\big{(}\sum_{(\mathbf{x}_{k},y_{k})\in\mathcal{H}_{t-1,i}}\mathbf{x}_{k}\mathbf{x}_{k}^{\top}\big{)}$
and
$\lambda_{\min}\big{(}\sum_{(\mathbf{x}_{k},y_{k})\in\mathcal{H}_{t-1,j}}\mathbf{x}_{k}\mathbf{x}_{k}^{\top}\big{)}$
are at least $\frac{2\psi^{d}\sigma^{2}}{\gamma^{2}}$, where
$\psi^{d}=F^{-1}\big{(}\frac{(1-F(\upsilon^{c};d,\psi^{c}))}{M-1};d,\upsilon^{c}\big{)}$.

Proof

Compared with the type-I and type-II error probabilities given in Lemma 11 and
8, the probability
$P(\|\theta^{*}_{i}-\theta^{*}_{j}\|\leq\epsilon|S(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})\leq\upsilon^{c})$
also depends on the population being tested on.

Denote the events
$\big{\\{}\|\theta^{*}_{i}-\theta^{*}_{j}\|>\epsilon\big{\\}}\cap\big{\\{}S(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})>\upsilon^{c}\big{\\}}$
as True Positive ($TP$),
$\big{\\{}\|\theta^{*}_{i}-\theta^{*}_{j}\|\leq\epsilon\big{\\}}\cap\big{\\{}S(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})\leq\upsilon^{c}\big{\\}}$
as True Negative ($TN$),
$\big{\\{}\|\theta^{*}_{i}-\theta^{*}_{j}\|\leq\epsilon\big{\\}}\cap\big{\\{}S(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})>\upsilon^{c}\big{\\}}$
as False Positive ($FP$), and
$\big{\\{}\|\theta^{*}_{i}-\theta^{*}_{j}\|>\epsilon\big{\\}}\cap\big{\\{}S(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})\leq\upsilon^{c}\big{\\}}$
as False Negative ($FN$) of cluster identification, respectively. We can
rewrite the probabilities in Lemma 11, 8 and 13 as:

$\displaystyle
P\big{(}S(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})>\upsilon^{c}|\|\theta^{*}_{i}-\theta^{*}_{j}\|\leq\epsilon\big{)}$
$\displaystyle=\frac{P(FP)}{P(TN+FP)}\leq 1-F(\upsilon^{c};df,\psi^{c}),$
$\displaystyle
P\big{(}s(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})\leq\upsilon^{c}|\|\theta^{*}_{i}-\theta^{*}_{j}\|>\epsilon\big{)}$
$\displaystyle=\frac{P(FN)}{P(FN+TP)}\leq F(\upsilon^{c};df,\psi^{d}),$
$\displaystyle
P\big{(}\|\theta^{*}_{i}-\theta^{*}_{j}\|\leq\epsilon|s(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})\leq\upsilon^{c}\big{)}$
$\displaystyle=\frac{P(TN)}{P(TN+FN)}>\frac{1}{1+\frac{P(FN)}{P(TN)}}.$

We can upper bound $\frac{P(FN)}{P(TN)}$ by:

$\frac{P(FN)}{P(TN)}\leq\frac{P(TP+FN)}{P(TN+FP)}\cdot\frac{F(\upsilon^{c};df,\psi^{d})}{F(\upsilon^{c};df,\psi^{c})},$

where $\frac{TP+FN}{TN+FP}$ denotes the ratio between the number of positive
instances ($\|\theta^{*}_{i}-\theta^{*}_{j}\|>\epsilon$) and negative
instances ($\|\theta^{*}_{i}-\theta^{*}_{j}\|\leq\epsilon$) in the population.
We can upper bound this ratio for any pair $(i,j)$ uniformly sampled from
$[N]$, since we need to run the test on all $N^{2}$ pairs. First we note that
$\frac{P(TP+FN)}{P(TN+FP)}=\frac{P(\lVert\theta_{i}^{*}-\theta_{j}^{*}\rVert>\epsilon)}{P(\lVert\theta_{i}^{*}-\theta_{j}^{*}\rVert\leq\epsilon)}.$
We upper-bound this ratio by giving a lower bound on the probability of two
randomly sampled clients belonging to the same cluster as
$P(\|\theta_{i}^{*}-\theta_{j}^{*}\|\leq\epsilon)$ with

$\displaystyle P(\|\theta_{i}^{*}-\theta_{j}^{*}\|\leq\epsilon)$
$\displaystyle=\sum_{k=1}^{M}\frac{|C_{k}|}{N}\times\frac{|C_{k}|-1}{N-1},$
$\displaystyle>\sum_{k=1}^{M}\big{(}\frac{|C_{k}|-1}{N-1}\big{)}^{2},$
$\displaystyle>\sum_{k=1}^{M}\frac{1}{M^{2}},$ $\displaystyle=\frac{1}{M}.$

The second inequality is true because the probability that two uniformly
sampled clients belonging to the same cluster is minimized when the clusters
are all of equal sizes. Therefore we have

$\displaystyle\frac{P(\lVert\theta_{i}^{*}-\theta_{j}^{*}\rVert>\epsilon)}{P(\lVert\theta_{i}^{*}-\theta_{j}^{*}\rVert\leq\epsilon)}\leq\frac{1-\frac{1}{M}}{\frac{1}{M}}=M-1.$

It is worth noting that in the event that $M=1$, the ratio can trivially be
upper bounded by $1$. With this upper bound of $\frac{P(FN)}{P(TN)}$, we can
now write:

$P\big{(}\|\theta^{*}_{i}-\theta^{*}_{j}\|\leq\epsilon|S(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})\leq\upsilon^{c}\big{)}\geq{1}/\Big{(}1+(M-1)\cdot\frac{F(\upsilon^{c};df,\psi^{d})}{F(\upsilon^{c};df,\psi^{c})}\Big{)}.$

Then by setting
$\psi^{d}=F^{-1}\big{(}\frac{(1-F(\upsilon^{c};df,\psi^{c}))}{(M-1)};df,\upsilon^{c}\big{)}$,
we have:

$P\big{(}\|\theta^{*}_{i}-\theta^{*}_{j}\|\leq\epsilon|S(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})\leq\upsilon^{c}\big{)}\geq{1}/\Big{(}1+(M-1)\cdot\frac{F(\upsilon^{c};df,\psi^{d})}{F(\upsilon^{c};df,\psi^{c})}\Big{)}=F(\upsilon^{c};df,\psi^{c}),$

and the lemma is proven.

###### Corollary 14

Under the condition that we set the threshold $\upsilon^{c}\geq
F^{-1}(1-\frac{\delta}{N^{2}},df,\psi^{c})$, with an exploration phase length
of
$T_{0}=\min\\{\frac{64}{3\lambda_{c}}\log(\frac{2Td}{\delta}),\frac{16\psi^{d}\sigma^{2}}{\lambda_{c}\gamma^{2}}\\}$,
we have $P(\hat{C}\subseteq C)\geq 1-\delta$.

Proof

Under Assumption 3, and with exploration length
$T_{0}=\min\\{\frac{64}{3\lambda_{c}}\log(2Td/\delta),\frac{16\psi^{d}\sigma^{2}}{\lambda_{c}\gamma^{2}}\\}$,
the application of Lemma 9 from (Li and Wang, 2022) gives with probability
$1-\delta$ that

$\lambda_{\min}(\mathbf{X}_{i}^{\top}\mathbf{X}_{i})\geq\frac{\lambda_{c}T_{0}}{8}=\frac{2\psi^{d}\sigma^{2}}{\gamma^{2}}.$

As a result, we can apply Lemma 13, which gives

$\displaystyle
P\big{(}\|\theta^{*}_{i}-\theta^{*}_{j}\|\leq\epsilon|s(\mathcal{H}_{t-1,i},\mathcal{H}_{t-1,j})\leq\upsilon^{c}\big{)}\geq
F(\upsilon^{c};df,\psi^{c}).$

Using the same steps as shown in Corollary 12, we can see our choice of test
statistic threshold $\upsilon^{c}\geq
F^{-1}(1-\frac{\delta}{N^{2}};df,\psi^{c})$ results in this event occurring
with probability $1-\frac{\delta}{N^{2}}$. Because our algorithm conducts this
pairwise homogeneity test across all pairs of clients, a union bound over all
$N^{2}$ pairwise tests proves the corollary.

The combination of Corollaries 12 and 14 prove that based on our choice of
$\upsilon^{c}$ and $T_{0}$, $\hat{\mathcal{C}}=\mathcal{C}$ with probability
$1-\delta$.

##  Appendix C Proof of Lemma 2

In this section, we present the complete proof of the confidence ellipsoids,
following similar steps to the proof of Theorem 2 in (Abbasi-Yadkori et al.,
2011).

Before we begin the proof, we will introduce a couple of useful notations to
prevent clutter. Recall from Section 3.1 that the design matrix of client $i$,
denoted as $\mathbf{X}_{i}$, only contains the observations made by client $i$
through timestep $t$ and does not include aggregated observations from other
clients. In this proof, we assume without loss of generality, that client $i$
is a member of ground-truth cluster $C_{k}$ and is therefore collaborating
with clients $j\in C_{k}$. As a result, we can denote
$\overline{V}_{t,i}^{-1}=\lambda
I+\sum_{j\in{C}_{k}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}$ and
$b_{t,i}=\sum_{j\in{C}_{k}}\mathbf{X}_{j}^{\top}(\mathbf{X}_{j}\theta_{j}^{*}+\eta_{j})$
due to the sharing of sufficient statistics among clients in ${C}_{k}$ (line
21 in Alg. 3), where we denote
$\eta_{j}=(\eta_{1,j},\eta_{2,j},...,\eta_{t,j})^{\top}$. Note that in this
proof, we only focus on the case where client $i$ is collaborating with
members of its ground-truth cluster, because in Theorem 1, we already prove
with high probability $\mathcal{C}=\hat{\mathcal{C}}$. In our subsequent
regret analysis in Theorem 3, we demonstrate that the regret incurred when
$\mathcal{C}\neq\hat{\mathcal{C}}$ is upper bounded by a constant.

Proof

$\displaystyle\hat{\theta}_{t,i}$
$\displaystyle=\overline{V}_{t,i}^{-1}b_{t,i},$
$\displaystyle=\overline{V}_{t,i}^{-1}\sum_{j\in
C_{k}}\mathbf{X}_{j}^{\top}(\mathbf{X}_{j}\theta_{j}^{*}+\eta_{j}),$
$\displaystyle=\overline{V}_{t,i}^{-1}\biggr{[}\sum_{j\in
C_{k}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}\theta_{j}^{*}+\sum_{j\in
C_{k}}\mathbf{X}_{j}^{\top}\eta_{j}\biggr{]},$
$\displaystyle=\overline{V}_{t,i}^{-1}\biggr{[}\sum_{j\in
C_{k}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}\theta_{i}^{*}+\sum_{j\in
C_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})+\sum_{j\in
C_{k}}\mathbf{X}_{j}^{\top}\eta_{j}\biggr{]},$
$\displaystyle=\overline{V}^{-1}_{t,i}\biggr{[}(\lambda I+\sum_{j\in
C_{k}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j})\theta_{i}^{*}-\lambda\theta_{i}^{*}+\sum_{j\in
C_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})+\sum_{j\in
C_{k}}\mathbf{X}_{j}^{\top}\eta_{j}\biggr{]},$
$\displaystyle=\overline{V}_{t,i}^{-1}\overline{V}_{t,i}\theta_{i}^{*}-\lambda\overline{V}_{t,i}^{-1}\theta_{i}^{*}+\overline{V}_{t,i}^{-1}\sum_{j\in
C_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})+\overline{V}_{t,i}^{-1}\sum_{j\in
C_{k}}\mathbf{X}_{j}^{\top}\eta_{j}.$

As a result, we have,

$\hat{\theta}_{t,i}-\theta_{i}^{*}=\overline{V}_{t,i}^{-1}\sum_{j\in
C_{k}}\mathbf{X}_{j}^{\top}\eta_{j}-\lambda\overline{V}_{t,i}^{-1}\theta_{i}^{*}+\overline{V}_{t,i}^{-1}\sum_{j\in
C_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*}).$

Applying the self-normalized bound gives:

$\displaystyle\big{\|}\theta_{i}^{*}-\hat{\theta}_{t,i}\big{\|}_{\overline{V}_{t,i}}$
$\displaystyle\leq\big{\|}\sum_{j\in
C_{k}}\mathbf{X}_{j}^{\top}\eta_{j}\big{\|}_{\overline{V}_{t,i}^{-1}}+\sqrt{\lambda}\big{\|}\theta_{i}^{*}\big{\|}_{\overline{V}_{t,i}^{-1}}+\bigg{\|}\sum_{j\in
C_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})\bigg{\|}_{\overline{V}_{t,i}^{-1}},$
$\displaystyle\leq\big{\|}\sum_{j\in
C_{k}}\mathbf{X}_{j}^{\top}\eta_{j}\big{\|}_{\overline{V}_{t,i}^{-1}}+\sqrt{\lambda}\|\theta_{i}^{*}\|_{2}+\bigg{\|}\sum_{j\in
C_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})\bigg{\|}_{\overline{V}_{t,i}^{-1}},$

where we used that
$\|\theta_{*}\|^{2}_{\overline{V}_{t,i}^{-1}}\leq\frac{1}{\lambda_{\min}(\overline{V}_{t,i})}\|\theta_{*}\|^{2}\leq\frac{1}{\lambda}\|\theta_{*}\|^{2}$.

The application of Lemma 6 and using $\|\theta_{i}^{*}\|_{2}\leq 1$ give:

$\displaystyle\|\theta_{i}^{*}-\hat{\theta}_{t,i}\|_{\overline{V}_{t,i}}$
$\displaystyle\leq\sigma\sqrt{2\log\biggr{(}\frac{\det(\overline{V}_{t,i})^{1/2}\det(\lambda
I)^{-1/2}}{\delta}\biggr{)}}+\sqrt{\lambda}+\bigg{\|}\sum_{j\in
C_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})\bigg{\|}_{\overline{V}_{t,i}^{-1}}:=\beta_{t,i},$

with probability at least $1-\delta$. Then with a union bound over all $N$
clients applied to the inequality above, we prove that
$\|\theta_{i}^{*}-\hat{\theta}_{t,i}\|_{\overline{V}_{t,i}}\leq\beta_{t,i},\forall
i,t$ with probability at least $1-N\delta$.

##  Appendix D Proof of Theorem 3

In this section we present the full proof of our algorithm’s cumulative regret
and communication upper bounds. Before proving the theorem, we will need to
prove the following lemmas.

######  Lemma 15 (Heterogeneity Term Bound)

Under the condition that the homogeneity test threshold $\upsilon^{c}$ is set
to be greater than $F^{-1}(1-\frac{\delta}{N^{2}},df,\psi^{c})$, and with an
exploration phase length of
$T_{0}=\min\\{\frac{64}{3\lambda_{c}}\log(\frac{2Td}{\delta}),\frac{16\psi^{d}\sigma^{2}}{\lambda_{c}\gamma^{2}}\\}$
we have with probability $1-\delta$:

$\bigg{\|}\sum_{j\in{C}_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})\bigg{\|}_{\overline{V}_{t,i}^{-1}}\leq
1.$

Proof

$\displaystyle\|\sum_{j\in
C_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})\|_{\overline{V}_{t,i}^{-1}}$
$\displaystyle\leq\sum_{j\in
C_{k}\setminus\\{i\\}}\|\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})\|_{\overline{V}_{t,i}^{-1}},$
$\displaystyle=\sum_{j\in
C_{k}\setminus\\{i\\}}\sqrt{(\theta_{j}^{*}-\theta_{i}^{*})^{\top}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\lambda
I+\sum_{i\in
C_{k}}\mathbf{X}_{i}^{\top}\mathbf{X}_{i})^{-1}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})},$
$\displaystyle\leq\sum_{j\in
C_{k}\setminus\\{i\\}}\sqrt{(\theta_{j}^{*}-\theta_{i}^{*})^{\top}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\mathbf{X}_{j}^{\top}\mathbf{X}_{j})^{-1}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})},$
$\displaystyle\leq\sum_{j\in
C_{k}\setminus\\{i\\}}\|\theta_{j}^{*}-\theta_{i}^{*}\|\sqrt{\lambda_{\text{max}}(\mathbf{X}_{j}^{\top}\mathbf{X}_{j})},$
$\displaystyle\leq\sum_{j\in
C_{k}\setminus\\{i\\}}\|\theta_{j}^{*}-\theta_{i}^{*}\|\sqrt{t},$
$\displaystyle\leq\sum_{j\in
C_{k}\setminus\\{i\\}}\|\theta_{j}^{*}-\theta_{i}^{*}\|\sqrt{T},$

where the first inequality is given by the triangle inequality. The second
inequality holds because the sum over all clients
$\overline{V}_{t,i}=\sum_{i\in{C_{k}}}\mathbf{X}_{i}^{\top}\mathbf{X}_{i}$
necessarily includes $\mathbf{X}_{j}^{\top}\mathbf{X}_{j}$, hence
$\overline{V}_{t,i}\geq\mathbf{X}_{j}^{\top}\mathbf{X}_{j}$. Additionally,
$\mathbf{X}_{j}^{\top}\mathbf{X}_{j}$ is positive semi-definite so that
$\overline{V}_{t,i}^{-1}\leq(\mathbf{X}_{j}^{\top}\mathbf{X}_{j})^{-1}$. The
third inequality is given by the Rayleigh-Ritz Theorem. We have the last
inequality because we know that since $\|x_{t,i}\|\leq 1$,
$\lambda_{\max}(\mathbf{X}_{i}^{\top}\mathbf{X}_{i})\leq\tau_{i}\leq T$.

Theorem 1 shows that by setting $\upsilon_{c}\geq
F^{-1}(\frac{\delta}{N^{2}},df,\psi^{c})$ and
$T_{0}=\min\\{\frac{64}{3\lambda_{c}}\log(\frac{2Td}{\delta}),\frac{16\psi^{d}\sigma^{2}}{\lambda_{c}\gamma^{2}}\\}$,
with probability $1-\delta$ we have $\hat{\mathcal{C}}=\mathcal{C}$.
Therefore, since $i,j$ belong to the same ground-truth cluster $C_{k}$, we
have by Assumption 1,
$\|\theta_{j}^{*}-\theta_{i}^{*}\|\leq\epsilon_{t}=\frac{1}{N\sqrt{t}}$. As a
result, we can further upper bound the heterogeneity term by

$\displaystyle\bigg{\|}\sum_{j\in{C}_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})\bigg{\|}_{\overline{V}_{t,i}^{-1}}\leq\sum_{j\in{C}_{k}\setminus\\{i\\}}\frac{\sqrt{T}}{N\sqrt{T}}\leq
1.$

###### Lemma 16

We define the single step pseudo regret
$r_{t,i}=\langle\theta_{i}^{*},x_{t,i}^{*}-x_{t,i}\rangle$ where
$x_{t,i}^{*}=\operatorname*{arg\,max}_{x\in\mathcal{A}_{t,i}}{\langle
x,{\theta}_{t,i}^{*}\rangle}$. With probability $1-N\delta$, $r_{t,i}$ is
bounded by

$\displaystyle r_{t,i}$ $\displaystyle\leq
2\biggr{(}\sigma\sqrt{2\log\biggr{(}\frac{\det(\overline{V}_{t,i})^{1/2}\det(\lambda
I)^{-1/2}}{\delta}\biggr{)}}+\sqrt{\lambda}S+O(1)\biggr{)}\|x_{t,i}\|_{\overline{V}_{t,i}^{-1}}=O\biggr{(}\sigma\sqrt{d\log\frac{T}{\delta}}\biggr{)}\|x_{t,i}\|_{\overline{V}_{t,i}^{-1}}.$
(6)

Proof  Assume without loss of generality $\theta_{i}^{*}\in{C_{k}}$. Then,

$\displaystyle r_{t,i}$
$\displaystyle=\langle\theta_{i}^{*},x_{t,i}^{*}\rangle-\langle\theta_{i}^{*},x_{t,i}\rangle,$
$\displaystyle\leq\langle\tilde{\theta}_{t,i},x_{t,i}\rangle-\langle\theta_{i}^{*},x_{t,i}\rangle,$
$\displaystyle=\langle\tilde{\theta}_{t,i}-\theta_{i}^{*},x_{t,i}\rangle,$
$\displaystyle=\langle\tilde{\theta}_{t,i}-\hat{\theta}_{t,i},x_{t,i}\rangle+\langle\hat{\theta}_{t,i}-\theta_{i}^{*},x_{t,i}\rangle,$
$\displaystyle\leq\|\tilde{\theta}_{t,i}-\hat{\theta}_{t,i}\|_{\overline{V}_{t,i}}\|x_{t,i}\|_{\overline{V}_{t,i}^{-1}}+\|\hat{\theta}_{t,i}-\theta_{i}^{*}\|_{\overline{V}_{t,i}}\|x_{t,i}\|_{\overline{V}_{t,i}^{-1}},$
$\displaystyle\leq
2\biggr{(}\sigma\sqrt{2\log\biggr{(}\frac{\det(\overline{V}_{t,i})^{1/2}\det(\lambda
I)^{-1/2}}{\delta}\biggr{)}}+\sqrt{\lambda}S+\bigg{\|}\sum_{j\in
C_{k}\setminus\\{i\\}}\mathbf{X}_{j}^{\top}\mathbf{X}_{j}(\theta_{j}^{*}-\theta_{i}^{*})\bigg{\|}_{\overline{V}_{t,i}^{-1}}\biggr{)}\|x_{t,i}\|_{\overline{V}_{t,i}^{-1}}.$
(7)

The first inequality is because $\langle\tilde{\theta}_{t,i},x_{t,i}\rangle$
is optimistic. Applying Lemma 15 to upper bound the heterogeneity term gives

RHS of Eq.(7) $\displaystyle\leq
2\biggr{(}\sigma\sqrt{2\log\biggr{(}\frac{\det(\overline{V}_{t,i})^{1/2}\det(\lambda
I)^{-1/2}}{\delta}\biggr{)}}+\sqrt{\lambda}S+O(1)\biggr{)}\|x_{t,i}\|_{\overline{V}_{t,i}^{-1}},$
$\displaystyle=O\biggr{(}\sigma\sqrt{d\log\frac{T}{\delta}}\biggr{)}\|x_{t,i}\|_{\overline{V}_{t,i}^{-1}}.$

Now we are equipped to prove Theorem 3.

Proof  The cumulative regret of our system can be decomposed into three
components. The first component is the regret accumulated under our
exploration stage. During these timesteps we can trivially upper bound the
instantaneous regret by two. The second component considers the regret during
timesteps in which our estimated clusters are correct. The third component
considers the regret accumulated during the timesteps in which our estimated
clusters are incorrect, which we can also upper bound the instantaneous regret
by two, yielding

$R_{T}\leq\sum_{t=0}^{T_{0}}\sum_{i=1}^{N}2+\sum_{t=T_{0}+1}^{T}\sum_{k=1}^{\hat{M}}\sum_{i\in{\hat{C}_{k}}}r_{t,i}\cdot\mathds{1}\\{\hat{\mathcal{C}}=\mathcal{C}\\}+\sum_{t=T_{0}+1}^{T}\sum_{k=1}^{\hat{M}}\sum_{i\in{\hat{C}_{k}}}2\cdot\mathds{1}\\{\hat{\mathcal{C}}\neq\mathcal{C}\\}.$

Note that because our cluster estimation is non-parametric the number of
estimated clusters $\hat{M}$ is not a hyper-parameter to our clustering
algorithm.

According to Theorem 1, if we select $\upsilon^{c}\geq
F^{-1}(1-\frac{\delta}{N^{2}},df,\psi^{c})$ and
$T_{0}=\frac{16\psi^{d}\sigma^{2}}{\lambda_{c}\gamma^{2}}$, the probability
that $\hat{\mathcal{C}}=\mathcal{C}$ is $1-\delta$. Therefore, by setting
$\delta=\frac{1}{N^{2}T}$, the regret contributed by the rightmost term is of
the order $O(1)$. As a result, our high-probability regret bound is given by:

$R_{T}\leq\frac{32N\psi^{d}\sigma^{2}}{\lambda_{c}\gamma^{2}}+\sum_{t=T_{0}+1}^{T}\sum_{k=1}^{\hat{M}}\sum_{i\in{\hat{C}_{k}}}r_{t,i}\cdot\mathds{1}\\{\hat{\mathcal{C}}=\mathcal{C}\\}+O(1).$

In the subsequent steps, we will focus on the regret accumulated when
$\hat{\mathcal{C}}=\mathcal{C}$. This means we only need to examine the
instances when the estimated number of clusters and their compositions exactly
match the actual clusters. Consequently, in subsequent discussions $\hat{M}=M$
and $\hat{C}_{k}=C_{k}$ for all $k\in[M]$.

Now we prove Theorem 3 following the steps in the proof of Theorem 4 in Wang
et al. (2020). We consider the case where Eq.(6) holds because with the same
choice of $\delta=\frac{1}{N^{2}T}$, the expected instantaneous regret
resulting during timesteps when Eq.(6) does not hold is $O(1)$.

In our communication protocol, for each cluster $C_{k}$, there will be a
number of epochs separated by communication rounds. We denote $|C_{k}|$
denotes the number of clients in cluster $C_{k}$. If there are $P_{k}$ epochs
within cluster $C_{k}$, then $V_{P_{k}}$ will be the matrix with all samples
from $C_{k}$ included. Similarly we denote the last globally shared $V$ to the
clients in $C_{k}$ in epoch $p$ as $V_{p}$.

From Lemma 7, we have $\det(V_{0})=\lambda^{d}$.
$\det(V_{P,k})\leq\biggr{(}\frac{tr(V_{p})}{d}\biggr{)}^{d}\leq\left(\lambda+\frac{|C_{k}|\,T}{d}\right)^{d}$.
Therefore by the pigeonhole principle,

$\log\frac{\det(V_{p})}{\det(V_{0})}\leq
d\log\biggr{(}1+\frac{|C_{k}|\,T}{\lambda d}\biggr{)}.$

It follows that for all but $R:=d\log\big{(}1+\frac{|C_{k}|T}{\lambda
d}\big{)}$ epochs,

$1\leq\frac{\det(V_{j})}{\det(V_{j-1})}\leq 2.$ (8)

In these “good epochs” where Eq (8) is satisfied, we can follow Theorem 4 from
Wang et al. (2020) and treat all of the $|C_{k}|T$ observations from cluster
$k$ as observations from an imaginary single agent in a round-robin manner. We
similarly use $\tilde{V}_{t,i}=\lambda I+\sum_{\\{(p,q):(p<t)\lor(p=t\land
q<i)\\}}x_{p,q}x_{p,q}^{\top}$ to denote the $\overline{V}_{t,i}$ this agent
calculates before seeing $x_{t,i}$. If $x_{t,i}$ is in a good epoch, then:

$1\leq\frac{\det(\tilde{V}_{t,i})}{\det(\overline{V}_{t,i})}\leq\frac{\det(V_{j})}{\det(V_{j-1})}\leq
2.$

We similarly denote $\mathcal{B}_{p,k}$ as the set of $(t,i)$ pairs that
belong to epoch $p$ and $P_{good,k}$ as the set of good epochs in cluster $k$.
In that event, we can use the regret bound for a single agent which gives

$\displaystyle R_{good}$
$\displaystyle=\sum_{t=T_{0}+1}^{T}\sum_{k=1}^{M}\sum_{i\in{C_{k}}}r_{t,i},$
$\displaystyle\leq\sum_{k=1}^{M}\sqrt{|C_{k}|T\sum_{p\in
P_{good,k}}\sum_{(t,i)\in\mathcal{B}_{p,k}}r_{t,i}^{2}},$
$\displaystyle\leq\sum_{k=1}^{M}O\bigg{(}\sqrt{d|C_{k}|T\log(T/\delta)\sum_{p\in
P_{good,k}}\sum_{(t,i)\in\mathcal{B}_{p,k}}\min(\|x_{t,i}\|^{2}_{\tilde{V}_{t,i}^{-1}},1)}\bigg{)},$
$\displaystyle\leq\sum_{k=1}^{M}O\bigg{(}\sqrt{d|C_{k}|T\log(T/\delta)\sum_{p\in
P_{good,k}}\log\bigg{(}\frac{\det(V_{p})}{\det(V_{p-1})}\bigg{)}}\bigg{)},$
$\displaystyle\leq\sum_{k=1}^{M}O\bigg{(}\sqrt{d|C_{k}|T\log(T/\delta)\log\bigg{(}\frac{\det(V_{p})}{\det(V_{0})}\bigg{)}}\bigg{)},$
$\displaystyle\leq\sum_{k=1}^{M}O\bigg{(}d\sqrt{|C_{k}|\,T}\log(|C_{k}|\,T)\bigg{)}.$

Now we must analyze the regret caused by the bad epochs, of which there are
$R=O(d\log(|C_{k}|\,T))$ within each cluster $C_{k}\in\mathcal{C}$. This part
of the analysis differs from the proof in Theorem 4 of (Wang et al., 2020) due
to the fact that in our protocol, clusters that have requested collaboration
may have to wait in the queue until they are served in the event that multiple
clusters have requested collaboration at the same timestep.

Consider the regret for a particular cluster $C_{k}\in\mathcal{C}$ during this
bad epoch. Suppose that the bad epoch starts at time $t_{0}$ and lasts $n$
timesteps. We denote the time $t_{q}$ when the cluster $k$ is added to the
queue awaiting collaboration. We can decompose the regret of this cluster
during the bad epoch into two parts, corresponding to the timesteps before and
after $C_{k}$ has been added to the queue:

$\displaystyle REG_{bad}(k)$
$\displaystyle=\sum_{t=t_{0}}^{t_{q}-1}r_{t,i}+\sum_{t=t_{q}}^{n}r_{t,i}.$

Based on our algorithm design, we can see in line 13 of Algorithm 3 that a
cluster is only added to the queue when at least one client in that cluster
has exceeded its communication threshold $D_{k}$. Therefore we know that
before $t_{q}$, we can upper bound the regret of the cluster $k$ from $t_{0}$
to $t_{q}-1$ as:

$\displaystyle\sum_{t=t_{0}}^{t_{q}-1}r_{t,i}$ $\displaystyle\leq
O\biggr{(}\sqrt{d\log\frac{T}{\delta}}\biggr{)}\sum_{i\in{C_{k}}}\sum_{t=t_{0}}^{t_{q}-1}\|x_{t,i}\|_{\overline{V}_{t,i}^{-1}},$
$\displaystyle\leq
O\biggr{(}\sqrt{d\log\frac{T}{\delta}}\biggr{)}\sum_{i\in{C_{k}}}\sqrt{(t_{q}-1-t_{0})\log\frac{\det(V_{t_{q}-1,i})}{\det(V_{t_{q}-1,i}-\Delta
V_{t_{q}-1,i})}},$ $\displaystyle\leq
O\biggr{(}\sqrt{d\log\frac{T}{\delta}}\biggr{)}|C_{k}|\sqrt{D_{k}}.$

Once cluster $k$ is added to the queue at timestep $t_{q}$, it may have to
wait to be served by the central server based on how many clusters have
requested collaboration before it. Recall that our queue is a FIFO queue (line
19 in Algorithm 3), and we have $M$ total clusters. Therefore the maximum time
cluster $C_{k}$ could have to wait in the queue is $M$ timesteps. Each
timestep the cluster is waiting in the queue, a client in this cluster will
miss $|C_{k}|$ observations. For each of these missed observations, we can
upper bound the regret incurred by $2$, giving

$\displaystyle\sum_{t=t_{q}}^{n}r_{t,i}\leq 2(M+1)|C_{k}|^{2}.$

Combining our results, we have the following bound on the regret of cluster
$C_{k}$ during a bad epoch:

$\displaystyle REG_{bad}(k)$ $\displaystyle\leq
O\biggr{(}\sqrt{d\log\frac{T}{\delta}}\biggr{)}|C_{k}|\sqrt{D_{k}}+2(M+1)|C_{k}|^{2}.$

As we know we have at most $R=O(d\log(|C_{k}|\,T))$ bad epochs, we can further
bound it by

$\displaystyle REG_{bad}(k)$ $\displaystyle\leq
O\biggr{(}\sqrt{D_{k}}|C_{k}|d^{1.5}\log^{1.5}(|C_{k}|T)+2d|C_{k}|^{2}(M+1)\log(|C_{k}|\,T)\biggr{)}.$

with the choice of $D_{k}=\frac{T\log|C_{k}|T}{d|C_{k}|}$, our regret becomes:

$\displaystyle REG_{bad}(k)$ $\displaystyle\leq
O\biggr{(}d\sqrt{|C_{k}|T}\log^{2}(|C_{k}|T)+2d|C_{k}|^{2}M\log(|C_{k}|\,T)\biggr{)}.$

The summation over all $M$ clusters gives the regret for all clusters in all
of the bad epochs:

$\displaystyle REG_{bad}$
$\displaystyle\leq\sum_{k=1}^{M}O\biggr{(}d\sqrt{|C_{k}|T}\log^{2}(|C_{k}|T)+2d|C_{k}|^{2}M\log(|C_{k}|\,T)\biggr{)}.$

Combining the regret from the exploration phase, good epochs, and bad epochs
gives a final cumulative regret upper bound of:

$\displaystyle R_{T}\leq\frac{32N\psi^{d}\sigma^{2}}{\lambda_{c}\gamma^{2}}$
$\displaystyle+\sum_{k=1}^{M}O\bigg{(}d\sqrt{|C_{k}|\,T}\log(|C_{k}|\,T)\bigg{)},$
$\displaystyle+\sum_{k=1}^{M}O\biggr{(}d\sqrt{|C_{k}|T}\log^{2}(|C_{k}|T)+2d|C_{k}|^{2}M\log(|C_{k}|\,T)\biggr{)}+O(1).$

This can be further simplified with,

$\displaystyle R_{T}$ $\displaystyle\leq
O\biggr{(}\frac{N\psi^{d}\sigma^{2}}{\lambda_{c}\gamma^{2}}+\sum_{k=1}^{M}d\sqrt{|C_{k}|T}\log^{2}(|C_{k}|T)+2d|C_{k}|^{2}M\log(|C_{k}|\,T)\biggr{)}.$

###  D.1 Communication cost

The cumulative communication cost $C_{T}$ of our algorithm can be divided into
two parts. The first is the communication cost associated with the pure
exploration and cluster estimation phase. During the pure exploration phase,
no clients communicate with the central server, so that the communication cost
associated with that phase is trivially $0$. At the end of the exploration
phase, all $i\in[N]$ clients share with server their sufficient statistics
$V_{T_{0},i}$ and $b_{T_{0},i}$, each of which are $d\times d$ and $d\times 1$
respectively. Therefore, the communication cost of the cluster estimation is
$C_{cluster\\_est}=N(d^{2}+d)=O(Nd^{2})$.

Next, we characterize the communication cost of the second phase, the
federated clustered bandit phase. In our communication protocol, for each
cluster $C_{k}$, there will be a number of epochs separated by communication
rounds. Denote the length of an epoch as $\alpha$, so that there can be at
most $\lceil\frac{T}{\alpha}\rceil$ epochs with length longer than $\alpha$.
For an epoch with less than $\alpha$ time steps, similarly, we denote the
first time step of this epoch as $t_{s}$ and the last as $t_{e}$, i.e.,
$t_{e}-t_{s}<\alpha$. Therefore,
$\log{\frac{\det(V_{t_{e}})}{\det(V_{t_{s}})}}>\frac{D_{k}}{\alpha}$.
Following the same argument as in the regret proof, the number of epochs with
less than $\alpha$ time steps is at most $\lceil\frac{R\alpha}{D_{k}}\rceil$.
Then
$C_{fed\\_cluster}(k)=|C_{k}|\cdot(\lceil\frac{T}{\alpha}\rceil+\lceil\frac{R\alpha}{D_{k}}\rceil)$,
because at the end of each epoch, the synchronization round incurs $2|C_{k}|$
communication cost. We minimize $C_{fed\\_cluster}(k)$ by choosing
$\alpha=\sqrt{\frac{D_{k}T}{R}}$, so that
$C_{fed\\_cluster}(k)=O(|C_{k}|\cdot\sqrt{\frac{TR}{D}})$. With our choice of
$D_{k}=\frac{T\log|C_{k}|T}{d|C_{k}|}$, we have

$\displaystyle C_{fed\\_cluster}(k)$
$\displaystyle=O(|C_{k}|\cdot\sqrt{\frac{TR}{\frac{T\log|C_{k}|T}{d|C_{k}|}}}),$
$\displaystyle=O(|C_{k}|\cdot d\sqrt{|C_{k}|}).$

Combining our communication cost from our two phases together gives:

$\displaystyle C_{T}$
$\displaystyle=O(Nd^{2})+\sum_{k=1}^{M}O(d^{3}|C_{k}|^{1.5}).$

##  Appendix E Additional Empirical Enhancement Evaluation

In this work, we demonstrate the effectiveness of our empirical enhancements
on two synthetic datasets. In Section 4.2, we analyzed the performance of both
HetoFedBandit and HetoFedBandit-E on a balanced synthetic dataset that was
generated following the procedure described in Section 4.2. In this section,
we evaluate our models on an imbalanced synthetic dataset to emphasize the
distinct contributions of our priority queue and data-dependent re-clustering
enhancements.

##### Dataset

In this imbalanced dataset, we deliberately vary the distribution of clients
and the sizes of clusters. We establish $N=50$ clients and $M=13$ ground-truth
clusters. Instead of randomly assigning clients to clusters like we did in
Section 4.2, we manually assigned 26 clients to cluster $C_{1}$, and the
remaining $24$ clients were assigned in pairs to the remaining $12$ cluster
centers. After being assigned to a cluster center, we follow the same
procedure from Section 4.2 to generate the client parameters within $\epsilon$
of the cluster centers. For the other environment settings, we used $d=25$,
$K=1000$, $\gamma=0.85$ and $T=2500$.

##### Models

In order to evaluate the contributions of each enhancement proposed in Section
3.4, we implemented two additional enhanced algorithms of HetoFedBandit. In
HetoFedBandit-PQ, we replace the server’s FIFO queue with a priority queue
that selects a cluster to collaborate with based on their determinant ratios.
HetoFedBandit-DR performs data-dependent clustering at each collaboration
round. HetoFedBandit-E, as described in Algorithm 5, is our fully enhanced
algorithm, where both a priority queue and data-dependent clustering are
employed.

##### Results

In Figure 4(a), we conducted an empirical evaluation of the individual
enhancements proposed in Section 3.4. A comparison between HetoFedBandit-DR
and HetoFedBandit demonstrates that the use of data-dependent clustering
significantly improved performance on our imbalanced synthetic dataset. By
employing a data-dependent clustering threshold, our algorithm facilitated
greater collaboration among clients with similar observation histories during
the early rounds. Although this enhancement incurred additional communication
cost, the cost remained sub-linear and comparable to that of DisLinUCB.

Comparing HetoFedBandit with HetoFedBandit-PQ, our observations suggest that
the utilization of a priority queue yielded modest improvements in cumulative
regret, particularly in the initial rounds when multiple clients
simultaneously requested collaboration, leading to queue congestion. In this
imbalanced environment, we observed significant delays for the larger cluster
$C_{1}$ when using a FIFO queue. The larger size of cluster $C_{1}$ resulted
in a higher value of the cluster determinant ratio, indicating its potential
for greater regret reduction in the federated learning system. However, due to
the FIFO queue, several smaller clusters that that benefited less from
collaboration were served ahead of $C_{1}$. Nevertheless, as the algorithm
progressed, the frequency of communication among clients decreased, resulting
in reduced queue congestion. As a result, HetoFedBandit and HetoFedBandit-PQ
exhibited similar performance in the later rounds.

(a) Accumulative Regret

(b) Communication Cost

Figure 4: Experimental Results on Imbalanced Synthetic Dataset

##  Appendix F Sensitivity Analysis

According to our regret analysis, the performance of HetoFedBandit depends on
three key environment parameters: the number of ground-truth clusters $M$, and
the number of clients $N$, and the cluster separation parameter $\gamma$. In
this experiment, we analyze their influence on HetoFedBandit and baselines by
varying these parameters while keeping the others fixed. The accumulated
regret under different settings are reported in Table 1. As suggested by our
theoretical analysis, a larger client to cluster ratio $\frac{N}{M}$ leads to
higher regret of both HetoFedBandit (HFB) and HetoFedBandit-E (HFB-E) as shown
in setting 1, 2 and 3, since observations are split into more clusters with
smaller size each. Lastly, as shown in settings 4 and 5, 6, decreasing the
environment separation introduces a higher regret of HetoFedBandit since a
longer exploration period is required to discern which clients are safe for
collaboration. Additionally, the decreased cluster separation in setting 5
leads to an increase in regret for HetoFedBandit-E, as well as DyClu due to
the increased likelihood of a clustering error when the clusters are closer
together.

Table 1: Comparison of accumulated regret under different environment settings. |  $N$ |  $M$ |  $\gamma$ |  $T$ |  NIndep-LinUCB |  DisLinUCB |  FCLUB_DC |  DyClu |  HFB |  HFB-E
---|---|---|---|---|---|---|---|---|---|---
1 |  30 |  1 |  0.85 |  3000 |  772.03 |  59.20 |  648.22 |  48.77 |  576.31 |  173.89
2 |  30 |  4 |  0.85 |  3000 |  784.80 |  23776.10 |  784.01 |  227.18 |  669.17 |  443.89
3 |  30 |  30 |  0.85 |  3000 |  781.35 |  25124.46 |  791.19 |  776.86 |  883.51 |  822.24
4 |  30 |  4 |  0.65 |  3000 |  777.73 |  20129.05 |  788.12 |  231.57 |  699.89 |  461.54
5 |  30 |  4 |  0.05 |  3000 |  787.79 |  23823.61 |  771.04 |  269.45 |  916.73 |  582.21

## References

  * Abbasi-Yadkori et al. (2011) Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In _Advances in Neural Information Processing Systems_ , pages 2312–2320, 2011.
  * Auer et al. (1995) P. Auer, N. Cesa-Bianchi, Y. Freund, and R.E. Schapire.  Gambling in a rigged casino: The adversarial multi-armed bandit problem.  In _Proceedings of IEEE 36th Annual Foundations of Computer Science_ , pages 322–331, 1995.  doi: 10.1109/SFCS.1995.492488.
  * Auer et al. (2002) Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2-3):235–256, 2002.
  * Besson and Kaufmann (2018) Lilian Besson and Emilie Kaufmann.  What doubling tricks can and can’t do for multi-armed bandits, 2018.
  * Bonawitz et al. (2019) Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečnỳ, Stefano Mazzocchi, Brendan McMahan, et al.  Towards federated learning at scale: System design.  _Proceedings of machine learning and systems_ , 1:374–388, 2019.
  * Buccapatnam et al. (2013) Swapna Buccapatnam, Atilla Eryilmaz, and Ness B Shroff.  Multi-armed bandits in the presence of side observations in social networks.  In _52nd IEEE Conference on Decision and Control_ , pages 7309–7314. IEEE, 2013.
  * Cantador et al. (2011) Iván Cantador, Peter Brusilovsky, and Tsvi Kuflik.  2nd workshop on information heterogeneity and fusion in recommender systems (hetrec 2011).  In _Proceedings of the 5th ACM conference on Recommender systems_ , RecSys 2011, New York, NY, USA, 2011. ACM.
  * Cantrell et al. (1991) R Stephen Cantrell, Peter M Burrows, and Quang H Vuong.  Interpretation and use of generalized chow tests.  _International Economic Review_ , pages 725–741, 1991.
  * Caron et al. (2012) Stéphane Caron, Branislav Kveton, Marc Lelarge, and Smriti Bhagat.  Leveraging side observations in stochastic bandits.  _CoRR_ , abs/1210.4839, 2012.  URL http://arxiv.org/abs/1210.4839.
  * Cesa-Bianchi et al. (2013) Nicolo Cesa-Bianchi, Claudio Gentile, and Giovanni Zappella.  A gang of bandits.  In _Advances in Neural Information Processing Systems_ , pages 737–745, 2013.
  * Chapelle and Li (2011) Olivier Chapelle and Lihong Li.  An empirical evaluation of thompson sampling.  _Advances in neural information processing systems_ , 24, 2011.
  * Chow (1960) Gregory C Chow.  Tests of equality between sets of coefficients in two linear regressions.  _Econometrica: Journal of the Econometric Society_ , pages 591–605, 1960.
  * Dubey and Pentland (2020a) Abhimanyu Dubey and Alex ` Sandy'Pentland.  Differentially-private federated linear bandits.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 6003–6014. Curran Associates, Inc., 2020a.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/4311359ed4969e8401880e3c1836fbe1-Paper.pdf.
  * Dubey and Pentland (2020b) Abhimanyu Dubey and AlexSandy’ Pentland.  Differentially-private federated linear bandits.  _Advances in Neural Information Processing Systems_ , 33:6003–6014, 2020b.
  * Durand et al. (2018) Audrey Durand, Charis Achilleos, Demetris Iacovides, Katerina Strati, Georgios D Mitsis, and Joelle Pineau.  Contextual bandits for adapting treatment in a mouse model of de novo carcinogenesis.  In _Machine learning for healthcare conference_ , pages 67–82. PMLR, 2018.
  * Foley et al. (2022) Patrick Foley, Micah J Sheller, Brandon Edwards, Sarthak Pati, Walter Riviera, Mansi Sharma, Prakash Narayana Moorthy, Shi-han Wang, Jason Martin, Parsa Mirhaji, Prashant Shah, and Spyridon Bakas.  Openfl: the open federated learning library.  _Physics in Medicine & Biology_, 2022.  doi: 10.1088/1361-6560/ac97d9.  URL http://iopscience.iop.org/article/10.1088/1361-6560/ac97d9.
  * Gentile et al. (2014) Claudio Gentile, Shuai Li, and Giovanni Zappella.  Online clustering of bandits.  In _International Conference on Machine Learning_ , pages 757–765, 2014.
  * Gentile et al. (2017) Claudio Gentile, Shuai Li, Purushottam Kar, Alexandros Karatzoglou, Giovanni Zappella, and Evans Etrue.  On context-dependent clustering of bandits.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 1253–1262. JMLR. org, 2017.
  * He et al. (2020) Chaoyang He, Songze Li, Jinhyun So, Mi Zhang, Hongyi Wang, Xiaoyang Wang, Praneeth Vepakomma, Abhishek Singh, Hang Qiu, Li Shen, Peilin Zhao, Yan Kang, Yang Liu, Ramesh Raskar, Qiang Yang, Murali Annavaram, and Salman Avestimehr.  Fedml: A research library and benchmark for federated machine learning.  _Advances in Neural Information Processing Systems, Best Paper Award at Federate Learning Workshop_ , 2020.
  * He et al. (2022) Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu.  A simple and provably efficient algorithm for asynchronous federated contextual linear bandits.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=Fx7oXUVEPW.
  * Hong et al. (2021) Joey Hong, Branislav Kveton, Manzil Zaheer, and Mohammad Ghavamzadeh.  Hierarchical bayesian bandits.  _CoRR_ , abs/2111.06929, 2021.  URL https://arxiv.org/abs/2111.06929.
  * Hossain et al. (2021) Safwan Hossain, Evi Micha, and Nisarg Shah.  Fair algorithms for multi-agent multi-armed bandits.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=AlD5WD2ANIQ.
  * Huang et al. (2021) Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen.  Federated linear contextual bandits, 2021.  URL https://arxiv.org/abs/2110.14177.
  * Kairouz et al. (2021) 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 Trends® in Machine Learning_ , 14(1–2):1–210, 2021.
  * Korda et al. (2016) Nathan Korda, Balazs Szorenyi, and Shuai Li.  Distributed clustering of linear bandits in peer to peer networks.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pages 1301–1309, New York, New York, USA, 20–22 Jun 2016. PMLR.  URL https://proceedings.mlr.press/v48/korda16.html.
  * Li and Wang (2022) Chuanhao Li and Hongning Wang.  Asynchronous upper confidence bound algorithms for federated linear bandits.  In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , volume 151 of _Proceedings of Machine Learning Research_ , pages 6529–6553. PMLR, 28–30 Mar 2022.  URL https://proceedings.mlr.press/v151/li22e.html.
  * Li et al. (2021) Chuanhao Li, Qingyun Wu, and Hongning Wang.  Unifying clustered and non-stationary bandits.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1063–1071. PMLR, 2021.
  * Li et al. (2010a) Lihong Li, Wei Chu, John Langford, and Robert E. Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th International Conference on World Wide Web_ , WWW ’10, page 661–670, New York, NY, USA, 2010a. Association for Computing Machinery.  ISBN 9781605587998.  doi: 10.1145/1772690.1772758.  URL https://doi.org/10.1145/1772690.1772758.
  * Li et al. (2016) Shuai Li, Alexandros Karatzoglou, and Claudio Gentile.  Collaborative filtering bandits.  In _Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval_ , pages 539–548. ACM, 2016.
  * Li et al. (2019) Shuai Li, Wei Chen, and Kwong-Sak Leung.  Improved algorithm on online clustering of bandits.  _arXiv preprint arXiv:1902.09162_ , 2019.
  * Li et al. (2010b) Wei Li, Xuerui Wang, Ruofei Zhang, Ying Cui, Jianchang Mao, and Rong Jin.  Exploitation and exploration in a performance based contextual advertising system.  In _Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 27–36, 2010b.
  * Liu et al. (2022) Xutong Liu, Haoru Zhao, Tong Yu, Shuai Li, and John C. S. Lui.  Federated online clustering of bandits, 2022.  URL https://arxiv.org/abs/2208.14865.
  * Mahadik et al. (2020) Kanak Mahadik, Qingyun Wu, Shuai Li, and Amit Sabne.  Fast distributed bandits for online recommendation systems.  In _Proceedings of the 34th ACM international conference on supercomputing_ , pages 1–13, 2020.
  * Mannor and Shamir (2011) Shie Mannor and Ohad Shamir.  From bandits to experts: On the value of side-observations.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 24. Curran Associates, Inc., 2011.  URL https://proceedings.neurips.cc/paper_files/paper/2011/file/e1e32e235eee1f970470a3a6658dfdd5-Paper.pdf.
  * McMahan et al. (2016) H. Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas.  Federated learning of deep networks using model averaging.  _CoRR_ , abs/1602.05629, 2016.  URL http://arxiv.org/abs/1602.05629.
  * Shi and Shen (2021) Chengshuai Shi and Cong Shen.  Federated multi-armed bandits.  _CoRR_ , abs/2101.12204, 2021.  URL https://arxiv.org/abs/2101.12204.
  * Wang et al. (2020) Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang.  Distributed bandit learning: Near-optimal regret with efficient communication.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net, 2020.  URL https://openreview.net/forum?id=SJxZnR4YvB.
  * Wu et al. (2016) Qingyun Wu, Huazheng Wang, Quanquan Gu, and Hongning Wang.  Contextual bandits in a collaborative environment.  In _Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval_ , pages 529–538. ACM, 2016.