Exploiting Heterogeneity in Robust Federated Best-Arm Identification

Federated Learning (FL) has recently emerged as a popular framework for training statistical models using diverse data available at multiple clients (mobile phones, smart devices, health organizations, etc.) [1, 2, 3, 4, 5]. Two key challenges intrinsic to FL include statistical heterogeneity that arises due to differences in the data sets of the clients, and stringent communication constraints imposed by bandwidth considerations. Several recent works [6, 7, 8, 9, 10, 11] have reported that under statistical heterogeneity, FL algorithms that perform local computations to save communication can exhibit poor performance. Notably, these observations concern the task of supervised learning, which has almost exclusively been the focus of FL thus far.

In a departure from the standard supervised learning setting, the authors in [12] recently showed that for the problem of federated clustering, one can in fact benefit from a notion of heterogeneity defined suitably for their setting. This is a rare finding that naturally begs the following question.

Are there other classes of cooperative learning problems where, unlike federated supervised learning, local computations and specific notions of heterogeneity can provably help?

In this paper, we answer the above question in the affirmative by introducing and studying a federated variant of the best-arm identification problem [13, 14, 15, 16, 17, 18, 19] in stochastic multi-armed bandits. In our model, a set of arms is partitioned into disjoint arm-sets and each arm-set is associated with a unique client. Specifically, each client can only sample arms from its respective arm-set. This modeling assumption is consistent with the standard FL setting where each client typically has access to only a portion of a large data set; we will provide further motivation for our model shortly. The task for the clients is to coordinate via a central server and identify the best arm with high probability, i.e., with a given fixed confidence.¹¹1We will provide a precise problem formulation in Sec. 2 where we explain what is meant by a “best arm”. To achieve this task, communication is clearly necessary since each client can only acquire information about its own arm-set in isolation. Our formulation naturally captures statistical heterogeneity: other than the requirement of sharing the same support, we allow distributions of arms across arm-sets to be arbitrarily different. In what follows, we briefly describe a couple of motivating applications.

Applications in Robotics and Sensor Networks: Our work is practically motivated by the diverse engineering applications (e.g., distributed sensing, estimation, localization, target-tracking, etc.) of cooperative learning [20, 21, 22, 23, 24]. For instance, consider a team of robots deployed over a large environment and tasked with detecting a chemical leakage based on readings from sensors spread out over the environment. Since it may be infeasible for a single robot to explore the entire environment, each robot is instead assigned the task of exploring a sub-region. The robots explore their respective sub-regions and coordinate via a central controller. We can abstract this application into our model by mapping robots to clients, controller to server, sensors to arms, and sub-regions to arm-sets. Based on this abstraction, detecting the sensor with the highest readings directly translates into the problem of identifying the best arm.

Applications in Recommendation Systems: As another concrete application, consider a web-recommendation system for restaurants in a city. People in the city upload ratings of restaurants to this system based on their personal experiences. Based on these ratings, the system constantly updates its scores, and provides recommendations regarding the best restaurant(s) in the city. To capture this scenario via our model, one can interpret people as clients, the web-recommendation system as the server, and restaurants as arms. Since it is somewhat unreasonable to expect that a person visits every restaurant in the city, the rationale behind a client sampling only a subset of the arms makes sense in this context as well.

We have thus justified the reason for considering heterogeneous action spaces (arm-sets) for the clients. In contrast, as we discuss in Section 1.2, prior related works make the arguably unrealistic assumption of a common action space for all clients, i.e., it is assumed that each client can sample every arm. As far as we are aware, this is the first work to study a federated/distributed variant of the heterogeneous multi-armed bandit (MAB) best-arm identification problem. The core question posed by this problem is the following: Although a client can sample only a subset of the arms itself, how can it still learn the best arm via collaboration?

In this context, we will focus on two important themes relevant to each of the applications we described above: communication-efficiency and robustness. To be more precise, we are interested in designing best-arm identification algorithms that (i) minimize communication between the clients and the server, and (ii) are robust to the presence of clients that act adversarially. Minimizing communication is motivated by low-bandwidth considerations in the context of sensor networks, and privacy concerns in the context of recommendation systems. Moreover, for the latter application, we would ideally like to avoid scenarios where a few deliberately biased reviews culminate in a bad recommendation. The need for robustness has a similar rationale in distributed robotics and sensor networks. Having motivated the setup, we now describe our main contributions.

Our model is comprised of a set of arms $\mathcal{A}$, a set of clients $\mathcal{C}$, and a central server. The set $\mathcal{A}$ is partitioned into $N$ disjoint arm-sets, one corresponding to each client. In particular, client $i\in\mathcal{C}$ can only sample arms from the $i$-th arm set, denoted by $\mathcal{A}_{i}=\{{a^{(i)}_{1}},{a^{(i)}_{2}},\ldots,{a^{(i)}_{|\mathcal{A}_{i}|}}\}$. Throughout, we will make the mild assumption that each arm-set contains at least two arms, i.e., $|\mathcal{A}_{i}|\geq 2,\forall i\in[N]$. We associate a notion of time with our model: in each unit of time, a client can only sample one arm. Each time client $i$ samples an arm $\ell\in\mathcal{A}_{i}$, it observes a random reward $X_{\ell}$ drawn independently of the past (actions and observations of all clients) from a distribution $D_{\ell}$ (unknown to client $i$) associated with arm $\ell$. We will use $\hat{r}_{i,\ell}(t)$ to denote the average of the first $t$ independent samples $X_{i,\ell}(s),s\in[t]$ of the reward of an arm $\ell\in\mathcal{A}_{i}$ as observed by client $i$, i.e., $\hat{r}_{i,\ell}(t)=(\sum_{s=1}^{t}X_{i,\ell}(s))/t$.

As is quite standard [13, 14, 16, 17, 18, 15, 19], we assume that all rewards are in $[0,1]$. For each arm $\ell\in\mathcal{A}$, let $r_{\ell}$ denote the expected reward of arm $\ell$, i.e., $r_{\ell}=\mathbb{E}[X_{\ell}]$. We will use $\Delta_{\ell j}\triangleq r_{\ell}-r_{j}$ to represent the difference between the mean rewards of any two arms $\ell,j\in\mathcal{A}$. An arm with the highest expected reward in $\mathcal{A}_{i}$ (resp., in $\mathcal{A}$) will be called a locally best arm in arm-set $i$ (resp., a globally best arm in $\mathcal{A}$), and be denoted by $a^{*}_{i}$ (resp., by $a^{*}$). For simplicity of exposition, let the arms in each arm-set $\mathcal{A}_{i}$ be ordered such that $r_{a^{(i)}_{1}}>r_{a^{(i)}_{2}}>\cdots>r_{{a^{(i)}_{|\mathcal{A}_{i}|}}}$; thus, $a^{*}_{i}=a^{(i)}_{1}$. Without loss of generality, we assume that arm $1$ is the unique globally best arm, and that it belongs to arm-set $\mathcal{A}_{1}$, i.e., $a^{*}=a^{(1)}_{1}=1$. We can now concretely state the problem of interest.

In words, given a fixed confidence level $\delta$ as input, our goal is to design an algorithm that enables the clients and the server to identify the globally best arm with probability at least $1-\delta$. Following [14], we will call such an algorithm $(0,\delta)$-PAC. Since each client $i\in\mathcal{C}$ is only partially informative (i.e., can only sample arms from its local arm-set $\mathcal{A}_{i}$), it will not be able to identify $a^{*}$ on its own, in general. Thus, any algorithm that solves Problem 1 will necessarily require communication between the clients and the server. Given that the communication-bottleneck is a major concern in FL, our focus will be to design communication-efficient best-arm identification algorithms. Later, in Section 5, we will consider a robust version of Problem 1 where the goal will be to identify the globally best arm despite the presence of adversarial clients that can act arbitrarily. We now draw some interesting parallels between the above formulation and the familiar federated optimization setup that is used to model and study supervised learning problems.

Comparison with the standard FL setting: The canonical FL setting involves solving the following optimization problem via periodic communication between the clients and the server [1, 2, 3, 4]:

Here, $f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is the local loss function of client $i$, and $f(x)$ is the global objective function. Let $x^{*}_{i}=\operatorname*{\arg\!\min}_{x\in\mathbb{R}^{d}}f_{i}(x)$, and $x^{*}=\operatorname*{\arg\!\min}_{x\in\mathbb{R}^{d}}f(x)$. Under statistical heterogeneity, $P_{i}\neq P_{j}$ in general for distinct clients $i$ and $j$, and hence, $f_{i}(x)$ and $f_{j}(x)$ may have different minima. A typical FL algorithm that solves for $x^{*}$ operates in rounds. Between two successive communication rounds, each client performs local training on its own data using stochastic gradient descent (SGD) or a variant thereof. As a consequence of such local training, popular FL algorithms such as FedAvg [2] and FedProx [77] exhibit a “client-drift phenomenon”: the iterates of each client $i$ drift-off towards the minimizer $x^{*}_{i}$ of its own local loss function $f_{i}(x)$ [6, 7, 8, 9, 10, 11]. Under statistical heterogeneity, there is no apparent relationship between $x^{*}_{i}$ and $x^{*}$, and these points may potentially be far-off from each other. Thus, client-drift can cause FedAvg and FedProx to exhibit poor convergence.²²2By poor convergence, we mean that these algorithms either converge slowly to the true global minimum, or converge to an incorrect point (potentially fast). See [8], [9], and [80] for a detailed discussion on this topic. More recent algorithms such as SCAFFOLD [11] and FedLin [80] try to mitigate the client-drift phenomenon by employing techniques such as variance-reduction and gradient-tracking. However, even these more refined algorithms are unable to demonstrate any quantifiable benefits of performing multiple local steps under arbitrary statistical heterogeneity.³³3Indeed, in [80], the authors show that there exist simple instances involving two clients with quadratic loss functions, for which, performing multiple local steps yields no improvement in the convergence rate even when gradient-tracking is employed.

Coming back to the MAB problem, $a^{*}_{i}$ can be thought of as the direct analogue of $x^{*}_{i}$ in the standard FL setting. We make two key observations.

• •

  Observation 1: Unlike the standard FL setting, there is an immediate relationship between the global optimum, namely the globally best arm $a^{*}$, and the locally best arms $\{a^{*}_{i}\}_{i\in\mathcal{C}}$: the globally best arm is the arm with the highest expected reward among the locally best arms.

• •

  Observation 2: Suppose distributions $D_{\ell_{1}}$ and $D_{\ell_{2}}$ corresponding to arms $\ell_{1}\in\mathcal{A}_{i}$ and $\ell_{2}\in\mathcal{A}_{j}$ are “very different” (in an appropriate sense). Intuition dictates that this should make the task of identifying the arm with the higher mean easier, i.e., statistical heterogeneity among distributions of arms corresponding to different clients should facilitate best-arm identification.

The first observation, although simple and rather obvious, has the following important implication. Suppose each client $i$ does pure exploration locally to identify the best arm $a^{*}_{i}$ in its arm-set $\mathcal{A}_{i}$. Clearly, such local computations contribute towards the overall task of identifying the globally best arm (as they help eliminate sub-optimal arms), regardless of the level of heterogeneity in the distributions of arms across arm-sets. Thus, we immediately note a major distinction between the standard federated supervised learning setting and the federated best-arm identification problem: for the former, local steps can potentially hurt under statistical heterogeneity; for the latter, we can exploit problem structure to design local computations that always contribute towards the global task. In fact, aligning with the second observation, we will show later in Section 4 that statistical heterogeneity of arm distributions across clients can assist in minimizing communication. Building on the insights from this section, we now proceed to develop a federated best-arm identification algorithm that solves Problem 1.

In this section, we develop an algorithm for solving Problem 1. Since minimizing communication is one of our primary concerns, let us start by asking what a client can achieve on its own without interacting with the server. To this end, consider the following example to help build intuition.

Example: Suppose there are just 2 clients with associated arm-sets $\mathcal{A}_{1}=\{1,2\}$ and $\mathcal{A}_{2}=\{3,4\}$. The mean rewards are $r_{1}=0.9,r_{2}=0.3,r_{3}=0.8$, and $r_{4}=0.7$. From classical MAB theory, we know that to identify the best arm among two arms with gap in mean rewards $\Delta$, each of the arms needs to be sampled $O(1/\Delta^{2})$ times. Thus, after sampling each of the arms in $\mathcal{A}_{1}$ for $O(1/\Delta^{2}_{12})$ number of times (resp., arms in $\mathcal{A}_{2}$ for $O(1/\Delta^{2}_{34})$ times), client 1 (resp., client 2) will be able to identify arm 1 (resp., arm 3) as the locally best-arm in $\mathcal{A}_{1}$ (resp., $\mathcal{A}_{2}$) with high probability. However, at this stage, arm 1 will likely have been sampled much fewer times than arm 3 (since $1/\Delta^{2}_{12}\approx 3$, and $1/\Delta^{2}_{34}=100$), and hence, client 1’s estimate of arm 1’s true mean will be much coarser than client 2’s estimate of arm 3’s true mean. The main message here is that simply identifying locally best arms from each arm-set and then naively comparing between them may result in rejection of the globally best-arm. Thus, we need a more informed strategy that accounts for imbalances in sampling across arm-sets. With this in mind, we develop Fed-SEL.

Description of Fed-SEL: Our proposed algorithm Fed-SEL, outlined in Algo. 2, and depicted in Fig. 1, involves two distinct phases. In Phase I, each client $i\in\mathcal{C}$ runs a local successive elimination sub-routine (Algo. 1) in parallel on its arm-set $\mathcal{A}_{i}$ to identify the locally best arm $a^{*}_{i}$ in $\mathcal{A}_{i}$. Note that this requires no communication. Phase II then involves periodic encoded communication between the clients and the server to identify the best arm among the locally best arms. We assume that each client $i$ knows the parameters $|\mathcal{C}|,|\mathcal{A}_{i}|$, and $\delta$, and that the server knows $|\mathcal{C}|,\{|\mathcal{A}_{i}|\}_{i\in\mathcal{C}}$, and $\delta$. Additionally, we assume that the communication period $H$ is known to both the clients and the server. We now describe each of the main components of Fed-SEL in detail.

Phase I: Algo. 1 is based on the successive elimination technique [14], and proceeds in epochs. In each epoch $t$, client $i$ maintains a set of active arms $\mathcal{S}_{i}(t)\subseteq\mathcal{A}_{i}$. Each active arm $\ell\in\mathcal{S}_{i}(t)$ is sampled once, and its empirical mean $\hat{r}_{i,\ell}(t)$ is then updated. For the next epoch, an arm is retained in the active set if and only if its empirical mean is not much lower than the empirical mean of the arm with the highest empirical mean in epoch $t$; see line 5 of Algo. 1. This process continues till only one arm is left, at which point Algo. 1 terminates at client $i$ and outputs the last arm $a_{i}$. Let $\bar{t}_{i}$ represent the final epoch count when Algo. 1 terminates at client $i$. It is easy to then see that arm $a_{i}$, the output of Algo. 1 (if it terminates) at client $i$, is sampled $\bar{t}_{i}$ times at the end of Phase I. The quantities $\{\alpha_{i}(t),\beta_{i}(t)\}$ associated with arm-set $\mathcal{A}_{i}$ are given by line 1 of Algo. 1. Here, $c$ is a flexible parameter we introduce to control the accuracy of client $i$’s estimate $\hat{r}_{i,a_{i}}(\bar{t}_{i})$.

Phase II: The goal of Phase II is to identify the best arm from the set $\{a_{i}\}_{i\in\mathcal{C}}$. Comparing arms across clients entails communication via the server. Since such communication is costly, we consider periodic exchanges between the clients and the server as in standard FL algorithms. To further reduce communication, such exchanges are encoded using a novel adaptive encoding strategy that we will explain shortly. Specifically, Phase II operates in rounds, where in each round $k\in\{0,1,\ldots\}$, the server maintains a set of active clients $\bar{\Psi}(k)$: a client $i$ is deemed active if and only if arm $a_{i}$ is still under contention for being the globally best arm. To decide upon the latter, the server aggregates the encoded information received from clients to compute the threshold $\tilde{r}^{(L)}_{\max}(k)$ (lines 3 and 4 of Algo. 2). Computing this threshold requires some care to account for (i) imbalances in sampling across arm-sets, and (ii) errors introduced due to encoding (quantization). Having computed $\tilde{r}^{(L)}_{\max}(k)$, the server executes line 5 of Algo. 2 to eliminate sub-optimal arms from the set $\{a_{i}\}_{i\in\bar{\Psi}(k)}$. It then updates the active client set and broadcasts $\tilde{r}^{(L)}_{\max}(k)$ if $|\bar{\Psi}(k+1)|>1$.

Only the arms that remain in $\{a_{i}\}_{i\in\bar{\Psi}(k+1)}$ require further sampling by the corresponding clients. Each client $i\in\bar{\Psi}(k)$ uses the threshold $\tilde{r}^{(L)}_{\max}(k)$ to determine whether it should sample $a_{i}$ any further (i.e., it checks whether to remain active or not). If the conditions in line 7 of Algo. 2 pass, then client $i$ samples arm $a_{i}$ $H$ times, and transmits an encoded version $\sigma_{i}(k+1)$ of $\hat{r}_{i,a_{i}}(\bar{t}_{i}+(k+1)H)$ to the server. Here, $H$ is the communication period; if $H=1$, then the active clients interact with the server at each time-step in Phase II. Since we aim to reduce the number of communication rounds, we instead let each client perform multiple local sampling steps before communicating with the server, i.e., $H>1$ for our setting.⁴⁴4The local sampling steps in line 7 of Fed-SEL can be viewed as the analog of performing multiple local gradient-descent steps in standard federated optimization algorithms. Phase II lasts till the active client set reduces to a singleton, at which point the locally best arm corresponding to the last active client is deemed to be the globally best arm by the server. We now describe our encoding-decoding strategy.

Adaptive Encoding Strategy: At the end of round $k-1$, each active client $i\in\bar{\Psi}(k)$ encodes $\hat{r}_{i,a_{i}}(\bar{t}_{i}+kH)$ using a quantizer with range $[0,1]$ and bit-precision level $B_{i}(k)$, where

Specifically, the interval $[0,1]$ is quantized into $2^{B_{i}(k)}$ bins, and each bin is assigned a unique binary symbol. Since all rewards belong to $[0,1]$, $\hat{r}_{i,a_{i}}(\bar{t}_{i}+kH)$ falls in one of the bins in $[0,1]$. Let $\sigma_{i}(k)$ be the binary representation of the index of this bin. Compactly, we use $\texttt{Enc}_{i,k}\left(\hat{r}_{i,a_{i}}(\bar{t}_{i}+kH)\right)=\sigma_{i}(k)$ to represent the above encoding operation at client $i$. The key idea we employ in our encoding technique described above is that of adaptive quantization: the bit precision level $B_{i}(k)$ is successively refined in each round based on the confidence interval $\alpha_{i}(\bar{t}_{i}+kH)$.

For correct decoding, we assume that the server is aware of the encoding strategies at the clients, and the parameters $|\mathcal{C}|,\{|\mathcal{A}_{i}|\}_{i\in\mathcal{C}}$, $H$, and $\delta$. Based on this information, and the fact that at the end of Phase I, each client $i$ transmits $\bar{t}_{i}$ to the server, note that the server can exactly compute $\alpha_{i}(\bar{t}_{i}+kH)$, and hence $B_{i}(k)$ for each $i\in\mathcal{C}$. Let $\tilde{r}_{i}(k)$ be the center of the bin associated with $\sigma_{i}(k)$. Then, we compactly represent the decoding operation at the server (corresponding to client $i$) as $\texttt{Dec}_{i,k}(\sigma_{i}(k))=\tilde{r}_{i}(k)$. Using $\tilde{r}_{i}(k)$ as a proxy for $\hat{r}_{i,a_{i}}(\bar{t}_{i}+kH)$, the server computes upper and lower estimates, namely $\tilde{r}^{(U)}_{i}(k)$ and $\tilde{r}^{(L)}_{i}(k)$, of the mean of arm $a_{i}$ in line 3 of Algo. 2.

This completes the description of Fed-SEL. A few remarks are now in order.

In this section, we will focus on the following question: Can we still hope to identify the best-arm when certain clients act adversarially? To formally answer this question, we will consider a Byzantine adversary model [81, 82] where adversarial clients have complete knowledge of the model, can collude among themselves, and act arbitrarily. Let us start by building some intuition. Suppose the client associated with the arm-set containing the globally best arm $a^{*}$ is adversarial. Since this is the only client that can sample $a^{*}$, there is not much hope of identifying the best arm in this case. This simple observation reveals the need for information-redundancy: we need multiple clients to sample each arm-set to account for adversarial behaviour. Accordingly, with each arm-set $\mathcal{A}_{j}$, we now associate a group of clients $\mathcal{C}_{j}$; thus, $\mathcal{C}=\cup_{j\in[N]}\mathcal{C}_{j}$.⁹⁹9From now on, we will use the index $j$ to refer to arm-sets and client-groups, and the index $i$ to refer to clients. We will denote the set of honest clients by $\mathcal{H}$, the set of adversarial clients by $\mathcal{J}$, and allow at most $f$ clients to be adversarial in each client-group, i.e., $|\mathcal{C}_{j}\cap\mathcal{J}|\leq f,\forall j\in\mathcal{[}N]$. We will also assume that the server knows $f$.

Simply restricting the number of adversaries in each client-group is not enough to identify the best arm; there are additional challenges that need to be dealt with. To see this, consider a scenario where an arm $\ell\in\mathcal{A}_{j}$ has not been adequately explored by an honest client $i\in\mathcal{C}_{j}$. Due to the stochastic nature of our model, client $i$, although honest, may have a poor estimate of arm $\ell^{\prime}s$ true mean reward at this stage. How can we distinguish this scenario from one where an adversarial client in $\mathcal{C}_{j}$ deliberately transmits a completely incorrect estimate of arm $\ell$? In this context, one natural idea is to enforce each honest client to start transmitting information only when it has sufficiently explored every arm in its arm-set. This further justifies the rationale behind having two separate phases in Fed-SEL. In what follows, we describe a robust variant of Fed-SEL.

Description of Robust Fed-SEL: To identify $a^{*}$ despite adversaries, we propose Robust Fed-SEL, and outline its main steps in Algorithm 3. Like the Fed-SEL algorithm, Robust Fed-SEL also involves two separate phases. During Phase I, in each client group $\mathcal{C}_{j},j\in[N]$, every honest client $i\in\mathcal{C}_{j}\cap\mathcal{H}$ independently runs Algo. 1 on $\mathcal{A}_{j}$, and then transmits $\{a_{i},\hat{r}_{i,a_{i}}(\bar{t}_{i}),\bar{t}_{i}\}$ to the server exactly as in Fed-SEL. The key operations performed by the server as follows.

1) Majority Voting to Identify Representative Arms: At the onset of Phase II, the server waits till it has heard from at least $(2f+1)$ clients of each client group before it starts acting. Next, for each arm-set $\mathcal{A}_{j}$, the server aims to compute a representative locally best arm $\bar{a}_{j}$. Note that adversarial clients in $\mathcal{C}_{j}$ may collude and decide to report an arm to the server that has true mean much lower than that of the locally best arm $a^{(j)}_{1}$ in $\mathcal{A}_{j}$. Nonetheless, we should expect every honest client $i\in\mathcal{C}_{j}$ to output $a_{i}=a^{(j)}_{1}$ with high probability. Thus, if honest clients are in majority in $\mathcal{C}_{j}$, a simple majority voting operation (denoted by Maj_Vot) at the server should suffice to reveal the best arm in $\mathcal{A}_{j}$ with high probability; this is precisely the rationale behind line 2. During the remainder of Phase II, for each client group $j\in[N]$, the server only uses the information of the subset $\bar{\mathcal{C}}_{j}\subset\mathcal{C}_{j}$ of clients who reported the representative arm $\bar{a}_{j}$.

2) Trimming to Compute Robust Arm-Statistics: Phase II involves periodic communication and evolves in rounds. In each round $k$, the server maintains a set $\bar{\Psi}(k)$ of active client-groups: group $j$ is deemed active if $\bar{a}_{j}$ is still under contention for being the globally best arm. To decide whether group $j$ should remain active, the server performs certain trimming operations that we next describe. Given a non-negative integer $e$, and a set $\{m_{i}\}_{i\in[K]}$ of $K$ scalars where $K\geq 2e+1$, let $\texttt{Trim}\left(\{m_{i}\}_{i\in[K]},e\right)$ denote the operation of removing the highest $e$ and lowest $e$ numbers from $\{m_{i}\}_{i\in[K]}$, and then returning any one of the remaining numbers. Based on this Trim operator, the server computes robust upper and lower estimates, namely $\bar{r}^{(U)}_{j}(k)$ and $\bar{r}^{(L)}_{j}(k)$, of the mean of the representative arm $\bar{a}_{j},\forall j\in\bar{\Psi}(k)$; see line 6.¹⁰¹⁰10The trimming parameter $f_{j}$ is set based on the observation that clients in $\mathcal{C}^{\prime}_{j}$ who report an arm other than $\bar{a}_{j}$ are adversarial with high probability. Using these robust estimates, the server subsequently updates the set of active client-groups by executing lines 7-8.

If group $j$ remains active, then the server needs more refined arm estimates of arm $\bar{a}_{j}$ from $\bar{\mathcal{C}}_{j}$. Accordingly, the server sends out a binary $N\times 1$ vector $\mathbf{d}_{k}$ that encodes the active client-groups: $\mathbf{d}_{k}(j)=1$ if and only if $j\in\bar{\Psi}(k+1)$. Upon receiving $\mathbf{d}_{k}$, each honest client $i$ in $\bar{\mathcal{C}}_{j}$ checks if $\mathbf{d}_{k}(j)=1$. If so, it samples arm $a_{i}=\bar{a}_{j}$ $H$ times, encodes $\hat{r}_{i,a_{i}}(\bar{t}_{i}+(k+1)H)$ as in Fed-SEL, and transmits the encoding $\sigma_{i}(k+1)$ to the server. If $\mathbf{d}_{k}$ is not received from the server, or if $\mathbf{d}_{k}(j)=0$, client $i$ does nothing further. This completes the description of Robust Fed-SEL.

Comments on Algorithm 3: Before providing formal guarantees for Robust Fed-SEL, a few comments are in order. First, note that unlike Fed-SEL where the server transmitted a threshold to enable the clients to figure out whether they are active or not, the server instead transmits a $N\times 1$ vector $\mathbf{d}_{k}$ in Robust Fed-SEL. The reason for this is as follows. Even if $\bar{r}^{(L)}_{\max}(k)\geq\bar{r}^{(U)}_{j}(k)$ for some client-group $j$, it may very well be that $\bar{r}^{(L)}_{\max}(k)<\tilde{r}^{(U)}_{i}(k)$ for some $i\in\bar{\mathcal{C}}_{j}\cap\mathcal{H}.$ Thus, even if the server is able to eliminate client group $j$ on its end, simply broadcasting the threshold $\bar{r}^{(L)}_{\max}(k)$ may not be enough for every client in $\bar{\mathcal{C}}_{j}\cap\mathcal{H}$ to realize that it no longer needs to sample arm $\bar{a}_{j}$. Note that for line 10 of Robust Fed-SEL to make sense, we assume that every client is aware of the client-group to which it belongs.

During Phase II, for each group $j$, since the server only uses the information of clients in $\bar{\mathcal{C}}_{j}$ , we have not explicitly specified actions for honest clients in $\mathcal{C}_{j}\setminus\bar{\mathcal{C}}_{j}$ to avoid cluttering the exposition. A potential specification is as follows. Suppose the first time an honest client $i\in\mathcal{C}_{j}$ hears from the server, it is still in the process of completing Phase I. Since in this case client $i$ cannot belong to $\bar{\mathcal{C}}_{j}$, it deactivates and does nothing further. In all other cases, client $i\in\mathcal{C}_{j}$ acts exactly as specified in line 10 of Robust Fed-SEL.

The main result of this section is as follows.

Discussion: Under information-redundancy, i.e., under the condition that “enough” clients sample every arm in each arm-set ($|\mathcal{C}_{j}|\geq 3f+1,\forall j\in\mathcal{[}N]$), Theorem 2 shows that Robust Fed-SEL is an adversarially-robust $(0,\delta)$-PAC algorithm. Despite the flurry of research on tolerating adversaries in distributed optimization/supervised learning [26, 27, 28, 29, 30, 31, 32, 33, 34, 35], there is no analogous result (that we know of) in the context of MAB problems. Theorem 2 fills this gap. The sample- and communication-complexity bounds for Robust Fed-SEL are of the same order as that of Fed-SEL; hence, we do not explicitly state them here. For a discussion on this topic, see Appendix B where we provide the proof of Theorem 2.