Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper looks into the problem of cooperatively determining the best arm in kernel bandits. The study builds on the prior CoPE formulation, which emphasizes the conventional MAB model, while retaining the fundamental communication concept. This paper makes two contributions: 1) it generalizes earlier work to the kernel bandit problem space, and 2) it produces nearly-optimal algorithms for both fixed-confidence and fixed-budget scenarios.

Minor:

It is better if the author(s) could provide line numbers in the manuscript.
strength_and_weaknesses: Strength
*  This paper is a valuable extention of previous CoPE formulation. Each agent may experience a varied environment (reward functions) because of the characteristics of kernel bandits.
* Strong and comprehensive theoretical analysis is provided.

Weaknesses
* In contrast to CoPE, where the sample complexity is defined as the greatest number of samples used per agent, the purpose specified in this study is a little bit different. The sample complexity is defined in this study as the average number of samples across all agents, which makes the speed-up definition less strong than that in CoPE. Since the running duration is determined by the one running the longest, I believe the definition in CoPE is more reasonable practically.
* It is better if the authors could put the experiment results in the main paper
clarity,_quality,_novelty_and_reproducibility: This paper is written well and the theory established looks comprehensive and strict. It is the first one trying to identify the best arm in kernel bandits collaboratively using the communicaiton model formulated in CoPE.
summary_of_the_review: This paper is a valuable extention of the previous work CoPE and it is the first one trying to identify the best arm in kernel bandits collaboratively using the communicaiton model formulated in CoPE. Additionally, it provides nearly-optimal algorithms. Overall I think it is a nice paper. However, I am a little bit worried about the goal of the problem, which tries to optimize the average number of samples per agent instead of the maximum one. I am happy to raise my score if the author(s) could provide practical examples to motivate this goal.

After rebuttal
--------------------------
The author(s) have promised to include the discussions regarding the difference between the goal of this paper and that of CoPE, hence I would like to increase my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors prefer a new kernel bandit model where multiple agents collaborate to complete different but related tasks with limited communication. The authors devise a novel communication scheme and design algorithms for fixed-confidence and fixed-budget objectives. 
strength_and_weaknesses: Strengths
- Model is useful for neural architecture search problems. 
- Algorithms achieve communication optimality. 

Weaknesses
- Lack of experiments for this model in the main paper. Would be great to see applications in the main work. 
clarity,_quality,_novelty_and_reproducibility: The work and theorems are high quality and clear. Code is provided for reproducibility. 
summary_of_the_review: This paper provides novel algorithms for a well-founded and novel problem setting, which provide a clear contribution. While experiments are not the primary focus of the paper, it would be nice to see more experimental evaluation in the main paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work focuses on a new problem: collaboration pure exploration with multiple tasks and general reward structures. It explores both fixed-confidence and fixed-budget settings. Nearly-matching upper and lower bounds on sampling and communication complexity are derived.
strength_and_weaknesses: Strength:
1. The paper is easy to follow and provides a thorough overview of existing works.
2. The motivation of this work is convincing: some tasks such as objective detection and object tracking are related but different, and they can be viewed as a possible application of the proposed model.
3. The explanation and analysis of the proposed algorithm are detailed.

Weaknesses:
1. Is it possible to provide some numerical results?
clarity,_quality,_novelty_and_reproducibility: The paper is in general clear and is with novelty. I believe that it makes a contribution to the bandit study.
summary_of_the_review: This work clarifies its motivation and formulation in the beginning. After that, it studies the pure exploration problem for both fixed-confidence and fixed-budget settings. The nearly-matching bounds convince the efficacy of the proposed algorithms. However, numerical results are appreciated to even improve the work.

========================

After rebuttal: thanks for your reply. You may consider to involve the experiment results in the first version next time.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper the authors study collaborative exploration in kernel bandits. This problem is very general, and it generalizes a lot of works done in collaborative exploration. Due to the use of kernel, which allows non-linear structure of arms, it generalizes the works done on collaborative exploration in MAB and in linear bandits. Moreover, this work allows agents to collaborate on different tasks: the set of arms and the best arm are not necessary the same for each agent, as well as the features of arms.
The authors study the both exploration problems: fixed confidence and fixed budget. They propose and analyze an algorithm for each problem setting. They notably prove near optimal sample complexity and a near optimal number of communication rounds in the fixed confidence setting. Last but not least for the confidence setting, they provide a lower bound of the near optimal number of communication rounds that generalizes (Tao et al 2019) to structured rewards. Finally the same job is done for the fixed budget setting.

strength_and_weaknesses: The studied problem is very general. The paper is technically sound. The analytical results are convincing.

The paper is quite difficult to read. This is largely due to the complexity of the studied problem. 
However, sometimes some notations are not well introduced. This complicates the task of the reader. For instance at the end of page 2 \tilde{X} is the set of arms, while in page 3 X_v is also the set of arms for agent v. The reader learns at the end of page 3, what is the difference between \tilde{X} and X, \tilde{X} = Z x X, where Z is the task feature space…
In Algorithm 1, the authors should emphasizes that t is not the standard time index, but the index of communication rounds. May be by simply writing line 3, for round r = 1,2,… do, could help the reader to understand the algorithm.

This paper has a lot of results, including some experiments, but only the analysis of fixed confidence exploration problem is in the main paper, without any experiment. 

clarity,_quality,_novelty_and_reproducibility: On the novelty side, the paper generalizes some well-known problems. The idea of communication rounds is not new, but the authors add a specific and new kernelized estimator to reduce the dimension of sent messages. The communication lower bound for structured arms is new and general (it also holds at least for multi-armed bandits and linear bandits).
summary_of_the_review: It is a theoretical paper that generalizes some well-known problems and results. The paper is quite hard to read. The authors could help a little bit more the reader. That being said, I clearly vote for its acceptance.

________________________
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 collaborative pure exploration in kernel bandits and proposes two algorithms under fixed confidence and fixed budget respectively. It also provides theoretical analysis for the proposed algorithms. 

Strengths:
Nearly matching upper and lower bounds in both sample complexity and communication complexity are established. 

Weaknesses:
Lack of thorough experiments in the main paper (before revision).

justification_for_why_not_higher_score: This is mostly a theory paper, and its audience might be limited in ICLR.
justification_for_why_not_lower_score: There is unanimous support to accept this paper after the author's response.
Decision: Accept: poster