Linear Ensemble Sampling with Smaller Ensembles

Taehyun Hwang; Min-hwan Oh

cs.LGSep 12, 2026

Linear Ensemble Sampling with Smaller Ensembles

Authors: Taehyun Hwang, Min-hwan Oh

Organizations: Seoul National University

Abstract

Ensemble sampling offers a practical approach to randomized exploration by maintaining a collection of models, but how small an ensemble can be while retaining strong regret guarantees remains unresolved. In particular, the existing guarantees use an ensemble size of $Θ(d\log T)$ , leaving a logarithmic gap in the horizon $T$ relative to the intrinsic $Ω(d)$ ensemble-size barrier. We aim to narrow this gap by proposing an ensemble sampling algorithm that refreshes the ensemble only when the regularized Gram matrix changes substantially. This mechanism localizes the perturbation analysis to epochs with controlled Gram-matrix drift and reduces the sufficient ensemble size to $Θ(d\log d+d\log\log T)$ , while preserving the state-of-the-art $\tilde O(d^{3/2}\sqrt T)$ regret for ensemble sampling with arbitrary bounded arm sets. We further show that, when the arm set is finite of cardinality $K$ , the proposed algorithm achieves the sharper regret bound $\tilde O(d\sqrt{T\log K})$ . To the best of our knowledge, this is the first ensemble-sampling guarantee that simultaneously recovers both canonical regret scalings known for randomized linear bandit algorithms: the $\tilde O(d^{3/2}\sqrt{T})$ rate for arbitrary bounded arm sets and the $\tilde O (d\sqrt{T\log K})$ rate for finite arm sets. The algorithm also admits an anytime implementation without resetting past data, and experiments show that it remains competitive with baselines while using substantially smaller ensembles.

Figures & tables

Paper	Ensemble size	Regret	Setting
Lu and Van Roy [13]	$\sqrt{K}T$	N/A	Finite fixed arms
Qin et al. [18]	$dT$	$\sqrt{dT}$ †	Finite fixed arms
Janz et al. [8]	$d\log T+d\log\frac{1}{\delta}$	$d^{5/2}\sqrt{T}$	Arbitrary bounded arms
Lee and Oh [12]	$K\log T+\log\frac{1}{\delta}$	$d^{3/2}\sqrt{T}$	Finite fixed arms
Sun et al. [19]	$K\log T+\log\frac{1}{\delta}$	$d^{3/2}\sqrt{T}+d^{9/2}$	Finite fixed arms, GLM
Janz et al. [7]	$d\log T+d\log{\frac{1}{\delta}}$	$d^{3/2}\sqrt{T}$	Arbitrary bounded arms

Table 1: Comparison of regret bounds and ensemble complexities for linear ensemble sampling. Here

d

is the feature dimension,

K

is the number of arms,

T

is the horizon, and

\delta

is the failure probability in high-probability regret guarantees. The dependence on

\delta

is omitted for results stated in Bayesian regret, where no high-probability failure parameter is used. Logarithmic factors other than those displayed are suppressed in the regret bounds.

\mathbf{s}_{t-1}^{j}=\mathbf{V}_{\tau}^{1/2}\mathbf{g}^{j}\,,\quad\boldsymbol{\theta}^{j}_{t-1}=\hat{\boldsymbol{\theta}}_{t-1}+\gamma\beta_{t-1}\mathbf{V}_{t-1}^{-1}\mathbf{s}^{j}_{t-1}

Algorithm 1 Linear Ensemble Sampling with Epoch Refresh ( LinES-ER )

Figure 1: Cumulative regret and runtime on stochastic linear bandits over $\mathcal{B}_{2}^{d}$ with $d=30$ and $T=10{,}000$ .

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

$T$	$d$	$\delta$	$m_{\mathrm{ours}}$	$m_{\mathrm{base}}$	$m_{\mathrm{base}}/m_{\mathrm{ours}}$	Runtime improvement
$10^{4}$	$10$	$10^{-4}$	$55$	$185$	$3.36$	$9.65\%$
$10^{4}$	$20$	$10^{-4}$	$114$	$369$	$3.24$	$24.71\%$
$10^{4}$	$30$	$10^{-4}$	$178$	$553$	$3.10$	$30.5\%$
$10^{4}$	$50$	$10^{-4}$	$316$	$922$	$2.92$	$36.55\%$

Appendix

Table 2: Comparison of theoretical ensemble sizes and runtime improvement for different dimensions. The baseline ensemble size

m_{\mathrm{base}}

is computed using the prescription of Janz et al. [7] ,

m_{\mathrm{base}}=\lceil d\log(T/\delta)\rceil

, whereas our ensemble size is computed as

m_{\mathrm{ours}}=\lceil d\log d+d\log\log T+\log(1/\delta)\rceil

. Runtime improvement is measured relative to LinES .

Panel of Figure 2 — Figure 2: Cumulative regret and runtime on stochastic linear bandits over $\mathcal{B}_{2}^{d}$ with $T=10{,}000$ and $d\in\{10,20,50\}$ .

\mathbf{s}_{t-1}^{j}=\mathbf{V}_{\tau}^{1/2}\mathbf{g}^{j},\qquad\boldsymbol{\theta}_{t-1}^{j}=\hat{\boldsymbol{\theta}}_{t-1}+\gamma\beta_{t-1}\mathbf{V}_{t-1}^{-1}\mathbf{s}_{t-1}^{j}

Appendix

Algorithm 2 Anytime Linear Ensemble Sampling with Epoch Refresh

Panel of Figure 3 — Figure 3: Anytime implementation under the doubling schedule for $T=10{,}000$ and $d\in\{10,20,30,50\}$ . Left panels: cumulative regret. Right panels: total runtime.

Panel of Figure 4 — Figure 4: Finite-arm experiments with randomly generated arms on the unit sphere.

Multi-Armed Bandits

Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.

See all 347 papers

Oct 12, 2025

Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits

We provide a unified algorithmic framework for ensemble sampling in nonlinear contextual bandits and develop corresponding regret bounds for two most common nonlinear contextual bandit settings: Generalized Linear Model Ensemble Sampling (GLM-ES) for generalized linear contextual bandits and Neural Ensemble Sampling (Neural-ES) for neural contextual bandits. Both methods maintain multiple estimators for the reward model parameters via maximum likelihood estimation on randomly perturbed data. We prove high-probability frequentist regret bounds of

\widetilde{\mathcal{O}}(d^{3/2} \sqrt{T} + d^{4})

for GLM-ES and

\widetilde{\mathcal{O}}(\widetilde{d}^{3/2} \sqrt{T})

for Neural-ES, where

d

is the dimension of feature vectors,

\widetilde{d}

is the effective dimension of a neural tangent kernel (NTK) matrix and

T

is the number of rounds. The regret bound of GLM-ES matches the state-of-the-art result of randomized exploration algorithms in generalized linear bandit setting. In the theoretical analysis, we introduce techniques that address challenges specific to nonlinear models. Practically, we remove fixed-time horizon assumption by developing anytime versions of our algorithms, suitable when

T

is unknown. Finally, we empirically evaluate GLM-ES, Neural-ES and their anytime variants, demonstrating strong performance. Overall, our results establish ensemble sampling as a provable and practical randomized exploration approach for nonlinear contextual bandits.

Jiazheng Sun, Weixin Wang, Pan Xu

Duke University

Ensemble Learning Contextual Bandits Generalized Linear Models Generalized Linear Bandits

Ask PDF

Jun 26, 2026

Randomized Exploration for Linear Bandits via Absolute Perturbations

In stochastic linear bandits, the canonical Upper Confidence Bound (UCB) algorithm admits a simple frequentist regret analysis but can be computationally demanding, while Thompson Sampling (TS) is computationally attractive yet typically harder to analyze due to its non-optimistic nature. We propose Absolute Thompson Sampling (ATS), a simple modification of TS that ensures optimism in expectation by replacing the signed exploration noise with its absolute value. This preserves the computational efficiency of TS while avoiding the technically involved anti-concentration arguments common in TS analyses, enabling a simple UCB-style regret analysis. We show that ATS achieves

\tilde{O}(d^{3/2}\sqrt{K})

regret, matching existing bounds for TS in linear bandits. We further introduce Ensemble Absolute Thompson Sampling (EATS), which takes the maximum over multiple absolute perturbations with normalization by the ensemble size. As the ensemble size grows, EATS converges to the UCB objective, recovering UCB behavior in the limit. Experiments show that moderate ensemble sizes already yield strong performance. Our results point to a bridge between randomized exploration and deterministic optimism both in theory and practice.

Toshinori Kitamura, Shuai Liu, Csaba Szepesvári

Department of Computing Science, University of Alberta, Canada

Thompson Sampling Multi-Armed Bandits UCB Algorithms

Ask PDF

Jun 18, 2026

Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learning

Optimal Reinforcement Learning (RL) algorithms typically rely on carefully constructed count-based uncertainty estimates to drive exploration. Although theoretically sound, such estimates are hard to compute in practical settings and therefore offer limited insight for designing exploration heuristics. Meanwhile, ensembling has emerged as a practical approach, but remains without theoretical justification. Building on a recent ensemble-based method for Multi-Armed Bandits, we propose a quantile-based ensemble method for finite-horizon Markov Decision Processes (MDPs). Our simple count-free approach achieves optimal variance-dependent regret bounds, providing theoretical grounding for ensemble-based exploration in RL.

Asaf Cassel, Aviv Rosenberg

Google Research

Regret Minimization in RL Reinforcement Learning RL Exploration

Ask PDF

Abstract

Multi-Armed Bandits

Explore similar work

Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits

Randomized Exploration for Linear Bandits via Absolute Perturbations

Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learning