aiqbench analysis
This paper proposes TS-SA, a Thompson Sampling variant for multi-armed bandits that replaces the inner Markov chain with a single Langevin step per reward, combined through a stochastic approximation update. The main contribution is theoretical: a near-optimal regret bound of Õ(√(KT)) under log-concavity and smoothness assumptions, plus experiments showing competitive performance against standard baselines. Readers should weigh the assumptions and the scope of the empirical comparisons, since results on bandit benchmarks don't necessarily transfer to large-scale learning settings.
Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective
arXiv:2510.05023v2 Announce Type: replace-cross Abstract: Langevin-based Thompson Sampling (TS) methods for multi-armed bandits use likelihood gradients to approximate posterior samples when exact sampling is intractable. As new rewards arrive, the posterior changes, and these methods run an inner Markov chain to approximate the updated target. To simplify this repeated sampling procedure, we introduce TS-SA, which incorporates stochastic approximation (SA) within the TS framework. In each round, TS-SA takes one Langevin step using the newly observed reward and applies an SA update to combine the noisy proposal with the current parameter estimate. By retaining this estimate across rounds, TS-SA maintains one continuing Markov chain for each arm, preserving the influence of past observations without storing or sampling them again. Within this recursion, the proposal step size remains fixed across rounds, while the SA weights decrease as observations accumulate to control the effect of noise on the estimate. This continuing-chain formulation simplifies the theoretical analysis, allowing us to establish a near-optimal worst-case regret bound of $\widetilde{\mathcal O}(\sqrt{KT})$ under log-concavity and smoothness assumptions with one update per new reward. Our experiments further demonstrate that TS-SA, using a single-step Langevin update after an initial warm-up, achieves strong performance against standard baselines.
Abstract:Langevin-based Thompson Sampling (TS) methods for multi-armed bandits use likelihood gradients to approximate posterior samples when exact sampling is intractable. As new rewards arrive, the posterior changes, and these methods run an inner Markov chain to approximate the updated target. To simplify this repeated sampling procedure, we introduce TS-SA, which incorporates stochastic approximation (SA) within the TS framework. In each round, TS-SA takes one Langevin step using the newly observed reward and applies an SA update to combine the noisy proposal with the current parameter estimate. By retaining this estimate across rounds, TS-SA maintains one continuing Markov chain for each arm, preserving the influence of past observations without storing or sampling them again. Within this recursion, the proposal step size remains fixed across rounds, while the SA weights decrease as observations accumulate to control the effect of noise on the estimate. This continuing-chain formulation simplifies the theoretical analysis, allowing us to establish a near-optimal worst-case regret bound of $\widetilde{\mathcal O}(\sqrt{KT})$ under log-concavity and smoothness assumptions with one update per new reward. Our experiments further demonstrate that TS-SA, using a single-step Langevin update after an initial warm-up, achieves strong performance against standard baselines.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)
arXiv:2510.05023 [cs.LG]
(or arXiv:2510.05023v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2510.05023 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 290 words
Related coverage
A Stochastic Analysis Perspective on Diffusion Models
arXiv · Oct 14, 2026
Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oracles
arXiv · Sep 3, 2026
Regret Optimality of Sample Average Approximation for Data-Driven Newsvendor Problems: A General Optimization Perspective
arXiv · Jul 21, 2026
Bayesian Nonparametric Thompson Sampling for Multi-Armed Bandits
arXiv · Oct 14, 2026