mlsanityData to 7 Oct 2026

When and why randomised exploration works (in linear bandits)

arXiv 2502.08870 ↗First posted 13 Feb 2025cs.LG stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

We provide an approach for the analysis of randomised exploration algorithms like Thompson sampling that does not rely on forced optimism or posterior inflation. With this, we demonstrate that in the d-dimensional linear bandit setting, when the action space is smooth and strongly convex, randomised exploration algorithms enjoy an n-step regret bound of the order O(d√n log(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.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 12 of its 32 references that are in the map. First posted on arXiv 13 Feb 2025.

Builds on

12 of 32 references.

References · 12

  1. 2017A Tutorial on Thompson Samplingcited by 420
  2. 2013Learning to Optimize Via Posterior Samplingcited by 253
  3. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  4. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  5. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  6. 2017Ensemble Samplingcited by 62
  7. 2016The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Banditscited by 48
  8. 2013Thompson Sampling for 1-Dimensional Exponential Family Banditscited by 41
  9. 2019Old Dog Learns New Tricks: Randomized UCB for Bandit Problemscited by 21
  10. 2020On Frequentist Regret of Linear Thompson Samplingcited by 14
  11. 2023Exploration via linearly perturbed loss minimisationcited by 13
  12. 2023Ensemble sampling for linear bandits: small ensembles sufficecited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 4.

8 papers.

  1. 2025Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Designcited by 3
  2. 2026Sharp analysis of linear ensemble samplingcited by 1
  3. 2025Best-of-Both Worlds for linear contextual bandits with paid observationscited by 0
  4. 2025Exploration via Feature Perturbation in Contextual Banditscited by 0
  5. 2025Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoidscited by 0
  6. 2026Variance-sensitive Thompson sampling for generalised linear bandits, revisitedcited by 0
  7. 2026Randomized Exploration for Linear Bandits via Absolute Perturbationscited by 0
  8. 2026A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Setscited by 0