Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors propose a novel analysis of Thompson Sampling using ensemble sampling, which is an approximation technique in order to correct for the fact that in general, sampling from the posterior distribution of the unknown vector theta is impractical in high dimensions. The idea of ensemble sampling resembles a particle filter, where one samples a finite number of points in order to approximate the intractable posterior distribution. They propose a regret analysis which corrects deficiencies of an earlier analysis of (Lu and Van Roy, 2017).
strengths_and_weaknesses: Strengths:
- The paper is well written and easy to follow.
- The paper corrects technical deficiencies in an earlier paper
- Theorem 2 is nice in the sense that it might apply to a wider range of settings, and shows that controlling the Hellinger distance between the approximate distribution and the actual posterior yields usable upper bounds. 
- In general, the idea of finding computationally efficient alternatives to Thompson Sampling for structured bandits is a very important problem, and certainly non trivial.

Weaknesses
- Dependency on the number of arms $K$: The dependency on the regret on the number of points $M$ is very significant, and imposes that, for the regret bound to be non trivial, one requires at least $M \ge K$, and for the regret bound to be close to the regret of Thompson Sampling one requires $M \ge {T K \over d}$. Now, the number of arms $K$ is going to be larger than the dimension $d$ (otherwise one can simply ignore the linear structure and treat the problem like a classical $K$ armed bandit, and in many cases, $K$ is going to be exponential in $d$ (an example of this would be combinatorial bandits). This implies that the algorithm might not be usable in high dimensions. The authors argue that one could use $M = O( {d \over \epsilon^2})$ instead of  $M = O({K \over \epsilon^2})$ but this seems dubious. At the very least the authors could expand on this issue. In fact, determining a lower bound on $M$ as a function of $K,T$ would be very interesting.

- Noise floor when $\sigma^2 \to 0$: in the regret upper bound of Theorem 1, when the variance of the rewards $\sigma^2$ is taken close to $0$, the regret upper bound becomes $O( \sqrt{dT H(A)})$, which is probably not tight since, when rewards have no variance, it is sufficient to sample $d$ linearly independent actions in order to figure out the optimal action with probability 1, and hence the regret in this regime should be at most $O( d \sqrt{\log K})$ where $O(\sqrt{\log K})$ is the expected value of the largest gap between the optimal arm and a non optimal arm.

questions: Two questions:
- is it possible to lower bound the value of $M$ as a function of $K,T$ to ensure a regret comparable to Thompson Sampling ?
- why is there a noise floor in the regret upper bounds ? and can it be fixed ?
limitations: See above.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper focuses on the Ensemble Sampling (ES) algorithm, a method designed to approximate Thompson Sampling (TS) in settings where the exact posterior on unknown parameters is intractable. ES maintains an ensemble of plausible models and instead of attempting to sample a model from the full intractable posterior, it samples from a discrete distribution over the ensemble. It then proceeds, similarly to TS, to select at action which is optimal under the assumption that the sampled model represents the ground truth. The main contribution of the paper is to present a rigorous Bayesian regret analysis of the algorithm in the stochastic linear bandit setting, where Lu and van Roy (2017) previously presented a frequentist regret analysis that has subsequently been identified to be flawed.

The paper produces an ES-specific analysis by first deriving a Bayesian regret bound for ‘any learning algorithm’ which essentially consists of the information theoretic bounds of Russo and Van Roy (2016) for exact TS plus a term which is proportional to the cumulative differences between the action selection distribution of TS and of the alternative learning algorithm which is the subject of the analysis.

strengths_and_weaknesses: The paper is well-written, in straight-forward language and clearly presents its contributions. ES is, as the related literature attests, a practical and relevant alternative to TS and thus any valid analysis of its performance is useful, particularly since previous results have been shown to be invalid. The theoretical results are, as far as I have been able to verify, accurate. As the authors suggest, there does seem to be opportunity to extend this line of analysis to more complex problems.

In my opinion the weaknesses are twofold. Firstly, as I describe in more detail below, I feel closely related results giving bounds on frequentist regret in stochastic linear bandits are not adequately addressed. Secondly, I feel the paper could have been stronger if it attempted to push beyond the linear bandit setting, where as the authors identify, ES as an approximation to TS is not necessary and the utility of the analysis is principally illustrative. 

On this second point, I feel the paper could have been stronger if it had at least speculated in more detail as to what an analysis of a more challenging setting would look like or as to what the principal theoretical challenges would entail. Ideally, the paper would go so far as to extend this analytical technique to at least one setting where ES is genuinely required to deploy a TS-like approach. The level of contribution that merits publication is of course a subjective matter, and I am therefore not bound to the view that it is close to the borderline for NeurIPS. I will pay close attention to the subsequent discussions with authors and other reviewers to update my recommendation on this point.

questions: General: Kveton et al. (2020, UAI) present a result of a similar flavour, but in the (stronger) frequentist setting. They have (as I understand it) a bound on the (frequentist) regret of any algorithm for stochastic linear bandits, which can then be specified to particular algorithms by deriving the appropriate form of a general term. I think this is an important related piece of work which should be addressed in the present paper. My question is how does the new analysis of the Bayesian regret compare to that of the frequentist regret. Does it open a possibility to analyse algorithms for which the result of Kveton et al. (2020) cannot be used? Does it just provide a quicker route to a reasonable performance guarantee for randomised algorithms? Could a stronger analysis of ES be provided using the framework from Kveton et al. (2020)? Could the present analysis inspire some analysis in some more challenging setting where the frequentist analysis could not be so readily extended?

References:
-	Kveton, Szepesvari, Ghavamadzeh, Boutilier (2020) Perturbed-History Exploration in Stochastic Linear Bandits. In Unceratinty in Artificial Intelligence

limitations: Adequately addressed, there are unlikely to be ethical issues linked to this theoretical work.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper develops a regret bound for the methodology of ensemble sampling as applied to Linear Gaussian Bandits.  The resulting bound shows the regret to be a combination of the regret of Thomson sampling and a term to capture the posterior distribution mismatch. 
In order to prove this regret, they prove a general regret bound for linear bandits for any learning algorithm which bounds the regret by a combination of the entropy of the optimal solution and a gap between the model and exact and approximate posterior as observed from sampling. They then use this result for their own bound. 
strengths_and_weaknesses: Strengths
The paper provides the first theoretical results for ensemble sampling. 
It also provides intermediate bounds which can be leveraged by other learning methods to prove their own bounds.

Weaknesses
The paper focuses on linear bandits which are relatively simple. 
questions: It would be good to see a comparison of regret bounds for other learning methods on the linear gaussian bandits besides Thomson sampling. Though part of the bound provided by them is order optimal, it is difficult to judge the quality of the overall bound without such a discussion. 

limitations: The authors have not addressed this issue. I do not think the work has any direct negative societal impact. 
The key limitation of the work is the use of Linear Bandits which seems to be a requirement of the analysis anyways.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper aims to establish a regret bound for ensemble sampling when it is applied to the linear bandit problem. This is done through leveraging information-theoretic concepts and novel analytic techniques.

Specifically, this paper:

* Formulates the linear bandit problem and the ensemble sampling algorithm
* Provides a bayesian regret bound for ensemble sampling in linear bandits
* Motivate the general regret bound and sketch the proof
strengths_and_weaknesses: Strengths:
This paper is the first rigorous regret analysis of ensemble learning, and it provides a bayesian regret bound to it in linear bandits.

Weaknesses:
This is likely just personal taste and limitation, but it would be great if the authors could include some instructions about how this could be applied to downstream tasks like neural architecture design.



questions: Could the authors include some more detailed instructions about how this could be applied to downstream tasks?
limitations: In the conclusion section, the authors mentioned several ways the results of this paper can be used, including analyzing and approximating different sampling algorithms in different problems. It would be great if the authors could elaborate on that a little bit more.
review_title: null

Meta-review: metareview: There was broad agreement about this paper. All reviewers valued the main contribution: the first rigorous analysis of ensemble sampling as an approximation to Thompson sampling. The reviews and discussion all indicate that the paper is clear and honest in stating its contributions and supporting them with evidence, and that this main contribution is valuable. The remaining discussion revolved around finer points of scope of significance; on one hand, the setting of linear bandits was viewed as relatively simple, and some of the given bounds may not be tight; on the other hand, there is speculation that some of the analysis may apply more broadly than the simple setting considered in the paper. Overall, there is broad consensus about recommending the paper be accepted.
confidence: Certain
Decision: Accept