Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes Neural UCB for the neural-linear bandit setting. The main contribution of the paper is the theorem that the proposed method, Neural UCB, is guarantee to achieved a good regret bound, which for the first time extends bandits result to neural networks. Overall the paper is well written and easy to follow. 

While the result of this paper seems to be interesting, the idea of the paper is simply combining a recent progress on the neural tangent kernel for overparametrized neural networks and a standard linear UCB algorithm. 

The main concern I have is about the constant S in the regret bound. Note that this constant is an upper bound of \sqrt{h^T H h}, where h is in the dimension of TK and H is in the dimension of TK by TK. A naive bound for S could be sup-linear in T, which makes the bound vacuous. What would be a lower bound for \lambda_0 for eg. the setting in the experiments?

Other comment:
1. It should be explicitly stated somewhere in the paper that x_{t,k} are assumed to be deterministic. Thus \theta^* is deterministic. It is more important that \theta^* does NOT depends on a_t. Otherwise lemma 6.2 could be problematic. 

=====================
Based on the new version of the paper and the discussions, I change the score to weak accept.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper proposes to use the Neural Tangent Kernel (NTK) with the Upper Confidence Bound for stochastic contextual bandits. 
- The paper instantiates Kernel UCB (Valko, 2013) with the NTK and the novelty is limited from a theoretical point of view. 
- There is no experimental comparison with Neural Linear or Kernel UCB using a fixed kernel, (for example, the RBF kernel) or to methods like Thompson sampling that work well in practice even with non-linearities. 

Detailed review below:
- Section 2.2 is not relevant to the paper and it might be more useful to use this space to explain NTK better. 
- Please explain NTK before instantiating the algorithm in Section 4. 
- The "Efficient Implementation" section in Section 4 is standard and done in all the linear bandit papers. Please acknowledge this or say how it is different. 
- The NTK description in Definition 5.1 needs to be clarified. At the moment, it is difficult to parse. Please give some intuition about it. 
- For the regret analysis, could you explain how the analysis is different from that of a fixed kernel in Valko, 2013. 
- What is the intuition for having a lower bound on "S", the norm parameter? Why is there no upper bound? 
- The width of the neural network depends on T^4. How does this affect the effective dimension \tilde{d} in the worst case? Can it result in linear regret?
- For Lemma 6.2, 6.3, please say that these are directly borrowed from Valko, 2013 and Abbasi, 2011. 
- From an experimental perspective, the width of the neural network is a constant wrt to T, K and L and clearly doesn't align with the theoretical bounds. Please justify why this is a valid thing to do? 
- As mentioned earlier, there is no comparison with Kernel UCB with a fixed kernel, Neural Linear or Thompson sampling, methods that work well in practice. 
- Finally, real-world experiments are necessary to show the benefit of using NTK in practice. 
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: The authors proposed a neural network based UCB algorithm for bounded reward contextual bandit problems with theoretical guarantee thanks to the recent development of Neural Tangent Kernel (NTK).

Throughout the paper, the authors do not use much of the specific property of neural networks and NTK. They only use the gradient of neural networks as the feature and use the NTK as the kernel in the kernelized contextual bandits. This can be beneficial, for example, it can enriching the class of kernels. However, I feel the whole paper lacks novelty, and have some technical flaws.

Detailed Comments:
1. In Sec 3, the authors argued that kernelized contextual bandits suffers from the unknown RKHS problem and RKHS realizability problem. However, with universal kernel, RKHS is dense in L^2 space, thus can in principle approximate any function in L^2 space within any precision. So generally, this is not a problem. Moreover, bounded function does not necessarily contain the linear function, generalized linear function and bounded RKHS norm function. At least if we do not add some assumption on the input, linear function can be unbounded. On the other hand, the proposed methods also need p>TK to guarantee the realizability, and we can also design some kernel with feature map dimension larger than TK with some good property to guarantee realizability, so I think this claim is not fair.
2. In Assumption 5.2, the authors assume that the norm of contexts is smaller than 1. However, as far as I know, most of the existing work assumed the context have norm 1, and can be only relaxed to the norm upper lower bounded by two positive constant c1 and c2 (see [1]). Otherwise, there can be some issue on the positive definiteness of the NTK. Can the authors carefully check this? Meanwhile, I think it is not suitable to directly assume the NTK is positive definite. It is better to follow and refer the readers to the existing work.
3. It is better to introduce \theta^* before Sec 6, like for example the parameter that can perfectly predict the mean reward.
4. I am confusing on the proof of Lemma 6.1 in Page 12. When the authors calculate the norm of \theta^* - \theta_0, how to transform Q^\top A^{-2} Q to G^\top G? If we use the singular value decomposition, we only have that G^\top G=QA^2 Q^\top. If I understand correctly, here we should do an inverse, and we cannot simply get the desired results, as the minimum singular value of G can be small under current assumption. However, it is still possible to upper bound this distance to derive the remaining proof.
5. In the first line of Equation (B.3), there is a typo that omits the \phi(x)^\top.
6. How does the second inequality of (B.4) derives? I can understand that the authors may use the Cauchy-Schwartz inequality, but Frobenius norm cannot be directly upper bounded by spectral norm (though they are equivalent, but we need to add an additional constant like \sqrt{TK}). If the authors use the spectral norm, then the second term should be nuclear norm, not Frobenius norm. Probably I do not understand it correctly and it is not the core issue, but I think it is better to clarify it.
7. There is a typo in the fourth line of (B.4), it should be \lambda / \lambda_0,
8. The last derivation of Appendix B.3 have several typos omitting det(\lambda I).
9. The authors should better include the kernelized contextual bandits for a fair comparison, as LinUCB and Neural \epsilon-greedy both have theoretical issue that can be solved by kernel methods. I doubt that kernelized contextual bandits can solve these cases well.

Overall, I feel that most of the proof can be derived similarly from [2][3]. And Lemma C.1 is also from [4]. The authors only verify some conditions that when use NTK as the kernel in kernelized contextual bandits to adjust the main result from [2][3]. Thus, I think the technique used in this paper is not novel as well.

In my opinion, the communities are interested in solving contextual bandits with ``''gradient based'' neural network methods that use the neural network to predict the rewards given some contexts as input. But just as the Equation (6.1) shows, the prediction is not based on the neural network, but with a linear model taken \phi(x_i) as input. Also, throughout the paper, the authors never use the network output f. To this end, I feel this paper is over-claimed on ''neural''. On the other hand, I think it can be interesting to think about how kernel methods can benefit from NTK. Directly use the gradient as the feature map seems not an interesting and meaningful method, I think.

[1] Cao, Yuan, and Quanquan Gu. "A generalization theory of gradient descent for learning over-parameterized deep relu networks." arXiv preprint arXiv:1902.01384 (2019).
[2] Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. 2013. Finite-time analysis of kernelised contextual bandits. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI'13), Ann Nicholson and Padhraic Smyth (Eds.). AUAI Press, Arlington, Virginia, United States, 654-663.
[3] Abbasi-Yadkori, Yasin, Dávid Pál, and Csaba Szepesvári. "Improved algorithms for linear stochastic bandits." Advances in Neural Information Processing Systems. 2011.
[4] Arora, Sanjeev, et al. "On exact computation with an infinitely wide neural net." arXiv preprint arXiv:1904.11955 (2019).
review_title: Official Blind Review #3

Meta-review: As the reviewers have pointed out and the authors have confirmed, the original version of this paper was not a significant leap beyond combining recent understanding of Neural Tangent Kernels and previous techniques for kernelized bandits. In a revision, the authors updated their draft to allow the point at which gradients are centered around, theta_0, to now equal theta_t. This seems like a more reasonable algorithm and it is satisfying that the authors were able to maintain their regret bound for this dynamic setting. However, the revision is substantial and it seems unreasonable to expect reviewers to read the revised results in detail--the reviewers also felt it may be unfair to other ICLR submissions. All reviewers believe the paper has introduced valuable contributions to the area but should go under a full review process at a future venue. A reviewer would also like to see a comparison to Kernel UCB run on the true NTK (or a good approximation thereof). 
Decision: Reject