# Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective

arXiv: https://arxiv.org/abs/2510.05023 · HTML: https://mlsanity.com/paper/2510.05023/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 51 references that are in the map.
- First posted on arXiv 6 Oct 2025.

## Builds on (most cited first, 24 of 24)

- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Ensemble Sampling](https://mlsanity.com/paper/1705.07347/) (2017)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation](https://mlsanity.com/paper/2207.04475/) (2022)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [MOTS: Minimax Optimal Thompson Sampling](https://mlsanity.com/paper/2003.01803/) (2020)
- [An Analysis of Ensemble Sampling](https://mlsanity.com/paper/2203.01303/) (2022)
- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.10728/) (2024)
- [More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling](https://mlsanity.com/paper/2406.12241/) (2024)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2401.11665/) (2024)
- [Ensemble sampling for linear bandits: small ensembles suffice](https://mlsanity.com/paper/2311.08376/) (2023)
- [On Thompson Sampling with Langevin Algorithms](https://mlsanity.com/paper/2002.10002/) (2020)
- [VITS : Variational Inference Thompson Sampling for contextual bandits](https://mlsanity.com/paper/2307.10167/) (2023)
- [Improved Regret of Linear Ensemble Sampling](https://mlsanity.com/paper/2411.03932/) (2024)
- [Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning](https://mlsanity.com/paper/2306.08803/) (2023)

## Built on by (most cited first, 1 of 1)

- [Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits](https://mlsanity.com/paper/2510.10730/) (2025)

## Abstract (arXiv)

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 widetildemathcal O(√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.