Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduces a collaborative learning multi-armed bandits formulation, which generalizes the previous stochastic federated bandit with personalization framework. The authors provide two new lower bounds on the sample complexity of pure exploration and on the regret. They also propose a near-optimal algorithm for pure exploration, achieving the lower bound up to logarithmic factors.
strengths_and_weaknesses: Strengths:

- The proposed model is more flexible in terms of how the rewards are mixed, compared with the previous work (Shi et al, 2021a).

- Novel lower bound analyses are provided, which largely answer the open question proposed in Shi et al (2021a). The analysis technique is inspiring not only for federated bandits but also for similar cooperative multi-agent bandits models.

- Inspired by the lower bound analysis, a new algorithm termed W-CPE-BAI is proposed. 

- For the best arm identification formulation, the proposed algorithm is shown to be capable of approaching the lower bound.

- For the regret minimization formulation, a regret lower bound is proved, which largely complements the conjecture in Shi et al (2020a) and further sheds light on the corresponding algorithm design.

Weaknesses:
- Nothing major.
questions: No major questions.
limitations: The authors did a great job explaining the limitation in the theory side, and the work does not have negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Authors consider the model that there are $M$ agents and $K$ number of arms. At each round, each agent samples an arm (or is idle) and gets a reward. They assume that the agents share a known weight matrix and the objective function is to find the best arm which has a maximum expected mixed reward. The expected mixed reward of an arm for each agent is the summation of the weighted mean rewards of the arms. Therefore, the agents need to communicate with other agents to share information about their local rewards (collaborative learning). 

They provide a lower regret bound in Theorem 1 for the best arm identification problem, in which the goal is to find a $\delta$-correct strategy while achieving a small exploration cost and small communication cost. Then they propose an elimination-based algorithm achieving a near-optimal exploration cost bound. The algorithm computes the number of required samples for each arm and agent, using the oracle allocation from proxy mean reward gaps. Based on the rewards, it estimated the weighted mean reward and eliminate bad arms.  With updating gap estimators, it repeats this process. Lastly, they provide a lower regret bound of this problem.

strengths_and_weaknesses: **Strengths**
- They propose a novel problem in bandit research. In their problem, collaborative learning by sharing information with agents is necessary, which makes the problem non-trivial.
- They provide a lower bound for exploration cost and propose an algorithm achieving near-optimal exploration cost while requiring a small communication cost. 

**Weaknesses**
- Even though the problem is novel considering collaborative learning and the paper provides some motivation examples, I have a concern about whether there exist convincing applications in the real world. This is because the purpose to find a weighted maximum arm for each agent may not be convincing in a situation where each agent can learn its own best arm individually.  

- For the required samples for each agent and arm in Lemma1, it would be better if the paper provides some detailed interpretation of the influence of weight value on the number of samples such as where $w^2$ comes from.

- Also, it would be better to discuss how to compute oracle $P$ (definition1) efficiently to be used in the algorithm.

- In the regret bound in Theorem 2, $log(1/\Delta)$ could be large in the worst case, which makes the bound far from the lower bound.


questions: 
- In lemma 1, I was wondering the reason why the required samples are influenced by $w^2$ rather than $w$?

- $log(1/\Delta)$ is not familiar to me in performance bounds. Could you explain why this term is hard to remove? or whether this term is significant or not for the algorithm performance?

- In practice, could we compute the oracle $P$ in definition 1 efficiently?


limitations: I believe that it would be better if the paper could provide more convincing motivation examples in which agent-dependent weighted arm rewards should be considered.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a collaborative bandit model in which each player seeks to identify an arm that maximizes an arbitrary weighted sum of the rewards of the players. An algorithm is proposed that is shown to be nearly optimal. The model is a generalization of a recently proposed model, for which a bounded-regret algorithm was previously given, and the paper also establishes a regret lower bound for the generalized model.

strengths_and_weaknesses: The main strength of the paper is the analysis of the algorithm. The algorithm is obtained by relaxing an optimization formulation that characterizes the optimal number of rounds to identify the best arm with high probability. A similar trick is used to obtain the regret bound.

Nominally, introducing the generalized model is also a contribution. But, the main weakness of the paper is that I really cannot think of a setting that actually has the key feature of this model: namely, that the player wishes to choose an arm that does not correspond to that player's actual observed reward distribution. What would make sense to me is if the players had reward distributions that were somehow known to be similar, so that perhaps by sharing estimates they might be able to more quickly estimate their own rewards. To me, this is a more appropriate analogue of "personalization" in which the parameters (estimates) of the collective can be used as a starting point to reach a more accurate set of parameters for an individual player. (More strongly, in most collaborative bandit formulations, the problem is set up so that the players all have the same reward distributions.) But in such a case, the players can still simply solve their independent bandit instances at a possibly greater cost. The central feature in this model (like the previous "personalization" work), by contrast, is that it has been designed so that the players must communicate, since the players need to identify an arm that isn't determined by their
observed rewards. While this indeed hadn't been considered previously, in this case I think the reason is in large part the lack of motivation to consider this setting. I certainly don't agree with the claims on lines 67-78 about potential applications; in each case, the success rate for an individual user or a therapy at an individual center corresponds to the reward distribution observed for that
specific user or at that specific site. I don't see any compelling reason to choose an arm just because it has higher rewards elsewhere.

So, in summary, the question to me is whether the technical novelty outweighs the lack of a compelling motivation for the model.


questions: Can you give a setting that is faithfully captured by the proposed model that was not already captured by a previous model?

Can you suggest a concrete family of problems beyond the ones considered in this work that might be addressed by the techniques developed here? (Note: I don't consider the top-N variant of the best arm problem in this model to be substantially more natural.)

limitations: It's fine. I'm sure that a personalized bandit algorithm could be misused to addict users to continue engaging with content platforms -- indeed, as I understand it, this is already being done. But I don't think the paper needs a "don't be evil" warning label or anything like that.
review_title: null

Meta-review: metareview: The paper introduces a new formulation for a multi-player MAB motivated by federated learning. The reviews are all positive and agree that the paper is a significant contribution.
confidence: Certain
Decision: Accept