Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Scalable Exploration via Ensemble++
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.
Proposes Ensemble++, a shared-factor ensemble that approximates Thompson Sampling with only Θ(d log T) ensemble members via random linear combinations, with regret guarantees for linear bandits and an SGD-trained neural extension.
Problem
Thompson Sampling is hard to scale to high-dimensional or non-conjugate (neural) models, and prior ensemble sampling methods with TS-matching regret guarantees require ensemble sizes that grow with T or the number of actions.
Approach
Maintain a single shared ensemble factor matrix A_t updated incrementally with random perturbations, so that random linear combinations of its columns approximate posterior samples; extend to neural bandits by learning a feature extractor with a symmetrized regression loss and FIFO buffer SGD updates.
Key results
- Linear Ensemble++ nearly matches TS regret with M=8 in a finite-action linear bandit (d=50, |X|=10,000), outperforming Linear Ensemble Sampling at the same ensemble size.
- Theory: Linear Ensemble++ with M=Θ(d log T) achieves Õ(d^{3/2}√T (log T)^{3/2}) regret for compact action sets and Õ(d√(T log|X|) log T) for finite action sets.
- Ensemble++ outperforms Ensemble+ by about 5% on the hate speech detection bandit using GPT-2, and achieves sublinear regret in the quadratic bandit where baselines show linear regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Linear Ensemble++ Sampling with M=8 instead of Linear Ensemble Sampling | Finite-action Linear Bandit · Finite-action Linear Bandit | regret | Helped |
| Use Ensemble++ instead of Ensemble+ | GPT-2 hate speech bandit · Online Hate Speech Detection | regret: 5% | Helped |
| Increase ensemble size M (ablation) | Ensemble++ · Nonlinear bandits | regret | Helped |
| Vary decision set size (ablation) | Ensemble++ · Nonlinear bandits | regret | No clear effect |
| Reduce buffer capacity below the total time horizon (ablation) | Ensemble++ · Nonlinear bandits | performance | No clear effect |
| Change the perturbation distribution (ablation) | Ensemble++ with a neural network · Neural bandits | performance | No clear effect |
Surprising findings
- The perturbation distribution choice has a negligible impact on performance when using a neural network, according to the authors.
Limitations
- Theoretical guarantees cover only the linear case; tighter bounds for the neural extension are left open.
- Regret analysis relies on an inflation parameter for the posterior variance, which is needed for frequentist guarantees.
- EpiNet could not be applied to the Transformer-based hate speech task due to architectural constraints.
Experimental setup
Datasets: UCI Shuttle measuring-hate-speech (Hugging Face)
Benchmarks: finite-action linear bandit quadratic bandit neural bandit UCI Shuttle contextual bandit online hate speech detection bandit
Metrics: cumulative regret accuracy regret vs. number of parameters
Baselines: Ensemble+ EpiNet Greedy Linear Thompson Sampling Linear Ensemble Sampling LMC-TS
Builds on: Thompson Sampling ensemble sampling local perturbation Ensemble+ EpiNet
Closest papers by meaning
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.89)
- Improved Regret of Linear Ensemble Sampling (NeurIPS 2024 · similarity 0.88)
- Exploration via Feature Perturbation in Contextual Bandits (NeurIPS 2025 · similarity 0.88)
- Infrequent Exploration in Linear Bandits (NeurIPS 2025 · similarity 0.87)
- Ensemble sampling for linear bandits: small ensembles suffice (NeurIPS 2024 · similarity 0.87)
- Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.