📊 statistics

Sharp analysis of linear ensemble sampling

This paper provides a sharp analysis of linear ensemble sampling in stochastic linear bandits, demonstrating that it achieves $\tilde O(d^{3/2}\sqrt n)$ high-probability regret with an ensemble size of $m=\Theta(d\log n)$ by leveraging a novel continuous-time perspective that reduces the problem to time-uniform exceedance bounds for independent Brownian motions.

Original authors: David Janz, Arya Akhavan, Csaba Szepesvári

Published 2026-06-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: David Janz, Arya Akhavan, Csaba Szepesvári

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Core Problem: The "Blind Chef" Dilemma

Imagine you are a chef in a restaurant with an infinite number of potential recipes (actions). You want to find the one recipe that customers love the most (the optimal action). However, you don’t know the secret ingredient mix (the true parameter $\theta^*$ ) that makes a dish delicious.

Every time you serve a dish, you get feedback (a rating), but it’s noisy. Maybe the customer had a bad day, or the lighting was dim. This is called a Stochastic Linear Bandit problem. The "Linear" part means the taste depends on a simple combination of ingredients, but you have to figure out the right weights for those ingredients through trial and error.

The goal is to minimize Regret. Regret is the difference between the total happiness you could have created if you knew the perfect recipe from day one, versus the happiness you actually created while figuring it out. You want this regret to be as small as possible.

The Strategy: Ensemble Sampling (The "Committee of Chefs")

One popular strategy to solve this is called Ensemble Sampling (ES). Instead of having one chef guessing the recipe, you have a committee of $m$ chefs (an "ensemble").

Here is how it works:

Diverse Guesses: Each chef in the committee starts with a slightly different, random guess about the secret ingredients.
Learning with Noise: As they cook, they don’t just look at the customer ratings. They also add a little bit of "random static" or noise to their data. This forces them to explore different possibilities rather than just sticking to what seems safe.
Random Selection: In every round, you pick one chef from the committee at random. That chef chooses the recipe to serve based on their current best guess.

The appeal of this method is that it’s computationally cheap. You don’t need to calculate complex probabilities for every single possibility; you just train a few models and pick one.

The Previous Problem: The "Gap"

For a long time, researchers knew that a different method called Thompson Sampling was the gold standard. It achieved a very low regret rate (specifically, proportional to $d^{3/2}\sqrt{n}$ , where $d$ is the number of ingredients and $n$ is the number of days).

However, when people analyzed Ensemble Sampling, they found it was slightly worse. The best previous proofs showed that Ensemble Sampling had a higher regret (proportional to $d^{5/2}\sqrt{n}$ ). This extra factor of $d$ (the number of ingredients) was a "gap." It suggested that Ensemble Sampling was less efficient than Thompson Sampling, especially when there were many ingredients to consider.

The Paper’s Big Discovery: Closing the Gap

This paper proves that Ensemble Sampling is actually just as good as Thompson Sampling, provided you use the right amount of "noise" and have a committee of the right size.

The authors show that if you have a committee size of roughly $m \approx d \log(n)$ (which is small and efficient), Ensemble Sampling achieves that same optimal regret rate of $d^{3/2}\sqrt{n}$ . They closed the gap.

The Secret Weapon: Turning Discrete Steps into Smooth Rivers

How did they prove this? The math behind Ensemble Sampling is tricky because the chefs’ guesses are coupled. If Chef A serves a dish today, it affects the data Chef B sees tomorrow. It’s a messy, step-by-step (discrete) process.

The authors used a clever mathematical trick involving Brownian Motion.

The Analogy:
Imagine the "noise" added to each chef’s data is like a leaf floating down a river.

In the real world (the algorithm), the river flows in choppy, discrete steps. One second the leaf is here, the next second it jumps there. This is hard to analyze.
The authors showed that you can imagine this choppy river as a smooth, continuous stream (a Brownian Motion).

They proved that the messy, discrete updates of the chefs’ models can be mathematically represented as independent smooth rivers flowing at their own speeds. By switching to this "continuous time" view, they could use powerful tools from calculus and probability theory that don’t work well with choppy steps.

The Key Insight: The "Exceedance" Threshold

The core of the proof relies on a concept called Exceedance Frequency.

Think of the "noise" added to the chefs' models as a way to keep them optimistic. If a chef’s noise pushes their estimate of a recipe’s quality high enough, they will try it. This is "exploration."

The authors needed to prove that, at any given time, a certain fraction of the chefs (say, 10%) will always have enough "noise optimism" to try new things. If too many chefs become too conservative, the restaurant stops learning, and regret goes up.

Using their "smooth river" analogy, they proved that for independent rivers (Brownian motions), you can guarantee that a specific percentage of them will stay above a certain "optimism threshold" uniformly over time. This guarantee ensures that the committee never stops exploring, keeping the regret low.

Summary of Results

Optimal Performance: Ensemble Sampling with Gaussian noise achieves the same high-probability regret bound as Thompson Sampling ( $\tilde{O}(d^{3/2}\sqrt{n})$ ).
Efficient Size: You don’t need a huge committee. A size of $m = \Theta(d \log n)$ is sufficient. This is much smaller than previous requirements that depended on the number of possible recipes (which could be infinite).
Computational Efficiency: Because the committee size is small, the method remains computationally feasible, unlike methods that require massive ensembles.
Lower Bound: The paper also proves that you can’t make the committee too small. If the committee is smaller than $d/2$ , the method fails and regret becomes linear (very bad). So, their proposed size is close to the minimum necessary.

Why This Matters

This paper is significant because it validates Ensemble Sampling as a top-tier algorithm. It shows that we don’t need to use the more complex Thompson Sampling to get the best results. We can use Ensemble Sampling, which is often easier to implement in complex real-world scenarios, and still get the same theoretical guarantees. It also introduces a new mathematical technique (using continuous-time embeddings for discrete problems) that might help solve other difficult problems in machine learning.

Technical Summary: Sharp Analysis of Linear Ensemble Sampling

Problem Setting and Motivation
This paper addresses the stochastic linear bandit problem, a canonical model for structured exploration where the expected reward is linear in the action. The specific algorithm analyzed is Ensemble Sampling (ES), a randomized exploration method that maintains an ensemble of $m$ models, each trained on a perturbed version of the historical data. In each round, ES selects one model uniformly at random and chooses the action that maximizes the predicted reward under that model.

The central challenge in analyzing ES is the dependence induced by adaptation: while the noise perturbations are independent across ensemble members and time, the fitted models are coupled because they are trained on data collected by the ensemble itself. Prior work established that Thompson Sampling (TS) achieves a regret bound of $\tilde{O}(d^{3/2}\sqrt{n})$ in $d$ -dimensional linear bandits with horizon $n$ . However, the best existing regret bounds for ES with a computationally efficient ensemble size ( $m = \tilde{O}(d)$ ) were $\tilde{O}(d^{5/2}\sqrt{n})$ , leaving a gap of a factor of $d$ compared to TS. Existing results that matched the TS regret rate required ensemble sizes scaling with the number of actions $k$ (i.e., $m = \Omega(k \log n)$ ), which is infeasible for large or infinite action sets.

Methodology
The authors’ analysis builds upon the framework of Janz et al. (2024), which reduces regret control to establishing a high-probability lower bound on "time-uniform self-normalized exceedance frequencies." Specifically, the analysis requires showing that a constant fraction of the ensemble members’ self-normalized noise processes exceed a fixed threshold uniformly over time.

The key technical innovation is the use of continuous-time stochastic analysis tools to handle the discrete-time adaptive processes. The methodology proceeds in three main steps:

Diagonal Martingale Representation: The authors identify the relevant noise processes in ES as predictable diagonal martingale transforms of Gaussian noise. In the linear setting, these transforms are scalar multiples of the identity, meaning all coordinates share a common "clock" (predictable quadratic variation).
Brownian Embedding (Theorem 5.3): Leveraging the Gaussian nature of the perturbations, the authors prove a representation lemma. They show that these discrete-time diagonal martingale transforms can be exactly represented as independent standard Brownian motions evaluated at random times determined by the predictable quadratic variation. This step utilizes the Dambis–Dubins–Schwarz time-change theorem and Knight’s construction to ensure the independence of the resulting Brownian motions. This converts the coupled discrete-time problem into a problem involving independent Brownian motions with random clocks.
Time-Uniform Exceedance Bounds (Theorem 5.4): The core probabilistic contribution is a new bound on the exceedance frequency for $m$ independent Brownian motions. The authors prove that over any time window, the fraction of Brownian motions staying above a curved boundary ( $c\sqrt{t}$ ) remains above a target level $p$ with high probability, provided $m$ is sufficiently large. This proof employs an Ornstein–Uhlenbeck time change, boundary-crossing estimates, Chernoff bounds, and a union bound over a logarithmic time discretization.

Key Contributions and Results
The paper’s primary contribution is closing the gap between ES and Thompson Sampling in terms of regret bounds while maintaining computational efficiency.

Regret Bound (Theorem 4.1): The authors prove that for an ensemble size $m = \Theta(d \log(n/\delta))$ , ES with standard Gaussian perturbations achieves a high-probability regret bound of $\tilde{O}(d^{3/2}\sqrt{n})$ . This matches the canonical regret rate of Thompson Sampling. The bound holds for a fixed, potentially infinite action set (e.g., the unit ball in $\mathbb{R}^d$ ).
Ensemble Size Lower Bound (Theorem 4.2): To demonstrate the tightness of their ensemble size requirement, the authors prove a lower bound showing that if $m \leq d/2$ , there exist linear bandit instances where ES incurs linear regret. This indicates that the $\Theta(d \log n)$ scaling is close to optimal for avoiding linear regret.
Computational Efficiency: The proposed method maintains a per-round computational cost comparable to competing methods, scaling as $\tilde{O}(d^2 + md^{\omega-1})$ , where $\omega$ is the matrix multiplication exponent. By keeping $m$ linear in $d$ , the overhead remains manageable.

Significance and Outlook
The paper claims significance in providing a "sharp" frequentist analysis of ES that matches the performance of the gold-standard Thompson Sampling algorithm without requiring large ensemble sizes. The authors emphasize that the continuous-time lens is not merely an approximation but provides an exact representation of the discrete-time processes, which they argue is the key conceptual lever enabling this sharp analysis. They note that they do not know another route to such a sharp bound for ES.

The authors conjecture that similar time-uniform exceedance guarantees may hold for other perturbation distributions (e.g., Rademacher), but proving this would require different tools, such as Skorokhod embeddings. They also suggest that the technique of using continuous-time embeddings to derive self-normalized tail inequalities for discrete-time stochastic processes may have broader applications in sequential learning analysis.