Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This work proposes a neural network based thompson sampling algorithm for general bounded reward contextual bandit problems.  They provide a theoretical regret guarantee for the proposed algorithm with the help of recent advances of Neural Tanget Kernel.

The main techniques that use the gradient of the neural networks and NTK have been developed in a recent paper, Neural UCB, as cited by the authors as well. Based on estimations of mean and variance developed in the Neural UCB, NeuralTS is a variant that uses a Gaussian posterior on the top of those estimations. The theoretical contribution is adapting some well-known tricks in the bandit literature to analyze the regret of TS algorithm. That is why I think the contribution is quite incremental.

The authors provide sufficient experimental data points to justify the advances of the proposed Neural TS against all the existing benchmarks, which is a plus.

Besides, I have the following detailed comments:

1. In Section 2, I didn't find a clear definition of $m$. I have to infer that it is the nework width until Algorithm 1.
2. In the entire paper, I didn't find a definition for $g(x,\theta)$. I have to infer its meaning by reading Neural UCB paper.
3. In Theorem 3.5, many parameters depend on the time horizon T. However, in some use case, we may not have the information of T and some algorithms have this advantage of so-called any-time regret bound. Is it possible to get rid of this dependence by playing some doubling trick?
review_title: Interesting idea, incremental contribution

final_score: rating: 7: Good paper, accept
review_content: *****  Paper's Summary  *****

The authors proposed an algorithm named Neural Thompson Sampling (NeuralTS) for solving contextual multi-armed bandit problems. NeuralTS uses deep neural networks for dealing with exploration and exploitation. In the paper, the authors proved the sub-linear regret of NeuralTS, which is also verified using experiments. 


*****  Paper's Strengths  *****

As NeuralTS uses the deep neural network, it can be used for estimating non-linear reward function in the contextual bandits problem.

The authors proved the sub-linear regret using the recent theoretical results from deep learning. The regret upper bound is similar (in terms of the number of contexts and effective dimension) to the regret bound of existing methods.

The performance of NeuralTS matches with the state-of-the-art baselines. In some cases, the performance is even better than the existing methods.


*****  Paper's Weaknesses  *****

The weak point of the paper is its novelty. The result incorporates recent deep learning and contextual bandits results [Zhou et al. 2019] (paper in ICML 2020) with the existing Thompson Sampling variant for contextual bandits problem.

Since the neural network (parameters m and L) is fixed before using the algorithm, it may not be possible to estimate any arbitrary reward function with the fixed neural network. Therefore, NeuralTS can have linear regret for the cases where the reward function can not be estimated.


*****  Comments  *****

It is difficult to understand the second part of Assumption 3.4. More clarity may help readers.

The experiments can be repeated 50 or more times to get a better confidence interval.


*****  Questions for the Authors  *****

Please address the above weaknesses of the paper.

How are the values of '\nu,' 'L,' and 'm' set in the experiments?

Why does NeuralTS need T as input? 


***** Post Rebuttal *****

I thank authors for the clarifications! After reading the rebuttal and comments of other reviewers, I am increasing my score. 
review_title: Paper is marginally above the acceptace threshold

final_score: rating: 7: Good paper, accept
review_content: Summary:

The paper proposes a novel Thompson sampling algorithm for neural networks which can be applied to any arbitrary, bounded reward function. While existing works apply Thompson sampling (TS) to neural networks in a heuristic way (e.g., sampling parameters in the last layer only), this algorithm considers the posterior distribution of all the parameters and is the first to provide a theoretical, tight regret upper bound. The work builds on the neural tangent kernel theory, which enables the use of techniques developed for linear reward functions (Agrawal and Goyal, 2013). Actually, the paper is analogous to the work of Zhou et al. (2020) which proposed the NeuralUCB algorithm by combining the neural tangent kernel theory and the Linear UCB methodology (Abbasi-Yadkori et al., 2011).

Reason for Score:

I vote for accepting. I believe the contribution of the paper is significant, as it is the first to construct a valid posterior distribution for the parameters in the neural networks. The method also achieves a tight regret upper bound that matches the bound of NeuralUCB. The experiments show that empirically, neuralTS performs better than the state of the art, neuralUCB.

Pros

The paper provides an efficient way for doing directed exploration in bandits with neural network reward models.
The presentation of the algorithm, theorem, and experiments is clear and concrete.

Cons

According to the proofs, the neural TS algorithm that uses initial parameter \theta_0 instead of \theta_t should have smaller regret than the current algorithm. That is to say, according to the proofs, the regret can be decomposed as (the regret of the algorithm which does not update \theta ) + (a term related to the difference of \theta_t and \theta_0).  I think the authors should add discussion about this point.
 
Minor comments

 In the last line of page 1:
“Sampling the estimated reward from posterior” is a confusing statement. Actually, we sample a parameter from the posterior. The same goes for “sampling the reward” between equations (2.2) and (2.3)

In the last line of Related work, authors mention Foster and Rhaklin. I don’t think they use UCB exploration. They also use a randomized algorithm although it isn't TS.
 

review_title: Novel and efficient Thompson sampling algorithm for neural networks

final_score: rating: 7: Good paper, accept
review_content: The paper proposes neural thompson sampling (TS) - a method to run TS without assuming that the reward is a linear function of the context, as is generally assumed in literature. This is not the first paper to use neural networks for TS, however existing papers either a) used TS only in the last layer, or b) maintained uncertainty over the weights and sampled the entire neural network. This paper instead maintains a single network that computes the mean of the reward distribution of an arm. 

The paper also is the first paper to provide regret guarantees for a neural TS algorithm. Experiments show that their algorithm performs better than other baselines.

My concern with the theoretical results is a missing discussion on their utility with respect to the assumptions. The necessary assumption for all results in the paper is Condition 4.1, which assumes that m, the width of the network is larger than T^6 L^6 K^6. With T as the horizon, this assumes a neural network width of 10^18 even for a modest horizon of 1000 (as used in the experiments). I don't think the experiments used this width in their implementation. I would like if the authors point out this disconnect for the benefit of the readers, and have a discussion section. I believe this assumption may be necessitated by the use of NTK.

Second, the algorithm uses the function g to model the variance of the distribution, but I did not find any discussion. Is g assumed to be known? If not, how is it learned?

I like that the authors study the delayed reward experiments as it is often the case in practical situations. What will also be useful is to discuss the implementation complexity (computation required to decide the next arm to be sampled) of various algorithms (ideally through a plot). Some algorithms may be faster than others, and readers can use this plot to make an informed choice.


review_title: Good paper overall; would have liked more discussion on the assumptions

Meta-review: All reviewers tend towards accepting the paper, and I agree.
Decision: Accept (Poster)