Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the decentralized multi-armed bandit problem and proposes an algorithm, appealing to the ideas of batched exploration and adaptive communication, which has the same order of regret as the centralized version of the problem. 
main_review: The decentralized heterogeneous bandit problem is important and hard. Both the ideas of batched exploration and adaptive communication are interesting. My concern of the paper is as follows. 

The paper aims to close the gap in regrets between the centralized and decentralized settings. However, the proposed algorithm heavily relies on centralized design. For example, there is a leader among all the agents which can collect all information from all agents and perform a centralized optimization task at each round. Another example is that the batched exploration procedure also depends on a network-wise pieces of information, like the smallest arm counter. With these, it is not reasonable to me to call the algorithm decentralized. More importantly, with allowing such information collection and processing in a "center", it can be expected that the proposed algorithm can perform as good as (or even outperform) the centralized algorithm. 

Update Sep 6: Thanks the authors for their responses.
 
The paper claims to close the "gap" between centralized and decentralized regrets. However, the authors to some extend "mixed" the existing literature. The original decentralized setting does not allow communication among the agents (e.g. Kalathil et al. 2014 and Nayyar et al. 2016 in the Related Works section, as well as the NIPS paper Bistritz and Leshem, 2018 in the authors' response); this is why the gap exists in my understanding. Now, the paper follows some recent development and allows communication among the agents. To me, this significantly changes the game. I would call it a distributed/cooperative setting, since it requires that all the agents coordinate (have to send correct information). In the vast distributed convex optimization (which allows communication among the agents and the communication graph can be sparse, as long as connected) literature, it is known that distributed convex optimization algorithms can achieve the same order of convergence rate as the centralized counterpart; the difference is in the constant coefficient level, which depends on the graph connectivity. Intuitively, the more connected the graph is, the faster (better constant coefficient) the convergence is. Since the current paper makes use of a leader-follower scheme in communication, it essentially corresponds to a complete graph in a distributed setting. So it is not surprising to me that it can achieve the regret close to the centralized setting. Also, from a distributed algorithm design point of view, assigning a unique ID to each agent, as the current paper does, is a very strong assumption; that is why in most distributed optimization algorithms, there does not exist a "leader".

With the above in mind, my understanding of the paper contribution is how to design a communication efficient scheme between the leader and each follower to achieve an "optimal" tradeoff between communication and system regret, instead of closing the "gap" between centralized and decentralized regrets, because it essentially considers a very special distributed setting. Note that transmitting one bit is essentially different from transmitting more bits as the former implicitly requires establishing new communication channels. 

From my focus point of view (the distributed/decentralized setting), the paper's scope is limited and the title could be misleading, so I keep my score 5.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes the BEACON algorithm under Multi-player MAB settings. The authors make use of the ideas in combinatorial-MAB area and implement batched exploration, in which they choose an update rule for the arm counters to sufficiently but not excessively explore the arms. Then, they  extends the adaptive communication to adaptive differential communication, also, the communication only happens when the sample mean is sufficiently precise. With the combination of these strategies, the BEACON achieves the regret lower bound while requiring less assumptions (unknown horizon, non-linear reward functions, etc.) than prior works in the area. 
main_review: Originality: The combination of implicit communication for distributed operation with the use of centralized UCB (CUCB) seems like the main novelty of the work. The idea of using differential encoding to reduce the communication load, while natural, is useful. 

Clarity: The paper is very clearly written and well organized, even though the notation is heavy, the clear presentation make it sufficiently easy to read and understand the paper. The authors explain the key ideas very clearly. The literature review appear sufficient as well. In particular, the related works are carefully discussed and compared to emphasize the contributions.

Significance: The proposed BEACON achieves the regret lower bound while requiring less assumptions than earlier works. Also, the possibility of allowing the reward function to be non-linear may be significant. While these technical results appear solid, I am not convinced in the importance of the problem setting. The need for implicit communication amongst distributed agents via collisions is quite artificial and forced. I do not see strong justification for enforcing such a constraint especially in a cooperative setting such as the one in this work. It may be more acceptable is a non-cooperative setting where users have self-interests. However, this would make the existing design useless, as it assumes thrust. 

Minor question: why is the expected system reward V_{\mu,S} given by the sum_m \mu_{s_m,m} in line 84? Shouldn't there be an expectation over the  no-collision indicator?

limitations_and_societal_impact: As the author pointed out, the work utilizes a combinatorial optimization ORACLE, which can be infeasible when the scale is large. There aren’t any negative societal impact of their work that I can identify.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies heterogeneous multiplayer bandits (with collision sensing). Designing a new communication protocol, it proposes a batched and decentralized version of CUCB to reach centralized performances in heterogeneous multiplayer bandits.
The proposed algorithm can also be extended to more general reward functions, similarly to CUCB in combinatorial bandits.
main_review: I have read the other reviews and the authors' answers and maintain my positive opinion about this work.

-----------------------------------------

I find this work very interesting: nicely combining combinatorial bandits and multiplayer bandits was necessary to reach near centralized bound in the heterogeneous setting and is done nicely here, thanks to the differential communication protocol (which leads to log(T) communication rounds instead of log^2(T)).

The paper is well written, although we feel that the authors struggled to fit the 9 pages limit (eg it contains many footnotes): the description of the algorithm is very clear and the analysis seems to follow from the analysis of CUCB once the communication protocols are carefully handled. I have no major concern regarding this work, hence my overall score. 

- Note that if the horizon T is a priori known, using epochs of length 2^p log(T) (instead of 2^p) leads to a constant (in T) number of communication phases for existing ETC algorithms. Could such an improvement be combined with differential communication to decrease even further the communication cost? This could be of great interest, especially without sensing information, as sending a single bit here has a cost of order log(T)

------- minor comments --------

- I think the "matching" denomination is poorly chosen, as matching usually means that no arm is assigned to several players (ie it corresponds to the set S_b here)

- line 83: V_{mu, S} is not well defined in case of collisions. It is here suggested that collisions do not degrade the total reward.

- The length of communication is random (and thus unknown) to the different players. This is an additional challenge of the algorithm that is only mentioned in the Appendix. If the authors manage to save some room, I suggest to at least mention this additional difficulty in Section 3.3

- equation (3): in the last formulation, the second term is not necessary since it is dominated by the first one

- in table 1: I think it would be better to remove the tilde on O for all the algorithms that do not incur extra log(K) terms

- Section 6 does not really seem at its right place in the current structure. I would rather postpone it after the experiments (or before the conclusion)
limitations_and_societal_impact: Not concerned
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Overall, this paper introduces a new algorithm BEACON for multi-agent multi-armed bandits that closes the gap between the state-of-the-art upper bound and information theoretic lower bound of the regrets by implicit communication via adaptive differential communication protocols and efficient exploration via UCB-based algorithms. In addition to the existing case where the system-level reward is a linear combination of individual rewards, BEACON also tackles the general cases where the combination is non-linear, obtaining a regret bound of O(log T). Experiments show that BEACON significantly outperforms state-of-the-art benchmarks in decentralized bandits.  
main_review: Strengths:
1. The paper is well-written, with all the sections clearly explained and the contributions clearly stated. The authors have made comprehensive comparisons against state-of-the-art benchmarks from prior work, and have clearly stated future directions from the work.  

2. The contributions of this paper to the research community are evident and non-trivial. Using batch processing along with implicit communication protocols, BEACON not only closes the regret gap to information-theoretic lower bounds, but also generalizes to general reward functions with fewer assumptions/prerequisites.  

3. Proper experiments have been conducted, with the necessary comparisons with existing state-of-the-art bandit algorithms included in the paper. 

Weaknesses:
1. Rather than putting all discussion of the connection between Combinatorial MAB and MP-MAB into the supplementary materials, it would be beneficial to provide a summary as to how MP-MAB could be reduced to/relates to a CMAB problem. What does ‘the largest amount of matchings’ stand for in Section 3.1? The descriptions at this point are inadequate and don’t provide enough intuition.

2. It is not immediately clear why the differential bit representation in the ADC protocol would help reduce the overall (expected) regret at each communication epoch to O(1). It would be ideal to include a brief description(at least intuitively) how truncating bits of the intra-epoch mean difference would result in regret reduction. 

3. Are there any constraints with respect to the number of players each player is able to communicate with? It appears from the paper that BEACON sets constraints on the number of times a player(as leader) communicates with other players(as followers ) during communication, but not who to communicate with. What does the underlying communication graph amongst players look like? Some additional clarification would be helpful for further understanding.

Overall, my recommendation would be a ‘6, marginally above’. I’d be happy to revise my score, if the authors address my concerns accordingly. 

limitations_and_societal_impact: Limitations:  BEACON depends on an oracle solver for combinatorial optimization, a requirement of which might make BEACON computationally infeasible when the numbers of arms and players becomes extremely large. 

Societal Impact: Not applicable. The paper is largely algorithmic and centers on theoretical justification of an abstract model. If any, the potential impact of this paper to the research community would be beneficial as it provides new methods for cooperative bandit decision making.
review_title: null

Meta-review: This paper looks at the multi-player multi-arm bandit problem, with heterogenous rewards. This specific problem of reaching the centralized case with  decentralized protocols was still open, while it was settled with homogenous rewards.

This result requires combining additional, non trivial techniques from combinatorial bandits amongst others, hence hitting the acceptance bar.






Decision: Accept (Poster)