Sharp analysis of linear ensemble sampling

• URL: http://arxiv.org/abs/2602.08026v1
• Date: Sun, 08 Feb 2026 15:58:36 GMT
• Title: Sharp analysis of linear ensemble sampling
• Authors: Arya Akhavan, David Janz, Csaba Szepesvári,
• Abstract summary: We show that for ensemble size $m=(dlog n)$, ES attains $tilde O(d3/2sqrt n)$ high-probability regret.<n>The proof brings a new perspective on randomized exploration in linear bandits.
• Score: 31.13444548932784
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We analyse linear ensemble sampling (ES) with standard Gaussian perturbations in stochastic linear bandits. We show that for ensemble size $m=Θ(d\log n)$, ES attains $\tilde O(d^{3/2}\sqrt n)$ high-probability regret, closing the gap to the Thompson sampling benchmark while keeping computation comparable. The proof brings a new perspective on randomized exploration in linear bandits by reducing the analysis to a time-uniform exceedance problem for $m$ independent Brownian motions. Intriguingly, this continuous-time lens is not forced; it appears natural--and perhaps necessary: the discrete-time problem seems to be asking for a continuous-time solution, and we know of no other way to obtain a sharp ES bound.

Related papers

• Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits [10.131895986034314]
  Generalized Linear Ensemble Sampling (textttGLM-ES) for generalized linear bandits and Neural Ensemble Sampling (textttNeural-ES) for neural contextual bandits.<n>We prove high-probability frequentist regret bounds of $mathcalO(d3/2 sqrtT + d9/2)$ for textttGLM-ES and $mathcalO(widetilded sqrtT)$ for text
  arXiv  Detail & Related papers  (2025-10-12T18:05:53Z)
• When and why randomised exploration works (in linear bandits) [9.167278626563007]
  We show that when the action space is smooth and strongly convex, randomised exploration algorithms enjoy an $n$-step regret bound to the order $O(dsqrtn log(n))$.<n> Notably, this shows for the first time that there exist non-trivial linear bandit settings where Thompson sampling can achieve optimal dimension dependence in the regret.
  arXiv  Detail & Related papers  (2025-02-13T00:49:28Z)
• 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)
• Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
  We study high-probability convergence in online learning, in the presence of heavy-tailed noise.<n>We provide guarantees for a broad class of nonlinearities, without any assumptions on noise moments.
  arXiv  Detail & Related papers  (2024-10-17T18:25:28Z)
• Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel [10.840582511203024]
  We show that our algorithm can be parallelized to run in only $widetilde O(log2 d)$ parallel rounds. We also show that our algorithm can be parallelized to run in only $widetilde O(log2 d)$ parallel rounds.
  arXiv  Detail & Related papers  (2024-06-03T01:34:34Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  We show that wetailed high-prob convergence guarantees of learning on streaming data in the presence of heavy-tailed noise. We demonstrate analytically and that $ta$ can be used to the preferred choice of setting for a given problem.
  arXiv  Detail & Related papers  (2023-10-28T18:53:41Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  We study the problem of online generalized linear regression in the setting of a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of the classical follow-the-regularized-leader (FTRL) algorithm to cope with the label noise. We propose an algorithm based on FTRL to achieve the first variance-aware regret bound.
  arXiv  Detail & Related papers  (2022-02-28T08:25:26Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  We provide a new convergence analysis of gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave. At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain.
  arXiv  Detail & Related papers  (2020-10-19T15:23:18Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model [0.0]
  We analyze the convergence of single-pass, fixed step-size gradient descent on the least-square risk under this model. As a special case, we analyze an online algorithm for estimating a real function on the unit interval from the noiseless observation of its value at randomly sampled points.
  arXiv  Detail & Related papers  (2020-06-15T08:25:50Z)

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.