Ensemble sampling for linear bandits: small ensembles suffice
Authors: David Janz
Alexander Litvak
Csaba Szepesvari
Venue: NeurIPS 2024 poster (2024)
Keywords: linear
bandits
ensemble sampling
Primary area: bandits

Abstract: We provide the first useful and rigorous analysis of ensemble sampling for the stochastic linear bandit setting. In particular, we show that, under standard assumptions, for a $d$-dimensional stochastic linear bandit with an interaction horizon $T$, ensemble sampling with an ensemble of size of order $\smash{d \log T}$ incurs regret at most of the order $\smash{(d \log T)^{5/2} \sqrt{T}}$. Ours is the first result in any structured setting not to require the size of the ensemble to scale linearly with $T$---which defeats the purpose of ensemble sampling---while obtaining  near $\smash{\sqrt{T}}$ order regret. Our result is also the first to allow for infinite action sets.

Ensemble sampling for linear bandits: small ensembles suffice
David Janz University of Oxford* david. janz@stats ox. ac uk
Alexander E. Litvak University of Alberta alitvakeualberta.cm ca
Csaba Szepesvári University of Alberta szepesvaQualberta.
Abstract
We provide the first useful and rigorous analysis of ensemble sampling for the stochastic linear bandit setting. particular, we show that, under standard assump- tions, for d-dimensional stochastic linear bandit with an interaction horizon T, ensemble sampling with an ensemble of size of order log T incurs regret at most of the order (d 5/5// Ours is the first result in any structured setting not to require the size of the ensemble to scale linearly with T-which defeats the purpose of ensemble sampling- while obtaining near / order regret. Our result is also the first to allow for infinite action sets.
Introduction
Ensemble sampling (Lu and Van Roy, 2017) is a family of randomised algorithms for balancing exploration and exploitation within sequential decision-make making tasks. These algorithmss maintain an ensemble of perturbed models of the value of the available actions and, in each step, select an action that has the highest value according to model chosen uniformly random from the ensemble. The ensemble then incrementally updated the new observations.
Ensemble sampling was introduced as an alternative to Thompson sampling (Thompson, 1933) that is tractable whenever incremental model updates are cheap (Osband et al., 2016; Lu and Van Roy, 2017). It is thus particularly popular in deep reinforcement learning, where the models (neural networks) are trained via gradient descent an incremental fashion. Therein, ensemble sampling features directly in algorithms such bootstrapped DON and ensemble+ (Osband al., 2016. 2018), part of other methods (Dimakopoulou and Van Roy. 2018; Curi et al., 2020). and as the motivation for methods, including random network distillation (Burda et al., 2018) and hypermodels for exploration (Dwaracherla et al., 2020). Ensemble sampling has also been applied to online recommendation systems (Lu et al., 2018; Hao al., 2020; Zhu and Van Roy, 2021), the behavioural sciences (Eckles and Kaptein, 2019) and to marketing (Yang et al., 2020).
Despite its practicality and simple nature, ensemble sampling has thus far resisted analysis. Indeed, Qin et al. (2022), who showed bound of order VT on its Bayesian regret under the impractical condition that the size of the ensemble scales least linearly with the horizon T, summarise the -fate-of-the-ar in this regard follows:
'A lot of work has attempted to analyze ensemble sampling, but none of them has been successful.'
Readers familiar with the literature know that the analysis of randomised exploration methods, such as Thompson sampling, perturbed history exploration (Kveton et al., 2020; Janz et al., 2024), relies on showing that at each step there a constant probability of choosing model that overestimates the true value (Agrawal and Goyal, 2013; Abeille and Lazaric, 2017). For these methods, the analysis
Work carried out while David Janz was postdoc with Csaba Szepesvári the University of Alberta.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

is relatively simple, because the algorithms can be described as first fitting a model to the past data, and then using a fresh source of randomness to perturb the model, which is then used derive the action to be used. Ensemble sampling does not fit this pattern: here, the distribution of models given the past is controlled only implicitly, making the analysis challenging.
Our contribution is guarantee that (a symmetrised version of) ensemble sampling, given an ensemble size logarithmic in T' and linear in the number of features d, incurs regret no worse than order (d log T)5//VT. This is the first successful analysis of ensemble sampling in the stochastic linear bandit setting, or indeed, any structured setting (see Remarks and for discussion of this claim). Our result is based on (a slight extension of) the now-standard framework of Abeille and Lazaric (2017), and as such ought be possible extend (Filippi et al., 2010), kernelised bandits (Srinivas et al.. 2010), deep learning (via the neural tangent kernel, per Jacot et al., 2018) and reinforcement learning (following the work of Zanette et al., 2020).
the usual settings: generalised linear bandits
2 Linear ensemble sampling
We now outline our problem setting, a version of the linear ensemble sampling algorithm and our main result, and discuss these in the context of prior literature. We encourage readers less familiar with the motivation around ensemble sampling to consult Lu and Van Roy (2017) or Oshand et al. (2019); our focus will be on analysis. We will use the following notation:
Sets and real numbers We write N+ = ( N N+ U (0} and [n] [1 (1.2.....,,7
n2.. We or N+ when this index can be
use the shorthand (a:); for a sequence indexed by deduced from the context. For a, 6 E R. that is, for real numbers a and 6, a A b denotes their minimum and a 6 their maximum.
Vectors and matrices We identify vectors and linear operators with matrices. We write || lla for the 2-norm of a vector, and || for the operator norm of a matrix corresponding to the largest singular value, which we denote by (-)): we write s2(-), sz(-).... for the remaining singular values, ordered descendingly. For vectors u, of matching dimension, {u, v) = u denotes their usual inner product. We write By for the 2-ball in IRd, 8
OBg for its
surface, the (d -sphere, and H, for the closed half-space {u E Rd: (u, u) 2 1}.
Probability
We work on a probability space with probability measure F, and denote the correspond- ing expectation operator by E. We write a-)) for the o-algebra generated by the argument. For an event A, we write 1 [A] for the indicator function of A.
Uniform distribution We write (BB) for the uniform distribution over set (when well-defined), and U( @0m for its m-fold outer product: that is, (U1...., Um) ~ U(B 8m are i.i.d. random variables with common law (B))
2.1 Problem setting: stochastic linear bandits
We consider the standard stochastic linear bandit setting. At each step t e N+, a learner selects an action X, from action set X, a compact subset of BBj, and receives random reward Y, R that obeys the following assumption:
Assumption 1. At each time step L. N+, the agent receives a reward of the form Y, (X,, 0-) + Z. with 0* E IB a fixed instance parameter and Ze random variable satisfying
Elcxp(sZi) l (F (x(())) S cxp(s2/2), Es
almost surely, where Fi-1 (X,, X Y(-1) and A₁ is the o-algebra generated by the random variables used by the learner to select actions up to and including time t.
The learner given a horizon T E N+ and its performance is evaluated by the )reuudo-)regret, R(T),
incurred for the first T steps, defined as
R(T)
max T
c X., 0*)
1=1
The smaller the regret, the better the learner. Under our assumptions, up to logarithmic factors, the regret of the best learners is of order d (Chapters 19-24, Lattimore and Szepesvári, 2020). Our

---

main result will show that if a learner follows the upcoming ensemble sampling algorithm to select the actions .I.....Ty: the regret incurs will satisfy similar high probability bound, with slightly worse dependence on the dimension d.
2.2 Algorithm: linear ensemble sampling
Linear ensemble sampling, listed as Algorithm 1, proceeds as follows. At the outset, we fix an ensemble size m N a regularisation parameter À > and a sequence of perturbation scale parameters To, T1, 72, > O. Then, before the start of each round E N+, linear ensemble sampling computes m + d-dimensional vectors. The first of these is the usual ridge regression estimate of 0*,
Σ i=1
X.Y. where Vi-1 = Vo +
XxX and Vo AI.
(1)
The remaining m parameter vectors, which shall serve as perturbations, are the form
8L -
S
+
X.U?) for each F=
[m].
where S/ 12d is random initialisation, and is taken to be uniform on Av d and UP, U2 ................................ are random targets, uniform on the interval [-1, 1]. the past at the time they sampled and across the m-mmny replications. The algorithm then selects a random index Je E [m]] and sign & E {= both uniformly distributed over their respective ranges, computes the perturbed parameter
All of these random variables are independent of
0: 0,-1 re-
and selects action
X₃ E arg max(z, 0z)
with ties dealt with in measurable way. All in all, the vectors
0,-1 +
0,-1 + 1
serve ensemble of 2m-many perturbed estimates of 0*, and in each round the algorithm acts optimally with respect to one of these, selected at uniformly at random.
Our linear ensemble sampling algorithm deviates in two ways from that of Lu and Van Roy (2017):
1. The random sequence of targets used to fit the ensembles in our algorithm consists of uniform random variables rather than the Gaussians used in the previous literature. This choice simplifies the proofs, but our results hold (up to constant factors) for any suitable subgaussian targets, including Gaussian-see Remark 14 for sketch of the argument.
2. We symmetrise our perturbations using Rademacher random variables, which does not feature in previous formulations of the ensemble sampling algorithm. This helps create more uniform distribution of the perturbations (0') ); around zero with minimal computational overhead, and is important for our proof technique.
In Appendix A, we provide reformulation of our linear ensemble sampling algorithm that more in line with the style of presentation of the algorithm given by Lu and Van Roy (2017).
2.3 Regret bound for linear ensemble sampling
Our advertised result is captured in the following theorem. To state the theorem we need the sequence
x = VX + / /log(1/)) + log(det(V))/xd), E
Here and in related quantities, the superscripted å expresses the dependence a 8 (0, 1].

---

Algorithm 1 Linear ensemble sampling
Input regularisation parameter À > 0, ensemble size m E N+, perturbation scales ro, rI.... >
Sample (5m))e(m) ~ U(Av dis-dd-gsss
Let Vo- XI, 0o 0, and let 0g V for each j E [m]
for t E N+ do
Sample (Et, J1) [( (ml) and let 0, 0c-1 + r1-16:0
Compute an X, E arg m (2r 0z), play action X, and receive reward Y₁
Sample (U,) )e{(m] ~ -M[[-1, 1)m and let S = S/_1 + U, X₂ for each E [m]]
Let Vi Vi-1 + XxXT, 0. = Vv Eis Y,X,, and let 0j V, sy for each j E [m]
Theorem 1. Fix 8 E (0. 1] and take r, = 7 for all t E 2 5 and m 2 400 log((N///)) for N = (134/I+T/XX Then there exists a universal constant C > O such that, with probability at least 1 -- 6, the regret incurred by learner following linear ensemble sampling with these parameters in our stochastic linear bandit setting (formalised in Assumption 1) is bounded as
R(T) S Cm s6-1 (Vdr log(1 + +/(d)) + (T/A))
log(t/
for all T [T).
Remark 1. 1 2 1/T for some a > and we take À = 5 and m to be as small as possible given the constraint of Theorem 1, then
S Cad and R(T) C. (d
for some constants Ca, C > O that depend on only and where the bound on the regret holds with probability 1 6. That is, for polynomially sized confidence parameters, the ensemble size scales linearly with d log(T), while the regret scales with d5/2 up logarithmic-in-T factors. The latter scaling is slightly worse than that obtained for Thompson sampling (cf. Theorem 17), where the regret scales with d again, up to logarithmic-in-11 factors.
Remark 2. Theorem 1 does not recover the expected behaviour for large ensemble sizes; that is, as m - Do. On one hand, this is not an issue: we are interested in the practical regime where the ensemble size is small. On the other, suggests that better analysis might be possible. In Remark 12, we discuss a potential looseness in our analysis, which, if addressed, would result in the removal of a factor of m from the bound, thus bringing the regret in line with that of Thompson sampling. The technique that would be required to do so could then also be used to change the remaining vm dependence to an order / log T dependence, thus recovering a bound with the right dependence on m. However, as discussed in Remark 12, such improvements, if possible, may be hard to attain.
Remark 3. Our ensemble sampling algorithm requires the ensemble size m to be fixed in advance. As m depends on the horizon T, the method only provides guarantees for a fixed, finite horizon T, and our regret bound has a direct dependence on T. The doubling trick would be a simple, but somewhat unsatisfactory way of removing this dependence. An alternative is to grow the ensemble online. However, naive implementation of growing the ensemble size would require storing all past observations and computation per time step also growing with time, which is counter the idea of fast incremental method.
Remark 4. In light of Theorem 1, linear ensemble sampling might be seen as less effective and less computationally efficient version of linear Thompson sampling. This is correct: in the linear setting, where Thompson sampling may be implemented in closed form, ensemble sampling has no clear advantages. With that said, variants of ensemble sampling and related bootstrapping methods are popular in more complex settings where closed forms are not available (say, deep reinforcement learning, per Osband et al., 2016, 2018), and the linear setting provides an important testing ground for the soundness of these algorithms.
Remark S. Instead of using randomly sampled sign and index (Ee, Ji), we could use the upper- confidence-boure -boun strategy of selecting the actions using a maximum over the ensemble, that is
X, E arg max (z)) for Q(x) = max (xr, 6 + rr-15* J+) E (+1) [m]]- ZEX
It is immediate from the proof of Theorem I that this would yield regret bound scaling with d3/2 This raises the question of whether this max-over-ensemble approach is actually superior, or whether it's just that its much simpler analysis more readily yields a good bound.

---

2.4 Comparison to related results
We now discuss the results of Lu and Van Roy (2017), Qin al. (2022), and Lee and Oh (2024), showing that our result is the first to begin justifying the practical effectiveness of ensemble sampling. Remark 6. The work of Lu and Van Roy (2017) makes strong claims on the frequentist regret of linear ensemble sampling. However, as pointed out by Qin et al. (2022), and confirmed by Lu and Van Roy (2017) in their updated arxiv manuscript, the analysis of Lu and Van Roy (2017) is flawed. Remark 7. The only correct result on the regret of linear ensemble sampling is by Qin et al. (2022), which gives that for d-dimensional linear bandit with an action set X of cardinality K, the Bayesian regret incurred that is, average regret for 0 NO0, Ia) -ss bounded as
K log(mT) (d K)
BR(T) C CVT K - CTV
m
for some universal constant C' O. Observe that this bound needs an ensemble size linear in for Bayesian regret that scales as vT (up to constant and volylogarihmic the purpose of ensemble sampling. Furthermore, the ensemble size needs to scale linearly with K to get a log K overall dependence on K. Therefore, to tackle a bandit with X =Bg using the bound of Qin et al. (2022) and discretisation, since order 20-1 -many actions would be needed to guarantee a small discretisation error, the ensemble size m would need to scale exponentially in d.
which largely defeats
Remark Building on our result, Lee and Oh (2024) have shown that for a K -armed linear bandit, an ensemble of size on the order of K Kogg T suffices to ensure bound on R(T) on the order of (3/2v/T ignoring logarithmic-in-11 factors. This gives regret bound tighter by factor of d relative to ours, but at the cost of replacing the dimension d by the number of arms K in the ensemble size. Recalling that, K can be exponential in d (per Remark 12), their result may require rather large ensemble sizes. Lee and Oh (2024) also contribute some rather curious remarks about our proofs.
Analysis of linear ensemble sampling
Our analysis of ensemble sampling will be based on master theorem, presented in Section 3.1 and proven in Appendix B. The master theorem provides a method for obtaining regret bound for Thompson-sane saapooonn---iigg-----.. llike randomised algorithms. Thereafter, in Section 3.2, we apply the said master theorem to linear ensemble sampling, using some intermediate results proven in Sections 3.3 and 3.4, and some routine calculations that have been deferred to the appendix. Additionally, in Appendix D, we validate our master theorem by demonstrating that recovers a previous result for a more classical algorithm.
Thompson-samplingg
3.1 Master Theorem: regret bound for optimistic randomised algorithms
Our analysis of ensemble sampling will rely on the revered principle of optimism. To make this precise, consider fixed instance parameter 6* E Rd Writing (() max (2, f), we call
OPPT (0 TRd J(O) 2 J(O))
the set of parameters optimistic for 8*. We now present a 'master theorem' that bounds the regret of any algorithm that chooses actions based on randomly chosen parameter in terms of the probabilities that, given the past, the algorithm samples a parameter that falls in the intersection confidence sets and the optimistic region OPPT, This result generalises similar theorem stated for Thompson sampling by Abeille and Lazaric (2017), extending it to allow for finitely supported perturbations (critical for the proof of Theorem 1) and for finer control over the way dependencies between time-steps are handled.
ellipsoidal
Theorem 2 (Master regret bound). Fix T E N+ (+oo) E (0, 1222 1, and let (Ve, Oz)e be defined per equation (1). Let Assumption hold, recalling the filtrations (Fi)e and (Ar)s defined therein, and let (Af)s be any filtration satisfying
A-11 Al-1 C Ar,
Vt E+
Let (be) be sequence of a (F,, U At) nonnegative random variables, and define the ellipsoids
θ, 0, b.V, 1/2 B2
tEN.
5

---

Let (0t), be a (o(Fi A.)) adapped R -valued sequence and suppose that
X, E arg 2 0t), E [T].
Suppose further that there exist events Er and Ej satisfying
Er C cn (0t E O
& En E and P(ET) 21-5. (2)
Then, writing
Pt-1 P(O; E g n o(Fr-1 tENt
we have that on a subset of &T n Ef of probability at least 1 - 36, for all T E [7],
R(T) S 2 max
bi-1
2 2dz log log (1
- dA
2
/4r/++1
RE(T, Pi-1
8
We defer the proof of Theorem 2 to Appendix B.
Remark 9. To apply the theorem, we need to show that our algorithm generates (0t)e such that the probability of each 0, landing in O n 1t-1, conditional on ( bounded away from zero for all t E [T]. We have two degrees of freedom in our analysis:
1. We can choose (be),, the widths of the ellipsoids (Ot).. Larger widths may make it easier to bound (pe)z away from zero, but at a linear cost in the regret bound.
2. We can choose A4-1, the 'point' between observing Y--1 and selecting 9, with respect to which we consider the aforementioned conditional probabilities defined.
Remark 10. The introduction of Ai-1 serves to model the case where Og is sampled from distribu- tion Pt that itself depends on X1, YI, Yi,..., X..,,,,,,, in a random manner. The a-algebra A/ is then such that Pe is (F U A4 meeaurabble.
The upcoming two lemmas will be helpful our applications of the Master Theorem; both are stated in terms of the random functions v/, Rd + Rd given by
v (u) 0, + VV, 1/2 u,
LE N.
The first is the classic concentration result of Abbasi- Yadkori et al. 22011), and the second, Proposition 5 of Abeille and Lazaric (2017).
Lemma 3. Under Assumption 1, for any 8 E (0, P(VEN, 0r E of > - 6.
Lemma 4, If Assumption holds and 0r E
then for any measure Q over R2d and > 0,
Q(0OPT n vh (aB.))
2 inf Q(1 (Ha naBB))
MER
where we recall that H2 denotes the closed halfspace (u E TRd: (u, u) 2 1}.
We provide short, clean proof of Lemma 4 in Appendix C.
3.2 Proof of Theorem 1: regret bound for linear ensemble sampling
Let lo, Ii.... be the sequence of random matrices in d with the jth column given by r = V, -/ s/ such that 0² V
Recall that S s + Ei=, X and observe that each (S*), is vector vector-valued random walk with increments given by (U,X)),, where (X,), is a serially correlated vector-valued sequence and (UF), is a sequence of independent 41[-1, 1]) variables, and (IY), is normalised version of (S/). ) Consider the extremal singular values of Tt,
sa (T.))
min [1Tull2 2 min WES
(1%% and s1(T') - max I|T ull2. WER
wEBd-1
The lower of these may be interpreted as capturing how well the columns T .I....IT cover all directions Sq 8d-1 and the upper, their maximal deviations from zero. The following theorem, proven in Section 3.3, shows that, for sufficiently large m, with high probability, for all / (7), all the singular values of I 1-1 are the order of mm.

---

Theorem 5. For X 5 and m 2 400 1og + T) V 10d, the event
Er fvt E (T), vm/7 7 - (a (T s 10/m/7)
satisfies P(Er) 2 NTe 1,क where N (134 1
Proof of Theorem I. We will use the master theorem, Theorem 2. We let the filtrations (Ar), and (At), needed in this theorem be defined recursively via
Ag (S....... ST", A, o (J), and Ai Uo U()), With this, the conditions concerning these filtrations hold.
We let b, a&8 for 10, for each E N, which is (Fr U Al) required. For the two required events, we take the event Er from Theorem 5 and the event E7 = NeeNt0. E (BB)). To see that these satisfy the requirements given in equation (2), observe the following:
Conditions on Ey By our assumptions on and X, the conditions for Theorem 5 are satisfied.
Hence, P(Er) 5. 8. We now show that on &r, for all E [T], 0g Ot-1- Note this is
equivalent to the statement that on &r, for all E (7], T ll b-1//r-1 10/m/7. And indeed, on Er,
1 ll2 I max, |T/ S (T & 10/m/7, vE [T]
(3)
Conditions on Ej. Since a 2 1, the (IB)) C the (alB)) Or, and thus, by Lemma 3, 0, E O for all N jointly with probability at least -
remains to lower-bound the sequence (pt).- For this, define P--1()) = P(: 1 1-F--1-A ((-1) Fixing E N+, writing Q(A) (0, E A), we have that on E/.
Pt-1 = -(O0PT n
> inf Q Q(v2-1 n)B))) wES
(Lemma 4)
inf P (76,1 e (H, (
(definition of 0,, Q)
wEB
inf Py. 1 Hn naB
(W6 is bijection)
wesd
inf wE
Σ
1|7s| Hu naB3)
2m
(+1))
where the last equality used the definitions of PP F and A/-1.
We now show that on εr, regardless of the choice of u, for at least one (s,j) E {+1} x [m]. 7aT E H naBy. Assume thus that & holds. First observe that for any (s, by equation (3), 7sTl_ E alBo Hence, it remains to show that for any u, for some (s.j), 7817 t-1 E Hy; this holds because for any u.
(7T < 1
1
(7T)
u/² max 2-,,
(4)
Hence, on Er n E7, Pi-1 2 1/(2m) and thus by-1/Pt-1 S 3/2 pp_ Inserting this bound into the regret bound of Theorem 2 establishes the result.
Remark 11 (On symmetrisation). If the algorithm were run without symmetrisation, following the steps of the proof we see that we need to show that on Er, regardless the choice of u, for a the presence of symmetrisation, the equivalent statement
least one of j E [m]. 7T/ E Hu is that regardless of the choice of u, for at least one 'particle", j. we have either 7T 1 E H,, or 7 H_ Through equation (4), the latter reduces to studying quadratic forms, which lead to convenient algebra.
7

---

Remark 12 (Can we improve our bound?). For any u E S2 we lower bound the maximum max;(7T),-1) u2² by the average 1 1 ( u)² which we show exceeds 1. thus establish- m ing the existence of at least one element = :-1 H. (out of 2m). This gives a 1 1/(2m) lower bound for Pt-1- However, lower bounding maximum by an average might be wasteful. If. in- stead, we managed to lower bound the median (or any other fixed-proportion order statistic) of (7];-1,u),,... ,...., (7I t-1: u,)², we would be able to conclude that pt is lower bounded by constant (since constant proportion of "particles' are then contained in Hgah, and thus conclude that linear ensemble sampling performs similarly to Thompson sampling (see Appendix D for an analysis of the latter). However, order statistics are considerably more technical to work with than averages, especially in non-i..d. setting, and we do not currently know if such result is attainable (for order statistics, see Gordon et al. (2012) and Litvak and Tikhomirov (2018) and the references within).
Remark 13 (Upper versus lower bound). When it comes to singular values, the difficulty is usually in the lower bounds. This is so for our problem as well. Consider our use of the upper bound in the middle inequality of equation (3): all we really needed there is that [|T._lll is upper bounded for all j E [mm] and L E [T]. But, for any fixed j E [m]] we can apply the standard method-of-men oof-mitures of bound of Abbasi- Yadkori et al. (2011) to obtain that [IT/-lll = O log T) for all t E [T]. An application of the union bound over the j E [m]] then recovers what we need, up to logarithmic terms. We note that the vd factor is strictly necessary, per Lattimore (2023).
3.3 Setting up to prove Theorem 5: bound on singular values
Theorem 5 for t = 0 follows by standard methods (see Appendix E for proof):
Lemma 6. Whenever m 2 10d,
P (vm/25 sa(To) S (T S /3m/2) 2 1 mmm224
To extend the result to t > 0, we will consider the processes (R( and (Re(w)) defined for M E Rdd u + by
(T( = (u, S/y2 and Re(u)= = 1 Σ R2(
|ulB
Note that for e- = V u F 0 one has (2( = (v. / Since V is positive-definite (and hence bijection when viewed as a linear map) we observe the following relations: Claim 7. For all & 2 0, j E [m]]
(v, T
sT(,.)
sup Ru(w)) = sup u
=|T and sup (u = sup uşب
||012
oft ml ml|uu
v
m
and likewise inf unf Ru( (T))))/ m
In the upcoming section (Section 3.4) we establish the following bound on Ru) for fixed u S Lemma 8. Fix s and X 5. Suppose that m > 400 log(3 + 2T'). Then, there exists event Er with P(E+)= > 1 - Te too such that on Ey n 2 < Ro(u) < 3).
9
5
< R,(u) S
Vt [
100
3
Our proof of Theorem 5 employs the above pointwise bound together with a covering argument over $2 For that, we need the following Lipschitzness result, proven in Appendix F (by simple algebra), and standard bound on the size of c-nets of s sd-1 (Lemma 4.10 in Pisier, 1999).
Lemma 9. On Sy sd-1, Rg is L-Lipschitz with L S /ttp///lll///1///m////
Lemma 10. For all in (0, 11, there exists e-net N of with [V s (1 +1+23 2)
Proof of Theorem 5. Let No be a minimal e-net of s and define the event
E. = Yu E No, Vt E [T] 100 < R((v) = 3
8

---

We will now confirm that, for a suitable choice of e, & is a subset of the event in Theorem 5, and that P(E,) 2 2 150, which establishes the theorem.
Let u - and v Ne be such that ||u v 2 S e. From Lemma 9, and choosing
VA/(L32VT++ A), and noting that 11 - V + X, we get
1| 1/2
|ell
RR(u)= Re(v))
S
mvx
33m
Then on &,, for our choice of c,
|
5
|T
||l sup (u) S sup (u) + u
vEN.
33
3
33
Solving for ||r, we have that |Tr| = (1
165
96 m.
The same argument also gives that, on &..
(T 2 m inf Rs (v( 1
rr
3
2
m
2
m
MEN.
33
100
33
100
Loosening these bounds slightly, we have that on E., vm/7 7 S (T)) S $1 (T.) S 10/m/7.
The probability that occurs is at least the probability that the event of Lemma 6 occurs and that the event of Lemma 8 occurs for each u E Ne, noting that the former ensures S Ro(u) S for all N,- Taking union bound over these events, we have that
P(E.) 2 e 24
T 400 >
T(M + 1)e 400
We conclude by noting that, by Lemma 10, for our choice of N 2 Wi
3.4 Proof Lemma 8
Since we now consider fixed u S we will write R == (R) and R₂ == (u). Let (Af)), be the filtration given by A" (AA, U (f441, Je+1)) for each N. and let E denote the (F,, U A" o (Xx()))) (xx+1)) expectation, which will be used to integrate out the random targets U11 ........ U
With that, we define
D. = E" Re+1 Rd and W4+1 R141 E,, Re+1
be the drift and the noise of the process (Rt) respectively. Also let
Q = (u, Xx+1) /
be the strength of the drift. These are related by the following two results:
Claim 11. D. = fu for all t E N.
Lemma 12. For any T E N+ and m 2 400 log(3 + T), there exists an event & with P(E) >
1 Te 400, such that on E n (Ro I 2), for all <T
Σ W41 <
3 + Σ Q.Ri
10
The lemma is proven Appendix G, and the claim in Appendix The constant 2 above just the almost sure value of E )²]; see also Remark 14 for discussion of the significance of the (U/41)2 terms and how we bound these in the proof of said lemma.
Proof of Lemma 8. Fix < St T. We can decompose R
Ri+1 R - EE R&+1 + E Re+1 Rs - R₁ = W.+1 + Dr + Rs,
which unrolled back to and combined with Claim 11 gives that
R++1 = R2 +
2 3
Rs
Q + Σ W
(5)

---

Observe from the above that the process Ro, Ri.... drifts towards 2 with strength proportional the level of deviation, scaled by Q;- We will now show that on the event of Lemma 12, whenever R, moves sufficiently far away from 3. the drift will overwhelm the effect of the noises (Wi),. Assume henceforth that the aforementioned event holds.
3'
Lower bound. We consider the excursions of (Re), where it goes and stays below 1/2. Let 0 S << s S T be endpoints of such maximal excursion, in the sense that Rt 2 1/2, R +1,...... ................................ R. 1/2 and if 8 + 1 < 'I' then Ra+1 2 1/2. Our goal is to show that for any S t < 8, R&+1 2 9/100, which suffices to prove the lower bound. Fix E s). From equation (5) and since the event from Lemma 12 holds, defining a = 1/10,
Re+1 2 R, +
Σ
2
Rí
Qi
a 3 Σ QiRk
3
1=1
2
- (1=(1aa) +30 - -3a +
Σ
-11
(1
R) Qi
3
1=1+1
2 11
2 (1 - (1+ + 30, 3a +
Q:
3 20
(Rr+1...., R, < 1/2, def. of a)
2 (1 - (1+a)Q+) -3x
0.,20,3 3 26 > 0)
11
2 (1 50 10
33
(Q: 1/15 R 2 1/2, def. of a)
9
100
Upper bound. The upper bound follows near-verbatim, taking with R, S R
The proof of Lemma 8 was where we use that the targets (UF) are uniform or, in particular, that they are bounded random variables-for for each W++1 features (U/)² terms, and might otherwise be only sub-exponential. Of course, in that case, we would simply use a truncation argument: pick some truncation level a > 0, set W [+11 W A a for each t E N and work with the process given by the recursion R1+1 = W + D. + Rt Then, Rg 2 R2, for all t E N. and the truncated noises ( are once again subgaussian, so our approach to lower bounding Rd would also work for Rt, We could then establish what we needed from the upper bound (that is, a bound for the quantity in equation (3)) as discussed in Remark 13, which does not require bounded targets.
Remark 14.
4 Discussion
We showed that linear ensemble sampling can work with relatively small ensembles, providing the first useful theoretical grounding for the method (see Remarks and 7 for comparisons). We do, however, believe our result to be loose (see Remarks 2 and 12 for discussion); resolving this would make for an important step forward. Moreover, our algorithm uses a certaín symmetrisation not used within the work of Lu and Van Roy (2017) (see Section 2.2 and Remark 11). While this symmetrisation comes with no particular downsides, we would nonetheless be curious to see whether there is a clean way of making the analysis go through without it. A natural further question is whether dilemma. On
the idea of adding noise to the rewards is the right approach to the explore-vs-explle this, first, in Janz et al. (2024) we showed that beyond the linear setting, it is losses rather than rewards that should be perturbed- with the two approaches being equivalent in the GaeasiGa setting. Second, the very recent work of Cassel et al. (2024) shows that in the multi-armed bandit setting, a simple bootstrap-base method, which takes a max over the ensemble (as in Remark 5), yields instance dependent bounds. This raises the question of the trade-offs, if any, between randomising over the ensemble and taking a maximum, and between bootstrapping and using perturbations.
10

---

Acknowledgements
We thank Alireza Bakhtiari for proofreading the manuscript. Csaba Szepesvári gratefully acknowl- edges funding from the Canada CIFAR AI Chairs Program, Amii and NSERC.
References
Y. Jobasi-Yadkoots D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 2011. Cited on pages 6, 8.
M. Abeille and A. Lazaric. Linear Thompson sampling revisited. Electronic Journal of Statistics, (1(2):16355111 2017. Cited on pages 1, 2, 5, 6, 15, 16.
Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In Interna- lional Conference on Machine Learning, 2013. Cited on pages 1, 15.
S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013. Cited on pages 13, 17.
Y. Burda, H. Edwards, A. Storkey, and O. Klimov. Exploration by random network distillation. arXiv preprint arXiv.1810.12899 2018. Cited on page 1.
A. Cassel, O. Levy, and Y. Mansour. Batch Ensemble for Variance Dependent Regret in Stochastic Bandits. arXiv preprint 20t::2400085700 2024. Cited on page 10.
S. Curi, F. Berkenkamp, and A. Krause. Efficient model-based reinforcement learning through optimistic policy search and planning. Advances in Neural Information Processing Systems, 2020. Cited on page 1.
V. H. de la Pena, M. J. Klass, and T. Leung Lai. Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. The Annals of Probability, 2004. Cited on page 18.
M. Dimakopoulou and B. Van Roy. Coordinated exploration in concurrent reinforcement learning. In International Conference on Machine Learning, 2018. Cited on page
V. Dwaracherla, X. Lu, M. Ibrahimi, Osband, Z. Wen, and B. Van Roy. Hypermodels for exploration. arXiv preprint 2xXiv22066.04444 2020. Cited on page 1.
D. Eckles and M. Kaptein. Bootstrap Thompson sampling and sequential decision problems in the behavioral sciences. Sage Open, 9(2)21158244119551677 2019. Cited on page 1.
K. W. Fang. Symmetric multivariate and related distributions. Chapman and Hall/CRC, 1990. Cited on page 16.
Filippi, O. Cappe, A. Garivier, and C. Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems, 2010. Cited page 2.
Y. Gordon, A. E. Litvak, C. Schütt, and E. Werner. Uniform estimates for order statistics and Orlicz functions. Positivity, 16(1):1-28, 2012. Cited on page
B. Hao, J. Zhou, Z. Wen, and W. W. Sun. Low-rank tensor bandits. arXiv preprint arXiv:2007.15788, 2020. Cited on page 1.
A. Jacot, F. Gabriel, and C. Hongler, Neural tangent kernel: Convergence and generalization in neural networks. Advances Neural Information Processing Systems, 2018. Cited on page 2.
D. Janz, S. Liu, A. Ayoub, and C. Szepesvári. Exploration via linearly perturbed loss minimisation. In International Conference on Artificial Intelligence and Statistics, 2024. Cited on pages 1, 10.
B. Kveton, C. Szepesvári, M. Ghavamzadeh, and C. Boutilier. Perturbed-Hiisory Exploration in Stochastic Linear Bandits. In Proceedings of The 35th Uncertainty Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pages 530-540. PMLR, 2020. Cited on page 1.
11

---

T. Lattimore. A lower bound for linear and kernel regression with adaptive covariates, In The Thirty Sixth Annual Conference on Learning Theory, 2023. Cited on page 8.
T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020. Cited on pages 2, 13, 18.
H. Lee and M.-h. Oh. Improved Regret of Linear Ensemble Sampling, In Advances in Neural Information Processing Systems, 2024. Cited on page
A. E. Litvak and K. Tikhomirov. Order statistics of vectors with dependent coordinates, and the Karhunen-Loove basis. The Annals of Applied Probability, 28(4):2083-2104, 2018. Cited on page 8.
X. Lu and B. Van Roy. Ensemble sampling. Advances in Neural Information Processing Systems, 2017. Cited on pages 1-3, 10, 13.
X. Lu, Z. Wen, and B. Kveton. Efficient online recommendation via low-rank ensemble sampling. In Proceedings of the 12th ACM Conference Recommender Systems, 2018. Cited page 1.
I. Osband, J. Aslanides, and A. Cassirer. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems, 2018. Cited on pages 1,
I. Osband, C. Blundell, A. Pritzel, and B. Van Roy. Deep exploration via bootstrapped DQN. Advances in Neural Information Processing Systems, 2016. Cited on pages 1, 4.
I. Osband, B. Van Roy, J. Russo, Z. Wen, et al. Deep Exploration via Randomized Value Functions. Journal of Machine Learning Research, 20(124):1 62, 2019. Cited on page 2.
G. Pisier. The volume of convex bodies and Banach space geomelry, volume 94, Cambridge University Press, 1999. Cited on page 8.
C. Qin, Z. Wen, X. Lu, and B. Van Roy. An analysis of ensemble sampling. In Advances in Neural Information Processing Systems, 2022. Cited on pages 1, 5.
M. Skorski. Bernstein-typp -tppe bounds for beta distribution. Modern Stochastics: Theory and Applications, (0(2):211-228) 2023. Cited on page 16.
N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In 2010. Cited on page
W. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-22)) 2944, 1933. Cited on page 1.
R. Vershynin. High-dimensions probability: an introduction with applications in data science, volume 47, Cambridge University Press, 2018. Cited on page 16.
Yang, D. Eckles, P. Dhillon, and S. Aral. Targeting for long-term outcomes. arXiv preprint arXiv:2010. 15835, 2020. Cited on page 1.
A. Zanette, D. Brandfonbrener, E. Brunskill, M. Pirotta, and A. Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, 2020. Cited on page 2.
Z. Zhu and B. Van Roy. Deep Exploration for Recommendation Systems. arXiv preprint arXiv:2109. /20009/22000 /2509, 2021. Cited page 1.
12

---

A A reformulation of Algorithm 1 in the style of Lu and Van Roy (2017)
Below in Algorithm 2, we list reformulation of Algorithm written using updates in the style of Lu and Van Roy (2017), with one difference: the algorithm here accepts only single time- time-stationary perturbation scale r > (this unavoidable with the Lu and Van Roy (2017) style of updates). Taking r = 7,34 where 3 the deterministic upper bound on B0. P...... : S4 given by
3 vĀ+ log((1)))) d (d d/)
allows the same guarantee as given in Theorem I, but with B4 in place of 33-11
Algorithm 2 Equivalent form of Algorithm 1 assuming time-stationary perturbation scale r
Input regularisation parameter half-ensemble size m N+ perturbation scale
Let Vo AI, sample (wz) ~ U(v ds 1 yam and let w wy for each j [ml]
for t E N+ do
Sample Jr ~ ( 2m.]
Compute an X, E arg maxx (2, w play action X, and receive reward Y,
Sample (U²) Jm(m) ~ u([[1, 1))8 and let U. - for each [m]] Let V, Vt-1 + X,X,, and let w (V-- X.YY, + rU()) for each j E [2m]
To confirm that Algorithm is equivalent Algorithm 1 if the sequence To; P1y... is set to the common value r, it suffices to compare the list of parameters w:- wi........ w used here with the list
0 + r i....... P + rō r
each step of the algorithm. We leave this a simple algebraic exercise for the reader.
B Proof of Theorem 2: master regret bound
We need the following concentration inequality, a simple consequence of Exercise 20.8 in Lattimore and Szepesvári (2020)² and Hoeffding's lemma (Lemma 2.2, Boucheron et al., 2013), and the elliptical potential lemma (Lemma 19.4 in Lattimore and Szepesvári, 2020).
Lemma 13. Fix 0 < 8 < 1. Let (ft) be real-valued martingale difference sequence satisfying Iel < с almost surely for each N and some e 0. Then,
2
Vo +1
3r:
Σ &
2 1)
Lemma 14 (Elliptical potential lemma). Let (De)eeNt be a sequence of vectors in Bd, let Vo = XI for some 2 and Ve = Vo + Ei= Nıae for each E N Then, for all t E N+,
| | < 2dlog (1 (1+
)
T
Xd
Recall that J(Ø) maxxex (x. 0) is the support function of X, and observe the following: Claim 15. For any E N+, X, is subgradient of J at Or.
Proof. Fix t E N For any 0 e Rdd
J(O.) (X,, 0.) (X,, ( 01) = (X,, < max (z, 0) J(H).
(6)
xE
which is the inequality that defines subgradient.
"The statement of this result within said exercise contains a typographical error. in that the e² appears outside the brackets, rather than multiplying just the The version here is the correct result.
13

---

Proof of Theorem 2. Throughout this proof, we work on the intersection Ey n E and therefore in particular use that for any t E [T] f. H* E Φ We let 7 Vy-weighted Euclidean norm width of O in the sense that
2b,, and observe that this is the
Y max
0'11v, 0,0' Oc)
We will also use the shorthands F; = (F U A.), P. = P(- FF)) and E; = E/- F-
The proof is based on decomposing the regret into two parts, which we then control separately:
R(T) Σ (J(0*) J(O()) (J(O.) (X,,
(8)
Fix t E [r] and consider the second term, J(O() - (Xe: 8*). We have that
J(O.) (Xe, 0*) = (X,,0, - 0*) S || 11 0 llv S n- xxlll,
(9)
where the first inequality is by Sauchy-Schwarre the second uses that 0c, 8 E O--1 and then equation (7).
Now consider the first term, J(0*) (O.). Let 0 be minimiser J over 0,-1 (which is well-
defined, since J is continuous and θ, closed) and let 6+ be an element of Q n 0 (which is
non-empty, since it contains least 0*). Then, since 0", E O we have the bound
J(0") J(a.) _ J(0*) J(( S J(0*) J(0)))
It follows that for any probability measure Q over O n n
J(0)) ((0)) - J(0 J(0 J((0))-((000))) dQ((t))
Let 0 = 60PT n 1 and take Q = Q:-1 in the integral above defined by
(0 E (
Pt-1 0; otherwise,
Q--1 any arbitrary probability measure,
which yields the bound
J(0") J(Oe)
1
EE,, J( ))1(0, 6,TT1,
Pt-1
where for pt we take the upper bound to positive infinity. Observing that X, is subgradient of J at 0, (Claim 15 and equation (6)) and applying Cauchy-Schwarrz. we have that
(0c) ((0) S (X,, 0-) s | |00 0g llv._.>
Moreover, since 0- E O observing that norms non-negative, that O C C and using equation (7),
|10 0.11 v. 10, E 0 < |00 - 0.1lv, 10, E 0,-1] S #t-
and therefore, since 7 is F measurable (by assumption), we have the bound
E J(0 1) e 0PPTI s Tt- E2
Pi-1
Pt-1
Chaining the above inequalities and writing these in terms of A, = Xe have the bound
|xelvyzt we
1(0)) ((.)) < 2-
20-1
(1xelly, + Ao).
(10)
P
Pt-1
Combining equations (9) and (10) with the regret decomposition in equation (8),
R(T)
2--1
|X, v
7t-1 A.)
<
max K-1 :E|T]
2
|
v +
Σ A
Pi-1
Pi-
Pi-1
1=1
(11)
14

---

for any 7 E [T]. For the first sum in that upper bound. by Sauwhy-Schwartz and the elliptical potential lemma (Lemma 14, which can be applied because by assumption À 2 1). for any N
|xellv
r
S 2rdloog (1+ dx
(12)
To deal with the second sum, observe that since for all t E N Vi-1 ł AI and X₁ E Bg
| (X,, x, < | & 1/A and
A S 2/VA for all e
Moreover, observe that (Ae), is an addptted martingale difference sequence. We thus apply Lemma 13 with = 2/v X,, to obtain the deviation probability bound
/A/
AT
BreNt E 2(4T/>+ lo
S
8.
(13)
The bounds the sums, equation (12) and equation (13), when inserted into equation (11) and combined with a union bound, yield the claimed result.
C Proof of Lemma 4: optimism for elliptical confidence sets
Lemma 16. Let F R2 IR be convex function and let be maximizer over the unit ball. Then, for any E H. = {u E Rd: (v, u. 2 11, we have F(v) 2 F(u).
Proof. For any E IRd with (v, u) > 1, the ray from v to u enters the interior of the unit ball. Hence, for any such v, there exists a z E B3 and a E (0, 1) such that u = az + (1 ar)u. By convexity and maximality,
F(u)= = F(az + (1 a)u) S aF((2) + (1 a() aF +1 (v).
Hence, F(u) < F(v). Since any finite convex function on an open set is continuous, the result holds for any V E Hu-
Proof of Lemma 4. Write F= J vi; since J is convex and v is affine, F is convex. Let ut be the maximiser of F over IB.. Since F is convex function and By is convex set, ut aBg Sy By assumption, 6* E ubf (Bg), and so J(0') s F(ut). By Lemma 16, F(ut) s F(u') for any u' E H.t. Thus, oft (H,+) C OOPT, and so
OPT n (aB)) = v (H,+ ) n 2he (aBB) v (Hat O naBg)
Therefore, for any measure Q on Rdd Q(0OPT n n (aB:)) 2 Q(v)(Hat n nBB3)) > inf (H.
wEs
D Analysis of Thompson sampling via our master theorem
Algorithm is a version of Thompson sampling we call confident linear Thompson sampling. is extremely simple: at each step & E [7]. it picks an action X, that is optimal according to estimate 0, sampled uniformly on (vdB)) differs from usual linear Thompson sampling Agrawal and Goyal (2013) through the use of uniform sampling distribution.
O,- v d-ditllation of the ridge regression confidence set.
Remark 15. Our use of the uniform distribution to generate perturbed parameters is purely for the sake of a clean exposition, and for easy comparison with our linear ensemble sampling algorithm. Observe that the usual analysis for the Gaussian (or subgaussian) case begins by restricting to high--robabillng event where every 02 lands within some inflated version of the corresponding O,-1 (as in Agrawal and Goyal, 2013; Abeille and Lazaric, 2017).
15

---

Algorithm 3 Confident linear Thompson sampling
for t E N+ Sample U2 U(v diBd) and compute 0, (
Compute some X, arg max (i, Ot), play action X, and receive reward Y
Theorem 17. Let Assumption 1 hold. Fix 8 (0.1] and let X 1. There exist some universal constami C >> O such that with probability - ō, a learner using Algorithm 3 incurs regret satisfying
R(T) & CBL_ivd [V 7/(Ad) + (V(e))//((////// (Tg/))oo((T/(A))
for all T [T].
The above result recovers the same regret bound for confident linear Thompson sampling as that given by the analysis of Abeille and Lazaric (2017). The proof is as follows.
Proof of Theorem 17. Take T = co. Fix b, vd for all t E N. As each 8g is a uniform random variable on θ;-1 for all N, and so event &r holds almost surely. Moreover, as for ensemble sampling, we take E to be the event from the standard concentration result for ridge regression, Lemma 3, observing as before that, 1
(Vdd)) (b,
We pick A/-1 A,-1 for all E N Now, to lower bound each Pt-1. note that on E7, by Lemma applied with Q(AA) ( E A (F U 1) (0, A).
Pt-1 = (0, E 00PT n no,-i)
(H, n V d inf Fr (0, E (H, west
And, since v6_1 a bijection and U, is uniform on vTBg and thus rotationally invariant,
inf (0 E w (Ha VdB:)) inf MEBH
PU E Hu n VdBA) = U(H n nVdBs)
uE3y
As established in Appendix A of Abeille and Lazaric (2017), u(H n VBB)) > 1m
b-1 independently of d. This means that, Et, Pr-1 16 for all f E N plugging this into the regret bound of Theorem 2 yields the claim.
E Proof of Lemma 6: singular values at initialisation
Lemma 6 follows by taking =
81m and 20 in Theorem 18. 2500
Theorem 18. Let U E Rmndd 2 d, be random matrix with independent rows U1,..., Um
distributed uniformly on vasg-1. Then, for all y > 0, c C 102).2), and with = =1/(1 2c), IP covD < (U) S (U) S vm+ + c.vT) 2 exp(-3:p + log(2(1 (1 + 2/e)())
The proof of Theorem 18 follows the approach of Chapter 4 of Vershynin (2018), but makes the constants explicit. For these constants, we will need the following claim:
Claim 19. Fix E S sd-1 let U($ and X2 x). Then, EX2 g 1/d, and for some c 0 satisfying 2/d and S 4/d and all 0 s 1/c.
/22v/2
Eexp(8 xx2 EX2) < exp
1
Proof. It is known that x ~ Beta(}. d-1) (see, for example, Theorem 1.5 and the discussion thereafter in Fang, 1990). the expectation of which is 1/d. We thus need only look up moment generating function bounds for beta random variables. Skorski (2023) derives such in their proof of their Theorem and our result follows by substituting in the parameters of our beta distribution, and bounding the resulting y and crudely.
We will need the next two results from Vershynin (2018), appearing as Lemma 4.1. 1.5 and Exercise 4.4.3 respectively.
16

---

Lemma 20 (Appropximate isometry), For any matrix A E m and 2 0,
| /11 eev = 1- sc(A) - $1 (1) S ce
Lemma 21 (Quadratic form on a net). For a symmettrc matrix A Raxd and an e-net N of with E (0, 1/2).
|ll - I- 2E zEN
sup (Ar,
Proof of Theorem 18. Fix x E Sy and consider 2 serve that each U U(S; thus, by Claim 19 and since UI...., Um are independent, adopting the notation of the claim, we have that, for all 0 < sd/m < 1/c.
|0 d En / Ob-
E exp(( 1 1
II E Eex 3=1
sd X2
EX21 S exp
[22dv// (2m)
1 csd/sdm m
1| is what Boucheron al. (2013) would term sub-gamma with parameters (dvv/m, cd/m rd/m) on both tails. Applying the maximal-fomm of the there-stated Bernstein-type bound for sub-gamma random variables, a union bound over the two tails, and the bounds v S 2/d² and S 4/d from Claim 19, we have that, for all O.
Thus, |z?
2 x
2 y/m V y/m) 2e 33/8 23/88
Now let Ne. c E (0, 1/2), be an c-net of S Sd-1 By Lemma 21,
12 S 1 2E ZEN.
max 2 1/.
sup #ESt
Also, by our bound on nets from Lemma 10, [W,| < (1+ 2/eed, Thus, taking union bound over x E Nr. we have that for any > and e E (0, 1/2), the probability that
13 1|
1
(Vu/m V//m)y//m)
2 1 - expl + (og(((1++//e)))
sup
2c
We conclude the proof by observing that sup suppes--1 |2 1 110TUmm Ill and applying Lemma 20.
F Proof of Lemma 9: Lipschitzness result
Proof of Lemma 9. Fix u + 0 and let = = v.1/2 Then,
1 m m
m (2, 1222
|T
(u)
R (u)
||
m m||
m
j=1
Now note that for all non-negative a, b, A, B with b 2 a,
A
B²
A² a²) + (A² B²)a²
2A²2 a²
b - a
A ( + +B)
a
62
=
2212
b
62
Let u, U E $2 gd-1 z V2/22u u. w 22/2u. u. Let e = | -lu-vla 0/12.
Let A = |||
B = | w 2.
|| b= |w||2. Assume without loss of generality that b > Since E S and b 2 vX.
2 b al
A2
2| wilk < 2
| 2/2
a²
b
VA
VA
and likewise
(A+
A B)
TTT w)ll2
|V Ví
<
2||[T|||
c.
62
VĀ
Putting things together, we have
Re(w) - R((U)s
myx X
17

---

G Proof of Lemma 12: concentration result
This proof will require the following definition of conditional subgaussianity. and the standard de la Peti-ttype concentration result for sequences of such random variables, stated thereafter.
Definition 22. Let A, B be random variables and F o-algebra. We say that A is F-conditionally B-subgaussian when B is non-negative and F-measurable, and for all E I.
[se) | exp(s B² [2] almost surely.
Lemma 23. Let (A,, B,, H4)s be such that each A, is H Ho-conditionally By-subgaussian. Then, for any 2, y > 0,
log 1 1+ 1 Bi ))
P Fr N:
Σ Ai
Σ B //
S/-
Lemma 23 is an immediate consequence of Theorem 2.1 in de la Pena et al. (2004), in particular comparing our Definition 22 with their condition (1.4). For more background, see Lattimore and Szepesvári (2020), Lemma 20.2, and the surrounding discussion.
We will also need the following three claims, verified in Appendix H. Therein,
V 2Q + QuR.
Claim 24. Each W1 is a (F,, U A -conditionall o,/
-atp://oonnnloooo///o/moooasaaa /m-suggaussiinn
Claim 25, For any 0 < < t < T, + Ei_, of S 3 - Q,R,
Claim 26. For any 0 < L r T, on the event (Ro s 2]. + Ei_ 53
Proof of Lemma 12. For any < T. by Claim 24 and Lemma 23 applied with 1/m and any O, with probability exp( }), for E (T....: 1}.
2
Σ Wi+1
log Eoi+1))
+
Σ of -1)
We take x = (3 + 2T), which by Claim 26 exceeds log(E> i-r of 1) on {Ro S 2). Therefore, on the intersection of {Ro s 2} and the event implicitly defined above,
Σ W
2x
Σ
of
+1.
By our assumption on m, / //x/m m S 1/10. Also, and using trivial bound and Claim 25,
Σ of +15 Σ of +153+ Q.R.
which combined with the display above yields the form of the claimed bound.
To conclude the proof, we take union bound over 7 {O...., 1} and note that, by our assumption m and choice of a, x/2 < m/400.
H Proofs of Claims 11 and 24 to 26
Let RM = oF,; UA Uo(+++1), where we recall that A" = oAA, Uo(Er+1, Je+1, 1)) for each I N, that F. denotes the RV -ondiiiiooaal expectation, and that the purpose of conditioning on By will be to integrate out the random targets U.! U.. Um U141.
18

---

Proof of Claim 11. Fix u E _ and note that
R441 (u, (u,St + U1+1X1+41> (u, (1, + (U (2 X + 20/+1 (u, Sti(u, X441) | + X2+1)
1lul/.11
(14)
Observe that X2+1 and Sp = = + Esst U2X2 are F meaauuauabl and that U2 is independent of FY. The latter of these gives UXUU++1 1+1 = 0 and EE (U/+1)) = E. With that, we have that
(u, S/, + (m, X S2)
E
R²
(15)
||ull i {u, X
3 (u, X1+1)² |1ull8
2
(u, S1) ( X(t1)2
|/ (11u113
+ (u, X
(u, Xe+1)* 1)²
2
{u, S/
| V + (u, Xe+1)²
3
2 V/2
Q: 3
R
The statement follows by averaging over j E {l....,
Proof of Claim 24. Subtracting the first expression the right-hand side of equation (15) from equation (14) and averaging over j E {m....,m). we see that
W++1 = Ro+1 EE Re+1
Qc
(U (3
- (
m U 1=1
m
m
Note that Qt and He are F` measurable and that U. U441...., U are independent of Ry and one another, and that their absolute values are bounded by 1. Thus, examining the two terms in the sum we see that:
where H/ = (2,1 (u, //)/ll//l
Q: E ((U/41)² 3 is condiiiity Qr --ssubaaussian. vm
1 En
UZ Hi is
F. conditionaly
H. subgaussssin where /2m
1 m
1 m
(
Q m (u, S/)2
(H,)²
m Σ (
m Σ
= R..
||ullt
|ull
m
The result follows by recalling that the sum of an a-subgaussian random variable and a b-subgaussian random variable is /2(a² + buubauuuaassiann
The proof of the final two claims will require the following simple lemma. Lemma 27. Let by, by.... be a sequence of real numbers in [0, 1]. Then, for any X > 0 and n E N+,
n by
S log(1 + n/A) and Σ
b 1
n
1 X
$
Ein bi
A(A + n)
1=1
Proof. Let By = 0 and for j E [n] let B, = By-1 + bb. The function f(x) = A+z
1
is decreasing on
00). Hence, J f(z)dz 2 (B,). Summing these up,
[Ag(A> + =) = / ( f(z)dr= Σ
Bnn
- 1=1 B1-1
n
B,
1 f(x)dr N bb,((B)) Σ
n
bj
j=1 X
Σ b;
1=1
19

---

Evaluating the left-hand side and noting that B, S n holds because b; S gives the first result. For the second sum, we use similar argument with g(z) 1/(2 + x)
bj
by
bi
(A + B,}²
bj
(because 0 05 S 1)
(1 + B3}²
g(x)dz
(g is decreasing on [0, (0). B, S n)
n
A +
X(1 + n)
Proof of Claim 25. Noting that since ||u||2 = and 2 5, by Lemma 27,
T
(u, x
E
I log(1 + T/5) s T
A
+
Σj= (u, Xz)²
1=7
1=0
and
t
T-1
T-1
{u, x1+1) 12 2 (u, X2)
2
Σ
07
S 1
S1. S1
1=T
1=0
i=0
Using these, we have
Σ = Σ 0 + Σ
R2Q; 53+ Σ R2Q. 33Q
max Rg 75i5t
1=1
i=r
Proof of Claim 26. Since (a + 6)2 S 20² - 212 and by symmetry,
(u, (u, 2
R (u, S/ Ei= x2
S 2R + max (ib)²
+ Ei=1 (u, X2)² < 2Rg +2
\ + Ei= (U, Xe)²
bE(0,1] X it2
< 2R + 2i.
By definition, R² m E R$, and by assumption Rg < and i $ TT RS S 4+2i 2+2T.
And so,
3 T max R₁ 3 3 (2 + 27) - (3 23)
Sist
20

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
21

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
22

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nipp cc/pu Sww.oooddessssiiioooo
blic/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips.co.. wwtppplcccgggpciiicccceoooocccce http//uwde///eee CCodeSubmiieeeeeee htt.oi///uuddeesoeeeeubbbiiiiiii wwweeiissiiooooooo seionnolccy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
23

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : /nnuurirss...// cc cc/pppbccc//thhicchcieeeleeeeeee
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of the package should be provided. For popular datasets, paperswithcode com/ dataasess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
25

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "SOfbU326Zp", "reviewer": "Reviewer_Pgmx", "summary": "This paper studies the ensemble sampling in the stochastic linear bandit setting, and shows that the ensemble sampling can achieve $\\mathcal{O}( (d\\log T)^{5/2}  \\sqrt{T})$ regret with an ensemble size of order $\\mathcal{O}(d log T)$. The authors claim this is the first meaningful result of ensemble sampling as it does not require sub-linear ensemble size.", "questions": "The questions are raised in the weakness section. I am willing to re-evaluate the scores if these questions are properly answered.", "limitations": "This paper is pure theoretical and does not have any limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Though I have skimmed the proof of several lemmas, the analysis part seems to be rigorous and mathematically correct. The notations are clear defined before their references. \n2. The result which shows that ensemble learning is able to deal with linear bandit problem is quite interesting. This result would be applied in other similar settings.", "weaknesses": "1. It would be better to emphasis the differences between Algorithm 1 and LinUCB and explain how these differences work. The beta is quite similar. \n2. Though the authors refer the audience to the previous works for the motivation of studying ensemble sampling, it's still beneficial to include the related works on linear bandits and briefly discuss the specific advantages of using ensemble sampling.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nTo answer the reviewer’s two “weaknesses” points directly:\n1. 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).\n2. 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.\n \nWith 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sb6gS4uWbC", "reviewer": "Reviewer_P6Xa", "summary": "The authors study an upper confidence bound (UCB) type of ensemble sampling method specific to the stochastic linear bandits. Based on previous work, it improves the analysis by introducing Rademacher variables for symmetrising the ensemble. The authors are thus able to obtain $\\sqrt{T}$ dependency in the regret with an ensemble size scaling with $d$ (dimension) and $\\log T$ instead of $T$ (horizon).", "questions": "- I may have missed this - can the authors point out the significance of the regularization parameter λ? It seems from the theorems (2 and 5) λ only needs to be larger than 5 (i.e. an absolute constant)?", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "- Removing the linear dependency of $m$ (ensemble size) on $T$ (horizon) for this ensemble sampling method is significant.\n- The master theorem in Section 3 introduces intermediate filtrations $A'$ that may be of independent interest.", "weaknesses": "- The point of introducing the ensemble sampling in [Lu and Van Roy 2017] seems to be approximating Thompson sampling for complex models where computation is intractable. Meanwhile, the regret of linear bandits is known and achievable by LinUCB. Although the analysis improves for using smaller ensemble size in linear bandits, it deviates from the difficult setup and hence undermines the contribution of this paper.\n- The number and omnipresence of remarks in the main text obscures the core idea of this paper. For example, Remark 3 does not add much to its section (the upper bound) and is under-explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nWe 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).\n\nAs 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.\n\n_Osband, Ian, et al. \"Deep exploration via randomized value functions.\" Journal of Machine Learning Research 20.124 (2019): 1-62._", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Otw63ipRkM", "reviewer": "Reviewer_N2aY", "summary": "The paper presents a regret analysis of ensemble sampling within the stochastic linear bandit framework. It demonstrates that an ensemble size scaling logarithmically with time and linearly with the number of features suffices, marking a theoretical advancement. The paper shows that under standard assumptions for a \\(d\\)-dimensional stochastic linear bandit with an interaction horizon \\(T\\), the regret is of the order \\((d \\log T)^{5/2} \\sqrt{T}\\). Although the regret bound is not as tight as the existing bounds for the linear bandits, this is the first analysis of ensemble sampling in a structured setting that avoids the need for the ensemble size to scale linearly with \\(\\sqrt{T}\\), which previously compromised the purpose of ensemble sampling, while still achieving near-optimal order regret.", "questions": "- Regarding the comments in Remark 3, under unknown $T$, can't you derive some regret bound with the doubling epoch trick though? Or, do you argue that you cannot get any bound (sublinear in T) even with the doubling trick?", "limitations": "There is no separate \"Limitations\" section. But the authors discuss the weakness of the proposed method.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The paper makes a decent theoretical contribution by reducing the required scaling of ensemble size, which enhances the applicability and efficiency of ensemble sampling in linear bandit problems. By showing the better scaling of ensemble size, the paper provides a pathway for more efficient implementation of the ensemble sampling algorithms.\n- To my knowledge, this is the first correct frequentist regret analysis of linear ensemble sampling.", "weaknesses": "- One drawback is that, as the authors acknowledge, the regret bound of \\(O(d^{5/2} \\sqrt{T})\\) is relatively loose compared to existing linear bandit results. For example, TS-based algorithms like LinTS typically achieve \\(O(d^{3/2} \\sqrt{T})\\) regret, making the proposed bound clearly suboptimal.\n- The dependence on \\(m\\) in the regret bound indicates that as the ensemble size increases, the algorithm's regret performance worsens. This superlinear dependence, with regret being \\(O(m^{3/2})\\), raises concerns. Given this result, it is unclear why one would opt for this particular way (as proposed in the paper) of linear ensemble sampling.\n\n**Minor comment (but for clarity)**\n- I recommend that the authors explicitly write the linear \\(d\\)-dependence on the ensemble size \\(m\\) instead of shoving \\(d\\)-dependence into \\(N\\) in the theorem statement of Theorem 1 if possible, as I see that authors are transparent about $d \\log T$ dependence on $m$ in Remark 1.\n- I am not sure whether the expression \"**slightly** worse than that obtained for Thompson sampling\" (in Line 120) is adequate given that such a gap (extra $d$) can be seen as **significantly** by among many bandit researchers. I understand the authors' intention, but I suggest removing such an expression of \"slightly.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We must clarify two important misunderstandings:\n1. 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.\n2. 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.\n\nWe are happy to correct the two issues raised as “minor comments” in the way suggested by the reviewer.\n\nRegarding 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. \n\nRegarding 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. \n\nNote 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.\n\nIn 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.\n\n_Qin, Chao, et al. \"An analysis of ensemble sampling.\" Advances in Neural Information Processing Systems 35 (2022): 21602-21614._", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WuahWaK9xN", "reviewer": "Reviewer_YgVw", "summary": "This paper presents theoretical results for an exploration algorithm using ensemble sampling in the stochastic linear bandit setting. The proposed algorithm creates $2m = O(d \\log T)$ ensemble models, selects one model uniformly at random, and then chooses the greedy action based on the parameters of that model.\nThe proposed algorithm achieves a regret bound of $\\tilde{O}(d^{5/2} \\sqrt{T})$, and it does not depend on the size of the action set.", "questions": "1. When I first saw the ensemble sampling setting, it reminded me of the LSVI-PHE algorithm for linear MDPs with perturbed history exploration (Ishfaq et al., 2021). Ishfaq et al. (2021) address algorithms in the MDP setting, but with a horizon length of 1 ($H=1$), it can align with the linear bandit setting. Ishfaq et al. (2021) estimate perturbed parameters using Gaussian noise on observed rewards from previous episodes, repeating this process $M$ times. Actions are chosen based on the most optimistic of these estimated parameters. If we consider each perturbed estimator as an ensemble model, we have an ensemble size of $M$. However, the algorithm in Ishfaq et al. guarantees a high probability regret bound of $\\tilde{O}(d^{3/2} \\sqrt{T})$ (when $H=1$), with a theoretical sampling size of $M=O(d)$.\nThe only difference from the proposed ensemble sampling in this paper is that this paper selects the ensemble model to play uniformly at random. If the most optimistic model were chosen as in Ishfaq et al., could a better regret bound be guaranteed? Additionally, are there any other differences between the algorithm in Ishfaq et al. and the one proposed in this paper?\n\n* * *\nIshfaq, Haque, et al. \"Randomized exploration in reinforcement learning with general value function approximation.\" International Conference on Machine Learning. PMLR, 2021.", "limitations": "The authors have addressed the limitations in Section 4.\nThe content discussed in this paper appears to have little to no negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Unlike previous ensemble sampling algorithms (Lu & Van Roy, 2017; Qin et al., 2022), the proposed algorithm presents a frequentist regret analysis with a reasonable ensemble size. The authors also explain well the differences (e.g., symmetrization) compared to existing randomized algorithms like Thompson sampling and perturbed history exploration.\n- The master theorem (Theorem 1) for analyzing the regret bound of the randomized algorithm using the probability that the selected parameter by the algorithm is more optimistic than the true parameter is also intriguing. Proof seems correct, even though I didn’t check very carefully.", "weaknesses": "- As noted in Remark 4, although this paper provides a meaningful theoretical result for ensemble sampling, compared to randomized algorithms like Thompson sampling and perturbed history exploration, the proposed algorithm is neither computationally efficient nor statistically efficient. Ensemble sampling is generally effective in complex settings such as DeepRL. However, the regret bound presented in this paper does not seem sufficient to prove the validity of the ensemble algorithm even in the linear setting.\n- Thompson sampling algorithms generally have looser regret bounds than UCB algorithms but are known to perform better empirically. It would be beneficial if there were experimental results showing that ensemble sampling algorithms could empirically outperform existing randomized algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nWith 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.\n\nAs 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.\n\nRegarding 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.\n\nWe 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. \n\nWith 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.\n\n_Osband, Ian, et al. \"Deep exploration via bootstrapped DQN.\" Advances in neural information processing systems 29 (2016)._\n\n_Osband, Ian, John Aslanides, and Albin Cassirer. \"Randomized prior functions for deep reinforcement learning.\" Advances in Neural Information Processing Systems 31 (2018)._", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We respectfully disagree with the current assessment of our work and would like to encourage the reviewers to reconsider the following: We believe that the successful resolution of a long-standing open problem, one that has attracted multiple prior attempts, holds significant value within the NeurIPS community. Notably, two of these prior attempts were themselves published at NeurIPS (Lu & Van Roy 2017 and Qin et al. 2022). A well-written and sound paper addressing this open problem is a significant contribution. Novel proof ideas and techniques are of interest and contribute to the advancement of the field. It appears to us that none of the reviewers considered these aspects of our work; hence, again, we respectfully ask the reviewers to reconsider their assessment taking the above into account. We will also make an effort to revise the paper to make it (even) more clear that the above is what makes our paper interesting for the community, along with some other revisions (which we think are minor) to clarify a few things that seemed to be missed by the reviewers; in particular, the relation of ensemble sampling and Thompson sampling/perturbed history exploration, and the applicability of our results in the deep learning setting.

__Relation to TS/PHE__ There was a common misunderstanding amongst the reviewers as to the relation between ensemble sampling (ES), Thompson sampling (TS) and Perturbed History Exploration (PHE). In the linear setting, PHE and Thompson sampling are equivalent, and so we will make the comparison only between Ensemble sampling (ES) and PHE. In PHE, at every round, you take all past observations, add fresh noise to all of the data, then fit a model, and select a greedy action. That means that at every iteration, you have to fit a new model! If the models are neural networks, this is extremely expensive.

Could you, perhaps, instead of fitting a new, fresh model at every round, have an ensemble of $m$ models, and update these incrementally? That is, at each round, you do not add fresh noise to all previous observations, but only to the observation just received. This is ensemble sampling; in contrast to PHE, it does not require fitting a new model from scratch at every round; and it does not require storing past data—it is a completely online algorithm.

This leaves the question of whether ES works; whether we can get away with using incremental updates, and not train models from scratch. This is the question that we resolve with an affirmative answer: yes you can! The answer to this question was genuinely not known at all before our work. Our regret bound isn’t as good as if you had trained $m$ new models each iteration… maybe our bound is suboptimal, or maybe it's a real trade-off: we do not know; we discuss this in Remarks 2, 4 and 10. 

__Neural network function approximation__ The second concern of our reviewers was whether we had dodged the difficult “deep learning” setting by considering only the linear setting. We did not: the difficulty of proving a result for ensemble sampling comes from the incremental nature of the updates, and is tricky whenever there are any dependencies (correlations) between actions in the problem; the linear setting fully captures these difficulties. The core contribution of the paper is a completely novel proof addressing this difficulty. With a result on the regret proven for the linear setting, one can extend the result to deep learning using neural tangent kernel techniques—this is standard and requires no novel proof ideas or techniques; but at the same time rather tedious. Given the short page limit of NeurIPS papers, we decided not to include this in our manuscript. We believe that our contribution in the linear setting is valuable for its techniques and ideas, regardless of application to neural networks.

Furthermore, the difficulty is not in showing that an algorithm based on the linear bandit setting can have bounded regret when combined with neural network function approximation, but that it remains tractable in that setting. PHE and TS are not tractable in this setting. Ensemble sampling, on the other hand, is the method behind the BootstrapDQN and Ensemble+ algorithms of Osband et al. 2016 & Osband et al. 2018; as evidenced by the citation counts of these papers, these ensemble sampling algorithms are commonly used. 

We are thus proving results for methods actually used in practice, rather than the PHE/TS algorithms, which while simple to analyse (and often analysed and extended in the theory literature), are not really used in deep reinforcement learning. We believe that proving results for algorithms that practitioners actually use, rather than for simpler theoretical constructs, is of crucial importance to the community, and often overlooked in theory work.

__Moving forward__ When writing the paper, given that PHE, Thompson sampling and ensemble sampling are not our inventions and are thoroughly described and discussed in the literature, we assumed that it was not necessary to describe the above mentioned points and that it was sufficient to refer to the literature; and that we should use the scarce space for describing the novel parts of our work instead. As the camera ready allows for an extra page, we now think that the extra space should be used to include a discussion of the relationship of these methods, making the motivation to analyse ensemble sampling as we do it, clear, regardless of the familiarity of the readers with the literature. 

We must again emphasise that our paper solves a long-standing open problem, which attracted two failed attempts, both published at NeurIPS. We think that a well-written, sound paper that successfully solves this open problem is surely a strong contribution publishable at NeurIPS.

With the above in mind, we must ask that all reviewers reconsider their scoring of our paper.

Meta-review: This paper provides the first frequentist regret analysis of ensemble sampling for linear contextual bandits. The authors present a $(d\log T)^{5/2}\sqrt{T}$ regret upper bound and only require an ensemble size of $d\log T$. Though the regret result is not optimal in linear bandits (and is larger than that of Thompson Sampling, PHE, and other randomized algorithms by a factor of $d$), ensemble sampling has been extensively adopted in the deep RL community. This work provides a valuable starting point for theoretically understanding ensemble sampling, which warrants its acceptance.

During the rebuttal and discussions, some reviewers raised questions regarding the motivation behind ensemble sampling, its theoretical analysis in the linear setting, and its comparison/discussion with other randomized exploration strategies. I hope the authors will address these comments and include the promised discussion in the camera-ready version.
Decision: Accept (poster)