Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Improved Regret of Linear Ensemble Sampling
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.
Shows linear ensemble sampling with ensemble size logarithmic in T (m = Omega(K log T)) achieves Otilde(d^{3/2} sqrt(T)) frequentist regret, via a general optimism-probability analysis framework, and proves LinPHE is linear ensemble sampling with m=T.
Problem
Existing frequentist regret bounds for linear ensemble sampling are sub-optimal (d^{5/2} sqrt(T)) and require ensemble sizes that are either linear in T or scale with d log T, leaving a gap to LinTS and LinPHE.
Approach
Uses a general regret framework based on the probability of optimistic action, shows that anti-concentration along a single direction U_{t-1} suffices for optimism, and bounds the union over arm sequences via a permutation-invariance argument so ensemble size needs only be K log T; also observes that ensemble sampling with m=T and round-robin selection equals LinPHE.
Key results
- Linear ensemble sampling with ensemble size m = Omega(K log T) achieves Otilde(d^{3/2} sqrt(T)) frequentist regret with probability at least 1-4 delta, improving the prior d^{5/2} sqrt(T) bound by a factor d.
- The regret bound does not depend on K or m, and no performance degradation is shown as ensemble size grows.
- LinPHE is shown to be linear ensemble sampling with m=T and round-robin selection, and its regret is Otilde(d^{3/2} sqrt(T)) independent of K.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Improve the regret analysis of linear ensemble sampling, using ensemble size m = Ω(K log T) | Linear ensemble sampling · Finite-armed linear bandit | frequentist regret: \tilde{\Ocal}(d^{5/2} \sqrt{T}) -> \tilde{\Ocal}(d^{3/2}\sqrt{T}) | Helped |
| Analyze LinPHE with the linear ensemble sampling framework | LinPHE · Linear bandit | cumulative regret: \tilde{\Ocal} ( d \sqrt{ T \log K } ) -> \tilde{\Ocal}(d^{3/2} \sqrt{T}) | Helped |
Surprising findings
- The prior symmetrized ensemble sampling bound grows super-linearly with ensemble size, which is counter-intuitive.
- Ensemble size requirement is logarithmic in T rather than linear, despite the union bound over K^T arm sequences, via a permutation argument.
Limitations
- Analysis restricted to stochastic linear bandits with finite arm sets for the main ensemble result; general contextual settings left open.
- Regret bound holds with high probability and requires Gaussian (or symmetric subGaussian) perturbations with known S and sigma.
- Ensemble size m = Omega(K log T) still depends on the number of arms K.
Experimental setup
Metrics: cumulative regret
Baselines: linear ensemble sampling (Lu and Van Roy 2017) symmetrized linear ensemble sampling (Zhou et al.) LinTS LinPHE LinUCB
Builds on: ensemble sampling LinPHE linear Thompson sampling OFUL
Closest papers by meaning
- Ensemble sampling for linear bandits: small ensembles suffice (NeurIPS 2024 · similarity 0.93)
- Scalable Exploration via Ensemble++ (NeurIPS 2025 · similarity 0.88)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.88)
- Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits (ICLR 2025 · similarity 0.88)
- Thompson Sampling for Multi-Objective Linear Contextual Bandit (NeurIPS 2025 · similarity 0.88)
- Linear Bandits with Partially Observable Features (ICML 2025 · similarity 0.88)
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.