Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers the problem of online collaborative filtering. In each round of this problem, a user is randomly sampled and a set of items/arms are provided to the learner. The goal of the learner is to recommend one of these items to the user so that the cumulative reward it collects over time is maximized. One key structure that is usually imposed on this problem is the cluster structure: for each item, it is assumed that the users can be grouped into a small number of clusters, where users within the same cluster have the same reward for the item. This problem has received significant attention in recent years. Previous works assumed that the reward of each user-item pair is a linear function of the item vector [1]. The current paper extends this to consider more general non-linear reward functions. In particular, the paper uses neural networks to model the unknown reward function. The authors provide a meta learning based algorithm (meta-ban) that achieves O(sqrt{nT}) regret for this problem, where n is the number of users and T is the number of online rounds. Experimentally, the authors show that the proposed technique achieves better regret than baselines on benchmark tasks. 

[1] Li, Shuai, Alexandros Karatzoglou, and Claudio Gentile. "Collaborative filtering bandits." In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pp. 539-548. 2016.
strength_and_weaknesses: Strengths:
The problem considered in the paper is a nice generalization of the past work to non-linear rewards, and is relevant in practice. Some of the theoretical results in the paper (e.g., regret bounds not depending on dimension, no distributional assumptions on the arms) are interesting, but unfortunately lack a thorough discussion on how these were obtained.

Weaknesses:
I believe the paper is a little bit under-cooked. The clarity and presentation in the paper can be significantly improved. The algorithm is not well motivated and described. The theoretical results are not well discussed and the proofs in the appendix could be presented better. Here are some key concerns I have:

* Clarity: I had to take multiple passes through the paper to clearly understand the notation, the main algorithm, and the theoretical results. 
  - first of all, the algorithm needs to be clearly explained. what is the motivation behind introducing a meta learner in Algorithm 2? It is never mentioned.  What happens if we solve the objective in Algorithm 2 exactly (i.e., increase $J_2$ and don't warm-start $\Theta_{(0)}$ with $\Theta_{t-1}$)?  Will the resulting algorithm have poor performance?
  - why is $\ell_1$ norm used in Algorithm 2? Why not $\ell_2$ norm?
  -  it is not clear how the proposed algorithm is different from the algorithms proposed in prior works such as Li et al. 2016 [1]. Is the extension to nonlinear reward functions straightforward? What are the key challenges and insights needed for this extension? These things were never discussed in the paper.
  - while Theorem 4.2 is interesting, a proof sketch in the main paper would have helped the reader understand the proof better. Currently, it is very hard to understand the key ideas in the proof. I tried looking at the appendix, it is poorly organized and without a high level overview of the proof, I found it hard to read through the appendix. For example, I tried looking at Theorem B.1. It refers to Lemma E.4, which in turn refers to Lemma E.3, which in turn refers to E.5 and so on. By the time I traced this graph, I lost track of many things. 
  - some key details in the experiment section are missing. For example, details on how the classification datasets are converted into collaborative bandit problem  should be added to the main paper. This will help the reader better understand the task being solved.
  - there are several issues with the notation. Here are few examples: L in section 3 appeared before it was defined. Operator grad_{theta^u for u in N} in line 8 of algorithm 2 was never defined. 

* Theoretical Results: 
  - the regret looks too good to be true. why is there no dependence on $d$? Even in the linear case (without and collaborative filtering stuff), the minimax regret has dependence on dimension. Are there any assumptions that are causing this to happen? In particular, is assumption 4.1 the main reason for these rates? A discussion on this would be appreciated.
  - On a related note, why is there only a $T^{1/2}$ term in the regret? The NTK kernel is a very complex kernel with slowly decaying eigen spectrum. It's worst case regret bound in standard contextual bandit setting scales as $O(T^{1-d^{-1}})$. Can the authors explain what is causing this discrepancy?
  - the cluster sizes and the number of clusters never came up in the analysis at all ($q_{t,i}$). Shouldn't the regret depend on these quantities? I'd appreciate if the authors make this dependence more explicit. 

* Analysis:
  -  The analysis in the paper seems to be in the NTK regime. In fact, the paper relies on a number of results proved in the past works on NTK. There are some caveats with these results that the authors never brought up in the paper. 
      - First, most of the past works on NTK assume certain kind of initialization for the NN. But the initialization scheme used in Algorithm 3 doesn't match with the past works. Given this, do the past results carry over directly to the setting in this paper? In particular, do Lemmas E.6 to E.10 follow directly from past works? 
      - Second, the result in Theorem 4.2 doesn't say anything about how the context vectors are generated suggesting that the result holds even if the context vectors are generated adversarially. But I doubt if this is the case. The NTK results such as the ones in [2] require the context vectors for all the rounds to be generated by an oblivious adversary before the start of the algorithm. If the context vectors are generated adversarially, the NTK analysis in these works doesn't go through. Can the authors comment on this?

* Experiments Issues:
  - I have a concern regarding how the ML classification datasets are converted to the collaborative bandits problem. Based on the description in Appendix A.2, it looks like the reward function for any given context vector is the same for all the users (i.e., h_u(x) is independent of u). This suggests that there is a single cluster for any given arm. If this is the case, the problem simply boils down to the neural contextual bandit problem studied in [2]. Then, why is there a huge difference in performance between the proposed technique and NeuUCB-ONE?


[2] Zhou, Dongruo, Lihong Li, and Quanquan Gu. "Neural contextual bandits with ucb-based exploration." In International Conference on Machine Learning, pp. 11492-11502. PMLR, 2020.
clarity,_quality,_novelty_and_reproducibility: see my comments above
summary_of_the_review: While the problem being studied is interesting, the clarity in the paper needs to be significantly improved. And there are several concerns with the theoretical and experimental results presented in the paper. I'd appreciate if the authors address my comments above.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: 
The paper studies Neural Collaborative filtering bandits that incorporate collaborative effects among users with both linear or non-linear reward assumptions, and proposes a meta-learning based bandits algorithm (Meta-Ban) that could adapt to dynamic groups with a UCB-type exploration. It then provides theoretical analysis on its regret upper bound for the proposed algo, Meta-Ban, and evaluate them on 10 datasets and show that the proposed algorithms outperforms against baselines. 
strength_and_weaknesses: Strengths: 
- The paper studies Neural Collaborative filtering bandits that incorporate collaborative effects among users with both linear or non-linear reward assumptions, and proposes a meta-learning based bandits algorithm (Meta-Ban) that could adapt to dynamic groups with a UCB-type exploration. 
- the paper provides theoretical analysis on its regret upper bound for the proposed algo, Meta-Ban, and evaluate them on 10 datasets and show that the proposed algorithms outperforms against baselines. 

Weakness or questions: 
- In the first step of the proposed algos, it would like to infer a user's relative group. The question is what assumptions made on these relative group? are they independent? can a user belong to multiple groups? If they are dependent, how does it impact the algorithm in terms of regret analysis and performance? Also, what are constraints or structure properties do we want to place when designing relative group? 
- In Challenge 1, the paper also asked whether the returned group is the true relative group, but was not clear on its importance and what's the consequence if it is not true relative group (sorry if overlook). 
- in Page 4 when defining Group Inference, the paper mentioned that it is natural to use the universal approximator. Could they explain intuition on why and this is chosen? 
-  In challenge 3, the paper mentioned the rapidly-changing relative groups, and wonder if the authors could provide more detail information on what mathematical assumptions and properties on them, as they would likely impact how we think/propose solutions in terms of efficacy and efficiency. 
clarity,_quality,_novelty_and_reproducibility: questions: 
- In the first step of the proposed algos, it would like to infer a user's relative group. The question is what assumptions made on these relative group? are they independent? can a user belong to multiple groups? If they are dependent, how does it impact the algorithm in terms of regret analysis and performance? Also, what are constraints or structure properties do we want to place when designing relative group? 
- In Challenge 1, the paper also asked whether the returned group is the true relative group, but was not clear on its importance and what's the consequence if it is not true relative group (sorry if overlook). 
- in Page 4 when defining Group Inference, the paper mentioned that it is natural to use the universal approximator. Could they explain intuition on why and this is chosen? 
-  In challenge 3, the paper mentioned the rapidly-changing relative groups, and wonder if the authors could provide more detail information on what mathematical assumptions and properties on them, as they would likely impact how we think/propose solutions in terms of efficacy and efficiency. 

cosmetics: 
1. In Algorithm 1 on page 4, missing a space in row 1 between greek letters. Also, no space before J_1 and comma was misplaced. 
summary_of_the_review: 
The paper studies Neural Collaborative filtering bandits that incorporate collaborative effects among users with both linear or non-linear reward assumptions, and proposes a meta-learning based bandits algorithm (Meta-Ban) that could adapt to dynamic groups with a UCB-type exploration. It then provides theoretical analysis on its regret upper bound for the proposed algo, Meta-Ban, and evaluate them on 10 datasets and show that the proposed algorithms outperforms against baselines. 

Overall it was an interesting and important problems. However, it also raised many of questions that were not clear in the paper in terms of what assumptions for a couple of 4 challenges they aim to tackle in the paper, and how does assumptions and structure properties on these challenges could impact the efficacy and performance of the proposed algorithms. Please see some detail questions below: 
- In the first step of the proposed algos, it would like to infer a user's relative group. The question is what assumptions made on these relative group? are they independent? can a user belong to multiple groups? If they are dependent, how does it impact the algorithm in terms of regret analysis and performance? Also, what are constraints or structure properties do we want to place when designing relative group? 
- In Challenge 1, the paper also asked whether the returned group is the true relative group, but was not clear on its importance and what's the consequence if it is not true relative group (sorry if overlook). 
- in Page 4 when defining Group Inference, the paper mentioned that it is natural to use the universal approximator. Could they explain intuition on why and this is chosen? 
-  In challenge 3, the paper mentioned the rapidly-changing relative groups, and wonder if the authors could provide more detail information on what mathematical assumptions and properties on them, as they would likely impact how we think/propose solutions in terms of efficacy and efficiency.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper explores the neural collaborative filtering bandits problem. Specifically, the authors first introduce relative groups to formulate groups given a specific content. Then, they use a meta learner and user learners to learn non-linear and linear reward functions. The authors also claim that this is the first work incorporating ‘collaborative effects’ in neural bandits. Besides experimental results, the authors also provide theoretical analysis of the regret upper bound of complexity, in which it is sharper than existing related works.
strength_and_weaknesses: Strength:

1. The presentation of the paper is intuitive and easy to understand. The authors introduce four challenges (i.e., C1-4) and subsequently tackle each challenge, which make it easy for the readers to follow
2. This is good that the authors also provide pseudo-code for Meta-Ban, with GradientDecent_Meta and GradientDecent_User.
3. The authors also have good regret analysis (Section 4), in which it shows that the proposed method is comparable with existing clustering of bandits and neural bandits
4. The experiments show that Meta-Ban outperforms all baselines across datasets over 10 runs, according to Figure 1-2.

Weaknesses: 

1. Although the experiments yield good results, I believe the authors should focus more on recommendation datasets/tasks, rather than ML datasets. Specifically, among all the datasets used in the paper, only two of them (i.e., MovieLens and Yelp) are common recommendation datasets. In addition, the preprocessing steps in Appendix A.2 seem to be not common in my opinion. For example, “If the user’s rating is less than 2 stars (5 stars totally), its reward is 1; Otherwise, its reward is 0” or “we use K-means to divide users into 50 clusters”. Could you please give more explanations of the preprocessing steps? How did we decide the ‘threshold’ of 2 stars to set the reward of 1? How did we come up with 50 clusters? Can we have more/less clusters? 
2. Also from Configurations paragraph of Appendix A.2, the authors use only a simple neural network of 2 fully-connected layers, which is a bit surprising to me as this paper introduces neural collaborative filtering bandits but with only a simple neural network of 2 layers. Can we have a larger neural network with more layers? If not, why? 
3. In Section 5 Experiments, NeuUCB-ONE and NeuUCB-IND seem to perform quite well. Would it be possible to combine NeuUCB based models with ‘relative groups' and compare them with Meta-Ban? Moreover, can we also compare Meta-Ban with NeuMF [1] beside NeuUCB-* so that we can compare our method with two groups of baselines: i) neural network and ii) neural network + bandits for personalized recommendation tasks? 
4. In the Appendix A.5, the authors mentioned that “This fluctuation is acceptable given that different input dimensions may contain different amount of information”. How can we determine if the fluctuation is ‘acceptable’?

[1] Neural Collaborative Filtering. WWW 2017.
clarity,_quality,_novelty_and_reproducibility: The paper has good quality and clarity in general. However, in order to improve the current version, the authors should also emphasise more on recommendation in the experimentation. 
summary_of_the_review: All in all, although the analysis is good, I personally found the experiments are a bit shallow towards recommendation. The authors should focus/provide more experiments on recommendation datasets such as Netflix, and also with more baselines towards personalized recommendations. In addition, I am also curious to see deeper analyses of run time, complexity, and scalability issues with dealing with large-scale systems.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper the authors study the collaborative effects among users in order to improve recommendations. This line of works is known as collaborative filtering bandits. 
The authors propose an interesting approach for this problem. Rather than assuming a linear model between the arm features and the expected reward, they use a neural bandit approach that allows dropping the linear assumption. Rather than using a clustering algorithm for capturing the collaborative effect, they define a relative group as a set of users that have similar expected rewards on the same item. Then, for each group (i.e. for each item) they learn a meta-neural bandit that shares historical data between users of the same group. The choice of the item for user u_t is done at the group level. This allows capturing collaborative effect among users. A neural bandit per user is also learnt in order to approximate the expected reward of items for the considered user. This allows building the estimated relative groups. 
The proposed algorithm is analyzed using over-parameterized neural network regime. They improve by a factor \sqrt{\log T} the previous results of (Zhou et al 2020). Moreover the obtained pseudo-regret upper bound does not depend on the dimension of arm features. They also provide a high probability guarantee on the time spent to find the true relative groups.
Finally, the proposed algorithm is favorably tested with respect to baselines on different datasets.

strength_and_weaknesses: The paper is well written. Theoretical and experimental evidences of the efficiency of the proposed algorithm (Meta-Ban) are provided. 

However, the reviewer has some comments and questions.

1/ The authors assume that the reward is bounded, but the noise seems to be unbounded. So it seems that equation (1) is not accurate. Why do the author not assume a sub-gaussian noise as in (Zhou et al 2020)?

2/ The authors use the over-parametrized neural network framework to analyze their algorithm, and they show a \sqrt {log T} regret bound improvement in comparison to the state-of-the-art. But in comparison to the state of the art, the regime where the neural network is analyzed is even more unrealistic than that of the state of the art. Indeed at each time step, the needed number of steps of the gradient descent in the order of T^56, while it was in \tilde O (T) in (Zhou et al 2020).

3/ In the experimental section, the value of J_2 is not given. I suggest to the authors to reassure the reader by giving the used value of J_2.

clarity,_quality,_novelty_and_reproducibility: The paper is clear, it is sound. Best of my knowledge the idea of relative groups seems new. In the experimental section more details on the values of the parameters must be provided.
summary_of_the_review: Despite some drawbacks that the authors can fix, overall it is a good paper. 
_______________________________________________
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 meta-learning in neural bandits. The authors bound the regret of their algorithm and also evaluate it empirically.

The strength of the paper is that this is the first time that this problem is studied. Arguably though, general algorithms have been proposed in the bandit community before, such as

* [Meta-Thompson Sampling](https://proceedings.mlr.press/v139/kveton21a.html)

* [Bayesian Decision-Making Under Misspecified Priors with Applications to Meta-Learning](https://proceedings.neurips.cc/paper/2021/hash/ddcbe25988981920c872c1787382f04d-Abstract.html)

* [Hierarchical Bayesian Bandits](https://proceedings.mlr.press/v151/hong22c.html)

It is just that their analysis is limited to linear models, which this paper overcomes. The paper has three weaknesses:

* Strong assumptions in the analysis, such as the arm separability in Assumption 4.1 and the uniformity conditions in Theorem 4.2. These assumptions lead to a regret bound where the model complexity does not appear, which is unusual. While this may be common in some neural bandit analyses, it needs to be discussed in detail and explained.

* The algorithm cannot be run as analyzed and requires hyper-parameter tuning. Therefore, it is hard to run online and its impact on practice may be minimal.

* Some experiments require heavy and unnatural preprocessing (Appendix A.2). For instance, in "ML Datasets", Mnist and Notmnist datasets are merged together and each is treated as a user cluster.

This paper was discussed in an online meeting with all reviewers. It is a borderline with a bias to reject.
justification_for_why_not_higher_score: The theory is not strong enough and the experiments alone do not carry the paper.

This paper should be treated as a **weak reject**, reject and bump up if there are not better papers.
justification_for_why_not_lower_score: This paper solves a novel problem in an active research area.
Decision: Reject