Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies distributed multi-armed bandits with the goal of minimizing the largest regret incured among all the agents. This work makes two contributions: First, it suggests a different objective—minimizing individual regret rather than group regret—motivated by real-world applications. Second, it proposes a new algorithm—UCB-TCOM—with almost optimal bound for both individual and group regret. In addition, the new approach only incurs communication cost of $O(\log \log T)$ times.
strength_and_weaknesses: Strength
* The new objective is strongly supported by practical applications. 
* Numerical simulations with real-world data are offered to verify the proposed algorithm
* The paper is written well.

Weaknesses
* It seems to me the key technique to lower the communication complexity from $O(\log T)$ to $O(\log \log T)$ is the doubling technique or observation-buffering broadcast mentioned in the paper, which is a well-known technique in bandit literature. It would be preferable if the author(s) could explain in the study why establishing the intended outcomes was challenging.
--------------------

After rebuttal

The author(s) have added discussions regarding the challenge raised during the proof of the communication complexity. And I have raised my score.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written, in my opinion, and it is organized effectively for ease of reading. Despite the fact that the technique is not new, the proposed goal is intriguing and may have real-world implications.
summary_of_the_review: This paper is well-motivated by real-world applications. The author(s) have proposed a new algorithm with nearly-optimal individual and group regret. Besides, it incurs only $O(\log \log T)$ communication times. However, the techniques used are not brand-new. I struggle to understand how challenging it is to establish the theory in the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work focuses on a cooperating learning version of the classical multi-armed bandit problem, where M agents play the same problem instance over T rounds. Agents can communicate their observations through global broadcasts. The authors propose an algorithm that needs O(log log T) communication rounds to achieve logarithmic individual as well as group regret.
strength_and_weaknesses: The main contribution appears to be showing that a factor of M improvement in group as well as individual regret is possible using only O(log log T) rounds of (broadcast) communications between the M agents. The improvement is relative to the scenario where the agents do not communicate and simply keep playing their own instance, oblivious to the rewards accrued by others. The communication efficiency of O(log log T) is achieved by sharing information about (empirically) sub-optimal arms as opposed to optimal ones, which I find to be a very neat idea.


clarity,_quality,_novelty_and_reproducibility: Typo: In line 292, the lower bound is on group regret (not individual); the superscript 'ind' should be removed I reckon?

Is factor of M the best possible improvement? In particular, how does group as well as individual regret compare with lower bounds for the scenario where an entire vector of M reward realizations is broadcasted per period? This, in my opinion, is a more interesting statistical baseline compared to the no communication one.

Can you black-box the algorithm into communication and learning modules while preserving regret guarantees? This begs the question, is communication efficiency a fundamental property of the algorithm itself? Can you comment on whether Thompson Sampling might work using the same broadcast signals and the same broadcast rate?

Is it possible to trace out a Pareto frontier of regret (individual/group) vs. communication overhead?
summary_of_the_review: The paper is generally well written and a pleasure to read. Appears to be technically sound, comprehensive in literature survey, and meaningful in contribution as it improves upon extant baselines by a considerable margin. It would be great if the authors could address or at least remark upon the questions raised earlier; that would really cement the contributions well and make it accessible for a more general audience. Overall, I vote for an acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper study the collaborative MAB, where agents can communicate together to handle the same MAB problem. The authors propose a new notion of regret: the individual regret is the maximum regret over the players. This notion of regret is given in addition to the usual notion of regret. This regret could be related to the notion of fairness, since the closer the individual regret to regret the greater the fairness is. 
In collaborative MAB the goal is to minimize the regret but also the communication cost. They provide a communication policy that has a communication cost in O(log log T) and that benefits from a near-optimal regret bound for both notions of regret. In some experiments, they show that their algorithm (UCB-TCOM) provides a good compromise between group regret and individual regret, while they obtain a low communication cost, even if it is not the smallest. 

strength_and_weaknesses: The proposed communication policy is sound. The analysis and the experiments are well done. 
However, the paper presents some shortcomings. 

1/The definition of both regrets seems incorrect. Indeed, there is an expectation in the regret, while there is no random variable inside: \mu(A^i_t) is the mean reward of arm chosen by agent i at time t. Did the authors take the expectation over the choices of players? Why not using the usual definition of pseudo-regret (cumulative difference between the expected reward of the optimal arm and the expected reward of the chosen arm)?

2/ In comparison to DEP2, UCB-TCOM is outperformed in two metrics (group regret and communication time). So the only advantage of UCB-TCOM is that its individual regret is smaller. So in the comparison, individual regret is crucial, and it has to be better motivated. May be by enhancing fairness ?

Minor comments:
Table 1 presents an error: the communication time is in O(1) for DEP2.
The authors could refer some works done in the collaborative exploration setting. Indeed, explore then commit algorithm can also reach a near-optimal regret (Garivier et al 2016), and despite different contexts, the two following papers use similar ideas: doubling trick for communication policy in (Hillel et al 2016), communicating only about bad arms in (Feraud et al 2019).

(Hillel et al 2013) Distributed exploration in multi-armed bandits, NeurIPS 2016. 

(Feraud et al 2019) Decentralized exploration in multi-armed bandits, ICML 2019.

(Garivier et al 2016), On explore the commit strategies, NeurIPS 2016.

clarity,_quality,_novelty_and_reproducibility: Despite some weaknesses, the paper is very well written. 
The idea used in TCOM is well known: the doubling trick. It has already been used for minimizing communication rounds (Hillel et al 2014). However, the present paper introduces some novelty that are sound.

summary_of_the_review: Overall, despite some shortcomings that can be fixed, this paper is technically sound, well written, and presents some novelties.
_____________________________
I read the rebuttal and I thank the authors for their answers.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies distributed multi-armed bandits with the goal of minimizing the largest regret incurred among all the agents. This is a novel and meaningful objective. The authors proposes an algorithm CMA2B which is shown to be near-optimal and furthermore, the amount of communication is O(log log T) where T is the number of decision rounds. 

Generally, the reviewers were convinced about the novelty of the setup and contributions and all recommended acceptance. This paper is a welcome addition to the bandit literature. It would be good if the authors can think about the question of the Pareto optimality (tradeoff) between the regret (individual/group) and the communication overhead. I believe such questions may have been addressed in the bandit-federated learning literature. 
justification_for_why_not_higher_score: I don't think there's a significant breakthrough in terms of techniques but the problem formulation is nice and cute. 
justification_for_why_not_lower_score: There's no reason the paper should be rejected. Hence, it should be accepted.
Decision: Accept: poster