Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies a contextual bandit problem for which the authors propose a neural network-based policy that takes a raw feature vector as an input without knowledge of the specific reward generating function. The proposed policy transforms the raw feature vector using the last hidden layer of a deep ReLU neural network and uses the upper confidence bound (UCB) approach to explore in the last linear layer which the authors call "shallow exploration" instead of using the entire network to explore. The paper provides regret analysis which shows O(\sqrt{T}) regret. The proposed method enjoys computational advantages over existing neural contextual bandit policies.
main_review: The authors argue that the proposed decoupling of the representation and the exploration will achieve the best of both worlds: efficient exploration in shallow (linear) models and the high expressive power of deep models. However,  the high-level idea of decoupling the representation and exploration has already been proposed in previous literature [38] although those works focused on a Thompson sampling-based algorithm. Hence, I am not convinced that credit should be given to this paper for the decoupling idea. I believe the paper should be evaluated on theoretical merit and wish that the authors are more explicitly clear about what is technically challenging and what technical innovations they are providing to the community compared to the existing techniques in [51,52].

In Line 262, the authors state that the width of the neural network satisfies m = poly(L, d, 1/δ, H, log(T K/δ)). Is it the same order of m as shown in the previous works [51,52] which is too large (hence very restrictive) for any practical settings? I wish the authors are more clear about this. I feel that what the authors are appealing for is a more practical version of neural contextual bandits with "shallow exploration" But, not stating what is crucial information for their result to hold, which does hinder practicality, is clearly not helping the readers.

While the numerical results show that the performance of the proposed method is slightly better than the existing methods. The plots are not showing any sublinear regret in Figure 1 which is a bit disappointing despite the claim of achieving the best of both worlds.


limitations_and_societal_impact: Not applicable
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Authors provide a new regret bound for a recent approach to solving contextual bandits. Previous approaches have introduced deep neural networks to learn context, leading to a paradigm where one must explore over the entire network parameter space, which is inefficient for learning. 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. Although this has been done previously in the context of Thompson sampling, there has not been a regret bound given. 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, they show experimentally that their algorithm is better than neural-only or linear-only contextual bandits.
main_review: 
Strengths:
- Authors combine known 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 O(\sqrt(T)) regret.
- The paper is well written, limitations clearly addressed, and assumptions made clear.
- Authors give results from 3 tabular and 1 image domain, providing a decent test bed for their algorithm against competitors under different neural network depths. Their algorithm always outperforms the competitors.


Weaknesses:
- The way the paper is written somewhat undersells the novelty of the authors' contribution. Right now, their contribution is framed such that their algorithm is a subset of the Neural-linear idea from Riquelme et al., and the purpose of the whole paper is mainly to provide this regret bound for one version of a neural-linear contextual bandit. This left me wanting more -- e.g., are there new conceptual ideas here, were there specific challenges to achieving the proof that could be part of the authors' contribution, does the proof provide some more general implication about the way contextual or other bandits can be learned? Similarly the experimental results showed very little separation between the competitor NeuralUCB and the authors' Neural-LinUCB -- one thing that would have been interesting to see would be an analysis of whether more separation could be achieved between the two, as the size of the networks increase -- that would be an interesting way to experimentally verify the differences between the O(d\sqrt(T)) regret bound of NeuralUCB and the O(\sqrt(T)) regret bound of the authors' method.
---------------------------------------------
Update: I have read the other reviews and the author responses. First, I think the authors adequately addressed my concern (also mentioned by reviewer 7ZGH) that the technical challenges over previous literature needed to reach their results were unclear. Authors should make this clear in their final version. Second, authors make a reasonable argument about why running experiments with larger architectures (where they would see more separation against the competitor) were not carried out. However, some version of this experiment really should be included in the final paper. Authors should at least run a small version of this scaling experiment against the competitor (e.g., network widths of 2000, 3000, 4000...) and include it in the main text (they could be added to Figure 1 relatively easily.) I have increased my score by 1 to reflect the authors addressing my main concerns.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the contextual bandit without knowing the specific reward generating function. The authors propose to use a deep neural network to model the reward function where the hidden layers of the deep neural network are used to represent the features and the exploration is only performed in the last layer of the
neural network. In this way, the reward generating function can be expressed as the inner product between a deeply represented feature vector and an exploration weight parameter. As the author explained, the main advantage of this reward model is to efficiently reduce computation because we only need to explore the last layer of the deep neural network instead of exploring the whole network like existing neural bandit algorithms. 
The authors show that the proposed algorithm for this problem obtains a near-optimal regret which matches the regret bound of linear contextual bandits. They also provided experiments based on real-world datasets to show the performance and computational efficiency.

main_review: The idea of using a deep representation and an exploration at the last layer of a neural network has been exploited in the literature. I think that their main contribution consists of a novel algorithm using the UCB approach and their theoretical results. The paper sounds technically correct. 
Overall, the paper is very well written and easy to follow. It would be better if the authors can clearly explain the notation of “exploration” used in the last layer. I understand that this notation is different from that of the exploitation-exploration tradeoff in the contextual bandit. 
I have several questions as follows:
To guarantee the near-optimal regret, the neural network must be over-parameterized. As Corollary 4.6 showed, m > T^3 is needed. If T =1000, then m > 10^9. Such a network is so large to implement and train. How did you solve this issue in your experiments and what is a potential solution? 
In the experimental results in Figure 1, I see that Neural-LinUCB always outperforms NeuralUCB on all the datasets. Why? Is it because of the computational issue of the inverse matrix Z^{-1} of NeuralUCB?
In contextual bandit, Thompson Sampling algorithms often outperform UCB-based algorithms. See paper “Neural Thompson Sampling”. Why does your UCB-based algorithm always outperform Neural-Linear, a Thompson-Sampling-based algorithm?

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a novel contextual bandit algorithm, Neural-LinUCB, that transforms the raw feature vector using the last hidden layer of a deep ReLU neural network (deep representation learning), and uses an upper confidence bound (UCB) approach to explore in the last linear layer (shallow exploration). The algorithm is shown to enjoy the best of two worlds: strong expressiveness due to the deep representation and computational efficiency due to the shallow exploration. In theory, a $\sqrt{T}$ regret bound is established. Numerical experiments further demonstrated the importance of decoupling representation learning and uncertainty estimation.
main_review: Overall, this paper is very well written and is easy to follow. The contribution over NeuralUCB (Zhou et al. 2020) is clear and convincing. Below are some questions for further clarification.

1. The algorithm relies on the exploration parameter $\alpha_t$, which is set to be an increasing function of $t$ and an unknown constant $M$ in Theorem 4.4. However, in the experiment, $\alpha_t = 0.02$ for all $t$. Can authors provide any justification or explanations on this inconsistency. 

2. As shown in Corollary 4.6, the final rate is $\sqrt{T}$ only when $\sqrt{(r-\tilde{r})^{\top} H^{-1} (r-\tilde{r})}$ is bounded. Note that $r \in R^{TK}$ and $H\in R^{TK \times TK}$. The authors justified this by claiming that Zhou et al. (2020) assumed that this can be upper bounded by a constant. Personally, I would like to see more justifications on this statement as the $\sqrt{T}$ regret bound was claimed in the abstract and introduction. 

3. Suggestion: one advantage of the proposed Neural-LinUCB over NeuralUCB (Zhou et al. 2020) is the computational efficiency. I would suggest the authors to move some runtime comparisons in Section A.1 of the supplement to the main paper. 

4. Typo: line 313, "$L=2$ and $2000$" should be "$L=2$ and $m=2000$".

limitations_and_societal_impact: NA
review_title: null

Meta-review: This work presents a neural contextual bandit algorithm with computational improvements over prior work.  The work is very interesting, however reviewers, throughout both the feedback phase but also the extensive internal discussion, ended up very split; some find the overall approach very exciting and sound, others are concerned about the concrete improvement over prior work, which is powered by additional assumptions and thus a bit hard to measure.  Independent of the final decision, this is a valuable paper and I urge the authors in either their revisions or in re-submission to work to solidify the improvement over prior work, for instance achieving computational benefits without the extra assumptions, or relaxing the assumptions and/or making the analysis with them and the discussion and justification of the assumptions more compelling.
Decision: Reject