Venue: NeurIPS 2022 Conference

Reviews:

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 current paper studies the distributed kernelized bandit, a generalization of the distributed linear bandit. Different from the distributed linear bandit [25], one cannot upload/download sufficient statistics (i.e., Gram matrix) for total $O(\log T)$ communication rounds, since for later communication rounds, sending either the raw data (size of $dT$ to resume the sufficient statistics) or the original kernelized Gram matrix (size of $p^2$, where p can be infinite) will be prohibitively expensive. The author adopts the idea of sparse approximation, i.e., Nyström embedding, to project the $p\times p$ kernelized Gram matrix into a new matrix that is of size $O(\gamma_{NT})$, where $O(\gamma_{NT}$ is the information gain of order $O(\log T)$ for some kernel functions. To this end, the authors can prove $O(\sqrt{NT}\gamma_{NT})$ regret and $O(N^2\gamma_{NT}^3)$ communication cost.
strengths_and_weaknesses: Strength.

1. The problem is well-motivated. To the best of my knowledge, there are no previous works studying distributed kernelized bandit, with rigorous sublinear regret and sublinear communication cost guarantee. I enjoy the way how the authors first discuss the straightforward usage of the previous solution [25] as a warm-up and motivate the challenge of the problem.

2. From the technical point of view, though I did not go through all the proofs, the intuition of the current paper is clear and reasonable. I think the authors borrow the batched/delayed kernelized bandit as building blocks to save the communication round and use the sparse approximation to save the per-round data to be uploaded/downloaded. The main contributions of this paper are designing a suitable triggering event with only approximated sufficient statistics at hand and using ridge leverage score sampling to send sampled information. From my perspective, the solution and the analysis should be of independent interest to other related works. 

Weakness.

1. Unlike [25], I do not find any discussion about the tightness of the result and the communication and regret trade-off. Also, there are no lower bound results for communication cost, so it is a little bit confusing how tight the communication cost $O(N^2\gamma_{NT}^3)$ is. Moreover, it is not clear to me why there are no $d$ factors in the regret, I guess the reason is you replace both $d$ and $T$ to $\gamma_{NT}$ so you can replace the trivial bound (for Algorithm 1) to $O(N^2\gamma_{NT}^2)$, but this again is one $O(\gamma_{NT})$ factor less than your current result.
questions: Can you discuss and explain more about the tightness of your result? This could be comparing with the degenerate case, the lower bound, or the trade-off between the communication cost and the regret. 
limitations: The authors adequately addressed the limitations and there is no foreseen potential negative societal impact of the current work
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: This paper studies the distributed kernel bandit problems in a decentralized setting. As a first observation, they consider Distributed-Kernel UCB, which is naturally derived from the one for distributed linear bandits, and prove that its communication cost suffers from the linear dependence of time horizon T. To remedy this, they propose Approximated Distributed Kernel UCB that uses the Nyström approximation techniques. The resulting communication depends on the term on maximum information gain $\gamma_{NT}^3$, removing the linear dependence of T. They also conducted a series of experiments using real-world dataset.

strengths_and_weaknesses: Strength:
The idea of Nyström approximation techniques enables the improved Dist Kernel UCB to have a better communication cost than the naive Kernel UCB. Approximated Kernel UCB maintains the good representation of the whole dataset, which is used to escape the sending of all unshared raw data.
In order to deal with such an approximated estimator, the event-trigger in Eq (4) is derived for determining when to incur the global synchronization.

The size of the dictionary $S_t$ scales linearly w.r.t. the maximum information gain $\gamma_{NT}$, which therefore improves the communication efficiency. 
All of the parameters such as threshold D in the event-trigger and how the subroutine of RLS in algorithm 3 is invoked is clearly stated. 

The value of the information gain $\gamma_{NT}$ is now a key factor in the analysis. They satisfactorily discussed what this factor implies and which affected the factor, when it is sufficiently smaller than $T^{1/3}$. 


Weakness:
The lower bound on communication costs for this problem is not fully discussed. 

===Post Rebuttal===
Thank you for author's response and detailed discussion for communication lower bound result with Square Exponential kernels.
I also read other reviews and keep my score for acceptance.  

questions: Some may say that the key techniques are essentially imported from the work of [2,3] and combining these with distributed Kernel bandits seems to be a straightforward approach. It would be appreciated if the authors explain what difficulties arise when applying them to distributed kernel bandits.
limitations: -
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: This paper investigates the communication efficiency challenge of kernelized contextual bandits in a distributed setting. This paper resolves this challenge by equipping all agents to communicate via a common Nyström embedding which is updated adaptively as more data points are collected. This paper proposes an algorithm named Approx-DisKernelUCB and demonstrated that Approx-DisKernelUCB can achieve sub-linear rate in both regret and communication cost.
strengths_and_weaknesses: **Strengths:**
The proposed Nyström embedding technique is very interesting, which makes a solid contribution to the communication challenge of distributed kernelized contextual bandits. The proposed algorithm Approx-DisKernelUCB achieves good performance in terms of both regret and communication costs.

This paper is well-written and the presented theoretical analysis looks sound and solid. Readers can easily understand the main idea behind algorithm Approx-DisKernelUCB.

**Weaknesses:**

The structure of this paper could be further improved. I suggest the authors to give more intuition behind the theoretical analysis and put some representative experimental results in the main text.

It would be better if the authors can comment and discuss the following related works on distributed pure exploration in the literature review part.

1. Distributed exploration in multi-armed bandits. Hillel et al.
2. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. Tao et al.
3. Collaborative Pure Exploration in Kernel Bandit. Du et al.

questions: Could you explain the differences of the techniques used to handle communication challenges between this work and prior distributed linear bandit works?

Can the Nyström embedding technique solve the communication challenges of distributed linear bandits?

Why not directly present algorithm Approx-DisKernelUCB? The algorithm DisKernelUCB seems not satisfactory due to its linear communication cost. 

limitations: See the weakness above.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies the problem of distributed bandits when the reward function lies in an RKHS. The paper proposes algorithms to enable clients to make a decision at each round. The regret and communication cost of proposed algorithms are studied.
strengths_and_weaknesses: Strength: The paper proposes an algorithm based on Nystrom approximation which can achieve sub-linear regret of $\mathcal{O}(\sqrt{NT})$ which is proved to require communication cost of $\mathcal{O}(N^2)$.

Weaknesses:
1. Clients needs to send their data samples to the server. Therefore, the proposed algorithms cannot protect the privacy of clients.
2. The novelty of the proposed algorithm DisKernelUCB seems to be limited. Since the communication cost of the algorithm should be $\mathcal{O}(TN^2d)$ to achieve regret of $\mathcal{O}(\sqrt{NT})$, it seems that DisKernelUCB is a simple extension of centralized algorithm where each client locally learns to take an action. In fact, it seems that making minor changes in the centralized algorithm can lead to this result.
questions: What is the relations between the regret bound of Approx-DisKernelUCB and the Nystrom method to map $x$? How the approximation affect the regret bound? I think it is useful if authors can elaborate more on this in the paper.
limitations: The paper assumes that the rewards are generated using a kernel function belongs to an RKHS. Furthermore, privacy of clients cannot be protected using the proposed algorithms.
review_title: null

Meta-review: metareview: The paper studies distributed kernelized bandit and applies the Nyström approximation to achieve communication efficiency, which is a novel technique appreciated by the reviewers. After some discussions, and including adding another extra reviewer, I believe the paper has enough contribution and is worth to be published at NeurIPS'2022. However, the authors do need to take all review comments serious and give a thorough revision to the paper, including comparisons to other possible approaches, such as federated learning. The authors also need to make it very clear why studying kernelized bandit and distributed bandit setting is important for applications.
confidence: Certain
Decision: Accept