Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective

Weixin Wang; Haoyang Zheng; Guang Lin; Wei Deng; Pan Xu

cs.LGOct 6, 2025

Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective

Authors: Weixin Wang, Haoyang Zheng, Guang Lin, Wei Deng, Pan Xu

Organizations: Duke University · Purdue University · Morgan Stanley

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.

Figures & tables

Figure 1: Comparison of updates for one arm, where

n

is the number of pulls. Left (existing LMC-based methods): each reward changes the posterior. An inner Markov chain, initialized from the previous output, approximates the updated posterior using a step size

h_{a}^{(n)}

that depends on the number of observations. Right (TS-SA): each reward advances one continuing Markov chain through a Langevin proposal and an SA update.

Panel of Figure 2 — Figure 2: Cumulative regret under different reward gaps $\Delta$ , numbers of arms $K$ , and reward settings.

Panel of Figure 3 — Figure 3: Effects of repeated updates and the SA schedule in SGR, with $K=10$ , $\Delta=0.5$ , $\tau=1$ , and $T=1,000$ . Results are averaged over 100 independent trials. (a) We vary $N$ with $h=0.05$ . (b) We vary $\alpha$ with $N=1$ and $\mathcal{B}=5$ . Other parameters follow Section E.3 .

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Symbols	Explanations
$h$ , $\gamma_{n}$ , $h_{n}^{\prime}$	Langevin, SA, and effective step sizes; $h_{n}^{\prime}=h\gamma_{n}$ .
$d$ , $\pi_{a}$	Parameter dimension and initialization distribution for arm $a$ .
$\bm{\phi}_{a}$ , $B_{a}$	Arm feature and its norm $B_{a}=\\|\bm{\phi}_{a}\\|_{2}$ .
$\bar{X}_{a}$ , $\Delta_{a}$	Mean reward and gap $\Delta_{a}=\bar{X}_{1}-\bar{X}_{a}$ .
$m_{a}$ , $\nu_{a}$ , $L_{a}$	Strong log-concavity constants in $\bm{\theta}$ and $X$ , and the score Lipschitz constant.
$\tau_{a}$	Controls the decision noise variance $(\tau_{a}n)^{-1}$ after $n$ pulls.

Appendix

Table 1: Notation summary in the analysis of TS-SA.

Figure 4: Slice plots of TS-SA hyperparameter tuning using Bayesian hyperparameter optimization, under fixed settings $K=10$ , $\Delta=0.5$ , $\tau=1.0$ , and $N=1$ . The $x$ -axis denotes the tuning range of a single hyperparameter, while the $y$ -axis shows the corresponding cumulative regret averaged over 50 independent runs. The color gradient from blue (early trials) to red (later trials) reflects the optimization trajectory. Regret decreases as Bayesian hyperparameter optimization identifies favorable values for warm-up pulls, batch size, and SA parameters $(c_{1},c_{2},\alpha)$ , while the step size $h$ and offset $c_{3}$ exhibit relatively weak influence.

Panel of Figure 5 — Figure 5: Ablation study of key hyperparameters in TS-SA ( $K=10$ , $\Delta=0.5$ ). The x-axis denotes the number of rounds, while the y-axis represents the cumulative regrets over 100 independent trials. Each subfigure plots the cumulative regret as a function of a single parameter while keeping others fixed. (a–b): Warm-up pulls ( $\Omega$ ) and batch size ( $\mathcal{B}$ ) show clear threshold behavior around 20, below which performance degrades significantly. (c): Increasing inner iterations ( $N$ ) improves performance with diminishing returns. (d–h): Sampling-related parameters ( $h$ , $c_{1}$ , $\alpha$ ) exhibit notable sensitivity and must be tuned carefully, while $c_{2}$ and $c_{3}$ show minor impact, which indicates robustness with respect to these choices.

Explore similar work

Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors
Sep 12, 2023Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya +1Thompson Sampling Multi-Armed Bandits
Department of Quantitative Methods, Daniels School of Business, Purdue University, West Lafayette, IN 47906, USA. · Department of Statistics, University of Wisconsin-Madison, Madison, WI 53706, USA. · Department of Statistics, Texas A&M University, College Station, TX 77843, USA.
Bayesian Nonparametric Thompson Sampling for Multi-Armed Bandits
Aug 8, 2018Iñigo Urteaga, Chris H. WigginsMulti-Armed Bandits Thompson Sampling
Department of Applied Physics and Applied Mathematics Data Science Institute Columbia University New York City, NY 10027
Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards
Jun 8, 2026Joel Q. L. ChangThompson Sampling Multi-Armed Bandits

Sep 12, 2023J/K move · Enter open · S save

Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors

Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya, Bani K. Mallick

Department of Quantitative Methods, Daniels School of Business, Purdue University, West Lafayette, IN 47906, USA. · Department of Statistics, University of Wisconsin-Madison, Madison, WI 53706, USA. · Department of Statistics, Texas A&M University, College Station, TX 77843, USA.

Thompson Sampling Multi-Armed Bandits Posterior Sampling

Open paper AskPDF arXiv

Thompson sampling (TS) is one of the most popular and earliest algorithms to solve stochastic multi-armed bandit problems. We consider a variant of TS, named

α

-TS, where we use a fractional or

α

-posterior (

α\in(0,1)

) instead of the standard posterior distribution. To compute an

α

-posterior, the likelihood in the definition of the standard posterior is tempered with a factor

α

. For

α

-TS we obtain both instance-dependent

\mathcal{O}\left(\sum_{k \neq i^*} Δ_k\left(\frac{\log(T)}{C(α)Δ_k^2} + \frac{1}{2} \right)\right)

and instance-independent

\mathcal{O}(\sqrt{KT\log K})

frequentist regret bounds under very mild conditions on the prior and reward distributions, where

Δ_k

is the gap between the true mean rewards of the

k^{th}

and the best arms, and

C(α)

is a known constant. Both the sub-Gaussian and exponential family models satisfy our general conditions on the reward distribution. Our conditions on the prior distribution can be easily satisfied by a density that is positive, continuous, and bounded. We also establish another instance-dependent regret upper bound that matches (up to constants) to that of improved UCB [Auer and Ortner, 2010]. Our regret analysis carefully adapts and combines recent theoretical developments in the non-asymptotic concentration analysis and Bernstein-von Mises type results for the

α

-posterior distribution. Moreover, our analysis does not require additional structural properties such as closed-form posteriors or conjugate priors.

Abstract

Explore similar work

Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors

Bayesian Nonparametric Thompson Sampling for Multi-Armed Bandits

Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards