Metraipolis › archive › dc_7cba26fe3f29

Linear Ensemble Sampling with Smaller Ensembles — arXiv:2609.13954

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.13954
License (as archived)
CC0-1.0
Archived
2026-10-16T00:10:35.388Z
SHA-256 of the archived text
b3042ea8dc366c8c9a46483b048830ff1051cee1a81941a04d33dd7eba039068
Stable URL of this page
https://metraipolis.com/documento/dc_7cba26fe3f29

How to cite

Linear Ensemble Sampling with Smaller Ensembles — arXiv:2609.13954 — arXiv (en), https://arxiv.org/abs/2609.13954 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7cba26fe3f29 (Metraipolis archive dc_7cba26fe3f29, sha256 b3042ea8dc366c8c9a46483b048830ff1051cee1a81941a04d33dd7eba039068)
BibTeX
@misc{dc7cba26fe3f29,
  title = {Linear Ensemble Sampling with Smaller Ensembles — arXiv:2609.13954},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.13954},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7cba26fe3f29; sha256 b3042ea8dc366c8c9a46483b048830ff1051cee1a81941a04d33dd7eba039068},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.13954. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Theta(d\log T)$, leaving a logarithmic gap in the horizon $T$ relative to the intrinsic $\Omega(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 $\Theta(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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-15 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2609.13954 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T23:54:14.665Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).