Improved Regret of Linear Ensemble Sampling
Authors: Harin Lee
Min-hwan Oh
Venue: NeurIPS 2024 poster (2024)
Keywords: Linear Bandit
Ensemble Sampling
Primary area: bandits
TL;DR: We prove a $O(d^{3/2}\sqrt{T})$ frequentist regret bound for linear ensemble sampling.

Abstract: In this work, we close the fundamental gap of theory and practice by providing an improved regret bound for linear ensemble sampling. We prove that with an ensemble size logarithmic in $T$, linear ensemble sampling can achieve a frequentist regret bound of $\tilde{\mathcal{O}}(d^{3/2}\sqrt{T})$, matching state-of-the-art results for randomized linear bandit algorithms, where $d$ and $T$ are the dimension of the parameter and the time horizon respectively. Our approach introduces a general regret analysis framework for linear bandit algorithms. Additionally, we reveal a significant relationship between linear ensemble sampling and Linear Perturbed-History Exploration (LinPHE), showing that LinPHE is a special case of linear ensemble sampling when the ensemble size equals $T$. This insight allows us to derive a new regret bound of $\tilde{\mathcal{O}}(d^{3/2}\sqrt{T})$ for LinPHE, independent of the number of arms. Our contributions advance the theoretical foundation of ensemble sampling, bringing its regret bounds in line with the best known bounds for other randomized exploration algorithms.

Improved Regret of Linear Ensemble Sampling
Harin Lee Scoul National University Seoul, South Korea harinboy@snu.cc ac.
Min-hwan Oh Seoul National University Seoul, South Korea minoh@smu. ac. kr
Abstract
In this work, we close the fundamental gap of theory and practice by providing improved regret bound for linear ensemble sampling. We prove that with an ensemble size logarithmic in T, linear ensemble sampling can achieve a frequen- tist regret bound of ((d//vT)) matching state-of-the-art results for randomized linear bandit algorithms, where d and T the dimension of the parameter and the time horizon respectively. Our approach introduces a general regret analy- sis framework for linear bandit algorithms. Additionally, we reveal significant relationship between linear ensemble sampling and Linear Perturbed-Histee ploration (LinPHE), showing that LinPHE special case of linear ensemble sampling when the ensemble size equals T. This insight allows us to derive new regret bound of (223/2T) for LinPHE, independent of the number of arms. Our contributions advance the theoretical foundation of ensemble sampling, bringing its regret bounds in line with the best known bounds for other randomized exploration algorithms.
Ex-
1 Introduction
Ensemble sampling 16 has emerged as an empirically effective randomized exploration technique in various online decision-making problems, such online recommendation [17 27 26 and deep reinforcement learning [8] Despite its popularity. the theoretical understanding of ensemble sampling has lagged behind, even for the linear bandit problem, with previous results revealing sub- optimal outcomes. For instance, a prior work [2]] demonstrated that linear ensemble sampling could achieve O(VT) Bayesian regret with an ensemble size growing at least linearly with T. However, the requirement for the ensemble size be linear in highly unfavorable and prohibitive in many practical settings. A recent work [10] showed that symmetrized version of linear ensemble sampling could provide an improvement in dependence on ensemble size of (d T') and show frequentist regret bound of O(d"/2VT)) However, this regret bound clearly falls short the existing frequentist regret achieved by standard randomized algorithms such Thompson Sampling (TS) [ and Perturbed Historry Exploration (PHE) [B
In this work, we close this fundamental gap by providing an improved regret bound for linear ensemble sampling. We prove that linear ensemble sampling with an ensemble size logarithmic T can still attain a frequentist regret bound of ((d2/2TT), marking the first time that linear ensemble sampling achieves fftee-o-thhe-e of-the-art result for randomized linear bandit algorithms. Our
'LiTTS 4 2 has regret of Ö min(d /T, /ooloog K)). and LinPHE 12 has regret of Od K). For exchanges between factors of ((vd) and (vVlog K). refer to the analysis of Agrawal and Goyal 4 Therefore, the existing result
linear ensemble sampling [10] has gap of at least (d)) compared to LinTS and LinPHE. Besides this gap in regret bounds, there appears to be rather counter-in intuitive dependence on ensemble size in Janz et al. 10 (see Remark 2 in Section
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

approach not only improves upon the regret bound but also simplifies the algorithm by avoiding the use of symmetrized perturbations. making more practical for implementation. For regret analysis. we present a general, concise framework for analyzing linear bandit algorithms,, which may be of independent interest. Furthermore, we rigorously reveal the significant relationship between ensemble sampling and PHE for the first time, showing that in the regime where the ensemble size equals T, linear PHE (LinPHE) is a special case of linear ensemble sampling. With this new insight, we can use the regret analysis for ensemble sampling to derive a new regret bound of O(d/2 /T) for LinPHE, which is independent of the number of arms K.
Our main contributions are summarized as follows:
We prove (dd//2 regret bound (Theorem | for linear ensemble sampling with an ensemble size of m = QK( log T), where K denotes the number of arms, Importantly, our regret bound does not depend on K or m even logarithmically. Our result is the first to establish ((d3/2 regret for linear ensemble sampling with ensemble size sublinear in T, improving the previous bound by the factor d while maintaining the ensemble size to be logarithmic in T.
As part of the regret analysis, we present general regret analysis framework (Theorem 2 for linear bandit algorithms. This framework not only generalizes the regret analysis of randomized algo- rithms such as ensemble sampling and PHE but also applies to other optimism- -aasd deterministic algorithms. This result can be of independent interest beyond ensemble sampling.
We rigorously investigate the relationship between linear ensemble sampling and LinPHE. We show that in the regime of ensemble size T, LinPHE is special case of the linear ensemble sampling algorithm. To our best knowledge, this is the first result to show the equivalence between linear ensemble sampling and LinPHE.
As a byproduct, with this new insight into the relationship between linear ensemble sampling and LinPHE, we provide an alternate analysis for LinPHE as an extension of the analysis for linear ensemble sampling, achieving a (13/2 /T) regret bound with no dependence on K.
1.1 Related Work
The stochastic linear bandit problem [4] is foundational sequential decision-making problem and a core model for multi- numd bandits with features. Numerous algorithms have been developed for this problem. including deterministic approaches such UCB-based methods [5] g and
randomized algorithms such as Thompson sampling [24] 7 and PHE [1+
Thompson sampling [24]_ classical randomized method, utilizes the posterior distribution of hidden
parameters based on observed data. Initially proposed for Bayesian settings [2 23), it has also
demonstrated strong performance in frequentist settings [3] 4 22 For the stochastic linear bandit,
Agrawal and Goyal [4] showed that Thompson sampling with a Gaussian prior achieves a regret bound of Od8//2 /T). which can be reduced to Odd/TToo K) for small K. However, applying Thompson sampling to complex problems remains challenging, especially when posterior computation becomes intractable, though approximate methods have been proposed [16] 25).
PHE | is another class of randomized algorithms that does not rely posterior distributions, making it potentially applicable to more complex settings. In the finite-armed linear bandit model, PHE achieves a (dd/T K)) regret bound, matching the performance of Thompson sampling for finite arms 44. However, the relationship between PHE and ensemble sampling remains unexplored in previous studies.
Ensemble sampling 116] has gained popularity as randomized exploration method across various decision-making tasks [17 27 26, [8/20] Despite its empirical success, its theoretical foundation, particularly for linear bandits, is still relatively underdeveloped. Qin et al. [21 showed that linear ensemble sampling achieves O (VT) Bayesian regret but requires impractically large ensemble size that scales linearly with T. More recently, Janz et al. [10] reduced the dependence on ensemble size to (d log T') and achieved a frequentist regret bound of 0(55/2 /T). However, the frequentist regret bound of (/23/2 /T) for ensemble sampling has yet to be achieved.

---

Algorithm Linear Ensemble Sampling
Input:
regularization parameter 0, ensemble size N, initial perturbation distribution P, on R reward perturraatoiiaiion distribution Pn on R,
ensemble sampling distribution {Je) [m]
Sample W ~ Py for each j E [m/]-
Initialize 1/6 = xPy, S = WJ, o Vo- Sy for each j [m]]
for 2, .. do
Sample j: Tt
Pull arm X, argmaxxExx x 0 and observe Y
Update V, Vi-1 + X,X,
for j = 1, 1.2..... , m do
Sample Z ~ PR
Update S = S + X,(Y, + z/) and 02 = Vi-
end for end for
2 Preliminaries
2.1 Notations
N denotes the set of natural numbers starting from 1. For a positive integer M, [M] denotes the set {1.2.... M). O₂ denotes the zero vector in Id and Ia denotes the identity matrix in Rdxdd We define and work within a probability space (S, J,P). where Q is the sample space, and P' is the probability measure. N Σ) denotes the uni- or multi-variate Gaussian distribution with mean 1 and covariance E. denotes logical conjunction ("and") and V denotes logical disjunction ("or"). With slight abuse of notation, we write {w E Ω. A} and A interchangeably when A is some condition, for simplicity.
the event set,
(-)) denotes the asymptotic growth rate with respect to problem parameters d, T, and K. (-) further hides logarithmic factors of and d.
2.2 Problem Setting
We consider the stochastic linear bandit problem. The learning agent is presented with non-empty arm set X' C Rd. For T time steps, where T N is the time horizon, the agent selects an arm X, E X' and receives real-valued reward Y,, where the reward is generated based on hidden true parameter vector, 8* e Rd. Specificall,, Y, is defined as follows:
= X, + T
where is a zero-mean random noise. The objective of the agent is to maximize the cumulative reward, equivalently, minimize the cumulative regret R(T) defined
R(T) = Σ
sup To x, x,Tor) xE
3 Ensemble Sampling for Linear Bandits
Algorithm describbe linear ensemble sampling. The learner maintains an ensemble of m estimators, where each estimator fits perturbed rewards. For the j-th estimator, random vector W Rd acts initial perturbation on the estimator, and random variable Z perturbs the reward time t. Specifically, 0i is the solution of the following minimization problem:
minimize A ||0 W /AIl2 + Σ x (v++2;) BERd
(I)
When selecting an arm, one of the m estimators is chosen according to an ensemble sampling distribution J. and acts greedily with respect to the sampled estimator. Previous ensemble sampling

---

algorithms [16] 21 10 sample the estimators uniformly from the ensemble, but we allow any policy for selecting the estimator. Further distinguishing from the algorithm presented in Janz et al. [TO], we do not sample Rademacher random variables for symmetrization, making our algorithm simpler. Ensemble sampling capable of being generalized to complex settings whenever solving mínimiza- tion problem ① is tractable. Especially when incremental updates of the minimization problem are cheap, for instance with neural networks or other gradient descent-based models, ensemble sampling can be efficient exploration strategy. The algorithm may simply store an ensemble of models, sample one to select an action, and then update the models incrementally based on the observed reward and generated perturbation.
4 Regret Bound of Linear Ensemble Sampling
Before we present the regret bound of linear ensemble sampling (Algorithm I we present the following standard assumptions the problem structure.
Assumption 1 (Arm set and parameter). X' is closed and for all x E X, ||<||| s 1. There exists S > O such that |6* S S. Both bounds are known to the agent.
Remark 1. Under Assumption [ X is a compact set. argmax x T and rewrite the definition of R(T) as 3
Therefore, we can define xt
For rigorous statement of the second assumption, we define several filtrations. For t E [T] U (0). let F == a (X,,... Xt) and F.¹ a (m, (M....... n1)) be the o-algebras generated by X; and 1): up to time respectively. We also define the o-algebra generated by the algorithm's internal randomness up until the choice of X, F.A. Let F, == (JA UFX U.F?') be the o-algebra generated by the first iterations of the interaction between the environment and the agent. In addition, let J. := (FA U F² FーL1) be the o-algebra generated in the same way as Fr, but excluding np-
Assumption (Noise). There exists a 2 0 such that T7 is Fū -conditionally o-subGaussian for all 1 E [T), ie., E [exp(sn)]FF]] S eex (a²>²//2 /2) holds almost surely for all s RR.
Now, we define a value Be to describe the variance of the generated perturbation values. Define sequence (8)) as 3,) o d log (1 + お + 2 log 1/2 + VĀS. We may omit ò when its value is clear from the context. The definition of 3r comes from Abbasi- et al. MI as a confidence radius of the ridge estimator, which we later specify in Lemma 1 We now present the regret bound of linear ensemble sampling (Algorithm D
Theorem 1 (Regret bound of linear ensemble sampling). Fix 5 (0, 1). Assume | K < cc and run Algorithm | with À > 1, m 2 C(K log T + log t), Py = NOss, X8 La), PR = (O,, ) and J. = mm) where C is universal constant and Uni((m) denotes the uniform distribution over [m]. Then, with probability at least 1 - 46, the cumulative regret of Algorithm 7
R(T) = o(ddlogT))8/)
Discussion of Theorem Theorem shows that Algorithm achieves (28 (T) frequentist regret bound with an ensemble size of m S2(K log Importantly, our regret bound does not depend on K or m even logarithmically. Hence, this regret bound matches the state-of- state-of-the-art -he- frequentist regret bound of linear Thompson sampling 4 22. Our result is the first to establish ((d/2VT) regret for linear ensemble sampling with an ensemble size sublinear in T, improving the previous bound by the factor d compared to the existing result in Janz et al. [00] We conjecture that D(d)/2VT) regret is highly likely to be the best bound for linear ensemble sampling based on the negative result in Hamidi and Bayati (9] for LinTS Compparnnn with the algorithm in Janz et al. [10] our version of linear ensemble sampling algorithm does not utilize Rademacher random variable for symmetrized perturbation. This allows our algorithm to be simpler than that of Janz et al. [10]. Partially due to this algorithmic difference, our regret analysis is quite distinct from the analysis of Janz et al. 10 (see the proof in Section 5.2)
Hamidi and Bayati have shown that LinTS without the posterior variance inflation by Vd factor (compared optimism- based algorithms such as LinUCB or OFUL ( can lead to linear regret in T. That is, the frequentist regret bound of ((2 T for LinTS is the best can derive for the algorithm.

---

Table I: Comparison of regret bounds for linear ensemble sampling
Paper
Frequentist / Bayesian
Regret Bound
Ensemble Size
Lu and Van Roy [16
Frequentist
Invalid
Invalid
Qin et al. 21
Bayesian
O log K)
((KT)
Janz et al. 10
Frequentist
((di/2 Olda/2
(d T)
This work
Frequentist
Q(K log T)
As in Lu and Van Roy 16 and Qin et al. [21], we study the finite-armed problem setting. Both studies analyze the excess regret of ensemble sampling compared to Thompson sampling through an information theoretical approach. However, direct comparisons of the regret bounds are non-trivial. The analysis by Lu and Van Roy [16] includes an error admitted by the authors and Qin et al. (21) analyze the Bayesian regret, which is a weaker notion of regret than the frequentist regret that we analyze in this work. Along with Janz et al. [00, our result also makes a progress in reducing the size of the ensemble compared to Lu and Van Roy [16] and Qin et al. [1]. The size of the ensemble required by Janz et al. [T] is (d log T). This requirement implics that their ensemble size may be smaller than ours when K is larger than d and also allows K to be infinite. However, it is important note that their resulting regret bound of (dd//2 is clearly sub-optimal compared regret bounds of other randomized exploration algorithms. Theorem achieves the tighter regret bound while simultaneously reducing the size of the ensemble.
Remark 2 (Counter-intuitly dependence on ensemble size in Janz et al. [1]] ). The regret bound in Janz al. (10) actually grows super-linearly with the ensemble size, which counter-intuitive.
Their regret bound implies that as the ensemble size increases, the performance of the algorithm deteriorates. This fails explain the superior empirical performance observed for ensemble sampling even with a large ensemble. On the contrary, our result in Theorem does not show any performance degradation as the ensemble size increases.
Remark (Generalizability of perturbation distributions). We show that Gaussian distribution for perturbation is not essential. The only properties of the Gaussian distribution we utilize are its tail probability and anti-concentration property. stated as Lemma andd Fact Tact[in in Section 5.2 Therefore, any other distributions exhibiting similar behaviors can instead be adopted. In Appendix H we rigorously demonstrate that any symmetric subGaussian distribution with lower-bounded variance can be employed, possibly at cost of constant factor. A large class of distributions, including uniform distribution, spherical distribution, Rademacher distribution, and centered binomial distribution with p 1/2 satisfy this condition. This result can be of independent interest.
5
Analysis
5.1
General Regret Analysis for Linear Bandits
We hegin by presenting general regret bound for any algorithm that selects the best arm based on an estimated parameter. This result can be of independent interest. This general bound and analysis serve general framework that includes the regret analysis of linear ensemble sampling (Theorem [ Theorem 2 (General regret bound for linear bandit algorithm). Fix E N. Assume that at each time step t [T). the agent chooses X, argmax,ex* x 0,, where 0, E Rd is chosen by the agent under some (either deterministic or random) policy. Let > and V = XI + Ei= X,X,T. Let (Er,)i
and {E2,) YT, be sequences of events that satisfy conditions:
1. (Concentration) There exists a constant ? > 0 such that
||0, 8" lly 11 (Eir) S
(2)
holds almost surely for all t E [.]].
2. (Oplimism) ε2,t E F.-1 holds and there exists a constant p E (0, 1] such that
P ((x 0r < <x, 0, and Er,) or ES, Fi-1) 2 p
(3)
holds almost surely for all t [T].
5

---

Take 3 = _ (E1., n E2,1) and any å E (0. 1]. Then, under the event & and an additional event whose probability is at least 6, the cumulative regret is bounded as follows:
2 ( 1+ p 2dT log
T dA
7 p
2T
R(T) S ?
1+
log
(4)
8
Discussion of Theorrmm2 2 The audience well-versed in the regret analysis of randomized algorithms such as TS and PHE would recognize that bounding the regret using the probability of being optimistic is standard procedure, also presented in Theorem 1 of Kveton et al. [2] and Theorem 2 of Janz al. [TO] as generalizations of the results in Agrawal and Goyal 4 and Abeille and Lazaric [2] respectively. However, our regret analysis offers much more concise approach than the existing techniques, which can be of independent interest beyond the analysis of ensemble sampling.
Theorem states that the two conditions, specifically concentration in 2 and optimism in ( are
met, then the algorithm achieves vT regret. We provide the proof of Theorem 2 in Appendix B Our
proof technique generalizes the well-studied analysis of Abeille and Lazaric 22. While their work poses conditions on a dddiimensional perturbation vector that is added to the ridge estimator, we do
not assume the use of ridge regression nor we assume that the estimator is perturbed. Instead, we only pose conditions on the final estimator the algorithm exploits, Due to this generalization, Theorem 2 even capable of inducing the regret bound of LinUCB (... which always opts for an optimistic estimator, by setting 7 23r and p = 1 with appropriate concentration events assigned to ε and Eg,1 In addition, there are several improvements that simplify the proof which are worth noting. To exploit the optimism condition, we apply Markov's 's inequality on a well-defined random variable. The proof of Abeille and Lazaric 22 relies on defining a conditional distribution, conditioned on both history and the event of being optimistic. However, such distribution may not be well-defined if the probability of the event 0 for given history. Janz et al. [TO] try to solve this problem by separately handling such exceptional cases using conditional measures. However, their conditional measures depend on the random history, leading the probability p to be a random variable, which complicates the analysis. We also note that our proof does not require convex analysis studied in Abeille and Lazaric 22]
Remark 4 (Role of event &2,) Previous results that utilize the probability of being optimistic 4 2
12 10 do not explicitly define events {E However, their existence is crucial in our analysis of linear ensemble sampling. Since the perturbation sequences are also part of the history in ensemble sampling. the probability of 0g being optimistic may be extremely small under some events in F,-1 that sample unfavorable sequences. The role of E is to confine our analysis to the case where such undesirable events do not occur.
5.2 Proof of Regret Bound in Theorem
1
We prove the regret bound of linear ensemble sampling stated in Theorem I To apply Theorem 2
of the sequences of events, namely {E,,, ) should be guaranteed with an appropriate values of y and p. We show that separate constraints can imposed on the randomness of the rewards and the perturbations respectively to guarantee the probabilities of the events. We begin by decomposing the estimator into two parts: one that fits the observed rewards and the other that perturbs the estimator.
(v++ (2) = - Σ
0. = V, S = -.-1
W
X,
X.Y+
X.Y: +
VV-1
W +
X
im1
=: 0 p.
(5)
where we define 0, = V'' X,Y and 0: = vw El= x,Zz). d is the ridge regression estimator of the observed data, and its randomness mainly comes from the noise of the rewards, {n: 1 0% is the perturbation added to 6,, and its randomness comes from the generated perturbation, W and { 1 The following lemma states the well-known concentration result for the ridge estimator.
Lemma 1 (Theorem 2 of Abbasi-Yadkori et al. M. Fix d E (0, For t E N U [0}, define
sequence of events with (8) o - /dlo (1 + +xxx + 2 log 1 + VXS as
: = (w E Ω: : 110, 0 l1v s 3,)))

---

and their intersection & : Ni=o &s. Then, P(ε) 2 21- 1
Now, address 8/- Define perturbation vector that represents the perturbation sequence for each model as follows:
2 = ( WST
zí
z1-1)
T E R
vj E [m]]
(6)
Let Z, == 2 so that Z, the perturbation vector of the model chosen at time I. The following lemma demonstrates that optimism condition Z, alone.
3 can be satisfied by an anti-concentration property of
Lemma 2 (Sufficient condition for optimism), Fort t E [T), define a vector UL-1 E Rd+t-l by
UL (VAla X1
Xx-1)
Then, x T 0" S X Og holds whenever there exists a constant c > O such that U,_ Z, 2 C-UUt1112 and 110 0--1llv,_ S c hold.
We present straightforward proof of Lemma 2 in Appendix C We significantly deviate from the analyses of Abeille and Lazaric [2] and Janz et al. [00 in the method of guaranteeing the optimism condition. Their analyses require d-dimensional perturbation vector to have constant probability of having positive component, so-called anti-concentratte, in "every" possible direction in Rd since they only prove the existence that it suffices to consider just "one" direction, specifically U--1. to produce an optimistic estimator. Since Ut-1 depends only on the sequence selected arms, the dependency between Ut-1 and Z, decouples when the dependency between {xx,]= and ) are decoupled, which we later achieve by taking the union bound in a unique way.
direction that implies optimism. We observe and exploit the fact
The following lemma shows that concentration and amti-concentration properties of the perturbation are sufficient conditions for Theorem 2 details to Appendix [
We provide sketch of its proof and defer the remaining
Lemma 3. Suppose the agent runs Algorithm 7 with some parameters. Fix 7 0 and p (0, 1]. For each t E [T') define two events
ε,, = { w wEs:
10 $ū].
E,, == fw:==weR:PP
(U, (UE::P(U.IZZ
Br-1 1102-112 and Ere Fi-1)) 2 p).
Then, E,, and where UL-1 is defined as in Lemma Take E₁ E and E2,= EG,
=
E2 satisfy concentration condition
2 with 7 = 7 Br and optimism condition (3) with the same
value of p. Consequently, with probability at least 25 - TPEE), where = 7Z (E,, i E2,))
Algorithm 7 achiives regret bound (4) of Theorem 2
Remark 5. Lemma 3 applies any perturbation- algorithm that exploits 0g 0-- 1 + 0z-1,
where 0 1 is linear transform of a random perturbation vector Z,, version of linear Thompson
sampling 2 and LinPHE also fall into this category.
Lemma 3 shifts the problem of constructing the regret bound of I lower-bounding the probabilities of the two sequences of events, {E and {E,,) Note that ε₁, and Eg, regard {x and Z, only, and are independent of further randomness of {me)T-
Sketch of Proof of Lemma 3 The concentration condition follows immediately by the triangle in- equality. To show the optimism condition, we verify the following logical implication relationship:
(UU
B (1,_ A EL.1) v E = ((x* S X, 8.) ^ E1,1) V ES,--
where Lemma bridges the unti-concentration the left hand side the optimism the right hand side. This implication relationship converted to the following probability inequality:
((xx TT= < x, 0.) A EI.) & F.-1) 2 P ((UII 2 B-1 (1,- A ε..)) & (F-1i)
By the definition of ε2, the right hand side bounded below by p. implying optimism condition The probability of failure is bounded by the union bound and Lemma
7

---

Theorem emmploys the Gaussian perturbation for a concrete instantiation of Algorithm I two values "n and yr, which serve as the confidence radii of 0r and Og for t E [2'] under the Gaussian perturbation.
We define
fr = Br (Vdlog 1+
T dx
2T x + Vd + 2 log 2T 5
+ 2 log
TT = YT + BT
Note that in terms and T. both Tr and Yr are in O (d T). Lemma 4 Illustrates the concentra- tion result. Its proof is simple application of Lemma and is presented in Appendix E
Lemma 4. Suppose Algorithm is run with parameters specified in Theorem 4 Fix E (T] and j E [m]. Suppose the sequence of arms X1, X,,...,X is chosen arbitrarily randomly, not necessarily
by the the agent. Let 02 be defined as in Eq. 5). Then, with probability at least - 5/T, 110 llv, S fr holds.
The following fact describes an anti-concentration property of Gaussian distribution, which follows from the fact that linear combination of independent Gaussians is again Gaussian.
Fact 1. If Z (0, a² Im) for some 2 0 and u. E IR" is fixed vector for some n. E N, then P (u Z 2 a [ull2)) 2 PP (= 2 1) =: Pv, where 2 ~ (0, 1). We note that pv 2 0.15.
All the building blocks we need to prove Theorem is ready. The proof illustrates that the events specified in Lemma 3 occur with high probability.
Proof of Theorem 7 Define EL, and & as in Lemma 3 with 7 fr and p PN /4, where er is defined in Eq. 7 and pv is defined in Fact [I We show that these events occur with high probability, and the rest follows from Lemma 3 For the sake of the analysis, assume that 5/T pN/2 /2 zs 0.08, which holds whenever T 2 14 or o < 0.07.
Assume that the perturbation values W and Z are F -measurable for all j [m] and i [T]. An interpretation of this assumption is that the algorithm samples all the required values in advance. Note that we still obtaín an equivalent algorithm and this modification need not actually take place in the execution. Under this assumption, the uniform sampling of je J. is the only source of randomness regarding the choice of Og and X, when conditioned on the history Fi-1- It may seem unintuitive, but this modification simplifies the proof because we only need to deal with jr.
4 and obtain PP[10 llvi_, S Rr) 2 1-8/ 8/T. Since je is sampled independently of 0 0 it holds that
We first bound the probability of E,,-- When E [m] is fixed, we can apply Lemma
E1,
Σ
- j. 10-21l1 s <5T)
m
(10Lallv. S 5TT) 2
8 T
(8)
Now, we bound the probability of Ez.. Fix j [m]] Recall that z is the perturbation vector of the j-th model, defined in Eq. ( The choice of Gaussian perturbation implics that Z ~ (0 1, (., Suppose that the sequence of arms X1, Xy is fixed. Then, we can apply Fact 1 obtaining that PU, Z 2 3 l12) 2 PN. where the probability is measured over the randomness of the perturbation sequence Z Let 1/ = I[ z 2 (r-1l((-1112)) A (100/11l v._,, S }. Then, we have that
PPI = PUU B ( P(00 1l 5T 2 PN 8/T 2 PN (9)
where the first incquality uses that ()A 2 P(A) -1A4-PP' -P(BB) holds for any events A and B, and the last inequality holds by the assumption 5/T S P2/22. However, as we assumed that the perturbation sequence is Fig meesurabbee, it is F hence 1/ is also measuraase..le.. It means that the value of Tę is determined when the history up to time is fixed. The only remaining source of randomness in choosing 9r conditioned on F._1 is the sampling of je ~ J,. Therefore, it holds that
1 m
P (1U Z 2 B -1-11U ^ (10%
$Tx) |F-11)
Σ
(10)
m j=1
8

---

Algorithm 2 Linear Perturbed-History Exploration (LinPHE)
Input: regularization parameter > 0, initial perturbation distribution Ps on R
reward-perturbatioon distribution Px on R
Initialize V/- = Ala
for /. 1,2,.... T do
Sample Wt ~ PI,
-0,1- i.i.d. PR
Update O2 V W. + + X,(Y, + 2.,i)
Pull arm X; argmaxzex" I 0,, and observe Y
Update V, = V + X,X, !
end for
Since we have verified that the expectation of the right hand side is greater than pv pv/2, Azuma- Hoeffding inequality (Lemma 12 implies that P( m Zj= I/ < /P//4) I exp m/)). Recall that this result is obtained assuming that X1,..., Xr are fixed. We take the union bound over all possible sequences of arms. However, a naive union bound multiplies K" to the failure probability, which leads to an undesirable result of m scaling linearly with T. We present the following proposition inspired by observation from Lu and Van Roy [16] that a permutation of selected arms can be regarded as equivalent. We note that the strong result of Lemma in Lu and Van Roy [16] is not applicable to setting since independently. Although we present all the main ideas to support Proposition in this section, there may be few points that readers find require further justification. Due limited space, we provide full, rigorous justification of Proposition in Appendix F where we present a different perspective on the sampling of perturbation.
do not assume that {m)) is distributed identically nor
Proposition 1. 1,...,T and P(())) < TK exp( (xp(-13m/88)
There exists an event Eg such that under Eg, 1. ES 1f PN/4 holds for t
The key observation in Proposition iis that the perturbation vector consists of i.i.d. components, hence its distribution is invariant under independent permutations. Therefore, the distributions of 0-11 and U,_,Z, Z remain invariant under the permutation of selected arms. Although the sequence of arms and the perturbation vector not independent selected arms preserves the distribution of Z. since X, and Z₂ are independent for all f E [T]. The number of equivalence classes up to permutation over sequences of arms with lengths at most T 1 is less than 7", since each arm can be selected 0 to '' - times inclusively. Therefore, we take the union bound over the 7 sequences of arms and attain Eg.
whole, the permutation that sorts the
Taking m = 8 (K log + log }),, we obtain that P(EE() < 8. Eq. (10) implies that &(,)_ P(E))
Py Therefore, by Lemma with probability at least 1 46, the cumulative regret is bounded as follows:
R(T) S Yr
1+ {)
2dT log
T [1 dd
4Yr
2T
log
1
o (IdlogT)&VT)
T)
pn
PN
Ensemble Sampling and Perturbed-History Exploration
In this section, we rigorously investigate the relationship between linear ensemble sampling and LinPHE. A generalized version of LimPHE is described in Algorithm 2 Note that the perturbed estimator, 0, = V. (W, + El=l X,(Y, + Z,,)),, resembles the estimator of linear ensemble sampling, which becomes evident when compared with Eq. (5). The main difference that in LinPHE (Algorithm 2). the perturbation sequence is generated independently of the history at every time step, whereas in linear ensemble sampling (Algorithm []) the sequence is not renewed but incremented at each time step. However, we further observe that in linear ensemble sampling, as long as an estimator is not sampled for the arm selection, its perturbation sequence independent of the selected arms and rewards. This implics that the estimator in the ensemble that is selected for the

---

first time is equivalent to the estimator computed by the policy of LinPHE. Specifically, if the j-th estimator is selected for the first time at time step t, then the perturbation values of the estimator, W and (Z,) have had no effect on previous interactions. Therefore, newly sampling them as W ~ Pr and { t.i.d. Pn. as in LinPHE, does not alter future interactions. We conclude that in the case where the ensemble size is greater than or equal to T, linear ensemble sampling becomes equivalent to LinPHE by selecting the estimators in a round robin.
Proposition 2. Linear ensemble sampling (Algorithm) ! with m = and deterministic policy of choosing model, e.g., Jt t for 1,............ ,,..., T, is equivalent LinPHE (Algorithm 2
Proposition Sanrsstttoonshowww shows that LinPHE is special case of linear ensemble sampling and provides insightful consequences in both directions of the equivalence. To our best knowledge, Proposition 2 is the first result to formally demonstrate the relationship between linear ensemble sampling and LinPHE.
Linear ensemble sampling with T models is LinPHE: Since an ensemble of I' models is equivalent to LinPHE which achieves regret bound Od log K), the ensemble size larger than T is not necessary. This implication certainly emphasizes the sub-optimal requirements of the ensemble size in Lu and Van Roy [16], Qin et al. (2I]. Even when K >> T in our problem setting, this equivalence provides the ground for upper bounding the ensemble size by T.
LinPHE is linear ensemble sampling with T models: Conversely, since LinPHE can be regarded as linear ensemble sampling with T models, it is possible to derive a regret bound of LinPHE by following the proof of Theorem [T
We present Corollary [ which states new regret bound of Odd T)) for LinPHE, Note that in this case, the regret bound is independent of K. Corollary 1 (Regret bound of LinPHE). Fix 8 E (0, 1]. Algorithm and R NO, .4) achieves O(dlog T)3/2 (T) cumulative regret with probability at least 38.
2
with À 1, P, NN(a. la)
Discussion of Corollary Kveton et al. [1] provide a ((d T Tlog K) regret bound when the number of arms is finite. Our result is the first to prove that LinPHE achieves a O(d5/2 regret bound that is independent of the number of arms. Hence, we view our overall results a generalization of Kveton et al. [12]. It is widely observed that assuming the size of the arm set to be
K may lead to an interchanging of vd factor with a vlog K factor in the regret bound 44, although attaining such reduction may not always be done a trivial manner [S] 6 Our focus is not merely on proving another regret bound for LinPHE, but rather on highlighting the close relationship between linear ensemble sampling and LinPHE, which, to our knowledge, has been overlooked the literature.
The proof of Corollary follows the proof of Theorem I Note that the latter part of the proof of Theorem focuses on decoupling the dependency between (X,) ) and Z, However, in the case of LinPHE, they are already independent since the perturbation sequence is freshly sampled at every time step, enabling more elegant and concise proof. Especially, it skips the parts that require the number of arms to be finite, for instance the use of Proposition[] [ Corollary Tholds even when the number of arms is infinite. The whole proof is presented in Appendix G
7 Conclusion
We prove that linear ensemble sampling achieves a T(T3/2/T) regret bound, marking the first such result in the frequentist setting and matching the best-known regret bound for randomized algorithms. The required ensemble size scales logarithmically with the time horizon as Q2K log T'). Additionally, we expand our analysis LinPHE, demonstrating that it is a special case of linear ensemble sampling with an ensemble of T models, achieving the same regret bound of D(d3/2/T) While our work focuses on linear bandits, ensemble sampling applications have shown superior performance in more complex settings. This suggests that theoretical extensions beyond the linear setting are worth pursuing, with our results providing important foundation for possibly understanding these extensions. Extending the results to general contextual settings, where the arm set may change over time with potentially non- linear reward functions, represents a promising direction for future work.
10

---

Acknowledgements
This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea governmen((MSIT) (No. 0022RICICIONR 1922R144110300 and RS-2023-00022666) and by AI-Bio Research Grant through Seoul National University.
References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances Neural Information Processing Systems, 24:2312-2322 2320, 2011.
[2] Mare Abeille and Alessandro Lazaric. Linear Thompson Sampling Revisited, In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pages 176-184. PMLR, PMLR, 2017.
[3] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
[4] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127-135. PMLR, 2013.
[5] Peter Auer. Using confidence bounds for exploiaation-exploraiin trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
[6] Sébastien Bubeck, Nicolo Cesa-Bianchi, and Sham M Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference on Learning Theory, pages 41-1. JMLR Workshop and Conference Proceedings, 2012.
[7] Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling, Advances in neural information processing systems, 24, 2011.
[8] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208 214. JMLR Workshop and Conference Proceedings, 2011.
[9] Nima Hamidi and Mohsen Bayati. On frequentist regret of linear thompson sampling. arXiv preprint arXiv:2006. 06790, 2020.
[10] David Janz, Alexander E Litvak, and Csaba Szepesvári. Ensemble sampling for linear bandits: small ensembles suffice. arXiv preprint arXiv:2311.08376 2023.
[11] Branislay Kveton, Csaba Szepesvari, Mohammad Ghavamzadeh, and Craig Boutilier. Perturbed- history exploration in stochastic multi-armed bandits. International Joint Conference on Artifi- cial Intelligence, 2019. htLhsttss://// httppppss/ppp.ssmttiiccooooooolo .rg. (oorruuII::6755650
[12] Branislav Kveton, Csaba Szepesvári, Mohammad Ghavamzadeh, and Craig Boutilier. Perturbed- history exploration in stochastic linear bandits. In Uncertainty in Artificial Intelligence, pages 330-540. PMLR, 2020.
[13] Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. In International Conference Artificial Intelligence and Statistics, pages 2066-2076. PMIR, 2020.
[14] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[15] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of statistics, pages 1302-1338, 2000.
[16] Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. Advances Neural Information Processing Systems, 30, 2017.

---

[17] Xiuyuan Lu, Zheng Wen, and Branislav Kveton. Efficient online recommendation via low-rank ensemble sampling. In Proceedings of the 12th ACM Conference on Recommender Systems, pages 460-464, 2018.
[18] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in Neural Information Processing Systems, 29, 2016.
[19] Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep rein- forcement learning. Advances in Neural Information Processing Systems, 31, 2018.
[20] Ian Osband, Benjamin Van Roy, Daniel Russo, Zheng Wen, et al. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1-62 2019.
[21] Chao Qin, Zheng Wen, Xiuyuan Lu, and Benjamin Van Roy. An analysis of ensemble sampling. Advances Neural Information Processing Systems, 35:21602-21614, 2022.
[22] Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221-1243 2014.
[23] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, lan Osband, Zheng Wen, et al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
[24] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):255-29, 1933.
[25] Runzhe Wan, Haoyu Wei, Branislav Kveton, and Rui Song. Multiplier bootstrap-based ex- ploration. In International Conference on Machine Learning, pages 35444-35490, PMLR, 2023.
[26] Jie Zhou, Botao Hao, Zheng Wen, Jingfei Zhang, and Will Wei Sun. Stochastic low-rank tensor bandits for Association, pages 1-14, 2024.
online decision making, Journal of the American Statistical
[27] Zheqing Zhu and Benjamin Van Roy. Deep exploration for recommendation systems. In Proceedings of the 17th ACM Conference Recommender Systems, pages 963-970, 2023.
12

---

Appendix
A Notations
We summarizes the notations in this paper in Table and Table 3
Table 2: Notations specific this paper
Linear Bandit
X
Set of arms
True parameter vector
x
Optimal arm
X
Chosen time
Y
Observed reward at time / Zero-mean noise time
T
O
SubGaussian variance proxy of f) Dimension of arms and true parameter vector
d
K
Number of arms (if [ < oc)
T
Time horizon
R(T)
Cumulative regret
Algorithm
X
Regularization parameter
V
XLa - X,X; Perturbed estimator
O2
W WW.
Initial perturbation vector
Z ZIA
Reward perturbation
P1
Distribution for initial perturbation W Distribution for reward perturbation Z₁
PR
Ti
Sampling policy at time t
Analysis
8
Probability of failure a((X,)=_)
FX
F
a((n)=))
FA
o-algebra generated by algorithm's internal randomness until time
F.
(FFFFFX U.F'.. o-algebra generated by the first t-iterations of interaction Ridge regression estimator by samples
0
0
Perturbation in the estimator, 0,+1 0
8
Confidence radius of 0₂ Confidence radius 0r
7
Confidence radius of 0g Probability of optimistic arm selection
p
PN
P(Z 2 1) Rv 0.15 where ~ N/O,
3
High probability event Concentration event Optimism event
E,
&
&
Concentration event of 0₂
E
Concentration event of f
E
anti-concentration event of 0,-1 Perturbation vector time
Z.
4.
(VXIa X1 X,) E Rd-t
U.
T V, +
13

---

Table 3: Generic notations
Sets and functions
N
Set of natural numbers, starting from Set of natural numbers up M, i... (1,
[M]
Indicator function
Vector and matrices
E norm of vector
(+)s
i-th element of a vector
0g La Probability
Zero vector in TRd Identity matrix gdxd
F)
Probability space
E
Expectation
N(p, Σ)
Gaussian distribution with mean μ and covariance Σ
Logical conjunction ("and")
Logical disjunction ("or")
B Proof of Theorem 2
Lemma 5 (Lemmas 10 and 11 in Abbasi-Yadkonn et al. M.. Let A 1, {Xx, be any sequence of d-dimensional vectors such that [|Xoll2 S 1 for all E [T), and V2 = AI Ei X,X, Then,
E. |xxll 2d log
As alluded in the discussion of Theorem 2 we utilize Markov's inequality and the random variable of interest is X, 0,1 {E1, n ). However, this random variable may not be non-negative, precluding the use of Markov's inequality. The following lemma shows that adding an appropriate term guarantees its non-negativity.
Lemma Assume the conditions of Theorem
2 Let (() = supaex x T 0, where E Rdd Let
+, = {0 E Rd 110-00 l1v I 7}. Define 0, argmingge, (0) and X, = argmax xf 0,. For any 0 I&d and an event E', we introduce the following notation:
ge (0,E') (J(0) ((, 1(E').
Then, 90 ,E') 2 0 holds for any event E' E F, and y (0r, En) 2 0 holds almost surely for any event such that E" EE
Proof. We first prove g0") 0. Since 0- E Ot.
J(0") 2 inf J(O) J(0,)
always holds. Therefore, for any event 8', (0 E¹) > 0 holds.
We now suppose E" E1, and prove (f,, E") 2 0. We consider two cases where E" does and
does not hold. Under E" since E" C ε1,t and by concentration condition (2), 0 θ, holds almost
surely. Then, J(O,) 2 infage, J(0)= = J(0,) holds. Under g"C (0,, E") = 0 > trivially holds.
Therefore, Si (0,, 8d) holds almost surely.
Proof of Theorem
We show that with probability at least 1 - 5, it holds that
( < 1+ p
2dT log
1+
T dA
2
log
We first bound the instantaneous regret under the event & at time I.
(x - x, 0*) (8} = (x+ x 0, + x, 0, - x, 0-) 1 {8)
(x= 4" x, 0.) 1 18
(x, 0, x, 1
14

---

In is directly bounded under E.
1 X2 (6, 8*) (1 {8}
1 [Xollv |10: 0 1 1 {E}
1 <>1|Xellvee
where the first inequality is due to the Cauchy-Schwarz inequality and the second incquality comes from condition (2). Now, we bound 11. Let XT Oi, and St be defined as in Lemma 6 By Lemma almost surely. Then,
6 ga (f,, E) 2 0 holds
1 x T (E) - X, {E}
00 {8) - x,- (8) + X (, X,
91 (0", .E- - 9t ()),8)
91 (0" 88)
S 91 (0" ,22,)
where the last incquality holds since & C. E,, Again by Lemma 6 (0" E2,) and E n2,,)
are non-negative almost surely. Note that by the first part of condition 3 E2 is Feas-mesurrbble and hence 9t E2,1 (x=T 0" X 00 (Eg,) is also F,- -measurbee.. Applying Markov's inequality conditioned on Fi-1, obtain that
,E2,)) ,2,) S gr (0c, (E2 ( (i-11) S
gr Ei, E2, F (11)
We lower-bound the probability on the left hand side utilizing condition (3). Suppose the event of interest in condition
(3), namely ((x* 0r S X, 0.) &1,e) Eg holds. Under the event, either ES, or (x T < X, 0,) A E1e A E2 holds. Under ES,,, 9e(0", ,2,1) S Se (0,, E,, n E2,x) becomes 0 S O, which trivially holds. Otherwise, we have (x* T I X, 0,) A A E2,e. Under this event, we have that
x² T0 0-
S
X, O2 + T xx--xx-0 X, S Sx, 0, 0,,0-
+ (I- 0- -0-- x,)0, (E21) S (x, - -x 0,) (E1, E2,
+ 90 E2,1) S gl E1, n n22)).
Therefore, we have shown that
(00T 0r (x, v ES, 90 ,2,1) s E0,, n E2x)) which implies
(gi (2,1) S 9: E1, n E2,) | Fi-1) 2 P ((x TT" < X, 8 1 V
VEL, Fi-1)
2p
by condition
3
Therefore, we obtain that (0",",
p E (0.. E1 E2,1 Fi-1] from in-
equality
Lastly, we bound ge E1, E2,)
9t E1, (2,1)
(x 0, x,- 1 (E1, n E
< (x 0, - x, 0,) 1 (E1, n E
X, llv
|10, 8, 1.11vn. llv 1 1{Er,}
(102,- - 8" + +1105 - -00 -111)- 1 {E
X, llv
< 27 | [
where the first inequality uses that x;- = sup x. T 0, the second inequality is due to the Cauchy- Schwarz inequality, the third inequality holds by the triangle incquality, and the last inequality comes
15

---

from condition (2) and that 0, E O as defined in Lemma 6 Combining all, the instantaneous regret time under the event bounded follows:
+ 21 [|xellac |i-1]
1 (8) - >> 11
P
y
27 p
||x.ll==
+
27 (E
[X [r-1] [Xellvz)
p
Then, the cumulative regret under & is bounded
1+ 2 Σ
27
B(T) (8) 5 7
[
Fi-1] - ||
To bound the first sum, we apply the Cauchy-Schweer inequality and then Lemma
Xellv S
T
Xe li
T dx
22T log
1+
The second sum is bounded by Azuma- Hoeff-Hog inequality. Note that 0 < || <
V Amaax (V,=3) [Xell2 s + where Amax(-) (-) denotes the maximum eigenvalue.
By Lemma 12
with probability at least - 8. it holds that
Σ ( (B [F-i]] -1x.lvlx
T
1 8
log
2X
Therefore, with probability at least 1 8, the cumulative regret under & is bounded as follows:
R(T) St 1 (++2 p (1+
T
2T
2dT
log
d)
C Proof of Lemma 2
Proof of Lemma 2
The proof is simple algebra utilizing useful matrix d, Define 4, to be the matrix that stacks X, in addition to an identity matrix as follows:
4 = (VXla X,
X.) E dx((+))
We express relevant matrix and vectors using .,, which are V2 D. V,- i.Z..... and U,T = x- V b. Defining 0,-1 00"1, to be the perturbation in the selected estimator at time we obtain that
x -T = xx -V 1.
U,_ IZ.
In addition, it holds that
11--1112
Tx, V. 2 2 TT, v
= -V
= =|100||
16

---

By X, 0: = su xe x' 8,, it holds that r= 0/ S x, dz. Then, we have that
x, 0, x² 0r 2 x² 0, x² lr x==
xx (0, 8*)
xx* (8.- 81-1-10
-U +x" xT (0--1-00 -0-)
By the condition of the lemma, there exists positive constant such that |10,- - 0-1lv__ and
U c|IU,-1l22 2 By the Cauchy-Schwarz inequality, it holds that
x (0--1 - 0r) 2 - =/ 11,_ 8* ll
2 c 10111112
Therefore,
x, 0, xx 2 U,T,2. Z. - cl1U1-1l2
0,
where we proved that X, 0, 2 Tr.
D Proof of Lemma 3
Proof of Lemma 3 Under = Eτ, n E the concentration condition, specifically condition
in Theorem 2 holds by the triangle inequality.
|10- 0 Il = 110- + 0.-1 - 1' S 1110--11mm. + 1|0.-1 - 0' S 3 S7.
To show the optimism condition, condition 3 in Theorem we first show that Ez E Fi-1- E E Ft-1 holds since it regards ()), only. Since PPU Z, 2 3 (U2~1ll)) A & F(-1) a 1- random variable and &g,r an event that the specified random variable is greater than or equal to p, ε is in Ft-1. Therefore, we obtain that &g, & & Ft-1- To prove the remaining part of condition relationships:
we demonstrate the following logical implication
(UU Z, 2 (0-11( ^ Aε1,)
v VEg,
(U. A E., A E21) VE,, (UUTIZ) / 10 2. A Es, n E VES, (1 Tr sx.0)) A En, A E v VEs,
(T 0 x, 0.) E1,) EC
where the first implication follows from Av B + (AN BV the second implication holds since E2, C E,-1, the third implication holds by Lemma which states that (UI, Z, 2 3 [|,-- ll2 ^
E--1) (x+ 0+ < x 0z), and the last by Et,- Ei,, E This implication relationship shows that
(((x* 0" < X7 0.) E V Ve,. Fi-1) > PP ((UTI 2 B (l- ^ E.i.) VES, Fr-1).
17

---

We bound the right hand side using the definition of E2,
IP 2 2
V Fi-1))
= =FL(((1112222-111111 E1.0) v V } Fr--1
E 21((U112222-1111
_ 10.11 1 1 (82,r + ( Fr-1]
E p1 + ( P.
[I 2 8-1 (,-11b)) (0-1Ib) / Fe-1 1 (82,) + +1 (22,)
where the third equality uses that E E Fi-1 and the first inequality holds since under &2, C E2
(U,T, Ze 2 9 (1)--112) E1,1 Fi-1
2 p holds by the definition of εz,t-
Therefore, EL,; and En satisfy conditions and (3). By Theorem 2 the regret bound stated in
inequality 4 holds with probability at least 1 8 - P(EC), where the union bound is taken. Note that
= -izz (E1. &2,1 = - (51 n E n & C E E. The failure probability is bounded as
8 + P (8C)
< 2 (&C) +P (EC
< 25 P {c
where the first inequality takes the union bound over E C &C U E and the second inequality is due to Lemma
E Proof of Lemma
Lemma[4is a special case of Lemma which generalizes Gaussian distribution to any subGaussian
distribution. We first provide a general chi-squared concentration result, which is required to bound the perturbation induced by W. generalized version Lemma is presented in Lemma TT
Lemma 7. If (0, Ia) a d-dimensional multivariate Gaussian vector, then for any 8 (0. 1].
P
|| 2 Vd + 2oo 8
S 8.
Proof. By Lemma 13 with x = log J. it holds that
1 P |1212 - d 2 2 dlog g + 2 log [
1
S 56.
Since d + 2 dlog 1 + 2 2og
(va+ + 22log } it holds that
+ log :)
|2112 2 Vd / 2
S
|211 2 d d 2 dlog
58.
Proof of Lemma 4 By Lemma 7 with 5/2T instead of 6, yields
P | 2 vxer (va+ v 2log
27
8
5
2T
18

---

since W ~ NN(a A5)Ja). Applying Lemma 9 with 6/2T instead of yields that
T + log
27
27
0 .llll. v S B dlog
+
Br
vd + 2 log
dA
holds with probability at least 1 - 8/T. Note that the right hand side is equal to the definition of YT. defined in Eq. 7
F Rigorous Justification of Proposition I
In this section, we rigorously justify Proposition I that is stated in the proof of Theorem To so, we present a different viewpoint on the perturbation sequences.
Denote the arms as X' {z ..... "3 .x......K For the sake of the analysis, assume that 8/T S PN/2 ...,,," 0.08, which holds whenever 2 14 or < 0.07.
We reconstruct the perturbation sampled by Algorithm ! Assume that in addition to (W*)7_ i.j.
Pn at the beginning. where the subscript (k:, I) enumerates from (1, (K, T). Define Nu.- = -i (x; = x*) to be the number of times arm k has been chosen up to time I. If the a,-th arm, x²', is selected at time 4, then we assign Z = Zi
Pr, Algorithm 1 samples mKT samples of ( i.i.d.
Li, Nu,. Since Z2,, No,, is still an i.i.d. sample of PR conditioned on history,
specifically on oFF UFF (112))) (-)=)) )), we attain an equivalent algorithm with Algorithm We note that these modifications need not be taken the execution of the algorithm, and their purpose (=.))) which reflects the fact that they are sampled in advance. For t [T]. define F,A = a (Fi-1 (jt)),, which indicates that the only additional randomness of the algorithm when choosing 0g is the sampling of je ~ Tt. Define the extended perturbation vector as follows:
purely for the analysis. Define Fzt = o ((W',
3KT ( WS
2
ZKTT)
E Bd+KT
Removing some components and reordering ZxxT yields Zi, where the removal and reordering depend on the sequence of chosen arms, namely a1..... at-1. Note that D'TT ~ (0&+ F la KT). We also define the corresponding extensions of 4, and U,. Define a matrix that has n columns, first of which are copies of v R and the rest are O₂ as follows.
rep(v, a, n) (e
V O₂
0a) E Rd
Define the extended version of 4, as follows:
+ = (VAi
rep(x* NN,,, T)) E dx
L, extends 4, by permuting the columns so that the feature vectors from the same arm appear in consecutive columns, then inserting multiple O₂ appropriately. Then, we have V2 2. and 0, V Z since Zkr is permuted and extended from Z in a similar manner. We define the extended version of U, as U, = (x * V,- TV, @ E Rd+KTT U, is also a permutation U, with additional zeros inserted. It holds that U,T Z = U. UKT and ||U|]| =||U,
Let X be the set of all possible p, Since o, is fully determined by NI...... NK. and each NR. takes value between 0 and T inclusively when
t < T we obtain that | % T For any E (T), take any 4 E X, Note that U,-1 = T ( (
fully determined by p.-1, and 0/-1 (D, 1 - -., Z is determined by Φ.-1 and Z Assuming that p.-1 fixed, U.-1 is also fixed, therefore we can apply Fact and obtain that IP IPU,,_Z > 8r (U,()11))) 2 PN. where the only source of randomness comes from KTT Applying Lemma 4
we obtain that P(10)_1Ilv._ & 5r) 2 21 1- 8/T. Let 1 (c-1) = 1((U, 1Kr 2 3r A [102_1llv; 7. Then, P( = 1) > PN 8/T 2 pN/2. Since the only randomness
on choosing the arm conditioned on Fr comes from sampling jr. it holds that
m
( P ((U,_ Zer 2 3r (1-11 112)) (10 s 2 1
Σ P $
(.-1)
m
j=1
19

---

We apply Zauma-Hoefddie inequality to show that 3 -ー= 1 (.:-1) is bounded below with high probability. Since {1 (P:;-))) are i..d. Bernoulli random variables with the associated probability greater than PN/2 /2, it holds that
m
P
P(
PN 4
m
j=1
P
1
m
(
1 m
Σ
PN
1 m
Σ E
4 2--1) 1)1
m j=1
m j=1
4
m
P
1
P
P
1
PN PN
m
m
P
1
(()
1
Σ
E (
(
PN
m
m
j=l
S
exp
where Lemma
12 is applied at the end. By taking the union bound over -p--+x, Xt,
we obtain that
P cΦ
Σ P
PN
T exp (- pi
4
8
The event E is defined the complement of the event above. The proof is complete.
1 m
E = w wee: e -T-1% X4:
Σ
(
>
pn
m j=1
G Proof of Corollary I
Proof of Corollary 7 Let E and εz, be defined as in Lemma redefine couple notations adapt Algorithm Let
3 with 7 -ir and PN/2. We
T
Z, = WT
Zen
Ze,-1)
IRd++-1
be the perturbation vector at time f, and
1-1 W; + Σ
XiZes
t=1
be the perturbation in the estimator 0, Regarding f.-1 one of 00 in the proof of Theorem we obtain that (
5/T and PU Z. 2 B B 1112)) inequalities and 9 respectively. Moreover, in contrast to the proof of Theorem [ the perturbation vector Z. now independent F.-1. Noting that U,-1 is F 1 F
2 pn hold, analogously to
measurable, it always holds that
P
( Z, 2 1,- E,,, F
PN
2
This proves that ε2, is in fact the whole event. Taking the union bound, we obtain that P(EC) < Dt IP(E))) < By Lemma with probability at least 36, the cumulative regret is bounded by
4) R(T) S 7r 1+ pn/
(1+
T dd
2TT
2T 1 3 =0
2dT log
log
PN
20

---

H
Generalizability of Perturbation Distributions
In this section, we demonstrate that any distribution that is symmetric, subGaussian, and has lower- bounded variance satisfies the results of Lemmaç and Fact I possibly to a constant factor. As mentioned in [ implies that our results are valid when the Gaussian distribution is replaced with any symmetric non-degenerate subGaussian distribution. The following lemma is standard concentration result for vector martingales with subGaussian noises.
Lemma 8 (Theorem 1 in Abbasi- Yadkori et al. [. Let {Fi) be filtration. Let { - be sequence of real-valued random variables such that & is Fe-measurable and is F
a-
subGaussian for some 2 O. Let (X+)i= be sequence - random vectors such that X Fe-i-measurable and |X+l| S
almost surely for all 2 1. Fix X 2 Let Vi X1+ X, X, Then, for any å E (0, 1). with probability at least 5, the following inequality holds for all t 2 0.
L dA
Σ EXX,
S Soy doog
1
+loog 8
Next lemma a simple application of Lemma which proves the concentration result 0g under the subGaussianity of 'RR-
Lemma 9 (Sufficient condition for concentration). Fix any E (0,1) and E [T]. Assume that P (l|W > L(,0) I and {ZiY-z are mutually independent of each other and are F. conditionally o subGaussian respectively for each i E Eit- [tt-1] 1]. Then, with probability at least 1 - 28, holds that
0 00-11l S SoR dlog 1+ dA
+ 2 log
8
VX
Proof. Recall that 0,-1 V +
1-1 X;Zi). Therefore,
| Ve-
Vi-
K
1-1
I| + Σ Xi
1-1
$ Wilv +
X
V
where the triangle inequality used for the last incquality. To bound the first term, we use the fact that Amax (V=l)) I 1. where Amaa(()) denotes the maximum eigenvalue. It implies that ||W]v== S
I L holds with probability least 1 8. The second term bounded by Lemma g With probability 8, it holds that
Wll.. Since F[]] > L S 5 by assumption, ||Wl|y
VX
--
1 g
Σ
X,Z
SoRv dlog 1
+ 2 log
dx
By taking the union bound over the two events, we obtain that
T |m- V.- VX
L.0
1+ + dd
<
- TRy / doog
+ 2
log
holds with probability at least 1 28, which proves the the lemma.
We also provide that the f--norm of the vector W whose components are i.i.d. samples of subGaussian distribution is upper-bounded with high-probability. This lemma, combined with Lemma 9 justifies P, to distribution over Rdd such that each component is i..dd sample of subGaussian distribution.
21

---

Lemma 10. Suppose that W E R and each component of W is sampled ii.d. from a of- subGaussian distribution. Take any 8 (0, 1). Then, with probability 1 6, it holds that
| - oiv 2d + 4 logg g
Proof. Take Xi e.,..., Xa = eg. where (el,.... ed) is the standard basis of R2. By Lemma g with & = (W); and X = 1, it holds that
1
Σ (W) e
S Sorvdloge 2 2 log 8
(21a)-1
with probability at least 8. The proof is completed by noting that || v2 Wll2.
(W) (W)ee
Finally, we demonstrate that subGaussian distribution with lower-bounded variance satisfies the anti- concentration condition analogous to [ We normalize the distribution that it is 1-subGaussian. Lemma 11 (Sufficient condition for anti- coneentneen......). Suppose that P is a real-valued distribution that is symmetric, I I-subGaussian, and has variance at least 1/2. Suppose Z E TR" for some n E N and components are i...d. samples Pf Then, for any fixed E R", it holds that
P
Z
2 3
|ull2
0.01.
Proof. Without loss of generality, we may assume that |/11|2 = 1. Let = u Z. Then, Var(Y) =
Var(Z i (2)) = Ei.( (u)3 Var((Z);) = Var(P) 2 2. On the other hand, we attain an upper
bound of VYr(Y) as follows:
Var(Y) E [
11
+E y²1 < | s 4 + E [Y 1 4y]
E
Y²1 1
Y
3
1 p
MM)
S
1
+ 16P
<
18| s ) + 2 (1 2 4
3
1 + 16P
3 IK1)
+ L [ 43]
(12)
We upper-bound | 2 4}] using its subGaussian property. Note that Y = u Z is 1-
subGaussian since ||u||2 = 1 and the components of Z are independent and I-subGaussian. Applying the standard tail bound of subGaussian random variables, it holds that P ([Y) 2 x) s 2 exx (-x²//2)
or equivalently, PP (Y² N x)
S 2 exp (-x/2). Then, holds that
E y 1r > 16
P ( 1 {Y² 2 > 16) 2x) x) dx
16
P PY (r² 2 16) 2 x) dr +
/
P P (Y² 16) 2x) dr
J16
16P (Y² 2 16) + / P P 2 2) dx
0
S 32c 8 +
2e dr
16
32c 8 + -8 0.0121.
(13)
By plugging in the upper bound of (13) to inequality 12 and reordering the terms, we obtain that
P
0.0121 > 0.023.
16
2
Finally, recall that Z is symmetric, therefore Y is symmetric. Therefore, we have IP (Y 2 1) 0.023 0.01.
22

---

I
Auxiliary Lemmas
Lemma 12 Hooea--n Inequality). Fix a E N. Let (2i) be sequence of real-valued random variables adapted a filtration (Fi) Suppose that there exists < such that Z, E [a, bj holds almost surely for all i E [nl] Then, for any ò E (0, 11, the following inequality holds with probability least 6:
Σ (Z, - (Z F(-1)) S (b -a)y
7 2
log 8
Lemma 13 (Lemma of Laurent and Massart 15
Let Y,,.., Yu be ii.d. standard Gaussian
variables. Set Z = EY= -1). Then, the following inequality holds for any > 0.
P 2 vdx + 2x) se
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We accurately describe the problem we set and the results we obtain in the abstract and introduction, specifically Section
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
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of the work at the end of Section 7
Our work is lim-
ited to the linear bandit setting, while ensemble sampling also exhibit superior performance in complex settings. However, our results provide a necessary stepping stone to expand the theoretical analysis of ensemble sampling to such regimes.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are 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 on 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play 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]
Justification: The full set assumptions is presented in Section 4
The complete and correct
proof is provided throughout Section and the Appendix. All the important ideas provided as sketch in the main paper, if not provided as a whole.
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 or referenced 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 proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA].
Justification:
The paper does not include experiments.
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 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the of a 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) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
25

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA].
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://mips.c/
htaili/cguiiees/oeeeubbiiii cissoniPPccc for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is 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 NeurlPS code and data submission guidelines (https
/ wwtpc//bbbbcguuddeeeeeoooooeeoie /eeeeeeeeeoooddiiiccce
wwwsssssiioooooooo hotpee///ooossbbmsssooooooooo// for more details.
The authors should provide instructions data access and preparation, including how to 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. 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 as 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:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary 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:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the 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, or overall with given experimental conditions).
26

---

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).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
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 errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA].
Justification:
The paper does not include experiments.
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 of compute required for each of the individual experimental runs as 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 failed experiments that didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: There is no societal impact of the work performed.
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 why the paper does not address societal impact.
27

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA].
Justification:
The paper poses no such risks.
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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA].
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does 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 used and, 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 (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 package should be provided. For popular datasets, paperswithcode com/ datatsss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
28

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 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:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl 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. Crowdsoureing 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 details about compensation (if any)?
Answer: [NA].
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
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 as much detail as possible should be included the main paper.
According 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 the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 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.
29


Reviews:
[{"review_id": "r1QxWxCELz", "reviewer": "Reviewer_QBvS", "summary": "An analysis of Ensemble Sampling in the linear setups with closed-form incremental update and finite action set.", "questions": "1. See weakness.\n\n2. Can you provide more in-depth justification of assumption you made in line 270 for the proof of theorem 1. Intuitively, it seems right by sampling these R.V. in the beginning whose randomness are from algorithm side. But it needs rigiours justification.\n- The random variables $\\{W^j\\}$  are sampled independently in the beginning. \n- $J_t$ and $Z_{t}^j$ are independent of the history before step t. \n- However, (1) $(X_s, Y_s)$ depend on $J_t$  for $s \\ge t$.\n- and (2) $(X_s, Y_s)$ depend on $Z_t^j$ for $s > t$.\n\n3. Can you provide empirical evidence to support the scaling on ensemble size? Is it really scaling linearly with size of action set $K$? What is the scaling factor with ambient dimension $d$? **What theory-practice gap are you closing?**", "limitations": "Any implication on scalable posterior sampling in complex setting?", "rating": 3, "confidence": 5, "soundness": 1, "presentation": 3, "contribution": 1, "strengths": "Provide a new analysis of linear Ensemble sampling.", "weaknesses": "1. **Lack of Practical Implications for Ensemble Sampling in Complex Settings:**\n- The paper does not discuss how Ensemble Sampling can be effectively applied in complex, real-world scenarios. Practical considerations and potential challenges are not addressed, which limits the practical utility of the proposed approach.\n\n2. **Over-Claims:**\n- The authors claim to close the gap between theory and practice by providing an improved regret bound for linear ensemble sampling. However, they do not clearly define this gap. The paper lacks simulations or rigorous arguments to support the existence or closure of this gap. For instance, the paper does not present practical scenarios or empirical results that highlight the gap.\n\n3. **Incorrect Claims:**\nThe authors incorrectly claim that their work matches the state-of-the-art results for randomized linear bandit algorithms. Specifically:\n- The best-known regret bound for exact Thompson Sampling (TS) in a finite-arm (K actions) setting is $O(d \\sqrt{T \\log K \\log T})$ [1].\n- The paper proves a regret bound for linear Ensemble Sampling of $O((d \\log T )^{3/2} \\sqrt{T})$.\n- This bound does not match the state-of-the-art results or even the exact TS bound.\n- Additionally, exact TS is not the state-of-the-art for randomized linear bandit algorithms in terms of regret bound.\n- **The authors' claim that their result matches state-of-the-art randomized linear bandit algorithms is incorrect** as their bound does not even match the exact TS. \n\n[1] Agrawal, S., & Goyal, N. (2013, May). Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning (pp. 127-135). PMLR.\n\n4. **Mischaracterization of Perturbed History Exploration (PHE):**\n- In linear Ensemble sampling, $J_t$ sampled from uniform distribution.\n- Perturbed history exploration can be viewed as deterministic choosing $T$ different ensemble models with entirely independent set of perturbed noise one by one. This observation is **not** new.\n- Perturbed history exploration is not a special case of the linear ensemble sampling algorithm as one is a deterministic algorithm and the other is randomized algorithm.\n- Therefore, it is **not** valid to use the result from LinPHE to claim that \"linear Ensemble sampling use $\\min (K \\log T, T )$ ensembles, allowing the number of arms to be infinite\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the time and effort you have invested in evaluating our work. However, we believe there are several fundamental misunderstandings in your review that we would like to address.\n\n**The theory-practice gap:**\nVariants of ensemble sampling have already been shown to perform effectively in practice, such as in online recommendation [16,24,23] and deep reinforcement learning [17,18,19]. However, the theoretical understanding of ensemble sampling has been lagging behind, even for the linear bandit problem, as recognized by previous theoretical works.\n- Lu and Van Roy [15] attempted to provide a regret analysis of ensemble sampling but admitted to an **erroneous analysis** that invalidates their results (see [15](https://arxiv.org/pdf/1705.07347)).\n- Qin et al. [20] analyzed the Bayesian regret, a weaker notion of regret than the frequentist regret analyzed in this work. More importantly, their result requires that the **ensemble size be linear in $T$**, which is highly prohibitive in practice.\n- Janz et al. [8] showed that the ensemble size only scales logarithmically with $T$, an improvement over [20] on the requirement for the ensemble size. However, their regret bound is unsatisfactory $\\mathcal{O}(d^{5/2}\\sqrt{T})$ with an **additional $d$ dependence** compared to linear Thompson Sampling [2,3], and a **super-linear dependence on the ensemble size $m$ in the regret bound**. That is, their result is not only loose but also very counterintuitive (the larger the ensemble size, the worse the performance, which questions the motivation of ensemble sampling).\n\nTo summarize, there was no frequentist (worst-case) regret bound matching that of other comparable linear TS (or LinPHE) with the number of ensembles not scaling linearly with $T$. **Despite previous attempts, there has been a significant gap**. Our work aims to close this gap by demonstrating the **first non-vacuous theoretical guarantee** of linear ensemble sampling whose **regret bound matches that of LinTS for the first time** and ensemble size is still **logarithmic in $T$**, **without any performance degradation as the ensemble size grows**. We provide this tighter regret bound through new analysis and with an even simpler algorithm than that of Janz et al. [8].\n\n---\n**Correct Claim:**\nIt is crucial to acknowledge that both $\\tilde{\\mathcal{O}}(d^{3/2}\\sqrt{T})$ and $\\tilde{\\mathcal{O}}(d\\sqrt{T \\log K})$ bounds are well-established in the finite-arm setting [3], and neither is inherently superior.\n- **FACT**: $\\tilde{\\mathcal{O}}(d^{3/2}\\sqrt{T})$ is a valid best-known upper bound of LinTS [2,3], even for the finite-arm setting. \n\nFor instance, when $d=2$ and $K=8$, $\\tilde{\\mathcal{O}}(d^{3/2}\\sqrt{T})$ is clearly smaller than $\\tilde{\\mathcal{O}}(d \\sqrt{T \\log K})$ for any $T$.\n\nExperts in the bandit literature agree that $\\mathcal{O}(d^{3/2}\\sqrt{T})$ (for the $K$-independent bound—here \"$K$-independent\" indicates that the regret is independent of $K$, not implying an infinite arm setting) is the best bound for TS-type (not UCB-type or hybrid with UCB) algorithms in linear bandits. Thus, **we respectfully disagree with the assertion that our regret bound is worse than Thompson Sampling**.\nWe sincerely hope that the reviewer and we can agree on this well-accepted fact within the community. **Our regret bound for linear ensemble sampling matches that of LinTS for the first time**, marking a significant contribution to the field.\n\n---\n**Relationship between ensemble sampling and LinPHE:**\nAlthough previous studies of ensemble sampling have fixed the ensemble sampling distribution to be merely uniform, it turns out that **uniform distribution is not necessary**.\n-  **FACT**: The sampling distribution in ensemble sampling does not have to be uniform.\n\n For instance, even if some models' probabilities are increased by a constant factor (and others' decreased), both our analyses and previous work remain valid, achieving the same order of regret bounds.\n  \n**To our best knowledge, the relationship between perturbed history exploration (PHE) and ensemble sampling has not been rigorously discussed on either side**. If you could provide any references revealing the relationship between ensemble sampling and LinPHE as argued in your review, we would appreciate it.\n\nAs mentioned earlier, uniform sampling is not a necessary characteristic of ensemble sampling. Therefore, we take a broader perspective of linear ensemble sampling (Algorithm 1) to include any sampling policy, rather than restricting it to a uniform distribution. This generalization reveals a significant connection between LinPHE and ensemble sampling, allowing us to use ensemble sampling analysis techniques to derive a new regret bound for LinPHE.\n\nMost importantly, our Corollary 1 does **not** \"use the result from LinPHE to claim\" anything. On the contrary, we apply our analysis framework for linear ensemble sampling **to** analyze LinPHE, deriving a new regret bound. With the generalized algorithm, Proposition 1 and Corollary 1 together imply that an ensemble size greater than $T$ is superfluous, as a round-robin selection of the ensemble models guarantees the same regret bound as Theorem 1.\n\nThis result opens up new possibilities for ensemble sampling to adopt alternate sampling policies, demonstrating that policies other than uniform sampling can also achieve strong guarantees. This expansion should not be viewed as a weakness of our work; rather, it should be recognized as a significant contribution. Even if the reviewer were to restrictively define ensemble sampling to be associated with uniform distribution only (contrary to the evidence above), the fact that we can apply our novel regret analysis framework to derive a new and unified analysis of both LinPHE and ensemble sampling (two \"different randomized algorithm classes\" as one wishes to believe) would be even more interesting. Regardless, this new result will be of independent interest to 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": "0T32MY7JKm", "reviewer": "Reviewer_QJqu", "summary": "This paper proposes a neater version of linear ensemble sampling and streamlines the analysis of OFUL-inspired algorithms for linear bandits. The authors proved that this version of linear ensemble sampling has its high-probability regret upper bound the same order as LinTS, i.e., $\\tilde{O}(d^{3/2}\\sqrt{T})$ so long as the ensemble size is at least linear in $K$ (the cardinality of the arm set) and logarithmic in $T$. Their analysis introduces a lightweight way for the community to deal with the dependency between the sequence of perturbations and the sequences of selected arms while preserving a sublinear ensemble size. This paper also tries to subsume linear perturbed-history exploration under the streamlined analysis framework.", "questions": "1. The ensemble size $m$ in Theorem 1 depends on $T$, which seemingly makes the algorithm inherently incompatible with double-trick-style techniques and thus less practical, right?\n2. See the second point in the Weaknesses section.", "limitations": "See Weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed algorithm is the first to achieve the same statistical performance as LinTS up to logarithmic factors.\n2. The proposed analysis framework in Theorem 2 identifies key components in OFUL-inspired algorithms, which is of broader interest to the community of online learning.\n3. The reformulations (of Algorithm 1) made in the analysis are insightful and easy to follow, especially the reindexed viewpoint of the sequence of selected arms in the proof of Claim 1.", "weaknesses": "1. The presentation in Section 6 is very confusing. As far as I can tell, Theorem 1 requires the ensemble size to be at least linear in $K$, and the justification of Claim 1 in the proof of Theorem 1 relies on $K \\leq \\infty$ at least superficially. However, the authors claim that, Corollary 1, as a corollary of Theorem 1, can implies a regret bound for LinPHE \"under the infinite arm setting\" in Line 349 and even in the Abstract. It could be highly possible that both Theorem 1 and Corollary 1 are correct, but the authors should clarify the relationship between the two results further. I am willing to reconsider my evaluation if the authors can provide a more detailed and satisfactory explanation.\n2. Though this paper is mathematically significant, it is not rigorously clear why should we prefer linear ensemble sampling over LinTS if we focus on the linear bandits setting (instead of more complex models like neural networks). For example, the authors mention that it might be intractable to compute the posterior of LinTS and Theorem 1 should be applicable to perturbations following \"any symmetric non-degenerate subGaussian distribution\"; then mathematically speaking, linear ensemble sampling should be preferred over LinTS **only if** there does exist a symmetric non-degenerate subGaussian distribution (serving as the perturbation in linear ensemble sampling) whose counterpart in LinTS has an intractable posterior. However, the authors do not provide any concrete examples or discussions on this point. I am willing to reconsider my evaluation if the authors can provide a more detailed and satisfactory explanation.\n3. Line 244: There seems to be certain typo in the indices range for $\\eta_t$.\n4. The presentation between Line 527 and Line 528 is inconsistent with the definition of $N_{k,t}$. (Back to front)\n5. Minor typo in Line 240: \"lienar\" -> \"linear\". \n6. Minor typo between Line 480 and Line 481: $\\beta_t$ -> $\\beta_{t-1}$.\n7. Minor typo in the proof of Lemma 4: $\\sqrt{d} + \\sqrt{...}$ -> $\\sqrt{d} + \\sqrt{2} \\cdot \\sqrt{...}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your overall positive feedback and particularly recognizing the theoretical value of our work. We strongly and sincerely believe that the first two points you mentioned as weaknesses are not weaknesses. We sincerely hope you take our response into account in reassessing our work.\n\n---\n### **Corollary 1 and Theorem 1**\n\nAlthough Theorem 1 shows that an ensemble size of $\\mathcal{O}(K \\log T)$ is sufficient to guarantee an $\\mathcal{O}(\\sqrt{T})$ regret bound, it does not state that an ensemble size smaller than $\\mathcal{O}(K \\log T)$ must fail. This is a sufficient condition, not a necessary one. \n\nPlease note that Corollary 1 derives a regret bound for LinPHE that is independent of the number of arms. What Corollary 1 highlights is that an ensemble of size $T$ with a round-robin selection rule is also sufficient to attain the same regret bound, following the same logic as Theorem 1. We strongly believe this is a novel finding.\n\nThe proof of Corollary 1 follows the analysis framework of Theorem 1 but skips the latter part, including the use of Claim 1. This adjustment makes it applicable to the infinite arm setting for LinPHE (or the arm-independent regret bound of LinPHE even for the finite arm setting). The latter part of the proof in Theorem 1, particularly Claim 1, focuses on decoupling the dependency between the sequence of selected arms and perturbations, which are already independent in the case of LinPHE.\n\nWe refer to the discussion in Corollary 1, especially the last few sentences. Appendix G, where we present a concise proof of Corollary 1 and provide additional discussion, should also help resolve your concerns. We are more than happy to include a more detailed discussion about this point.\n\n\n---\n### **Ensemble Sampling and LinTS**\n\nFirst of all, thank you for acknowledging the mathematical significance of our work. Regarding your question on whether one should prefer ensemble sampling over LinTS, let's review what was known prior to our work, which we believe the reviewer is well aware of.\n\n- **Lu and Van Roy [15]** attempted to provide a regret analysis of ensemble sampling but admitted to an **erroneous analysis**, invalidating their results.\n- **Qin et al. [20]** analyzed the Bayesian regret, a weaker notion of regret than the frequentist regret analyzed in our work. Moreover, their result required the **ensemble size to be linear in $T$**, which is highly prohibitive in practice.\n- **Janz et al. [8]** showed that the ensemble size only scales logarithmically with $T$, an improvement over Qin et al. [20]. However, their regret bound is $\\mathcal{O}(d^{5/2}\\sqrt{T})$, with an **additional $d$ dependence** compared to linear Thompson Sampling [2, 3], and a **super-linear dependence on the ensemble size $m$**. This result is not only loose but also counter-intuitive (the larger the ensemble size, the worse the performance, raising the question of why to use ensemble sampling).\n\n**Prior to our work:** Hence, if you had asked the same question prior to our work, the answer would have been: there is no theoretical evidence that ensemble sampling can perform on the same level as LinTS in the worst case, as the worst-case regret guarantees [8] were worse than those of LinTS. Furthermore, the previously proposed algorithm's algorithmic complexity and super-linear dependence on the ensemble size $m$ in the regret bound made the use of a larger ensemble size impractical.\n\n**Our work:** Our work provides the first theoretical evidence that, even in the worst case, ensemble sampling can be a viable alternative to LinTS, matching the same regret bound of $\\mathcal{O}(d^{3/2}\\sqrt{T})$ (with no dependence on $m$ in the regret bound at all) for the first time.\n\nPlease note that, as mentioned in the paper, ensemble sampling has already been used in practice and exhibits competitive performance in complex settings [16, 17, 18, 19, 23, 24]. However, the theoretical study of its statistical behavior has been lagging behind, not even in the linear bandit setting [15, 20, 8]. As the linear bandit problem serves as a foundational framework for many other problems, an improved analysis of linear ensemble sampling is absolutely necessary, particularly because existing studies have shown clearly inferior results compared to LinTS either in the regret bounds or in the requirements for ensemble size.\n\nRegarding the \"intractable posterior\", our statement refers to more \"complex problems\" (we did not mention LinTS is intractable in the linear model assumption). What is important is that TS in more general and complex problem settings is much more difficult to implement, whereas ensemble sampling is easily generalizable to more complex problems.\n\n---\n### **[W3-7] Minor Typos**\nWe appreciate your thorough inspection of the manuscript. We will make edits incorporating your feedback.\n\n\n\n---\n### **Answer to Question: Double-trick?**\n\nOne can apply the doubling trick by restarting the algorithm with doubling periods, each time with a larger ensemble. The regret bound we obtained should still be valid when the doubling trick is employed, possibly with some larger constant factors, but the main order should remain the same. \nOf course, as you are well aware, the doubling trick has its own drawbacks, but these apply to the previous algorithm in Janz et al. [8] as well. This is not a particular issue with our algorithm.", "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": "KOQ1MWfkJ7", "reviewer": "Reviewer_TPGY", "summary": "The paper explores ensemble sampling for linear bandit problems and enhances the existing regret bounds by a factor of $d$, aligning the scaling with respect to $d$ to that of Thompson sampling algorithms. The algorithm is somewhat simpler than the existing work [8] by permitting any policy for selecting the estimator, and without requiring the symmetry needed in [8].", "questions": "Could the authors please comment on the scaling of the ensemble size with $K$? Is it appropriate to compare your results with those presented in [8]? Is a small $K$ crucial for obtaining the improved results? Additionally, what implications would there be in continuous domains or in general where $K$ is large?", "limitations": "Yes, some limitations are discussed in Appendix K.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper improves the existing regret bounds for ensemble sampling by a factor of $d$. \n\nThe analytical details are effectively presented, supplemented by several insightful remarks.", "weaknesses": "The scaling of the ensemble size with $K$ presents some issues. Utilizing a discretization argument over a continuous domain with a fine grid, where the distance between points is $O(1/\\sqrt{T})$ — to preserve the regret bound, results in $K=O(T^{d/2})$ arms. This is polynomial in $T$ and exponential in $d$. Assuming a finite, small number of arms could be crucial for achieving the improved results. Therefore, it might not be fair to directly compare these results with those in [8], which seems applicable to continuous domains with many arms\n\nThe abstract is challenging to read and understand because terms like 'K' and 'LinPHE' are used without prior introduction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your overall positive feedback and particularly recognizing the theoretical value of our work. We sincerely hope you take our response into account in reassessing our work.\n\n---\n### **Scaling of $K$**\n\nWe respectfully believe there is a misunderstanding in your comment. We are more than happy to clarify any confusion.\nWe emphasize that **our regret bound does NOT depend on the number of arms $K$ at all, even logarithmically**. More crucially, **our regret does not have any dependence on the ensemble size $m$ at all (not even logarithmic)**. We do not assume the number of arms to be small, as long as it is finite (which is only needed for the ensemble size requirement). Even for instances with $K = O(T^{d/2})$ arms as you mention, our improved regret bound remains valid with the same order.\n\nAssuming you understand the key statistical efficiency (regret guarantees) independent of $K$ or $m$, which is our main focus, let us compare our result with Janz et al. [8].\n\nThe ensemble size shown as sufficient by Janz et al. [8] was $\\Omega(d \\log T)$ to derive the unfavorable $\\tilde{O}(d^{5/2} \\sqrt{T})$. Their regret bound depends super-linearly on the ensemble size $m$ (see Remark 3), which is counter-intuitive. Sure, Janz et al. [8]'s proposed ensemble size does not scale with $K$ (but still scales with the dimensionality $d$ which is a contrast with ours). However, what does it get you? Only a very sub-optimal and counter-intuitive result despite a more complicated algorithm with symmetrization. Furthermore, consider when $d$ is higher—the situation gets even worse, both for the ensemble size and especially the regret bound with much worse super linear dependence $O(d^{5/2})$.\n\nOn the other hand, we present a new way of treating ensembles with $\\Omega(K \\log T)$ (using novel analysis techniques) and achieve $\\tilde{O}(d^{3/2} \\sqrt{T})$, matching the worst-case regret of LinTS for the first time! We propose a simple algorithmic approach (with a new way of looking at the ensemble) and significantly novel analysis (compared to [8]) to improve the regret of ensemble sampling. Therefore, it is absolutely appropriate to compare our results with those in [8].\n\nWe believe we should welcome any new way of implementing ensemble sampling if it can provide improved regret guarantees.\n\n---\nThank you for your feedback on the abstract. We will make the necessary edits in the final version.", "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": "ZNPEQtBtbp", "reviewer": "Reviewer_vWv8", "summary": "This paper proposes a simple ensemble sampling (ES) approach and its frequentist analysis for the linear bandit problem. Specifically, it shows that the proposed algorithm achieves $\\tilde{O}(d^{3/2}\\sqrt{T})$ regret when the ensemble size $m$ is $\\Omega(K \\log T)$. This regret bound improves the dependency on $d$ and the ensemble size compared to existing regret bounds for ES. In the regret analysis, it proposes a framework that can comprehensively handle various algorithms and a novel analytical technique to ensure the optimism of ES. It also shows that linear perturbed-history exploration (LinPHE) is a special case of ES.", "questions": "While I do not verify all the proofs in detail, I believe this paper is deserving of acceptance.\n\n### Questions\n- In my understanding, applying the theoretical analysis in this paper to linear contextual bandits is challenging due to the difficulty in extending Lemma 2, making it hard to derive the regret bound for ES. Is my understanding correct?\n\n### Minor comments\n- Algorithm 2: $Z_{t.1}$ -> $Z_{t,1}$", "limitations": "The authors discuss the limitations of this paper in Appendix K.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper proposes a simple ES, demonstrating that the proposed algorithm achieves $\\tilde{O}(d^{3/2}\\sqrt{T})$ regret when the ensemble size $m$ is $\\Omega(K \\log T)$.\n  - This regret bound improves the dependency on $d$ compared to existing work.\n  - Furthermore, this bound matches the regret bound achieved by the Thompson sampling.\n- This paper proposes a new analytical framework that can uniformly handle algorithms like ES, LinPHE, LinUCB, and LinTS (Theorem 2).\n- This paper introduces a novel theoretical analysis to ensure the optimism of ES (Lemma 2).\n- This paper shows for the first time the theoretical connection that LinPHE is a special case of ES.\n- This paper provides a detailed and comprehensive comparison with existing work.", "weaknesses": "- The theoretical analysis in this paper does not derive the regret upper bound for ensemble sampling in linear contextual bandits.\n  - Additionally, the reason for this is not discussed in detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your positive feedback and particularly recognizing the theoretical value of our work. We are more than happy to address any questions.\n\n**Linear Contextual Bandits:**\nPlease note that none of the existing linear ensemble sampling literature [15, 20, 8] has discussed linear contextual bandits with changing context in each round, if that is what you mean. Additionally, many linear bandit papers, such as [1, 3, 11], do not separately address the contextual case, even though their analyses are applicable to contextual cases. Therefore, we first addressed on the problem setting that the previous ensemble sampling literature has focused on — linear bandit.\nYour comment about Lemma 2 is correct, as it would not be directly applicable when the arm set, specifically the optimal arm, is given adversarially. Techniques in our work are developed to derive a sharper regret bound for linear bandits. It would be an interesting future direction to derive regret for the contextual setting. We will include a discussion on this. Thank you for pointing it out.", "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:
Although our main contribution is providing a tighter regret bound for linear ensemble sampling, we have performed experiments as per Reviewer QBvS's request. The results are shown in the attachment.

We strongly believe that our work should be evaluated on its theoretical merit. Our improved regret bound for ensemble sampling matches LinTS for the first time, and our novel analysis should be sufficient for recognition. Furthermore, our regret analysis framework can be generalized to analyze other randomized algorithms such as LinPHE (and derive new regret bounds), which is always a plus, regardless of one's view on LinPHE and ensemble sampling.

Meta-review: This paper makes a significant progress towards emsemble sampling, which is a generic strategy that can be instantiated for any hypothesis class (with minor adjustments). Obtaining a improved frequentists regret and showing that the ensemble size is tilde O(1) is quite an advancement from the existing result. This is in particular meaningful since the prior art by Janz et al. takes a variation of Ensemble sampling that is, depending on interpretation, closer to Thompson sampling than Ensemble sampling.

Please try to improve the quality of the manuscript by incorporating comments from the reviewers (I also recommend adding the nice table of comparison the authors provided during the rebuttal).
Decision: Accept (poster)