Ensemble sampling for linear bandits: small ensembles suffice

Authors: david  janz
alexander e litvak
csaba  szepesvári
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 18:11:11

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. Ours is also the first result that allows infinite action sets.

Main paper: 
 introduction: 
 Ensemble sampling (Lu and Van Roy, 2017 ) is a family of randomised algorithms for balancing exploration and exploitation within sequential decision-making tasks. These algorithms 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 a model chosen uniformly at random from the ensemble. The ensemble is 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 in an incremental fashion. Therein, ensemble sampling features directly in algorithms such as bootstrapped DQN and ensemble+ (Osband et al., 2016 (Osband et al., , 2018)) , as 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 et 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 a bound of orderT on its Bayesian regret under the impractical condition that the size of the ensemble scales at least linearly with the horizon T , summarise the state-of-the-art in this regard as 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, or perturbed history exploration (Kveton et al., 2020; Janz et al., 2024) , relies on showing that at each step there is a constant probability of choosing a model that overestimates the true value (Agrawal and Goyal, 2013; Abeille and Lazaric, 2017) . For these methods, the analysis 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 to 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 a 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/2 √ T . This is the first successful analysis of ensemble sampling in the stochastic linear bandit setting, or indeed, any structured setting (see Remarks 5 and 6 for a 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 it ought to be possible to extend it to the usual settings: generalised linear bandits (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) . 
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 Osband et al. (2019) ; our focus will be on analysis. We will use the following notation:Sets and real numbers We write N + = {1, 2, . . . }, N = N + ∪ {0} and [n] = {1, 2, . . . , n}. We use the shorthand (a t ) t for a sequence indexed by t in N or N + when this index set can be deduced from the context. For a, b ∈ R, that is, for real numbers a and b, a ∧ b denotes their minimum and a ∨ b their maximum. Vectors and matrices We identify vectors and linear operators with matrices. We write ∥ • ∥ 2 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 s 1 (•); we write s 2 (•), s 3 (•), . . . for the remaining singular values, ordered descendingly. For vectors u, v of matching dimension, ⟨u, v⟩ = u T v denotes their usual inner product. We write B d 2 for the 2-ball in R d , S d-1 2 = ∂B d 2 for its surface, the (d -1)-sphere, and H u for the closed half-space {v ∈ R d : ⟨u, v⟩ ≥ 1}. Probability We work on a probability space with probability measure P, and denote the corresponding expectation operator by E. We write σ(•) for the σ-algebra generated by the argument. For an event A, we write 1[A] for the indicator function of A. Uniform distribution We write U(B) for the uniform distribution over a set B (when well-defined), and U(B) ⊗m for its m-fold outer product; that is, (U 1 , . . . , U m ) ∼ U(B) ⊗m are m i.i.d. random variables with common law U(B).We consider the standard stochastic linear bandit setting. At each step t ∈ N + , a learner selects an action X t from an action set X , a compact subset of B d 2 , and receives a random reward Y t ∈ R that obeys the following assumption: Assumption 1. At each time step t ∈ N + , the agent receives a reward of the formY t = ⟨X t , θ ⋆ ⟩ + Z t with θ ⋆ ∈ B d 2 a fixed instance parameter and Z t a random variable satisfying E[exp{sZ t } | σ(F t-1 ∪ A t ∪ σ(X t ))] ≤ exp{s 2 /2}, ∀s ∈ R, almost surely, where F t-1 = σ(X 1 , Y 1 , . . . , X t-1 , Y t-1) and A t is the σ-algebra generated by the random variables used by the learner to select its actions up to and including time t.The learner is given a horizon T ∈ N + and its performance is evaluated by the (pseudo-)regret, R(T ), incurred for the first T steps, defined asR(T ) = max x∈X T t=1 ⟨x -X t , θ ⋆ ⟩ ,The smaller the regret, the better the learner. Under our assumptions, up to logarithmic factors, the regret of the best learners is of order dT (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 X 1 , . . . , X T , the regret it incurs will satisfy a similar high probability bound, with a slightly worse dependence on the dimension d.Linear ensemble sampling, listed as Algorithm 1, proceeds as follows. At the outset, we fix an ensemble size m ∈ N + , a regularisation parameter λ > 0 and a sequence of perturbation scale parameters r 0 , r 1 , r 2 , . . . > 0. Then, before the start of each round t ∈ N + , linear ensemble sampling computes m + 1 d-dimensional vectors. The first of these is the usual ridge regression estimate of θ ⋆ ,EQUATIONThe remaining m parameter vectors, which shall serve as perturbations, are of the formθj t-1 = V -1 t-1 S j 0 + t-1 i=1 X i U j i for each j ∈ [m] ,where S j 0 ∈ R d is a random initialisation, and is taken to be uniform on λ√ dS d-1, and U j 1 , U j 2 , . . . are random targets, uniform on the interval [-1, 1]. All of these random variables are independent of the past at the time they are sampled and across the m-many replications. The algorithm then selects a random index J t ∈ [m] and sign ξ t ∈ {±1}, both uniformly distributed over their respective ranges, computes the perturbed parameterθ t = θt-1 + r t-1 ξ t θJt t-1and selects an actionX t ∈ arg max x∈X ⟨x, θ t ⟩ ,with ties dealt with in a measurable way. All in all, the vectorsθt-1 ± r t-1 θ1 t-1 , . . . , θt-1 ± r t-1 θm t-1serve as an ensemble of 2m-many perturbed estimates of θ ⋆ , 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 Gaussians, as used in previous literature. This choice simplifies the proofs, but our results hold (up to constant factors) for any suitable subgaussian targets, including Gaussian. We return to this in Remark 12.2. We symmetrise our perturbations using Rademacher random variables, which does not feature in previous formulations of the ensemble sampling algorithm. This helps to create a more uniform distribution of the perturbations ( θj t ) t 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 is more in line with the style of presentation of the algorithm given by Lu and Van Roy (2017) .Our advertised result is captured in the following theorem. To state the theorem we need the sequenceβ δ t = √ λ + 2 log(1/δ) + log(det(V t )/λ d ) , t ∈ N .Here and in related quantities, the superscripted δ expresses the dependence on a δ ∈ (0, 1].Algorithm 1 Linear ensemble sampling Input regularisation parameter λ > 0, ensemble size m ∈ N + , perturbation scales r 0 , r 1 , . .. > 0 Sample (S j 0 ) j∈[m] ∼ U(λ √ dS d-1 2 ) ⊗m Let V 0 = λI, θ0 = 0, and let θj 0 = V -1 0 S j 0 for each j ∈ [m] for t ∈ N + do Sample (ξ t , J t ) ∼ U({±1} × [m]) and let θ t = θt-1 + r t-1 ξ t θJt t-1Compute an X t ∈ arg max x∈X ⟨x, θ t ⟩, play action X t and receive rewardY t Sample (U j t ) j∈[m] ∼ U([-1, 1]) ⊗m and let S j t = S j t-1 + U j t X t for each j ∈ [m] Let V t = V t-1 + X t X T t , θt = V -1 t t i=1 Y i X i , and let θj t = V -1 t S j t for each j ∈ [m]Theorem 1. Fix δ ∈ (0, 1] and take r t = 7β δ t for all t ∈ N, λ ≥ 5 and m ≥ 400 log(N T /δ) for N = (134 1 + T /λ) d . Then there exist a universal constant C > 0 such that, with probability at least 1 -δ, the regret incurred by a learner following linear ensemble sampling with these parameters in our stochastic linear bandit setting (formalised in Assumption 1) is bounded asR(τ ) ≤ Cm 3/2 β δ τ -1 dτ log(1 + τ /(λd)) + (τ /λ) log(τ /(λδ)) for all τ ∈ [T ] .Remark 1. If δ ≥ 1/T α for some α > 0 and we take λ = 5 and m to be as small as possible given the constraint of Theorem 1, thenm ≤ C α d log T and R(T ) ≤ C ′ α (d log T ) 5/2 √ Tfor some constants C α , C ′ α > 0 that depend on α only and where the bound on the regret holds with probability 1 -δ. That is, for polynomially sized confidence parameters, the ensemble size scales linearly with d log(T ), while the regret scales with d 5/2 √ T up to 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 3/2 √ T , again, up to logarithmic-in-T factors. Remark 2. Theorem 1 does not recover the expected behaviour for large ensemble sizes; that is, as m → ∞. On one hand, this is not an issue: we are interested in the practical regime where the ensemble size is small. On the other, it suggests that better analysis might be possible. In Remark 10, 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 √ m dependence to an order d log T /δ dependence, thus recovering a bound with the right dependence on m. However, as discussed in Remark 10, 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, a 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 to the idea of a fast incremental method. Remark 4. In light of Theorem 1, linear ensemble sampling might be seen as a 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 Osband et al., , 2018)) , and the linear setting provides an important testing ground for the soundness of these algorithms.We now relate our result to those of Lu and Van Roy (2017) and Qin et al. (2022) : Remark 5. 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 6. The only correct result on the regret of linear ensemble sampling is by Qin et al. (2022) , which gives that for a d-dimensional linear bandit with an action set X of cardinality K, the Bayesian regret incurred-that is, average regret for θ ⋆ ∼ N (0, I d )-is bounded asBR(T ) ≤ C dT log K + CT K log(mT ) m (d ∧ log K)for some universal constant C > 0. Observe that this bound needs an ensemble size linear in T for Bayesian regret that scales as √ T (up to constant and polylogarithmic factors), which largely defeats the purpose of ensemble sampling. Furthermore, the ensemble size m needs to scale linearly with K to get a log K overall dependence on K. Therefore, to tackle a bandit with X = B d 2 using the bound of Qin et al. (2022) and discretisation, since order 2 d-1 -many actions would be needed to guarantee a small discretisation error, the ensemble size m would need to scale exponentially in d.The results of Lu and Van Roy (2017) and Qin et al. (2022) form the entirety of the previous analysis of ensemble sampling in any structured setting. In light of that, we believe that our result is the first to begin justifying the practical effectiveness of ensemble sampling. 
analysis of linear ensemble sampling: 
 Our analysis of ensemble sampling will be based on a master theorem, presented in Section 3.1 and proven in Appendix B. The master theorem provides a method for obtaining regret bound for Thompson-sampling-like 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 it recovers a previous result for a more classical Thompson-sampling-type algorithm.Our analysis of ensemble sampling will rely on the revered principle of optimism. To make this precise, consider a fixed instance parameter θ ⋆ ∈ R d . Writing J(θ) = max x∈X ⟨x, θ⟩, we callΘ OPT = {θ ∈ R d : J(θ) ≥ J(θ ⋆ )}the set of parameters optimistic for θ ⋆ . We now present a 'master theorem' that bounds the regret of any algorithm that chooses actions based on a randomly chosen parameter in terms of the probabilities that, given the past, the algorithm samples a parameter that falls in the intersection of ellipsoidal confidence sets and the optimistic region Θ OPT . This result generalises a 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 a finer control over the way dependencies between time-steps are handled.Theorem 2 (Master regret bound). Fix T ∈ N + ∪ {+∞}, δ ∈ (0, 1], λ ≥ 1, and let (V t , θt ) t be defined per equation (1). Let Assumption 1 hold, recalling the filtrations (F t ) t and (A t ) t defined therein, and let (A ′ t ) t be any filtration satisfyingA t-1 ⊂ A ′ t-1 ⊂ A t , ∀t ∈ N + . Let (b t ) t∈N be a sequence of σ(F t ∪ A ′ t )t -adapted nonnegative random variables, and define the ellipsoidsΘ t = θt + b t V -1/2 t B d 2 , t ∈ N . Let (θ t ) t be a (σ(F t ∪ A t )) t -adapted R d -valued sequence and suppose that X t ∈ arg max x∈X ⟨x, θ t ⟩ , ∀t ∈ [T ] .Suppose further that there exist events E T and E ⋆T satisfyingE T ⊂ ∩ T t=1 {θ t ∈ Θ t-1 } , E ⋆ T ⊂ ∩ T t=1 {θ ⋆ ∈ Θ t-1 } and P(E T ) ∧ P(E ⋆ T ) ≥ 1 -δ .(2) Then, writingp t-1 = P(θ t ∈ Θ OPT ∩ Θ t-1 | σ(F t-1 ∪ A ′ t-1 )) , t ∈ N + ,we have that on a subset ofE T ∩ E ⋆ T of probability at least 1 -3δ, for all τ ∈ [T ], R(τ ) ≤ 2 max i∈[τ ] b i-1 p i-1   2 2dτ log 1 + τ dλ + 2(4τ /λ + 1) log 4τ /λ + 1 δ   .We defer the proof of Theorem 2 to Appendix B. Remark 7. To apply the theorem, we need to show that our algorithm generates (θ t ) t such that the probability of each θ t landing inΘ OPT ∩ Θ t-1 , conditional on σ(F t-1 ∪ A ′ t-1), is bounded away from zero for all t ∈ [T ]. We have two degrees of freedom in our analysis:1. We can choose (b t ) t , the widths of the ellipsoids (Θ t ) t . Larger widths may make it easier to bound (p t ) t away from zero, but at a linear cost in the regret bound.2. We can choose A ′ t-1 , the 'point' between observing Y t-1 and selecting θ t with respect to which we consider the aforementioned conditional probabilities defined. Remark 8. The introduction of A ′ t-1 serves to model the case where θ t is sampled from a distributionP t that itself depends on X 1 , Y 1 , . . . , X t-1 , Y t-1 in a random manner. The σ-algebra A ′ t-1 is then such that P t is σ(F t-1 ∪ A ′ t-1 )-measurable.The upcoming two lemmas will be helpful our applications of the Master Theorem; both are stated in terms of the random functions ψ t : R d → R d given byψ δ t (u) = θt + β δ t V -1/2 t u, t ∈ N .The first is the classic concentration result of Abbasi-Yadkori et al. ( 2011), and the second, Proposition 5 of Abeille and Lazaric (2017) .Lemma 3. Under Assumption 1, for any δ ∈ (0, 1], P(∀t ∈ N, θ ⋆ ∈ ψ δ t (B d 2 )) ≥ 1 -δ. Lemma 4. If Assumption 1 holds and θ ⋆ ∈ ψ δ t (B d 2 ), then for any measure Q over R d and a > 0, Q(Θ OPT ∩ ψ δ t (aB d 2 )) ≥ inf u∈S d-1 2 Q(ψ δ t (H u ∩ aB d 2 )) ,where we recall that H u denotes the closed halfspace {v ∈ R d : ⟨v, u⟩ ≥ 1}.We provide a short, clean proof of Lemma 4 in Appendix C.Let Γ 0 , Γ 1 , . . . be the sequence of random matrices in R d×m with the jth column given byΓ j t = V -1/2 t S j t , such that θj t-1 = V -1/2 t-1 Γ j t-1 .Recall that S j t = S j 0 + t i=1 U j i X i and observe that each (S j ) t is a vector-valued random walk with increments given by (U t X t ) t , where (X t ) t is a serially correlated vector-valued sequence and(U j t ) t is a sequence of independent U([-1, 1]) variables, and (Γ j t ) t is a normalised version of (S j t ) t . Consider the extremal singular values of Γ t , s d (Γ t ) = min u∈S d-1 2 ∥Γ T t u∥ 2 = min u∈S d-1 2 m j=1 ⟨Γ j t , u⟩ 2 1 2 and s 1 (Γ t ) = ∥Γ T t ∥ = max u∈S d-1 2 ∥Γ T t u∥ 2 .The lower of these may be interpreted as capturing how well the columns Γ 1 t , . . . Γ m t cover all directions u ∈ S d-1 2 , and the upper, their maximal deviations from zero. The following theorem, proven in Section 3.3, shows that, for a sufficiently large m, with high probability, for all t ∈ [T ], the singular values of Γ t-1 are on the order of √ m. Theorem 5. For λ ≥ 5 and m ≥ 400 log(3 + T ) ∨ 10d, the eventE T = {∀t ∈ [T ], √ m/7 ≤ s d (Γ t-1 ) ≤ s 1 (Γ t-1 ) ≤ 10 √ m/7} satisfies P(E T ) ≥ 1 -N T e -m 400 , where N = (134 1 + T /λ) d .Proof of Theorem 1. We will use the master theorem, Theorem 2. We let the filtrations (A t ) t and (A ′ t ) t needed in this theorem be defined recursively viaA ′ 0 = σ(S 1 0 , . . . , S m 0 ), A t = σ(A ′ t-1 ∪ σ(J t , ξ t )) and A ′ t = σ(A t ∪ σ(U 1 t , . . . , U m t )) , t ∈ N + .With this, the conditions concerning these filtrations hold.We let b t = aβ δ t for a = 10 √ m, for each t ∈ N, which is σ(F t ∪ A ′ t ) t -adapted, as required. For the two required events, we take the event E T from Theorem 5 and the eventE ⋆ T = ∩ t∈N {θ ⋆ ∈ ψ t (B d 2 )}.To see that these satisfy the requirements given in equation ( 2), observe the following:Conditions on E T By our assumptions on m and λ, the conditions for Theorem 5 are satisfied.Hence, P(E T ) ≥ 1 -δ. We now show that on E T , for all t∈ [T ], θ t ∈ Θ t-1 . Note this is equivalent to the statement that on E T , for all t ∈ [T ], ∥ξ t Γ Jt t-1 ∥ 2 ≤ b t-1 /r t-1 = 10 √ m/7. And indeed, on E T , ∥ξ t Γ Jt t-1 ∥ 2 ≤ max j ∥Γ j t-1 ∥ 2 = s 1 (Γ t-1 ) ≤ 10 √ m/7 , ∀t ∈ [T ] .(3)Conditions on E ⋆ T Since a ≥ 1, ψ t (B d 2 ) ⊂ ψ t (aB d 2 ) = Θ t ,and thus, by Lemma 3, θ ⋆ ∈ Θ t for all t ∈ N jointly with probability at least 1 -δ.It remains to lower-bound the sequence (p t ) t . For this, defineP ′ t-1 (•) = P(• | σ(F t-1 ∪ A ′ t-1 )). Fixing t ∈ N + , writing Q(A) = P ′ t-1 (θ t ∈ A), we have that on E ⋆ T , p t-1 = Q(Θ OPT ∩ Θ t-1 ) ≥ inf u∈S d-1 2 Q(ψ δ t-1 (H u ∩ aB d 2 )) (Lemma 4) = inf u∈S d-1 2 P ′ t-1 (ψ δ t-1 (7ξ t Γ Jt t-1 ) ∈ ψ δ t-1 (H u ∩ aB d 2 )) (definition of θ t , Q) = inf u∈S d-1 2 P ′ t-1 (7ξ t Γ Jt t-1 ∈ H u ∩ aB d 2 ) (ψ δ t-1 is a bijection) = inf u∈S d-1 2 1 2m (s,j)∈{±1}×[m] 1[7sΓ j t-1 ∈ H u ∩ aB d 2 ] ,where the last equality used the definitions of P ′ t-1 , F t-1 and A ′ t-1 . We now show that on E T , regardless of the choice of u, for at least one (s, j)∈ {±1} × [m], 7sΓ j t-1 ∈ H u ∩ aB d 2 .Assume thus that E T holds. First observe that for any (s, j), by equation ( 3),7sΓ j t-1 ∈ aB d 2 .Hence, it remains to show that for any u, for some (s, j), 7sΓ j t-1 ∈ H u ; this holds because for any u,1 ≤ s 2 d (7Γ t-1 ) m ≤ 1 m m j=1 ⟨7Γ j t-1 , u⟩ 2 ≤ max j ⟨7Γ j t-1 , u⟩ 2 . (4) Hence, on E T ∩ E ⋆ T , p t-1 ≥ 1/(2m) and thus b t-1 /p t-1 ≤ 20m 3/2 β δ t-1 .Inserting this bound into the regret bound of Theorem 2 establishes the result.Remark 9 (On symmetrisation). If the algorithm were run without symmetrisation, following the steps of the proof we see that we need to show that on E T , regardless the choice of u, for at least one of j ∈ [m], 7Γ j t-1 ∈ H u . In the presence of symmetrisation, the equivalent statement is that regardless of the choice of u, for at least one 'particle' j, we have either 7Γ j t-1 ∈ H u or 7Γ j t-1 ∈ H -u . Through equation (4), the latter reduces to studying quadratic forms, which lead to convenient algebra.Remark 10 (Can we improve our bound?). For any u ∈ S d-1 2 , we lower bound the maximum max j ⟨7Γ j t-1 , u⟩ 2 by the average 1 m m j=1 ⟨7Γ j t-1 , u⟩ 2 , which we show exceeds 1, thus establishing the existence of at least one element ±7Γ j t-1 in H u (out of 2m). This gives a 1/(2m) lower bound for p t-1 . However, lower bounding a maximum by an average might be wasteful. If, instead, we managed to lower bound the median (or any other fixed-proportion order statistic) of ⟨7Γ 1 t-1 , u⟩ 2 , . . . , ⟨7Γ m t-1 , u⟩ 2 , we would be able to conclude that p t is lower bounded by a constant (since a constant proportion of 'particles' are then contained in H ±u ), 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, and we do not currently know if such a result is attainable.Theorem 5 for t = 0 follows by standard methods (see Appendix E for proof): Lemma 6. Whenever m ≥ 10d,P m/2 ≤ s d (Γ 0 ) ≤ s 1 (Γ 0 ) ≤ 3m/2 ≥ 1 -e -m/24 .To extend the result to t > 0, we will consider the processes (R j t (u)) t and (R t (u)) t defined foru ∈ R d , u ̸ = 0 by R j t (u) = ⟨u, S j t ⟩ 2 ∥u∥ 2 Vt and R t (u) = 1 m j R j t (u). Note that for v = V 1/2 t u ̸ = 0 one has R j t (u) = ⟨v, Γ j t ⟩ 2 /∥v∥ 2. Since V t is positive-definite (and hence a bijection when viewed as a linear map) we observe the following relations:Claim 7. For all t ≥ 0, j ∈ [m], sup u̸ =0 R j t (u) = sup v̸ =0 ⟨v, Γ j t ⟩ 2 ∥v∥ 2 2 = ∥Γ j t ∥ 2 2 and sup u̸ =0 R t (u) = sup v̸ =0 ∥Γ T t v∥ 2 2 m∥v∥ 2 2 = s 2 1 (Γ t ) m ,and likewiseinf u̸ =0 R t (u) = s 2 d (Γ t )/m.In the upcoming section (Section 3.4) we establish the following bound on R t (u) for a fixed u ∈ S d-1 2 .Lemma 8. Fix u ∈ S d-1 2 and λ ≥ 5. Suppose that m ≥ 400 log(3 + 2T ). Then, there exists an eventE ′ T with P(E ′ T ) ≥ 1 -T e -m 400 such that on E ′ T ∩ { 1 2 ≤ R 0 (u) ≤ 3 2 }, 9 100 ≤ R t (u) ≤ 5 3 , ∀t ∈ [T ] .Our proof of Theorem 5 employs the above pointwise bound together with a covering argument over S d-1. For that, we need the following Lipschitzness result, proven in Appendix F (by simple algebra), and a standard bound on the size of ϵ-nets of S d-1 2 (Lemma 4.10 in Pisier, 1999) .Lemma 9. On S d-1 2 , R t is L-Lipschitz with L ≤ 4∥Γ t ∥ 2 ∥V 1/2 t ∥/(m √ λ).Lemma 10. For all ϵ in (0, 1], there exists an ϵ-netN of S d-1 2 with |N | ≤ 1 + 2 ϵ d .Proof of Theorem 5. Let N ϵ be a minimal ϵ-net of S d-1 2 and define the eventE ϵ = ∀v ∈ N ϵ , ∀t ∈ [T ], 9 100 ≤ R t (v) ≤ 5 3 .We will now confirm that, for a suitable choice of ϵ, E ϵ is a subset of the event in Theorem 5, and that P(E ϵ ) ≥ 1 -N T e -m 400 , which establishes the theorem.Let u ∈ S d-1 2 and v ∈ N ϵ be such that ∥u -v∥ 2 ≤ ϵ. From Lemma 9, and choosing ϵ = √ λ/(132 √ T + λ), and noting that ∥V1/2 t ∥ ≤ √ T + λ, we get |R t (u) -R t (v)| ≤ 4∥Γ t ∥ 2 ∥V 1/2 t ∥ m √ λ ϵ ≤ ∥Γ t ∥ 2 33m .Then on E ϵ , for our choice of ϵ,∥Γ t ∥ 2 = m sup u̸ =0 R t (u) ≤ m sup v∈Nϵ R t (v) + ∥Γ t ∥ 2 33 ≤ 5 3 m + ∥Γ t ∥ 2 33 , Solving for ∥Γ t ∥ 2 , we have that ∥Γ t ∥ 2 = s 2 1 (Γ t ) ≤ 165 96 m.The same argument also gives that, on E ϵ ,s 2 d (Γ t ) ≥ m inf v∈Nϵ R t (v) - ∥Γ t ∥ 2 33 ≥ 9 100 m - ∥Γ t ∥ 2 33 ≥ 3 100 m.Loosening these bounds slightly, we have that onE ϵ , √ m/7 ≤ s d (Γ t ) ≤ s 1 (Γ t ) ≤ 10 √ m/7.The probability that E ϵ occurs is at least the probability that the event of Lemma 6 occurs and that the event of Lemma 8 occurs for each u ∈ N ϵ , noting that the former ensures 1 2 ≤ R 0 (u) ≤ 3 2 for all u ∈ N ϵ . Taking a union bound over these events, we have thatP(E ϵ ) ≥ 1 -e -m 24 -T |N ϵ |e -m 400 ≥ 1 -T (|N ϵ | + 1)e -m 400 .We conclude by noting that, by Lemma 10, for our choice of ϵ, N ≥ |N ϵ | + 1.Since we now consider a fixed u ∈ S d-1 2 , we will write R j t := R j t (u) and R t := R t (u). Let (A ′′ t ) t be the filtration given by A ′′ t = σ(A t ∪ σ(ξ t+1 , J t+1 )) for each t ∈ N, and letE ′′ t denote the σ(F t ∪ A ′′ t ∪ σ(X t+1))-conditional expectation, which will be used to integrate out the random targets U 1 t+1 , . . . , U m t+1 . With that, we defineD t = E ′′ t R t+1 -R t and W t+1 = R t+1 -E ′′ t R t+1to be the drift and the noise of the process (R t ) t∈N , respectively. Also letQ t = ⟨u, X t+1 ⟩ 2 /∥u∥ 2be the strength of the drift. These are related by the following two results:Claim 11. D t = ( 2 3 -R t )Q t for all t ∈ N. Lemma 12. For any T ∈ N + and m ≥ 400 log(3 + T ), there exists an event E with P(E) ≥ 1 -T e -m 400 , such that on E ∩ {R 0 ≤ 2}, for all 0 ≤ τ ≤ t < T ,t i=τ W i+1 ≤ 1 10 3 + t i=τ Q i R i .The lemma is proven in Appendix G, and the claim in Appendix H. The constant 2 3 above is just the almost sure value of E ′′ t [(U j t+1 ) 2 ]; see also Remark 12 for a discussion of the significance of the (U j t+1 ) 2 terms and how we bound these in the proof of said lemma.Proof of Lemma 8. Fix 0 ≤ τ ≤ t < T . We can decompose R t+1 asR t+1 = R t+1 -E ′′ t R t+1 + E ′′ t R t+1 -R t + R t = W t+1 + D t + R t ,which unrolled back to τ and combined with Claim 11 gives us thatEQUATIONObserve from the above that the process R 0 , R 1 , . . . drifts towards 2 3 , with strength proportional the level of deviation, scaled by Q i . We will now show that on the event of Lemma 12, whenever R t moves sufficiently far away from 2 3 , the drift will overwhelm the effect of the noises (W t ) t . Assume henceforth that the aforementioned event holds.Lower bound. We consider the excursions of (R t ) t where it goes and stays below 1/2. Let 0 ≤ τ < s ≤ T be endpoints of such a maximal excursion, in the sense that R τ ≥ 1/2, R τ +1 , . . . , R s < 1/2 and if s + 1 ≤ T then R s+1 ≥ 1/2. Our goal is to show that for any τ ≤ t < s, R t+1 ≥ 9/100, which suffices to prove the lower bound. Fix t ∈ [τ, s). From equation ( 5) and since the event from Lemma 12 holds,EQUATION(Q i ≤ 1/λ ≤ 1/5, R τ ≥ 1/2, def. of α) = 9 100 .Upper bound. The upper bound follows near-verbatim, taking τ with R τ ≤ 3 2 < R τ +1 . Remark 11. The lower bound of Lemma 8 was the difficult direction; the upper bound follows straightforwardly from standard de la Peña-type bounds. See, for example, Theorem 20.4 of Lattimore and Szepesvári (2020) .Remark 12. The proof of Lemma 8 was where we use that the targets (U j t ) are uniform-or, in particular, that they are bounded random variables-for each W t+1 features (U j t ) 2 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 ′ t+1 = W t+1 ∧ a for each t ∈ N + and work with the process given by the recursionR ′ t+1 = W ′ t+1 + D t + R ′ t . Then, R t ≥ R ′t for all t ∈ N, and the truncated noises (W ′ t+1 ) are once again subgaussian, so our approach to lower bounding R t would also work for R ′ t . We would establish the upper bound as in Remark 11, observing that the result cited therein does not require bounded targets. 
discussion: 
 We showed that linear ensemble sampling works with small ensembles. Per Remark 6 and Remark 5, ours is the first useful theoretical result for linear ensemble sampling. However, our bound might be loose: we discuss this in Remark 2 and point out a potential source of looseness in Remark 10. Addressing this would make for an interesting direction for future work. As discussed in Section 2.2 and Remark 9, our algorithm uses a certain symmetrisation not used within the work of Lu and Van Roy (2017) . 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 A reformulation of Algorithm 1 in the style of Lu and Van Roy (2017) Below in Algorithm 2, we list a reformulation of Algorithm 1 written using updates in the style of Lu and Van Roy (2017) , with one difference: the algorithm here accepts only a single time-stationary perturbation scale r > 0 (this is unavoidable with the Lu and Van Roy (2017) style of updates). Taking r = 7 βδ T , where β δ T is the deterministic upper bound on β δ 0 , . . . , β δ T given by βδT = √ λ + 2 log(1/δ) + d log((d + T /λ)/d) ,allows for the same guarantee as given in Theorem 1, but with βδ T in place of β δ τ -1 .Algorithm 2 Equivalent form of Algorithm 1 assuming time-stationary perturbation scale r Input regularisation parameter λ > 0, half-ensemble size m ∈ N + , perturbation scale r > 0Let V 0 = λI, sample (w j 0 ) ∼ U( √ dS d-1 2 ) ⊗m and let w m+j 0 = -w j 0 for each j ∈ [m] for t ∈ N + do Sample J t ∼ U({1, . . . , 2m}) Compute an X t ∈ arg max x∈X ⟨x, w Jt t-1 ⟩, play action X t and receive reward Y t Sample (U j t ) j∈[m] ∼ U([-1, 1]) ⊗m and let U m+j t = -U j t for each j ∈ [m] Let V t = V t-1 + X t X Tt , and letw j t = V -1 t (V t-1 w j t-1 + X t (Y t + rU j t )) for each j ∈ [2m]To confirm that Algorithm 2 is equivalent to Algorithm 1 if the sequence r 0 , r 1 , . . . is set to the common value r, it suffices to compare the list of parameters w 1 t-1 , . . . , w 2m t-1 used here with the list θt-1 ± r θ1 t-1 , . . . , θt-1 ± r θ1 t-1 , at each step of the algorithm. We leave this as a simple algebraic exercise for the reader.We need the following concentration inequality, a simple consequence of Exercise 20.8 in Lattimore and Szepesvári (2020)2 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 < δ ≤ 1. Let (ξ t ) t∈N + be a real-valued martingale difference sequence satisfying |ξ t | ≤ c almost surely for each t ∈ N + and some c > 0. Then,P   ∃τ : τ t=1 ξ t 2 ≥ 2(c 2 τ + 1) log √ c 2 τ + 1 δ   ≤ δ.Lemma 14 (Elliptical potential lemma). Let (x t ) t∈N + be a sequence of vectors in B d 2 , let V 0 = λI for some λ ≥ 1 andV t = V 0 + t i=1 x i x T i for each t ∈ N + . Then, for all τ ∈ N + , τ t=1 ∥x t ∥ 2 V -1 t-1 ≤ 2d log 1 + τ λd .Recall that J(θ) = max x∈X ⟨x, θ⟩ is the support function of X , and observe the following: Claim 15. For any t ∈ N + , X t is a subgradient of J at θ t .Proof. Fix t ∈ N + . For any θ ∈ R d ,EQUATIONwhich is the inequality that defines a subgradient.Proof of Theorem 2. Throughout this proof, we work on the intersection E T ∩ E ⋆ T , and therefore in particular use that for any t ∈ [T ], θ t , θ ⋆ ∈ Θ t . We let γ t = 2b t , and observe that this is the V t -weighted Euclidean norm width of Θ t , in the sense thatEQUATIONWe will also use the shorthandsF ′ t = σ(F t ∪ A ′ t ), P ′ t = P(• | F ′ t ) and E ′ t = E[• | F ′ t ].The proof is based on decomposing the regret into two parts, which we then control separately:EQUATION)Fix t ∈ [τ ] and consider the second term, J(θ t ) -⟨X t , θ ⋆ ⟩. We have thatEQUATIONwhere the first inequality is by Cauchy-Schwartz, the second uses that θ t , θ ⋆ ∈ Θ t-1 and then equation ( 7).Now consider the first term, J(θ ⋆ ) -J(θ t ). Let θ -be a minimiser J over Θ t-1 (which is welldefined, since J is continuous and Θ t-1 closed) and let θ + be an element of Θ OPT ∩ Θ t-1 (which is non-empty, since it contains at least θ ⋆ ). Then, since θ ⋆ , θ t ∈ Θ t-1 , we have the boundJ(θ ⋆ ) -J(θ t ) ≤ J(θ ⋆ ) -J(θ -) ≤ J(θ + ) -J(θ -) .It follows that for any probability measureQ over Θ OPT ∩ Θ t-1 , J(θ ⋆ ) -J(θ t ) ≤ J(θ + ) -J(θ -) dQ(θ + ). Let Θ OPT t-1 = Θ OPT ∩ Θ t-1, and take Q = Q t-1 in the integral above defined byQ t-1 = P ′ t-1 (θ t ∈ • ∩ Θ OPT t-1)/p t-1 , p t-1 > 0 ; any arbitrary probability measure, otherwise , which yields the boundJ(θ ⋆ ) -J(θ t ) ≤ 1 p t-1 E ′ t-1 [(J(θ t ) -J(θ -))1[θ t ∈ Θ OPT t-1 ]],where for p t-1 = 0 we take the upper bound to be positive infinity. Observing that X t is a subgradient of J at θ t (Claim 15 and equation ( 6)) and applying Cauchy-Schwartz, we have thatJ(θ t ) -J(θ -) ≤ ⟨X t , θ t -θ -⟩ ≤ ∥X t ∥ V -1 t-1 ∥θ --θ t ∥ Vt-1 ,Moreover, since θ -∈ Θ t-1 , observing that norms are non-negative, that Θ OPT t-1 ⊂ Θ t-1 and using equation ( 7),∥θ --θ t ∥ Vt-1 1[θ t ∈ Θ OPT t-1 ] ≤ ∥θ --θ t ∥ Vt-1 1[θ t ∈ Θ t-1 ] ≤ γ t-1, and therefore, since γ t-1 is F ′ t-1 -measurable (by assumption), we have the bound1 p t-1 E ′ t-1 [(J(θ t ) -J(θ -))1[θ t ∈ Θ OPT t-1 ]] ≤ γ t-1 p t-1 E ′ t-1 [∥X t ∥ V -1 t-1].Chaining the above inequalities and writing these in terms of∆ t = E ′ t-1 [∥X t ∥ V -1 t-1 ] -∥X t ∥ V -1 t-1, we have the boundEQUATIONCombining equations ( 9) and ( 10) with the regret decomposition in equation ( 8),EQUATIONfor any τ ∈ [T ]. For the first sum in that upper bound, by Cauchy-Schwartz and the elliptical potential lemma (Lemma 14, which can be applied because by assumption λ ≥ 1), for any τ ∈ N + ,EQUATION)To deal with the second sum, observe that since for all t ∈ N + , V t-1 ⪰ λI andX t ∈ B d 2 , ∥X t ∥ 2 V -1 t-1 = ⟨X t , V -1 t-1 X t ⟩ ≤ ∥X t ∥ 2 2 /λ ≤ 1/λ and so |∆ t | ≤ 2/ √ λ for all t ∈ N + .Moreover, observe that (∆ t ) t is an (F ′ t ) t -adapted martingale difference sequence. We thus apply Lemma 13 with c = 2/ √ λ, to obtain the deviation probability boundEQUATION)The bounds on the two 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 : R d → R be a convex function and let u be its maximizer over the unit ball. Then,for any v ∈ H u . = {v ∈ R d : ⟨v, u⟩ ≥ 1}, we have F (v) ≥ F (u).Proof. For any v ∈ R d 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 ∈ B d 2 and α ∈ (0, 1) such that u = αz + (1 -α)v. By convexity and maximality,F (u) = F (αz + (1 -α)v) ≤ αF (z) + (1 -α)F (v) ≤ αF (u) + (1 -α)F (v) .Hence, F (u) ≤ F (v). Since any finite convex function on an open set is continuous, the result holds for any v ∈ H u .Proof of Lemma 4. Write F = J • ψ δ t ; since J is convex and ψ δ t is affine, F is convex. Let u + be the maximiser of F over B d 2 , and note that since F is a convex function andB d 2 is a convex set, u + ∈ ∂B d 2 = S d-1 2 . By assumption, θ ⋆ ∈ ψ δ t (B d 2 ), and so J(θ ⋆ ) ≤ F (u + ). By Lemma 16, F (u + ) ≤ F (u ′ ) for any u ′ ∈ H u + . Thus, ψ δ t (H u + ) ⊂ Θ OPT , and soΘ OPT ∩ ψ δ t (aB d 2 ) ⊃ ψ δ t (H u + ) ∩ ψ δ t (aB d 2 ) ⊃ ψ δ t (H u + ∩ aB d 2 ) . Therefore, for any measure Q on R d , Q(Θ OPT ∩ ψ δ t (aB d 2 )) ≥ Q(ψ δ t (H u + ∩ aB d 2 )) ≥ inf u∈S d-1 2 Q(ψ δ t (H u ∩ aB d 2 )) .Algorithm 3 is a version of Thompson sampling we call confident linear Thompson sampling. It is extremely simple: at each step t ∈ [T ], it picks an action X t that is optimal according to an estimate θ t sampled uniformly onψ δ t-1 ( √ dB d 2 ) = Θ t-1 , a√ d-inflation of the ridge regression confidence set. It differs from usual linear Thompson sampling of Agrawal and Goyal (2013) through the use of a uniform sampling distribution. Remark 13. 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 a high-probability event where every θ t lands within some inflated version of the corresponding Θ t-1 (as in Agrawal and Goyal, 2013; Abeille and Lazaric, 2017) .Algorithm 3 Confident linear Thompson sampling for t ∈ N + do Sample U t ∼ U( √ dB d 2 )and compute θ t = ψ δ t-1 (U t ) Compute some X t ∈ arg max x∈X ⟨x, θ t ⟩, play action X t and receive reward Y t Theorem 17. Let Assumption 1 hold. Fix δ ∈ (0, 1] and let λ ≥ 1. There exist some universal constant C > 0 such that with probability 1 -δ, a learner using Algorithm 3 incurs regret satisfyingR(T ) ≤ Cβ δ τ -1 √ d dτ log(1 + τ /(λd)) + (τ /λ) log(τ /(λδ)) for all τ ∈ [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 = ∞. Fix b t = √ d for all t ∈ N. As each θ t is a uniform random variable on Θ t-1 for all t ∈ N, and so event E T holds almost surely. Moreover, as for ensemble sampling, we take E ⋆ T to be the event from the standard concentration result for ridge regression, Lemma 3, observing as before that,ψ δ t-1 (B d 2 ) ⊂ ψ δ t-1 ( √ dB d 2 ) = ψ δ t-1 (b t B d 2 ). We pick A ′ t-1 = A t-1 for all t ∈ N + . Now, to lower bound each p t-1 , note that on E ⋆ T , by Lemma 4 applied with Q(A) = P(θ t ∈ A | σ(F t-1 ∪ A ′ t-1 )) =: P ′ t-1 (θ t ∈ A), p t-1 = P ′ t-1 (θ t ∈ Θ OPT ∩ Θ t-1 ) ≥ inf u∈S d-1 2 P ′ t-1 (θ t ∈ ψ δ t-1 (H u ∩ √ dB d 2 )) .And, since ψ δ t-1 is a bijection and U t is uniform on √ dB d 2 , and thus rotationally invariant,inf u∈S d-1 2 P ′ t-1 (θ t ∈ ψ δ t-1 (H u ∩ √ dB d 2 )) = inf u∈S d-1 2 P ′ t-1 (U t ∈ H u ∩ √ dB d 2 ) = U(H 1 ∩ √ dB d 2 ) .As established in Appendix A of Abeille and Lazaric (2017) ,U(H 1 ∩ √ dB d 2 ) ≥ 1/(16 √ 3π), independently of d. This means that, on E ⋆ T , bt-1 pt-1 ≤ 16 √ 3πd for all t ∈ N + ; plugging this into the regret bound of Theorem 2 yields the claim.Lemma 6 follows by taking y = 81m 2500 and ϵ = 1 20 in Theorem 18. Theorem 18. Let U ∈ R m×d , m ≥ d, be a random matrix with independent rows U 1 , . . . , U m distributed uniformly on √ dS d-1. Then, for all y > 0, ϵ ∈ (0, 1/2), and withc ϵ = 1/(1 -2ϵ), P{ √ m -c ϵ √ y ≤ s d (U ) ≤ s 1 (U ) ≤ √ m + c ϵ √ y} ≥ 1 -exp{-3y/8 + log(2(1 + 2/ϵ) d )} .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 x ∈ S d-1 2 , let X ∼ U(S d-12 ) and X 2 x = ⟨X, x⟩ 2 . Then, EX 2 x = 1/d, and for some ν, c > 0 satisfying ν ≤ 2/d 2 and c ≤ 4/d and all 0 < s < 1/c,E exp(s |X 2 x -EX 2 x |) ≤ exp s 2 ν/2 1 -cs . Proof. It is known that X 2 x ∼ Beta( 1 2 , d-12 ) (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 1, and our result follows by substituting in the parameters of our beta distribution, and bounding the resulting ν and c crudely.We will need the next two results from Vershynin (2018) , appearing as Lemma 4.1.5 and Exercise 4.4.3 respectively.Lemma 20 (Appropximate isometry). For any matrix A ∈ R m×d and ϵ ≥ 0,∥A T A -I∥ ≤ ϵ ∨ ϵ 2 =⇒ 1 -ϵ ≤ s d (A) ≤ s 1 (A) ≤ 1 + ϵ .Lemma 21 (Quadratic form on a net). For a symmetric matrix A ∈ R d×d and an ϵ-net N of S d-1 2 with ϵ ∈ (0, 1/2),∥A∥ ≤ 1 1 -2ϵ sup x∈N |⟨Ax, x⟩| .Proof of Theorem 18. Fix x ∈ S d-1, and considerZ 2 x = 1 m ∥U x∥ 2 2 = d m m j=1 ⟨U j / √ d, x⟩ 2 . Ob- serve that each U j / √ d ∼ U(S d-12 ); thus, by Claim 19 and since U 1 , . . . , U m are independent, adopting the notation of the claim, we have that, for all 0 < sd/m < 1/c, Boucheron et al. (2013) would term sub-gamma with parameters (d 2 ν/m, cd/m) on both tails. Applying the maximal-form of the there-stated Bernstein-type bound for sub-gamma random variables, a union bound over the two tails, and the bounds ν ≤ 2/d 2 and c ≤ 4/d from Claim 19, we have that, for all y > 0,E exp(s |Z 2 x -1|) = m j=1 E exp sd m |X 2 x -EX 2 x | ≤ exp s 2 d 2 ν/(2m) 1 -csd/m . Thus, |Z 2 x -1| is whatP(|Z 2 x -1| ≥ y/m ∨ y/m) ≤ 2e -3y/8 . Now let N ϵ , ϵ ∈ (0, 1/2), be an ϵ-net of S d-1 2 . By Lemma 21, sup x∈S d-1 2 |Z 2 x -1| ≤ 1 1 -2ϵ max x∈Nϵ |Z 2 x -1| .Also, by our bound on nets from Lemma 10, |N ϵ | ≤ (1 + 2/ϵ) d . Thus, taking a union bound over x ∈ N ϵ , we have that for any y > 0 and ϵ ∈ (0, 1/2), the probability thatP sup x∈S d-1 2 |Z 2 x -1| ≤ 1 1 -2ϵ y/m ∨ y/m ≥ 1 -exp{-3y/8 + log(2(1 + 2/ϵ) d )} .We conclude the proof by observing that sup x∈S d-1|Z 2x -1| = ∥U T U/m -I∥ and applying Lemma 20.Proof of Lemma 9. Fix u ̸ = 0 and letz = V 1/2 t u. Then, R t (u) = 1 m m j=1 R j t (u) = 1 m m j=1 ⟨z, Γ j t ⟩ 2 ∥z∥ 2 2 = ∥Γ T t z∥ 2 2 m∥z∥ 2 2 . Now note that for all non-negative a, b, A, B with b ≥ a, A 2 a 2 - B 2 b 2 = A 2 (b 2 -a 2 ) + (A 2 -B 2 )a 2 a 2 b 2 ≤ 2A 2 a 2 |b -a| b + |A -B|(A + B) b 2 . Let u, v ∈ S d-1 2 , z = V 1/2 t u, w = V 1/2 t v. Let ϵ = ∥u -v∥ 2 . Let A = ∥Γ T t z∥ 2 , B = ∥Γ T t w∥ 2 , a = ∥z∥ 2 , b = ∥w∥ 2 . Assume without loss of generality that b ≥ a. Since v ∈ S d-1 2 and b ≥ √ λ, 2 A 2 a 2 |b -a| b ≤ 2∥Γ t ∥ 2 ∥z -w∥ 2 √ λ ≤ 2∥Γ t ∥ 2 ∥V 1/2 t ∥ √ λ ϵ ,and likewise|A -B|(A + B) b 2 ≤ 2∥Γ t ∥∥Γ T t (z -w)∥ 2 √ λ ≤ 2∥Γ t ∥ 2 ∥V 1/2 t ∥ √ λ ϵ .Putting things together, we have|R t (u) -R t (v)| ≤ 4∥Γ t ∥ 2 ∥V 1/2 t ∥ m √ λ ϵ .This proof will require the following definition of conditional subgaussianity, and the standard de la Peña-type concentration result for sequences of such random variables, stated thereafter. Definition 22. Let A, B be random variables and F a σ-algebra. We say that A is F-conditionally B-subgaussian when B is non-negative and F-measurable, and for all s ∈ R,E[exp{sA} | F] ≤ exp{s 2 B 2 /2} almost surely. Lemma 23. Let (A i , B i , H i ) i be such that each A i is H i -conditionally B i -subgaussian.Then, for any x, y > 0,P    ∃τ ∈ N : τ i=1 A i 2 ≥ τ i=1 B 2 i + y x + log 1 + 1 y τ i=1 B 2 i    ≤ e -x/2 .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,σ t = 2Q 2 t + Q t R t . Claim 24. Each W t+1 is σ(F t ∪ A ′′ t )-conditionally σ t / √ m-subgaussian. Claim 25. For any 0 ≤ t ≤ τ < T , 1 + t i=τ σ 2 i ≤ 3 + t i=τ Q i R i . Claim 26. For any 0 ≤ t ≤ τ < T , on the event {R 0 ≤ 2}, 1 + t i=τ σ 2 i ≤ (3 + 2T ) 2 .Proof of Lemma 12. For any τ < T , by Claim 24 and Lemma 23 applied with y = 1/m and any x > 0, with probability 1 -exp{-x 2 }, for all t ∈ {τ, . . . , T -1},t i=τ W i+1 2 ≤ x m + 1 m log t i=τ σ 2 t + 1 τ i=1 σ 2 i + 1 .We take x = 2 log(3 + 2T ), which by Claim 26 exceeds log( t i=τ σ 2 t + 1) on {R 0 ≤ 2}. Therefore, on the intersection of {R 0 ≤ 2} and the event implicitly defined above,t i=τ W i+1 ≤ 2x m τ i=1 σ 2 i + 1 .By our assumption on m, 2x/m ≤ 1/10. Also, and using a trivial bound and Claim 25,τ i=1 σ 2 i + 1 ≤ τ i=1 σ 2 i + 1 ≤ 3 + t i=τ Q i R i ,which combined with the display above yields the form of the claimed bound.To conclude the proof, we take a union bound over τ ∈ {0, . . . , T -1} and note that, by our assumption on m and choice of x, x/2 ≤ m/400.H Proofs of Claims 11 and 24 to 26Let F ′′ t = σ(F t ∪ A ′′ t ∪ σ(X t+1 )), where we recall that A ′′ t = σ(A t ∪ σ(ξ t+1 , J t+1 , X t+1 )) for each t ∈ N, that E ′′ t denotes the F ′′ t -conditional expectation, and that the purpose of conditioning on F ′′ t will be to integrate out the random targets U 1 t+1 , . . . , U m t+1 .Proof of Claim 11. Fix u ∈ S d-1 2 and note thatR j t+1 = ⟨u, S j t + U j t+1 X t+1 ⟩ 2 ∥u∥ 2 Vt+1 = ⟨u, S j t ⟩ 2 + (U j t+1 ) 2 ⟨u, X t+1 ⟩ 2 + 2U j t+1 ⟨u, S j t ⟩⟨u, X t+1 ⟩ ∥u∥ 2 Vt + ⟨u, X t+1 ⟩ 2 .(14) Observe that X t+1 and S j t = S j 0 + s≤t U j s X s are F ′′ t -measurable and that U j t+1 is independent of F ′′ t . The latter of these gives E ′′ t U j t+1 = 0 and E ′′ t (U j t+1 ) 2 = 2 3 . With that, we have thatE ′′ t R j t+1 -R j t = ⟨u, S j t ⟩ 2 + 2 3 ⟨u, X t+1 ⟩ 2 ∥u∥ 2 Vt + ⟨u, X t+1 ⟩ 2 - ⟨u, S j t ⟩ 2 ∥u∥ 2 Vt (15) = 2 3 ⟨u, X t+1 ⟩ 2 ∥u∥ 2 Vt -⟨u, S j t ⟩ 2 ⟨u, X t+1 ⟩ 2 ∥u∥ 2 Vt ∥u∥ 2 Vt + ⟨u, X t+1 ⟩ 2 = ⟨u, X t+1 ⟩ 2 ∥u∥ 2 Vt + ⟨u, X t+1 ⟩ 2 2 3 - ⟨u, S j t ⟩ 2 ∥u∥ 2 Vt = Q t 2 3 -R j t .The statement follows by averaging over j ∈ {1, . . . , m}.Proof of Claim 24. Subtracting the first expression on the right-hand side of equation ( 15) from equation ( 14) and averaging over j ∈ {1, . . . , m}, we see thatW t+1 = R t+1 -E ′′ t R t+1 = Q t m m j=1 (U j t+1 ) 2 - 2 3 + 1 m m j=1 U j t+1 H j twhere H j t = ⟨u, X t+1 ⟩⟨u, S j t ⟩/∥u∥ 2 Vt+1 . Note that Q t and H t are F ′′ t measurable and that U 1 t+1 , . . . , U m t+1 are independent of F ′′ t and one another, and that their absolute values are bounded by 1. Thus, examining the two terms in the sum we see that:• Qt m m j=1 ((U j t+1 ) 2 -2 3 ) is F ′′ t -conditionally Qt √ m -subgaussian. • 1 m m j=1 U j t+1 H j t is F ′′ t -conditionally Ht √ 2m -subgaussian,where(H t ) 2 := 1 m m j=1 (H j t ) 2 = 1 m m j=1 ⟨u, X t+1 ⟩ 2 ⟨u, S j t ⟩ 2 ∥u∥ 4 Vt+1 = Q t m m j=1 ⟨u, S j t ⟩ 2 ∥u∥ 2 Vt+1 = Q t R t .The result follows by recalling that the sum of an a-subgaussian random variable and a b-subgaussian random variable is 2(a 2 + b 2 )-subgaussian.The proof of the final two claims will require the following simple lemma. λ + j i=1 b i 2 ≤ n λ(λ + n) ≤ 1 λ .Proof. Let B 0 = 0 and for j ∈[n] let B j = B j-1 + b j . The function f (x) = 1 λ+x is decreasing on [0, ∞). Hence, Bj Bj-1 f (x)dx ≥ b j f (B j ). Summing these up, [log(λ + x)] Bn 0 = Bn 0 f (x)dx = n j=1 Bj Bj-1 f (x)dx ≥ n j=1 b j f (B j ) = n j=1 b j λ + j i=1 b i .Evaluating the left-hand side and noting that B n ≤ n holds because b i ≤ 1 gives the first result. For the second sum, we use a similar argument with g(x) = 1/(λ + x) 2 :n j=1 b j λ + j i=1 b i 2 = n j=1 b 2 j (λ + B j ) 2 ≤ n j=1 b j (λ + B j ) 2 (because 0 ≤ b j ≤ 1) ≤ n 0 g(x)dx (g is decreasing on [0, ∞), B n ≤ n) = -1 λ + x n 0 = n λ(λ + n) .Proof of Claim 25. Noting that since ∥u∥ 2 = 1 and λ ≥ 5, by Lemma 27,t i=τ Q i ≤ T -1 i=0 ⟨u, X i+1 ⟩ 2 λ + i+1 j=0 ⟨u, X j ⟩ 2 ≤ log(1 + T /5) ≤ T and t i=τ Q 2 i ≤ T -1 i=0 Q 2 i = T -1 i=0 ⟨u, X i+1 ⟩ 2 λ + i+1 j=0 ⟨u, X j ⟩ 2 2 ≤ 1 λ ≤ 1 .Using these, we have1 + t i=τ σ 2 i = 1 + 2 t i=τ Q 2 i + t i=τ R i Q i ≤ 3 + t i=τ R i Q i ≤ 3 + T max τ ≤i≤t R i .Proof of Claim 26. Since (a + b) 2 ≤ 2a 2 + 2b 2 and by symmetry, Guidelines:R j i = ⟨u, S j 0 + i i=1 U j ℓ X ℓ ⟩ 2 λ + i ℓ=1 ⟨u, X ℓ ⟩ 2 ≤ 2R j 0 + 2 i ℓ=1 ⟨u, X ℓ ⟩ 2 λ + i ℓ=1 ⟨u, X ℓ ⟩ 2 ≤ 2R j 0 + 2 max b∈[0,1] (ib) 2 λ + ib 2 ≤ 2R j 0 + 2i. By definition, R i = 1 m m j=1 R j i ,• 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or 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? 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of 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 is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.The statement of this result within said exercise contains a typographical error, in that the c 2 appears outside the brackets, rather than multiplying just the τ . The version here is the correct result. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 
2. 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.
questions: questions: The questions are raised in the weakness section. I am willing to re-evaluate the scores if these questions are properly answered.
limitations: limitations: This paper is pure theoretical and does not have any limitations.
paper_summary: paper_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).
strength_weakness: strength_weakness: - 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.
- 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.
questions: 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.

**Minor comment (but for clarity)**
- 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.
- 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."
questions: 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: limitations: There is no separate "Limitations" section. But the authors discuss the weakness of the proposed method.
paper_summary: paper_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.
The 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.
strength_weakness: strength_weakness: - 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.
- 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.
questions: 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)$.
The 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?

* * *
Ishfaq, Haque, et al. "Randomized exploration in reinforcement learning with general value function approximation." International Conference on Machine Learning. PMLR, 2021.
limitations: limitations: The authors have addressed the limitations in Section 4.
The content discussed in this paper appears to have little to no negative societal impact.

Comments: title: thanks
Please read the authors’ rebuttal and reply by August 13, 2024 (11:59 PM, AOE time)
References
comment: Thank you for the author's detailed response. I understand the motivation behind ES research in the linear setting and believe that the contributions of this paper should be appreciated. (Please note that I support the acceptance of this paper.) However, I feel that the current manuscript and the author rebuttal do not fully explain that motivation, and I believe this aspect needs to be supplemented.

I am not trying to depreciate this work; rather, I believe the results in this paper can be further strengthened through appropriate comparisons and motivation with other works.

I sincerely hope that the content of the author-reviewer discussion has helped the authors to further polish their work.

Accordingly, I will raise my score from 5 to 7.
Sorry for the late reply. 

Thank the authors for their response. I would like to increase my score to 6.
Thank you for the comment. We will be happy to expand the discussion of randomized methods, as indicated beforehand. 

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

On "discussing in detail the pros and cons of the algorithm studied in this paper compared with those randomized methods in the literature":
As confirmed in our rebuttal, we would be happy to spend the additional page granted at camera ready on this discussion. We could also include a more extensive related works section in the appendices. Nonetheless, we must emphasize that our novel contribution is theoretical, not algorithmic–-we do not introduce ensemble sampling, its already a commonly used method in the applied literature–-and there is a strict page limit. We are also not writing a tutorial paper on randomized methods, but providing a novel theoretical contribution. We are writing for an expert that understands randomized methods, and wants to know what specific tricks are required to show that ensemble sampling works: for an expert that can make the comparison between methods themselves. Nevertheless, again, we are happy to use the extra space for a discussion of the relative merits of all methods mentioned.
__Clarifying the confusion about the goal of studying ES in the linear setting__ A minimum requirement for an algorithm that aims at some level of generality is that it should also work reasonably well in simpler settings. Moreover, if the algorithm achieves some generality, compromising on optimality in a simpler setting (in our case, the linear setting) should be  acceptable. We are sure that the reviewer is also aware of the many examples where such a compromise exist or is even unavoidable (there is a large body of literature on problems of this type). Ours is the first paper that gives *any* sort of theoretical support for ES. Given the amount of work devoted to ES (empirical and theoretical), we think that a paper that changes this poor status quo should be of major interest (news!) to the community. We note in passing that all previous papers on analyzing ES started with the linear setting (Lu and Van Roy'17; Phan et al,'19; Qin et al,'22 -- all papers published at NeurIPS!), and their rationale for studying ES in the ensemble sampling was exactly the same as ours (see, e.g., the introduction of the paper by Qin et al.) 

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

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

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

__On ES vs PHE in Deep Learning__ Suppose that our model is a neural network with $p$ parameters, and we use a standard NTK-style linearisation (see, e.g., Jia et al., 2022). TS/PHE with incremental updates gives:
- $O(p^2)$ per step computational complexity for the matrix-vector product, used for Sherman-Morrison updates
-  $O(p^2)$ memory for storing the covariance matrix. 

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

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

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

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

In conclusion, we are not claiming that we solve all longstanding open problems related to ES, or even that we solve the hardest of these, but we claim that we solve some of these problems, which we think are of major interest to the community, especially given the new proof techniques we employ.
Thank you to both the authors and the reviewers for the excellent discussion here. I would like to chime in briefly regarding the theoretical and empirical merits of randomized exploration techniques. According to Proposition 3.2 of Ishfaq et al. (2021), LSVI-PHE should be equivalent to Thompson Sampling in the linear case. However, the concept of PHE is more easily generalizable to complex settings where the reward is nonlinear (Kveton et al., 2020; Jia et al., 2022).

Regarding the practical use of randomized exploration, I believe that recently proposed algorithms, such as LMC-TS (Xu et al., 2022) and LSVI-LMC (Ishfaq et al., 2023), which utilize MCMC to approximate complex posterior distributions, serve as strong baselines. These algorithms not only achieve the same regret as TS algorithms but also feature simple algorithmic designs that generalize well to nonlinear and complex environments.

Therefore, it would be beneficial to discuss in detail the pros and cons of the algorithm studied in this paper compared with those randomized methods in the literature, both empirically and theoretically.

**References**
 
Ishfaq, Haque, et al. "Provable and practical: Efficient exploration in reinforcement learning via langevin monte carlo." arXiv preprint arXiv:2305.18246 (2023).

Jia, Yiling, et al. "Learning Contextual Bandits Through Perturbed Rewards." arXiv preprint arXiv:2201.09910 (2022).

Kveton, Branislav, et al. "Randomized exploration in generalized linear bandits." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

Xu et al. “Langevin monte carlo for contextual bandits.” International Conference on Machine Learning (2022).
I appreciate the authors for the detailed explanation. Now, I understand the difference between ensemble sampling and PHE better. It would be great to include this explanation in the main text. However, according to the author’s explanation, PHE does not seem to be equivalent to Thompson sampling, at least in the linear case, from the perspective that PHE requires refreshing the noise for observations from previous episodes in each round. Note that in LinTS (Agrawal & Goyal, 2013), the mean vector and covariance matrix are updated incrementally (i.e., $\mathbf{V}\_t = \lambda \mathbf{I}\_d + \sum\_{i=1}^t X\_i X\_i^\top = \mathbf{V}\_{t-1} + X\_t X\_t^\top$, $\mathbf{b}\_t = \sum\_{i=1}^t Y\_i X\_i = \mathbf{b}\_{t-1} + Y\_t X\_t$ ). 

Now consider a variant of Thompson sampling where sampling $M$ parameters $\theta\_t^{(j)} \sim \mathcal{N}(\mathbf{V}\_{t-1}^{-1} \mathbf{b}\_t,   \nu \mathbf{V}\_t^{-1})$ for $j \in [M]$, and select an action based on the most optimistic parameter, i.e., $X_t = \arg \max\_{x, j} \langle x, \theta_t^{(j)} \rangle$ (or we may choose a parameter uniformly random as this paper does). This variant of Thompson sampling would guarantee the same $\tilde{O}(d^{3/2} \sqrt{T})$ regret as traditional TS (Agarawal & Goyal, 2013), but it also can work online. It would be helpful if you could explain the advantages of the ensemble approach in this paper compared to this variant of Thompson sampling.

Moreover, as the author mentioned, although this paper theoretically addresses a longstanding open problem that had previously been a failed attempt published in NeurIPS, I do not believe the paper offers a complete solution to the open problem.

Certainly, ensemble sampling has shown to be tractable and empirically effective for nonlinear, complex tasks like Deep RL. Given this, one would intuitively expect that ensemble sampling would be at least equivalent to or provide a tighter regret bound than existing randomized exploration algorithms, even in a linear setting. However, I believe the theoretical results proposed in this paper, while very interesting, are only a partial solution.

According to the rebuttal to Reviewer Pgmx, the author claims that “if an algorithm provably cannot work in the linear setting, chances are it won’t work beyond it, either”. However, by the same token, the results of this paper indicate that ensemble sampling is not optimal even in the linear setting. Furthermore, if ensemble sampling is advantageous only when a closed form is not provided, wouldn’t there be no reason to use ensemble sampling in linear settings where a closed form is given? Although the paper presents a novel proof technique, I do not think it offers a solution to the longstanding open problem, especially since even this technique, which is based on the closed-form of the linear setting, fails to demonstrate the efficacy of ensemble sampling in the linear setting where a closed form is provided.
Thank you!
Dear reviewer,

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

The author-reviewer discussion period is shortly coming to an end. We were hoping to get a confirmation from you that you've considered our rebuttal, and to let us know if you have any further questions.
I agree that the work can be extended with NTK and itself is of interest to the theoretical community. And it would be a good addition to provide the discussion on $\lambda$.
Given the placement of its previous attempts and the authors' response, I'll change my rating toward having this work published i.e. from 4 to 6.
A paper offering contributions of this magnitude deserves acceptance. I am raising my score from 6 to 7.
Dear Reviewers,

Thank you for your hard work during the review process. The authors have responded to your initial reviews. **If you haven’t already done so, please take the time to carefully read their responses.** It is crucial for the authors to receive acknowledgment of your review by the deadline for the author-reviewer discussion period, which is August 13, 2024 (11:59 PM, Anywhere on Earth). Please address any points of disagreement with the authors as early as possible.

Best,

Your AC
Here are all the papers referred to in our rebuttals:

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

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

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

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

_Lu, Xiuyuan, and Benjamin Van Roy. "Ensemble sampling." Advances in neural information processing systems 30 (2017)._