Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Ensemble sampling for linear bandits: small ensembles suffice

NeurIPS 2024 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Thompson sampling analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first useful regret analysis of ensemble sampling for stochastic linear bandits, showing an ensemble of size order d log T achieves regret order (d log T)^{5/2} sqrt(T).

Problem

Ensemble sampling is popular for exploration but has resisted rigorous analysis; prior bounds required ensemble sizes linear in T, defeating its purpose, and no structured-setting analysis with small ensembles existed.

Approach

A symmetrised linear ensemble sampling algorithm with uniform random initialisations and uniform random-walk targets, analysed via a master theorem for optimistic randomised algorithms. The key is showing singular values of the ensemble matrix are order sqrt(m) with high probability, so each sampled parameter lands in the optimistic region with probability at least 1/(2m).</били>

Key results

• With ensemble size m of order d log T (for polynomial confidence parameter delta), regret is bounded by C(d log T)^{5/2} sqrt(T) with high probability.
• Ensemble sampling analysis yields regret scaling d^{5/2} sqrt(T) versus d^{3/2} sqrt(T) for Thompson sampling, up to log factors.
• The analysis also covers infinite action sets, which prior ensemble sampling bounds did not.

Surprising findings

• The max-over-ensemble (UCB-style) variant would yield d^{3/2} dependence by the same proof, suggesting the randomised selection rule may be the looser part of the analysis.

Limitations

• Regret bound is loose by a factor of m and by sqrt(m) relative to Thompson sampling; the d^{5/2} dependence is worse than the d^{3/2} of Thompson sampling.
• Requires the ensemble size and horizon to be fixed in advance; the bound depends directly on T, and the doubling trick is needed for anytime guarantees.
• Uses symmetrisation and uniform rather than Gaussian targets, departing from the algorithm analysed in prior work.

Experimental setup

Metrics: cumulative regret upper bound

Baselines: Lu and Van Roy (2017) ensemble sampling linear Thompson sampling confident linear Thompson sampling Lee et al. (2024) improved ensemble sampling bound

Builds on: Thompson sampling analysis (Agrawal and Goyal / Russo-Van Roy style) Lu and Van Roy 2017 ensemble sampling Abbasi-Yadkori 2011 self-normalised bound master theorem for optimistic randomised algorithms (Janz et al.)

Closest papers by meaning

• Improved Regret of Linear Ensemble Sampling (NeurIPS 2024 · similarity 0.93)
• Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.89)
• Thompson Sampling for Multi-Objective Linear Contextual Bandit (NeurIPS 2025 · similarity 0.89)
• Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits (ICLR 2025 · similarity 0.88)
• Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.88)
• Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox (NeurIPS 2024 · similarity 0.88)