Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the classic multi-armed bandit problem, but in the presence of many cooperating agents distributed over a graph.
main_review: This paper studies the classic multi-armed bandit problem, but in the presence of many agents distributed over a graph. Each agent is a node in a graph, and can receive messages from the neighbors of that node. Every agent is faced with making a decision in every time step, for t = 1...T. Each agent wants to minimize regret, and the goal is to have even the agent with the largest regret suffer a smaller regret than the standard single-agent UCB algorithm. This can be expected because after all an agent comes to possess more information now with the gossipping that goes on because of the network connections. 

This area of cooperating agents on a network playing MAB has seen decent activity recently, with papers developing methods to achieve exactly this objective of smaller regret than the single-agent case. This paper's goal is to ensure that each agent knows nothing more than their neighbors about the graph --- not the total number of nodes or spectral properties of the graph etc. --- and achieve the same. This would make the cooperation model truly decentralized. The paper achieves this with a variant of UCB called Decentralized_UCB (Dec_UCB).

Evaluation:

1) Overall, at least theoretically, it makes an interesting question to ask what happens if agents cooperate in a network and exchange feedback information. So that's a plus.
2) But the model itself is not being introduced in this paper. It has been studied in many papers recently, and the paper's main contribution is to make it fully decentralized.
3) The improvement over UCB can necessarily come only on the constant in front of the log(T) term, and not asymptotically on the log(T) term itself. Also, regarding the improvement in constant, although there is *definitely* work to be done to establish this, overall, given the nature of the setting, it is reasonable to expect that an improvement in constants is going to happen when agents gossip over the network. Therefore, the results are not super surprising. 
4) One interesting part is how the improved constant for the directed graphs case is independent of the number of neighbors, where as it is dependent on the number of neighbors for the undirected graphs case. The authors say that this is also borne out in simulations, although I don't exactly see the simulation plots that vary the number of neighbors.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: A multi-agent pure-distributed (no shared data) algorithm for the stochastic Multi Armed Bandit setting is presented and analyzed.
Regret bounds for different agents connectivity schemes are provided, incorporating the related quantities, namely the diameter for strongly connected graphs and the number of each agent neighbors for undirected graphs. Experiments are conducted to illustrate the superiority of the algorithms and the related bounds over the single-agent UCB1 algorithm performance and the qualitative difference of the performance of the agents in the different connectivity settings.
main_review: The main contribution and novelty of the paper is the pure distributed algorithm and the regret bounds for the different connectivity settings. The (synchronous) algorithm presented is simple and easy to implement, the results are clearly stated, and the experiments nicely illustrate the claims.  The asymptotic performance advantage over the classical UCB1 (or other algorithms in which agents do not share information) is not surprising, nevertheless. Furthermore, the proof sketch of Theorem 1 in the main body of the paper does not provide any insight regarding the incorporation of the characteristics of the connectivity architecture (namely, the diameter of the strongly connected graph) or the constant $L$ of remark 3 into the regret bound (the main contribution of the paper).
Theory-wise,  beyond the improvement in the constant factor $\log T$ (from 8 to $\frac{16}{3}$), also (and probably more) interesting would be a lower bound on the achievable improvement (with a multiplicity of $N$ agents sampling the bandits) and the relation to the better bound of UCB2 (which is indeed mentioned in line 194 but without commenting on the performance or the applicability of the analysis).

typo: should be $X_{i, a_{i}(t)}$ in the formula after line 129.

omission? rewards after "arm k" in line 147.

The main algorithm is clearly presented, probably with some redundancy as the updates appear several times (e.g., after line 148, in  the algorithm description after line 181 and in the pseudocode in appendix A). 
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors propose a novel algorithm in order to extend the UCB1 algorithm to a distributed setting where agents are represented by the nodes of a digraph and these agents are allowed to exchange information with all of their neighbors at each step. The authors prove two performance guarantees, one for a general connected digraph, another one when the graph is non directed.
main_review: 1) The communication model is never really clearly stated. What are the agents allowed to exchange ? Are they forced to communicate with each neighbor at each time step ? How many bits are allowed to be exchanged per round ? This is fundamental in order to assess the applicability of the results: for instance it seems that the algorithm requires to exchange real numbers (as opposed to integers) between agents, which is impossible using a communication network unless some quantization is performed. Also communicating with all neighbors all the time might generate a lot of unnecessary traffic etc.

2) The authors do not provide information theoretic lower bounds on the regret of any algorithm in their setting, nor do they try to compare their performance guarantees to other lower bounds. Therefore it is hard to tell whether or not the performance guarantees of Theorem 1 are interesting.

3) Theorem 1 shows only a constant improvement with respect to UCB1, so that the regret of each node scales as $R_i(T) = O(M\log(T)/\Delta)$ even though nodes are allowed to exchange a lot of information. One would expect the regret of each node to scale as $R_i(T) = O((M/N) \log(T)/\Delta )$ simply based on the argument that, if all agents explore an arm $(1/N) \log(T)/\Delta^2$ times and then broadcast their respective estimates to other nodes (one can always broadcast information to all nodes in at most $N$ communication rounds, providing that the graph is connected), then this arm can be safely discarded. 

4) In Theorem 2, the choice of weights implies that all nodes know the number of their neighbors, as well as the number of their neighbors neighbors. This contradicts the assumptions in the model (unless one first designs an initial step in the algorithm in order to exchange this information as well).

5) Why not use KL-UCB instead of UCB in the algorithm's design ? Especially since they require the same information. Also, the numerical performance of the proposed algorithm should be compared to that of KL-UCB and Thompson sampling, which are the state-of-the-art algorithms for the centralized case.

6) In Theorem 1, the regret bound features a term proportional to $M^2 \sum_{k} \Delta_k$ which can scale like $O(M^3)$. This suggests that the algorithm can sometimes perform much worse than UCB1 since its regret scales like $O(M \log(T)/\Delta )$. Why is that so ? Is this an artifact of the analysis or does this phenomenon really appear in numerical experiments ?

7) In Theorem 1, a number $L$ appears, and Remark 3 bounds this number as a function of the eigenvalue gap of the graph. However, how does $L$ scale with $N$ ? Does there exists networks with arbitrarily large L value (if so this is a problem) ? What is the "worse case" network ?  
 
Minor Comments: the authors claim that their approach is "fully distributed" which is misleading since a "full distributed" setting would be the case where agents are not allowed to exchange any information. Here they do exchange information with their neighbors.

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers a multi-agent cooperative bandit system, where the agents are connected on a graph and can share messages. The arm-pulls of each agent does not interfere with that of the others, but agents can speed up learning by communicating. The paper proposes a parameter-free (no information on the global system) algorithm that each individual agent executes locally. if the graph is strongly connected, the per-agent regret is shown to be strictly better than that of vanilla UCB. If the graph is undirected, the regret of an agent is inversely proportional to the number of neighbors it can share information with. The key algorithmic innovation is to ensure that the number of times an arm is pulled by all agents are within M (a constant which is a hyper-parameter) of each other. This enables agents to arrive at consensus and get low regret
main_review: The paper is very well written and was a pleasure to read and follow along. Multi-agent bandit algorithms that are truly parameter-free are an important line of work and the present paper makes progress on that front. 

My main question is whether in some case (a class of undirected graphs), can the algorithm achieve a regret reduction by a factor of N (the total number of agents), as opposed to N_i, the number of neighbors. Indeed for the complete graph they are the same, but can they be extended to for example expanders or other fast mixing topologies? 

Related to above is a Missing reference :  The article of "The gossiping insert-eliminate algorithm for multi-agent bandits by Chawla et.al. in AISTATS 2021" is relevant to your study. They consider an algorithm that requires knowledge of number of agents, but obtains regret scaling as 1/N times that of the vanilla UCB, "for any undirected graph". Thus the regret guarantee is stronger compared to the present paper, but relies on global information.

More generally, I recommend a survey in the related work along the following lines -" stronger results have been obtained under global information while the present work obtains weaker results without any assumption of global information." 
limitations_and_societal_impact: See above.
review_title: null

Meta-review: The reviewers have all felt that while this is a decent paper, its contribution is somewhat uninspiring: the model it studies is nice but not new, and the improvement it provides over UCB is marginal and not very surprising.  The paper might benefit from a revision that will include stronger motivation and a more rigorous comparison with existing work---I suggest the authors to follow the suggestions of Reviewer w9xA to this end.
Decision: Reject