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..o 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 eeriiionnmmkinn 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) cesssageppassing 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>1
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 pp (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 1 1-Pr. 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.
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 ( Et [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 dmin (G). 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- message-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)N,
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(.,
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 log 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 ÖKKTNTe + 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)-UCB 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 regret achieved due to low tail probabilities is given by the second term of h(G 7))
d, (G (d,(G,)+1))) ) is negative Vt > 7, and hence lower
'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]()))((())))=) (-((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 Tolay
Random Carruption
Perfect Commonication
103- xx. 1E31
2200
8500
1000
3000
1003
1000
2300
6000
0111
Doogg 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:///wwet //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": "sNv5_-ufp7", "reviewer": "Reviewer_huWS", "summary": "Final comment: in its current form, I believe this paper is borderline. I went back and forth with it, but having to commit to either a weak acceptance or a weak rejection, considering all comments and the discussion with the other reviewers, I am, unfortunately, picking the latter.\n----------\n\nTLDR: The authors study three variants of a cooperative bandit setting with imperfect communication. \n\nBase setting in short: at each round, each agent in a network pulls an arm, sees and gains its corresponding reward, then shares some messages with its neighbors with the goal of minimizing the collective regret. \n\nVariant 1: each message can fail to reach its recipient with probability $1-p$.\n\nVariant 2: messages arrive with a stochastic (but deterministically bounded) delay\n\nVariant 3: the real numbers shared in the messages are corrupted with a small perturbation\n\nThe authors introduce and analyze simple algorithms for these three variants. \nThey also consider the problem with perfect communication, for which they prove an upper and lower bound. The lower bound is improved in a special case but none of them scale with the same problem-dependent constants of the upper bound.\n\nThe theoretical results are complemented by some experiments.", "questions": "", "limitations": "", "rating": 5, "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": "TLDR: the variants introduced are of some interest but I am not fully convinced that the current state of the paper meets the NeurIPS standards in terms of novelty, techniques, and completeness.\n\nDiscussion\n\nThe idea of modeling some sort of communication impediment within a cooperative setting is worth exploring. To this end, I suggest adding the reference [1], where the impediment is a constraint in the number of bits of the messages, and look at the references therein.\nIn particular, I find all three variants studied in this paper to be worthy research directions and of interest to the NeurIPS community.\n\nMy main issue is the novelty. \nThe algorithms are all pretty natural. This would not be a flaw per se but their analysis and the corresponding results are not too different from the most standard techniques and the most expected results that one could think of. This leads me to question the value that this work in (its current state) would add to the community.\nOn a similar note, this paper seems incomplete. Of the five upper bounds that are presented, only one of them has a corresponding lower bound (that on top of it, is mismatching). Moreover, the paper introduces two protocols for their setting (message-passing and instantaneous reward sharing, 117-118) and it analyzes both of them at the beginning, but then it abruptly drops one of them without giving a real reason why (220-221).\nOverall, this feels more like a collection of several loosely related minor results than a coherent paper with a clear message. I would have preferred to see fewer variants (even just one of them) fully fleshed out instead.\n\nQuestions/issues on specific sections.\n\n- Section 3. \n\t- The bound in Thm 1 depends on the clique-covering number. However, [2] suggests that for these types of distributed problems the right scaling is usually with the independence number (which is always smaller). Do you believe your analysis could be refined or do you have an argument for why the correct constant is the clique-covering number?\n\t- Remark 1 is fine but it would be preferable to have a proper lower bound, that matches the dependence on p and $\\bar \\chi$ of Thm 1\n\t- In Remark 2, the tuning of $p_i$ depends on $d_{\\min}(G)$, meaning that the nodes need some knowledge of the global structure of the network. This is an undesirable requirement in cooperative learning. Is there a way to keep the same bound but only require the agents to have local knowledge (i.e., only about their neighborhoods)?\n\t- Thm 2. Same question of Thm 1 on $\\bar \\chi$ vs $\\alpha$.\n\t- Remark 3. Similar remark and question as for Remarks 1 and 2.\n- Section 4\n\t- Why dropping message-passing? Inconsistent approach.\n\t- Applications of delayed analysis in cooperation already appeared in recent work. I suggest adding a reference to [3] and look at the references therein.\n\t- Remark 4. See Remark 1.\n- Section 5\n\t- Remark 5. See Remark 1.\n- Section 6\n\t- Thm 5. Same remark as per Thm 1. Should the bound depend on $\\bar \\chi$ or $\\alpha$? Also, $h$ depends on $d_i$. Who is $i$? Does it hold for any agent $i$? If so, there could be a minimum over agents.\n\t- Thm 6. The first bound depends on a constant $\\widetilde d$ that is a function of terms $\\bar d_{=i}$ that were never introduced, so it is not clear what that means. Still, it does not depend on $\\bar \\chi$, showing that at least one between the upper and this lower bound is loose. In the second bound, I finally see the form I was expecting. If I had to make an educated guess, I would say that this is the correct rate and I would recommend trying to extend this result to the general case and finding an algorithm that matches it (or tightening the analysis of Delayed MP-UCB, if possible).\n\n\n[1] Della Vecchia et al. An Efficient Algorithm for Cooperative Semi-Bandits, 2021.\n\n[2] Cesa-Bianchi et al. Delay and cooperation in nonstochastic bandits, 2019.\n\n[3] Hsieh et al. Multi-agent online optimization with delays: Asynchronicity, adaptivity, and optimism, 2020.\n\n\nMinor comments\n\nThe writing is not always great. In particular:\n\n- 109. As presented, $\\Delta_2$ could be equal to $\\Delta_1$. If this is the case, there are a bunch of divisions by $0$ scattered throughout the paper. Unless you assume that there is a unique maximizer $\\mu_1$, you should clean up all the expressions in which the sum over $\\Delta_i$ appears at the denominator (it is probably just a matter of summing only on suboptimal arms).\n- 111. I strongly suggest avoiding the use of f and g (this choice makes things gratuitously hard to read), replacing them with reasonably looking big-O's in the theorems where they appear.\n- 111. (not-so-minor comment) In many places in the paper, $o(\\cdot)$ is used where it should really be $O(\\cdot)$.\n- 111. (not-so-minor comment) What is the role of $\\xi$? Based on your upper bounds and the definition of $Q_k^i$ in Fig. 2, it seems that you would be better off by always picking $\\xi$ as small as possible. Is that so? This way, you could get rid of a parameter.\n- 131. size of the smallest possible covering -> size of the smallest possible clique cover\n- 165. (this relates to all other algorithms as well) The clarity would greatly improve if each algorithm had its float rather than having a generic one plus added text mixed with the rest of the narrative.\n- 221. future work. -> future work).\n- 223. Vernade et al. (2017). -> Vernade et al. (2017)).\n- 249. You call your algorithm RCL-AC but point to a float where it is called CHARM. Pick one.\n- Algorithm 1. Why do you need the huge constant 1024?\n- 290. I would consider stating Thm 4 like this since it cannot really be used with the smallest dominating set.\n- 295. delayed(MP) -> Delayed(MP). Also, the font for \"Delayed\" is wrong.\n- 296. I highly recommend restating this theorem in a cleaner, more explicit manner.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The settings considered are not fully fleshed out. I would at least add an Open problem section in which all the open questions are candidly laid out.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "ZcRsWIdMEbX", "reviewer": "Reviewer_9KQ6", "summary": "Cooperative stochastic bandits are studied under several imperfect communications models. Most results study, for each node, the information provided by a clique to which it belongs, resulting in the clique covering number appearing as a factor of log(T) in many bounds. The imperfect communication is also reflected in the regret bounds. There is also an algorithm proposed for perfect communication and a lower bound.  ", "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": "This paper is a mixture of many simple extensions of other analyses. For instance, some results just consist on quantify how much delay one incurs and then one just need to apply well-known results about regret of stochastic bandits under delays. Still, the results provide some value. Although some choices taken seem a bit arbitrary.\n\nFor example, your results say that you can drop messages and pay some quantifiable regret for it. You argue that dropping messages at some particular rate for each node allows to make things more unbiased, but there is no theoretical nor empirical evidence in this paper for such a claim.  The bounds actually indicate that not discarding messages is best to have a better upper bound on the regret.\n\nThese factors you obtain multiplying log T can be quite a high price to pay, can't they? If you don't analyse things in cliques but do over the whole network you might get some extra constant regret in the bound but you will not get these factors in the log T. If you don't have a factors multiplying the log T it means that this part of the regret will not be as large as the corresponding part with the factors until T is exponential in the first case (wrt to some fixed T in the second one)\n\n\nIn thm 4 one needs to have an algorithm that needs to compute a clique covering.\n\nMany lemmas are essentially the same. I feel presentation could be done to compress them into one.\n\nWhat happens with UCB and delays is already well known (Jouliani et al) even if there are errors in the estimates of the means (Martinez-Rubio et al).\n\n(Cesa-Bianchi and Lugosi, 2006) is cited in the appendix but it does not appear in the list of references.\n\n\nMinor typos/suggestions:\n\n+ l307 O(\\sum_{k>1}...) do you mean \\Omega ?\n\n+ Figure 3 there are two \"(a)\"s and no \"(b)\"s\n\n+ l343 comma after [N]\n    + Also, a space is missing before \\forall\n\n+ Algorithm 1: \n    + second line. Add commas between different parameters, like before lambda.\n    + I don't understand why some m's have _i and some don't. I think all of them should not have the _i\n    + Where is the definiton of T_i(m) and \\Delta_{k}^i(m) when m > 0?\n\n+ centered equation of statement of lemma 1 (and others). N_k^i should be mathcal{N}_k^i according to the notation table\n\n+ lemma 2. \"is the clique number of graph G\" -> \"be the clique number of graph G\" \n\n+ Equation (6). The |\\mathcal{C}| could be in the line below to avoid confusion since it really belongs to the third summand.\n\n+ l508 \"this results\" ->  \"these results\"\n\n+ In (26), the second instance of the notation for the clique covering number is wrong.\n\n+ l518 \"$\\forall \\tau > 0$.\" ->  \"$\\forall \\tau > 0$:\"\n\n+ l540 (59). You could mention that you first bound the first 3 summands and then the rest is bounded by the integral.\n\n+ (62) I believe there should be a 3 multiplying (d_i+1) inside of the log in the right hand side of (62). So in the statement of the lemma there should be a 3 as well multiplying the (d_i+1) in the second log (equation (58)). The final bound of theorem 1 should also change accordingly\n\n+ l555 \"similar to proof of\" ->  \"similar to the proof of\"\n\n+ l555 \"We star\" ->  \"We start\"\n\n+ l608 \"by all the agent\" ->  \"by all the agents\"\n\n+ l609 \"is the clique number\" ->  \"be the clique number\". Same in l721\n\n+ l685 There is a missing citation (I presume it would be to Angluint and Valiant 1979)\n\n+ l707 \"satisfy\" ->  \"satisfies\"\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "--", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "MorrmUkTFP", "reviewer": "Reviewer_CiVs", "summary": "The paper studies the cooperative bandit problem. Players can communicate with each other, but the communication can be imperfect.\nThe authors consider three possible imperfect communication--link failures, stochastic delay, and adversarial corruption. For each case, they give algorithms and provide performance guarantees. For the case of perfect communication, they develop an improved algorithm for the case of stochastic delays and give a minimax lower bound.", "questions": "", "limitations": "", "rating": 6, "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": "Communication constraints arise naturally in many real-life applications of cooperative bandits. The study of communication constraints in cooperative bandits is timely and relevant. However, the aspects like delayed and adversarial corruption are looking into separately in bandit literature. Based on this the idea and techniques proposed in this paper look incremental. I have the following questions.\n\n1) Is it possible to show that the regret bound in Thm. 1 is always better than the regret incurred in the case on no-communication setup for all possible $p$ and $p_i$s\n2)  Line 192: Probilites  $(\\marx_{i\\leq N} p_i)p$ and $\\sum_{i\\leq N} (1-p_i*p)$ do not add to one. Why they are treated as probabilities for perfect communication and no-communication regret. If their sum exceeds one, what is common between perfect communication and no-communication regret, and if their sum does not exceed one, which event is missing?\n\n\n------\nPost rebuttal:\n\nI looked into their rebuttals. The authors partly answered my 2nd question, but the answer to the first question is unclear. From their arguments, I do not see how the group performance for any communication probability p>0 is better than the no-communication case.\nPost rebuttal I still feel that this paper is incremental and hence retain my score.\n\n\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper failed to generate sufficient support among the reviewers, who consider the results to be incremental.
Decision: Accept (Poster)