Linear Ensemble Sampling with Smaller Ensembles

• URL: http://arxiv.org/abs/2609.13954v1
• Date: Sat, 12 Sep 2026 13:54:32 GMT
• Title: Linear Ensemble Sampling with Smaller Ensembles
• Abstract summary: We propose an ensemble sampling algorithm that refreshes the ensemble only when the regularized Gram matrix changes substantially.<n>This mechanism localizes the analysis to epochs with controlled Gram-matrix drift and reduces the sufficient ensemble size to $(dlog d+dloglog T)$.<n>We show that, when the arm set is finite of cardinality $K$, the proposed algorithm achieves the sharper regret bound $tilde O(dsqrtTlog K)$.
• Score: 38.66646896933269
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Parameter-Free Dynamic Regret for Unconstrained Linear Bandits [21.35587581980097]
  We study dynamic regret in unconstrained adversarial linear bandit problems.<n>We provide the first algorithm for linear bandits achieving the optimal regret guarantee of order.
  arXiv  Detail & Related papers  (2026-03-26T21:16:18Z)
• On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits [15.93884263655552]
  We study the fixed-budget best-arm identification problem in non-stationary linear bandits.<n>A learner aims to identify the arm with the largest cumulative reward $x_* = argmax_x in mathcalX xtopsum_t=1T _t$ with high probability.
  arXiv  Detail & Related papers  (2026-03-11T02:34:29Z)
• Improved Regret of Linear Ensemble Sampling [9.410437324336275]
  We prove that with an ensemble size logarithmic in $T$, linear ensemble sampling can achieve a frequentist regret bound of $tildeO(d3/2sqrtT)$.<n>Our approach introduces a general regret analysis framework for linear bandit algorithms.
  arXiv  Detail & Related papers  (2024-11-06T14:09:11Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise [45.60098988395789]
  We propose a new algorithm for constructing UCB-type algorithms for multi-armed bandits. We show that in the case of symmetric noise in the reward, we can achieve an $O(log TsqrtKTlog T)$ regret bound instead of $Oleft.
  arXiv  Detail & Related papers  (2024-02-10T22:38:21Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Ensemble sampling for linear bandits: small ensembles suffice [75.4286948336835]
  We show that ensemble sampling with an ensemble size of order $d log T$ incurs regret at most of the order $(d log T)5/2 sqrtT$.<n>Ours is the first result in any structured setting not to require the size of the ensemble to scale linearly with $T$.
  arXiv  Detail & Related papers  (2023-11-14T18:41:28Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso bandit is an algorithm that estimates the vector defining the reward function as well as its sparse support. We establish non-asymptotic regret upper bounds scaling as $mathcalO( log d + sqrtT )$ in general, and as $mathcalO( log d + sqrtT )$ under the so-called margin condition.
  arXiv  Detail & Related papers  (2020-10-22T19:14:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.