Ensemble sampling for linear bandits: small ensembles suffice

Thank you for your review. There is an unfortunate, but crucial, misunderstanding, in the relation between our work and algorithms such as Thompson sampling and Perturbed History Exploration (PHE), which we believe is responsible for your low scoring of our work. We have clarified these relations in our main rebuttal, which we would ask you to consider.

With the contents of the main rebuttal in mind, let’s discuss LSVI-PHE. Yes, LSVI-PHE fits an ensemble of $m$ estimates, just like we do. But, being an instance of PHE, it fits $m$ estimates from scratch at every single iteration! In contrast, Ensemble Sampling only updates each of the $m$ ensemble elements with the new received observation—so ensemble sampling does something akin to a single gradient step for each of the $m$ estimates at each timestep, whereas LSVI-PHE trains $m$ models to convergence at each step. This is a huge difference in the practicality of the methods, and the reason ensemble sampling is so interesting.

As to taking a maximum over the ensemble: this is a very good question. Yes, you could do that with our iterative updates, and you’d get a better regret bound; you would recover the regret of Thompson sampling (so, $\sqrt{d}$ loose on LinUCB). But it is completely unclear that this would give a better algorithm: after all, it is random-element-type algorithms that are used in practice (see Osband et al. 2016, Osband et al. 2018 and papers that cite these), and practitioners are pretty good at trying out different sensible alternatives. We thank the reviewer for this suggestion. We will insert a comment discussing this point in the manuscript, acknowledging the reviewer.

Regarding how the proof works for the version where the maximum is taken: Whether taking a random element or the maximum, the technical challenge in getting a bound is the same: it is showing that there exists at least one optimistic ensemble element in each “direction” of the parameter space when incremental updates are used. This result and the techniques we use to show it are the main contributions of our paper.

We hope that the above and our main rebuttal clarified the key aspects of the paper. We will use the additional page available at the camera ready stage to clarify these points to future readers.

With that said, we must emphasise that our paper solves a long standing open problem, which attracted two failed attempts previously published at NeurIPS. We believe that a well-written, sound paper with novel proof ideas and techniques that solves a hard open problem—one clearly of interest to the community—is a strong contribution to NeurIPS. As such, we would ask the reviewer to reconsider their assessment of our manuscript.

Osband, Ian, et al. "Deep exploration via bootstrapped DQN." Advances in neural information processing systems 29 (2016).

Osband, Ian, John Aslanides, and Albin Cassirer. "Randomized prior functions for deep reinforcement learning." Advances in Neural Information Processing Systems 31 (2018).

Dear reviewer,

The author-reviewer discussion period is shortly coming to an end. We were hoping to get a confirmation from you that you've considered our rebuttal, and to let us know if you have any further questions.

Clarifying the confusion about the goal of studying ES in the linear setting A minimum requirement for an algorithm that aims at some level of generality is that it should also work reasonably well in simpler settings. Moreover, if the algorithm achieves some generality, compromising on optimality in a simpler setting (in our case, the linear setting) should be acceptable. We are sure that the reviewer is also aware of the many examples where such a compromise exist or is even unavoidable (there is a large body of literature on problems of this type). Ours is the first paper that gives any sort of theoretical support for ES. Given the amount of work devoted to ES (empirical and theoretical), we think that a paper that changes this poor status quo should be of major interest (news!) to the community. We note in passing that all previous papers on analyzing ES started with the linear setting (Lu and Van Roy'17; Phan et al,'19; Qin et al,'22 -- all papers published at NeurIPS!), and their rationale for studying ES in the ensemble sampling was exactly the same as ours (see, e.g., the introduction of the paper by Qin et al.)

Another confusion that we would like to clarify is that our work does not give a definite answer to whether ES can be optimal (or even meet the guarantee TS can). While we could not obtain a result like this, ours is an exponential improvement over the previous result in terms of what ensemble size gives the optimal rate of growth of regret (up to logarithmic factors).

While we also like to think that we have high standards, expecting that every paper will close a whole area of study by providing a final answer is unrealistic and unhealthy for the community. Just to mention an example close to our work, by this standard, the LinTS work of Agrawal & Goyal (2013) also cited and perhaps liked by the reviewer, which we think is a breakthrough paper, should not have been published: As is well known, the regret bound given in this work falls short of that available for LinUCB by a multiplicative factor of size $\sqrt{d}$. Yet, this paper sparked a lot of good work in the community. Today, we even know that the extra $\sqrt{d}$ factor is even unavoidable (Hamidi et al'20). But achieving this result required the cooperation of many researchers through many years, which was greatly facilitated by reviewers who let the many papers that provided some small steps towards the final solutions to be published. In light of this, we respectfully ask the reviewer to reconsider their position as to what constitutes an interesting, publishable result.

Finally, at the risk of repeating earlier arguments, we would like to note that even if in the linear setting ES is inferior to alternatives, the alternatives loose their edge against ES as soon as the setting becomes slightly more complicated. We show this now in the deep learning setting.

On ES vs PHE in Deep Learning Suppose that our model is a neural network with $p$ parameters, and we use a standard NTK-style linearisation (see, e.g., Jia et al., 2022). TS/PHE with incremental updates gives:

• $O(p^2)$ per step computational complexity for the matrix-vector product, used for Sherman-Morrison updates
• $O(p^2)$ memory for storing the covariance matrix.

Consider on the other hand Ensemble Sampling in the NTK setting. Let $d$ denote the effective dimension of the RKHS with feature map given by the gradient of the neural network. Then the required ensemble size will be $m=d \log T$ (crucially, not $p \log T$). Updating each ensemble element requires a step (or a number of steps) of backpropagation, so order $O(p)$ runtime and $O(p)$ memory. With that, ensemble sampling uses

• $O(dp \log T)$ runtime,
• $O(dp \log T)$ memory.

Observe that $d\leq p$ always. In cases where $d$ might be much smaller than $p$, ensemble sampling is beneficial. This is why ES works in the deep learning setting, and TS/PHE does not.

One might then say: okay, why don't we implement TS/PHE with sketching? That will make the runtime of TS depend on $d$ in place of $p$. But implementing sketching for large models is very difficult, due to both numerical stability issues and choosing parameters involved in sketching. We haven't seen popular practical methods built around sketching.

We will be happy to include some extra discussion of why ensemble sampling is a sensible choice if the paper gets accepted using the extra page. This seems something easy to address would the reviewer think this to improve the paper.

In conclusion, we are not claiming that we solve all longstanding open problems related to ES, or even that we solve the hardest of these, but we claim that we solve some of these problems, which we think are of major interest to the community, especially given the new proof techniques we employ.

Thank you for the comment. We will be happy to expand the discussion of randomized methods, as indicated beforehand.

We agree with the AC on the motivations for using PHE. And if one thinks of PHE, running ES instead is a natural choice. We prove that doing so still achieves reasonable regret–-even if our result is not optimal (or maybe it is, in the sense that maybe there is a real cost to ES over PHE/TS, and a tighter result is not possible).

On "discussing in detail the pros and cons of the algorithm studied in this paper compared with those randomized methods in the literature": As confirmed in our rebuttal, we would be happy to spend the additional page granted at camera ready on this discussion. We could also include a more extensive related works section in the appendices. Nonetheless, we must emphasize that our novel contribution is theoretical, not algorithmic–-we do not introduce ensemble sampling, its already a commonly used method in the applied literature–-and there is a strict page limit. We are also not writing a tutorial paper on randomized methods, but providing a novel theoretical contribution. We are writing for an expert that understands randomized methods, and wants to know what specific tricks are required to show that ensemble sampling works: for an expert that can make the comparison between methods themselves. Nevertheless, again, we are happy to use the extra space for a discussion of the relative merits of all methods mentioned.

We must clarify two important misunderstandings:

1. Our upper bound scales superlinearly with m, but that does not mean that the regret of the algorithm scales superlinearly with m. Our bound is simply not tight when m goes to infinity (we will adjust the wording of Remark 2 to make this clear). It is tight for small ensembles, which is the crucial regime (we do not think anyone has any doubts whether ensemble sampling can work when m goes to infinity! Even previous results of Qin et al. 2022 show that it can, at least in the Bayesian set-up). Our interest is in showing that ensemble sampling as it is used in practice, with small ensembles, can work; and that’s what we demonstrate.
2. Our algorithm is not a “particular version” of ensemble sampling. It's almost the standard version, with the only requirement being a symmetrisation of the ensemble, which can clearly only be beneficial in practice and should be done anyway. In any case, we have no doubt that our result would hold without symmetrisation; but showing this would involve a much, much more tedious argument, from which it would be significantly harder to extract useful insight on how and why ensemble sampling actually works. We address this point in remark 9 of our paper.

We are happy to correct the two issues raised as “minor comments” in the way suggested by the reviewer.

Regarding remark 3: yes, one can of course use the “doubling trick” to obtain an algorithm the regret bound of which is only a constant larger. The problem is that the doubling trick doesn’t just increase the regret bound (which is harmless) by some factor, but it will increase the actual regret incurred by said factor (which is bad). The aim of our paper is to analyse the algorithm as practitioners might use it, and for the aforementioned reason, practitioners would use the doubling trick only as a last resort if ever. Thus, implementing the algorithm without knowledge of the horizon in a way that does not increase the actual regret incurred much in comparison to if the horizon were known is a problem we do not have an answer to—and one where we suspect that a good answer might not exist.

Regarding the weakness of our bound: yes the bound is likely suboptimal; but it is also exponentially better in two quantities than the previously given bound, and holds for the more stringent minimax regret criterion, rather than for Bayesian regret, as in the previous paper. We must point out that the previous paper with the much weaker guarantees was published at NeurIPS in 2022 (Qin et al. 2022), and therefore we believe that our much stronger results are more than sufficient for publication.

Note that we also detail what it would take to get a bound better than ours in Remark 10 of our paper; the required arguments around order statistics in a sequential setting are far beyond the current literature on the topic, but there is hope that it might be solvable in the coming years—time uniform concentration bounds are currently a hot topic, and work on similar questions is beginning to pop up in the literature.

In light of our rebuttal, we must ask the reviewer to reconsider their recommendation of only a “weak accept” for a paper that improves exponentially in multiple respects over a previously published NeurIPS work; a paper that solves a rather long-standing problem in theory; a paper comprising many novel proof ideas and interesting techniques.

Qin, Chao, et al. "An analysis of ensemble sampling." Advances in Neural Information Processing Systems 35 (2022): 21602-21614.

I think these results deserve recognition. I am raising my score from 6 to 7.

While our focus is on the novel proof ideas and techniques needed to get a bound for ensemble sampling, we would be happy to use the additional page available at the camera ready stage to provide more context on ensemble sampling and its relation to other methods.

To answer the reviewer’s two “weaknesses” points directly:

1. The beta featuring in our work is indeed the same as that used in LinUCB, as it is the standard confidence width multiplier used for the confidence ellipsoids of linear ridge regression, as obtained from the method-of-mixtures. However, the difficulty with ensemble sampling lies in proving that the ensemble parameters are “sufficiently spread out” in the confidence ellipsoid in an appropriate sense. Thus, while we reuse part of the ideas from standard bandit proofs (optimism), much work had to go into showing that optimism thus indeed holds (in a certain sense).
2. Regarding advantages of using ensemble sampling, as discussed in Remark 4: Ensemble sampling should only be used in settings where closed forms are not available. There are no advantages to using ensemble sampling in the linear setting studied in this work, where Thompson sampling has a closed-form solution. The linear setting is studied in theoretical work because it provides a testing ground for the soundness of algorithms: if an algorithm provably cannot work in the linear setting, chances are it won’t work beyond it, either.

With this out of the way, we ask the reviewer to consider our main rebuttal. In particular, we ask the reviewer to reconsider their assessment of our contribution as merely “fair”; we solve a long-standing open problem that has had two failed attempts published at NeurIPS. And we would ask that the reviewer reconsiders their scoring of the paper as “Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject”, since to our reading, the reviewer has not provided any significant reasons to reject, whereas reasons to accept are plentiful: a very strong theoretical contribution with interesting, novel proof techniques, on a question that has attracted much attention in the community.

Dear reviewer,

The author-reviewer discussion period is shortly coming to an end. We were hoping to get a confirmation from you that you've considered our rebuttal, and to let us know if you have any further questions.

We would ask that the reviewer confirms that they have read our main rebuttal, and to acknowledge that they understand and agree that our paper solves an open problem in the theory community that has attracted two previous failed attempts—both published at NeurIPS. With that in mind, we would ask the reviewer to reconsider their recommendation to reject our work: NeurIPS is precisely the place for well-written, sound papers that address hard open problems highlighted by the community with novel proof ideas and techniques.

We would also ask the reviewer to clarify the issue with respect to remark 3: to us, the lack of a good anytime version of ensemble sampling poses an interesting problem. We would have also liked to see some more details of as to why the reviewer thinks that remark 3 is underexplained. We acknowledge that the text can be dense, but we ask the reviewer not to forget that we are bound by a length constraint, and we think the text has just enough information to understand the issue (here and elsewhere).

As to the question regarding $\lambda$: the significance of $\lambda$ is that it is the scale of the noise injected into our estimates of the instance parameter prior to observing any data. The lower bound on lambda shows that it is crucial to inject some noise—this has already been understood by practitioners, and indeed the main contribution of Osband et al. 2018 over Osband et al. 2016 is the introduction of such “prior noise”. Our theory successfully confirms what practitioners have observed and developed an intuitive/heuristic understanding of (this intuitive understanding is outlined in Osband et al. 2019). This is a non-trivial contribution, and we will highlight it in our next revision of the manuscript.

Osband, Ian, et al. "Deep exploration via randomized value functions." Journal of Machine Learning Research 20.124 (2019): 1-62.