Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the cooperative bandit problem. Players can communicate with each other, but the communication can be imperfect.
The 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.
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.

1) 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
2)  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?


------
Post rebuttal:

I 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.
Post rebuttal I still feel that this paper is incremental and hence retain my score.







limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
----------

TLDR: The authors study three variants of a cooperative bandit setting with imperfect communication. 

Base 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. 

Variant 1: each message can fail to reach its recipient with probability $1-p$.

Variant 2: messages arrive with a stochastic (but deterministically bounded) delay

Variant 3: the real numbers shared in the messages are corrupted with a small perturbation

The authors introduce and analyze simple algorithms for these three variants. 
They 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.

The theoretical results are complemented by some experiments.
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.

Discussion

The 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.
In particular, I find all three variants studied in this paper to be worthy research directions and of interest to the NeurIPS community.

My main issue is the novelty. 
The 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.
On 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).
Overall, 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.

Questions/issues on specific sections.

- Section 3. 
	- 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?
	- 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
	- 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)?
	- Thm 2. Same question of Thm 1 on $\bar \chi$ vs $\alpha$.
	- Remark 3. Similar remark and question as for Remarks 1 and 2.
- Section 4
	- Why dropping message-passing? Inconsistent approach.
	- Applications of delayed analysis in cooperation already appeared in recent work. I suggest adding a reference to [3] and look at the references therein.
	- Remark 4. See Remark 1.
- Section 5
	- Remark 5. See Remark 1.
- Section 6
	- 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.
	- 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).


[1] Della Vecchia et al. An Efficient Algorithm for Cooperative Semi-Bandits, 2021.

[2] Cesa-Bianchi et al. Delay and cooperation in nonstochastic bandits, 2019.

[3] Hsieh et al. Multi-agent online optimization with delays: Asynchronicity, adaptivity, and optimism, 2020.


Minor comments

The writing is not always great. In particular:

- 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).
- 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.
- 111. (not-so-minor comment) In many places in the paper, $o(\cdot)$ is used where it should really be $O(\cdot)$.
- 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.
- 131. size of the smallest possible covering -> size of the smallest possible clique cover
- 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.
- 221. future work. -> future work).
- 223. Vernade et al. (2017). -> Vernade et al. (2017)).
- 249. You call your algorithm RCL-AC but point to a float where it is called CHARM. Pick one.
- Algorithm 1. Why do you need the huge constant 1024?
- 290. I would consider stating Thm 4 like this since it cannot really be used with the smallest dominating set.
- 295. delayed(MP) -> Delayed(MP). Also, the font for "Delayed" is wrong.
- 296. I highly recommend restating this theorem in a cleaner, more explicit manner.
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_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.  
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.

For 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.

These 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)


In thm 4 one needs to have an algorithm that needs to compute a clique covering.

Many lemmas are essentially the same. I feel presentation could be done to compress them into one.

What 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).

(Cesa-Bianchi and Lugosi, 2006) is cited in the appendix but it does not appear in the list of references.


Minor typos/suggestions:

+ l307 O(\sum_{k>1}...) do you mean \Omega ?

+ Figure 3 there are two "(a)"s and no "(b)"s

+ l343 comma after [N]
    + Also, a space is missing before \forall

+ Algorithm 1: 
    + second line. Add commas between different parameters, like before lambda.
    + I don't understand why some m's have _i and some don't. I think all of them should not have the _i
    + Where is the definiton of T_i(m) and \Delta_{k}^i(m) when m > 0?

+ centered equation of statement of lemma 1 (and others). N_k^i should be mathcal{N}_k^i according to the notation table

+ lemma 2. "is the clique number of graph G" -> "be the clique number of graph G" 

+ Equation (6). The |\mathcal{C}| could be in the line below to avoid confusion since it really belongs to the third summand.

+ l508 "this results" ->  "these results"

+ In (26), the second instance of the notation for the clique covering number is wrong.

+ l518 "$\forall \tau > 0$." ->  "$\forall \tau > 0$:"

+ l540 (59). You could mention that you first bound the first 3 summands and then the rest is bounded by the integral.

+ (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

+ l555 "similar to proof of" ->  "similar to the proof of"

+ l555 "We star" ->  "We start"

+ l608 "by all the agent" ->  "by all the agents"

+ l609 "is the clique number" ->  "be the clique number". Same in l721

+ l685 There is a missing citation (I presume it would be to Angluint and Valiant 1979)

+ l707 "satisfy" ->  "satisfies"

limitations_and_societal_impact: --
review_title: null

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