Sharp analysis of linear ensemble sampling Arya Akhavan, David Janz, Csaba Szepesvári Abstract We analyse linear ensemble sampling (ES) with standard Gaussian perturbations in stochastic linear bandits. We show that for ensemble size m = Θ ( d log n ) m=\Theta(d\log n) , ES attains O ~ ( d 3 / 2 n ) \widetilde{O}(d^{3/2}\sqrt{n}) high-probability regret, closing the gap to the Thompson sampling benchmark while keeping computation comparable. The proof brings a new perspective on randomized exploration in linear bandits by reducing the analysis to a time-uniform exceedance problem for m m independent Brownian motions. Intriguingly, this continuous-time lens is not forced; it appears natural–and perhaps necessary: the discrete-time problem seems to be asking for a continuous-time solution, and we know of no other way to obtain a sharp ES bound. \coltauthor University of Oxford, UK and University of Oxford, UK and University of Alberta, Canada namesep= ,pairsep= and ,listsep=, ,lastsep= and ,tpairsep= and ,tlistsep=, ,tlastsep=, and ,notesep= ,rangesep= to ,type=book,Name-sg=Book,name-sg=book,Name-pl=Books,name-pl=books,type=part,Name-sg=Part,name-sg=part,Name-pl=Parts,name-pl=parts,type=chapter,Name-sg=Chapter,name-sg=chapter,Name-pl=Chapters,name-pl=chapters,type=section,Name-sg=Section,name-sg=section,Name-pl=Sections,name-pl=sections,type=paragraph,Name-sg=Paragraph,name-sg=paragraph,Name-pl=Paragraphs,name-pl=paragraphs,Name-sg-ab=Par.,name-sg-ab=par.,Name-pl-ab=Par.,name-pl-ab=par.,type=appendix,Name-sg=Appendix,name-sg=appendix,Name-pl=Appendices,name-pl=appendices,type=page,Name-sg=Page,name-sg=page,Name-pl=Pages,name-pl=pages,rangesep=–,rangetopair=false,type=line,Name-sg=Line,name-sg=line,Name-pl=Lines,name-pl=lines,type=figure,Name-sg=Figure,name-sg=figure,Name-pl=Figures,name-pl=figures,Name-sg-ab=Fig.,name-sg-ab=fig.,Name-pl-ab=Figs.,name-pl-ab=figs.,type=table,Name-sg=Table,name-sg=table,Name-pl=Tables,name-pl=tables,type=item,Name-sg=Item,name-sg=item,Name-pl=Items,name-pl=items,type=footnote,Name-sg=Footnote,name-sg=footnote,Name-pl=Footnotes,name-pl=footnotes,type=endnote,Name-sg=Note,name-sg=note,Name-pl=Notes,name-pl=notes,type=note,Name-sg=Note,name-sg=note,Name-pl=Notes,name-pl=notes,type=equation,Name-sg=Equation,name-sg=equation,Name-pl=Equations,name-pl=equations,Name-sg-ab=Eq.,name-sg-ab=eq.,Name-pl-ab=Eqs.,name-pl-ab=eqs.,refbounds-first-sg=,(,),,refbounds=(,,,),type=theorem,Name-sg=Theorem,name-sg=theorem,Name-pl=Theorems,name-pl=theorems,type=lemma,Name-sg=Lemma,name-sg=lemma,Name-pl=Lemmas,name-pl=lemmas,type=corollary,Name-sg=Corollary,name-sg=corollary,Name-pl=Corollaries,name-pl=corollaries,type=proposition,Name-sg=Proposition,name-sg=proposition,Name-pl=Propositions,name-pl=propositions,type=definition,Name-sg=Definition,name-sg=definition,Name-pl=Definitions,name-pl=definitions,type=proof,Name-sg=Proof,name-sg=proof,Name-pl=Proofs,name-pl=proofs,type=result,Name-sg=Result,name-sg=result,Name-pl=Results,name-pl=results,type=remark,Name-sg=Remark,name-sg=remark,Name-pl=Remarks,name-pl=remarks,type=example,Name-sg=Example,name-sg=example,Name-pl=Examples,name-pl=examples,type=algorithm,Name-sg=Algorithm,name-sg=algorithm,Name-pl=Algorithms,name-pl=algorithms,type=listing,Name-sg=Listing,name-sg=listing,Name-pl=Listings,name-pl=listings,type=exercise,Name-sg=Exercise,name-sg=exercise,Name-pl=Exercises,name-pl=exercises,type=solution,Name-sg=Solution,name-sg=solution,Name-pl=Solutions,name-pl=solutions 1 Introduction We consider the standard stochastic linear bandit problem with a fixed, potentially infinite action set. Ensemble sampling (ES) ( 18 ) is a randomized algorithm for this problem that has received considerable attention in recent years (e.g., 21 ; 20 ; 22 ; 19 ; 23 ; 9 ; 11 ; 16 ; 28 ; 27 ) . The algorithm maintains a collection (ensemble) of models, each trained on its own perturbed version of the history, and each modelling the dependence of the mean reward on actions. In every round, ES chooses one model uniformly at random from the ensemble and selects the action that maximizes the predicted mean reward under the chosen model. The appeal of ES is that it reduces exploration to model training and action selection from a single model, and as such it can be implemented whenever model training and single-model action selection are feasible. ES is one of several randomized algorithms for exploration in bandit problems. A gold standard among these is Thompson sampling (TS) ( 26 ; 4 ; 3 ) , whose n -step regret in d -dimensional linear bandits is known to be \widetilde{O}(d^{3/2}\sqrt{n}) ( 3 ; 10 ) . A long line of research has sought to establish whether ES can match this performance (see ?? ). Despite this effort, the best results for ES fall short of achieving the same regret as TS, except in the case where the action set is finite and small enough that an ensemble size ( m ) scaling with the number of actions k is tolerable. Indeed, 16 recently showed that ES can match the regret of TS in the finite- k setting; however, their result requires setting m=\Omega(k\log(n)) , which makes the method unsuitable for large or infinite action sets. In particular, if one insists on using this approach for the case where the action set is the unit ball in \mathbb{R}^{d} via discretization, the discretized action set size must scale exponentially with the dimension d . From a computational perspective, to keep the per-round cost comparable to that of competing methods in d -dimensional linear bandits, it is natural to restrict attention to the case m=\widetilde{O}(d) (where \widetilde{O} hides \log(n) factors), regardless of the number of actions. We note in passing that this scaling cannot be pushed too far: a simple lower bound (proved in this paper, see ?? ) shows that if m\leq d/2 then there are linear bandit instances on which ES incurs linear regret. In the regime m=\widetilde{O}(d) , the best prior regret bound for ES in linear bandits is \widetilde{O}(d^{5/2}\sqrt{n}) ( 11 ) , achieved with m=\Theta(d\log(n)) , lagging behind the regret of TS by a factor of d . The main contribution here is to close this gap by showing that ES with m=\Theta(d\log(n)) can achieve the canonical \widetilde{O}(d^{3/2}\sqrt{n}) regret rate. Table 1: Overview of results on ES for the stochastic linear bandit setting. Here, n denotes the decision horizon, d the dimension, and k the number of arms (where a given result requires this to be finite). Thompson sampling result is per 4 . For readability, regret bounds are stated omitting \log n factors. Where results allow a trade-off between regret and ensemble size, we pick the ensemble size to give \sqrt{n} regret. For high probability results we set \delta=1/n . Paper Regret bound Ensemble size Notes & comments 18 d^{3/2}\sqrt{n} \sqrt{k}n given proof is incorrect 23 \sqrt{dn} dn Bayesian regret, not frequentist 11 d^{5/2}\sqrt{n} d\log n algorithm uses symmetrisation 16 d^{3/2}\sqrt{n} k\log n k can be as large as e^{d} 25 d^{3/2}\sqrt{n} k\log n generalised linear model setting this paper d^{3/2}\sqrt{n} \mathclap{d\log n} — Thompson sampling d^{3/2}\sqrt{n} — — Technical contributions The primary difficulty in analysing ES—and the reason for the gap in prior results—is the dependence induced by adaptation: although the perturbations injected into the data are independent across ensemble members and time, the fitted models are coupled by training on data collected using actions selected by the ensemble itself. Our proof builds on 11 , who show that regret control reduces to establishing a high-probability lower bound on certain time-uniform self-normalized exceedance frequencies (i.e., the fraction of ensemble members whose self-normalized noise exceeds a fixed threshold, uniformly over time). Our first contribution is to identify the relevant noise processes as predictable diagonal martingale transforms : processes of the form S_{t}\;=\;\sum_{s=0}^{t}D_{s}\xi_{s}, where (\xi_{s})_{s\geq 0} are the i.i.d. noise variables used in model training and D_{s} are predictable diagonal matrices (in our linear setting, D_{s} is a scalar multiple of the identity). A key realization here is that Gaussian perturbations unlock powerful continuous-time tools, as we describe next. With this choice in place, we prove a representation/embedding lemma showing that such Gaussian transforms can be realized by evaluating independent Brownian motions at random times given by the predictable quadratic variation of the transform (key ingredients include a pinned Brownian motion/Brownian bridge construction, the Dambis–Dubins–Schwarz time change, and orthogonality/covariation arguments to obtain independence). This step converts the coupled discrete-time noise processes arising in ES into independent Brownian motions with random clocks, isolating all adaptivity into the clocks. An important feature of our linear ES setting is that the diagonal transforms are in fact scalar multiples of the identity, so all coordinates share a common clock—precisely the regime in which we can control time-uniform exceedance frequencies of independent Brownian motions. (When the clocks differ across coordinates, the problem becomes substantially more delicate.) Our second contribution is a time-uniform lower bound on the exceedance frequency for m independent Brownian motions: over any time window t\in[\tau,\tau^{\prime}] , the fraction of Brownian motions above the curved boundary c\sqrt{t} stays above a target level p uniformly in t with probability at least 1-\delta , provided p is below a constant p_{0}(c) depending on c (on the order of the Gaussian tail at c ), and with a suitable discretization step h=h(c,p) (which is a constant when c and p are fixed; e.g. c\leq 1/20 and p\leq 1/10 allow h=1/250 ), m\;\gtrsim\;\frac{1}{p}\log\!\Big(\frac{\log(\tau^{\prime}/\tau)}{h\,\delta}\Big)\qquad(\text{up to universal constants}). (This bound is the core probabilistic step; the final ensemble-size requirement in our bandit theorem additionally accounts for uniformity over directions.) Key ingredients include an Ornstein–Uhlenbeck time change, boundary-crossing estimates for Brownian motion, Chernoff bounds, and a union bound over a log-time discretization. Combining these yields the desired time-uniform self-normalized exceedance frequency guarantee, and hence our regret bound. Proof insight and outlook. While the stochastic-analysis ingredients are classical, their role here is not: the Brownian embedding and time-change tools are what unlock a tractable analysis of the adaptive, self-normalized discrete-time exceedance problem. This continuous-time viewpoint is the key conceptual lever in the paper. We find it striking that these tools are so effective in a purely discrete-time setting, and at present we do not know an equally sharp purely discrete alternative. We conjecture that analogous time-uniform self-normalized exceedance frequency guarantees hold for other perturbation distributions (e.g., Rademacher), but proving this would require different tools. Plausible routes include Skorokhod embeddings and strong approximation couplings. Developing either into a sharp exceedance bound remains open. Our use of continuous-time tools differs from prior work on discrete-time algorithms and processes, which uses continuous-time limits as approximations (e.g., 6 ; 13 ; 7 ; 15 ) ; here the continuous-time process gives an exact representation. A natural direction is to use such embeddings to derive self-normalized tail inequalities for Gaussian martingale transforms, an approach that appears both in early work such as 8 (LIL for i.i.d. Gaussians) and more recently in 17 (self-normalized bounds for scalar Gaussian martingale transforms in SDE discretization analysis). Given the elegance of the approach, it seems likely that it could find further applications in deriving sharp inequalities for discrete-time stochastic processes. Finally, it is an interesting open direction to understand whether related mechanisms persist in nonlinear settings when the effective noise retains an approximately conditionally independent component structure. 2 Notation and problem setting The purpose of this section is to introduce our notation and the linear bandit setting we consider. We start with notation that will be used throughout. We let \mathbf{N}_{+} denote the set of positive integers, for n\in\mathbf{N}_{+} we let [n]=\{1,\dots,n\} . We use \mathbf{R} to denote the set of real numbers, \mathbf{R}^{d} to denote the d -dimensional Euclidean space and \mathbf{B}^{d}_{2} to denote the unit ball of this space under the Euclidean norm \|\cdot\|:=\|\cdot\|_{2} , while \mathbf{S}^{d-1}_{2} denotes the corresponding sphere. For x,y\in\mathbf{R}^{d} , \langle x,y\rangle=x^{\top}y denotes their inner product. For a positive definite matrix A\in\mathbf{R}^{d\times d} , we let \|x\|_{A}=\sqrt{x^{\mkern-1.5mu\mathsf{T}}Ax} denote the associated weighted 2-norm. For a probability distribution P , we let P^{\otimes m} denote the m -fold product distribution of P . We use \mathbf{1}\{\cdot\} to denote the indicator that returns one when its argument is true and zero otherwise. Linear bandits The standard subgaussian stochastic linear bandit setting ( 14 , Chapter 19) is as follows: Fix d\in\mathbf{N}_{+} , a closed action set \mathcal{X}\subset\mathbf{B}^{d}_{2} , and a fixed parameter \theta_{\star}\in\mathbf{B}^{d}_{2} . In a stochastic linear bandit environment \mathcal{E} specified by (\mathcal{X},\theta_{\star}) , a learner interacts with the environment in rounds. The action set \mathcal{X} is known to the learner, but the parameter \theta_{\star} is unknown. The learner sequentially selects actions from \mathcal{X} , sends them to the environment, and the environment responds with noisy rewards that follow a linear model: in round t\in\mathbf{N}_{+} the learner selects action X_{t}\in\mathcal{X} , then it receives reward Y_{t}\in\mathbf{R} such that the mean reward is \langle X_{t},\theta_{\star}\rangle . We assume that the environment generates noise that has light tails. In particular, the noise \eta_{t}=Y_{t}-\langle X_{t},\theta_{\star}\rangle is assumed to be conditionally 1 -subgaussian, given the past actions and rewards and randomizations of the learner. That is, we assume that for all t\in\mathbf{N}_{+} , \mathbf{E}\big[\exp(s\eta_{t})\mid\mathcal{G}_{t}\big]\leq\exp\left(\frac{s^{2}}{2}\right)\,,\quad\text{for all $s\in\mathbf{R}$}\,, where \mathcal{G}_{t} is a \sigma -algebra that makes X_{1},Y_{1},\dots,X_{t-1},Y_{t-1},X_{t} , as well as any other random variables the learner used to generate X_{1},\dots,X_{t} , measurable. We fix a horizon n\geq 1 and measure the performance of the learner by the n -step (pseudo)regret, which captures the shortfall of mean rewards generated by the learner compared to that of an oracle that always selects the optimal action: R_{n}=\max_{x_{\star}\in\mathcal{X}}\sum_{t=1}^{n}\langle x_{\star}-X_{t},\theta_{\star}\rangle\,. Our goal will be to show that when (X_{t}) is selected by ensemble sampling, which we specify next, R_{n} is small with high probability. 3 Ensemble sampling In this section we introduce ensemble sampling (ES) and recall the state-of-the-art result available for it in the linear bandit setting. Algorithm description To estimate the unknown parameter \theta_{\star} , ES uses ridge regression estimates based on the data collected so far with some perturbations. Recall that ridge regression estimates the parameter \theta_{\star} by minimising a regularised squared loss over the data collected so far. Since the regulariser is chosen to be the squared Euclidean norm, the resulting estimates and confidence ellipsoids enjoy closed-form expressions. In particular, given observations (X_{1},Y_{1},\dots,X_{t-1},Y_{t-1}) up to time step t-1 and a regularisation parameter \lambda>0 , the \lambda -regularised ridge regression estimate for \theta_{\star} is given by \hat{\theta}_{t-1}=V_{t-1}^{-1}\sum_{i=1}^{t-1}X_{i}Y_{i}\quad\text{where}\quad V_{t-1}=V_{0}+\sum_{i=1}^{t-1}X_{i}X_{i}^{\mkern-1.5mu\mathsf{T}}\quad\text{and}\quad V_{0}=\lambda I\,. (1) Now, ES will maintain an ensemble of m such ridge regression estimates (\theta_{t}^{1},\dots,\theta_{t}^{m})_{t\geq 0} . The estimates for model j\in[m] are obtained by ridge regression, but with two changes: First, the regularisation is not towards zero, but towards a random vector \zeta^{j}\in\mathbf{R}^{d} drawn from some fixed distribution, before seeing any data (“the prior”). Second, the data used for training is perturbed by adding noise to the rewards, as the rewards are observed. The noise is drawn afresh for each model and each time step, but once chosen, it remains fixed for that model and time step. In particular, if these noise variables are (\xi_{t}^{j}\colon t\geq 1,j\in[m]) then the j th model parameters in the ensemble will be given by the ridge regression estimate \displaystyle\theta_{t-1}^{j}=V_{t-1}^{-1}\sum_{i=1}^{t-1}X_{i}(Y_{i}+\xi_{i}^{j})+\sqrt{\lambda}\zeta^{j}=\hat{\theta}_{t-1}+V_{t-1}^{-1}S_{t-1}^{j}\,,\quad j\in[m]\,, (2) where S_{t-1}^{j}=\sqrt{\lambda}\zeta^{j}+\sum_{s=1}^{t-1}X_{s}\xi^{j}_{s}\,,\quad j\in[m]\,. Action selection in round t\in[n] proceeds by taking a random index J_{t} uniformly on [m] , setting the current model parameter to \theta_{t}=\theta_{t-1}^{J_{t}} and selecting X_{t}\in\argmax_{x\in\mathcal{X}}\langle x,\theta_{t}\rangle\,. Noise scale It is standard to scale the noise injected into the data to ensure sufficient exploration. The idea of inflating the noise can be traced back to 4 , who, in the context of Thompson sampling for linear bandits, proposed inflating the posterior variance by a \sqrt{d\log(n)} factor. Here, following 11 , we consider a refinement where we allow noise scaling to be data-dependent. This has the potential to decrease the regret in benign cases, while keeping the computation comparable – provided that the computation of the data-dependent scaling term is cheap (which it is in the case considered below). The data-dependent scaling will also clarify how the noise level relates to controlling exploration. The specific modified formula for the model parameters we will use is \displaystyle\theta^{j}_{t-1}=\hat{\theta}_{t-1}+\overline{\gamma}\beta_{t-1}^{\delta}V_{t-1}^{-1}S_{t-1}^{j}\,,\quad j\in[m]\, (3) where \beta_{t-1}^{\delta} is the data-dependent scaling parameter and \overline{\gamma} is a tuning parameter (and the superscript is used to denote the dependence on this \delta , not exponentiation). The reason for writing the scale as a product of these two terms will be explained momentarily. This completes the description of ES. The full algorithm is given in ?? , where we leave the choice of the prior P_{0} and the noise distribution Q as inputs. Common sense suggests that these should be centered, light-tailed, but nontrivial (positive variance) distributions. inputs : ensemble size m\in\mathbf{N}_{+} , inflation parameter \overline{\gamma}>0 , regularisation parameter \lambda>0 , confidence parameter \delta\in(0,1) , distributions P_{0} and Q over \mathbf{R} 1 initialise the design matrix V_{0}=\lambda I and the accumulator S_{0}=0 2 let (\zeta^{1},\dots,\zeta^{m})\sim P_{0}^{\otimes m} S_{0}^{j}=\sqrt{\lambda}\zeta^{j} \theta^{j}_{0}=V_{0}^{-1}S^{j}_{0}(=S_{0}^{j}/\lambda) for each j\in[m] 3 for t=1,2,3,\dots do 4 select an ensemble index J_{t}\sim[m] uniformly at random and set \theta_{t}=\theta_{t-1}^{J_{t}} 5 compute the action X_{t}=\argmax_{x\in\mathcal{X}}\langle x,\theta_{t}\rangle 6 send X_{t} to the environment and receive feedback Y_{t}\in\mathbf{R} 7 compute the new design matrix V_{t}=V_{t-1}+X_{t}X_{t}^{\mkern-1.5mu\mathsf{T}} and let S_{t}=S_{t-1}+Y_{t}X_{t}\quad\text{and}\quad\hat{\theta}_{t}=V_{t}^{-1}S_{t} 8 compute \beta_{t}^{\delta} as in ( 4 ), sample (\xi_{t}^{1},\dots\xi_{t}^{m}) from Q^{\otimes m} and let \widetilde{S}_{t}^{j}=\widetilde{S}_{t-1}^{j}+\xi_{t}^{j}X_{t}\quad\text{and}\quad\theta_{t}^{j}=\hat{\theta}_{t}+\overline{\gamma}\beta_{t}^{\delta}V_{t}^{-1}\widetilde{S}^{j}_{t}\,. Algorithm 1 Linear ensemble sampling with adaptive noise levels Let us now return to clarifying how the scaling of the noise helps control exploration. The idea is to match the noise level to the size of a standard confidence ellipsoid for \theta_{\star} up to the constant multiplier \overline{\gamma} . This is what in turn allows the algorithm to explore sufficiently: By choosing this noise scaling, the perturbed model parameters will hopefully spread out in the confidence ellipsoid, making it likely that some fraction of the models in the ensemble are optimistic (i.e., yield a larger optimal reward than the true parameter). If this fraction can be kept above a positive constant uniformly over time, then the regret can be controlled (see 11 for details). Once the noise level is fixed, the central question becomes how large m must be in d dimensions to ensure a constant fraction of optimistic draws. ?? in ?? illustrates the underlying geometry. The standard radius mentioned above is given by \beta_{t-1}^{\delta}=\sqrt{\lambda}+\sqrt{2\log(1/\delta)+\log(\det(V_{t-1})/\lambda^{d})}\,,\quad t\in\mathbf{N}_{+}\,, (4) where \delta\in(0,1) is a confidence parameter. In particular, owing to the assumption that the reward noise is subgaussian, the following holds: 3.1 Confidence ellipsoids, ( 1 ) . With probability at least 1-\delta , \theta_{\star}\in\bigcap_{t\in\mathbf{N}_{+}}\Theta_{t-1}^{\delta} , where \Theta_{t-1}^{\delta}=\{\theta\in\mathbf{R}^{d}\colon\|\theta-\hat{\theta}_{t-1}\|_{V_{t-1}}\leq\beta_{t-1}^{\delta}\},\quad t\in\mathbf{N}_{+}\,. As to the magnitude of \beta_{t-1}^{\delta} , by the elliptical potential lemma (e.g., Lemma 19.4 of 14 ), it holds that \displaystyle\beta_{t-1}^{\delta}\leq\sqrt{\lambda}+\sqrt{2\log(1/\delta)+d\log(1+n/(\lambda d))}\,. (5) The noise perturbation magnitude can be set to the upper bound rather than tracking \beta_{t-1}^{\delta} itself, yielding a fixed noise level, but perhaps at some (small) loss of exploration efficiency. Computational complexity. With an incremental implementation, the complexity of a single step of ?? is on the order of d^{2}+md^{\omega-1} per round, where \omega\geq 2 denotes matrix multiplication complexity (so d^{\omega} is the cost of multiplying d\times d matrices). The d^{2} term comes from updating the design matrix V_{t} and computing its inverse using the Sherman-Morrison formula. The md^{\omega-1} term comes from packing S_{t}^{1},\dots,S_{t}^{m} into a d\times m matrix and then multiplying it with the d\times d matrix V_{t}^{-1} from the left to get all the model parameters \theta_{t}^{1},\dots,\theta_{t}^{m} . As noted earlier, avoiding linear regret in the worst case requires m\geq d/2 ( ?? ). Thus, absent further algorithmic innovations, sublinear - regret ES has an inherent per - round overhead relative to TS even before the \log n factor ( d^{\omega} vs. d^{2} ). Current state of the art. The state-of-the-art regret bound for ES in linear bandits is due to 11 . However, this result is stated for a slightly different version of ?? , when \theta_{t} is defined as \theta_{t}=\hat{\theta}_{t-1}+\overline{\gamma}\beta_{t-1}^{\delta}\xi_{t}V_{t-1}^{-1}\widetilde{S}_{t-1}^{J_{t}} , where \xi_{t} is a Rademacher random variable, which is chosen at the same time as J_{t} , independently of J_{t} . While 11 needed this symmetrization to carry out their analysis, it is not necessary for our analysis, and we work with ?? as stated (yet, the symmetrization does not hurt either and may even help in practice). Their result, Theorem 1 in 11 , gives that if we take \lambda=5 and m to be as small as their constraints allow, then, up to logarithmic-in- n factors, the regret bound scales as d^{5/2}\sqrt{n} , while the ensemble size scales as d\log(n) . 4 Results Our main results are as follows: 4.2 restate = theoremLinBound, name = Regret bound for ?? , linear ensemble sampling. Fix n\geq\max\{2,d\} , \delta\in(0,1/2) , \lambda\geq 80 , m\geq 2000d\log(n/\delta) , and \overline{\gamma}=40 . Consider the n -round interaction between ?? when P_{0} and Q are chosen to be standard normal, and a stochastic linear bandit environment \mathcal{E} specified by a closed action set \mathcal{X}\subset\mathbf{B}^{d}_{2} and an unknown parameter \theta_{\star}\in\mathbf{B}^{d}_{2} . Then, with probability at least 1-4\delta , the n -step regret R_{n} enjoys the bound R_{n}\leq C\sqrt{d\log(n/\delta)}\beta_{n-1}^{\delta}\left(\sqrt{dn\log\left(1+\frac{n}{d\lambda}\right)}+\sqrt{(n/\lambda+1)\log\left(\frac{\sqrt{n/\lambda+1}}{\delta}\right)}\right)\,, (6) where C>0 is a universal constant. 4.3 name=,restate=lowerBoundThm. Take \mathcal{X}=\mathbf{B}^{d}_{2} . Fix any law P_{0} on \mathbf{R}^{d} and suppose that m\leq d/2 . Then there exists a \theta_{\star}\in\mathbf{S}^{d-1}_{2} depending on P_{0} only, such that if ensemble sampling is initialised with (\zeta^{1},\dots,\zeta^{m})\sim P^{\otimes m}_{0} , any choice of \overline{\gamma},\lambda>0 , and the tie-breaking rule that for every t\geq 1 , \theta_{t}=0\implies X_{t}=0 , then \mathbf{P}\{\forall n\geq 1,R_{n}\geq n/4\}\geq 1/2. The second result, proved in ?? , shows that the ensemble size requirement in ?? is close to its minimum. From the first result, we see that if we set \lambda=80 (say) and m to be as small as possible given the constraint of ?? . From ?? we see that up to logarithmic-in- n factors, the regret bound scales as d^{3/2}\sqrt{n} , while the ensemble size scales as d\log(n) . This closes the gap to the regret of Thompson sampling in linear bandits, while keeping the ensemble size scaling only linearly with the dimension d and logarithmically with the horizon n . A few remarks are in order: First, there is a trade-off between the ensemble size m and the noise level (governed by \beta_{t-1}^{\delta}\overline{\gamma} here). In particular, by increasing m while keeping the noise level fixed, the effective noise level increases. Since increasing m incurs computational cost, while increasing the noise level does not, for the purposes of increasing the effective noise level, it is better to increase the noise level parameters while keeping m as small as possible. Second, 11 mentions that if one changes the algorithm to use max-over-ensemble action selection (i.e., selecting the action that maximizes the predicted reward over all models in the ensemble, instead of selecting the action according to a randomly selected model), then their proof techniques would yield a regret bound scaling as d^{3/2}\sqrt{n} , while keeping the ensemble size scaling with d\log(n) . The downside of max-over-ensemble action selection is that it is more expensive as it requires solving m linear maximization problems over the action set in each round, instead of just one. When this maximization is expensive (certain polytope action sets), it is better to use the random model selection approach of ?? . Our results imply that with random model selection, one can also achieve the d^{3/2}\sqrt{n} regret, while keeping the ensemble size scaling as d\log(n) . In our case, max-over-ensemble action selection would not yield further benefits: the “bonus” that we can achieve with this scales at best with \sqrt{\log(m)} , which is too small to be effective for the ensemble size regime we care about. 5 Proof of ?? When we omit details below, full proofs are deferred to the appendix. We start with a lemma extracted from the approach of 11 . For the proof, see ?? . 5.4 name=Self-normalized exceedance frequencies control regret,restate=exceedanceLemma. Fix p,\delta\in(0,1) , m,n\in\mathbf{N}_{+} , \overline{\gamma},\lambda\geq 1 . Assume that with probability 1-\delta , it holds that \min_{t\in[n]}\inf_{u\in\mathbf{S}^{d-1}_{2}}E_{t,m}(u,1/\overline{\gamma})\geq p, where for u\neq 0 , c>0 , E_{t,m}(u,c)=\frac{1}{m}\sum_{j=1}^{m}\mathbf{1}\left\{\langle u,S_{t-1}^{j}\rangle/\|u\|_{V_{t-1}}\geq c\right\}. Let \gamma_{t}^{\delta}=\sqrt{d}+\sqrt{\log(4m/\delta)}+\sqrt{2\log(4m/\delta)+d\log(1+t/(\lambda d))} . Then, with probability 1-4\delta , for all t\in[n] , R_{t}\;\leq\;\frac{2\overline{\gamma}}{p}\gamma^{\delta}_{t-1}\beta_{t-1}^{\delta}\left(2\sqrt{2dt\log\left(1+\frac{t}{d\lambda}\right)}+\sqrt{2(4t/\lambda+1)\log\left(\frac{\sqrt{4t/\lambda+1}}{\delta}\right)}\right)\,. The term \gamma_{t-1}^{\delta} is chosen so that with probability at least 1-\delta for all j\in[m] and t\in[n] , \|V_{t-1}^{-1/2}S_{t-1}^{j}\|\leq\gamma^{\delta}_{t-1} . The bound uses that S_{t-1}^{j} is a sum of the Gaussian prior \sqrt{\lambda}\zeta^{j} , which is handled using a standard Gaussian concentration bound, and the noise terms \sum_{s=1}^{t-1}X_{s}\xi_{s}^{j} , which are bounded using self-normalized martingales ( 1 ) . From this result, it is clear that the proof will be done if we establish that for m “not too large”, the exceedance frequencies E_{t,m}(u,c) for the self-normalized martingale transforms \langle u,S_{t-1}^{j}\rangle/\|u\|_{V_{t-1}^{-1}} are lower bounded by a constant uniformly over u\in\mathbf{S}^{d-1}_{2} and t\in[n] with high probability. The rest of the proof is devoted to establishing this. First, a covering argument can be used to show that it suffices to control the exceedance frequencies at a fixed direction u\in\mathbf{S}^{d-1}_{2} . To state a clean result, let \mathcal{E}_{P} denote the event that for all t\in[n] and j\in[m] , \|V_{t-1}^{-1/2}S_{t-1}^{j}\|\leq\gamma^{\delta}_{t-1} . A similar argument was used by 11 , but there only the process extrema are controlled, not exceedance fractions. 5.5 restate=fromFixedToUniform, name=From fixed to uniform direction. Assume that there exist p_{0}:(0,\infty)\to(0,1) such that for any fixed u\in\mathbf{S}^{d-1}_{2} , c>0 , 0
0 and \delta,p\in(0,1) , \varepsilon=2/(\overline{\gamma}L) , where L=2\gamma_{n-1}^{\delta}\sqrt{1+n/\lambda} . Then, if m\geq m_{0}(2/\overline{\gamma},(\delta/2)/(3/\varepsilon)^{d},p) , then with probability at least 1-\delta , for all u\in\mathbf{S}^{d-1}_{2} and all t\in[n] , E_{t,m}(u,1/\overline{\gamma})\geq p . Proof. The result follows from showing that the maps u\mapsto\langle u,S_{t-1}^{j}\rangle/\|u\|_{V_{t-1}^{-1}} are L -Lipschitz for all j\in[m] and all t\in[n] on an event of probability at least 1-\delta/2 , which we do in ?? . Then, a standard covering using an \varepsilon -net of size (3/\varepsilon)^{d} can be used to extend the fixed direction result to all directions. ∎ By the previous result, it suffices to control the exceedance frequencies at a fixed direction u\in\mathbf{S}^{d-1}_{2} . Hence, in what follows, we fix u\in\mathbf{S}^{d-1}_{2} and hide the dependence on it. We will find it useful to introduce the notation M_{t}=(\langle u,S_{t}^{j}\rangle)_{j=1}^{m}\,,\qquad t=0,1,\dots,n-1\,. (Deviating from our earlier notation, we will use M_{t,j} to denote the j th component of the vector M_{t} as this allows us to use linear algebra notation more easily.) Note that (M_{t})_{0\leq t\leq n-1} is an \mathbf{R}^{m} -valued, zero-mean martingale. In what follows, we study the self-normalized exceedance frequencies induced by this martingale. Recalling the definitions of S_{t}^{j} , we see that M_{t} is obtained from “mixing” m independent standard Gaussian noise processes: M_{t}=\sqrt{\lambda}\xi_{0}+\sum_{s=1}^{t}\langle u,X_{s}\rangle\xi_{s}\,, where, by slightly abusing notation, we denoted \xi_{0}=(\langle u,\zeta^{j}\rangle)_{j=1}^{m} and \xi_{s}=(\xi_{s}^{j})_{j=1}^{m} for s\geq 1 . Notably, while X_{s} may depend on \xi_{0},\dots,\xi_{s-1} , it is independent of \xi_{s} . Importantly, the mixing is diagonal in the sense that each component of the martingale is obtained by mixing only the corresponding component of the noise processes. In particular, in M_{t} , the variance of \xi_{s}^{j} is scaled by \langle u,X_{s}\rangle^{2} , but no “rotational” dependence is introduced between (\xi_{s}^{j})_{j=1}^{m} across j . Now, if we recall that at any fixed time t>0 , a standard Brownian motion gives rise to a standard normal random variable with variance equal to the time parameter t , we may view the process (M_{t})_{t\geq 1} as obtained by running m independent Brownian motions and reading out their values, sequentially, at the random times \|u\|_{V_{t}}^{2}=\lambda\|u\|^{2}+\sum_{s=1}^{t}\langle u,X_{s}\rangle^{2} . Indeed, imagine that we start by running m independent standard Brownian motions for a period of length t_{0}=\lambda . This gives rise to the prior term M_{0}=\sqrt{\lambda}\langle u,\zeta^{j}\rangle . Next, we continue each Brownian motion, independently of each other for a period of length \langle u,X_{1}\rangle^{2} . Reading out the values, we obtain M_{1} . Continuing, we eventually obtain all of M_{0},M_{1},\dots,M_{t} . The gain here is that now the problem of controlling the exceedance frequencies of the self-normalized martingale transforms is reduced to controlling the exceedance frequencies of m independent Brownian motions observed at random times. This is similar to switching from the “sequential” to the stacked reward model in bandits ( 14 ) . The astute reader will note that the Brownian motions are continued for each period, not restarted. Therefore, whether they are independent of each other, and whether they are even standard Brownian motions, requires a justification. Next, we show that indeed they are independent standard Brownian motions. We establish this for general diagonal martingale transforms of Gaussian noise, slightly generalizing our setting. If you have not seen the continuous-time martingale notation in a while, there is a short primer in ?? . An embedding result for diagonal martingale transforms of Gaussian noise Fix m\geq 1 . We say that an \mathbf{R}^{m} -valued process M_{t}=\sum_{s=0}^{t}U_{s}\xi_{s} is a diagonal martingale transform of a standard m -dimensional Gaussian noise if there exists a filtration (\mathcal{F}_{t})_{t\geq-1} such that the following hold: • (\xi_{s})_{s\geq 0} are i.i.d. \mathcal{N}(0,I_{m}) and \xi_{s} is independent of \mathcal{F}_{s-1} for each s\geq 0 , • U_{s}\in\mathbb{R}^{m\times m} is \mathcal{F}_{s-1} -measurable and diagonal for each s\geq 0 . (In our case, we can take \mathcal{F}_{-1} to be the trivial \sigma -algebra and U_{0}=\sqrt{\lambda}I_{m} .) 5.6 restate = theoremDiagGaussEmbedding, name = Diagonal Gaussian embedding. Fix a horizon n\in\mathbf{N} . Assume M_{t}=\sum_{s=0}^{t}\operatorname{diag}(D_{s})\xi_{s} is a diagonal martingale transform of a standard m -dimensional Gaussian noise, for 0\leq t\leq n-1 . Define the coordinate clocks A_{t,j}^{2}\;:=\;\sum_{s=0}^{t}D_{s,j}^{2},\qquad j\in[m]. Then, on an extension of the probability space, there exist independent standard Brownian motions W^{1},\dots,W^{m} such that for all t\in\{0,1,\dots,n-1\} and all j\in[m] , M_{t,j}\;=\;W^{j}\!\big(A_{t,j}^{2}\big). Proof sketch. The proof is based on the classical Dambis–Dubins–Schwarz (DDS) representation theorem ( ?? ) for continuous-time martingales. As explained above, the idea is to first embed each component M_{t,j} into a continuous-time martingale using pinned Brownian segments (see ?? below) and then apply the DDS theorem to obtain the desired Brownian motions. Then, Knight’s construction ( ?? ) can be used to ensure the independence of the Brownian motions. ∎ With ?? in hand, we can write the exceedance frequencies E_{t,m}(u,c) as E_{t,m}(u,c)=\frac{1}{m}\sum_{j=1}^{m}\mathbf{1}\left\{W^{j}\big(\|u\|_{V_{t-1}}^{2}\big)/\|u\|_{V_{t-1}}\geq c\right\}. Noting that \|u\|_{V_{t-1}}^{2}\in[\lambda,\lambda+n-1]\subset[\lambda,\lambda+n] for all t\in[n] , we then have \displaystyle\min_{t\in[n]}E_{t,m}(u,c)\geq\inf_{t\in[\lambda,\lambda+n]}\frac{1}{m}\sum_{j=1}^{m}\mathbf{1}\left\{W^{j}(t)/\sqrt{t}\geq c\right\}. (7) The final step is to control the expression on the right-hand side. Exceedance frequencies of Brownian motions For this, we present the following result: 5.7 restate = theoremExcBrownian, name = Time-uniform exceedance count for Brownian motions. Let W^{1},\dots,W^{m} be independent standard Brownian motions. Fix 0<\tau\leq\tau^{\prime}<\infty , positive constants c>0 and 0
0 , 0
0
such that if
m\geq Cd\ell
, then with probability at least
1-\delta
,
\min_{t\in[n]}\ \inf_{u\in\mathbb{S}^{d-1}_{2}}\ E_{t,m}\!\Big(u,\frac{1}{\overline{\gamma}}\Big)\ \geq\ \frac{1}{10}.
Proof sketch.
We use
??
to verify the premise of
??
with
p=1/10
and
c=1/20
. Lemma
5.5
then gives the desired
uniform conclusion, but requires checking its condition on
m
, which is expressed via
the threshold
m_{0}(\cdot)
from Proposition
5.8
. Evaluating this
condition leads to a log-inequality in
m
; solving it yields
m\geq Cd\ell
. See
??
.
∎
Proof of
??
.
Combining
??
and
??
reduces the proof to bounding
\gamma_{t-1}^{\delta}
, which is carried out in
??
(see
??
).
∎
The dependence on
1/p
in
??
is unavoidable: even at a fixed
time the exceedance count is binomial with mean
p
.
For readers curious about the exceedance problem itself,
??
offers a short discussion
of diagonal Gaussian martingale transforms that clarifies why the scalar-clock case is tractable and why the general
diagonal case is genuinely harder.
6
Conclusions
We provided a sharp frequentist analysis of Gaussian linear ensemble sampling.
Our main result,
??
, shows that with an ensemble size scaling linearly in the
dimension and logarithmically with the time horizon, ES achieves the canonical
\widetilde{O}(d^{3/2}\sqrt{n})
-type regret rate
with high probability in the standard stochastic linear bandit setting.
Technically, the proof reduces the core exploration question in ES to a time-uniform exceedance problem for
self-normalized diagonal Gaussian martingale transforms.
The key representation step,
??
, realizes such transforms as independent Brownian motions
evaluated at predictable quadratic-variation clocks, which enables us to translate exceedance control for ES into a
continuous-time exceedance statement.
A natural question is whether analogous time-uniform exceedance control can be obtained beyond Gaussian perturbations,
where the Brownian embedding in
??
is no longer available.
It would also be interesting to see whether one can combine the ideas from
2
with our techniques to get tighter regret bounds for action sets with favourable geometry.
Another direction is to understand how far the approach can be pushed for more complex model classes.
Besides these specific questions, we hope that our work will inspire others to explore the use of continuous-time embeddings in the analysis of sequential learning algorithms.
*Organisation of the appendix
The appendix is organized as follows:
First, we give the proof of
??
in
??
.
??
confirms the Lipschitz constant used in the proof of
??
to move from fixed to uniform control of exceedance fractions.
The next few sections contain material related to the continuous-time embedding and the Brownian exceedance control. We start these sections with a short primer on continuous-time martingales and related notions in
??
. This is followed by the proof of the embedding result for diagonal Gaussian martingale transforms,
??
, in
??
.
In the next section,
??
, we use the embedding to reduce the exceedance control problem for ES to a time-uniform exceedance control problem for Brownian motions. This finishes the development of the main continuous-time tools.
The next two sections contain proofs needed to finish the proof of
??
.
In
??
, we prove
??
, used in the proof of
??
.
In
??
, we give a bound on the term
\gamma_{t-1}^{\delta}
used in
??
.
In
??
, we offer a short discussion of diagonal Gaussian martingale transforms that clarifies why the scalar-clock case is tractable and why the general diagonal case is genuinely harder.
In the last section,
??
, we show that with only
d/2
ensemble members, the regret of ES is linear with constant probability.
Appendix A
Exceedance fraction to regret control (proof of
??
)
Here, we prove the following reduction from exceedance frequencies for self-normalised ensemble noise processes to the regret of ensemble sampling, itself used to prove
??
.
\exceedanceLemma
*
The proof is an application of the "master regret bound" of
11
, which we now state.
??
gives a schematic illustration of the property we are after.
A.10
Master regret bound,
11
.
Fix
\delta\in(0,1)
,
\lambda\geq 1
and an integer
n\geq 1
. Let
(\mathcal{F}_{t})_{t\geq 1}
be a filtration. Let
(\theta_{t})_{t\geq 1}
be a
(\mathcal{F}_{t})
-adapted
\mathbf{R}^{d}
-valued sequence and suppose that
(\forall t\geq 1)\qquad X_{t}\in\argmax_{x\in\mathcal{X}}\langle x,\theta_{t}\rangle\,.
For each
t\geq 1
, let
V_{t-1}=\lambda I+\sum_{s=1}^{t-1}X_{s}X_{s}^{\mkern-1.5mu\mathsf{T}}
and let
\hat{\theta}_{t-1}
be the usual ridge regression estimate of
\theta_{\star}
, which we assume to be
\mathcal{F}_{t-1}
-measurable. Let
(b_{t-1})_{t\geq 1}
be a
(\mathcal{F}_{t})
-predictable sequence of nonnegative random variables such that:
1.
the event
\mathcal{E}=\{\forall t\leq n\,,\ \|\theta_{t}-\hat{\theta}_{t-1}\|_{V_{t-1}}\leq b_{t-1}\}
satisfies
\mathbf{P}\{\mathcal{E}^{\complement}\}\leq\delta
; and
2.
the event
\mathcal{E}_{\star}=\{\forall t\leq n\,,\ \|\theta_{\star}-\hat{\theta}_{t-1}\|_{V_{t-1}}\leq b_{t-1}\}
satisfies
\mathbf{P}\{\mathcal{E}_{\star}^{\complement}\}\leq\delta
.
Let
(\mathcal{A}_{t})
be a filtration on the same probability space with
(\forall t\geq 1)\qquad\mathcal{F}_{t-1}\subset\mathcal{A}_{t-1}\subset\mathcal{F}_{t}\,,
and for each
t\geq 1
, define the
\mathcal{A}_{t-1}
-conditional probability of optimism
p_{t-1}=\mathbf{P}\{\langle\theta_{t},X_{t}\rangle\geq\langle x_{\star},\theta_{\star}\rangle\mid\mathcal{A}_{t-1}\}\,.
Then, on an event
\overline{\mathcal{E}}\subset\mathcal{E}\cap\mathcal{E}_{\star}
with
\mathbf{P}\{\overline{\mathcal{E}}\}\geq 1-3\delta
, for all
\tau\in[n]
, the
\tau
-step regret associated with the action sequence
(X_{t})_{t\geq 1}
satisfies
R_{\tau}\leq 2\max_{i\in[\tau]}\frac{b_{i-1}}{p_{i-1}}\left(2\sqrt{2d\tau\log\left(1+\frac{\tau}{d\lambda}\right)}+\sqrt{2(4\tau/\lambda+1)\log\left(\frac{\sqrt{4\tau/\lambda+1}}{\delta}\right)}\right)\,.
(9)
Proof of
??
.
For each
t\geq 1
, we identify
\theta_{t}=\theta_{t-1}^{J_{t}}
and take
b_{t-1}=\overline{\gamma}\gamma_{t-1}^{\delta}\beta_{t-1}^{\delta}
. The result will hold on the
1-4\delta
event given by the intersection of the event of the master theorem and the event where the uniform lower bound on the exceedance fraction holds. We will lower bound each
p_{t-1}
by
p
and use that
(b_{t-1})
is nondecreasing to bound
\max_{i\in[t]}b_{i-1}\leq b_{t-1}
.
First, we confirm that our choice of
(b_{t-1})_{t\geq 1}
leads to the needed properties for
\mathcal{E}^{\complement}
and
\mathcal{E}_{\star}^{\complement}
. Recall that for every
j\in[m]
,
\theta^{j}_{t-1}=\hat{\theta}_{t-1}+\overline{\gamma}\beta_{t-1}^{\delta}V_{t-1}^{-1}S^{j}_{t-1}\,.
Therefore, for every
j\in[m]
,
\|\hat{\theta}_{t-1}-\theta_{t-1}^{j}\|_{V_{t-1}}=\overline{\gamma}\beta_{t-1}^{\delta}\|S_{t-1}^{j}\|_{V_{t-1}^{-1}}\leq\gamma\beta_{t-1}^{\delta}(\|\zeta^{j}\|+\|\sum_{s=1}^{t-1}\xi^{j}_{s}X_{s}\|_{V_{t-1}^{-1}})\,.
Now, since
\zeta^{1},\dots,\zeta^{m}
are standard Gaussian random vectors on
\mathbf{R}^{d}
, by Gaussian concentration and the union bound,
\mathbf{P}\{\exists j\in[m]\colon\|\zeta^{j}\|>\sqrt{d}+\sqrt{2\log(4m/\delta)}\}\leq\delta/2
. On the other hand, by the self-normalised concentration inequality of
1
and a union bound over
j\in[m]
, we also have that
\mathbf{P}\{\exists t\geq 1,\,\exists j\in[m]\colon\|\sum_{s=1}^{t-1}\xi^{j}_{s}X_{s}\|_{V_{t-1}^{-1}}>\sqrt{2\log(4m/\delta)+d\log(1+(t-1)/(\lambda d))}\}\leq\delta/2\,.
(See, in particular, Theorem 20.4 and Note 20.2.1 of
14
). Taken together, and noting that
\theta_{t}\in\{\theta_{t-1}^{1},\dots,\theta^{m}_{t-1}\}
, these yield that
\mathbf{P}\{\mathcal{E}^{\complement}\}\leq\delta
. Moreover, since
\overline{\gamma}\gamma_{t-1}^{\delta}\geq\overline{\gamma}\sqrt{d}\geq 1\,,
we have that
b_{t-1}\geq\beta_{t-1}^{\delta}
, and therefore
\mathbf{P}\{\mathcal{E}_{\star}^{\complement}\}\leq\delta
by
??
.
We define the filtrations
(\mathcal{F}_{t})
and
(\mathcal{A}_{t})
by taking
\mathcal{F}_{t}=\sigma(\zeta^{1},\dots,\zeta^{m})\vee\sigma((X_{s},Y_{s},J_{s},\xi^{1}_{s},\dots,\xi^{m}_{s})\colon s\leq t)\,,
and
\mathcal{A}_{t}=\sigma(\xi_{t+1}^{1},\dots,\xi_{t+1}^{m})\vee\mathcal{F}_{t}
, where
\vee
denotes the join of
\sigma
-algebras. The nesting property and the measurability requirements on the processes
(\theta_{t})
,
(b_{t-1})
,
(\hat{\theta}_{t-1})
, are met by construction.
To conclude, we will establish that on
\mathcal{E}_{\star}
, for all
t\geq 1
,
p_{t-1}\geq\min_{t\in[n]}\inf_{u\in\mathbf{S}^{d-1}_{2}}E_{t,m}(u,1/\overline{\gamma})\,,
with the result then following by the union bound over
\overline{\mathcal{E}}
and the event where the right-hand side is lower-bounded by
p
. For this, fix
t\in[n]
. Observe that by the choice of
X_{t}
,
\langle\theta_{t},X_{t}\rangle\geq\langle\theta_{t},x_{\star}\rangle
. On
\mathcal{E}_{\star}
,
\langle\theta_{\star}-\hat{\theta}_{t-1},x_{\star}\rangle\leq\|\theta_{\star}-\hat{\theta}_{t-1}\|_{V_{t-1}}\|x_{\star}\|_{V_{t-1}^{-1}}\leq\beta_{t-1}^{\delta}\|x_{\star}\|_{V_{t-1}^{-1}}\,.
Hence, on
\mathcal{E}_{\star}
,
\langle\theta_{t}-\hat{\theta}_{t-1},x_{\star}\rangle\geq\beta_{t-1}^{\delta}\|x_{\star}\|_{V_{t-1}^{-1}}\implies\langle\theta_{t},X_{t}\rangle\geq\langle\theta_{\star},x_{\star}\rangle\,.
If
x_{\star}=0
, then
0\in\mathcal{X}
, and therefore
\langle\theta_{t},X_{t}\rangle=\max_{x\in\mathcal{X}}\langle x,\theta_{t}\rangle\geq 0=\langle\theta_{\star},x_{\star}\rangle
, so
p_{t-1}=1
and the result holds (indeed, without the need for the
1/p
factor). Assume henceforth that
x_{\star}\neq 0
and define
u_{\star}=V_{t-1}^{-1}x_{\star}
. Then
\|u_{\star}\|_{V_{t-1}}=\|x_{\star}\|_{V_{t-1}^{-1}}
, and using
\theta_{t}=\theta_{t-1}^{J_{t}}
we obtain
\langle\theta_{t}-\hat{\theta}_{t-1},x_{\star}\rangle=\overline{\gamma}\beta_{t-1}^{\delta}\langle V_{t-1}^{-1}S^{J_{t}}_{t-1},x_{\star}\rangle=\overline{\gamma}\beta_{t-1}^{\delta}\langle V_{t-1}^{-1/2}S^{J_{t}}_{t-1},u_{\star}\rangle\,.
Therefore,
\frac{\langle S_{t-1}^{J_{t}},u_{\star}\rangle}{\|u_{\star}\|_{V_{t-1}}}\geq\frac{1}{\overline{\gamma}}\implies\langle\theta_{t},X_{t}\rangle\geq\langle\theta_{\star},x_{\star}\rangle\,.
Now note that
\theta_{t-1}^{1},\dots,\theta^{m}_{t-1}
and
u_{\star}
are
\mathcal{A}_{t-1}
-measurable and that conditionally on
\mathcal{A}_{t-1}
,
J_{t}
is uniform on
[m]
. Thus,
\displaystyle p_{t-1}
\displaystyle=\mathbf{P}\{\langle\theta_{t},X_{t}\rangle\geq\langle x_{\star},\theta_{\star}\rangle\mid\mathcal{A}_{t-1}\}
\displaystyle\geq\mathbf{P}\{\langle S^{J_{t}}_{t-1},u_{\star}\rangle/\|u_{\star}\|_{V_{t-1}}\geq 1/\overline{\gamma}\mid\mathcal{A}_{t-1}\}
\displaystyle=E_{t,m}(u_{\star},1/\overline{\gamma})
\displaystyle\geq\min_{t\in[n]}\inf_{u\in\mathbf{R}^{d}\setminus\{0\}}E_{t,m}(u,1/\overline{\gamma})
\displaystyle=\min_{t\in[n]}\inf_{u\in\mathbf{S}^{d-1}_{2}}E_{t,m}(u,1/\overline{\gamma})\,,
where the final equality uses that
E_{t,m}(u,c)
is invariant under rescaling of
u
.
∎
Figure 1:
Schematic geometry for
\mathcal{X}=\mathbf{B}^{d}_{2}
:
the confidence ellipsoid (solid) is off-center and intersects level sets of the optimal reward
J(\theta)=\max_{x\in\mathcal{X}}\langle x,\theta\rangle=\|\theta\|
(dashed).
For illustration purposes,
a sample of
m
perturbed model parameters is drawn from a Gaussian
with covariance inflated by about
1.2\times
relative to the ellipsoid axes;
those whose optimal reward exceeds that of the true parameter are highlighted as optimistic (red coloured dots).
The master regret bound states that if we can keep the exceedance frequency of optimistic samples above a constant, then the regret will be under control.
The difficulty with ensemble sampling is that, unlike in Thompson sampling, the model parameters are not freshly drawn in each time step but evolve in a correlated fashion over time. As such, controlling the exceedance frequencies is more challenging, and this is the main technical contribution of the paper.
Appendix B
Lipschitzness of self-normalised martingale on unit sphere (proof of
??
)
\fromFixedToUniform
*
Proof of
??
.
To argue for Lipschitzness for a fixed
u\in\mathbf{S}^{d-1}_{2}
,
we separate out the self-normalized
V_{t-1}^{-1/2}S_{t-1}^{j}
term from the rest:
\frac{\langle u,S_{t-1}^{j}\rangle}{\|u\|_{V_{t-1}^{-1}}}=\left\langle\frac{V_{t-1}^{1/2}u}{\|V_{t-1}^{1/2}u\|},V_{t-1}^{-1/2}S_{t-1}^{j}\right\rangle\,.
By a Cauchy–Schwarz argument, the Lipschitz constant of the map under investigation is at most
the product of
\|V_{t-1}^{-1/2}S_{t-1}^{j}\|
and the Lipschitz constant of the map
u\mapsto V_{t-1}^{1/2}u/\|V_{t-1}^{1/2}u\|
.
By the choice of
\gamma_{t-1}^{\delta}
, a union bound, with probability at least
1-\delta/2
,
for all
t\in[n]
and
j\in[m]
,
\|V_{t-1}^{-1/2}S_{t-1}^{j}\|\leq\gamma_{n}^{\delta}
.
As to the Lipschitzness of the second map,
the inequality
\left\|\frac{a}{\|a\|}-\frac{b}{\|b\|}\right\|\leq\frac{2\|a-b\|}{\min\{\|a\|,\|b\|\}}
that holds for any
a,b\in\mathbf{R}^{d}
nonzero vectors gives that this map
is
2\|V_{t-1}^{1/2}\|/\sqrt{\lambda}
-Lipschitz on
\mathbf{S}^{d-1}_{2}
.
Now, since
V_{t-1}
is positive definite,
\|V_{t-1}^{1/2}\|=\sqrt{\|V_{t-1}\|}
and a standard calculation gives that
\|V_{t-1}\|\leq\lambda+\sum_{s=1}^{t-1}\|X_{s}\|^{2}\leq\lambda+n
.
Putting things together and a union bound gives the result.
∎
Appendix C
Continuous-time preliminaries
We will use a few standard notions from continuous-time martingale theory, and this short note fixes notation. First,
a\wedge b
denotes the minimum of
a
and
b
.
Many continuous-time texts index time with subscripts; we follow that convention in this preliminaries section and in quoted results.
In our own proofs we often write the continuous-time variable as an argument (e.g.,
W(t)
) to avoid clashes with discrete-time subscripts; we mix these notations and hope the context makes the time variable clear (see, e.g., the OU lemma).
For this subsection only, we write
(\mathcal{F}_{t})_{t\geq 0}
for the continuous-time filtration; it is unrelated to the discrete-time
\mathcal{F}_{t}
used elsewhere.
For the definitions below we only need that
(\mathcal{F}_{t})
is nondecreasing; if desired, one can assume the usual conditions (right-continuity and completeness).
An adapted process
M=(M_{t})_{t\geq 0}
is one with
M_{t}
being
\mathcal{F}_{t}
-measurable for each
t
.
A (continuous-time) martingale is an adapted process with
\mathbf{E}|M_{t}|<\infty
for all
t
and
\mathbf{E}[M_{t}\mid\mathcal{F}_{s}]=M_{s}
for
s\leq t
.
A continuous martingale is a martingale with continuous paths.
A local martingale is an adapted process for which there exists an increasing sequence of stopping times
\tau_{n}\uparrow\infty
such that, for each
n
, the stopped process
(M_{t\wedge\tau_{n}})_{t\geq 0}
is a martingale with respect to the same filtration; this is weaker than being a martingale and captures processes that behave like martingales up to larger and larger random horizons. Local martingales are the natural class in continuous-time analysis.
A continuous local martingale is a local martingale with continuous paths.
A standard Brownian motion
W=(W_{t})_{t\geq 0}
has
W_{0}=0
, continuous paths, independent, Gaussian increments with
W_{t}-W_{s}\sim\mathcal{N}(0,t-s)
for
0\leq s\leq t
; in particular, it is a martingale (hence a local martingale).
For Gaussian processes, the law is determined by the covariance function; in particular, a centered Gaussian process with covariance
\mathbf{E}[B_{s}B_{t}]=s\wedge t
is a standard Brownian motion.
For a continuous local martingale
M
, its quadratic variation
\langle M\rangle_{t}
can be defined as the limit in probability of sums of squared increments along partitions of
[0,t]
; it is an increasing process and the continuous-time analogue of accumulated conditional variance (indeed,
M_{t}^{2}-\langle M\rangle_{t}
is a local martingale).
For Brownian motion,
\langle W\rangle_{t}=t
.
For two continuous local martingales
M,N
, the covariation
\langle M,N\rangle_{t}
is defined similarly via products of increments, and we write
\langle M,N\rangle
for the process
(\langle M,N\rangle_{t})_{t\geq 0}
and
MN
for the pointwise product process
(M_{t}N_{t})_{t\geq 0}
; strong orthogonality means
\langle M,N\rangle
is identically zero as a process.
For background and proofs, see
24
for Brownian motion and filtrations,
24
for martingales,
24
for quadratic variation and covariation, and
24
for time changes and the DDS/Knight results.
Appendix D
A Representation Result for Diagonal Gaussian Martingale Transforms
\theoremDiagGaussEmbedding
*
We start with some auxiliary results.
D.11
Pinned Brownian segment.
Fix
\Delta>0
and let
Z\sim\mathcal{N}(0,\Delta)
. On an extension of the probability space,
there exists a standard Brownian motion
(B_{s})_{0\leq s\leq\Delta}
such that
B_{\Delta}=Z
.
Proof.
Let
\widetilde{B}
be a standard Brownian motion on
[0,\Delta]
, independent of
Z
, and define for
t\in[0,\Delta]
,
B(t)\;:=\;\frac{t}{\Delta}Z\;+\;(1-\frac{t}{\Delta})\;\widetilde{B}(\Delta).
Then
B(0)=0
and
B(\Delta)=Z
. The process
B
is continuous and Gaussian because it is an affine transform of the
jointly Gaussian family
(Z,(\widetilde{B}(t))_{t\in[0,\Delta]})
. Moreover, for
0\leq s\leq t\leq\Delta
,
\displaystyle\Cov(B(s),B(t))
\displaystyle=\frac{st}{\Delta^{2}}\Var Z+\Cov\!\Big(\widetilde{B}(s)-\frac{s}{\Delta}\widetilde{B}(\Delta),\,\widetilde{B}(t)-\frac{t}{\Delta}\widetilde{B}(\Delta)\Big)
\displaystyle=\Cov(\widetilde{B}(s),\widetilde{B}(t))=s\wedge t\,.
Since
B
has a centered Gaussian law with covariance
s\wedge t
, it is a standard Brownian motion.
∎
D.0
.
??
may be viewed as sampling
Z
and then sampling (conditionally on
Z
)
a Brownian bridge from
0
to
Z
over
[0,\Delta]
(i.e., a pinned Brownian segment).
D.13
Dambis–Dubins–Schwarz
24
, Ch. V, Thm. 1.6–1.7
.
Let
(M_{t},\mathcal{F}_{t})_{t\geq 0}
be a continuous local martingale with
M_{0}=0
and quadratic variation
\langle M\rangle_{t}
. Define the right-continuous inverse
\tau(s)\ :=\ \inf\{t\geq 0:\ \langle M\rangle_{t}\geq s\},\qquad s\geq 0\,,
and set
\tau(\infty):=\sup_{s\geq 0}\tau(s)
.
Then, there exists an enlargement of the filtered
probability space
(\Omega,\mathcal{F},(\mathcal{F}_{\tau(s)})_{s\geq 0})
and a standard Brownian motion
(W_{t})_{t\geq 0}
on the enlarged space such that for any
s\geq 0
,
W_{s}\ =\ M_{\tau(s)}\text{ on the event }\{0\leq s<\langle M\rangle_{\infty}\}\cup\{s=\langle M\rangle_{\infty}<\infty\}\,\,,
Consequently, for any
t\geq 0
,
\displaystyle M_{t}\ =\ W_{\langle M\rangle_{t}}\text{ on the event }\{0\leq t<\tau(\langle M\rangle_{\infty})\}\cup\{t=\tau(\langle M\rangle_{\infty}),\,\langle M\rangle_{\infty}<\infty\},
(10)
where for the last display
we let
M_{\infty}:=\lim_{t\to\infty}M_{t}
on the set
\{\langle M\rangle_{\infty}<\infty\}
and is defined arbitrarily otherwise.
Above,
M_{\infty}
is well-defined by Proposition IV.1.26 of
24
. The identity (
10
)
follows from elementary arguments.
The “enlargement” is only needed to handle the case where
\langle M\rangle_{\infty}<\infty
with positive probability.
Intuitively, the local martingale determines the Brownian motion up to the time
\langle M\rangle_{\infty}
, after which we just extend the Brownian motion independently.
In our case,
\langle M\rangle_{\infty} \;0,
so that
1-\Phi(c+3\varepsilon)=4p
.
Since
\varepsilon>0
, we can choose a discretization
h\in(0,1]
small enough so that
e^{-h/2}(c+3\varepsilon)\geq c+2\varepsilon\qquad\text{and}\qquad 4\exp\!\Big\{-\frac{2\varepsilon^{2}}{e^{h}-1}\Big\}\leq\frac{1}{2}.
(13)
Let
\sigma:=\log\tau
,
\sigma^{\prime}:=\log\tau^{\prime}
, and
K\;:=\;\Big\lceil\frac{\sigma^{\prime}-\sigma}{h}\Big\rceil\;=\;\Big\lceil\frac{\log(\tau^{\prime}/\tau)}{h}\Big\rceil,\qquad s_{k}:=\sigma+kh\quad(k=0,1,\dots,K),
so that
[\sigma,\sigma^{\prime}]\subseteq\bigcup_{k=0}^{K-1}[s_{k},s_{k+1}]
.
For each
j\in[m]
, define the time-changed process
U_{j}(s)\;:=\;e^{-s/2}W^{j}(e^{s}),\qquad s\in\mathbb{R}.
Then
(U_{j})_{j=1}^{m}
are independent standard Ornstein–Uhlenbeck processes (see
??
), and for
t\in[\tau,\tau^{\prime}]
(with
s=\log t\in[\sigma,\sigma^{\prime}]
),
W^{j}(t)\geq c\sqrt{t}\;\Longleftrightarrow\;U_{j}(\log t)\geq c.
Thus it suffices to prove that with probability at least
1-\delta
,
\forall s\in[\sigma,\sigma^{\prime}]:\quad\#\{j\in[m]:U_{j}(s)\geq c\}\geq pm.
For each
k\in\{0,\dots,K-1\}
define
S_{k}^{j}:=\mathbf{1}\Big\{\forall s\in[s_{k},s_{k+1}]:U_{j}(s)\geq c\Big\},\qquad S_{k}:=\sum_{j=1}^{m}S_{k}^{j}.
If we show that
S_{k}\geq pm
for all
k
, then the desired bound holds for all
s\in[\sigma,\sigma^{\prime}]
,
hence for all
t\in[\tau,\tau^{\prime}]
.
Fix
k\in\{0,\dots,K-1\}
. By
??
, for any
u\in[0,h]
,
U_{j}(s_{k}+u)\;=\;e^{-u/2}U_{j}(s_{k})+\widetilde{U}_{j,k}(u),
where
\widetilde{U}_{j,k}
is an OU process started at
0
at time
0
, independent of
U_{j}(s_{k})
.
Define the event indicators
A_{k}^{j}:=\mathbf{1}\{U_{j}(s_{k})\geq c+3\varepsilon\},\qquad E_{k}^{j}:=\mathbf{1}\Big\{\forall u\in[0,h]:\widetilde{U}_{j,k}(u)\geq-2\varepsilon\Big\}.
By (
13
), for all
u\in[0,h]
,
e^{-u/2}(c+3\varepsilon)-2\varepsilon\;\geq\;e^{-h/2}(c+3\varepsilon)-2\varepsilon\;\geq\;c,
so
A_{k}^{j}E_{k}^{j}=1
implies
S_{k}^{j}=1
. Hence, writing
Z_{k}^{j}:=A_{k}^{j}E_{k}^{j}
and
Z_{k}:=\sum_{j=1}^{m}Z_{k}^{j}
,
we have
S_{k}\geq Z_{k}
.
Now
\mathbb{P}(A_{k}^{j}=1)=\mathbb{P}(N(0,1)\geq c+3\varepsilon)=1-\Phi(c+3\varepsilon)=4p
.
Let
q:=\mathbb{P}(E_{k}^{j}=0)
(this does not depend on
j,k
). Since
A_{k}^{j}
and
E_{k}^{j}
are independent
(and independent across
j
),
Z_{k}\sim\mathrm{Binomial}(m,r)
with
r=(4p)(1-q).
We upper bound
q
.
By
??
, we may represent an OU process started at
0
as
\widetilde{U}_{j,k}(u)=e^{-u/2}\widetilde{W}_{j,k}(e^{u}-1)
for a standard Brownian motion
\widetilde{W}_{j,k}
.
Therefore,
\displaystyle q
\displaystyle=\mathbb{P}\Big(\inf_{0\leq u\leq h}\widetilde{U}_{j,k}(u)<-2\varepsilon\Big)\;\leq\;\mathbb{P}\Big(\sup_{0\leq u\leq h}|\widetilde{U}_{j,k}(u)|\geq 2\varepsilon\Big)
\displaystyle\leq\mathbb{P}\Big(\sup_{0\leq t\leq e^{h}-1}|\widetilde{W}_{j,k}(t)|\geq 2\varepsilon\Big)\;\leq\;4\exp\!\Big\{-\frac{(2\varepsilon)^{2}}{2(e^{h}-1)}\Big\}\;=\;4\exp\!\Big\{-\frac{2\varepsilon^{2}}{e^{h}-1}\Big\}\,,
where we used
??
for the last inequality.
By (
13
),
q\leq\tfrac{1}{2}
, hence
r\geq(4p)\cdot\tfrac{1}{2}=2p
.
By a Chernoff bound for binomials,
\mathbb{P}\Big(Z_{k}\leq\frac{rm}{2}\Big)\;\leq\;\exp\!\Big\{-\frac{rm}{8}\Big\}\;\leq\;\exp\!\Big\{-\frac{pm}{4}\Big\},
where we used
r\geq 2p
. On the event
\{Z_{k}\geq rm/2\}
we have
Z_{k}\geq pm
, hence also
S_{k}\geq pm
.
Finally, by a union bound over
k=0,\dots,K-1
,
\mathbb{P}\Big(\exists k\in\{0,\dots,K-1\}:S_{k} 0
for all
t\in\{0,1,\dots,n-1\}
and
j\in[m]
. Fix
c>0
,
\delta\in(0,1)
and
0 1
and suppose that
X_{1},\dots,X_{t-1}\in U
.
Then both
\sum_{s=1}^{t-1}X_{s}Y_{s}\in U
and
\sum_{s=1}^{t-1}X_{s}\xi_{s}^{j}\in U
.
Moreover,
V_{t-1}=\lambda I+\sum_{s=1}^{t-1}X_{s}X_{s}^{\mkern-1.5mu\mathsf{T}}
maps
U\mapsto U
.
Hence, its inverse
V_{t-1}^{-1}
also maps
U\mapsto U
because the restriction of
V_{t-1}
to
U
is invertible.
It follows that
\hat{\theta}_{t-1}\in U
and for each
j\in[m]
,
V_{t-1}^{-1}S_{t-1}^{j}\in U
. Hence,
\theta^{j}_{t-1}=\hat{\theta}_{t-1}+\overline{\gamma}\beta_{t-1}^{\delta}V_{t-1}^{-1}S_{t-1}^{j}\in U
also holds.
Since the action set is
\mathcal{X}=\mathbf{B}^{d}_{2}
,
X_{t}=\theta_{t-1}^{J_{t}}/\|\theta_{t-1}^{J_{t}}\|
or
X_{t}=0
almost surely, and so
X_{t}\in\operatorname{span}\{\theta_{t-1}^{1},\dots,\theta^{m}_{t-1}\}\subset U\quad\text{almost surely.}
The claim follows by induction.
∎
Next, we will need the upcoming corollary to this claim to move from spans to regret.
I.22
.
Let
U\subset\mathbf{R}^{d}
be a deterministic linear subspace with
\dim(U)=k\leq d/2
and let
V
be a random vector distributed uniformly on
\mathbf{S}^{d-1}_{2}
. Then
\mathbf{P}\{\|\Pi_{U}V\|^{2}\leq 1/2\}\geq 1/2\,.
Proof.
Without loss of generality assume that
U=\operatorname{span}\{e_{1},\dots,e_{k}\}
. Write
V=G/\|G\|
for a standard normal vector
G
on
\mathbf{R}^{d}
. Then
\|\Pi_{U}V\|^{2}=\frac{\|\Pi_{U}G\|^{2}}{\|G\|^{2}}=\frac{\sum_{i=1}^{k}G_{i}^{2}}{\sum_{i=1}^{k}G_{i}^{2}+\sum_{j=k+1}^{d}G_{j}^{2}}=:\frac{A}{A+B}\,,
where
A\sim\chi^{2}_{k}
,
B\sim\chi^{2}_{d-k}
and
A
and
B
are independent. Write
B=B_{1}+B_{2}
where
B_{1}\sim\chi^{2}_{k}
and
B_{2}\sim\chi^{2}_{d-2k}
are independent. Then
\mathbf{P}\bigg\{\frac{A}{A+B}\leq\frac{1}{2}\bigg\}=\mathbf{P}\{A\leq B\}\geq\mathbf{P}\{A\leq B_{1}\}=1/2\,,
where the final equality uses that
A
and
B_{1}
are independent and have the same law.
∎
I.23
.
Let
U\subset\mathbf{R}^{d}
be any random linear subspace of
\mathbf{R}^{d}
with
\dim(U)\leq d/2
. Then there exists a deterministic
\theta_{\star}\in\mathbf{S}^{d-1}_{2}
such that
\mathbf{P}\{\|\Pi_{U}\theta_{\star}\|^{2}\leq 1/2\}\geq 1/2\,,
where
\Pi_{U}
denotes the orthogonal projection onto
U
.
Proof.
Let
V
be a uniform random vector on
\mathbf{S}^{d-1}_{2}
independent of
U
. Conditional on
U
, apply
??
with
k=\dim(U)\leq d/2
and take expectation to get that
\mathbf{P}\{\|\Pi_{U}V\|^{2}\leq 1/2\}=\mathbf{E}_{U}[\mathbf{P}\{\|\Pi_{U}V\|^{2}\leq 1/2\mid U\}]\geq 1/2\,.
On the other hand, since we also have that
\mathbf{P}\{\|\Pi_{U}V\|^{2}\leq 1/2\}=\mathbf{E}_{V}[\mathbf{P}\{\|\Pi_{U}V\|^{2}\leq 1/2\mid V\}]\,.
Therefore, there exists a
\theta_{\star}\in\mathbf{S}^{d-1}_{2}
such that
\mathbf{P}\{\|\Pi_{U}\theta_{\star}\|^{2}\leq 1/2\}\geq 1/2
.
∎
Proof of
??
.
Let
U=\operatorname{span}\{\zeta^{1},\dots,\zeta^{m}\}
and let
\Pi_{U}
denote the orthogonal projection onto
U
. Since
\dim U\leq m\leq d/2
, by
??
, there exists a
\theta_{\star}\in\mathbf{S}^{d-1}_{2}
such that
\mathbf{P}\{\|\Pi_{U}\theta_{\star}\|^{2}\leq 1/2\}\geq 1/2
. Take this
\theta_{\star}
to be the instance parameter. On the aforementioned event, since
X_{1},X_{2},\dots\in U\cap\mathbf{B}^{d}_{2}
almost surely (
??
),
R_{n}=n-\sum_{t=1}^{n}\langle X_{t},\theta_{\star}\rangle\geq n(1-\sup_{u\in U\cap\mathbf{B}^{d}_{2}}\langle u,\theta_{\star}\rangle)=n(1-\|\Pi_{U}\theta_{\star}\|)\geq(1-\sqrt{2}/2)n\geq n/4\,.\qed