Linear Ensemble Sampling with Smaller Ensembles
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 Θ(dlog 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 Θ(dlog d+dloglog T), while preserving the state-of-the-art Õ(d3/2√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 Õ(d√(Tlog 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 Õ(d3/2√T) rate for arbitrary bounded arm sets and the Õ (d√(Tlog 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.
Related
- Invariant pseudo-unitary matrix ensembles and local statistics and conductance fluctuations of the DMPK ensemble
- A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding
- Quenched Ensemble Sampling
- Characterizing nonlinear information in the linear sampling method for inverse medium scattering
- Uniform Sampling of Linear Codes with Prescribed Hull Dimension
BibTeX
@misc{hwang2026linear,
title = {{Linear Ensemble Sampling with Smaller Ensembles}},
author = {Taehyun Hwang and Min-hwan Oh},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13954},
eprint = {2609.13954},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13954},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Linear Ensemble Sampling with Smaller Ensembles
AU - Taehyun Hwang
AU - Min-hwan Oh
PY - 2026
DA - 2026/09/12
PB - arXiv
DO - 10.48550/arxiv.2609.13954
UR - https://arxiv.org/abs/2609.13954
AB - 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 Θ(dlog 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 Θ(dlog d+dloglog T), while preserving the state-of-the-art Õ(d^3/2√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 Õ(d√(Tlog 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 Õ(d^3/2√T) rate for arbitrary bounded arm sets and the Õ (d√(Tlog 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.
ER -