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: In this work, the authors introduce and study a novel variant of the multi-armed bandit problem, where side-information on the similarity (in mean reward) among different arms is provided to the decision-maker. In particular, the authors consider a weighted graph on the arms/nodes, where the weight of each edge indicates how similar the two "adjacent" arms are. For this model, the authors provide a novel algorithm for the problem of best-arm identification, for which they provide associated guarantees. By providing a lower bound, they show that their algorithm achieves minimax optimality for an interesting class of instances. A variant of the algorithm for the problem of \zeta-best-arm identification is also provided. Finally, the authors evaluate the empirical performance of their algorithm on synthetic and real data.

strengths_and_weaknesses: STRENGTHS:

- Overall, the paper is very well-written and well-organized (including parts of the Appendix).

- The proposed model is (to the best of my knowledge) novel, and applies to several scenarios where the number of actions is very large, yet some form of similarity structure between "adjacent" actions is available (e.g., social networks).

- The proposed algorithm cleverly exploits the given graph structure and achieves minimax optimality a special class of natural problems.  

WEAKNESSES:

- Assuming some form of graph-encoded similarity structure is a reasonable assumption (e.g., all friends in a social network can have unit weight). However, knowledge of the smoothness parameter \epsilon on the graph seems critical for the perormance of the algorithm, which, in my opinion, weakens the obtained results.
questions: - Could the authors comment on how the smoothness parameter \epsilon scales (or should naturally scale) with the number of arms? Specifically, consider the example of a (dense) unit-weight random graph, where each edge appears with probability p = 0.1. What is \epsilon in that case? To rephrase, how \epsilon increases by adding a new arm to the graph? How this affects the provided guarantees compared to the case where no similarity structure is assumed?


- Personally, I would move the section on $\zeta$-GRUB to the Appendix (I do not think it contributes much to the main part). This would free some valuable space to add the pseudocode of GRUB and/or maybe some proof sketches of the main results.


- Maybe it would be reasonable to discuss the line of work "Online Learning with Gaussian Payoffs and Side Observations" (NeurIPS '15) by Wu et al. and "Asymptotically-optimal Gaussian bandits with side observations" (ICML'22) by Atsidakou et al. 
The side information structure assumed there (weighted graph) bears some similarities with the one considered in this paper.
limitations: Yes
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: The paper tackles the problem in which a MAB setting with a pure-exploration goal having a large number of arms, has also some structure among the arms by means of a similarity matrix stating how much the expected value of the arms can differ from each other. They propose an algorithm able to exploit such a structure and analyse the problem in terms of lower bound complexity. Finally, they show that exploiting the structure of the graph provides significant improvements over the standard MAB algorithms.
strengths_and_weaknesses: The topic analysed by the paper is interesting. The setting is clear, even if it is not clear how often the assumption required by the formulation of the problem is satisfied in real settings.

The paper requires some proofreading to polish it from orthographic errors. I mentioned a few of them in the minor section. Overall it is clear and well structured.

Overall, the paper is not self-contained. In my opinion, the authors should have done a better job in the identification of the crucial points of the paper, avoiding repetitions and inclusion of the elements which are crucial to having a self-contained paper. For instance, you decided to defer the parameters c_1 and c_2 to the appendix. The same holds for the pseudo-codes of the algorithms and the definitions of the sampling strategies.

Minor:
Line 85 (and following comments) State that "potentially without playing it even once!" is not necessary.
Line 155: "natural" it is not clear to me what you mean with "natural"
Line 159: sub-optima -> sub-optimal
Line 178> utilization -> use
Line 217: e.g -> e.g.,
Line 221: atleast -> at least
Line 279: in mean -> in terms of expected reward
questions: Could you give more details on the settings in which the smoothness assumption is satisfied? How it is possible to infer \epsilon?

What happens if the algorithm is used on settings in which the assumption about the smoothness of the problem?

Did you compare your approach also with Thompson Sampling?
limitations: I do not foresee limitations and potential negative societal impacts of this work.
review_title: null

Meta-review: metareview: All reviewers agree on the merits of the work. 
confidence: Certain
Decision: Accept