One More Step Towards Reality: Cooperative Bandits with Imperfect Communication
Authors: Udari Madhushani
Abhimanyu Dubey
Naomi Leonard
Alex Pentland
Venue: NeurIPS 2021 Poster (2021)
Keywords: multi-armed bandits
multi-agent learning
cooperative bandit
imperfect communication

Abstract: The cooperative bandit problem is increasingly becoming relevant due to its applications in large-scale decision-making. However, most research for this problem focuses exclusively on the setting with perfect communication, whereas in most real-world distributed settings, communication is often over stochastic networks, with arbitrary corruptions and delays. In this paper, we study cooperative bandit learning under three typical real-world communication scenarios, namely, (a) message-passing over stochastic time-varying networks, (b) instantaneous reward-sharing over a network with random delays, and (c) message-passing with adversarially corrupted rewards, including byzantine communication. For each of these environments, we propose decentralized algorithms that achieve competitive performance, along with near-optimal guarantees on the incurred group regret as well. Furthermore, in the setting with perfect  communication, we present an improved delayed-update algorithm that outperforms the existing state-of-the-art on various network topologies. Finally, we present tight network-dependent minimax lower bounds on the group regret. Our proposed algorithms are straightforward to implement and obtain competitive empirical performance.

One More Step Towards Reality: Cooperative Bandits with Imperfect Communication
Udari Madhushani Princeton University udarimoprinceton. edu
Abhimanyu Dubey
Massachusetts Institute of Technology dubeya@mit... edu
Naomi Ehrich Leonard
Alex Pentland
Princeton University naomi@princeton. edu
Massachusetts Institute of Technology pentland@mit.ec edu
Abstract
The cooperative bandit problem is increasingly becoming relevant due to its appli- cations in large-scale eeriiionnmmainn However, most research for this problem focuses exclusively on the setting with perfect communication, whereas in most real-world distributed settings, communication is often over stochastic networks, with arbitrary corruptions and delays. In this paper, we study cooperative ban- dit learning under three typical real-world communication scenarios, namely, (a) cesssage-passing over stochastic time-varying networks, (b) instantaneous reward- sharing over a network with random delays, and (c) message-passinn with ad- versarially corrupted rewards, including byzantine communication. For each of these environments, we propose decentralized algorithms that achieve competitive performance, along with near-optimal guarantees on the incurred group regret as well. Furthermore, in the setting with perfect communication, we present an im- proved delayed-update algorithm that outperforms the existing state-of-the-art on various network topologies. Finally, we present tight network-depende minimax lower bounds on the group regret. Our proposed algorithms are straightforward implement and obtain competitive empirical performance.
1 Introduction
The cooperative multi aamee bandit problem involves a group of N agents collectively solving multi-armed bandit while communicating with one another. This problem relevant for a variety of applications that involve decentralized decision-making, for example, in distributed controls and robotics [31] and communication [21]. the typical formulation of this problem, group of agents are arranged in network G (V, wherein each agent interacts with the bandit, and communicates with its neighbors in G, maximize the cumulative reward.
large body of recent work on this problem assumes the communication network G to be fixed [20, 22]. Furthermore, these algorithms inherently require precise communication, they construct careful confidence intervals for cumulative arm statistics across agents, e.g., for stochastic bandits, has been shown that the standard UCB1 algorithm [3] with a neighborhood confidence interval is loss
close to optimal [11. 20), and correspondingly, for adversarial bandits, a neighborhooddweiighe estimator can be utilized with the EXP3 algorithm to provide competitive regret [7]. Such approaches are indeed feasible when communication is perfect, e.g., the network is fixed, and messages are lost or corrupted. In real-workh environments, however, this is rarely true: messages can be lost, agents can be byzantine, and communication networks are rarely static [23]. This aspect has hence received much attention in the distributed optimization literature [35]. However, contrary to network optimization where dynamics in communication can behave synergistically [17], bandit problems
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

additionally bring a decision making component requiring an explore-explos trade-off. As result, external randomness and corruption are incompatible with the default optimal approaches, and require careful consideration [33, 25]. This motivates us to study the multi-agent bandit problem under real-world communication, which regularly exhibits external randomness, delays and corruptions. Our key contributions include the following.
Contributions. We provide set of algorithms titled Robust Communication Learning (RCL) for the cooperative stochastic bandit under three real-world communication scenarios.
First, we study stochastic communication, where the communication network G is time- varyiin, with each edge being present in G with an unknown probability p. For this setting, we present a UCB- like algorithm, RCL-LF (Link Failures), that directs agent to discard messages with an additional probability of - P: in order to control the bias in the (stochastic) reward estimates. RCL-LF obtains [ )
a group regret of o (( (E (1 Pt) + Ecee(max:ss Pt) -P)
where e is a non overlapping clique covering of G, T' is time horizon, and As is the difference in reward mean between the optimal and kth arm. The regret exhibits a smooth interpolation between known rates for no communication (p 0) and perfect communication (p 1).
Second, we study the case where messages from any agent can be delayed by a random (but bounded) number of trials 5 with expectation [[r]. For this setting, simple reward-sharing with natural extension of the UCB algorithm (RCL-SD (Stochastic Delays)) obtains regret of O X(G) (Ee>1 log T A&
+ (N E[r] + log(T) + /N E[r] log(T)) Ex>1 Ae). which is reminiscent of that of single-agent bandits with delays [18] (Remark 4). Here X(G) is the clique covering number of G.
Third, we study the corrupted setting, where any message can be (perhaps in byzantine manner) corrupted by an unknown (but bounded) amount This setting presents the two-fold challenge of receiving feedback after (variable) delays as well as adversarial corruptions, making existing arm elimination [25, 8, 16] or cooperative estimation [11] methods inapplicable. We present algorithm RCL-AC (Adversarial Corruptions) that overcomes this issue by limiting exploration only to well- positioned agents in G, who explore using hybrid robust arm elimination and local confidence bound
approach. RCL-AC obtains regret of O ((GG)) EK log T
+ +N +NER log
+ NTKg))
As
A.
where (G-)) denotes the domination number of the graph power of G, which matches the rates obtained for corrupted single-agent agent bandits without knowledge of c.
Finally, for perfect communication, we present a simple modification of cooperative UCB1 that provides significant empirical improvements, and also provides minimax lower bounds on the group regret of algorithms based on message-passing. passing.
Related Work. A variant of the networked adversarial bandit problem without communication constraints (e.g., delay, corruption) was studied first in the work of Awerbuch and Kleinberg [4), who demonstrated an average regret bound of order v + K //NNT'. This line of inquiry was generalized to networked communication with at most rounds of delays in the work of [7], that demonstrate an average regret of order / v(y + aGG,)/x)KT where aGG)) denotes the independence number of G.,, the 7-power of network graph G. This line of inquiry has been complemented for the stochastic setting with
analyses in the work of Kolla et al. [20] and Dubey and Pentland [11]. The former presents UCB1-style algorithm with instantaneous reward- -aaarnh that obtains a regret bound of (a()). > log that was generalized to message- sastaggg-pssingggggg communication with delays in the latter.
Alternatively, Landgren et al. [22] consider the multi-agent bandit where communication is done instead using a running consensus protocol, where neighboring agents average their reward estimates using the DeGroot consensus model [10]. This algorithm was refined in the work of Martínez-Rubie al. [29] by a delayed mixing scheme that reduces the bias in the consensus reward estimates. A specific setting of Huber contaminated communication was explored in the work of Dubey and Pentland [12]: however, in contrast to our algorithms, that work assumes that the total contamination likelihood is known priori. Additionally, multi-agent networked bandits with stochastic communi- cation was considered in Madhushani and Leonard [26, 27, 28), however, only for regular networks and multi-star star networks.

---

Table 1: Quantity (with notation) for any graph G.
Average degree (d)
Maximum degree (dmax)) Degree of i (d.)
Independence number (a:
Message life (7)
Minimum degree (dmin)
Neighborhood of (N)
Domination number (v))
p-ooeer of G (Gk)
Diameter (d.)
U. (V,5)
Clique covering number (x)
Our work also relates to aspects of stochastic delayed feedback and corruptions in the context of single-agent multi-armed bandits. There has been considerable research in these areas, beginning from
the early work of Weinberger and Ordentlich [34] that proposes running multiple bandit algorithms
in parallel account for (fixed) delayed feedback. Vernade al. [33] discuss the multi-armed bandit with stochastic delays, and provide algorithms using optimism indices based on the UCB1 [3] and KL-UCB [13] approaches. Stochastic bandits with adversarial corruptions have also received significant attention recently. Lykouris et al. [25] present an arm elimination algorithm that provides a regret that scales linearly with the total amount of corruption, and present lower bounds demonstrating
that the linear dependence is inevitable. This was followed up by Gupta et al. [15] who introduce the algorithm BARBAR that improves the dependence on the corruption level by better sampling of worse arms. Alternatively, Altschuler et al. [1] discuss best-arm identification under contamination, which a weaker adversary compared to the one discussed in this paper. The corrupted setting discussed in our paper combines both issues of (variable) delayed feedback along with adversarial corruptions, and hence requires novel approach.
In another line of related work, Chawla et al.[8] discuss gossip-based communication protocols for cooperative multi-armed bandits. While the paper provides similar results, there are several differences in the setup considered in Chawla et al compared to our setup. First, we can see that Chawla et al. do not provide uniform O xx) speedup, but in fact, their regret depends on the difficulty of the first K N arms, which is a O + speed up only when all arms are "uniformly" suboptimal, i... A = Dyvi, e [K]. In contrast, our algorithm will always provide speed up of order "N" regardless of the arms themselves, and when we run our algorithm by setting the delay parameter y = d, (G) (diameter of the graph G), we obtain an O( N. speedup regardless of the sparsity of G. Additionally, our constants (per-agent) scale O (K) ) in the worst case, whereas Chawla et al
obtain a constant between O(K + (log 9) and OKK + Nº) for some 3 >> 1, based on the graph structure, which can dominate the log T term when we have a large number of agents present.
2 Preliminaries
Notation (Table 1). We denote the set a, o.., bas [a, b). and as [b] when a = 1. We define the indicator of a Boolean predicate as 1 {ar). ). For any graph G with diameter d_ (G), and any S S dG),,, we define G. as the 7-power of G, i.e., the graph with edge (1,5) i,j are at most distance 7.
Problem Setting. We consider the cooperative stochastic and a group V of N agents. In each round & E [Z']. each agent i E V pulls an arm (t) [K] and receives a random reward (t) (realized as (t)) drawn i..d. from the corresponding arm's distribution. We assume that each reward distribution is uub-auussian with an unknown mean μ* and unknown variance proxy of upper bounded by known constant σ². Without loss of generality we assume that μ1 2 #22 ... 2 μK and define A& := #1 Pk. Vk > 1, to be the reward gap (in expectation) of arm k. Let Σ == ming>1 A be the minimum expected reward gap. For brevity in our theoretical results, we define g(E,o) := 8(8 + 1)o² = o(1) and fMM G) == M EN>I
armee bandit problem with K arms
1 A
4 EN N (3 (3log(((),(G)) + 1)) + (log (G) + 1))) Ess1 A = o((M + N log N). EEST AR).
Networked Communication (Figure 1). Let = - E) be connected, undirected graph encoding the communication network, where contains an edge (i.j) if agents and j can communicate directly via messages with each other. After each round f, each agent j broadcasts message my to all their neighbors. Each message is forwarded at most y times through G, after which it is discarded. For any value of y > 1, the protocol is called message- -asssing- [24], but for y 1 it is called instantaneous reward sharing, as this setting has no delays in communication.
Exploration Strategy (Figure 2). For Sections 3 and 4 we use natural extension of the UCB1 algorithm for exploration. Thus we modify UCB1 [3] such that at each time step for each arm each agent i constructs an upper confidence bound, i.c., the sum of its estimated expected reward
3

---

For t = 1, 1,2,... each agent i E V
Plays arm (t), gets reward rt),, computes m.(1) (A.(t), (t),
2. Adds (t) to the set of messages (t).). broadcasts all messages in M.()) to its neighbors and receives messages (t) from its neighbors.
Computes (, + 1) from (t) by discarding all messages sent prior to round - 7,
This is called instantaneous reward sharing for (no delays), and message passing for 1.
Figure I: The cooperative bandit protocol with delay parameter "/
For = 1,2, .. ...,
each agent i E V
Calculates, for each arm &t [K]. (t- Tu (t-
log(t-1] where (t
N1(1-1)
is the number of reward samples available for arm A at time t.
Plays (t) arg max, Q (f-1)
Figure 2: Cooperative UCB1 which uses additional arm pulls from messages.
i4 (t 1) (empirical average of all the observed rewards) and the uncertainty associated with the 1, and pulls the arm with the highest bound.
estimate C² - [[ ov (t--1))
logt where
Regret. The performance measure we consider, group regret, is a straightforward extension of pseudo regret for single agent. Group regret is the regret (in expectation) incurred by the group V by pulling suboptimal arms. The group regret is given by Regg(T)) Σ Σe>1 As IE (n((() where n (1) is the number of times agent pulls the suboptimal arm up to (and including) round I.
Before presenting algorithms and regret upper bounds present some graph terminology.
Definition 1 (Clique covering number). A clique cover C of any graph G (V,E) is partition of V into subgraphs e such that each subgraph C' is fully connected, i.c., a clique. The size of the smallest possible covering C* is known as the clique covering number XG))
Definition 2 (Independence number). The independence number a{G) of G (V,E) is the size of the largest subset of Va S V such that no two vertices in Va are connected.
Definition (Domination number). The domination number (G) G = (V, E) is the size of the smallest subset V. C V such that each vertex not in Vi is adjacent
least agent in V
Organization. In this paper, we study three specific forms of communication errors. Section discusses the case when, for both forwarding fails independently with probability p, resulting in stochastic communication failures. Section 4 discusses the case when instantaneous reward-sharing incurs a random (but bounded) delay. Section discusses the case when the outgoing reward from any message may be corrupted by an adversarial amount at most e. Finally, in Section 6, we discuss an improved algorithm for the case with perfect communication and present minimax lower bounds on the problem. We present all proofs in the Appendix and present proof-sketches highlighting the central ideas in the main paper.
and instantaneous reward-shar sharing. any message
Probabilistic Message Selection for Random Communication Failures
The fundamental advantage of cooperative estimation is the ability to leverage observations about suboptimal arms from neighboring agents to reduce exploration. However, when agents are commu- nicating over an arbitrary graph, the amount of information an agent receives varies according to its connectivity in G. For example, agents with a large number of neighbors receive more information, leading them to begin exploitation earlier than agents with fewer neighbors. This means that well- connected agents exhibit better performance early on, but because they quickly do only exploiting, agents that are poorly connected typically only observe exploitative arm pulls, which requires them to explore for longer in order to obtain similarly good estimates for suboptimal arms, increasing their regret. The disparity between performance in well-connected versus poorly connected agents is exacerbated in the presence of random link failures, where any message sent by an agent can fail to reach its recipient with failure probability 1 p (drawn i...d. for each message).

---

Indeed, it is natural to expect the group regret to decrease with decreasing link failure probability, i.e. increasing communication probability p. However, what we observe experimentally (Section 7) is that this holds only for graphs G that are regular (i.e., each agent has the same degree), or close to regular. When G is irregular, as we increase p from 0 to 1, the group performance oscillates. While, in some cases, the improved performance in the well-connected agents can outweigh the degradation observed in the weakly-connedd approach that mitigates this disparity by regulating information flow in the network.
agents (leading to lower group regret), it is prudent to consider an
Information Regulation in Cooperative Bandits. Our approach to regulate information is straight- forward: we direct each agent to discard any incoming message with an agent-specifis probability Pt. while always utilizing its own observations. For specific values of pi, we can obtain various weighted combinations of internal versus group observations. Our first algorithm RCL-LF (Link Failures) built on this regulation strategy, coupled with UCB1 exploration using all selected observa- tions for each arm. Essentially, each agent runs UCB1 using the cumulative set of observations it has received from its network. After pulling an arm, it broadcasts its pulled arm and reward through the network, but incorporates each incoming message only with a probability p;. Pseudo code for the algorithm is given in the appendix. We first present a regret bound for RCL-LF when run with the instantaneous reward-sharing protocol.
1 1- 1-p;.
Theorem LF Regret with instantaneous reward-sharing). RCL-LF running with the instanta- neous reward-sharing protocol (Figure 1, 7 1) obtains cumulative group regret of
(T) S o)
Σa- PL-
+ (max pi)
:P)
Σ
logT A
+ F(5N,G)
CEe
where @ is a non-overlapping clique covering of G.
Proof sketch. We follow an approach similar to the analysis of UCB1 by [3] with several key modifications. First, we partition the communication graph G into a set of non-overlapping cliques and then amalyze the regret of each clique. The group regret can be obtained by taking the summation of the regret over each clique. Two major technical challenges in proving the regret bound for RCL-LF are (a) deriving a tail probability bound for probabilistic communication, and (b) bounding the regret accumulated by agents by losing information due to communication failures and message discarding. We overcome the first challenge by noticing that communication is independent of the decision making process thus E cxp ( E [A = k) Ni.V - X²0
2 N(()) S 1
holds under probabilistic communication. We obtain the tail bound by combining this result with the Markov inequality and optimizing over À using pecling type argument. We address the second challenge by proving that the number of times agents do not share information about any suboptimal arm k can be bounded by term that increases logarithmically with time and scales with number of agents, G, and communication probabilities, as Ei P4 p) Ecee(max;cc) Pt) Pp. n
Remark 1 (Regret bound optimality). Under perfect communication (p = 1) and no message discarding, i.e., p:- = p = vi E [N] the dominant term in our regret bound scales with X()).
obtaining identical performance to deterministic communication over G [11]. Alternatively, when P: = p = there is no communication, and hence, the regret bound is ((N log 7). Theorem 1 quantifies the benefit of communication in reducing the group regret under probabilistic link failure and when agents incorporate observations with an agent-specific probability. Note that
EN P: p) + Ecee(maxige P:) p N - p- [EMP Eeee (max;ge p.)) Since the clique covering is non-overlapping, the results show that agents obtain improved group performance for any communication probability p > for any nontrivial graph as compared to the case with no communication in which each agent learns on its own.
Remark 2 (Controlling information disparity). In order regulate the information disparity across AminnG) the network we set p: d, Thus, the agent(s) with minimum degree dmin incorporate each message they receive with probability and we have that the expected number of messages for each agent is the same, i.e., T (minn()), Therefore, every agent receives the same amount of information (in expectation), providing a large performance improvement for irregular graphs (see Section 7).
Message- Passing. Under this communication protocol each agent i communicates with neighbors at distance at most 7, where each hop adds a 1 1-step delay. Our algorithm RCL-CF obtains a similar regret bound in this setting as well, when all agents use the same UCB1 exploration strategy (Figure 2).
5

---

Theorem 2 LF Regret with message paarggggg. Let e be a minimal clique covering of G.. For any C E e and i.j E C let % maxjec d((.j) j) be the maximum distance (in graph G) between agents i and j. RCL-LF running with the message- messane-passing protocol (Figure 1) with delay parameter y obtains cumulative group regret of
RT) S o(
N (1- Pe p") + x(Gr)
(max Pe VSN
p7))
Σ
logT) Ax + f((T 4)),
Proof sketch. We partition the graph Gy into non-overlapping cliques, analyze the regret of each clique and take the summation of regrets over cliques to obtain group regret. In addition to the challenges encountered in Theorem here we are required to account for having different probabilities of failures for messages due to having multiple paths of different length between agents and to account for the delay incurred by each hop when passing messages. We overcome the first challenge by noting that agent i receives each message with least probability p We overcome the second challenge by
identifying that regret incurred by delays can be upper bounded using
(E N NN ExsI Ak. D
Remark 3. Finding an optimal observation probability {p: for LF with message- passsigggpaanggggggeg is
difficult due to the delays added by each hop when forwarding messages. If messages are forwarded without a delay, optimal performance can be obtained by using dmin(G,) For dense Gy, the above choice of observation probability provides near-optimal performance. When 7 dG) (G.) we have that G, is a complete graph, P; C,, = 1, and agents do not discard any message. dwin
d,G,))
However, when y < d. (G), the graph G, is not complete. Therefore agents receive different amounts of information which are approximately proportional to the degree distribution of G.. As explained earlier this information disparity leads a performance disparity among agents. As result group performance decreases. In this case we design the algorithm such that each agent i discards messages dente (G,). This regulates the information flow mitigating the bias introduced with pt where p; d,G,,) by information disparity. As result the group obtains near-optimal performance.
4 Instantaneous Reward-sharing Under Stochastic Delays
Next, we consider a communication protocol, where any message is received after an arbitrary (but bounded) stochastic delay. We assume for simplicity that each message is sent only once in the network (and not forwarded multiple times as in message message-passinng, and leave the message- setting future work. We assume, furthermore that the delays identically and independently drawn from a bounded distribution with expectation E[r] (similar to prior work, e.g., Joulani et al. [18], Vernade et al. [33]). For this setting, we demonstrate that cooperative UCB1, along with incorporating all messages as soon as they are available, provides efficient performance, both empirically and theoretically. We denote this algorithm RCL-SD (Stochastic Delays), and demonstrate that this approach incurs only an extra O ((VN log + log T) overhead compared to perfect communication.
Theorem (RCL-SD Regret). Let D = [E[T] + log T + 22//N N [ log T denote an upper bound on the total number of outstanding messages. RCL-SD obtains, with probability at least + cumulative group regret of
log T A
Rega (T) S (((E,) X(G).
Σ
+ Droual
Σ Ax
+ f(NN.G).
sketch. sketch. We first demonstrate that the additional group regret due to stochastic delays can be bounded by the maximum number of cumulative outstanding messages over all agents at any given time step. Then we apply result similar Lemma of [18] bound the total number of outstanding messages using the cumulative expected delay N E[r], giving the result.
Remark 4. The Dioial term is a succinet upper bound on the maximum number of cumulative outstanding messages over all agents, and when the expected delay [E[]] = o(1), we see that the contribution of Dunat is O(vN N logT + log T). We conjecture that this cannot be improved without restricting communication, as each agent will send messages total. The result obtained by Joulani et al. [18] has similar dependence for a single agent.

---

Algorithm 1: RCL-RC: Cooperative Hybrid Arm Elimination
Parameters: Confidence (0, 1). horizon T, graph G with exploration set V. Initialize (0(0) K, e IA 1024 log for each subgraph N,; (G-)) where E I for [ 1, ..., K, each agent j M (G-) do
8K (Kv()) log2 T) and (1(0) 1, [K] and i I.
| Play arm K and get reward (t)... end
for epoch my = 1, 2, do
(m; Set n (m;) = X( (m: - 1)) E [K].
N2(m,)) Σx ni (m;) and T: (m,)) = T:,m,)) + N((,,) + 2y.
for agent j E EN (G,,) do
for / = (m, - to Timm: 1) + 27 do
if j + i then
if < K + d(i,j) then
| Pull random
end else
Pull (t) = A,(t -i(i,)) and get reward (t).
end
end
else
Pull (t) UCB1(t)
end
end
for f (mmm: 1) 2y to (:(m)) do
j * then
Pull A,(t) A, d(i,j)) and get reward (t).
end
else
Pull an arm At(t) = k E [K] with probability mi(mm))NN end
end
end
end
end
5
Hybrid Arm Elimination for Adversarial Reward Corruptions
In this section, we assume that any reward when transmitted can be corrupted by a maximum value of e, i.c., maX,,n [r, (t) F, (t) < e where (t) denotes the transmitted reward. Furthermore, we assume that the corruptions can adaptive, i.e., can depend on the prior actions and rewards of each agent. This model includes natural settings, where messages can be corrupted during transmission, as well as byzantine communication [12]. If were known, we could then extend algorithms for misspecified bandits [14] to create a robust estimator and subsequent UCB1-like algorithm that obtains regret of (x,(G,,) (1og2") + TN Ke). However, this approach has two issues. First, typically not known, and the dependence on G. can be improved as well, We present an arm- elimination algorithm called RCL-AC (Adversarial Corruptions) that provides better guarantees regret, without knowledge E in Algorithm
The central motif in RCL-AC's design is to eliminate bad arms by an epoch-based exploration, an stochastic bandits [25, 15]. The
idea that has been successful the past for challenge, however, in a message- passing decentralized setting is two-fold. First, agents have different amounts information based on their position the network, and hence badly positioned agents in G may be exploring for much larger periods. Secondly, communication between agents is delayed, and hence any agent naively incorporating stale observations may incur heavy bias from delays. To ameliorate the first issue, we partition the group of agents into two sets exploring agents (I) and
7

---

imitating agents (V') Z). The idea is to only allow well-positione agents in I to direct the exploration strategy for their neighboring agents, and the rest simply imitate their exploration strategy. We select I as minimal dominating set of Gy, hence [Z] *.G,). Furthermore, since V [ is a vertex cover, this ensures that each imitating agent connected (at distance at most 7) to at least one agent in I. Next, observe that there are two sources of delay: first, any imitating agent must wait at most 7 trials to observe the latest action from its corresponding exploring agent, and second, each exploring agent must wait an additional y trials for the feedback from all of its imitating agents. We propose that each exploring agent run UCB1 for 2y rounds after each epoch of arm elimination, using only local pulls. This prevents a large bias due to these delays, at a small cost of Ollog T)) suboptimal pulls. Theorem (RCL-RC Regret). RCL-RC obtains, with probability at least 6, group regret of
(T) = -000=000KN (KINNC + (Gz))
T Ah
log
[w(G.) log
N
D + Σ
N log(y log T)
5
4
R>1
Proof sketch. Since the dominating set covers V. we can decompose the group regret into the cumulative regret of the subgraphs corresponding to each agent in (GGG), For each subgraph, we can consider the cumulative regret incurred when the exploring agent follows UCB1 versus arm elimination. We have that arm elimination occurs for log T epochs, and since UCB1 runs for 2 rounds between succesive epochs, we have that in any subgraph of size n, the cumulative regret from UCB1 rounds is of OnnK log(y log T)). For arm elimination, a modification of the approach in Gupta et al. [15]: the difference in our approach is to construct a deppedent))))) corruptions from message-passee
can bound the subgraph regret using
multi-agent filtration for arbitrary applying Freedman's 's bound on the resulting martingale sequence. Subsequently, the regret in each epoch is bounded in a manner similar to Gupta et al. [15], and finally applying a union bound. D
and then
Remark 5 (Regret Optimality). Theorem 4 demonstrates a trade-off between communication density and the adversarial error, as seen by the first two terms in the regret bound. The first term (K) is bound on the cumulative error introduced due to message- -aassing. which is increasing in whereas the second term denotes the logarithmic regret due to exploration. where (G-,,, decreases as y increases: for y = d, (G), (G,,), L, matching the lower bound in Dubey and Pentland [11]. This too expected, as fewer exploring agents are needed with a higher communication budget. Furthermore, we conjecture that the first term is optimal (in terms of T, up to graphical constants): a linear lower bound has been demonstrated for the single-agent setting in Lykouris al. [25].
Remark 6 (Computational complexity). While the dominating set problem is known to be NP- complete [19], the problem admits a polynomial-time approximation scheme (PTAS) [9] for certain graphs, for which our bounds hold exactly. However, RCL-RC can work on any dominating set of size log I n, and suffer regret of ÖKKTNee + E A.
An Algorithm for Perfect Communication and Lower Bounds
For perfect communication, we present Delayed MP-UCB, a simple improvement to UCB1 with message-passing where each agent i only incorporates messages originated prior to 7 S time steps, reducing disparity in information across agents.
Theorem 5 (Delayed MP-UCB Regret). Delayed (MP) obtains cumulative group regret of
log T'
Rega (T) (1((E
+ +NN
Σ 1>1
Au+ S(NN + h 7)
A
where (((G,,))) = (AV
Σ
log
4,1G,18 (d. (dy 1111
EtsI A
log 1.3
1-
14
Proof sketch. Following similar approach to the proof of Theorem 2 we partition the graph G. into a set of non-overlapping cliques, analyze the regret of each clique via a UCB1 type analysis and take the summation of regret over cliques. However, using less information (due to delayed information usage) in estimates leads to large confidence bound Ci(() and this reduces the contribution to the
regret from tail probabilities. Note that log 1
d, (G (d,(G,)+1))) ) is negative Vt > 7, and hence lower
regret achieved due to low tail probabilities is given by the second term of h(G 7))
'The Ø notation ignores absolute constants and log log(-) factorrs in I'.
8

---

Remark 7. Incorporating only the messages originated before F time steps is similar to communi- cating over G. after delay of 7 time steps. When G connected and î = 7 d, this is similar to communicating over a complete graph with delay of d. Thus Delayed MP-UCB mitigates the disparity in information used by each agent, leading to improved group performance.
Lower Bounds. Without strict assumptions, a lower bound of O P( log7/s.) has been demon- strated both for y 1 (instantaneous reward-sharing, Kolla et al. (201) and 7 > (message- passing, Dubey and Pentland [11]), which both suggest that speedup of n For a more restrictive class of individually consistent and non-altruistic policies (i.e., that do not contradict their local feedback), a tighter lower bound of O (a((2) EkS1 logT/ax) can be demon- strated for reward-sharing [20], and consequently O (a(Gr++1 Ex>1 logT/2,) for message-passing To supplement these results, we present a lower bound to characterize the minimax optimal rates for the problem. We present first an assumption on multi-agent policies.
I' is potentially achievable.
Assumption (Agnostic decentralized policies). A set of N policies Ti,..., NNNN are termed agnostic decentralized policies, for every pair (i.j) of agents that communicate in G and each t [T), (1( is independent of {T) 1-d(i-)) conditioned on the rewards (xA]()))((())))=) (-t(5)
Theorem (Minimax Rate). For any policy A, there exists a K Kaareed environment over N agents with Ae 1 for any connected graph G and y 2 1 such that, for some absolute constant c,
Rega(A, 3 ev KN(T + ā(G)).
Furthermore, if is an agnostic decentralized policy, there exists a K Karred environment over N agents with 4 S for any connected graph G and y 2 +1 such that, for some absolute constant d'.
> é' (V
Here d(G)) = () ن=i i denotes the average delay incurred by message-passing across the network G, and a" (G,)) = N is Turan't 's lower bound [32] on a(,,).
I+d,
Remark (Tightness of lower bound). The first minimax bound does not make any assumptions on the policy A, and hence we only see additive dependence of the average delay incurred by communication over G. This dependence generalizes the minimax rate for delayed multi-armed bandits [30] to graphical feedback. For the latter bound, observe that variety of cooperative extensions of single-agent bandit algorithms [20, 11, 7] obey this assumption, where the decision- making for any agent independent of any other agent, conditioned on the observed rewards. In this setting, agents merely treat messages as additional pulls to construct stronger estimators, and do not strategize collectively. This bound is exact (up to constants) for variety of communication graphs G. For instance, for linear and circular graphs, (G() o(1), and for d-regular graphs, a (G,) = a(G,) [32].
a(G,)
7 Experimental Results
We consider the 10-armed bandit with rewards drawn from Gaussian distributions with 0 1 for each arm, such that μ = and μ4 = 0.5 for k * 1, and the number of agents N = 50. where we repeat each experiment 100 times with selected randomly from different families of random graphs. The bottom row of Figure 3 corresponds to Aedoos-Renyj graphs with p 0.7. The top row of Figure (a), (c) and (d) corresponds to multi-star graphs and (b) and (e) to random tree graphs. We set g 1.1 and 7 max(3 (3, d4, (2).
Stochastic Link Failure. Figure 3(a) and Figure 3(b) summarize performance of RCL (RS) -LF and RCL (MP) comparing it with the corresponding reward-sharing and message-passing UCB- like algorithms in which p; Vi E [N). for different p values. The group regret given at T 500. The results validate our claim that probabilistic message discarding improves performance for irregular graphs and provides competitive performance for near-regular graphs.
Stochastic Delays. We compare performance of RCL-SD with UCB1. We draw delays from a bounded distribution with [[T] 10 and 7max 50. The results summarized in Figure 3(c).
Adversarial Communication. We compute the (approximate) dominating set using the algorithm provided in networkx for each connected component in G.y. We draw corruptions uniformly from the

---

Link (uilure(R))
Link MM)
Stochoetie in Twlay
Random Carruption
Perfect Commonication
103- xx. 1E31
2200
8500
1000
3000
1003
1000
2300
6000
0111
Doog Boght
7000
10000
5002
7000
6.000
000
3000
5000
4002
200
2300
0.3
10
6.0
01.5 Profaliit (9)
1.5
900
3000
10,00
BL004
500
1000
Phobiliity GI
Tix:: (1)
Cherppãio (3)
Taee
(A)
(6)
(6)
(8)
[c)
Figure 3:
Experimental results for various imperfect communication settings.
range [0, E) for each message, where 6 is increased from 10-3 3 to 10-2. The group regret at 7 500 as a function of is shown in Figure 3(d) and compared against individual UCB1 and cooperative UCB with message-passing (MP-UCB), which incur larger regret increasing linearly with
Perfect Communication. We compare the regret curve for T 1000 for our Delayed (MP) against regular MP-UCB in Figure 3(e). We use 7 2. It is evident that delayed incorporation of messages markedly improves performance across both networks.
Conclusions
In this paper, we studied the cooperative bandit problem in three different imperfect communication settings. For each setting, we proposed algorithms with competitive empirical performance and provided theoretical guarantees on the incurred regret. Further, we provided an algorithm for perfect communication that comfortably outperforms existing baseline approaches. We additionally provided a tighter network-dependent minimax lower bound for the cooperative bandit problem. We believe that our contributions can be of immediate utility in applications. Moreover, future inquiry can be pursued in several different directions, including multi-agent reinforcement learning and contextual bandit learning.
Ethical Considerations. Our work is primarily theoretical, and we do not foresee any negative societal consequences arising specifically from our contributions in this paper.
References
[1] Altschuler, V.-E. Brunel, and A. Malek. Best arm identification for contaminated bandits. Journal of Machine Learning Research, 20(91):1-39, 2019.
[2] D. Angluin and L. G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. Journal of Computer and System Sciences, 18(2):155-193, 1979.
[3] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235-255 2002.
[4] B. Awerbuch and R. Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97-114, 2008
[5] Bubeck. Bandits games and clustering foundations. PhD thesis, 2010.
[6] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press,
2006.
[7] N. Cesa-Bianchi, C. Gentile, and Y. Mansour. Delay and cooperation in nonstochastic bandits. The Journal of Machine Learning Research, 20(1):613-650, 2019.
[8] R. Chawla, A. Sankararaman, A. Ganesh, and S. Shakkottai. The gossiping insert-eliminate algorithm for multi-agent bandits. In International Conference on Artificial Intelligence and Statistics, pages 3471-3481, PMLR, 2020.
[9] Crescenzi, V. Kann, and M. Halldórsson. A compendium np optimization problems, 1995. URL http:///weet //ww: nada, kth. se/viggo/ wtwgvv/proolleeiieeeeeeeo probpeolllllleoo ist/ compendi um. html.
[10] M. H. DeGroot. Reaching a consensus. Journal of the American Statistical Association, 69 (345):118 11-121, 1974.
10

---

[11] A. Dubey and A. Pentland. Cooperative multi-agent bandits with heavy tails. In International Conference on Machine Learning, pages 7730-2739. PMLR, 2020.
[12] A. Dubey and A. Pentland. Private and byzantine-prood cooperative decision-making. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 357-365, 2020.
[13] A. Garivier and O. Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond.
In Proceedings of the 24th Annual Conference Learning Theory, pages 359-376. JMLR Workshop and Conference Proceedings, 2011.
[14] A. Ghosh, S. R. Chowdhury, and A. Gopalan. Misspecified linear bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[15] A. Gupta, T. Koren, and K. Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562-1578. PMLR, 2019.
[16] S. Gupta, S. Chaudhari, G. Joshi, and O. Yagan. Multi-armed bandits with correlated arms. IEEE Transactions on Information Theory, 2021.
[17] S. Hosseini, A. Chapman, and M. Mesbahi. Online distributed convex optimization on dynamic 2016.
networks. IEEE Transactions on Automatic Control,
[18] P. Joulani, A. Gyorgy, and C. Szepesvári. Online learning under delayed feedback. In Interna- tional Conference on Machine Learning, pages 1453-1461, PMIR, 2013.
[19] R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Compu- lations, pages 85-103. Springer, 1972.
[20] R. K. Kolla, K. Jagannathan, and A. Gopalan. Collaborative learning of stochastic bandits over a social network. JEEE/ACM Transactions on Nenworking, 26(4):1782-1795, 2018.
[21] L. Lai, H. Jiang, and H. V. Poor. Medium access in cognitive radio networks: A competi- tive multi-armed bandit framework. In 42nd Asilomar Conference on Signals, Systems and Computers, pages 98-102. IEEE, 2008.
[22] P. Landgren, V. Srivastava, and N. E. Leonard. Distributed cooperative decision making in multi-agent multi-armed bandits. Automatica, 125:109445, 2021.
[23] Leskovec. Dynamics of large networks. PhD thesis, Carnegie Mellon University, School of Computer Science, Machine Learning, 2008
[24] N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-200
1992.
[25] Lykouris, V. Mirrokni, and Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages
1 122, 2018
[26] U. Madhushani and E. Leonard. Heterogeneous stochastic interactions for multiple agents in
a multi-armed bandit problem. In European Control Conference, pages 3502-3507, 2019.
[27] U. Madhushani and N. E. Leonard. Distributed bandits: Probabilistic communication d-regular graphs. In European Control Conference, 2021.
[28] U. Madhushani and N. E. Leonard. Heterogeneous explore-exploit strategies on multi-star networks. IEEE Control Systems Letters, 565): 2021.
[29] D. Martínez-Rubio, V. Kanade, and P. Rebeschini. Decentralized cooperative stochastic bandits.
In Advances in Neural Information Processing Systems, pages 4531-4542, 2019.
[30] G. Neu, A. Antos, A. György, and C. Szepesvári. Online markov decision processes under bandit feedback. In Advances in Neural Information Processing Systems, pages 1804-1812, 2010.
[31] V. Srivastava, P. Reverdy, and N. E. Leonard. Surveillance in an abruptly changing world via multi-armed bandits. In Conference on Decision and Control, pages 692-697, IEEE, 2014.
[32] Turán. On an external problem graph theory. Mat. Fiz. Lapok, 48:436-452, 1941.
[33] C. Vernade, O. Cappé, and V. Perchet. Stochastic bandit models for delayed conversions. In Conference Uncertainty in Artificial Intelligence, 2017.

---

[34] M. J. Weinberger and E. Ordentlich. On delayed prediction of individual sequences. IEEE Transactions on Information Theory. 48(7):1959-1976, 2002.
[35] T. Yang. X. Yi. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong. H. Wang. Z. Lin, and K. H. Johansson.
A survey of distributed optimization. Annual Reviews in Control, 47:278-305, 2019.
12


Reviews:
[{"review_id": "roAGl4P2giZ", "reviewer": "Reviewer_nCmj", "summary": "The paper studies cooperative multi-armed bandit in a few scenarios including stochastic time-varying networks, random communication delays, and byzantine data corruption. For each scenario, a decentralized algorithm is proposed and analyzed for its network regret bound. For the special case with perfect communication, an algorithm is proposed and shown to outperforms the existing state-of-the-art algorithms. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers an interesting and important problem with different \"realistic\" communication settings. \n\nMy biggest concern is about the setting of cooperative multi-armed bandit which is the basis for all four algorithms in the paper: A uniform upper bound for all arms' (unknown) variance proxy is known to each agent. In the problem formulation, each agent faces the same set of arms and there is no difference in reward observation distribution among the agents. That means each agent can learn the best arm by itself without any information from other agents, which can be done by any state-of-the-art UCB algorithms. However, now with collaboration and additional information from others, each agent even need more arm information -- the upper bound. The basic setting itself is not convincing. Moreover, in the proposed algorithms, each agent makes use of this uniform upper bound in the confidence bound function, which is a critical component determining regret bounds. Considering different arms may have large difference in variance proxy, such a design generally may not lead to optimal regret. \n\nThe algorithm RCL_LF is mainly described by words. To me it is not precise enough. \n\nIn Remark 1, the claim that \"Theorem 1 quantifies the benefit of communication\" needs more explanation/validation. The benefit of communication (i.e. collaboration) also needs to compare with the case when each agent learns itself by state-of-the-art UCB algorithms. \n\nI have trouble understanding Remark 2. There is no d in the theorem. The setting of p with d will needs further network information. Similarly, the claim in Remark 3 is also hard to follow, which needs further details/explanation.\n\nThe ideas and algorithm in Section 5 are not clearly explained. If the algorithm requires a partition of exploring and imitating agents, then it requires a centralized design procedure. Does the partition arbitrary? Can any agent be corrupted? \n\nUpdate on Sep 2:  Thanks the authors for detailed response. I am not fully convinced by the authors' response. The authors' model is based on the assumption that each agent can directly transmit reward values. To me this simplifies the algorithm design and analysis. Also because of this, the claim that cooperative bandit here can improve network regret is straightforward, since for each clique with M agents, it is essentially equivalent to the case where each agent can pull M arms at one time. Thus the constant before log T term, when p=1, is then the number of covering cliques instead of the number of total agents.\n\nAfter reading the references in the authors' response, I feel the random link failure (Theorem 1) and stochastic communication delays (Theorem 3) are incremental results, particularly the latter as also reflected by the proof sketch of Theorem 3.\n\nAs for Section 5, the authors admitted in the response that the proposed algorithm requires a centralized design/partition among the agents, which is not feasible for the decentralized/cooperative setting. \n\nWith the above, I decide to keep the score. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "BTbZoj6Vj6", "reviewer": "Reviewer_4XMJ", "summary": "This paper considers the stochastic cooperative bandit setting. In this setting a network of agents works together to control the regret, which is the expected difference between the cumulative rewards of the agents and the cumulative reward of the best arm. While this setting has been studied in prior work, this paper addresses some real worlds issues that may be encountered. These issues include communication between agents failing, delay in messages over the network, and adversarial corruptions of the messages. All these variations of the standard stochastic cooperative bandit setting lead to problems for standard algorithms, which the paper addresses. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem that is studied is quite well motivated and I agree that the results in this paper are a step towards applications of the setting in more realistic scenarios. \n\nWhile the influence of delay and adversarial corruptions have been studied in isolation, it appears that it has not been studied in the stochastic cooperative bandit setting. Therefore, the results surrounding these problems are novel, but not entirely unexpected given prior work. Nevertheless, the solutions to these problems appear to be novel and are very well explained. \n\nHowever, as far as I am aware, the problem of communication failing has not been studied before. The challenges this brings to algorithms are clearly explained and the solution, ignoring messages to control bias, is elegant. The experiments are also quite helpful in explaining the challenges that are posed to the problem of failing communication. There is one caveat, which is that the probability of communicating a message is assumed to be known (line 45). This appears to be a weak spot in the argument that this problem is a step towards reality, as I cannot imagine a scenario in which this is known. I think that a discussion on why it is realistic that this probability is known and why it needs to be known would be a good addition to the paper. \n\nThe results in the paper are well discussed. Where possible the results are related to prior work and lower bounds. The experiments are a good addition  to the paper. \n\nMinor comments,\n- Figure 3: the bottom plot of the message passing experiment does not appear to be correct: the y-label and the letter match the bottom plot of the instantaneous reward sharing experiment. Also, instantaneous contains a typo. \n- line 220: extra (\n- Algorithm 1, initialize:  before $\\lambda$ a comma is missing. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5"}, "extra_text": {}}, {"review_id": "6nUw8lFCxuz", "reviewer": "Reviewer_kyrg", "summary": "The paper studies the multi-agent cooperative bandit model and presents three scenarios where \"imperfections\" in the communications between agents. The first is when communication links fail, second is when communications are delayed and third is where the communication messages are corrupted. Each of these are important problems by themselves and are crucial to understand to deploy multi-agent bandit algorithms in practice. For these three cases, the paper proposes UCB based algorithms that exploit the graph structure, and show that, despite communication imperfection, the group regret is smaller than the sum of individual regrets had agents chosen not to collaborate at all. The results thus provide a smooth trade-off where if the communications are good, the regret is small, while in the worst case, the regret is no worse off than no communication.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is quite comprehensive and contains many results. The attractive feature of the paper is that the analysis for the various cases of imperfection can be handled using similar ideas. \n\nOne place off improvement is to give an algorithm for RCL-LF, which I did not find even in the supplementary materials. Overall, I like the paper and its attempts. Nevertheless, I had a few questions on the model with random link failure, which is the reason for my low score. I am happy to increase my score if the following items can be explained.\n\n1. In the noiseless case, the reference (missing in the submission) \"The gossiping insert-eliminate algorithm for multi-agent bandits\" by Chawla et.al. in AISTATS 2020 shows that for any graph, every agent incurs a regret reduction of order N. So, this is an improvement over the Dubey, Pentland result quoted in Line 188 of the submission. Therefore the results of Chawla et.al. is also an improvement over Theorem 5 of the submission ?\n\n2. I am a bit confused on lines 148-152 in the submission. I am quoting the last sentence (152): \"This improved performance has a consequence, however: agents that are poorly connected only observe exploitative arm pulls, which requires them to explore for longer in order to obtain similar estimates for sub-optimal arms, increasing their regret.\" This seems contradictory to results, of Chawla et.al. above, which show that for any graph, every agent incurs a regret reduction of order N ?\n\n3. I am confused about the algorithmic methodology, as to why must agents discard information. The generated messages are of the form  (Arm Pulled, Reward, Agent, time) that are floating around in the network. Second, the reward noted down in the message is independent of the decision to play the arm, as the decision of arm-pulls are based on historical samples. Thus, very message is \"useful\" and \"tractable\" (since they are iid) and can potentially be used to improve regret ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Provide pseudo-code for RCL-LF. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper investigates 3 scenarios in the multi-agent cooperative bandit model where the communications between agents is not perfect. 
In particular, the paper covers the cases when: (i) communication links fail; (ii) communications are delayed; and (iii) the communication messages are corrupted. For teach of these cases, the author propose a UCB based algorithm that exploits the graph structure of communication channels, and show that group regret is smaller than the sum of individual regrets (when agents chosen not to collaborate at all), even in the case of imperfect communication. That is, it's better to form a grand coalition rather than acting independently.

While the majority of the reviewers found the responses of the authors to be sufficient and have clarified most of their concerns, the 3rd reviewer still argues that the results (especially Theorems 1 and 3) are rather incremental. Let me express my own opinion here that I respectfully disagree with this reviewer, as I think each of these problems themselves is quite essential and therefore worth investigating. The proof techniques might not be too difficult, but I also agree with one of the reviewers that this should be a positive thing, rather than a reason for rejection (if the motivation + positioning of the problem is well justified). Therefore, I would like to recommend the opinion of the majority of the reviewers, that is, to accept this paper (although as a poster).
Decision: Accept (Poster)