Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds
Authors: Aritra Mitra
Arman Adibi
George J. Pappas
Hamed Hassani
Venue: NeurIPS 2022 Accept (2022)
Keywords: Collaborative Linear Bandits
Adversarial Attacks
Multi-Agent Systems
Robustness
Provably Correct Algorithms

Abstract:  We consider a linear stochastic bandit problem involving $M$ agents that can collaborate via a central server to minimize regret. A fraction $\alpha$ of these agents are adversarial and can act arbitrarily, leading to the following tension: while collaboration can potentially reduce regret, it can also disrupt the process of learning due to adversaries. In this work, we provide a fundamental understanding of this tension by designing new algorithms that balance the exploration-exploitation trade-off via carefully constructed robust confidence intervals. We also complement our algorithms with tight analyses. First, we develop a robust collaborative phased elimination algorithm that achieves $\tilde{O}\left(\alpha+ 1/\sqrt{M}\right) \sqrt{dT}$ regret for each good agent; here, $d$ is the model-dimension and $T$ is the horizon. For small $\alpha$, our result thus reveals a clear benefit of collaboration despite adversaries. Using an information-theoretic argument, we then prove a matching lower bound, thereby providing the first set of tight, near-optimal regret bounds for collaborative linear bandits with adversaries. Furthermore, by leveraging recent advances in high-dimensional robust statistics, we significantly extend our algorithmic ideas and results to (i) the generalized linear bandit model that allows for non-linear observation maps; and (ii) the contextual bandit setting that allows for time-varying feature vectors.

Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds
Aritra Mitra'
Arman Adibi'
George J. Pappas
Hamed Hassani
Department of Electrical and Systems Engineering famitra20, aadibi, hassani, pappasg) upenn. edu
Abstract
We consider a linear stochastic bandit problem involving M agents that can col- laborate via a central server to minimize regret. A fraction of these agents are adversarial and can act arbitrarily, leading to the following tension: while collabora- tion can potentially reduce regret, it can also disrupt the process of learning due to adversaries. this work, we provide fundamental understanding of this tension trade-off
by designing new algorithms that balance the exploration-exploiaae via carefully constructed robust confidence intervals. We also complement our algorithms with tight analyses. First, we develop robust collaborative phased elim-
ination algorithm that achieves Ô (x + 1/vM vdT regret for each good agent;
here, is the model-dimension and T is the horizon. For small a, our result thus reveals clear benefit of collaboration despite adversaries. Using an information- theoretic argument, we then prove matching lower bound, thereby providing the first set of tight, near-optimal regret bounds for collaborative linear bandits with adversaries. Furthermore, by leveraging recent advances high-dimensional robust statistics, we significantly extend our algorithmic ideas and results to (i) the generalized linear bandit model that allows for non-linear observation maps; and (ii) the contextual bandit setting that allows for time-varying feature vectors.
Introduction
One of the primary challenges in modern large-scale computing systems is that of security. Given that the individual agents in such large systems are often vulnerable to attacks, it is important to understand how the overall system behaves the face of adversarial corruptions. This observation has spurred a line of research dedicated to the design and analysis of distributed algorithms that are provably robust to a small fraction of adversarial agents; notably, motivated by emerging learning paradigms such as federated learning [1-3]. this body of work has focused primarily on empirical optimization [4-14]. However, when it comes to multi multi-agent sequential
risk minimizatiion/stocasst decision-making problems under uncertainty (e.g.. bandits and reinforcement learning), our under- standing analogous questions is quite limited. Our goal in this paper is to bridge the above gap by studying a collaborative linear bandit [15, 16] problem in the presence of adversaries.
In our model, . agents interact with the same linear bandit characterized by d-dimensional unknown parameter 0., and a finite set of K arms. These agents can collaborate via a central server to improve performance, as measured by cumulative regret. As examples, consider (i) team of robots exploring actions (arms) in common environment and interacting with a central controller; and (ii) a group of people exploring restaurants (arms) and writing reviews for a rew.mmmnddaiooonn server. In the absence of adversaries, there is a clear reason to collaborate in either case: by exchanging information, each agent can reduce its uncertainty about the arms faster than it could when acts
'The first authors contributed equally.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

alone, and thereby incur lesser regret. The situation becomes murkier and more delicate when certain agents misbehave: What if certain robots get attacked or certain people deliberately write spam reviews? More generally, the main question we ask in this paper is the following.
In multi-agent linear stochastic bandit problem, can we still hope for benefits of collaboration when a fraction a of the agents are adversarial? If so, what are the fundamental limits of such benefits?
As far as we are aware, the answers to these questions have thus far remained elusive, motivating our current study. The main technical hurdle we must overcome is to delicately balance the exploration- exploitation trade-off in the presence of both statistical uncertainties due to the environment, and worst-case adversarial behavior. Importantly, the above trade-off intrinsic to sequential decision- making is absent in static optimization problems. Thus, the ideas used to guarantee robustness for distributed optimization do not apply to our problem, making our task quite non-trivial.
Our Contributions. In this paper, we contribute to principled study of several canonical structured linear bandit settings with adversarial agents. Our specific contributions are as follows.
Robust Collaborative Linear Bandit Algorithm. We propose RCLB a phased elimination algorithm that relies on distributed exploration, and balances the exploration-exploitiion dilemma in the presence of adversaries via carefully constructed robust confidence intervals. We prove that RCLB guarantees Ô ((a+1//VI) 1/VM v dT regret for each good agent; see Theorem 1, This result is both novel, and significant in that reveals clear benefit of collaboration (despite adversaries) for small values of a. In particular, when a = O, the regret bound of RCLB is minimax-optimal in all relevant parameters: the model-dimension d, the horizon T, and the number of agents M.
Fundamental Limits. At this stage, one may ask: ly the additive oVT term in Theorem I simply an artifact of our analysis? ? In Theorem 2, we establish a fundamental lower bound, revealing that such a term is in fact unavoidable; it is the price one must pay due to adversarial corruptions. A key implication of this result is that our work is the first to provide tight, near-optime regret bounds for collaborative linear bandits with adversaries. The proof of Theorem 2 relies novel connection between the information-theoretii arguments in [17], and ideas from the robust mean estimation literature [18, 19]. As such, our proof technique may be relevant for related settings.
In our next set of contributions, we significantly extend our results to more general bandit models.
Generalized Linear Bandit Setting. In Theorem 3, we prove that one can achieve bounds akin to that in Theorem 1 for the generalized linear bandit model (GLM) [20, 21] that accounts for non-linear observation maps. To achieve this result, we propose a variant of RCLB that leverages very recently developed tools from nigh-dimensional robust Gaussian mean estimation [22]. Deriving robust confidence intervals for this setting requires some work: we exploit regularity properties of the non-linear observation model along with error bounds from [22] for this purpose. As far as we are aware, Theorem 3 is the first result to establish inverssrial-robusteee for GLMs, allowing our framework to be applicable to a broad class of problems (e.g.. logistic and probit regression models).
Contextual Bandit Setting. Finally, we turn our attention to the contextual bandit setting where the feature vectors of the arms can change over time. This setting is practically quite relevant as web-recommenattion systems are often modeled as contextual bandits [23]. The main challenge here arises from the need to simultaneously contend with time-varying optimal arms and adversaries. To handle this scenario, we develop robust variant of the SUPLINREL algorithm [24] that guarantees a near-optimal regret bound identical to that of Theorem 1; see Theorem 4.
Overall, via the proposal of new robust algorithms complemented with tight analyses, our work takes an important step towards multi-agent sequential decision decision-making in the presence of adversaries.
Related Work. There a growing strand of literature that studies the effect of reward corruption in stochastic bandits (for single-agent setting) where the adversary has fixed corruption budget [25-32]. The techniques in these papers do not apply to our work as our setting very different: the adversarial agents in our model can act arbitrarily, and have no budget constraints. Several papers study multi-agent bandit problems in the absence of adversaries [33-52]. A few very recent ones [53-56] also look at the effect of attacks, but for the simpler unstructured multi-armed bandit problem. Accounting for adversarial agents in the structured linear bandit setting we consider here requires significantly different techniques that we develop in this paper.
2

---

2 Problem Formulation
We consider setting comprising of central server and M agents; the agents can communicate only via the server. Each agent E [M] interacts with the same linear bandit model characterized by an unknown parameter O. that belongs to a known compact set θ C Id. We assume ||0.1l S 1. The set of actions A for each agent is given by K distinct vectors in IR", i..., A = {aI,.... .xx J. where K is finite, positive integer. Based on all the information acquired by agent up time t - it takes an action diet E A at time i, and receives a reward yi,t given by the following observation model:
Vi. (0., (r,)) + Th,
(I)
Here, {M.c}} is a sequence of independent Gaussian random variables with zero mean and unit variance. Thus far, we have essentially described a distributed/multi-ageett linear stochastic bandit model. Departing from this standard model, we focus on a setting where fraction a E [0, 1/2) of the agents are adversarial; the adversarial set is denoted by B, where [B| a.M. In particular, we consider a worst-case attack model, where each adversarial agent E is assumed to have complete knowledge of the system, and is allowed to act arbitrarily. Under this attack model, an agent E B can transmit arbitrarily corrupted messages to the central server.
Our performance measure of interest is the following group regret metric Rr defined w.r.t. the non-adversarial agents:
RT E
0.. U2 - axe))
[E[M]\B t=1
where a, arggax,,,,, (f., (P..a) a) is the optimal arm, and the time horizon. We will work under regime where the horizon T is large, satisfying T Md. The goal of the good (non-adversarial agents to collaborate via the server and play a sequence of actions that minimize the group regret Rr. Let now make few key observations. In principle, each good agent can choose to act independently throughout (i.e., not talk to the server at all), and achieve Ö(v regret by playing standard bandit algorithm. Clearly, the group regret Rr would scale as Ô ((1 al in such a case. In the absence of adversaries however, one can achieve a significantly better group regret bound of Ô (VMdT) via collaboration, i.e., the regret per good agent can be reduced by factor of VM relative to the case when it acts independently (see, for instance, [41] and [45]). Our specific interest in this paper is to investigate whether, and to what extent, of collaboration despite the worst-case attack model described above. Said differently, we ask: Can we improve upon the trivial per agent regret bound of ÖVVTT) in the presence of adversaries?
retain the benefits
Throughout the rest of the paper, we will answer the above question in the affirmative by deriving novel robust algorithms for several canonical bandit models, and then establishing near-optimal regret bounds for each such model.
3 Robust Collaborative Phased Elimination Algorithm for Linear Bandits
In this section, we develop a robust phased elimination algorithm that achieves the near-optimal regret bound of Ô ((a for the worst-case attack model described in Section 2. To highlight the challenges that we need to overcome, consider the following scenario. During the initial stages of the learning process, when the arms in A have not been adequately sampled by the agents, even a good agent may have "poor estimates" of the true payoffs associated with each arm, i.e., the variance associated with such estimates may be large. This statistical uncertainty can be exploited by the adversarial agents to their benefit. In particular, we need to devise an approach that can distinguish between benign stochastic perturbations (due the noise in our model) and deliberate adversarial behavior. In what follows, describe our proposed algorithm Robust Collaborative Phased Elimination for Linear Bandits (RCLB) that precisely does so in a principled way.
/1/M) (1a+)1/M)
VdT) per good agent. This is non-trivial as we must account
We will use || to represent the Fuclidean norm, and denote the transpose of vector a. For ease of exposition, assume that there unique optimal arm.
3

---

Algorithm Robust Collaborative Phased Elimination for I Linear Bandits (RCLB)
Input: Action set A = {ai,..., ,ak) confidence parameter ò, and corruption fraction Initialize: l f= 1 and A A.
I: Let Ve(TT) LeEAe T(a)aa' and (T( _ max.eA. ||all Vi(m)- Server solves an approximate
G-optimal design problem to compute distribution нe over A such that ge( s 2d and [Tupp( I 48d log log d.
2: For each Ac, server computes ma (4) via Eq. (5), and broadcasts {ml (2) Jue.,,
JuE,, to all agents.
3: for i E [M] \ B do
(2) 4: For each arm Ae, pull it ml times. Let ri be the average of the rewards observed by
agent for arm during phase L. Compute local estimate 6/9) of as follows.
5:
0/00 YY,,, where Ve - Σ m
Yi, =mm= 1
aESupp(Ft)
acSupp(#e)
6: Transmit 0/0) to server. Adversarial agents transmit arbitrary vectors at this stage.
7: end for
(2) 8: Server computes robust mean pay-offss for each active arm: for each Ar, estimate pe as
Median (1(0,9) ,)) [M]))
9: Define robust confidence threshold " & V2C (1 (1+ ce. where C' is as in Lemma Server performs phased elimination with the robust means and y/ to update active arm set:
Ac+1 = {a (a E A max 14 p/ S 27
(4)
DEA:
10: 8= +1 and Goto line 1.
Description of RCLB (Algorithm 1). The RCLB algorithm we propose is inspired by the phased elimination algorithm in [57, Chapter 22], but features some key differences due to the distributed and adversarial nature our problem. The algorithm proceeds in epochs/phases, and in each phase f, the server maintains an active candidate set Ar of potential optimal arms. The exploration of arms in A is distributed among the agents. Upon such exploration, each agent i reports back local estimate g()) of the unknown parameter 0.: adversarial agents can transmit arbitrarily corrupted messages at this stage. Using the local parameter estimates (0(0)) ]E[M) the server then constructs (i) robust estimate of the true mean payoff (0., a) for each active arm a E Ar, and (ii) an inflated confidence interval that captures both statistical and adversarial uncertainties associated with such robust mean estimates. This step is crucial to our scheme and requires a lot of care as we explain shortly. With the robust mean payoffs and associated confidence intervals in hand, the server eliminates arms with rewards far away from that of the optimal arm a,, We now elaborate on above ideas.
Optimal Experimental Design. To minimize the regret incurred in each phase E, we need to minimize the number of arm- cem-pulls made to arms in Aç. To that end, we appeal to a concept from statistics known as optimal experimental design. The concept is as follows. Let क A + [0, 1] be distribution on T(a)aa'; g(T)) & maX ||a||2 V(r) -1 The so-called G-optimal design problem seeks to find distribution (design) æ. that minimizes In essence, sampling each arm a E A in proportion to x. (a) minimizes the number of samples/arm-pull needed to achieve a desired level of precision in the estimates of the arm means (0+.a), our purpose, we only need to solve an approximate G-optimal design problem: using the Frank-Wollh algorithm and an appropriate initialization, one efficiently find approximate optimal design ı such that g(T) < 2d, and [Supp(r)] < 48d log log [58, Chapter 3]. Accordingly, the server computes such approximate optimal distribution n. over A in each epoch (line of Algo. 1).
A such that ΣnEA (a)) = 1. Now define V(TT)
A. For
4 'Thouuhout, we assume that V is invertible in each epoch E; this the case when Ae spans Rd. If Ae does not span Rd can consider the lower dimensional subspace given by span(AA)).

---

Construction of Robust Arm- Pay-aayoff Estimates and Confidence Intervals. In each phase f, the server computes T and ma for every Ar as follows:
(6)
(T((add
1 5z
T
T
log
and m
(5)
M
where (e(a) is obtained from the approximate G-optimal design problem, 62 = 2- 2- 8, 3066=8(KKP) K/(K))
and 8 is a design variable to be chosen later. The idea is to explore an arm To times to estimate (0., a) up to a precision that scales linearly with ey; in later phases, we require progressively finer precision (hence, fg decays exponentially with é). The task of exploration is distributed among the agents, with each agent being assigned ml! arm- arm-pulls for every a E Ag. Using the rewards that it observes during phase f, each good agent i E [M] \ B computes a local estimate 0:00 of 0.. and transmits it to the server (lines 3-7 of Algo. 1). The key question now follows: How should the server use the local estimates "e ? Let us consider two natural strategies.
Candidate Strategies. One option could be to use the local estimates (0 (0:he Hetan along with high- sich-dmmnnsooal robust mean estimation algorithm to compute robust estimate of 6.. Yet another strategy could be for the server to query the raw observations (i.e., the Gi, 's) from the agents, use an univariate robust mean estimation algorithm (e.g., trimmed mean or median) to generate a "clean" version of each observation, and then use these clean observations to compute robust estimate of 0.. Although feasible, each of the above strategies can unfortunately lead an additional vd factor in the regret bound; we discuss this point in detail in the Appendix. The main message we want to convey here is that certain natural candidate solutions can lead to sub-optimal regret bounds.
Main Ideas. Our main insight is the following: to achieve near-optimal optimal regret bounds, one need not go through the route of first computing a robust estimate of 0.. As our analysis will soon reveal, it suffices to instead compute robust estimates of the arm pay-off's { a) Joc directly by employing the estimator in line 8 of Algo. 1. The key statistical property that we exploit here is
that for each a E A and i E [M] B, the quantity (8(0) a) is conditionally-Gaussie (0., a)- This observation informs the choice of the median operator in line 8 of Algo. 1. Our next task is to compute appropriate confidence intervals for the robust arm-mean-este -ean-estimates in order to eliminate sub-optimal arms. This a delicate task as such confidence intervals need account for both statistical uncertainties and adversarial perturbations. Indeed, if the confidence intervals are too tight, then they can lead to elimination of the optimal arm a.; if they are loose, then they can lead to large regret. The confidence threshold y/ in line 9 of Algo. 1 strikes just the right balance; the choice of such intervals is justified in Lemma 1.
with mean
We now state and discuss our main result concerning the performance of RCLB.
Theorem 1. (Performance of RCLB) Suppose E [0, 0.5). Given any ó E (0, set ő = 8/ (10K).
Then, RCLB guarantees that with probability at least - 6, the following holds for each good agent i [M] \ B:
E -aiz) Ō 0 ((a VIM V dT
(6)
Main Takeaways. From Theorem 1, note that RCLB guarantees sublinear regret despite the presence of adversarial agents. More importantly, the regret bound in Eq. (6) has optimal dependence on the model-dimension d. the horizon T, and also on the number of agents M when a = 0 (i.e., in the absence of adversaries). When a is small, Eq. (6) reveals that one can indeed retain the benefits of collaboration, and improve upon the trivial per agent regret of Ó(V Interestingly, this result mirrors that of similar flavor for distributed stochastic optimization under attacks: given M machines, a fraction of which are corrupt, the authors in [6] showed that no algorithm can achieve
statistical error lower than á (a/vT + 1/VMT) for strongly convex loss functions; here, is the number of samples on each machine. As far as we are aware, this is the first work establish an analogous result for collaborative linear bandits. Inspired by the lower bound in [6], one may ask: Is the additive av'T term in Eq. (6) unavoidable? We will provide a definitive answer in Section 4. Finally, we note that Theorem immediately implies a bound of Ô ( (a.M + vM) VaT) on the group regret Rr. We provide formal proof of this fact in Appendix C.
5

---

Proof Outline of Theorem 1. The first main step in our analysis of Theorem is to provide guarantees on the estimates {ua JaEAc computed in line of RCLB. This achieved as follows.
Lemma 1. (Robust Confidence Intervals) Fix any epoch There exists an universal constant > such that for each active arm b E Ae, the following holds with probability at least - ōg:
(9) 1mg
(0,, by S ye, where ye= =VV2' (1 (1+0 (VaMM) ce-
Equipped with the above result, we argue that with high-probability, (i) the optimal arm a, is never eliminated by RCLB (Lemma 4 in App. C); and (ii) in each epoch an active arm in A, can contribute to at most ((Te) per-time-step regret (Lemma in App. C). Putting these pieces together in a careful manner yields the desired result; we defer a detailed proof of Theorem 1 Appendix C.
In the next section, we derive a lower bound that provides fundamental insights into the impact of the adversarial agents for the multi-agent sequential socision-making problem considered in this paper.
4 Lower Bounds
In this section, we assess the optimality of the regret bound obtained in Theorem 1. To do so, we consider a slightly different attack model: we assume that each of the agents is adversarial with probability a, independently of the other agents. Thus, the expected fraction of adversaries is Next, to provide clean argument, we will focus on a class of policies II where at each time-step t, the server assigns the same action to every agent, i.e., Oi,t a,, Vi [M]. We note that all the algorithms developed in this paper adhere to policies in II. Moreover, policies within the class IT yield the minimax optimal per-agent regret bound of order Ö( / /M) when a = O. Since the standard multi-armed bandit setting [59] is special case of the structured linear bandit setting considered here, a lower bound for the former implies one for the latter. With this in mind, let us denote by e(K) Ex" (1) the class of multi-armed bandits with K arms, where the reward distribution of each arm is Gaussian with unit variance. An instance Vμ E EX² (1) is characterized by the mean vector E IR associated with the K arms. Finally, let (v,)) denote the expected cumulative regret of the server (which is the same as that of good agent E [M) \ (3) when it interacts with the instance Vμ. We can now state the following result which establishes a fundamental lower bound for our problem.
Theorem 2. (Fundamental Lower Bound) Given any policy in 11, there exist two distinct instances Vas Uy E {(2) (1), and an universal constant > 1, succh that
max (v)),
(vp). R (vw)) 2 caVT,
(8)
irrespective of the number agents M.
Main Takeaways. Observe from Eq. (6) that even when M is arbitrarily large, the additive avT term due to the adversaries remains unaffected Is this term truly unavoidable or just an artifact of our analysis? ? Theorem 2 settles this question by revealing fundamental performance limit: every policy in IT has suffer the additive a T regret, regardless of the number of agents. Thus, taken together, Theorems / and 2 provide the first set of tight, near-optimal regret guarantees for the setting considered in this paper. We consider this to be a significant contribution of our work.
Proof Idea for Theorem 2. For our setting, the standard techniques to prove lower bounds for non-adversarial bandits do not directly apply. The lower-bound proofs used for reward-corruption models [60], and attacks with a fixed budget [31], are not applicable either. This motivates us to use new proof technique that combines information-theoreee arguments in [17] with ideas from the robust mean estimation literature [18, 19]. Specifically, for a two-armed bandit setting, we carefully construct two instances and attack strategies such that the joint distribution of rewards seen by the server is identical for both instances. Moreover, the instances are constructed such that (i) the optimal arm in one instance is sub-optimal for the other; and (ii) the per-time-step regret for selecting sub-optimal arm in either instance is M(a VT). For detailed proof, see Appendix D.
Having established tight bounds for the linear bandit model in Section 2, in the sequel, we will show how our algorithmic ideas and results can be significantly extended to more general settings.

---

5 Extension to Generalized Linear Models with Adversaries
In this section, we will show how to achieve regret bound akin to that in Theorem 1 for the non-linear observation model shown below [20, 21 known as the generalized linear model (GLM):
yi, = μ ((0.. ax,1)) + 7h,t:
where μ : R - I. is a continuously differentiable function typically referred to as the (inverse) link function, and T,, (N0 1) is as before. Our goal is to now control the following notion of regret:
R
Σ
Σ (N ((), - (())))))))))
(10)
(E(M)
where a, argmaX, (0.,,)) The main technical challenge relative to the setting considered in Section 2 pertains to the construction of the robust confidence intervals. In particular, the non- linearity of the map za(-) makes it hard to apply the technique adopted in line 8 of RCLB, necessitating a different approach that we describe next. We start with the following standard assumption [20, 21].
Assumption 1. The function μ : ER- + R is continuously differentiable, Lipschitz with constant 2 2 L, and such that
h = min inf ((((,,)) a))3 > O.
DEE,aEA
Here, j(() is used to represent the derivative of n..))
Next, for any 0 E Rd, we define he(0)= Ea Sugp(t( ma ( (6,, a))a. We now describe a variant of RCLB dubbed RC-GLM- for generalized linear models. Notably, unlike the standard bandit algorithms [20, 21] for GLM's that build on LinUCB, RC-GLM is based on phased elimination.
Description of RC-GLM. Our algorithm uses as a sub-routine the recently proposed Iteratively Reweighted Mean Estimator for computing robust estimate of the mean of high-dimensional Gaussian random variables with adversarial outliers [22]. Specifically, suppose we are given M d-dimensional samples .i,.... MM. such that (1 a M of these samples are drawn i.i.d. from (w, Σ). where Rd is unknown mean vector, and Σ E Rdxd is known covariance matrix. The remaining a.M samples are adversarial outliers and can be arbitrary. The estimator in [22] takes as input the M samples, the corruption fraction a, and the covariance matrix Σ. It then outputs an estimate i of such that with high probability, ||0 ull = Ô (IEI!!? 1/2 (Vd/M + a (1/og(1/a))
Importantly, the estimator [22] runs in polynomial-time, and is minimax- minimax--ate-optimaal Let us now see how this estimator described in Appendix E can be applied to our setting.
We only describe the key differences RC- GC- relative to RCLB here, and defer a detailed description of GLM to Appendix E. To get around the difficulty posed by the non-line non-linear link function, our main idea is to first compute a robust estimate (( of f., at the server, and then use it to develop phased elimination strategy. To that end, instead of computing local estimate g( as in RCLB, each good agent E [M] \ transmits Yi, to the server, and the server computes a vector X, as follows: X; = ITW((? (TW((V-2//0) (V,22/yy,,, E [M]]). Here, V and Y., are as in Eq. (3), and we used ITW(.) to denote the output of the robust estimator in [22]. Our key observation here is that for each
good agent i, V/-1/2y,, is a d-dimensional Gaussian random variable with mean / hv.(.), and covariance matrix Σ- = Ia, justifying the use of the robust Gaussian mean estimator in [22]. The fact that = La crucial our algorithm design as the error-bound in [22] scales with the 2-norm of E. Essentially, the above steps enable us to extract statistic X that captures information about the agents' observations during epoch é. Using this statistic, the server next computes estimate ((0) of 0, by solving ()((())) = 1/22 Xe, and employs the following phased climination strategy:
Art1 = {a E max ((8())) b8) (,00) a)) S 25:): &e = C(ka/k) (va ( + ay M log( ex,
where Õ is an universal constant known to the server. Deriving an analogue of Lemma to compute the robust confidence threshold 7 requires some work. This is achieved by exploiting the regularity properties of the link function in tandem with the confidence bounds in [22]; see Appendix E for details and a proof of our main result for RC-GLM stated below.
We argue in Appendix E that this equation admits unique solution.
7

---

Algorithm 2 Robust BaseLinUCB (at Server)
Input: Confidence parameter 8, corruption fraction a, and index set 1/t S 1].
1: Ag M + -EE Tr,a, VT,a."
2: for E [M]] do
> Compute local parameters for each agent
3: by,t f Erewh Th, 0r + +
4: end for
5: for E [K] do
Compute robust estimates for each feature vector
6: fr.a + Median (( a (MM)) wt, + a 20V
log(t) M
|| A, 1, where
C in Lemma 1.
7: end for
Theorem 3. (Performance of Algorithm RC-GLM) Suppose -5- 101/10 and M
Mlog KT)). Given any 5 E (0, 1), RC-GIL GLM guarantees that with probability at least 1 - 6, the following holds for each good a E [M]
(.t)) Σ (u ((0,, ((0, (lk2/ki) (avlog (1/a) + v ddM vaT)
(11)
Main Takeaways. Theorem 3 significantly generalizes Theorem I and shows that even for general non-linear observation maps, one can reap the benefits of collaboration in the presence of adversaries. The additional vd factor in the bound (11) relative to that in (6) is inherited from the error-rate guarantees in [22]; the task of tightening this bound is left as future work. Nonetheless, Theorem 3 is the only result we are aware of that provides adversarial-robustee
guarantees for GLMs.
Remark 1. (Communication Complexity of RCLB and RC-GLM) It is not hard to see that the number of epochs/phases in RCLB and RC- GLM is Olog((MT) (MT)). Since communication between the server and the agents occurs only once in every epoch, note that the communication complexity of these algorithms scale logarithmically with the horizon T. Thus, our proposed algorithms not only lead to near-optimal regret bounds in the face of worst-case adversarial attacks, they are also communication- efficient by design. This is an important point to take note of as communication -efiiiinneff is key consideration in large-scale computing paradigms such federated learning.
6 Robust Collaborative Contextual Bandits with Adversaries
In this section, will consider collaborative contextual bandit setting where at each time-step t E [T], the server and the agents observe K d-dimensional feature vectors, {Iz,ala [K]}, with ||=t,al| < L, Va [K] and Vt [T'. We assume that the adversarial agents have control over the generation of the feature vectors. Associated with each arm a E [K]. the stochastic reward observed by an agent E [M] comes from the following observation model:
(12) where {m,r(a)} are drawn i.i.d. from No, 1). At each time step t, good agent i E [M] \ B plays an action di,t E [.K and receives the corresponding reward ri,t 2 Vı., (a..) based on the observation model in (12). The main difference the setting considered here relative to the one in Section 2 is that the feature vectors for each arm can change over time. As a result, the optimal action a; = argmax_e|K]] (0., L1,a) can change over time, making it particularly challenging to compete with time-varying optimal action the presence of adversaries. This dictates the need for a different algorithmic strategy compared to the one we developed in Section 1. Before we develop such strategy, let first formally define the performance metric of interest to in this setting:
(a) (0., + Ta.)
R
Context E LEE
ΣΣ
(0,, Dt.az Frraa.))
(13)
LiE(MTTBL=L
The main question we ask is: For the contextual bandit setting described above, can one continue to hope for benefits of collaboration in the presence of adversaries? In what follows, we will answer this question in the affirmative by developing a variant of the SUPLINREL algorithm in [24].
8

---

Algorithm 3 Robust Collaborative SupLinUCB for Contextual Bandits (at Server)
Input: Confidence parameter 6, corruption fraction a, and horizon T.
1: S [In T7; ()()) <- D, Vs E [S].
2: for t E [T] do
3:
5 and A₁ + [K].
4: repeat
5: Use Algorithm 2 with d 8/(KST), and index set v/(²) to compute robust estimates
(Fl. ( of the means and variances of the payoffs associated with each arm a E AA.
6: If wii 2- for some a E As, then choose this arm, i.e., set at = a. Store the
corresponding phase: wile) = v6t)) U [t], (a) 7: Else if wi,a I 1/VMT Va E As then select the arm with the highest robust upper
vi(() [+1 = oi 4l + s.
confudence bound: ot = argmax ((()) + ww Do not store this phase, i.e., Vi41 =
w(
VLE [S).
8:
Else if 11a <2-2/VN Va E As. then update active arm-set as
(8) (f(e) w({)) (ple) + wa(( S 22(1-5)//1 M.
As+1= = {a Aal max
bEA,
9: S 1.
10: until action a, is chosen.
11: Broadcast the chosen action ot to every agent (i.e., Oz,t = ai E [M], and receive
corresponding rewards (ra,)ve[M]) Adversarial agents can transmit arbitrary reward values.
12: end for
Description of Algorithm 3. At each time-step i, our proposed algorithm, namely Algorithm 3, scans through the set A of arms to determine a suitable action a, This scanning process (lines 4-10 of Algo. 3) is done at the server over S phases. Corresponding to each phase [S], the server maintains a set o the set w/()) stores all the time-steps in [t - 1] where an action is chosen in phase of the scanning process based on line 6 on Algo. 3. The scanning process itself relies on Algorithm 2 as a sub-routine. Specifically, in each phase s, the server first invokes Algorithm to obtain a robust estimate p(.)) of Tr.a) for each arm a E A,,, along with an associated inflated confidence (*) width ii, (line 5 of Algo. 3). If the confidence width is too large for particular arm (as in line 6), then such an arm requires exploration and accordingly chosen to be at. If, on the other hand, the confidence widths of all arms are sufficiently small (as in line 7), then is chosen to be the arm with the highest upper-confidence bound. Thus, we follow the principle optimism in the face of uncertainty here, while exercising caution account for the presence of adversaries (via the use of inflated confidence intervals). If the conditions in lines 6 and both fail, then the arms in A, require further screening. Accordingly,
move to the next phase + 1. retaining only those arms that are sufficiently close to the optimal arm af; see line 8 of Algo. 3. Our main innovation lies in (i) the construction of the robust cum-estimates in Algo. 2 that account for both statistical and adversarial behavior, and (ii) the careful use of such estimates in lines 6-8 of Algo. 3 to pick the action a, The next result reveals that the combination of these ideas yields near-optimal regret bounds.
Theorem 4. (Performance of Algo. 3) Suppose a E (0, 0.5). Given any E (0, 1). Algo. 3 guarantees that with probability at least - 6, the following holds for each good agent E [M]] \ B.:
T
(0., Zi,a; ) =ō ((a+ (a++v//M VdT)
(14)
Main Takeaways. For the contextual bandit setting considered here, the single-agent minimax optimal regret in the absence of adversaries is (dTT) [24]. In light of the lower bound in Theorem 2, we see that Theorem 4 provides a near-optimal regret guarantee, just as Theorem I.
For ease of exposition, we have considered Gaussian noise (in the observation model) throughout the paper. However, both our algorithms and results can be extended with slight modifica- tions to Sab-Gaussian noise sequences. We elaborate on this point in Appendix B.
Remark 2.

---

So Kulee 7O1 Keili
Calleca
Edlett M0-000
ae Mabli
402
6-1
80-
120
30.0
(a)
(b)
(c)
(d)
Figure 1: Plots of per-agent regret for the linear bandit experiment. (a) Comparison between RCLB and vanilla non-robust phased elimination algorithm. (b) Performance of RCLB for varying number of agents M, with M = 100. For (d), we set a = 0.1, M = 100, and compare RCLB to a phased elimination algorithm where the agents do not collaborate. We also plot theoretical upper-bounds: (T = 40v d7 and (2(T) 40(a + VI
0.1. (c) Performance of RCLB for varying corruption fraction a. with
7 Simulation Results
We report simulation results on synthetic data to corroborate our developed theory. Additional simulations on contextual bandits and alternate attack models are presented Appendix
Experimental Setup. We consider a setting with 50 actions in I we describe how these actions and 8* are generated in Appendix The rewards are generated based on the observation model in Eq. (1). We now describe the attack model. To manipulate the server into selecting sub-optimal arms, each adversarial agent employs the simple strategy of reducing the rewards of the good arms and increasing the rewards of the bad arms. More precisely, in each epoch f, upon pulling an arm a and observing the corresponding reward Ya. adversarial agent i does the following: if ya > p(f., a.). then this reward is corrupted to Ja = 3; and if S p(fl,,,,) then the reward is corrupted to p = 0.6 and B Agent i then uses all the corrupted rewards in epoch l to generate the local model estimate 0 that is transmitted to the server.
U. = ya + 8. For this experiment,
Discussion of Simulation Results. Fig. summarizes experimental results. In Fig. 1()), compare our proposed algorithm RCLB to a vanilla distributed phased elimination (PE) algorithm that does not account for adversarial agents. Specifically, the latter is designed by replacing the median operation in line 8 of Algorithm with a mean operation, and setting the threshold Y in line to be eg. Fig. ((a) shows that even small fraction 0.1 of adversaries algorithm to incur linear regret. In contrast, RCLB continues to guarantee sub-linear regret bounds despite adversarial corruptions. Furthermore, the regret bound of RCLB in the presence of small fraction of ad adversarial agents is close to that of the non-robust algorithm in the absence of adversaries. This goes on to establish the robustness RCLE
cause the non-robust PE
Fig. 1(b) depicts the performance of RCLB for varying values of the number of agents M, at fixed 0.1. We observe that increasing M results in lower regret, indicating clear
corruption level benefit of collaboration despite the presence of adversaries. fraction a, keeping M fixed at 100. As expected, increasing leads higher (albeit sub-linear) regret. Importantly, the trends observed in both Fig. 1(b) and Fig. 1(c) are consistent with the theoretical upper-bound O((a (1((=+1/MM))) 1/VM)//T predicted by Theorem 1.
Fig. ((c), we vary the corruption
A trivial way to avoid adversarial corruption is for a good agent to not participate in any collaboration at all, and run standard single-agent bandit algorithm. This would result such an agent incurring O(vdT) regret. The purpose of Fig. ((d) is to drive home the point that RCLB can lead to significant improvements over trivial non-collaborative strategy. To make this point clear, compare RCLB to a standard single-agent phased climination algorithm that does not involve any collaboration, and observe that despite adversarial corruption, RCLB leads considerably lower regret bounds as compared to the non-collaborative strategy. This highlights the importance of our approach.
Acknowledgments and Disclosure of Funding. This work was supported by NSF Award 1837253, NSF CAREER award CIF 1943064, the AFOSR-YIP award FA9550-20-1-0111 and EnCORE.
10

---

References
[T] Jakub Konečný, H Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv: 2016.
[2] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, H Brendan McMahan, et al. Towards federated learning at scale: System design. arXiv preprint arXiv: 01046, 2019.
[3] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Commumication tiaeumicationneffccientt learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[4] Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM Measurement and Analysis of Computing Systems, 1 122):125,, 2017.
[5] Peva Blanchard, EI Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Proceedings of the 3 International Conference on Neural Information Processing Systems, pages 118-128, 2017.
[6] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robuse distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pages 5650-5659. PMLR, 2018.
[7] Lingjiao Chen, Zachary Charles, Dimitris Papailiopoulos, et al. Draco: Robust distributed training via redundant gradients. arXiv preprint UrXiv:1803.09877 2018.
[8] Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. arXiv preprint arXiv: arXiv: 11800.089177 2018.
[9] Cong Xie, Oluwasammi Koyejo, and Indranil Gupta. Generalized byzantine-tolerant sgd. arXiv preprint arXiv: 1802. 2018
[10] Liping Li, Wei Xu, Tianyi Chen, Georgios B Giannakis, and Qing Ling, Rsa: Byzantine- robust stochastic aggregation methods for distributed learning from heterogeneous datasets. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1544-1551, 2019.
[11] Avishek Ghosh, Justin Hong, Dong Yin, and Kannan Ramchandran. Robust federated learning heterogeneous environment. arXiv preprint arXiv: 066.9, 2019.
[12] Avishek Ghosh, Raj Kumar Maity, Swanand Kadhe, Arya Mazumdar, and Kannan Ramachan- dran. Communication efficient and Byzantine tolerant distributed learning. In 2020 IEEE International Symposium on Information Theory (ISIT), pages
IEEE, 2020.
[13] Avishek Ghosh, Raj Kumar Maity, and Arya Mazumdar. Distributed newton can communicate less and resist Byzantine workers. arXiv preprint arXivv20066.87777, 2020.
[14] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. International Conference on Machine Learning, pages 5311-5319, PMLR, 2021.
[15) Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008
[16] Yasin Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-2333 2011.
[17] Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet. Bounded regret in stochastic multi-armed bandits. In Conference on Learning Theory, pages 122-134. PMLR, 2013.
[18] Mengjie Chen, Chao Gao, and Zhao Ren. Robust covariance matrix estimation via matrix depth. arXiv preprint (0XXv:1100600099 2015.

---

[19] Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 665-674. IEEE, 2016.
[20] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In NIPS, volume 23, pages 586-59 1964594,44 2010.
[21] Lihong Li, Yu Lu, and Dengyong Zhou, Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR, 2017.
[22] Arnak S. Dalalyan and Arshak Minasyan. All-in-one robust estimator of the gaussian mean. The Annals of Statistics, 2022.
[23] Lihong Li. Wei Chu, John Langford, and Robert E Schapire. A contextual approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[24] Peter Auer. Using confidence bounds for exploitation-exploriioo trade-offs. Journal of Machine Learning Research, 3(Nov):397-422 2002.
[25] Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Xiaojin Zhu. Adversarial attacks on stochastic bandits. arXiv preprint arXiv: 1810. /2/88, 2018.
[26] Fang Liu and Ness Shroff. Data poisoning attacks on stochastic bandits. In International Conference on Machine Learning, pages 4042-4050. PMLR, 2019.
[27] Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1 14-112 2018.
[28] Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562-1578. PMLR, 2019.
[29] Ilija Bogunovic, Andreas Krause, and Jonathan Scarlett. Corruption-tolerant gaussian process bandit optimization, International Conference on Artificial Intelligence and Statistics, pages 1071-1081. PMLR, 2020.
[30] Evrard Garcelon, Baptiste Roziere, Laurent Meunier, Jean Tarbouriech, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirotta. Adversarial attacks on linear contextual bandits. arXiv preprint arXi::2002.008889 2020.
[31] Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 991-999. PMLR, 2021.
[32] Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. arXiv preprint r:Xiv:2205.0681/ 2022.
[33] Keqin Liu and Qing Zhao. Distributed learning in multi-armed bandit with multiple players. IEEE Transactions on Signal Processing, 58(1) 38(11):5667-54) ):5667-5681, 2010.
[34] Dileep Kalathil, Naumaan Nayyar, and Rahul Jain. Decentralized learning for multiplayer multiarmed bandits. IEEE Transactions on Information Theory, 60(4):2331 2014.
[35] Soummya Kar, H Vincent Poor, and Shuguang Cui. Bandit problems in networks: Asymptot- ically efficient distributed allocation rules. In 2011 50th IEEE Conference Decision and Control and European Control Conference, pages 1771-1778. IEEE, 2011.
[36] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. Distributed cooperative decision-making in multiarmed bandits: Frequentist and bayesian algorithms. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 167-172. IEEE, 2016.
[37] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. Distributed cooperative decision making in multi-agent multi-armed bandits. Automatica, 125:109445,
12

---

[38] Shahin Shahrampour, Alexander Rakhlin, and Ali Jadbabaie. Multi- bandits in multi-agent networks. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2786-2790. IEEE, 2017.
[39] Swapna Buccapatnam, Jian Tan, and Li Zhang. Information sharing in distributed stochastic bandits. In 2015 IEEE Conference on Computer Communications (INFOCOM), pages 2605- 2613. IEEE, 2015.
[40] Ravi Kumar Kolla, Krishna Jagannathan, and Aditya Gopalan. Collaborative learning of stochastic bandits over a social network. JEEE/ACM Transactions on Networking, 26(4):1782- 1795, 2018
[41] Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optimal regret with efficient communication. arXiv preprint
2019.
[42] Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai. Social learning in multi agent multi armed bandits. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(3):1-35, 2019.
[43] David Martinez-Rubio, Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. arXiv preprint arXiv: 1810.04468, 2018.
[44] Abhimanyu Dubey al. Kernel methods for cooperative multi-agent contextual bandits. In International Conference on Machine Learning, pages 2740-2750. PMIR, 2020.
[45] Abhimanyu Dubey and Alex Pentland. Differentialll-priiveee federated linear bandits. arXiv preprint arXiv:2010.11425 2020.
[46] Anusha Lalitha and Andrea Goldsmith. Bayesian algorithms for decentralized stochastic bandits. arXiv preprint 2rXiv:2010.10500 2020.
[47] Ronshee Chawla, Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai. The gossiping insert-eliminate algorithm for multi-agent bandits. In International Conference on Artificial Intelligence and Statistics, pages 3471-3481. PMLR, 2020.
[48] Ronshee Chawla, Abishek Sankararaman, and Sanjay Shakkottai. Multi-agent low-dimensional linear bandits. arXiv preprint arXiv:2007.01442, 2020.
[49] Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran. Collaborative learning and personalization in multi-agent stochastic linear bandits. arXiv preprint arXiv:2106.0890 2021.
[50] Mridul Agarwal, Vaneet Aggarwal, and Kamyar Azizzadenesheli. Multi-agent multi-armed bandits with limited communication. arXiv preprint arXiv:2102.08466, 2021.
[51] Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. In Abstract Proceedings of the 2021 ACM SIGMETRICS//ntenationn Conference on Measurement and Modeling of Computer Systems, pages 3-4, 2021.
[52] Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armed bandits with personalization. In International Conference on Artificial Intelligence and Statistics, pages 2917-2925. PMLR,
2021.
[53] Abhimanyu Dubey and Alex Pentland. Private and byzantine proof cooperative ciciisioo-makinn. In AAMAS, pages 357-365, 2020.
[54] Daniel Vial, Sanjay Shakkottai, and R Srikant. Robust multi-agent multi-armed bandits. In Proceedings the Twenty-secome International Symposium Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pages 161-170, 2021.
[55] Daniel Vial, Sanjay Shakkottai, and R Srikant. Robust multi-agent bandits over undirected graphs. arXiv preprint arXiv:2203. 00076, 2022.
[56] Aritra Mitra, Hamed Hassani, and George Pappas. Exploiting heterogeneity in robust federated best-arm identification. arXiv preprint arXiv:2109.05700 2021.
13

---

[57] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[58] Michael Todd. Minimum-volumee ellipsoids: Theory and algorithms. SIAM, 2016.
[59] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2))235-256, 2002.
[60] Sayash Kapoor, Kumar Kshitij Patel, and Purushottam Kar. Cormutiion-olerant bandit learning. Machine Learning, 108(4))687-715, 2019.
[61] Zixin Zhong, Wang Chi Cheung, and Vincent Tan. Probabilistic sequential shrinking: A best arm identificatiin algorithm for stochastic bandits with corruptions. In International Conference on Machine Learning. pages 12772-12781. PMLR, 2021.
[62] Shreyas Sundaram and Bahman Gharesifard. Distributed optimization under adversarial nodes. IEEE Transactions Automatic Control, (4(3):1033-1076 2018
[63] Lili Su and Nitin H Vaidya. Byzantine-resilien multiagent optimization. IEEE Transactions Automatic Control, 66(5):2227-22333 2233, 2020.
[64] Kananart Kuwaranancharoen, Lei Xin, and Shreyas Sundaram. Byzantine-resilieet distributed optimization of multi-dimensional functions. In 2020 American Control Conference (ACC),
pages 4399-4404. IEEE, 2020.
[65] Nirupam Gupta, Thinh T Doan, and Nitin H Vaidya. Byzantine fault-tolerance in decentralized optimization under 2f-redundancy. In 2021 American Control Conference (ACC), pages 3632- 3637. IEEE, 2021.
[66] Arman Adibi, Aritra Mitra, George J Pappas, and Hamed Hassani. Distributed statistical min-max learning in the presence of Byzantine agents. arXiv preprint arXiv:2204.0311 0312044..187,, 2022.
[67] Peter Huber. Robust estimation of a location parameter. In Breakthroughs in statistics, pages 592-518. Springer, 1992.
[68] Peter Huber. Robust statistics, volume 523. John Wiley & Sons, 2004.
[69] Yu Cheng, Ilias Diakonikolas, and Rong Ge. High-dimensional robust mean estimation in nearly-linear time. In Proc. of the thirtieth annual ACM-SIAM symp. on discrete algorithms, pages 2755-2771 STAM, 2019.
[70] Stanislav Minsker. Uniform bounds for robust mean estimators.
arXiv preprint
arXiv:18/2.03523, 2018.
[71] Gabor Lugosi and Shahar Mendelson. Robust multivariate mean estimation: the optimality of trimmed mean. The Annals of Statistics, 49(1):393 4100, 2021.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] While explaining the main takeaways from Theorem Section 5, we mention that our regret bound features an additional vd term relative to Theorem 1. Tightening this bound is part of our future
work.
(c) Did you discuss any potential negative societal impacts of your work? [No] We could not think of any negative socictal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We provide complete proof's of all our results the supplemental material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "h3BeGCyTM_", "reviewer": "Reviewer_Dj5j", "summary": "This work focused on the collaborative linear bandit problem with adversarial agents. The author proposes novel robust algorithms for the linear bandit and general linear bandit problems, with a $(\\alpha+1/\\sqrt{M})\\sqrt{dT}$ regret guarantee for each good agent. In addition, the author also provides a theoretical lower bound for the regret with adversarial agents and shows that the $\\alpha \\sqrt{T}$ regret is unavoidable.", "questions": "1. In the related work part, the author mentions recent advances in regret guarantees for the adversarial corruption bandit problem. More recent advanced works have focused on using the function approximation techniques. For instance, He et al. [2022] obtain a near-optimal regret guarantee with adversarial corruption. It is better if the author can mention them or discuss them.\n\nHe J, Zhou D, Zhang T, et al. Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions\n\n2. Since all theorems focus on regret for a single good agent, it seems unnecessary to consider total regret in equation (11).", "limitations": "This paper provides theoretical guarantees for learning linear bandit and linear mixture MDP. There is no negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. The author provides theoretical guarantees for the algorithms and achieves a near-optimal regret guarantee without adversarial agents. In addition, the lower bound suggest that the adversarial-dependent term $\\alpha \\sqrt{dT}$ is near optimal with the factors $T$ and $\\alpha$.\n\n2. For this problem, the author also provides a theoretical guarantee for the lower regret bound. \n\nWeakness:\n\n The algorithms require the stochastic noise to be Gaussian rather than sub-Gaussian, which is much more restrictive than previous work in linear bandit. In addition, for the contextual linear bandit and general linear bandit requires that all agents have the same feature vectors, which is far from the practice.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PZp1Lo5z68", "reviewer": "Reviewer_32Q7", "summary": "The paper considers the collaborative linear bandit problem in the case of adversarial agents. In the proposed setting, a fraction $\\alpha$ of agents can be adversarial. The main dilemma comes from the fact that although the collaboration reduces the number of required samples when adversarial agents are present, this can also work in the opposite direction. Besides the introduced setting, the authors propose a novel phased elimination algorithm that archives tight regret guarantees in the considered setting. Besides, the results are also provided for the two related settings: generalized linear bandit and the contextual bandit setting. ", "questions": "Please see the previous section.", "limitations": "Yes, I think so. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a well-written paper that considers an interesting twist to the collaborative linear bandit problem inspired by some recent works in the corrupted bandit literature. One of the main contributions is a novel and interesting setting that is first introduced in this paper, and that is not (to my knowledge) considered before.\n\nWhen it comes to the setting, one might argue why such a clean distinction among adversarial and non-adversarial agents, i.e., perhaps, in practice, it might make sense that even “good” agents suffer some adversarial observations. On the other hand, I can see how this clean separation (coming from the problem setting) is suitable for the median of means tools used in the analysis. \n\nCan you please comment on  $\\alpha \\in [0, 0.5)$, and what prevents us from $\\alpha > 0.5$? What are the limits here? For example, in case each good agent plays individually the bound $(1-\\alpha) M \\sqrt{dT}$ should still hold, i.e., it does not depend on $\\alpha$ being in  $[0, 0.5)$.\n\nWhile the phased algorithm and inflated confidence bounds are used in some similar adversarial settings, I still think the theoretical results of this paper are solid, and the techniques used in the analysis are different from the previous works. The obtained results are tight, as is evident by the lower bound result. Finally, the results are also provided for the GLM and contextual settings. \n\nThe paper is missing simulations. I would argue that a natural baseline is an algorithm that ignores collaboration. Depending on $\\alpha$, one can compare the proposed algorithm to that non-collaborative but completely robust one. Also, it is very easy to generate attacks in this setting by simply generating various $\\hat{\\theta}$’s in the case of adversarial agents. \n\nFinally, I think that this is an interesting work with solid theoretical results that can be of interest to the community. After the discussion period, I might rethink my score and consider increasing it. \n\nSome minor suggestions to improve:\n- I’m not sure that Corollary 1 is needed. Too much space is used to multiply the result of Theorem 1 with M. Perhaps, consider removing it and using this additional space to provide more intuition on the “Construction of Robust Arm-Payoff Estimates and Confidence Intervals”. \n- Problem formulation: Line 95: ”Based on all the information acquired by an agent ut to time…” This sentence was confusing because it was not clear how this is collaborative. It reads as if the agent only has access to its own observed rewards. Later on, this was explained, but a more careful introductory paragraph could avoid confusion. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MGgPrtXpdQF", "reviewer": "Reviewer_2PF8", "summary": "This paper considers the collaborative stochastic linear bandit problem where an $\\alpha$ portion of the $M$ agents may act arbitrarily.\n* The authors provided an algorithm RCLB that enjoys $\\mathcal O((\\alpha+1/\\sqrt M)\\sqrt{dT})$-style regret bound for each good agent.\n* They also proved that regardless of $M$, an $\\alpha\\sqrt{dT}$ factor is unavoidable. So the regret bound of RCLB is nearly tight.\n* They generalized the results to generalized linear bandits (GLM) and contextual linear bandits (CLB), giving near-optimal guarantees as well.", "questions": "* Is it possible to implement this algorithm more efficiently?\n* Is this algorithm able to handle more general noise models other than independent Gaussians (e.g., conditionally 1-sub-Gaussian or $[-1,1]$-bounded noises which are common in the linear bandit literature)?", "limitations": "See Questions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n* This work is the first to consider the presence of misbehaving adversaries among the agents, showing that it is still possible to achieve $\\mathcal O(\\sqrt{MdT})$ total regret even with adversaries.\n* The algorithm is not much more complicated compared to usual phase elimination algorithms (where there is no adversaries).\n* The authors justified that the algorithm is worst-case optimal by showing both $\\sqrt{MT}$ and $\\alpha \\sqrt{dT}$ factors are unavoidable.\n* The algorithm is also the first to work in harder generalizations (collaborative GLMs and CLBs with adversaries) while achieving near-optimal regret.\n\nCons:\n* The algorithm is not computationally efficient as it builds on phased elimination.\n* The noise model is assumed to be independent Gaussians.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Exlo2u4UIfU", "reviewer": "Reviewer_nXam", "summary": "\nThis paper studies a variant of collaborative linear bandits where $\\alpha$ fractions of M-agents act adversarially in a centralized setting. They propose a phased elimination algorithm with robust confidence intervals that achieves \\tilde{O}((\\alpha M+\\sqrt{M})\\sqrt{dT})  bound for the group regret. They also provide a lower bound on a slightly different model where each agent acts adversarially with probability $\\alpha$, showing that the additive term $\\alpha \\sqrt{T}$ term is unavoidable. They further consider generalized linear bandit setting and contextual bandit setting.\n", "questions": "What if corruption fraction $\\alpha$ is unknown to the system?\n\n\nIn algorithm 1, how do good agent's performance affect the resulting group regret? Indeed, it is not clear to me why G-optimal design is just solved approximately, though it can be exactly solved efficiently via convex optimization. \n\n＝＝Post Rebuttal＝＝\n\nThank you for author's detailed response. I have read other reviews and its response, which even made me vote for acceptance. \nHence I will keep my score.", "limitations": "-", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThey propose a novel problem for the collaborative bandit learning with adversarial agents. This problem is a good capture of the real-world case of multiple data observation points, some of which are spammed or collapsed.\n\nThey propose a first algorithm named Robust Collaborative Phased Elimination: good agents follow the arm selection based on G-optimal design and report their estimate and adversarial agents report arbitrary vectors. The central server must consider both statistical uncertainty and adversarial one. To overcome this, they consider a robust confidence interval for each active arm and employ robust mean pay-offs. The server decides which to eliminate in each phase. The presented regret analysis and lower bound shows the optimality of the algorithm.\n\nThey further consider generalized linear bandit setting and contextual bandit setting.\n\n\n\nWeakness:\nSometimes a sentence is too long or difficult to read (but in general, the paper is well structured)\n\nThe section “Related Work” is cluttered, citing more than 10 papers at a time. If you are proposing a new model, please provide a more careful summary of existing research and its position in the literature. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept