An Analysis of Ensemble Sampling
Authors: Chao Qin
Zheng Wen
Xiuyuan Lu
Benjamin Van Roy
Venue: NeurIPS 2022 Accept (2022)
Keywords: Ensemble sampling
Thompson sampling
bandit
information theory

Abstract: Ensemble sampling serves as a practical approximation to Thompson sampling when maintaining an exact posterior distribution over model parameters is computationally intractable. In this paper, we establish a regret bound that ensures desirable behavior when ensemble sampling is applied to the linear bandit problem. This represents the first rigorous regret analysis of ensemble sampling and is made possible by leveraging information-theoretic concepts and novel analytic techniques that may prove useful beyond the scope of this paper.

An Analysis of Ensemble Sampling
Chao Qin Columbia University cqin228gab.comm col.ubia...leeeeeccoccm. edu
Zheng Wen Xiuyuan Lu Benjamin Van Roy DeepMind
{zhengwen, 1xlu, bew..
Abstract
Ensemble sampling serves as a practical approximation to Thompson sampling when maintaining an exact posterior distribution model parameters is com- putationally intractable. In this paper, we establish a regret bound that ensures desirable behavior when ensemble sampling is applied to the linear bandit prob- lem. This represents the first rigorous regret analysis of ensemble sampling and is made possible by leveraging information-theoreii concepts and novel analytic techniques that may prove useful beyond the scope of this paper.
Introduction
Thompson sampling (TS) a popular heuristic for balancing between exploration and exploitation in bandit learning. In its basic form, TS maintains posterior distribution over model parameters. When the prior distribution and likelihood function exhibit conjugacy properties, the posterior distribution can be maintained through computationally tractable Bayesian inference. However, many practical contexts call for more complex models for which exact Bayesian inference becomes computationally intractable. For such contexts, ensemble sampling (ES) can serve practical approximation to TS [Lu and Van Roy 2017].
Instead of the posterior distribution, ES maintains ensemble of statistically plausible models that can be updated an efficient incremental manner. The corresponding discrete distribution represents an approximation to the posterior distribution. At the start of each timestep, model is sampled uniformly from the ensemble and an action selected to optimize expected reward with respect to the sampled model. Each model is initially sampled from the prior distribution and evolves through an updating process that adapts to observations and random perturbations.
While a growing literature [Osband et al. 2016 Russo et al. 2018 Osband et al., 2018 Lu et al.
2018 Oshand et al. 2019 Dwaracherla et al. 2020 Osband et 2022] presents applications of ES, there has been no rigorous theory that ensures desirable behavior similar to that enjoyed by TS.
regret bound for ES applied to Enear-Gaussian bandits is provided by [u and Van Roy [2017] but a flaw in the associated analysis has brought this result into question. Since the publication of that paper, several researchers have tried to remedy the analysis or otherwise establish performance guarantees for ES, but these efforts have gone without success.
We offer in this paper the first rigorous regret analysis of ES. Like Lu and Van Roy [017], we study ES applied to We establish a Bayesian regret bound (Theorem [T] that consists of two terms. The first term is identical to a Bayesian regret bound established for TS. The second term accounts for posterior mismatch and can be made arbitrarily small by increasing the ensemble size. Our analysis leverages information-theoretic concepts and novel analytic techniques that may prove useful beyond the scope of this paper.
bandits. This serves as a simple sanity check for the approach.
As stepping stone in our analysis. we establish a general Bayesian regret bound that applies to any learning algorithm for linear bandits (Theorem 2). In particular, this regret bound is based on the Hellinger distance between the action-selection distribution specified by the learning algorithm and
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the posterior distribution of the optimal action at each timestep. We believe that this regret bound of independent interest and might be useful in analyzing other learning algorithms, such as other approximate TS algorithms.
Note that for Thear-Gaussing bandits considered in this paper, Kalman filtering offers tractable means to exact inference and, as such, an approximation method like ES is not required. However, it is worth mentioning that the analysis in this paper also offers insight into more complex models that call for approximate inference. For example, consider neural network with very wide hidden layers. A recent research thrust (e.g., Dacot al.) [2018] Lee et al. (017)) highlights that, under suitable technical conditions, training such neural network via stochastic gradient descent (SGD) approximates Gaussian process inference. Our result extends directly to finite-armed Gaussian process bandits. This suggests that ES applied with neural networks that are trained via SGD can be effective in complex bandit problems, though formalizing this extension requires significant technical work, which we leave for future research.
The remainder of this paper is organized as follows: Section 2 reviews related work, and Section formulates the considered linear bandit problem and describes the ensemble sampling algorithm. Section presents the main result of this paper: a Bayesian regret bound for ES applied to linear bandits. Before diving into the analysis, we define some notation used in this paper in Section 5 Then we motivate and derive a general regret bound in Section 6 and apply it to analyzing ES in Section 7 Finally, we conclude the paper and discuss future directions in Section g
Related work
Thompson sampling [Thompson 1933, Chapelle and Li 2011 Russo et al. [2018) is a commonly used heuristic for balancing exploration and exploitation in bandits Lattimore and Szepesvári 2020 and reinforcement learning (Sutton and Barto 2018). However, the basic form of Thompson sampling can be computationally intractable unless the prior distribution and likelihood function exhibit conjugacy properties. To overcome this computational challenge, variants of approximate versions of TS have been developed (see Chapter of Russo et al.] (2088). including approximate TS using Laplace approximation [Chapelle and Li, 2011]. bootstrapping [Eckles and Kaptein 2019 Kveton al.] 2019]. variational inference Urteaga and Wiggins, 2018 Yu et al. [2020]. Markov chain Monte Carlo
[Casella and George, 1992 Roberts and Tweedie, 1996 hypermodels [Dwaracherla et al., 2020
and optimal transport Zhhng et al. 2019].
Ensemble sampling is an approximate version of Thompson sampling, formally proposed by Lu and Van Roy (2017). It has been one of the most popular methods in approximate Bayesian inference and has wide applications in sequential decision making. For example, variations of ES have been applied to (deep) reinforcement learning (Osband et al. 2016 2018 2019]. online recommendation (Lu et al.
2018 Hao al. 2020 Zhu and Van Roy 202 multi-agent reinforcement learning (Dimakopoulon
and Van Roy| 2018). behavioral sciences Eckles and Kaptein 2019). and marketing strategies (Yang
al. 2020 Recently, Osband et al.] [2022] has developed a testbed to compare and rank agents
designed for uncertainty modeling, including variants of ensemble agents.
A lot of work has attempted to analyze ensemble sampling, but none of them has been successful. In their original paper, Lu and Van Roy (2017) try to analyze ES in linear- Gaussian bandits, but there is mistake in the final step of the analysis where they compare the regret of ES to that of TS. In particular, in the proof of Lemma 8, the hypothetical actions selected by TS are defined on the histories of ES, instead of TS. Therefore, the cumulative regret incurred by these hypothetical TS actions is not equal to the cumulative regret of applying TS throughout all timesteps, while the paper incorrectly claims that they are equal.
In addition to Lu and Van Roy [2017]. Phan et al. 2019) aims to analyze general approximate TS with approximation errors measured in a-divergence for K Kaamedd bandit. To demonstrate the main result, [Phan et al. [209)] uses ES as an example, but also inherits the technical flaw in Lu and Van Roy [2017] In addition, though |haa et al. [2019] shows that the approximate version of TS with uniform sampling achieves sublinear regret, this result mainly benefits from this forced exploration.
There are also papers aiming to analyze bandit algorithms with approximate inference. A recent paper (Fuang et al.] 2022] studies an upper-confiddenceboune (UCB) type algorithm for bandit problems with approximate inference. Another recent paper [Ash et al. 2021] proposes and analyzes

---

an ensemble based UCB algorithm for bandit problems. Kveton et al. [2020] studies linear bandits in
the frequentist setting and provides general regret bound that tallored analyzing randomized algorithms with good concentration and anti-concentration properties, but it could not be directly applied to analyzing ES due to ES's discrete and incremental update nature.
3 Preliminaries
We begin by introducing a formulation of the linear bandit and ensemble sampling algorithm suited for this environment.
3.1 Linear bandit
The linear bandit [Abbasi- Yadkori et al. 2011 Lattimore and Szepesvári 2020] has received much attention in the bandit learning literature. serves as a simple didactic environment, often used to sanity-check agent designs. In this spirit, we will analyze ES as applied to the linear bandit.
We consider the linear bandit with Gaussian prior distribution and likelihood function. An instance is characterized by tuple& & = (A, No. o²), where A C IR is a finite action set, f40 and En are the prior mean vector and covariance matrix, and a² is the noise variance. Let K |AA denote the cardinality of the action set. Note that actions are vectors of dimension d. The prior distribution over the unknown coefficient vector Rdd P(0 -). multivariate Gaussian N (o) Rewards are generated by a random sequence (R, t = 1,2,...) of K -ddimensional vectors, which is i.i.d. conditioned on In particular, for 1,2 ...
Ra, a 0 Wi, Va E A.
where W₁ (Wr,))eEA is a K X-dimensional vector with each element distributed as N (N0,
An agent interacts with the linear bandit as follows: at timestep 0, 1...., the agent executes action A,; then it observes a reward R4+1,A, Note that only the reward associated with the executed action A, is observed through what is termed bandit feedback. The agent's experience through timestep is encoded by a history H, = (Ap, maximize expected reward over some duration T:
At-1, Re,A ). The agent's 'ss objective is to
T-1
E [Re41,..]
t=
This is equivalent to minimizing the Bayesian regret:
Regret(T) Σ L=0
E[RLLAA R441A.
where A, unif {arg m a TO. The expectations in both equations integrate over random reward realizations, algorithmic randomness, and the coefficient vector Note that A, random since it depends random 0 and the uniform sampling among maximizers (which breaks ties).
3.2 Ensemble sampling
In the absence of conjugacy properties that enable efficient Bayesian inference, TS in its exact form becomes computationally infeasible. ES serves as practical approximation to TS [Lu and Van Roy 2017). often suitable for such contexts. The key idea behind ES to maintain an ensemble of statistically plausible models that can be updated in an efficient incremental manner and to treat the discrete distribution represented by this ensemble of models as an approximation the posterior distribution. The algorithm begins by sampling M models from the prior distribution, where M is hyperparameter. At the start of each timestep, model is sampled uniformly from the ensemble and an action is selected to optimize the immediate expected reward with respect to the sampled model. Then, each model is updated incrementally based on the observed reward and random perturbation. Algorithm presents the associated pscudo-code for ES.

---

Algorithm Ensemble Sampling
1: Input: M and P(0 E
2: Sample: 0........ 0.. E)
3: for t= 0, 1,..... do
4: Sample: my unif {1.... I......M M
5: Execute: A unif
arg max a me, aEA
6: Observe: RE+LAA,
7: Update: ft.m - 01+1.
Vm [M]
8: end for
For Gaussian prior N (Uo, Mo). by conjugacy, the posterior distribution is also Gaussian with covari- ance matrix and mean vector updated as follows,
E, Me RI-LA: A1)
Σx+1 E 02 A.A
and Me+1 = Ex+1
(1)
While this highlights conjugacy properties of sort that allow for efficient Bayesian inference and thus tractable implementation cxact TS, the linear bandit with a Gaussian prior distribution and likelihood function
useful context for studying the behavior of ES in relation to TS. Like [Lu and Van Roy 2017], we consider a version of ES that updates each m-th model according to
0.11m E1+1 1g f0. R1+1.A. + W W141m A
(2)
where W441 (Wi+1,))eet is M-dimensional vector with each element distributed as N(0, of) and [M] = f1....,M0 M).
4 A regret bound for ensemble sampling
In this section, we establish the following regret bound for ES (Algorithm) T when applied to linear bandits described in Section 3.1 Theorem 1. Under ensemble sampling.
K log log(6T'M) MT
(T) S &WdTT dTTH(A.) v
M
(a)
where Iil(A.) is the Shannon entropy of the optimal action A, under the prior, and
A
/2
max
T Epa + +02) and 17 - 2 E
max (a
TT)²
+ +
(3)
acA
aEA
Note that (1) and Lemma in Appendix shows 17 0 O /minfd, log K}),
min log K K log (Tg()TM)
RTg 50 VdTTH(A)) VT
Theorem represents the first rigorously proved regret bound that ensures some degree of robustness application of ES to nontrivial bandit problem. One limitation that the second term (6) in our regret bound depends on the action set size K since our current analysis uses the method of (finite) types Cover and Thomas, 2006), which might be tight for linear bandit. We conjecture that the second term (b) can be improved to be only dependent of the dimension d. Another limitation is that result applies only to the linear bandit with Gaussian prior distribution and likelihood function, which admits tractable application of exact TS. Nevertheless, this result represents beginning of the theory of ES, suggesting that the approach is sound and the analysis might be extended broader problem classes.

---

Comparison with the regret bound for TS The regret bound in Theorem consists of two terms. The first term (a) is exactly the regret bound achieved by TS with exact postenor [Russo and Van Roy 2016]. Since the action set size is K. the entropy of the optimal action H.(A,)) < log K, and as discussed in Russo and Van Roy (0066) when the prior informative, (T.))) < log K. Therefore, the first term (a) is order optimal and improves upon the worst-case regret bound achieved by other algorithms, e.g.. upper confidence bound type algorithms. On the other hand, the second term (6) is an incremental term and accounts for posterior mismatch. Note that as the ensemble size M approaches infinity, the second term (b) converges to zero and our regret bound for ES reduces to that for TS with exact posterior. Moreover, long as the ensemble size M reaches KT/d,, our regret bound for ES has the same order as that for TS in terms of and d (up to logarithmic factors).
Comparison with the regret bound in Lu and Van Royl [2017] Theorem 1 presents a Bayesian regret bound for the prior N(o, Σo) over 0, while Lu and Van Roy [2017] studies ES in the frequentist setting where unknown 0 is fixed. They try upper bound the frequentist regret of ES by that of TS plus some cumulative approximation error due to posterior mismatch, similar to the second term (6) in our Bayesian regret bound. Although there are some technical issues in their analysis, as is discussed in Section 2 we compare both regret bounds. The frequentist regret bound in Theorem 3 of Lu and Van Roy [017]] suggests that for any с > O, when the ensemble size M = ((K/=²) (Ô hides logarithmic factors), their cumulative approximation error is e ( where (()) = maxae a T min.e4 a 6. To make the second term (b) in our regret bound scale as (e))) (Ō hides logarithmic factors), we need the ensemble size M to be (K//e)) well. We conjecture the required ensemble size can be improved to be only dependent of the dimension d.
Information measures
Before proceeding, we present several information measures including Kullback Leibler divergence, Hellinger distance, Shannon entropy and mutual information.
5.1 Kullback-Leibler divergence and Hellinger distance
For two probability distributions P and Q, the Kullback- (KL) divergence between and Q is defined as
flog
dP
dkr (PII))
log aQ
dp
if P is absolutely continuous with respect to Q: otherwise, define d = +oo. Note that (Pl()) & dkI(Q][P) in general. The Hellinger distance between P and Q is defined as
( Vao)²
du (p(l)))
which is symmetric in P and Q. In the special case of discrete distributions P P= (pi,... Pn and Q = (g)...., :n), the KL divergence and Hellinger distance between P and Q can be written as
dk1. (PIQ) = Σ pa log (p:/a) and dn(())Q)= = Σ kE(n
(vpi - 2
=E(m]
5.2 Shannon entropy and mutual information
Consider random variable X that takes values in countable set X. The Shannon entropy of X is
H(X) 2 Σ
P( = x)) log IP(X x) = Ex log (PX E -)
DEX
with a convention that 0 Olog =
For ease of exposition, let Y be another random variable that takes values in countable set V. For y E 3/ such that P(Y y) 0, the realized conditional entropy of X given Y y
[H(X v) A
Σ
P (X x 2) log P(X x/Y y) Exl= log P(X E -YY) v].
5

---

and the conditional entropy of X given Y is H[XXY) - Ey Exxx - = x|Y) Note that the above definitions can be extended to general random variables.
log P(X X= = x||)] = By Y)J
The mutual information between X and Y is T(X;Y) - dKL (P(X e, Y E P[ E )P(Y E E.) = H(X) ()()))) and the conditional mutual information between X and Y given general random variable Z is I(X;YI2) & Ez [dKL (TP(X E,, E, E (1)) |[X E (Z E - [x H(X Y, 2).
A general regret bound
In this section, we derive a general regret bound for any learning algorithm (Theorem 2) based on the Hellinger distance between the (conditional) action-sclection distribution specified by the algorithm and the posterior distribution of the optimal action A., and apply it to analyzing the regret bound for ES in Theorem | We believe that our regret bound is of independent interest and might be used to analyze other bandit algorithms, such as variants of approximate TS algorithms, in the future.
To simplify the exposition, first define some shorthand notation to simplify the exposition of this paper. First, we use subscript to denote conditioning on H,, specifically, we define
Pa(-) & P(-)H,) and E, [.] & [[]]
In addition, we define two probability distributions D. and P. over action set AA as
(-)-) A Pe =) and Pr(-) a (A.
Conditional on the history H,, P, is the sampling distribution of the action A, and pt is the posterior distribution of the optimal action A.. Both pt and P, specific to the algorithm. Note that given the history H,, P, and p. are the same under TS, but they are not under other algorithms. For approximate TS algorithms, if the approximation is accurate, pe is close P.. Now we introduce general regret bound for any learning algorithm:
Theorem 2. Under any learning algorithm,
T-1
Regret (T) S A.) +
E (P
where and are defined in Equation
The regret bound in Theorem 2 holds for any learning algorithm. Note (l.)) is the entropy of the optimal action A. and we always have (A.)) S log K. The first term matches the regret bound for TS derived in Russo and Van Roy (0066). In the second term, Σ V [d] (P, IP:.]] quantifies the cumulative distance between the sampling distribution of the action A, and the posterior distribution the optimal action A.. Under TS with exact posterior. di (P,llp)) = 0 due to the posterior matching
property of TS, i.e., P, = Pc- Moreover, for approximate TS algorithms, if the approximation is accurate, di (Pr llp)) should be small.
Regret bounds in terms of KL divergence between P. and It is sometimes more convenient to analyze the KL divergence between P, and pe. Recall that the squared Hellinger distance symmetric and upper bound by the KL divergence.
Fact 1 (Lemma 2.4 in Tsybakov (009])). For two probability distributions P and Q. have (PIIQ) S min(dxx(PIlQ), (kL(
We obtain the regret upper bound with the approximation error in terms of two forms of KL divergence between P. and pt.
Corollary 1. Under any learning algorithm.
Regret(T) I / dTH((AA) +
min (dKL( dKL (pe (Pellp.))]]
We will show in Section that for ensemble sampling, dkr. (p.llx.) can be bounded in terms of the
ensemble size M. noteworthy that in some other problems, it is more convenient bound the other form dku (pc(pellie ll. One such example is the regret bound developed in Wen et al. 2002

---

6.1 Proof of Theorem? 2
Fort l1l,,..... ...,, we define per-timester main regret G, and per-timestep approxiaatoonn evvor Dj:
Gt _ Σ
(a((a)pí(a) (Be[Re+L.alA4 = a) -12((R++1.o)))
aEA
Dj - Σ (Prila) - Vp.(a))
a] + (p Ret1.l)) (Peta))((Rettl))
aEA
Lemma 1, The cumulative regret can be written as follows,
Regret (T)
Σ B[G. + D.).
Proof. By the tower property of conditional expectation,
Regret(T) = 2--1 E [E,,,, RE+LA
where
E, RR4LAA
R441,1
Σ AA
A. a Σ Re
aEA
aEA
Σ = Σ
(.) ( = Dr
aEA
aEA
where the second equality that R4+1 (Re+1,a)add independent of the action A,
Next we upper bound ΣnD E[G.] and Ei= E[Da], respectively. We first analyze per-timestep main regret Gt. The following lemma generalizes Proposition 5 and Corollary 1 in Russo and Van Roy [2016) for the case such that At and A, are not identically distributed given the history.
Lemma 2. With defined in Equation (3r t 0, ..... T
G. S L(A:; (Ac, R(+1,A))
where (A,; (At, Re+1,A,) the mutual information between the optimal action A, and action- reward pair (At, Re41,A)) conditioning on given history He at timestep t.
Proof. Let the action set A = -a1.....,ee .x). Fix L and define M E RR by
Ma.j V Pr (as)pi (E, Ret1, IA = az] E, (Re11,;)) Then G. Trace(M). By the proof of Proposition in Russo and Van Roy 2016),
Vi,j E (K).
1 (Ar; (Ae, Re+1.A.) = (Ax; A.) + (A.; Re+1.A,
[A.; REL1A (A,)
Σ
(aa))) Re41, = a:)
KE[K]
Σ (AL,
iE[K]
Σ (as) Σ JELK
pr(a;)dKL (Pi(Ret1a, E :IA, a;)) a;j)) E E)
([[K]
Σ [JE[K]
(a (((s)))) (Pr(Re41a, E :lA- = a;;]] E E))
where the first equality uses the chain rule of mutual information (Fact the second and fourth ones follow from that conditional on the history H,, A, jointly independent A, and R4 = (Re the fifth equality uses the KL divergence form of mutual information (Fact 3
7

---

By the updating rule on covariance matrix in Equation T conditional on Hi, 8 ~ N(u, Ex) with Σ, 3 En. Hence, for any i [K].
R441.. = Ve N (a, st, ag E,a; + o²) where a Lia; S a Ega; maxo a Ega.
atA
This implies that 1,+ is sub-Gaussian with variance proxy (maxue a T Ega + o²). Then by Lemma TO have
2 EmjeKK (a(a))p((ay) (Ee(Re+1,,,44 AA = 0z) - Eg (R
TA,A;: RetL,,))
2 2(maxEEA a Ega + o²)
EnjelKy M
2 (maxaed a Σea + 0²)
||M
2 (maxaed a' Eoa+ + 0²)
Then by F
G2
2 (max.e.A EEga + x²) Trace(M)2
max InaxaTei _oa + 0² (a)k(M). aed
22
Ie(A.; (Ae, Bet (,,),
MMP
Now we show that Rank (M) S d. Define
== B [0]
and 133 = 1AA = =a Vj [K].
Then for any i.j [K].
Mij (p(a)))((as) (Be [TTTaaaA
az ailA, a₁} Eg [0 a.)) [Taaia vr (V3 -)) ai
and thus
Vpi(az) (N1 -v)
M =
I (P.(aaaa
Vp.(ax)ax ].
Vp((ax) (ux- V)
Since Mi is the product of one K x d matrix and the other d x K matrix, we have Rank(M) < d.
Now are ready to bound T by following the analysis of Proposition Russo and Van Roy (2016).
E[G.] and derive the first term of the regret bound in Theorem
Lemma 3. With defined in Equation B the following inequality holds:
E|G.] S /v (A.).
Proof. By Lemma 2
T-1
Σ
B s wd
V1 (A., (Ar, (Ai:
Bet2,il)
S1
dTE
Ie (A.; (Ae, Ret1.A)))
T-1 (Ar, ReHL.)))
1=0
dT (H(A.)-
/VTH(AA
where the second inequality applies the Cauchy- -chhwar inequality, and the last inequality uses the chain rule for mutual information (Fact and the definition of mutual information.
The next lemma controls the expected per-timestep approximation error [R[D)] under (sub- Gaussian prior distribution and noises. Summing over timesteps completes the proof of Theorem 2

---

Lemma 4. With defined in Equation
3 for tort- = 0, 0,1,...,T-I
.
E[Da] S my E
Proof. Fix L. We write
Dr - Σ (VDila) - villa)) Vel
- =a] a] Σ
(VPr(a)- -vb(a)) (,
Σ aEA
(Vpila) virlal)
Σ aEA
Pe(a) (Ee(RetaalA, = =a)²² +
Σ aEA
P((a) (Ee(De+1,a)3?
<dH(P:llpd)
Σ pe(a) (Eg a |Ax a
Σ
Pr(a) (Eg [R [Ri+1.0))
V
aEA
REA
_dH(P.lpp))
Σ Pr(a) [R2+1,, AA aa
(a) [ =
aEA
aEA
(ve, R [ [
-dH(P.lppe)
Ve [ [
where the first inequality applies the Cauchy-Schware Schwarz inequality; the second inequality uses the definition of Hellinger distance and the Jensen's 's inequality; the second-to-late equality holds since A, is independent of Re+1 = (Re+1, Taking expectation of both sides, we have
B[D.] < E dn(Fa 11..) E2
[
E
du (dn(Filleng (lee) B,
RR [RGtT.
E [ (P.(lP))
IR
RC Ri
+
R2 R E
E [di lPx))
E [AATO + We+1,A, + E [(A 0 Wet1
V E [di (p. llx))
E [(ATO)] 0 [(AT +
s 22 ld] (D. (pp)))
E
max (a T0)2 TEA
+ +
where the second inequality uses the Cauchy-Schwand inequality and tower property of conditional expectation, and the second-to-las inequality holds for the independent mean-zero (sub-)Gaussee noises with variance bounded by o².
7 Completion of the proof of Theorem 1
In this section, we complete the proof of Theorem by controlling the cumulative approximation in Corollary for ensemble sampling, where P, is the sampling
error ErD v E (P, distribution of the action A, and pt the posterior distribution of the optimal action A.. It suffices to show Lemma 5 belloo for the per-timestep approximation error Ejdkı (7, [Pr)] since summing over timesteps yields the second term the regret bound for ensemble sampling in Theorem |
Lemma 5. Under ensemble sampling, for t 0, ,...., T
K log (6(( 1)M)
[dKL (p, (p.))
M
Proof. We first discuss the behavior of ensemble sampling. Ensemble sampling uniformly sam- ples model m E (I....,M} and then chooses the action A, uniformly from the set Arm e

---

arg aa a aT Om.m We define the following approximation of Pa(a):
pr(a) Σ
1 11 faf A,m
M
Ar.ml
Mc(M]
where |m is the cardinality of the set Ar.m (with probability one, |A.ml 1). At timestep I, ES would sample an action from the approximation pt. Notice that the history H₂ does not include independent random perturbation W, = (W..)mm((M) ~ (0, which is used updating M models Equation (2). Therefore, given history H,, fa(a) is still random variable, and its expectation is the conditional probability of sampling action a, i.c., Ee(āc(a)] (a(a). By convexity of KL divergence, the per-timestep approximation error
(kL(P,
dx1, (E, [ llpa) I E, [dKL (fellpt)
Taking expectation of both sides over He gives EE (Felle) S TE [dgL (fx [pe]]. Next upper bound LE [dKL (Pellp:)] by first writing it in terms of the cumulative distribution function:
E [dKL (fellp:) = /.
P (dKI (fe (((e) > de.
Then we use the following result to upper bound PP PdKI (pellpr) > <) in the above integral.
Lemma 6 (Lemmaa 4 in Lu and Van Roy 2017 Ler O. For 0, 1,.... T P (dKL (Pellpr) > E 0) S (t 1) (M + e-Me.
Taking expectation of both sides over 0 gives the same upper bound on IP (dKL (Pellp:) > c), and thus for any 2 0, the integral in Equation (4) can be decomposed and bounded as follows,
f (dKI. (p.ll.)) > E) de
/ PP (dKI. (érllp.) > e) de
(dKI. (p:llp)) e) de J f
s 8 (1 + 1 1) (M 1)K ( c-Meee (M + (t + (M 1)k e-M6
Taking derivative of RHS gives optimal 8" K[log(++ +og (M 11) and then plugging in 5* yields
M
P (dkI. (p.) > e) de S [log(t + 1) log( M + 1)]
K log(G(t + 1)M)
<
M
M
This completes the proof of Lemma 5 and summing over timesteps gives Theorem
8 Concluding remarks
We present the first rigorous analysis for ensemble sampling, approximate Thompson sampling method. ES maintains an ensemble of statistically plausible models that can be updated an efficient incremental manner. We develop the regret bound for ES in Theorem D for lincar bandits, which approaches the regret bound for TS as the ensemble size increases. The linear bandit problem serves only sanity check, and discussed in Section 2 ES has been developed for broader and more challenging bandit and reinforcement learning problems.
noteworthy that in many practical problems, ES with moderate ensemble size (e.g. 30 models) outperforms other ofte-oo-theeant arrt
benchmarks Lu and Van Roy 2017 Lu et al.) 2018 Osband et al. 2019
As stepping stone, we also establish a general regret bound in Theorem 2 that applies to any learning algorithm for linear bandits. This general regret bound may be of independent interest, since is particularly useful for analyzing other varieties of approximate TS. One only need to bound the (cumulative) approximation error measured by the Hellinger distance between the action-selection distribution specified by the algorithm and the posterior distribution of the optimal action.
Finally, Theorem is established by bounding the information ratios for linear bandits, and we believe it could be generalized to other bandit and online learning problems as long as the corresponding information ratios can be appropriately bounded. These problems include generalized linear bandits, combinatorial semi-bandits, online learning with full information feedback, and problems with pure exploration objectives. We also conjecture that the results of this paper can extended episodic reinforcement learning, but leave these extensions to future work.
10

---

References
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in neural information processing systems, volume 24, 2011.
Jordan T. Ash, Cyril Zhang, Surbhi Goel, Akshay Krishnamurthy, and Sham Kakade. Anti- concentrated confidence bonuses for scalable exploration. arXiv preprint arXiv:2110.11202, 2021.
George Casella and Edward George. Explaining the Gibbs sampler. The American Statistician, 46 (3):167-174, 1992.
Olivier Chapelle and Lihong Li. An empirical evaluation of Thompson sampling. In Advances in neural information processing systems, volume 24, 2011.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. A Wiley-Interscience publication. Wiley, 2006.
Maria Dimakopoulou and Benjamin Van Roy. Coordinated exploration in concurrent reinforcement learning. International Conference on Machine Learning, volume 80, pages 1271-1273 2018.
Vikranth Dwaracherla, Xiuyuan Lu, Morteza Ibrahimi, Ian Osband, Zheng Wen, and Benjamin Van Roy. Hypermodels for exploration. In International Conference on Learning Representations, 2020.
Dean Eckles and Maurits Kaptein. Bootstrap Thompson sampling and sequential decision problems in the behavioral sciences. SAGE Open, 9(2), 2019.
Botao Hao, Jie Zhou, Zheng Wen, and Will Wei Sun. Low-rank tensor bandits. arXiv preprint arXiv:2007.15788, 2020.
Jean Honorio and Tommi Jaakkola. Tight bounds for the expected risk of linear classifiers and PAC-Bayes finite-sample guarantees. International Conference on Artificial Intelligence and Statistics, volume 33, pages 184-392,14 2014.
Ziyi Huang, Henry Lam, Amirhossein Meisami, and Haofeng Zhang. Generalized Bayesian upper con- fidence bound with approximate inference for bandit problems. arXiv preprint arXiv: 12955, 2022.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnel: Convergence and gener- alization in neural networks. Advances in neural information processing systems, volume 31, 2018.
Branislav Kveton, Csaba Szepesvári, Sharan Vaswani, Zheng Wen, Tor Lattimore, and Mohammad Ghavamzadeh. Garbage in, reward out: Bootstrapping exploration in multi multi-armed bandits. In International Conference on Machine Learning, pages 3601-3610. 2019.
Branislav Kveton, Csaba Szepesvári, Mohammad Ghavamzadeh, and Craig Boutilier. Perturbed- history exploration in stochastic linear bandits. In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115, pages 530-540, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms.. Cambridge University Press, 2020.
Jaehoon Lec, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dicksteen. Deep neural networks as gaussian processes. arXiv preprint 1rXiv:1711.00165. 2017.
Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. In Advances in Neural Information Processing Systems, volume 30, 2017.
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.
11

---

Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. In Advances in Neural Information Processing Systems, volume 29, 2016.
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement
learning. In Advances in Neural Information Processing Systems, volume 31, 2018.
Ian Osband, Benjamin Van Roy, Daniel J. Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124): 62, 2019.
Ian Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Xiuyuan Lu, Morteza Ibrahimi, Dieterich Lawson, Botao Hao, Brendan O' Donoghue, and Benjamin Van Roy. The neural testbed: Evaluating joint predictions. In Advances in Neural Information Processing Systems, 2022.
My Phan, Yasin Yadkor,, and Justin Domke. Thompson sampling and approximate inference. In Advances in Neural Information Processing Systems, volume 32, 2019.
Gareth O. Roberts and Richard L. Tweedie. Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli, pages 341-363, 1996.
Daniel Russo and Benjamin Van Roy. An information-theoreee theorrtic analysis of Thompson sampling. Journal of Machine Learning Research, 17(68): 2016.
Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on Thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4) 1933.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer series statistics.
Springer, 2009.
lñigo Urteaga and Chris Wiggins. Variational inference for the multi-armed contextual bandit. In International Conference on Artificial Intelligence and Statistics, volume 84, pages 698-706, 2018.
Zheng Wen, Ian Osband, Chao Qin, Xiuyuan Lu, Morteza Ibrahimi, Vikranth Dwaracherla, Moham mad Asghari, and Benjamin Van Roy. From predictions decisions: The importance of joint 2022.
predictive distributions. arXiv preprint
Jeremy Yang, Dean Eckles, Paramveer Dhillon, and Sinan Aral. Targeting for long-term outcomes. arXiv preprint arXiv:2110.158: 2020.
Tong Yu, Branislav Kveton, Zheng Wen, Ruiyi Zhang, and Ole J. Mengshoel. Graphical models meet bandits: A variational Thompson sampling approach. In International Conference Machine Learning, volume 119, pages 10902-10912, 2020.
Ruiyi Zhang, Zheng Wen, Changyou Chen, Chen Fang, Tong Yu, and Lawrence Carin. Scalable Thompson sampling via optimal transport. In International Conference on Artificial Intelligence and Statistics, volume 89, pages 87-96, 2019.
Zheqing Zhu and Benjamin Van Roy. Deep exploration for recommendation systems. arXiv preprint arXiv:2109. 12509, 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] In this paper, we establish a regret bound for ES in linear bandits (Theorem D. which is based on novel general regret bound (Theorem
These contributions have been accurately reflected the abstract and introduction.
(b) Did you describe the limitations of your work? [Yes] We discuss the limitations of this work and future directions in Sections 4 and g
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is theoretical paper. We do not see any potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We clearly state the full set of assumptions.
(b) Did you include complete proofs of all theoretical results? [Yes] We indeed include (almost) all the proofs in the main body.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL.)? [N/A] This paper does not include any experimental results.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "rr58ADX6Vqf", "reviewer": "Reviewer_gXhC", "summary": "This paper aims to establish a regret bound for ensemble sampling when it is applied to the linear bandit problem. This is done through leveraging information-theoretic concepts and novel analytic techniques.\n\nSpecifically, this paper:\n\n* Formulates the linear bandit problem and the ensemble sampling algorithm\n* Provides a bayesian regret bound for ensemble sampling in linear bandits\n* Motivate the general regret bound and sketch the proof", "questions": "Could the authors include some more detailed instructions about how this could be applied to downstream tasks?", "limitations": "In the conclusion section, the authors mentioned several ways the results of this paper can be used, including analyzing and approximating different sampling algorithms in different problems. It would be great if the authors could elaborate on that a little bit more.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis paper is the first rigorous regret analysis of ensemble learning, and it provides a bayesian regret bound to it in linear bandits.\n\nWeaknesses:\nThis is likely just personal taste and limitation, but it would be great if the authors could include some instructions about how this could be applied to downstream tasks like neural architecture design.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gTim253z9wx", "reviewer": "Reviewer_iQHa", "summary": "The paper develops a regret bound for the methodology of ensemble sampling as applied to Linear Gaussian Bandits.  The resulting bound shows the regret to be a combination of the regret of Thomson sampling and a term to capture the posterior distribution mismatch. \nIn order to prove this regret, they prove a general regret bound for linear bandits for any learning algorithm which bounds the regret by a combination of the entropy of the optimal solution and a gap between the model and exact and approximate posterior as observed from sampling. They then use this result for their own bound. ", "questions": "It would be good to see a comparison of regret bounds for other learning methods on the linear gaussian bandits besides Thomson sampling. Though part of the bound provided by them is order optimal, it is difficult to judge the quality of the overall bound without such a discussion. \n", "limitations": "The authors have not addressed this issue. I do not think the work has any direct negative societal impact. \nThe key limitation of the work is the use of Linear Bandits which seems to be a requirement of the analysis anyways. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\nThe paper provides the first theoretical results for ensemble sampling. \nIt also provides intermediate bounds which can be leveraged by other learning methods to prove their own bounds.\n\nWeaknesses\nThe paper focuses on linear bandits which are relatively simple. ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_NETt9031kY", "reviewer": "Reviewer_oHyo", "summary": "The paper focuses on the Ensemble Sampling (ES) algorithm, a method designed to approximate Thompson Sampling (TS) in settings where the exact posterior on unknown parameters is intractable. ES maintains an ensemble of plausible models and instead of attempting to sample a model from the full intractable posterior, it samples from a discrete distribution over the ensemble. It then proceeds, similarly to TS, to select at action which is optimal under the assumption that the sampled model represents the ground truth. The main contribution of the paper is to present a rigorous Bayesian regret analysis of the algorithm in the stochastic linear bandit setting, where Lu and van Roy (2017) previously presented a frequentist regret analysis that has subsequently been identified to be flawed.\n\nThe paper produces an ES-specific analysis by first deriving a Bayesian regret bound for ‘any learning algorithm’ which essentially consists of the information theoretic bounds of Russo and Van Roy (2016) for exact TS plus a term which is proportional to the cumulative differences between the action selection distribution of TS and of the alternative learning algorithm which is the subject of the analysis.\n", "questions": "General: Kveton et al. (2020, UAI) present a result of a similar flavour, but in the (stronger) frequentist setting. They have (as I understand it) a bound on the (frequentist) regret of any algorithm for stochastic linear bandits, which can then be specified to particular algorithms by deriving the appropriate form of a general term. I think this is an important related piece of work which should be addressed in the present paper. My question is how does the new analysis of the Bayesian regret compare to that of the frequentist regret. Does it open a possibility to analyse algorithms for which the result of Kveton et al. (2020) cannot be used? Does it just provide a quicker route to a reasonable performance guarantee for randomised algorithms? Could a stronger analysis of ES be provided using the framework from Kveton et al. (2020)? Could the present analysis inspire some analysis in some more challenging setting where the frequentist analysis could not be so readily extended?\n\nReferences:\n-\tKveton, Szepesvari, Ghavamadzeh, Boutilier (2020) Perturbed-History Exploration in Stochastic Linear Bandits. In Unceratinty in Artificial Intelligence\n", "limitations": "Adequately addressed, there are unlikely to be ethical issues linked to this theoretical work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written, in straight-forward language and clearly presents its contributions. ES is, as the related literature attests, a practical and relevant alternative to TS and thus any valid analysis of its performance is useful, particularly since previous results have been shown to be invalid. The theoretical results are, as far as I have been able to verify, accurate. As the authors suggest, there does seem to be opportunity to extend this line of analysis to more complex problems.\n\nIn my opinion the weaknesses are twofold. Firstly, as I describe in more detail below, I feel closely related results giving bounds on frequentist regret in stochastic linear bandits are not adequately addressed. Secondly, I feel the paper could have been stronger if it attempted to push beyond the linear bandit setting, where as the authors identify, ES as an approximation to TS is not necessary and the utility of the analysis is principally illustrative. \n\nOn this second point, I feel the paper could have been stronger if it had at least speculated in more detail as to what an analysis of a more challenging setting would look like or as to what the principal theoretical challenges would entail. Ideally, the paper would go so far as to extend this analytical technique to at least one setting where ES is genuinely required to deploy a TS-like approach. The level of contribution that merits publication is of course a subjective matter, and I am therefore not bound to the view that it is close to the borderline for NeurIPS. I will pay close attention to the subsequent discussions with authors and other reviewers to update my recommendation on this point.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Bvu12JhnPM", "reviewer": "Reviewer_MPVW", "summary": "The authors propose a novel analysis of Thompson Sampling using ensemble sampling, which is an approximation technique in order to correct for the fact that in general, sampling from the posterior distribution of the unknown vector theta is impractical in high dimensions. The idea of ensemble sampling resembles a particle filter, where one samples a finite number of points in order to approximate the intractable posterior distribution. They propose a regret analysis which corrects deficiencies of an earlier analysis of (Lu and Van Roy, 2017).", "questions": "Two questions:\n- is it possible to lower bound the value of $M$ as a function of $K,T$ to ensure a regret comparable to Thompson Sampling ?\n- why is there a noise floor in the regret upper bounds ? and can it be fixed ?", "limitations": "See above.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and easy to follow.\n- The paper corrects technical deficiencies in an earlier paper\n- Theorem 2 is nice in the sense that it might apply to a wider range of settings, and shows that controlling the Hellinger distance between the approximate distribution and the actual posterior yields usable upper bounds. \n- In general, the idea of finding computationally efficient alternatives to Thompson Sampling for structured bandits is a very important problem, and certainly non trivial.\n\nWeaknesses\n- Dependency on the number of arms $K$: The dependency on the regret on the number of points $M$ is very significant, and imposes that, for the regret bound to be non trivial, one requires at least $M \\ge K$, and for the regret bound to be close to the regret of Thompson Sampling one requires $M \\ge {T K \\over d}$. Now, the number of arms $K$ is going to be larger than the dimension $d$ (otherwise one can simply ignore the linear structure and treat the problem like a classical $K$ armed bandit, and in many cases, $K$ is going to be exponential in $d$ (an example of this would be combinatorial bandits). This implies that the algorithm might not be usable in high dimensions. The authors argue that one could use $M = O( {d \\over \\epsilon^2})$ instead of  $M = O({K \\over \\epsilon^2})$ but this seems dubious. At the very least the authors could expand on this issue. In fact, determining a lower bound on $M$ as a function of $K,T$ would be very interesting.\n\n- Noise floor when $\\sigma^2 \\to 0$: in the regret upper bound of Theorem 1, when the variance of the rewards $\\sigma^2$ is taken close to $0$, the regret upper bound becomes $O( \\sqrt{dT H(A)})$, which is probably not tight since, when rewards have no variance, it is sufficient to sample $d$ linearly independent actions in order to figure out the optimal action with probability 1, and hence the regret in this regime should be at most $O( d \\sqrt{\\log K})$ where $O(\\sqrt{\\log K})$ is the expected value of the largest gap between the optimal arm and a non optimal arm.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept