We study the stochastic contextual bandit problem, where the reward is generated from an unknown bounded function with additive noise. We propose the NeuralUCB algorithm, which leverages the representation power of deep neural networks and uses a neural network-based random feature mapping to construct an upper confidence bound (UCB) of reward for efficient exploration. We prove that, under mild assumptions, NeuralUCB achieves O( √ T ) regret, where T is the number of rounds. To the best of our knowledge, our algorithm is the first neural network-based contextual bandit algorithm with near-optimal regret guarantee. Preliminary experiment results on synthetic data corroborate our theory, and shed light on potential applications of our algorithm to real-world problems.
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).