Ensemble Sampling
Thompson sampling has emerged as an effective heuristic for a broad range of online decision problems. In its basic form, the algorithm requires computing and sampling from a posterior distribution over models, which is tractable only for simple special cases. This paper develops ensemble sampling, which aims to approximate Thompson sampling while maintaining tractability even in the face of complex models such as neural networks. Ensemble sampling dramatically expands on the range of applications for which Thompson sampling is viable. We establish a theoretical basis that supports the approach and present computational results that offer further insight.
This paper proposes ensemble sampling which essentially approximates Thompson Sampling for complex models in a tractable way. This will be useful in a variety of applications. There does not seem to be an obvious mistake in the proofs. However, there are a number of limitations of the proposed method. See below for detailed comments: 
1. What is the underlying noise model for the rewards? Please clarify this. 
2. The weights of the neural network are assumed to be Gaussian distributed. Why is this a valid assumption? Please explain. 
3. Please explain under what assumptions can the proposed method be applied? Can it applied for other model classes such as generalized linear models, and SVMs?
4. A neural network offers more flexibility. But is this truly necessary for applications where the time horizon is not too large, and the number of samples are limited? 
5. Missing references in lines 85 - 92. Please add citations wherever necessary. 
6. In line 3 of Algorithm 1, the model is picked uniformly at random. Can the results be improved by using a more intelligent sampling scheme?
7. Using a sample from a randomly perturbed prior and measurements seems similar to the Perturb and MAP framework in [1]. Please cite this work and describe how your framework is different. 
8. To update the models, it is necessary to store the entire history of observations. This is inefficient from both a memory and computational point of view. 
9. In line 120, "some number of stochastic gradient descent iterations". Please clarify this. How many are necessary? Do you model the error which arises from not solving the minimization problem exactly?
10. In Theorem 3, the approximation error increases with T. The approximate regret is then in some sense linear in T. Please justify this. Also, what is the dimension dependence of the approximation error? Also, please give some intuition on the linear dependence of on the gap \delta. 
11. In section 5, the experiments should show the benefit of using a more complex model class. This is missing. Please justify this. 
12. A sampling based technique should be used as a baseline. This is also missing. Please justify. 
13. In line 249, "we used a learning rate of.. ". How did you tune these hyper-parameters? How robust are your results to these choices?
[1]. Gaussian Sampling by Local Perturbations,