Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper presents a new neural-bandit algorithm with shallow exploration and provides a regret bound for the proposed method. The existing approaches have introduced deep neural networks based bandit algorithms to learn reward functions, in which exploration takes place over the entire network parameter space, which can be inefficient for large-size networks which are typical in NTK based approaches. The authors address this by taking an existing approach that decouples the deep neural network feature representation learning from most of the exploration of the network parameters by only exploring over the final layer of the network. 

Despite the fact that this idea of shallow exploration has been proposed previously, there has not been a theoretical analysis with a regret bound. The authors analyze a UCB version of this approach, then build from techniques from both deep neural contextual bandits and linear contextual bandits to prove an O(\sqrt(T)) regret bound. Finally, the authors present experimental results to show that their algorithm work well in practice.
main_review: Strengths:
- The authors combine existing techniques to create an interesting algorithm for contextual bandits. Although the combination is not novel, the authors make a theoretical contribution by demonstrating that the combination has sub-linear O(\sqrt(T)) regret.
- The paper is well written, limitations are clearly stated.
- The authors show that their proposed algorithm outperforms the existing algorithms.

Weaknesses:
- Is the direct comparison with the existing neural bandit algorithms possible? It appears that this paper has an additional assumption than the existing literature on neural bandits. I am not sure even the regret bounds can be compared.
- The gap between the theoretically suggested setting and the experiment: there seems to be a huge gap between what is shown theoretically and what is executed in the experiments, for example, $m$. Can you show at least some experiments on how the algorithm behaves with a very large value of  $m$ which is what the theoretical results are based on?

summary_of_the_review: With the points I made above, I am leaning slightly on acceptance. I hope the authors address the concerns mentioned above.

========== Post-reponses ================= 

Thanks to the authors for the responses. I have read the comments of the other reviewers. I am staying with the current score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Authors tackle the setting of contextual bandits, using deep representation learning combined with an upper confidence bound algorithm. The main contribution of this work is to provide a regret bound for the setup which decouples the representation learning from the UCB search, by searching only over the last layer of the network. The setting had been studied before, but only empirically, and using Thompson sampling rather than UCB. Authors validate their results empirically on several domains from the UCI data repo, as well as on MNIST, comparing against state of the art baselines.

main_review: 
Strengths:
- The paper is well written, algorithmic motivations are clear, and the setting is interesting.
- The theoretical results, which are the main contribution, are nice and the assumptions made are very clearly described and contextualized.
- Experimental results consider several reasonable domains+baselines and support the claims.

Weaknesses:
- The main weakness is that the algorithm proposed is not particularly novel, since (Riquelme et al. 2018) already introduce the "decoupled deep representation+last layer search" methodology in a previous paper. So the question is whether the new regret analysis is enough on its own. For instance, the results are given for UCB only -- could a similar analysis be extended to the Thompson sampling case (i.e., that used in Riquelme et al. 2018)?
- There is also some concern about the requirement on the width of the neural network in thm 4.4 being so large in order for the main O(\sqrt(T)) bound to hold, rather than a maybe more honest O(m^{-1/6}T) bound, but the authors do at least provide some empirical evidence in the appendix that suggests the performance of their algorithm is not heavily reliant on very large values of the network width.

-------------------------------
Update: I have read the author response. They adequately address my few minor concerns and so my opinion to accept stays the same.
summary_of_the_review: I am recommending accept because the theoretical results are interesting, and combined with the given very clear discussion about the assumptions in context, I think provide a decent baseline for future such analyses, even if assumptions such as the large network width are restrictive.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies neural contextual bandits and proposes an algorithm that transforms the raw feature vector using the last hidden layer of a deep ReLU neural network, and uses an UCB approach to explore in the last linear layer. Compared with existing neural contextual bandit algorithms, the proposed algorithm attains computation efficiency. Regret guarantees and empirical results are provided to demonstrate the effectiveness of the proposed algorithms
main_review: Strengths: 

1. The studied neural contextual bandit is very interesting and important in the area of applying neural networks to online learning.
2. The proposed algorithm significantly reduces the computation costs when compared to existing neural contextual bandit algorithms.

Weakness:

While the proposed idea, i.e., transforming the raw feature vector using the last hidden layer of a deep ReLU neural network and adopting an UCB approach to explore in the last linear layer, is simple and effective, this idea is inspired by existing Thompson Sampling based work [Riquelme et al. 2018]. In addition, several techniques in the regret analysis of this paper are similar to existing works, e.g., [Riquelme et al. 2018; Zhou et al. 2020], which reduce the technical novelty of this paper.


---After Rebuttal---

I thank the authors for their response. However, my concern on limited contribution and novelty was not well addressed. See my following comments for details. I plan to stick my score 3, i.e., reject.

1. Algorithmic design.

The high-level idea of decoupling representation learning and exploration is originated from Riquelme et al. (2018). 
As we know, Thompson Sampling and UCB are two standard algorithmic styles in bandits.
While Riquelme et al. (2018) is a Thompson Sampling based algorithm and you design a UCB based algorithm, I do not think that adapting an existing idea in Thompson Sampling type algorithm to the UCB type algorithm is a significant contribution in algorithmic design. 

2. Theoretical analysis

I appreciate that you propose the first theoretical analysis for the idea of decoupling representation learning and exploration on your UCB type algorithm, while prior work [Riquelme et al. (2018)] does not give theoretical analysis on their Thompson Sampling type algorithm. 

However, it is well known that the Thompson Sampling based analysis is intrinsically more complicated and harder than the UCB based analysis, which reduces the technical challenges of analyzing this idea on your UCB type algorithm to some degree.

I go through the new technical contributions you mentioned, i.e., Lemma C.1 and Lemma C.4. The proofs of Lemma C.1 and Lemma C.4 also rely on prior NTK works, e.g., Theorem 3.1 in Arora et al. (2019b), Lemma 4.4 in Cao & Gu (2019b), Lemma B.3 in Cao & Gu (2019b), Theorem 3 in Allen-Zhu et al. (2019b). 
In my opinon, the analysis is a standard combination of existing techniques from prior neural contextual bandit [Zhou et al. 2020] and NTK [Arora et al. (2019b); Cao & Gu (2019b); Allen-Zhu et al. (2019b)] papers, following the high-level idea from [Riquelme et al. (2018)].

From my view, the biggest technical contribution of this paper is that you borrow many techniques from neural contextual linear bandit [Zhou et al. 2020] and NTK [Arora et al. (2019b); Cao & Gu (2019b); Allen-Zhu et al. (2019b)] to execute the high-level idea of decoupling representation learning and exploration from [Riquelme et al. (2018)] in theoretical analysis. However, I think that the contribution and novelty is weak.

----Additional Response----

I have read the authors' further response. Unfortunately, my concern on technical novelty and contributions was not relieved.

This paper borrows the high-level idea of decoupling representation learning and exploration from [Riquelme et al. (2018)] to design a UCB-type algorithm, and analyzes it by borrowing many techniques from existing UCB-type neural contextural bandit/NTK papers [Zhou et al. 2020;Arora et al. (2019b); Cao & Gu (2019b); Allen-Zhu et al. (2019b)]. 
Although this paper well executes the high-level idea in [Riquelme et al. (2018)] and completes the analysis (in the more well-studied UCB style), I do not think this is a big contribution.

The technical novelty/contribution of this paper is very limited.
Not only the theoretical analysis of this paper is mostly built upon existing works  [Zhou et al. 2020;Arora et al. (2019b); Cao & Gu (2019b); Allen-Zhu et al. (2019b)], but also the idea of algorithm design also comes from existing work  [Riquelme et al. (2018)].

My opinion can be supported by the following facts in the proof details in this paper:

In Appendix C, to prove the main theorem, the authors wrote Lemmas C.1-C.6, among which Lemmas C.1, C.3, C.6 (or their similar forms) have already appeared in existing papers [Zhou et al. 2020], [Cao & Gu 2019b], [Abbasi-Yadkori et al. 2011], respectively. 

In Appendix D, in the proof of (the only new) Lemmas C.2, C.4, C.5, the authors further borrowed many existing techniques, including Lemmas D.1 [Arora et al. (2019b)], D.2 [Cao & Gu 2019b], D.3 [Cao & Gu 2019b], D.4 [Allen-Zhu et al. (2019b)], D.5 [Abbasi-Yadkori et al. 2011]. 
In addition, the authors also followed the well-known analysis procedure of self-normalized concentration bound (in the proof of Lemma D.5) and confidence ellipsoid  (in the proof of Lemma D.4) from [Abbasi-Yadkori et al. 2011].

In conclusion, unfortunately, I do not think this paper has sufficient technical novelty. I will stick to my recommendation 'reject'.


summary_of_the_review: Overall, I think that the studied neural contextual bandit problem in this paper is very important. The idea behind the proposed algorithm is simple and effective. Theoretical and experimental results are provided to demonstrate the effectiveness of the proposed algorithm. However, this paper borrows the idea and analytical techniques in prior works and lacks theoretical novelty.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper study a novel contextual bandit algorithm: Neural-LinUCB.
As in (Riquelme et al 2019), the idea of this algorithm is based on decoupling deep representation learning and exploration. A deep neural network learns the mapping between the context $x_{t,a_t}$, while a linear bandit, OFUL (Abbasi-Yadkori 2011), chooses the arm to play.
In contrast to (Riquelme et al 2019), a regret upper bound of the algorithm a regret upper bound of the algorithm is stated in Corollary 4.6. The proposed algorithm is also an improvement over NeuralUCB (Zhou et al 2020) for two reasons: the computational cost of the exploration is lesser, since the exploration is only done in the last layer of weights, and the regret upper bound is tighter. Indeed, in contrast to (Zhou et al 2020) it does not depend on the dimension of the tangent kernel matrix, which can be in O(KT).
Experiments, done on four contextual bandit problems, show that Neura-lLinUCB outperforms LinUCB and performs as well as NeuralUCB and NeuralTS.

main_review: The paper is well written. The studied problem is significant. The theoretical results are interesting. 

The reviewer has some comments and questions.

If Neural-LinUCB reduces the computational cost of NeuralUCB, it remains very high in comparison to LinUCB due to the episodic retraining of the deep neural network. Worst, the computational cost over-linearly increases with T since the deep neural network is retrained every H episode with all data. Neural-LinUCB cannot be used if T is too large. 
Do the authors have any leads for handling this practical problem?

The theoretical results are very interesting since it concerns the best performer in contextual bandits, but they are still quite weak. 

First, the regret upper bound depends on r-\tilde(r), the regret between the obtained mapping of the reward function and the best mapping. It seems not oblivious that the right term of R_T in corollary 4.6 does not scale in \sqrt(T).

Second, the condition m \geq T^3 seems strong and confirms that the proposed algorithm does not scale with T. 

AFTER REBUTTAL
I thank the authors for their answers. The analytical results on the contextual bandits with Deep Neural Networks are not totally news, as well as the algorithm with shallow exploration on the last layer, but together, they constitute a significant step. The proposed algorithm is a LinUCB-like algorithm, but that uses the powerful representation obtained in the last layer of a Deep Neural Nertwork to perform LinUCB. As a result, a clear improvement of performances in comparison to LinUCB, and moreover this fixes a known issue of LinUCB: due to the matrix inversion, LinUCB cannot process more than few hundreds of features. Here due to the use of a representation layer, this issue is fixed. An efficient Neural Contextual Bandit algorithm is analyzed, and this could have a deep impact on the bandit community. That is why I vote for acceptance.

summary_of_the_review: The paper is well written. The studied problem is significant. The theoretical results are interesting. The reviewer accepts this paper.
review_title: null

Meta-review: This paper tackles the neural contextual bandit problem, for which existing approaches consists rely on bandit algorithms based on deep neural networks to learn reward functions. In these existing strategies, exploration takes place over the entire network parameter space, which can be inefficient for the large-size networks typically used in NTK-based approaches. In this work, the authors address this by building on an existing technique of shallow exploration, which consists in exploring over the final layer of the network only, allowing to decouple the deep neural network feature representation learning from most of the exploration of the network parameters. More specifically, they propose a simple and effective UCB-based strategy using this shallow exploration scheme, for which they provide a theoretical analysis. The proposed approach builds on several ideas for previous works, including borrowing proof techniques and theoretical arguments. Although this limits the novelty of the work, connecting these ideas together is not obvious and constitutes a significant contribution. Moreover, the proposed approach fixes an important known issue due to the matrix inversion in LinUCB, which could have a strong impact on the bandit community.
Decision: Accept (Poster)