NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID: 6497 SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits

### Reviewer 1

Originality: This paper invents the trick of implicit communication through collisions for synchronization case and it is used in subsequent papers. Also, it proposes the first algorithm without synchronization, which is an unrealistic assumption in real case. Quality: The proofs seem to be right and it clearly support the theorem given and the claim that the existing lower bound has potential problem. Clarity: The paper is well-organized. Significance: The paper gives a useful trick for synchronization case which uses the information deduced from collisions and explains why the previous lower bound has potential problem. It also invents the first algorithm with log regret in dynamic setting, which is more realistic.

### Reviewer 2

Originality: The paper studies the multiplayer bandit problem and is largely based on the Musical Chairs paper (Rosenski et al.). The fact that the players can use the collisions to their advantage, and that the resulting algorithm enjoys a similar regret bound to the centralized setting, is nontrivial. Quality: The results are sound. Clarity: The paper is well-written overall. However, the authors do not explicitly address the fact that SIC-MMAB2 and its analysis are only found in the supplementary material. Significance: The theoretical results are important as they contradict two previously known lower bounds. --- After rebuttal --- I have read the authors feedback and am satisfied with the fixes planned for the camera-ready version. I wholeheartedly suggest the papers acceptance.