Ensemble sampling needs smaller model collections for efficient learning
Linear Ensemble Sampling with Smaller Ensembles
Machine Learning
Summary
When computers try to learn the best choices in situations with many options, they often keep several guessers called models to explore different possibilities. The authors find a way to use fewer of these guessers while still making good decisions quickly. They do this by updating the models only when important changes happen, which saves effort and still keeps strong performance. Their technique works well even for situations with many possible actions.
What this means in practice
- •For online recommendation teams: Improve recommendation algorithms by using smaller ensembles to balance exploration and exploitation efficiently over time.
- •For robotics developers: Use reduced model collections to speed up decision-making in robotic systems learning from interactions with the environment.
Authors
Taehyun Hwang, Min-hwan Oh
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.