Byzantine-Resilient Decentralized Multi-Armed Bandits
Authors: Jingxuan Zhu
Alec Koppel
Alvaro Velasquez
Ji Liu
Venue: Accepted by TMLR ()

Abstract: In decentralized cooperative multi-armed bandits (MAB), each agent observes a distinct stream of rewards, and seeks to exchange information with others to select a sequence of arms so as to minimize its regret. Agents in the cooperative setting can outperform a single agent running a MAB method such as Upper-Confidence Bound (UCB) independently. In this work, we study how to recover such salient behavior when an unknown fraction of the agents can be Byzantine, that is, communicate arbitrarily wrong information in the form of reward mean-estimates or confidence sets. This framework can be used to model attackers in computer networks, instigators of offensive content into recommender systems, or manipulators of financial markets. Our key contribution is the development of a fully decentralized resilient upper confidence bound (UCB) algorithm that fuses an information mixing step among agents with a truncation of inconsistent and extreme values. This truncation step enables us to establish that the performance of each normal agent is no worse than the classic single-agent UCB1 algorithm in terms of regret, and more importantly, the cumulative regret of all normal agents is strictly better than the non-cooperative case, provided that each agent has at least $3f+1$ neighbors where $f$ is the maximum possible Byzantine agents in each agent's neighborhood. Extensions to time-varying neighbor graphs, and minimax lower bounds are further established on the achievable regret. Experiments corroborate the merits of this framework in practice.

Published in Transactions on Machine Learning Research (08/2024)
Byzantine- Decentralized Multi-Armed Bandits
Jingxuan Zhu
juzzus@zteejinnglla..or
Zhefiang Lab
Alec Koppel J.P. Morgan Al Research
adc.kkopec@@jpnccaas.com
Alvaro Velasquez
Awwro.uclasqueee@colorroe edd
University of Colorado Boulder
Ji Liu
fi. willi@sttnnbbrook.cii edu
Stony Brook University
Reviewed on OpenReview: https: ottp://veeerreveeeeemmmmm net/ forum? id=JoYMJJdury
Abstract
In decentralized cooperative multi-armed bandits (MAB), each agent observes distinct stream of rewards, and sccks to exchange information with others to select sequence of arms so as to minimize its regret. Agents in the cooperative setting can outperform single agent rumning a MAB method such as Upper-Confidence Bound (UCB) independently. In this work, we study how to recover such salient behavior when an unknown fraction of the agents can be Byzantine, that is, communicate arbitrarily wrong information in the form of reward mean-estimates or confidence sels. This framework can be used to model attackers in computer networks, instigators of offensive content into recommender systems, or manipulators of financial markets. Our key contribution the development of fully decentralized resilient upper confidence bound (UCB) algorithm that fuses information mixing step among agents with truncation of inconsistent and extreme values. This truncation step enables us to establish that the performance of each normal agent is no worse than the classic single-agent UCB1 algorithm in terms regret, and more importantly, the cumulative regret of all normal agents is strictly better than the non-coopens non-cooperative case, provided that each agent has least 3f + neighbors where f is the maximum possible Byzantine agents in each agent's 's neighborhood. Extensions to time-varying neighbor graphs, and minimax lower bounds further established the achievable regret. Experiments corroborate the merits of this framework in practice.
1 Introduction
In multi-armed bandits (MAB) [attimore & Szepesvári 2020), one is faced with the task of selecting a series of arms so as to accumulate the most reward in the long-term when rewards are incrementally revealed. The canonical performance measure is regret, which quantifics the difference in the cumulative return associated with one's chosen actions as compared with the best-in-hindsight up to some fixed time-horizon T. For the frequentist setting, that is, distributional model is hypothesized underlying the reward sampling process, both lower and upper bounds on the asymptotic regret exist (Lai & Robbins 1985). ) Upper confidence-bound
(UCB) selection method was proposed in Auer et al. (2002a) which achieves O(log T') regret.
In this work, we focus on cooperative multi-agent extensions this setting (Landgren et al., 2016 where each node a directed graph now receives a distinct reward sequence and needs to select own scries of arms. Cooperative MAB has received significant attention in recent years, where agents compute locally weighted averages of their agents' arm index parameters, i.e., they execute consensus (Jadbabaie et. al. 2003

---

Published in Transactions on Machine Learning Research (08/2024)
Olfati-Saber et al.
Numerous works have studied this problem class in recent years for the case that agents reward distributions are homogeneous (Landgren et al. 2016 Landgrena et al. 2021 Martínez-
2007
et al. 2019
Zhu et al. 2021 Chawla et al. 2020). as well as Lai et al. 2008 Liu & Zhao 2010 Szorenyi
cc al.
2013 Kalathil et al. 2014 Bistritz & Leshem 2018 Sankararaman et al. 2019 Wang et al., 2020
Dubey & Pentland 2020; Shi & Shen 2021] Madhushani & Leonard, 2020a
Martínez-Rubio et al. 2019)
extensions to models of "collision" (Nayar et al.]
2018 Liu & Zhao 2010 Bistritz Leshem 2018 Lai
et al.] 2008) and federated information structures SShi & Shen 2021 Shi
al.)
2021] Zhu et al.
2021
Dubey & Pentland 2020 et al., 2020; Réda et al.)
2022). Most pertinent to this work consensus- based
decentralized UCB-type methods [Landgren et al. 2016 Landgrena et al. 2021 Martinez-Rubio et al. 2019
Zhu et al. 2021 Zhu & Liu 2023). It is worth noting that in such a homogeneous setting, each agent in
a multi-agent network can independently learn an optimal arm using any conventional single-agent UCB
algorithm, ignoring any information received from other agents. With a careful design, decentralized multi- agent multi-armed bandits can outperform centralized single-agent upper confidence bound algorithms ZZhu
& Liu 2021 2024).
However, it is overly narrow to consider that all agents cooperate, many learning processes have mixture of cooperative and competitive agents, and it is not always clear to delincate between them (Littman 1994
Basar & Olsder 1998). To encapsulate this dynamic, we consider that an unknown subset of agents are "Byzantine" (Lamport et al. 1982), i.e., they chose their index parameters and selects arms in an arbitrary manner and can send conflicting values to different agents. The cooperative MAB in the presence of Byzantine
agents setting has intrinsic motivation in computer networks (Xiong & Jamicson 2013 Ferdowsi et al. 2019). recommender systems (Sankararaman al. 2019), and economies (Misra et al. 2019), to name a few, as model of how these systems should optimize performance in the presence of uncertainty in their incentives. In particular, cooperation can respectively model filesharing, collective interest around topic, market stability metrics. Moreover, the concept of Byzantine agents naturally emerges when some participants seek to derail the goal of the collective, as in denial of service attacks, injection of offensive content into social media, or market manipulation. To date, however, the majority of works that study MAB in the cooperative multi-agent setting do not. allow for any agents to be non-cooperative, leading to a learning process being inoperable in the presence of malefactors. Therefore, in this work, we pose the following question:
Can decentralzedd multi-armed bandit algorithms outperform the classic single-agent counterpart even in the presence of Byzantine agents?
In this work, we provide an affirmative answer to this question. Therefore, contributions are to:
pose the multi-armed bandit problem in the multi-agent setting in the presence of Byzantine agents;
derive a filtering step on the parameters exchanged by agents that thresholds extreme values, which guarantees consistency in the construction of confidence sets and helps limit the deleterious impact of the Byzantine agents by yielding accurate reward mean estimates, As a result, we construct a Byzantine- resilient variant of decentralized UCB framework;
establish that the regret performance of this method no worse than logarithmic regret bound of its single-agent counterpart (which is not true of MAB methods even in the Byzantino-free case (Landgren] et al. 2016 Landgrena et al. 2021 Martinez-Rubie et al. 2019 ) and is better than the non-cooperative counterpart in terms of network total regret when each agent has at least 3f+1 + neighbors, where f is an
upper-bound on the number of Byzantine agents that is commonly assumed known in resilient learning
(Gupta et al. 2021 Gupta & Vaidya 2021 Kaheni et al.) 2022 Liu et al. 2021b Gupta et al.) 2023
Notably, we do not require global knowledge of the network connectivity, as in Vial et al. 2021 2022
experimentally demonstrate that the proposed methodology achieves lower regret compared with single- agent (non-cooperative) UCB, meaning that the sum is more than the component parts. The constructed setting is representative of model of recommender systems, where advertising firms may share data to improve reliability of their targeted ads.
A detailed review of related work can be found in Appendix B
2

---

Published in Transactions on Machine Learning Research (08/2024)
2 Multi-agent Multi-armed Bandits
Consider a multi-agent network consisting of N > 1 agents, which may be mathematically formalized as a directed graph C = (V,&) with V = NI, Each vertex i corresponds to an agent and each directed edge (or arc) defines connectivity amongst. neighbors. To be more precise, we say agent j is a neighbor of agent i if (j,t) is an are in E, and similarly, agent & is an out-neighbor of agent i if (i, k) E E. Each agent may receive information only from its neighbors with an inward bound arc, meaning that the directions of ares represent the directions of information flow. We use Mr and N to respect denote the neighbor set and out-neighbor set of agent i, ie., Mr [j fje V: (i,z) E E} and N, [K V: (i,k) E}.
All agents face the same set of M > 1 arms (or options) denoted as M = fI.....Mf, time t E {0, ,.).., ,T, agent i E V must select an arm (t E M from the M options. If agent i selects an arm E M, it will receive a random reward (t). For any i E V and & E M, {Xxx(t))T_o is an unknown independent and identically distributed (i..d.) stochastic process. For each arm k E M, all its reward variables over the network (t),t), E V share the same mean ak while their distributions may be different. Without loss of generality, we assume that all (t), E V,V, k E M have bounded support [0, 1] and that μ1 2 μ2 2 ... 2 UM, which implics that arm 1 has the largest reward mcan and thus is always optimal option.
My.
At each discrete
There exist agents in the network which are able to transmit arbitrary values to their out-neighbors and capable of sending conflicting values to different neighbors strategically, which we refer to as Byzantine agents (Fischer al., 1986). The set of Byzantine agents is denoted by F and the set of normal (non-Ryzantine) agents is denoted by H. whereby V = H U F. Which agents are Byzantine is unknown however, we assume that each agent has at most Byzantine neighbors, and knows the number f. Knowing the number f can be viewed as limitation of this work, though it is a widely adopted assumption in the existing Byzantine-resilien algorithms in the literature.
normal agents;
The canonical performance measure in the multi-agent MAB setting may be formalized through the concept of regret among the non- non-Byzantine agents. That is, each normal agent seeks to select its sequence of arms {a,(t)?² so as to minimize its contribution to a network-wide cumulative regret
T
=(T)= =
(T) = Σ TH Σ E
(1)
IH
IEH
where the sum is over all non- non-Byzantinc agents though in the presence of Byzantine agents. Morcover, (T) quantifies the difference in the cumulative return Σ E E[X,.(o] as compared with the best-in-hindsiggt up to horizon T,, which by our assumption on the ordering of μa, is simply TM1
In the case when each agent does not have any neighbors, the aforementioned resilient multi-agent multi- armed bandit problem reduces to the conventional single-agent multi-armed bandit problem for each normal agent. It is well known that cach normal agent can appeal to the classic UCB1 algorithm and achiove an Olog T) regret (Auer et al., (2022a). Subsequently, we develop a Byzantine-resileen decentralized multi-agent UCB1 algorithm which guarantees that all normal agents collectively outperform the scenario had they each adopted the classic single-agent UCB1 algorithm. Before continuing, we introduce example to clarify the problem setting.
Example 1 (Recommender Systems) In personalized recommender systems web services (Sankarara- man et al. ) an application interface is charged with the task of presenting one of several advertising options to end-user, and receives reward any time the selection receives click. This trooh (CTR) paradigm of recommendation systems is standard. However, one challenge with obtaining good per- formance in this sctting is that there are many more options than arm pulls. Therefore, there is incentive for one advertising firm to exchange information with another in order to gain a better understanding of CTR (Elena et al., 2021). In this case, one may pose the resulting ad targeting problem as a multi-agent MAB problem. Here, the existence of Byzantine agents may come by the presence of firms that seck to introduce offensive or divisive content into web services for non-cconomic incentives (Hinds et al. 2020). This issue has occurred several times in the past. decade.
3

---

Published in Transactions on Machine Learning Research (08/2024)
Example 2 (Computer Networks) In this setting, each agent in the network is device or computer (Xiong & Jamieson 2013 Ferdowsi et al. 2019), the arm selection specifies non-local node in the network as a candidate which a data packet could be sent, meaning that the arm set is a subset of the node set. Reward is the outcome of a simple syuchromizz--ccknowlllde protocol (Syn-Ack), which is a binary indicator of whether a data packet was successfully received. The collaborative multi-agent aspect of this problem permits one to allow uploads within a Local Arca Network (LAN), as in file-sharig protocols. It is natural to consider that a random subset of nodes could be Byzantine in this context, as malicious code or devices may attempt to deny the regular operation of network. In this case, their presence would model a Distributed Denial of Service (DDOS) attack, or other similar cyber-attacks - see Gollmann (2010).
Example 3 (Financial Markets) Suppose a central treasury of a national government wants to stabilize its country's financial market. In this case, the arm pulled is an interest rate on treasury bonds which are typically held by large financial intuitions. The reward is the rate of increase/decreass in inflation, or another indicator of national economie health (such as labor force partieipation rale). In this context, there is an incentive to cooperate with the treasuries of other governments in order to achieve increased economic stability [Benigno & Benigno 2002). The presence of Byzantine agents in this context manifests because not all governing bodics are interested in the economic stability of another. Indeed, in the presence of a geopolitical rival, decreasing economic performance may motivate communicating spurious or incorrect information to others (Macekura, 2020).
With the setting clarified, next we introduce our main algorithmic framework based upon UCB.
3 Byzantine-Resillen Resilient Collaborative UCB
To present algorithm, we first need to introduce some notation. For cach i V and & E M, use ne,((() to denole the nunber of times agent i has selected arm k prior to time L. Moreover, denote (t,a(() as sample mcan of arm & reward tracked by i at time t, i.c., (t) (., 1 Et [((a ()),,(r), where (()) is the indicator function which is if the event in its argument is true and 0 otherwise.
We propose a protocol such that each agent E V transmits two scalars for each arm E M to all its out- neighbors: (t,x(t) and (t). Due to the existence of Byzantine agents, we use (iy,(t) and (ty, k e M to denote the possibly contaminated number of arm pulls and reward mean-estimates agent i transmits to its out-ncighbor j. If agent i is normal, (t)) nt,x(t) and Fzj,k (t) = (t) for all & E M and j E N,. If agent i is Byzantine, Mija()) (1) and Tzj,(()) may be arbitrary for all k E ...
Before formalizing the procedure, we describe the key concepts behind its execution. The main idea is to use UCB as the pocision-maaing policy. The key point of departure compared with singlo-agent UCB or non- Byzantine multi-agent UCB is that we have a filtering process to dewn- the effect of Byzantine agents. Recall that our goal is to design an algorithm that achieves full resilience and ensures no worse performance than the single-agent (non-cooperative) UCB. To this end, we construct reward mcan estimate (t) to be more accurate than the sample mean (t,,(t) (the corresponding reward mean estimate in single-agent UCB). For resilient bandit, there are two factors that can affect the accuracy of (f): (i) the consistency of sample counts of agents in the neighborhood and (ii) the role of Byzantine agents.
(i) Consistency Filter. While UCB provides an effective solution for exploration in the single-agent case, the multi-agent case mandates that each agent not only explores each arm sufficiently itself but also requires certain local "consisteney" conditions, i.e., the number of times an arm has previously been pulled is sufficient to construct valid confidence set. To address this, method to encourage a version of persistent exploration by forcing agents to select an insufficiently-esploree arm if its corresponding sample count falls too much behind the network maximal sample count has been developed (Zhu & Liu 2021). The upshot of this adjusted exploration scheme is that it can be shown to satisfy said consistency condition. However, it is inoperable in the Byzantine setting due to potentially spurious information. To alleviate this issue, we propose threshold-consiitennny consistensi,, which instcad of actively balancing the sample counts over the network, directly thresholds the number of neighbors an agent may employ to update the reward mean estimate by removing all the neighbors that have not explored sufficiently compared with itself. To be more precise, agents
4

---

Published in Transactions on Machine Learning Research (08/2024)
may ensure local consistency in their confidence sets through proper re-weighting of standard deviation in terms of (t, neighbors that are considered post-winnowing In particular, we introduce truncation parameter K4, which parameterizes the "consistency level" (addressing issue (i)). If K2 is too large, then the consistency is insufficient, see equation 19 if R2 is set to be too small, then the restriction omits too many agents to obtain valid reward mean estimates. This tension may be formalized by restricting viable range as S K4 < 2. For effect on regret for different H2 E 2), see Figures and 2
(ii) Trimmed Mean. To achieve the mullification of Byzantine effect, further propose winnowing procedure the reward mean-estinates in terms of an upper-bound on the number of Byzantine agents (addressing issue (ii)). That this is necessary may be observed by noting that even with the restricted construction of confidence sets, reward information from neighbors can be arbitrarily wrong. Therefore, no concentration bound may be employed to limit its impact. In this sense, to achieve resilience, normal agents need to negate the Byzantine effect, which may be achieved through the trimmedd-mean. This procodure, similar hard-threshol sone-thresholding, truncates the reccived sample mcans from other agents by omitting the f largest. and ʃ smallest values. This technique has found success in related resilient multi-agent. consensus methods (Vaidya et al. 2012 Leblance et al. 2013 Saldaña et al. 2017 Saulnier et al. 2017). Through re- re-parameterization (Lemma and the threshold consistency previously mentioned, we can establish that the reward mean estimate is actually superior to its single-agent counterpart. It is worth emphasizing that the trimmed-mean idea has to be incorporated with a suitably chosen consensus variable for resilient reward mean estimation; see Remark 2 and Example 4 in the Appendix.
With these elements properly motivated, we are ready to present the main algorithm for decentralized UCB with Byzantine agents.
Algorithm 1: Filter(i, t): Consistency and trimmed mean filters of agent i on arm k at time
Input: agent i, Ki, arm k time /
Set (tx(t)= N,
for j N,; do
if KeMli, (I) < (l) then Remove from (t)
// Comsistency-Fitter
end
end
Sct (t) = (t)
if
Ar,((1)] < 2 then
(t) = (t)
else
Set (1) (i,
12
Sort (t) in descending order for j (f, and removes the indices corresponding to the f largest and ff smallest values from (t)
13
// Trimmed-Mean
14
Set (t) = (t)
(1) (3. (1) ESEB., (t))
16 end
Initialization: At initial time 0, each normal agent i H samples each arm k exactly once and then (0) = and (0) (0).
Between clock times and t 1, with t E 10. T), each normal agent e H. performs the steps enumerated below in the order indicated.
Agent i transmits the possibly contaminated number of arm pulls (1y,(()) and reward mean- estimate (t), M to each its nut-neigh j e NN and meanwhile receives nigak (t) and (t). à E M from each of its neighbors h E N,
Transmitting:
Filtering: Agent performs two steps to possibly filter out the malefactors in its neighbor set No-
5

---

Published in Transactions on Machine Learning Research (08/2024)
Step A [Consistency Filter]: For each arm & E M, agent filters out those neighbors' indices j from Ne for which (1) < (t,)()), where E (1, is constant, and sets the remaining index set as Ai,a i.e,
A.x(t) (j E konju(tt 2 (t))
Step B [Trimmed Mean Filter]: For each arm & M, if [t,xtt) 2f, agent filters out those neighbors indices h from (t) whose (t),((t) are the f largest and ff smallest among (j, J E A,,(tt,, with ties broken arbitrarily, and then sets the remaining index set as (t), otherwise agent i sets (.,(t) = 0. To be more precise, let π be any non-decreasing permutation of Ai, (1) for which (x(0)((1)) & Fx(++1)((() for all (A....,,A,,x()))) 1}. Then,
0, (A,( s
(ix(()) (FFana(() :f:00))))))))) f+1 (A,x(0) - f}, else.
(2)
Decision Making: Agent calculates its current estimate of reward mean μu for each arm M as
1
(t) + Σ Ena(t))
(t) (t) +
(3)
(EB,,(())
and based upon this information, computes its exploration bonus (derived from Hoeffding in Lemma 3 the Appendix) from each arm k as
291, (t) logt
(lt,))((t)
(i,,)())
where the variance term is defined in terms of the proportion of arm pulls remaining post-filtering [t),
1, if (i,x(1) 0,
(t,x(t)=
Ki Ki
(4)
(() + (t), + 1)2
else.
4
Then, the at(t + 1) that maximizes the Byzantine-filtreed upper-confidence bound for agent i at time + is selected
a;(l+ + = arg max (z),e(() +
KEM
Updating: Agent updates its variables
(t + 1) = ne,a(() +1
k = a;(1 + 1),
(t.
if k + a:(t + 1),
H+1
(t + + (1 +
Σ =))x())))Xxx()))
7=0
These steps summarized as Algorithm in the Appendix.
Remark 1 (Communication Cost) Each agent to broadcast two variables: one real number and one integer for each arm at each time step. The communication cost is comparable to many existing decentralized cooperative MAB algorithms (Landgren et al. 2016 Landgrena al. 2021 Zhu & Liu 2021 A simple way to reduce the communication cost of Algorithm is to allow agents to pick subset of neighbors with which to communicate. Observe from Theorem 3 that no network connectivity requirement. is needed to ensure performance comparable to the single-agent counterpart. Using communication epochs with a fixed constant length is an alternative approach (Martínez-Rubil each agent only communicates and makes arm decisions at the start of the epoch, and keeps selecting the until the end of the phase. Doing so yields larger constant in the regret analysis of Theorem ?
al.) 2019 Dubey & Pentland] (2020)), where

---

Published in Transactions on Machine Learning Research (08/2024)
Remark 2 (On the insufficiency of consensus and its variants) Consider related algorithms under "full arm observability" setting in Landgren et al. (2016); Landgrena et al. 2022 Martinez- Rubio et al. (2019); Zhu & Liu (2021): each agent explores the entire arm set and then decides which arm to select. In this setting, agents arm selection strategies exhibit incompatibility with Byzantine filtering such as the Lrimmed-mean method. These methods build upon the consensus protocol, which incorporates the weighted average of neighbors' reward mean estimates in the previous step with reward information at current step in the updating of the reward mean estimate. For the non-Byzantine setting, such a technique propagates information over the network and ensures the reward mean estimate tends towards consistency time pro- gresses. In the presence of Byzantine agents, if one employs a running consensus on 2i,x (t), it forms one component of & (f- + 1), which causes each step to accumulate the bias from the previous (which can be shown in equation 9in Lemma D]. We note that the trimmed mean does not directly cancel out the Byzantine effect, that is, 24,a (t) can still be biased. Algorithm [ achieves resilience in that when (t, + 1) is updated, (t) is not used. Then, the bias of (t,((t) due to Byzantine agents does not accumulate across time. Thus, as normal agents have increasingly more accurale sample means as they accumulate samples, the potential effect of Byzantine attacks shrinks, eventuating in the bias converging to mull. Detailed discussion can be found in Appendix
4 Sublinear Regret in Presence of Byzantine Agents
This section presents our key theoretical results, which establish the sublinear regret of the algorithm pre- sented above. We begin with lower and upper bounds of each normal agent's regret.
Theorem (Lower Bound) The expected cumulative regret of any normal agent i e H. satisfies
(T) log T
2 o max (I.V. - 21,1
-
lim inf T-000
Observe from the above theorem that when a normal agent has at least 2 + 1 neighbors, the lower bound on its regret is actually better than the single-agent. UCB1 algorithm (Auer et al.) 2002a).. We clarify the
form of this gap next. To do so, denote as A e #l 14 the gap between the largest mean and the mean for each arm M.
Theorem (Upper Bound) The expected cumulative regret of any normal agent E H satísfies
(t)
+ (1+ 3 =²) Ass + + - -T)AM
(2(T) < min rE(L....f?
Σ
max (E(1.....T)
Ab
A+
(g)n logt (1
x² }
Σ
max (E(I.....T)
D&
(5)
A
k: A,
Note that the regret upper bound in Theorem 2 depends on (t) whose definition equation 4 is influenced by Bi, (() and Kg. The construction of set (() in equation 2 implies that, in general, larger ʃ and a smaller [N,] correspond to larger regret bound. The influence of on (i, () is not monotone; see Figures and its discussion in (i) Consistency Filter in the preceding section. The following results are the performance comparisons with the single-agent (non-cooperative) UCB1 (Auer et al. 2002a Theorem 1), 8log A
where the upper bound of cach agent's 's regret was establised as Ek: A,20
+ (1 ),))
Theorem (Per-agent Outperformance) The regret upper bound for each normal agent E H. is always no worse than that of the single-agent UCB1, i.e.,
8logT
x² (1+
-3) 1 )
(T(T) < Σ
A
k:
A,20
7

---

Published in Transactions on Machine Learning Research (08/2024)
Note that Theorems 1 do not rely on any graphical conditions like connectivity and local degrees, which is a departure from prior results (Vial et al. 2021 2022 Mitra et al., 2022). The following theorem shows that if certain local degree condition is satisfied, all the normal agents can collectively outperform the non- cooperative case, which is still independent of global connectivity.
Theorem 4 (Network Outperformance) If each agent has at least 3f+1 neighhors, then the cumulaaive regret upper bound of all normal agents is strictly better than that of the non-cooperativee counterpert:
8log A
R(T) = Σ R((T) < [Hl
E R: AE>0
+
(6)
SEH
The comparison of the above results with the existing literature can be found in Appendix the above theorems are given Appendix F Here we provide a sketch of the proofs.
The proofs of
Sketch of Proofs: To show the two outperformance results in Theorem 3 and Theorem we first detail
To begin with, we estimate the value of (()),((T)) each agent's s regret satisfies (T) ER:A >0 (T)) Towards this end, we first follow the logic flow of the standard single-agent UCB1 algorithm (Auer et al. 2002a] Proof of Theorem 1), which makes use of the
the regret upper bound in Theorem 2
makingg step in equation 11 and turns the problem into estimating the concentration bounds of the reward mean estimate equation 13 That is where we depart from the single-agent analysis, as we have a more complicated design of the reward mcan estimate. We proceed by dividing the analysis into two cases based on the number of neighbors retained after the filtering steps to estimate the concentration bound, which utilizes the Hoeffding's inequality (Temma 3/. To make Hoeffding's inequality apply; there are important. steps: we slice the random sample count to all possible values (see e.g., equation 14), the other is using Lemma 2 to restrict the Byzantine behavior with the help of Trimmed Mean Filter (Step B). In addition, to obtain a tight concentration bound, we make use of the local exploration consislency assured by Consistency Filter (Step A) in the computation of Hoeffding's inequality, see equation 16 In this way, our analysis contains fundamental steps that are not present in prior analyses of UCB, and addresses fundamental challenges associated with the Byzantine effect. Therefore, we can obtain equation 5 which implies Theorem B by showing the adjusted variance (ef. equation 4 (t) I 1 for all E H. M and t = 1,.... T. Then, it suffices to show there exists at least one agent have strictly better performance each arm at each time for Theorem 4
4.1 Time-varying Random Graphs
This subsection extends theoretical results to the cases when neighbor graph G(t) changes over time. Define (i(t) as NT((() (t) as the corresponding neighbor set and out-neighbor set of agent i at time t. Replacing M and N by NG(t) and N,- (t), respectively, in Algorithm 2 yields a Byzantine-resiliet decentralized bandit algorithm for time-varying graphs. Specifically, the results of per-agent regret stated in Theorems hold with exactly the same analyses. This is because when we estimate the reward mean estimate 24,k (t), we only make use of (t) where j E (tt),, which one-time local information, and thus its consequences do not rely on graph topology variation over time. Formal definitions regarding time-varying graphs are provided in Appendix(D) [D] The following theorem shows that Algorithm 2 possesses collective outperformance over the non-coopee case for time- sine-varying random graphs, provided a probabilistic local degree condition is satisfied.
still
Theorem (Network Outperformance) Tf the probability that every agent in the network has at least 3 + 1 neighbors is E [0, at each time then the network total regret upper bound is strictly better than the non-cooperative counterpart, i.e., equation 0 holds.
We note that this is the first. sublinear regret result for MAB in the decentralized setting in the presence of Byzantine ageants, to the best of our knowledge.
Remark 3 From the proof of Theorem 4 in Appendix F the outperformance over the single-agent counter- part over fixed graphs when the 3 degree requirement is logarithmic, i.e., we have a smaller coefficient
8

---

Published in Transactions on Machine Learning Research (08/2024)
350
300
agent 2 (c=11)
300
agent 3 (c=1.3)
agent (c=1,5)
250
kar1.3
k=1.5
average regret
250
non-cooperstive
agent (c=1.8)
average regret
200
1=r1.8
con-cooperaaive
200
150
150
100
100
50
50
0
2000
4000
6000
8000
10000
0
2000
4000
6000
8000
10000
time
time
Figure 1: Per-agent regret for each normal agent with helerogeneous Ki
Network averaged regret for normal agents with homogeneous k
Figure 2:
of the log T term. The same holds for Theorem with p because the analysis for Theorem can be directly applied to this case. Yet for random graphs with E (0, 1), the outperformance is of order O(1) from the proof of Theorem
5 Numerical Evaluation
We conduct experiments - additional studies are in Appendix G We consider four-arm bandit problem whose arm distributions are Bernoulli with mean 0.5, 0.45, 0.4, 0.3, respectively. The Byzantine agent broad- casts 0.4, 0.5, 0.4, 0.3 as the corresponding reward information of the four arms to all the normal agents, and sample count n (t)) = (t) to all normal agents j with being randomly selected in {2,3, 4, 5). can be shown in Appendix E that the same or similar Byzantine policy sufficient to make the existing decentralized bandit algorithms not suitable to find optimal arm. The graph in our experiments follows random structure where the probability each directed edge is activated is common value g. The total time T is set as T = 10000. Figure present sample means and standard shaded deviations over 50 runs.
We first conduct two simulations to illustrate the effect of agent network with only agent being Byzantine over a random graph generated with = 0.8. Figure [ shows the comparison of per-agent. regret of each normal agent i with a different K; and the non-cooperative counterpart (Auer et al.] (002a)) and Figure / presents the network total performance of all normal agents when they use same together with the non-cooperative counterpart (Auer et al. 2002a). Observe that our algorithm outperforms the non-cooperative counterpart in terms of both the network regret and the individual regret of each normal agent, which corroborates Theorems 3 and 4 Moreover, it appears that the +f+1 1 degree requirement (which requires the graph to be complete for a five-agent network) is not necessary for superior performance in practice. In addition, the regret does not appear to be monotone in terms of R;: which is consistent. with the discussion of K2 in Section
consssseecy parameter under a five-
We next test the network performance over ten-agent network with two Byzantine agents study the effect of 9, which is related to the expected degree of the network. The simulation result over fixed graph is shown in Figure 3 For time-varying graphs, note that when q == 1, the graphs are (fixed) complete graphs, there is relationship between and the probability of the degree requirement is (") (") (1- - The simulation result is shown in Fig- ure Observe that larger results in better performance. Moreover, the normal agents' performance using Algorithm is no worse than that of the singlc-agent counterpart, even with a small q, which substantiates Theorem 3 However, although for time-varying random graphs, Theorem holds a positive result in terms of comparison with the non-cooperative counterpart for all p & experimentally we see that in some
and when 0 < q
met, which is defined in Theorem 5
9

---

Published in Transactions on Machine Learning Research (08/2024)
300
300
q=1
q=1
250
q=0.9
250
q=0.9
q=0.5
q=0,5
average regret
200
q=0.2
non-cooperative
average regret
200
q=0.2
non-cooperative
150
150
100
100
50
50
0
2000
4000
6000
8000
10000
0
0
2000
4000
6000
8000
10000
time
time
Figure Network avcraged regret for normal agents under fixed random graphs with various val- ues of q
Figure 4: Network averaged regret for normal
agents under time-varying random graphs with various values of q
350
350
N-15
300
300
250
250
average regret
200
200
average
150
150
100
100
50
50
0
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
time
time
Network averaged regret for normal agents with various values of N
Figure
Network averaged regret for normal agents with various values of
Figure
cases our algorithm returns worse performance in experiments, illuminating a possibly cleory-practicn gap. Furthermore, unlike the fixed graph setting, the regret appears to be not decreasing in terms of q.
We then compare the algorithm performance of multi-agent networks with distinct network size N or the number of Byzantine agents f. Consider neighbor graphs, which are random graphs with a common q 0.8, and set all K; to a common value of 1.3. We first fix f 2 and test the performance the agents for =010, 10, 15, 20 respectively; the simulation results are shown in Figure 5. Then, we N and test the performance the agents for f 2, respectively, as illustrated Figure It can be seen that the regret increases with and decreases with N. Since, in a random graph scenario, the average average/expected /expected number of agent's neighbors increases with N, these observations consistent with the theoretical results discussed immediately after Theorem 2
Finally, we compare the actual regret with the theoretical upper bound. We set K; to a uniform value of 1.3, = 10, f = 2, and q 0.8; the simulation results are presented Figure Although there appears to be a nontrivial gap between the regret upper bound and the actual regret observed with our algorithm, this not surprising. Our algorithm is a decentralized multi-agent generalization of the single-agent UCB1 algorithm, which exhibits similar performance. The gap likely arises because the theoretical analysis considers the
10

---

Published in Transactions on Machine Learning Research (08/2024)
3000
2500
averaged value
2000
1500
1000
regret
our upper bound
sinlle-agent regret
500
single agent upper bound
0
2000
4000
6000
8000
10000
time
Figure 7: Network averaged regret v.s. network averaged regret upper bound
"worst-case" performance, which rarely occurs in practice and is difficult to identify and evaluate due to the complex statistical processes involved.
6 Conclusion
We considered cooperative multi-armed bandit problems in the presence of Byzantine agents. To solve this problem, developed consensus-type information mixing strategy that operates in tandem with filtering scheme that contains two stages: limit the number of possible neighbors with which to exchange information, and threshold extreme values of the reward mean estimate. The result achieves regret that is certifiably better than an individual agent. Numerical experiments demonstrate the merits of this approach in practice. Limitations of this framework include: (1) it is not yet capable incorporating contextual information into arm selection, (2) the obtained regret upper bound not monotone with respect to fi; requiring extra effort to tune this parameter, and (3) there is potential gap between theoretical and practical results in the time-varying random graphs scenario.
Acknowledgments
J. Zhu is currently with Zhejiang Lab and was previously affiliated with the Department of Applied Mathe- matics and Statistics at Stony Brook University. The majority of the work was completed while J. Zhu was at Stony Brook University. The work of J. Liu was supported by the National Science Foundation under Grant No. 2230101.
Disclaimer
This paper was propared for informational purposes in part by the Artificial Intelligence Rescarch group of JP Morgan Chase & Co and its affiliates ("JP Morgan"), and is not a product of the Research Department of JP Morgan. JP Morgan makes no representation and warranty whatsoever and disclaims all liability, for the completeness, accuracy or reliability of the information contained herein. This document not intended as investment research or investment advice, or a rocommendation, offer or solicitation for the purchasc sale of any security, financial instrument, financial product service, the merits of participating in any transaction, and shall not constitute solicitation under any jurisdiction or to any person, if such solicitation under such jurisdiction or to such person would be unlawful.
be used in any way for evaluating
References
D. Alistarh, Z. Allen-Zin Zhu, and Li. Byzantine stochastic gradient descent. In Advances in Neural Infor- mation Processing Systems, volume 31, 2018.
11

---

Published in Transactions on Machine Learning Research (08/2024)
J.-Y. Audibert and S. Bubeck. Minimax policies for adversarial and stochastic bandits. In Proceedings of the 22nd Annual Conference on Learning Theory, pp- 217-226, 2009.
P. Auer and C.-K. Chiang, An algorithm with nearly optimal pseudo-regret for both stochastic and adversar- ial bandits. In Proceedings of the 29th Arnual Conference on Learning Theory, volume of Proceedings of Machine Learning Research, pp. 116-120, 2016.
P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-288 256, 2002a.
P. Auer, N. Cesa- Bianchi,, Y. Freund, and R.E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 77, 2002b.
T. Başar and G.J. Olsder. Dynomic Noncooperative Game Theory, SIAM, 1998.
M. Bayati, N. Hamidi, R. Johari, and K. Khosravi. Unreasonable effectiveness of greedy algorithms in multi- armed bandit with many arms. In Advances in Neural Information Processing Systems, volume 33, pp. 1713 1723, 2020.
G. Benigno and P. Benigno. Implementing monetary cooperation through inflation targeting. SSRN, 2002. Available at SSRN:
I. Bistritz and A. Leshem. Distributed multi-player bandits - game of thrones approach. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 7222 7232, 2018.
P. Blanchard, E.M. El Mhamdi, R. Guerraoui, and J. Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems, volume 30, 2017.
S. Bubeck and N. Cesa-Bianche Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
R. Chawla, A. Sankararaman, A. Ganesh, and S. Shakkottai. multi-agent bandits. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 3471 3481, 2020.
The gossiping insert-eliminate algorithm for
L. Chen, H. Wang, Z. Charles, and D. Papailiopoulos. DRACO: Byzantino-resllent distributed training via redundant gradients. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Reseorch, pp. 903 008-9112 2018.
Y. Chen, L. Su, and J. Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2): Article No. 44, 2017.
Y. Chen, X. Zhang, K. Zhang, M. Wang, and X. Zhu. Byzantine-robust online and offline distributed reinforcement learning. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 3230-3269, 2023.
A. Dubey and A. Pentland. Diffcrentially-priaan federated Conference on Neural Information Processing Systems, 2020.
lincar bandits. In Proceedings of the 34th
A. Dubey and A. Pentland. Private and Byzantine- proof cooperative decision-making Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pp. 357-365, 2022.
G. Flena, K. Milos, and T. Eugene. Survey of multiarmed bandit algorithms applied to recommendation systems. International Journal of Open Information Technologies, 9(4):12 27, 2021.
X. Fan, Y. Ma, Z. Dai, W. Jing, C. Tan, and B.K.H. Low. Fault-tolerant federated reinforcement learning with theoretical guarantee. In Advances in Neural Information Processing Systems, volume 34, pp. 1007- 1021, 2021.
12

---

Published in Transactions on Machine Learning Research (08/2024)
C. Fang, Z. Yang, and W.U. Bajwa. BRIDGE: Byzantino-reslient decentralized gradient descent. 1EEE Transactions on Signal and Information Processing over Networks, 8:610-626, 2022.
A. Ferdowsi, S. Ali, W. Saad, and N.B. Mandayam. Cyber-physical security and safely of autonomous connected vehicles: Optimal control meets multi-armed bandit learning. IEEE Transactions on Commu- nications, (1100):7228-724 7244, 2019.
M.J. Fischer, N.A. Lynch, and M. Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1:26-39, 1986.
D. Gollmann. Computer security. Wiley Interdisciplinary Reviews: Computational Statistics, 2(5):544- -544, 2010.
Z. Guan, K. Ji, D.J. Bucci Jr., T.Y. Hu, J. Palombo, M. Liston, and Y. Liang. Robust stochastic bandit algorithms under probabilistic unbounded adversarial attack. Proceedings of the AAAI Conference on Artificial Intelligence, 34(4):4036-400) 2020.
N. Gupta and N.H. Vaidya. Byzantine fault-tolerance in pecr-to-pect distributed gradient-descent. arXiv, 2021. 7XXi:2101.12316 [cs.
N. Gupta, T.T. Doan, and N.H. Vaidya. Byzantine fault-tolerance in decentralized oplimization under 2f-redundancy. Tn Proceedings of the 2021 American Control Conference, pp. 222-3,37, 2021.
N. Gupta, T.T. Doan, and N. Vaidya. Byzantine fault-tolerance in federated local SGD under 2f- 2f-redundancy. IEEE Transactions on Control of Network Systems, 10(4):1669- 1081,, 2023.
L. He, S.P. Karimireddy, and M. Jaggi. Byzantine-robust decentralized learning via self-centered clipping. arxiv, 2022. arXiv:2202.01545 [cs.LG].
J. Hinds, E.J. Williams, and A.N. Joinson. "It wouldn't happen me"; Privacy concerns and perspectives following the Cambridge Analytica scandal. International Journal of Human- Computrr Studies, 143: 102498, 2020.
W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30 1963.
Jadbabaie, J. Lin, and A.S. Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. JEEE Transactions on Automatic Control, 48(6):988- 2003.
A. Jadbabaic, H. Li, J. Qian, and Y. Tian. Byzantinc-robust foderated linear bandits. In Proceedings of the 61st IEEE Conference on Decision and Control, pp. 5206 5213, 2022.
K.S. Jun, L. Li, Y. Ma, and J. Zhu. Adversarial attacks on stochastic bandits. In Advances in Newral Information Processing Systems, volume 31, 2018.
M. Kaheni, E. Usai, and M. Franceschelli. Resilient constrained optimization in multi-agent systems with improved guarantee on approximation bounds. IEEE Control Systems Letters, 6:2659-266 2022.
D. Kalathil, N. Nayyar, and R. Jain. Decentralized learning for multiplayer multiarmed bandits. IEEE Transactions on Information Theory, 60(4):2331 2334233553,, 2014.
K. Kuwaranancharoen, L. Xin, and S. Sundaram. Byzantine-resileet distributed optimization of multi- dimensional functions. In Proceedings of the 2020 American Control Conference, pp. 4399-4404, 2020.
J. Kwon, Y. Efroni, C. Caramanis, and S. Mannor. Coordinated attacks against contextual bandits: Funda- mental limits and defense mechanisms. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 11772-11789, 2022.
L. Lai, H. Jiang, and H.V. Poor. Medium access cognitive radio networks: A competitive multi-armed bandit framework. In Proceedings of the 42nd Asilomar Conference on Signals, Systems and Computers, pp. 98 182, 2008.
13

---

Published in Transactions on Machine Learning Research (08/2024)
T.L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules, Advances in Applied Mathemat- ies, 6(1):4-22, 22, 1985.
L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382-40) 1982.
P. Landgren, V. Srivastava, and N.E. Leonard. On distributed cooperative decision-making in multiarmed bandits. In Proceedings of the 2016 European Control Conference, pp. 243 243-248, 2016.
P. Landgrena, V. Srivastavab, and N.E. Leonarda. Distributed cooperative decision making in multi-agent multi-armed bandits. Automatica, 125:109445, 2021.
T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
H.J. Leblance, H. Zhang, X. Koutsoukos, and S. Sundaram. Resilient asymptotic consensus in robust networks. IEEE Journal on Selected Areas in Communications, 31(4):766 781, 2013.
T. Li, L. Song, and C. Fragouli. Federated recommendation system via differential privacy. In Proceedings of the 2020 IEEE International Symposium on Information Theory, pp. 2592 2597, 2020.
M.L. Littman. Markov games as a framework for multi-agent reinforcement learning. In W.W. Cohen and H. Hirsh (eds.), Machine Learning Proceedings 1994, pp- 157 163. Morgan Kaufmann, 1994.
F. Liu and N. Shroff. Data, poisoning attacks stochastic bandits. In Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Reseorch, pp. 4042 4050, 2019.
J. Liu, S. Li, and D. Li. Cooperative stochastic multi-agent multi-armed bandits robust to adversarial corruptions. arxiv, 2021a. arXiv:2106.04207 [cs.LG].
Liu and Q Zhao. Distributed learning in multi-armed bandit with multiple players. IEFE Transactions on Signal Processing, 58(11):56677 5681, 2010.
S. Liu, N. Gupta, and N.H. Vaidya. Approximate Byzantine fault-tolerance in distributed optimization. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pp. 379 389, 2021b.
S.J. Macekura. The Mismeasure of Progress: Economic Growth and Its Critics. University of Chicago Press, 2020.
T. Madhushani and N.E. Leonard. A dynamic observation strategy for multi-agent multi-armed bandit problem. In Proceedings of the 2020 European Control Conference, pp. 1677 1682, 2020a.
U. Madhushani and N.E. Lconard. Hoterogencous exploro-cxploit strategics on multi-star networks. JEEE Control Systems Lellers, 5(5):1603 1608, 2020b.
C. Madhushani, A. Dubey, N. Leonard, and A. Pentland. One more stop towards reality: Cooperative bandits with imperfect communication. In Advances in Newral Information Processing Syslems, volume 34, pp. 7813-7824, 2021.
D. Rubio, V. Kanade, and P. Rebeschini. Decentralized cooperative stochastic bandits. In Pro- ceedings of the 33rd Conference on Neural Information Processing Systems, pp. 4531-4542, 2019.
K. Misra, F.M. Schwartz, and J. Abernethy. Dynamic online pricing with incomplete information using multiarmed bandit experiments. Marketing Science, 382))222-- 2019.
A. Mitra, A. Adibi, G.J. Pappas, and H. Hassani. Collaborative linear bandits with adversarial agents: Near-optimal regret bounds. In Advances in Neural Information Processing Systems, volume 35, pp. 22602-2261 2022.
N. Nayyar, D. Kalathil, and R. Jain. On regret-optinal learning in decentralized plati-player multi-armir bandits. IEEE Transactions on Control of Network Systems, 5(1):597-66) 6606, 2018.
14

---

Published in Transactions on Machine Learning Research (08/2024)
R. Olfati-Saber, J.A. Fax, and R.M. Murray. Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE, 95(1):215-233 223, 2007.
C. Réda, S. Vakili, and E. Kaufmann. Near-optimal collaborative learning in bandits. In Advances in Newral Information Processing Systems, volume 35, pp. 14183-1411 2022.
D. Saldaña, A. Prorok, S. Sundaram, M.F.M. Campos, and V. Kumar. Resilient consensus for time-varying networks of dynamic agents. In Proceedings of the 2017 American Control Conference, pp. 252 258, 2017.
A. Sankararaman, A. Ganesh, and Shakkottai. Social learning in multi agent multi armed bandits. Proceedings of the ACM on Mensurement and Analysis of Computing Systems, 3(3):1335, 2019.
K. Saulnier, D. Saldaña, A. Prorok, G.J. Pappas, and V. Kumar. Resilient flocking for mobile robot teams. IEEE Robotics and Automation Letters, 2(2):1039 1046, 2017.
C. Shi and C. Shen. Federated multi-armed bandits. Proceedings of the AAAT Conference on Artificial Intelligence, 35(11):9603 9611, 2021.
C. Shi, C. Shen, and J. Yang. Federated multi-armed bandits with personalization. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2917 2925, 2021.
A. Slivkins. Contextual bandits with similarity information. In Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pp. 679-702 2011.
L. Su and N.H. Vaidya. Pault-tolerant multi-agent optimization: Optimal iterative distributed algorithms. In Proceedings of the 2016 ACM Symposium Principles of Distributed Computing, pp. 425-434, 2016.
L. Su and N.H. Vaidya. Byzintine-resllent multiagent optimization. IEEE Transactions on Automatic Control, 66(5)22227 2232-2233, 2020.
L. Su and J. Xu. Securing distributed gradient descent in high dimensional statistical learning. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(1):Article No. 12, 2019.
S. Sundaram and B. Gharesifard. Distributed optimization under adversarial nodes. JEEE Transactions on Automatic Control, 64(3):1063-1000 1076, 2018.
B. Szorenyi, R. Busa- Fekete I. Hegedus, R. Ormándi, M. Jelasity, and B. Kégl. Gossip-based distributed stochastic bandit algorithms. In Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 19-27, 2013.
N.H. Vaidya, L. Tseng, and G. Liang. Iterative approximate Byzantine consensus in arbitrary directed graphs. In Proceedings of the ACM Symposium on Principles of Distribuled Computing, pp. 365 374, 2012.
D. Vial, S. Shakkottai, and R. Srikant. Robust multi-agent multi-armed bandits. In Proceedingss of the 22nd International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pp. 161-170, 2021.
D. Vial, S. Shakkottai, and R. Srikant. Robust multi-agent bandits over undirected graphs. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(3):1-57, 2022.
A. Wang, Z. Qin, L. Zheng, D. Li, and L. Gao. Distributed robust bandits with efficient communication. IEEE Transactions on Network Science and Engineering, 10(3):1586 1598, 2022a.
Н. Wang, Н. Xu, and Н. Wang. When are linear stochastic bandits attackable? In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research. pp. 23254 23273, 2022b.
Y. Wang, J. Hu, X. Chen, and L. Wang. Distributed bandit learning: Near-optimal regret with efficient communication. In Proceedings of the 8th International Conference Learning Representations, 2020.
15

---

Published in Transactions on Machine Learning Research (08/2024)
Z. Wu, T. Chen, and Q. Ling. Byzantine-reslient decentralized stochastic optimization with robust aggre- gation rules. IEEE Transaclions on Signal Processing, 71:3179-1 1199-195, 2023.
J. Xiong and K. Jamieson. SecureArray: Improving wifi security with fine-gre ane-grained physical-layer information. In Proceedings of the 19th Annual International Conference on Mobile Computing and Networking, pp. 441-452 2013.
Z. Yang and W.U. Bajwa. ByRDiE: Byzantinc-resilient distributed coordinate descent for decentralized learning. IEEE Transactions on Signal and Information Processing over Networks, 5(4):611 627, 2019.
Z. Yang, A. Gang, and W.U. Bajwa. Adversary-resllien distributed and decentralized statistical inference and machine learning: An overview of recent advances under the Byzantine threat model. IEEE Signal Processing Magazine, 37(3):146-1558 2020.
C. Zhao, J. He, and Q-G. Wang. Resilient distributed optimization algorithm against adversarial attacks. IEEE Transactions on Automatic Control, 65(1))43308 4315, 2020.
J. Zhu and Liu. Distributed multi-armed bandit over arbitrary undirected graphs. In Proceedings of the 60th IEEE Conference on Decision and Control, pp. 6976-6981, 2021.
J. Zhu and J. Liu. Distributed multi-armed bandits. IEEE Transactions on Automatic Control, 68((): 3025 3040, 2023. Special Issue on Learning for Control.
J. Zhu and J. Liu. Decentralized multi-armed bandit can outperform classic upper confidence bound: homogeneous case over strongly connected graphs. In Proceedings of the 63rd IEEE Conference Decision and Control, 2024. to appear.
Z. Zhu, J. Zhu, J. Liu, and Liu. Federated bandit: A gossiping approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1)cArticl 2, 2021.
A Pseudocode
Algorithm 2: Resilient Decentralized UCB
Input: G,T,s, Initialization Each agent samples each arm exactly once. Initialize =0, = (i, = (o,,(0), m4,((0) = (0) =
for t t= 0....... T do
for k = ,,..,,M .M do Agent runs Filter (i, k) end
a:(t + 1) = arg max (t) + C(t, (t)()))
// decision making
7
(t,x(t+ 1) = (t), Ak E [M]
(t Ri,0,(141)(1
((+1)())) (t)+1 +1
// information updating
Ti,ill + (++1(++)) Σit1
10
Agent sends (t +1) (t) and (t) = (t,, Ak [M] to E N
11
Agent receives (t), (t), Ak E [M] from j N
// information propagation
12
end
B
Related Work
Resilience in multi-agent optimization dates at least back to Su & Vaidya (2016). Many prior works in this formalize tradeoffs between resilience and accuracy (Kuwaranancharoen et al. 2020 Yang & Bajwa
16

---

Published in Transactions on Machine Learning Research (08/2024)
2019
Fang et al. 2022 He et al. 2022 Wu et al. 2023 Su & Vaidya 2016 Sundaram & Gharesifard 2018 Su
& Vaidya 2020 Zhao et al. 2020), i.e., the limit point exhibits bias with respect to the optimizer dependent on the extent of adversarial manipulation. To refine this dependence, assumptions that there is "objective function rodundancy" have been considered (Gupta et al. 2021 Gupta & Vaidya 2021 Kahoni et al. 2022)
for the special case of a complete graph. Extensions to tree graphs (lederated setting) have also been studied
[Luu et al. 2021b Gupta et al., 2023). Significant attention has been paid to designing Byzantine-resliint
variants of stochastic gradient iteration (Chen al. 2017 Blanchard et al. 2017 Alistarh et al. 2018
Su
& Xu
2019 Chen et al. 2018 see Yang et al. (2020) for review.
Designing resilient bandit algorithms may be traced back to a singlo-agent setting in Auer et al. where an EXP3 with (vvT) regret was established. Follow-on work (Bbbeck & Besa-Bianchi, 2012 Audibert
2002b)
& Bubeck 2009 Auer & Chiang 2016) refined the regret constants. Subsequent work (Jun et al. 2018:
Liu & Shroff] 2019) established that with Oloo T) attack cost, UCB and greedy algorithms can suffer lincar
regret O Guan ct al. (2020) established that a Olog T) regret can be achieved under certain assumption
reward distributions with median-based Lechnique. Subsequent extensions of adversarial models to
contextual bandits have been studied Slivkins (2011); Wang et al. (2022b); Kwon et al. (2022). In recent
years, Byzantine robust reinforcement learning for federated sctting is also developed Chen et al. (2023)
Jadbabaie et al. 2002); Fan et al. 2021
Most similar to the setting studied here are models of adversarial manipulation of MAB methods in the
multi-agent setting. Dubey & Pentland (2022) discussed a Byzantine setting where at each time agents observe a true reward with probability 1 and observes a reward from an unknown but fixed distribution with probability c. Madhushani et al. (2021) Wang et al. 20022a) Liu et al. (2021a] considered
adaptive Byzantine corruption where any reward when transmitted can be corrupted the adversary. The setting we study is similar to Vial et al. (2021 2022): : Mitra et al. (2022). Mitra et al. (2022) is specialized for
linear bandit problems and it discussed a solution methodology that requires centralization, whereas Vial ct al. 2021 2022) partition the set of arms into distinct subsets that are assigned among the agents. To achieve robustness, a connected and undirected normal network required, in contrast to our setting. These methods mandate that the proportion of Byzantine agents relative to normal agents is sufficiently small, in order to outperform single-agent bandit method. In particular, (Vial et al., 2022 Theorem 2) contains the possibility that performance can be worse than the single-agent counterpart, and always exhibits degradation in regret bound under our arm aligning setting which is widely considered in multi-armed bandits literature
(e.g. Landgren et al. (2016); Landgrena et al. (2021); Martínez-Ruut et al. (2019); Zhu et al. (2021); Zhu
& Liu (2021)) ). A more rigorous contrast of the regret results in these works may be found in the succoeding section.
C Comparison With Existing Literature
C.1 Comparison with decentralized stochastic bandit algorithms
In the context of decentralized algorithms within stochastic bandit setting, as described in prior works such as Landgren et al. (2016): Landgrenaa et al. (2021] ; Martínez-Rubio et al. (2019): Zhu et al. (2021): ZZu & Liu (2021), it is observed that most of these algorithms impose specific network connectivity requirements even in the absence of Byzantine attacks. Furthermore, the majority of these algorithms do not guarantee superior individual performance compared to their non-cooperative counterparts, with the exception of [Zuu & Liu (2021}. In contrast, our proposed algorithm eliminates the need for any wetwork connectivity prerequisites while ensuring individual performance that is at least as good as that of the non-cooperative counterpart.
C.2 Comparison with resilient algorithms
In this subsection, we give a detailed comparison with the existing resilient bandit a algorithms Mitra el al. (2022;g Vial et al. 2021 2022). which are under the similar Byzantine setting with ours.
In the work of Mitra et al. 2022). the authors investigate a robust linear bandit problem within the context of federated learning. This scenario necessitates the presence of central server capable of managing all
17

---

Published in Transactions on Machine Learning Research (08/2024)
the communications. The study presents regret bound of O(VT), and this regret can be further improved when the proportion of Byzantine agents decreases or when the overall number of agents increases. Tn contrast, our algorithm is designed for a decentralized communication scenario, which is more versatile in terms of the types of communication graphs it can accommodate. It is worth noting that considering the lederated setting effectively implies an assumption that the underlying communication graph takes on either a complete graph or a star graph configuration, with the central node (or root) being consistently reliable. These configurations are considered special because they entail the presence of at least one normal agent capable of establishing communication with all other agents. Consequently, the methodology proposed by Mitra et al. (202)) finds limited applicability in our context. Nevertheless, like Mitra et al. (2022) our algorithr also affords agents the opportunity to enhance their performance in response to specific changes in the network structure. As detailed in Equation equation 5 each normal agent generally experiences a lower regret when it possesses a larger number of neighbors or when f decreases. This property is also explained in the subsoquent paragraph following Theorem 2 Furthermore,
the overlapping sccnario analyzod in both Mitra et al. (2022) and our paper, where agents engage in pefeerated/eentralllll
communication to address stochastic bandit problem, our algorithm achieves superior asymptotic regret bound. Specifically, the regret bound in Mitra et al. (0022) is at least O(VT), which is higher than our regret bound of Olog T).
In the work of Vial et al. 20021 2022). the authors explore scenario where each agent is exclusively responsible for exploring a subset of arms. While this setting may initially appear to encompass a more generalized arm alignment setup compared to ours, it imposes a requirement for a connected and undirected network among normal agents within the communication graph. This particular requirement diminishes its practicality from a design perspective. Furthermore, if examine the specific case where both papers allow each agent to explore the entire set of arms, it becomes evident that both Vial et al. 2021 and Vial et al. (2022) present regret bounds that are inferior to those of the non-cooperalive counterparts. To elaborate, both (Vial et al. 2021] Theorem 2) and (Vial et al. 2022 Theorem 2) reveal that the coefficient associated with the log T term in their respective regret upper bounds is given by Σk 4a with a parameter a strictly greater than 2. In contrast, the single-agent UCB algorithm achieves coefficient of Σk., A. for the same term. Consoquently, becomes evident that the algorithms proposed by VVal al. (2021 2022) fail to surpass the performance of the classic single-agent counterpart within the studied setting.
A
D Time-varying Graphs
Theorem 6 (Lower Bound) For ony lome-vorying neighbor gruph sequence (G()), the expecled cunnula- time regret of any normal agent i E H satisfies
(T)
o(
lim inf T-
mmxx/ (axi - 2f 2f +111)
logT
Theorem (Upper Bound) For any time-varying neighbor graph sequence {G(t)), the expected cumula- tive regret of any normal agent i E H satisfies
Σ A
(t) (EE(I....T)
(1+ x² ))²))a))
Ab) + (T +(T-T)AN
RT(T) < min rE(L....T)
max
+
As
k:
(g), logt (E(.....TT
22 (1+ )
Σ
max
+
A
k: >
Theorem 8 (Per-agent Outperformance) For any time-varying neighbor graph sequence (G(t)), the regret upper bound for each normal agent i E H. is always no worse than that of the single-agent UCB1, i.e.,
(T( < Σ
8 log
+ -1+ 3 AM)
A
A: A+>0
The above three theorems can be proved using the same argument as in the proofs of Theorems I respectively.
18

---

Published in Transactions on Machine Learning Research (08/2024)
E Counterexample
In this appendix, we will take the updating policy in Zhu & Liu (022) as an example to show that using running consensus, commonly used updating policy in the literature, cannot nullify the Byzantine effect even with a filtering process, rather, it makes the reward mean estimate inaccurate.
We begin with introducing the algorithm in Zhu & Liu 2021 Denote the reward mcan estimate as (t), which is updated as follows:
1 [Wll JEN.
2 (t+
E Eza(t) (t -x,,a(t)
(7)
where (t) denotes the sample mean, i.e.
Σ ((a(())= (+) (t, (4, ==0
Initial (0) is set equal to (0). We omit the decision-making process studied Zhu Liu (2021)
here. This is because, as we will show later discussions, under the resilient sctting, using such an updating
policy at agent cannot even ensure an accurate ε (I). Thus, regardless of the decision-making policy, the algorithm results in linearly escalating regret.
Under the resilient setting studied in this paper, for a fair comparison, we add a trimmed-mean filtering process before equation 7 to enable the algorithm to handle certain Byzantine effects. Let Eij,+ (1) = Z (t) if E H. and be an arbitrary value if F. At each time step, each agent E H transmits x.,((t) to each of out-neighbors j E N,; and simultancously receives (t), from cach of neighbors h E N;; the agent then sorts all received εx,, h E Mr descending order and filters out the largest and the smallest f values. Let Mi, (4) be the retained neighbor set of agent i after filtering at time t. Then, agent updates its reward mean estimate (t) as
2, (t +
Σ Ega(()) F.. +) -), (t)-
(t) jEM..(()
Here equation g serves as the modificd updating policy in Zhu & Liu 2021 under the resilient bandit sctting. We will show in the following example that it results in E(2,, - pkl being always bounded below by a strictly positive constant for any (t,)()) E (I,...,t). This fact implies that the reward mean estimate is always biased. With biased reward mean estimate, no matter what the decision-maiie making policy is, normal agents can never find optimal arm.
Example 4 Consider a 4-agent complete graph, with agent I being Byzantine agent and agents 2-4 being normal agents. Let one arm ho be of Bernoulli distribution with mean }. At each time, agent 1 sends 3 to all three normal agents as its reward mean estimate on arm k.
Lemma 1
With Example there holds [E)),,(()) puo 2 1 for any i (2,3,4) and / L (1,2....).
Proof of Lemma 1 Since the neighbor graph is complete and (t) for all (2,3, 4), it is easy see that
(t)) (t) = (t)).
Take agent 2 as an example, at each time t, it receives three pieces of reward information and only retains one of them for update. Let p(t) be the probability that agent retains the Byzantine value at time Then, we have
1
2 (ot() + (E(),,(tt) 2
1 1/1
E ((E (t)) ) (1 -P(())
E( + 1)) - ((2x (t)) + -
2
= (1
p(()
B (()),((1)) + (0(()
1
2
19

---

Published in Transactions on Machine Learning Research (08/2024)
If ((2,,((t) $ 3: then there holds
1 (1 (1-1()
p())
2 1))
3
3
and if (t)) > then
p(t)
p(t)
E( + & (()),((t))
+
(t))
3 2
6
Together we have
(t + S max (B(EL((t)), 1
3)
(9)
Now consider O. It is easy to see that E (0)) E(X,,((O)) for i E (2,3, 4) and that p(0) Thus,
11
(()),x(1)) 24'
Then, from equation 9 obtain that for any t fl....; T)
11
E (()) - 24'
since 146- 1, (t), -4cl 2 21. which completes the proof.
The above Example 4 can be straightforwardly generalized to any size complete graphs using similar argu- ments to those in the proof of Lemma
Proposition 1 Consider an n-agent complete neighbor graph with f agents being Byzantine. Set one arm k 's reward to be of Bernoulli distribution with mean P* and let all f Byzantine agents always transmil a contant. value 0& * pek to their out-neighbors at each time. If n 2 4 and f S [" then [E(2,,((1) - pal is uniformly bounded below by strictly positive constant for all normal agent and time t.
Proposition I shows that running consensus can lead to biased reward mean estimates. With a biased reward mean, normal agents will possibly misidentify an optimal arm, and as a result, no matter what decision- making policy normal agents use, may yield a linear regret. We will run experiments in Appendix G to visually demonstrate this result; see Figure and its discussion.
F Analysis
This section provides the analysis of the algorithm and proofs the main results in the paper.
Lemma 2 1f (t) > 2f, then (t, in equation can be expressed as convex combination of ii, and all (y, j E At, n H in that
(t) w.i.k(1)T,,
Σ (1)
(10)
JEAH,
where (t) and (t) non-negative numbers satisfying wa,((t) + ΣjENSnN Wijn (t) 1, and there exists a positive constant (t)(t)) = (0)++ such that for all i E H and t, (t) 2 mT,((t) and among all Wig.((t) k (nt(t) H. at least (t) of them are bounded below by (t)/2.
Proof of Lemma 2 From definition, (t) nFI means the number of Byzantine agents being retained by agent for arm i after the two filtering steps. From Trimmed Mean Filter, having (t) Byzantine agents being retained indicates that there are [B,x (FF normal agents who retained after Consistency
20

---

Published in Transactions on Machine Learning Research (08/2024)
Filter are filtered out in Trimmed Mean Filter due to having small sample mean and [B.x(t) (t) n n.F are filtered out due to having& large sample mean. In this sense, for any j E (t) F,, there exists distinct pair of normal agent j j.j E (t,(t)) \ x (t) n H, such that Ij ,x(t) S Ty,x(t) S ( Then, (t,((t) can be expressed as a convex combination ž-- (t) and Zyt (t), i.., there exists a Л,, such that
(1) = B5 (1) + 8,)
Then, equation 3 can be rewritten as
(t) = [BA(t))+ +1 (i,((t++ +
E
(n)((t) +
E (3y3, lltt + (1 (1-11111))) (B33))331100 (())) jEBr,(0)r
hEBralt)nn
Since (1) n H c (t)(1) n H and jー E (rx(() n H for all j E (1) n F, the above equation is exactly in the form of equation I0 Besides, for each j E (t) F,, at least one of B, and B are lower bounded by 1 2' Then, the number of (iy,((t) that are lower bounded by 2(BB,(0)+1)) is at least (B),(() n H (t) n FI = (t),, which completes the proof.
Lemma 3 (Hoeffding's inequality (Hoeffding 1963 Theorem 2)) If XI...., X, are independent random
variables and a, S X, S by for = 1, I,..., let X E Xt and be the expectation of X; then for any <> O, it holds that
2n²6
P(X
exp
Di=1 (b: a,)²
Now we are a position to prove the theorems.
Proof of Theorem 1 The lower bound for single-agent algorithm 2(log T) (Lai & Robbins 1985 Theorem 1). For all network structure, complete graph leads to best performance each agent has full knowledge of the reward information over the network. For each agent, this is equivalent to single-agent setting where it selects one arm and receives N pieces of reward information at cach time instance. From Filtering step B, at least 2f pieces of information are filtered out if B,, (1) is nonemply. This is to say, each agent at most retains max[[N] - 2f, 0} neighbors after the whole filtering process and thus is able to make use of at most max{[VV - -f, pieces reward information in the updates, which leads to a lower bound of order Q( ([N:) 2/+1,1])
Proof of Thcorem 2: Since (T(T) EE E(n (T)) we can convert the problem into finding an
estimate of E(n,,((T)) Let
(t log t
L
max
IE(1...,,T)
A
for any E H. if (T) 2 I., let 44 S T be the time such that na,e(ti) L2 then have
T
ni,((T) = L+ Σ
[(a = = k).
t=
Based on this fact, we obtain that
T (T) ++ Σ (aa = k, nt 1)) L).
1=1
Since (t 1) & (f), we immediately obtain from the above inequality that
T ((a k. m.) 2 L).
n4, (T) <
21

---

Published in Transactions on Machine Learning Research (08/2024)
from the decision-makee making step, if agent i selects arm & at time t, then 21,((t + ((t) 21,(t) + C(I, (t)) Thus,
T (T) S I 1 (1,A(t) + C(e, m()(t)) 2 (t) + C(I, (()) (z,(())))))))))))))))))))))))) 2 I.).
Σ
Since for any t E {l....,T} T), we have 1 1 (t) & t for all i E H and &o E M, considoring all possible values of ni, (1) and ns,1 (1) for a given t in the above inequality, we obtain that
T (T) S
Σ t=1
(ELA(1) c(I, =1,(1) ma,,)aa()))
M N1=1
me,(1)) = No: n4,1 n1, = No1.
(11)
Applying the expectation operation on both sides of the above inequality, it holds that
T
E(),a(T)) SL
Σ
Σ
Σ
P (L)(()) + ((L, 2 (1) + (()),,,
I=
Na=L Nn=1
(1) = No. (4,1 Na
T
S
Σ
P (1 - ph 2 C(I, n4 (1)), (s,,(1))))) = Nit))
Niz= Na=1
P( =1,(1) 2 C(I, n., (1)) (1) = No1)
P(2C(1, ni, (()) μr M4) n4,((t) Not)
(12)
It easy to verify that when n1,((1) L, for any & E (l,..., T3, it always holds true that 2C(1, n4, (t)) pi Pk, which is to say,
P(2C(t, (()) 2 P1 pk), (t) Nia) 0.
Substituting the result to equation
we obtain that
E(n,,x (T)) +
Σ
P(z.)(t) - pA C(t, m.,(()) = Nw)
t=1 Nu Nu=1
+ P(m (t) > mi. (1). ((a))
(13)
The two probabilities in equation 13 can be viewed concentration bounds of the reward mean estimates. Without loss of generality, we only provide detailed estimation for (t) 2 ((t,), nu,(()= = Na) in the following context, the analysis for P( (1) > C(t, ne, ((), (t) Na) is exactly the same. And to this end, we need to consider the following two cases based on the number of neighbors that are retained after two filters.
Case A: If (1) is empty, then (1) = (t), and the decision-making is exactly the same as that of lingleagentt UCB1 in Auer et al. (2002a). From the analysis in (Auer et al. 2002a Theorem 1), it holds that
((),,(()) - 14: 2 C(I, (i,x nz,a = -Na)
No= Na=1
+ +(( 21, 2 C(t, n4,1 (t), =Na)
2
22

---

Published in Transactions on Machine Learning Research (08/2024)
Case B: If (t) is nonempty, let (t, Ar,((t) n HUU {i}. from Lemma 2 convex combination of the sample mean of agents in Ar, (4). Then,
can write (1, as the
P ((zu((t) pA 2 C(I, m(),maa()) ma,)) Nak)
P
Σ (()aa()zaa(()) pa 2 Ctt, (t,(()) Noe (EAL,E()
From Consistoncy Filter, for any j E (t)(t), we have kmzz((t) 2 ni,k ni,x((), consider all possible values of Rz (1) for j (1,(1), we obtain that
((Z)((1) pe 2 ((,,))(())) (ix(() Naa)
Σ
Σ
P
Σ (t,,A(t)z,,((t) - Pa 2 C(t))t(t)),
Kik 2 m
Nok
jEAL.())
n3,x(() = N₁, for all j E Aual)):
(14)
where fi,... : are the labels of all the agents in (t, n H. Let C(t) be the collection of (N5x : j e (t)3 such that Nik 2 Nu//k, , for all j (t). Then,
((t μk 2 ml, (,,x m,)) Na) S max C(O)
(i) pi C(I, C(l.ma,(()): N₁x for all Asa(1)) jEA,.
Let (s) denote the averaged reward of agent i on arm for fixed sampling times it is clear that (ix(()) for all i E H are independent. In this sense, we have
((),a(1) 1s 2 C(I, (1) No.)
Σ w.j,((tX pa 2 Ni)
I max P c(t)
jEA
Then, using Lemma
3
(t
((=,((1)= 1.h ((),)))(0s = -Nx) S max exp
(15)
C(t)
(Wijk (t))² 2N,z
Since N₁u 2 Na/Ka for all j E Ai,((t) n H. we have
((z,((1)) pok 2 ((), (ix(() =Na)
(t, Na.
< exp
((wua(tt)) + KK ESEA, (w)
(16)
From Lemma 2 at least [1) of (i),(() for j E Ai,(!!) n H are lower bounded by ni. (1)/2 and that (t)x(t) + E (t).x(t) 1. Thus,
(wH,k(t)2 + Σ (t))
JOA
< (),a(()) Ne ((1 (1))22)))/2) + (1 m),(() - ((B.x(0) - 1),,{(()/22))
(t.((t) 2) (()
< (1) + ma
(17)
23

---

Published in Transactions on Machine Learning Research (08/2024)
Substituting equation 17 to equation 16
obtain that
((2.a(tt) - M4 2 C(t, ne.,((t)), = Nak) - +
Similarly,
P( (t) 2 C(t. na,(t)), (z,)) = NN1) 1
t².
Then, combining the above two inequalities together,
Σ Σ
(((E)(()= - - 2 Ci,, (,, ni,x Nu))
Na=L Na=1
+ +P( 21, 2 Ctt, ni,1 mz,) = Na)
2
Combining the results of both Case A and Case B with equation
13
we obtain that
2
x²
(T) L+
L +
(18)
t2
3
and further
(gi,u((t logt T +) +)
RT(T) Σ (())x(T))&a <
Σ
max (E())m))))
+
Ak
k:AS00
It is easy to see that 7 = 1,.... T, it holds that
R₂(T) S R.(T) (T T) max Ak:
REM
where RT( denotes the expected cumulative regret at time T, and -T- max As is the maximal reward loss gained after r by keeping selecting the arm with the lowest reward mean. In this sense, we can obtain the following tighter upper bound for the reward mean estimate,
RT(T) < min (E,.....TT)
(R)(T) +T T) max A&)
REM
Σ
Sgi, log (1+
72 m.
AB +(T +T -T)AMM
< min (E.......T)
max (1.......
Ak
3
k: AE
which completes the proof as maxKEM AS = AM-
Proof of Thcorem 3 We only need show for any E (1,..., T), E H and & E M, it holds that (1) 1. Consider the case when (l) nonempty, i.e., [B(,(()] 1. Then,
(1 = (t)) + 3x. (1) + 2x; + A( (?) 1)2
K; + [La(0]++ (1)
4
K; +1
1
(19)
Note that (t) when (t) is empty. We thus can conclude that g.. (t) S 1, which completes the proof.
Proof of Theorem We only need to show that for any t >> 0 and M, there exists agent i (t) such that its regret at time f is strictly lower than that of the single-agent case, i.e.
(1)
Σ
8log
AB (1
72
Ax
2020
24

---

Published in Transactions on Machine Learning Research (08/2024)
and to this end, from Theorem 2 only need to show that (iv(t),A (t) < 1.
For any & E M, let (t) = arg mi ni, (t). From the algorithm, agent (t) does not filter out any normal neighbor in Filtering Step A, as for all j E Na n H it holds that k,ng,((t) 2 nj,a(t) 2 n,,(()). Then, agent (t) at most filter out f (Byzantine) agents at time t in Filtering Step A. As a result, there holds (A)()))(())) 2f and thus (B(()) 2 1. Then, from equation 19
9sa(0.&(() <1
From Theorem we have (i) & for all i H. Then, it holds for any > 0 that
Σ gt, < [H].
(20)
iEH
From Theorem
2 R(T) satisfies
(1) (E(1.....7)
+ (15 + +1))
R(T) S
max
D
A.s0
8 EiEH Ri. (t) log
+ 1 +1)1711ss)
max [E(L....TT
AB
3
k: A230
Then, using equation 20 there holds
8logt t
x2 + +1)da
R(T) |71|
Σ
max [E(I.....T)
A
A450
|7
Σ
8logT A
+
(
+ +1)Aa)
3
l: A,50
which completes the proof.
Proof of Theorem 5: From Theorem
the network total regret R(T) satisfies
8 EiEH (1 logt
( + +1)1N11A).
R(T) S Σ
(21)
(E(I.....T)
As
A+>0
From equation
19 when the 3f + 1 degree requirement is satisfied at time t for any t= = I,..,,
Σ (1) < [H),
SEW
and when is not satisfied, we have a weaker result
(t) $ [7].
We discuss in the following analysis all the possibilities of the "last" time that the 3f + degree requirement is not satisfied. If the last time that the degree requirement is not met is T, then (T) = 1 and we have
Σ (t) |H log T.
LE (E.......77
iEH
From the random graph structure, this situation happens with probability 1 - p. If the last time that the degree requirement is not met is 1, then we have
max (E(1 (e(1.....')
Σ (t) & max log - 1), Σ
Ds.k (T)
iEH
25

---

Published in Transactions on Machine Learning Research (08/2024)
and this happens with probability (1 p)p. Continuing this process, If the last time that the degree require-
ment is not met is T - T, where 0 T < T, then we have
E (t,
(E(.....
iCH
|H|] log(T r), Σ
logt for t T T)
max
iEH
and this happens with probability (1-p)p² And if the degree requirement is always met, then
(t) logt for t = 1, I....,T T).
(inn(t)oogt & max
Σ
MIX
LEH
NEH
and this happens with probability p². For OS let
h(r, T) = max {
[L
Σ
(1) for t= T + 1, I....,,
iCH
Then, from equation 21
8 8 p)p" B(h(T, T)) + 8p" E("(ETTTTTT)
n² (s +1))
R(T) S
Σ
(22)
A
A420
Since from the proof of Thcorem 3
H(T,T) max
Σ
logt for t = 1, I.....,T
T
max logt = H log T, 10 (I...TT.TT
iEH
NE
and h(,,T) S [7|] Tog for 0 SSTST 1, then using equation 22
R(T) < Σ
p)p= + 8p"
H7| log T + +1)
Ak
t: A
8log
(T++1)
H7
Σ A.>0
A
The right hand side is the network lotal regret bound of the non-cooperative counterpart. Thus, we conclude that our regret bound is always strictly better than the non-cooperative counterpart. Moreover, let (T) be the difference in upper bound between the two algorithms, i.e.,
(8HH T
Ef p)p" B(h(T. T)) + 8p B(b(T,T))
T(T)=
Σ
AB
Ab
k: A420
Ii=1(1 p)p² (lH
E(h(T, T))) + p log E(h(T,T))
Σ
A
A+>0
Since for any 7 ,,..., we have
E(h(T, = max [P 1og(max((1,TT -1)), Σ 9i.k (t) logt for 1 1 T - T +,,.. .Tt,....77) .......)
> E( H (10g -})) |7[ (max 1
26

---

Published in Transactions on Machine Learning Research (08/2024)
substituting it to the definition of (T), we obtain that
E - plp log
T T-r + p" log T
(TT) S 8/H|
Σ
4
An: Ax30
<1== +
IT/2 5T
T T-r + +p" log / (1 (1-p)p" log
-8/1 H|
A
:: A0
DT/3 (1-p)p" log 2+ ET=T/2+1 (1 - p)p" log T + p" log
I 8 8
D
:: Ax
plog2 + (1-11))))
f)p (1-p)p log T/2 + p² log
I 8|
Σ
A
An Ax30
since for E (0, 1), both (1- p)p p)p T and p" log T are of order o(1), we conclude that +(7) S 0(1)
which completes the proof.
G Additional Simulations
We begin with the simulation with the same arm setting and Byzantine policy as in Section 5 to further validate the theoretical results. For all simulations in this section, the total time T is chosen to be 10000, and the figures are the averaged result 50 runs.
We first consider a ten-agent network with two of the agents being Byzantine. The graphs change over time but always satisfies that f 1. We consider two cases: (1) Each normal agent has at least 4 = 3f neighbors and the average number of neighbor of each normal agent equals 4.5. (2) Each directed edge is activated with common probability q = 1/2. For both cases, the average in-degree for each normal agent equals 4.5. The simulation result for the two-case comparison is given in Figure S Observe that the performance of the two cases differs significantly dcspite having a same average in-degrce for cach normal agent. This is because case (1) guarantees the 3/ + degree requirement be satisfied al each time whereas case (2) does not. This observation consistent with Remark 3
Next we consider a ten-agent complete network with one agent being Byzantine. Since the updating processes in Landgrenaa et al. (2021); Landgren et al. (2016); Martínez-Rann Rubio et al. (2019) are alike, only take Landgrena et al. (2021) as an example. We compare the performance of our algorithm with Zhu & Liu (2021) with a trimmed mean filter (denoted as Algorithm 3 in Figure 9] and Landgrena et al. (2021) with a trimmed mean filter (denoted as Algorithm 4 in Figure 9 For Zhu & Liu (2021). we use the same Byzantine policy as ours, and for for Landgrena et al. (2021). the Byzantine agent follows similar rule: it sets [0.4, 0.5. 0.4, 0.3) as r information for each arm, randomly copics one normal neighbor's â, and sets $ = á r. and then broadcasts these variables to its neighbors. The definition of r, f, 8 can be found in Landgrena et al. (2021). The simulation result is shown in Figure g It is clearly shown that the algorithms in Zhu & Liu 2021 Landgrena et al. (2021) are not resilient even with Byzantine filter and over a complete graph, as their corresponding regret curves appear to be linear, this observation is consistent with Lemma [
G.1 Application in Recommender Systems
In this appendix, we consider the application in the recommender systems, where advertising firm is charged with the task of presenting type of advertisement to user. If the user clicks the ad, the firm reccives as reward, and 0-reward otherwise. Each user has individual preference and thus has different probabilities to make a click on different types of ads. Consider that len advertising firms are seeking to present the optimal option to a user over twenty different types of ads. Each firm has connections with some others so that they can cooperate with each other for better performance. The connections form an undirected graph shown in Figure I0 with the white nodes representing for the firms that transmit honest information, and the grey nodes representing for the "evil" firms that transmit misleading information for
27

---

Published in Transactions on Machine Learning Research (08/2024)
300
000
case
resilient UCB
case non-Gooperative
non cooppraaaee
250
Algorithm
Algorithm 3
600
average regret
200
000
100
50
100
0
2000
4000
6000
8000
10000
1000
2000
5000
7000
time
Figure 8: Simulation result of the average regret of normal agents
Figure 9: Simulation result of the average regret of normal agents
700
Gaussian attack
adeptive attack
600
non-cooperative
500
average regret
400
300
200
100
2000
4000
6000
8000
10000
time
Figure 11: Simulation result the average regret of normal agents
Figure 10: Connections of the ten firms
malicious competition. The honest firms perceive that something is amiss but cannot identify the adversarial firms they decide to defend with resilient decision-making. For the adversarial firms, we consider the following two Byzantine attack models.
Gaussian Attack:
Let each adversarial firm i randomly generate a bias value 8L, (0, 1) for each arm For each neighbor j and time 6, generates a ct)t) from N(2, 0.01 and truncates (t,((t) + (t) to the range [0, 1], then transmits the value to its neighbors. For sample count information at time I, let each adversarial firm copy nt 1) from a neighbor j.
Adaptive Attack:
Here we assume the vdvessarial firms literally know everything, e.g., the informa- tion, the communication actívities and even the Byzantineddfending algorithm. This is possible via illegitimately monitoring other firms and when they already have the user's information in their database. For each normal neighbor and an arm k, let adver- sarial firm transmit a value slightly larger than (t,x(t) as the sample count information: the arm is the optimal arm 1, let the adversarial firm transmit the second smallest
We ((s,d) d) denote the Gaussian distribution with mean and variance d.
28

---

Published in Transactions on Machine Learning Research (08/2024)
(t) for j E A,,((t) (they are able to accurately predict (t, via monitoring) and otherwise transmit the second largest Fz,((t) for (t)) In this sense, the adver- sarial firms are able to down-weight the optimal arm and up-weight the sub-optimal arms in the decision-making of each normal neighbor to the maximum extent.
For the simmlattio under the above application model, the reward distribution of each arm is set to be a Bernoulli distribution with a randomly generated mean. Each honest firm i sets that is randomly picked from [1,2). The simulation result is shown in Figure I1 We observe that for both Byzantine attacking strategics, our algorithm ensures good performance. Bosides, the performance appears to be not sensitive to different Byzantine policies as the difference of performance under the two types of atlack is negligible.
Considering that the recent study Bayati et al. (2020) shows that the greedy algorithm performs extremely well when the number of arms are large, also test greedy algorithm incorporating Filter ktt) where each normal agent always selects the arm with largest (1,)(() in the decision-making step, i.e., a; (,(++1)= = arg M (t), after executing Filter(i, k,t We compare its performance under the adaptive Byzantine attack with algorithus (a) each normal agent runs Filter(i, k, () then executes softmax on the arms corresponding to the three largest (t, and samples one of them according to the probabilities softmax returns; (b) Resilient Decentralized UCB; (c) Resilient Decentralized UCB with a tuned parameter: similar
to what the single-agent UCB Auer et al. (2002a) does in simulation, we tune the confidence parameter C(t, (t)) to
C(t,n,,(t)) = 9s.8 (1) (t),
logg log!
(23)
The simulation results are shown in Figures 12 and 13
We observe that while softmax generally provides linear regret possibly because agents have probability of order O(1) to select sub-optimal arm at each time, greedy algorithm works well with Filter i, k. t) in resilient sctting. This indicates that our filtering and updating steps (i.e. Algorithm 2) may be compatible to various classic bandit algorithms and thus have great potentials in solving bandit problems, which deserves further investigation in the future. Moreover, when A = 20, i.e, the arm number is large, resilient greedy algorithm has a substantial advantage over Resilient Decentralized UCB while has a notable disadvantage when dealing with relatively small arm number, which is consistent with the observations in the non-resilient setting (aayti et al. (2020). Besides, find that the tuned Resilient Decentralized UCB always performs significantly better than Resilient Decentralized UCB (and in fact better than the resilient greedy algorithm for both arm scttings), which is consistent with the observations for single-agent UCB under the non-resilient setting Auer et al. (2002a). However, like Auer lt al. (2002a), we are not able to provide a theoretical prove for the regret bound. To help see the difference of exploration procedure of the two UCB algorithms, we further divide the total time T into three stages with equal length and provide the simulation of the frequency of arm selecting for normal agents when k 20; see Figures 14 and 15
29

---

Published in Transactions on Machine Learning Research (08/2024)
greedy
greedy
softmax
softmax
1000
UCB
UCB
tuned UCB
tuned
average regret
average regret
800
1000
500
200
0
2000
4000
6000
8000
10000
0
2000
4000
6000
8000
10000
time
time
Figure 12: Simulation result of the average regret of normal agents for different resilient algorithms when k 20
Figure 13: Simulation result the average regret normal agents for different resilient algorithms when
8000
10000
Initial Steps Intermediate Steps
Steps Intermediate Steps
Final Steps
8000
Final Steps
sample count
sample count
6000
4000
4000
2000
2000
0
5
10
15
20
10
15
20
arm index
arm index
Figure 14: Simulation result of the average ex- plorations of normal agents under Resilient De- centralized UCB
Figure 15: Simulation result. of the average explo- rations of normal agents under tuned Resilient Decontralized UCB equation 23
30


Reviews:
[{"review_id": "373h9peoVF", "reviewer": "Reviewer_2sdX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. The cooperative bandits with the Byzantine agents model is novel and interesting. \n2. The trim mean algorithmic technique is simple to understand and effective. The proposed message filter algorithm is straightforward and intuitive and possibly can be combined with other bandit algorithms. But there are some confusions that should be clarified as stated in the request for changes section. \n3. The simulation results are sufficient. \n\n### Weaknesses\n\n1. The consensus-based communication policy is not widely known in the community. The authors should explain the setting better (see the first bullet for Requested Changes).\n2. The theoretical results do not support the statement in the paper. See the second bullet below. \n3.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies a decentralized multi-armed bandit problem where agents employ UCB and consensus-based algorithms and have at most (known) $f$ number of byzantine in-neighbors. The authors design a message-filter algorithm (Algorithm 1) which, for each arm $k$, filters out a message if 1) its number of arm pulls is too small and 2) its reward-mean estimate is the $f$ largest or $f$ smallest among all messages. This paper then provides a byzantine-resilient decentralized multi-armed bandit algorithm that does not depend on connectivity knowledge by combining this message-filter algorithm with UCB and consensus procedures. Regret upper and lower bounds are given to show that normal agents enjoy better regret performance than their non-cooperative counterparts. This work also numerically studies the performance of the proposed algorithm.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. While the (ii) trimmed mean technique is key to achieving resilience, the reviewer cannot understand why (i) consistency filter (Step A) is necessary. Why do the sample times need to be consistent? Is it because estimator (3) does not de-biase the unbalanced sample times of each mean? The reviewer suggests that the authors add an explanation for that. \n\n2. The theoretical results are presented in a very informal manner. For example, the lower bound (Theorem 1) requires additional assumptions for policy (e.g., assume the policy is consistent), which are missed in the statement. Also, the equation in Theorem 1 has a redundant $\\log T$ on the RHS. Theorem 3 only shows a regret upper bound for a normal agent. As the RHS is also an upper bound, the theorem cannot infer that the normal agent with cooperation outperforms non-cooperative UCB1. Similar inference issues appear in Theorems 4 and 5. The \"strictly better\" statement is not well supported. \n\n3. In the proof of Theorem 3, the last inequality of equation (17) holds only if truncation parameter $\\kappa_i < \\frac{4}{3}$; however, the value of $\\kappa_i$ is allowed to be in $[1, 2)$, as introduced in section 3. It seems this makes Theorem 3 invalid. Please clarify that.\n \n4. Regret upper bound of the proposed algorithm (Theorem 2) does not match the given regret lower bound (Theorem 1). Among the regret upper and lower bounds, which is tight and which is loose? For the loose bound(s), please discuss the difficulties of tightening it. Moreover, the proof of Theorem 1 lacks details. \n\n5. In Appendix E, on page 17, the notation $z_{i, k}(t+1)$ is abused to denote both the reward-mean estimate in Zhu \\& Liu (2021) as well as the reward-mean estimate in this work; this makes Lemma 1 confusing. Moreover, the first equation in Appendix E makes use of all messages to update the reward-mean estimate; however, the proof of Lemma 1 assumes only one message is retained for the update. \n\n6. Besides the only limitation (extension to the contextual setting) mentioned in the conclusion section, other limitations include that the regret is not monotone in terms of $\\kappa_i$ (which means the practitioners need to spend extra effort to tune $\\kappa_i$) and that there is a potential theory-practice gap as shown by Figure 4.\n\n7. This paper compares with [Mitra et al. 2022] in Appendix C.2. Is it true that [Mitra et al. 2022]'s regret bounds are problem-independent bounds? If so, it is unfair to say their bounds are worse than the problem-dependent bounds in this work.\n\n8. Typos: \n\n   8.1. Citations should be in parentheses\n\n   8.2. Line 3 in Algorithm 1: $n_{ii, k}(t) \\rightarrow n_{i, k}(t)$\n  \n   8.3. In Equation (2): $\\% \\rightarrow \\emptyset$\n  \n   8.4. In proof of Theorem 2, the first equation on page 20, $n_{i,k}(t) \\rightarrow n_{i, k}(T)$ \n \n    8.5. In proof of Lemma 2, in the last sentence, $$|\\mathcal{B}_{i,k}(t) \\cap \\mathcal{H}|+|\\mathcal{B}_{i,k}(t) \\cap \\mathcal{H}|\\rightarrow |\\mathcal{B}_{i,k}(t) \\cap \\mathcal{H}|+|\\mathcal{B}_{i,k}(t) \\cap \\mathcal{F}|$$", "broader_impact_concerns": "This is a theoretical work. The reviewer is not aware of any foreseeable broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iqA1kf8ObJ", "reviewer": "Reviewer_8dob", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and easy to follow.\n\nThe theoretical derivations are fairly standard for UCB-like algorithms. Having regret no worse than the non-cooperative variant is nice. The improvement on non-cooperative UCB1 is by a small constant factor, which is underwhelming given that the number of samples that can potentially be used is large. It is unclear to me that one cannot devise algorithm that achieves smaller regret bounds in the presence of Byzantine agents, or if the proposed variant is too conservative. There is an asymptotic lower bound that takes into account the graph properties and the upper bound on the malevolent neighbors, but it is difficult to match the lower and upper regret bounds.\n\nThe empirical results do confirm that the proposed algorithm is performing better than the non-cooperative UCB1 variant, but the improvement is indeed by a small factor. Ultimately, this is not surprising, since the amount of exploration driven by the bonus term is reduced by only a small factor.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers decentralized stochastic multi-armed bandit in the presence of possible malevolent (Byzantine) peers. A variant of the UCB1 algorithm is proposed adapted to the multi-agent scenario. In each round agents communicate their empirical mean and sample count for each arm to their neighbors. The incoming stats are filtered out if the sample count is small. The highest and lowest mean estimations are also discarded. The remaining (unfiltered) mean estimations are mixed with the local estimations of the agent. The UCB1 bonus term is modified slightly to take into account the excess number of samples. Theoretical results show that the regret is not worse than the regret without communication, and slightly better by some constant factor in certain cases. Numerical evaluations on synthetic problems show that the proposed algorithm achieves lower regret than the non-cooperative UCB1 variant.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There are some minor typos:\n      * Algorithm 1, line 3: $n_{i,k}$ should be instead of $n_{ii,k}$\n      * there is a strange symbol for the empty set in Equation (2)\n\nIn the experiments it would be useful to plot the regret bounds.", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "l0ipIrPzMf", "reviewer": "Reviewer_ztqz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1.\tThe studied problem, Byzantine-Resilient Decentralized Multi-Armed Bandits, is an interesting problem and finds various applications in computer networks, recommender systems, and financial markets with attacks.\n2.\tThe authors design a fully decentralized resilient upper confidence bound (UCB) algorithm, which adopts a crucial step to truncate inconsistent and extreme values. The idea of this truncation step is interesting.\n3.\tThe authors provide regret upper bounds to show that the regret of each normal agent is no higher than the classic single-agent UCB1 algorithm, and the cumulative regret of all normal agents is strictly better than the non-cooperative case.\n4.\tEmpirical evaluations are conducted to demonstrate the effectiveness of the proposed algorithm.\n\n\n**Weaknesses:**\n\n1.\tIn Theorem 2, the factor $g_{i,k}$ seems to depend on the algorithm? Is it of constant order? It would be better to give a universal upper bound for this factor.\n2.\tIn Theorem 2, it is unclear how the numbers of agents and Byzantine agents ($f$) influence the regret bound. In many prior cooperative multi-player bandit works, when the number of agents increases, the average regret of each agent decreases. Does the result in this paper have the similar property? \n3.\tIt would be more clear to put a formal regret upper bound in Theorem 4, instead of just showing the relationship to the non-cooperative result.\n4.\tIn experiments, can the authors show how the numbers of agents and Byzantine agents ($f$) influence the regret performance of the proposed algorithm in practice?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies how to recover such salient behavior when an unknown fraction of the agents can be Byzantine, that is, communicate arbitrarily wrong information in the form of reward mean-estimates or confidence sets. This formulation is applicable to computer networks, recommender systems, and financial markets. One key contribution of this paper is the development of a fully decentralized resilient upper confidence bound (UCB) algorithm, which fuses an information mixing step among agents with a truncation of inconsistent and extreme values. This truncation step enables the algorithm to achieve the results that the regret of each normal agent is no worse than the classic single-agent UCB1 algorithm, and furthermore, the cumulative regret of all normal agents is strictly better than the non-cooperative case, provided that each agent has at least $3f + 1$ neighbors where $f$ is the maximum possible Byzantine agents in each agent’s neighborhood. The authors also provide a lower bound for this problem, and investigate the extensions to time-varying neighbor graphs. The experimental results corroborate the effectiveness of the proposed algorithm in practice.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the review on weaknesses above.", "broader_impact_concerns": "I do not think that this paper involves ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewer 2sdX in particular found some minor errors, which the authors have already addressed. The other reviewers had minor comments and questions which encouraged the authors to make some nice changes to the manuscript, including an additional simulation. This paper easily satisfies both criteria for acceptance, so I am happy to recommend acceptance.
Decision: Accept (poster)