Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective

• URL: http://arxiv.org/abs/2510.05023v1
• Date: Mon, 06 Oct 2025 17:01:29 GMT
• Title: Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective
• Authors: Weixin Wang, Haoyang Zheng, Guang Lin, Wei Deng, Pan Xu,
• Abstract summary: We introduce TS-SA, which incorporates approximation (SA) within the Thompson Sampling (TS) framework.<n>In each round, TS-SA constructs a posterior approximation only using the most recent reward(s) and applies an SA step to average noisy proposals over time.<n>This can be interpreted as approximating a stationary posterior target throughout the entire algorithm.
• Score: 17.53150194998013
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most existing approximate Thompson Sampling (TS) algorithms for multi-armed bandits use Stochastic Gradient Langevin Dynamics (SGLD) or its variants in each round to sample from the posterior, relaxing the need for conjugacy assumptions between priors and reward distributions in vanilla TS. However, they often require approximating a different posterior distribution in different round of the bandit problem. This requires tricky, round-specific tuning of hyperparameters such as dynamic learning rates, causing challenges in both theoretical analysis and practical implementation. To alleviate this non-stationarity, we introduce TS-SA, which incorporates stochastic approximation (SA) within the TS framework. In each round, TS-SA constructs a posterior approximation only using the most recent reward(s), performs a Langevin Monte Carlo (LMC) update, and applies an SA step to average noisy proposals over time. This can be interpreted as approximating a stationary posterior target throughout the entire algorithm, which further yields a fixed step-size, a unified convergence analysis framework, and improved posterior estimates through temporal averaging. We establish near-optimal regret bounds for TS-SA, with a simplified and more intuitive theoretical analysis enabled by interpreting the entire algorithm as a simulation of a stationary SGLD process. Our empirical results demonstrate that even a single-step Langevin update with certain warm-up outperforms existing methods substantially on bandit tasks.

Related papers

• SACn: Soft Actor-Critic with n-step Returns [3.305353787222645]
  Soft Actor-Critic (SAC) is one of the most relevant off-policy online model-free reinforcement learning (RL) methods.<n>SAC is notoriously difficult to combine with n-step returns, since their usual combination introduces bias in off-policy algorithms.<n>In this work, we combine SAC with n-step returns in a way that overcomes this issue.
  arXiv  Detail & Related papers  (2025-12-15T10:23:13Z)
• Inference-Time Scaling of Diffusion Language Models with Particle Gibbs Sampling [70.8832906871441]
  We study how to steer generation toward desired rewards without retraining the models.<n>Prior methods typically resample or filter within a single denoising trajectory, optimizing rewards step-by-step without trajectory-level refinement.<n>We introduce particle Gibbs sampling for diffusion language models (PG-DLM), a novel inference-time algorithm enabling trajectory-level refinement while preserving generation perplexity.
  arXiv  Detail & Related papers  (2025-07-11T08:00:47Z)
• Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
  Proximal samplers (SPS) for sampling from non-log-concave distributions are studied. We show that the convergence to the target distribution can be guaranteed as long as the algorithm trajectory is bounded. We provide two implementable variants based on Langevin dynamics (SGLD) and Langevin-MALA, giving rise to SPS-SGLD and SPS-MALA.
  arXiv  Detail & Related papers  (2024-05-27T00:53:18Z)
• VITS : Variational Inference Thompson Sampling for contextual bandits [10.028119153832346]
  We introduce and analyze a variant of the Thompson sampling (TS) algorithm for contextual bandits. We propose a new algorithm, Varational Inference Thompson sampling VITS, based on Gaussian Variational Inference. We show that VITS achieves a sub-linear regret bound of the same order in the dimension and number of round as traditional TS for linear contextual bandit.
  arXiv  Detail & Related papers  (2023-07-19T17:53:22Z)
• Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo [104.9535542833054]
  We present a scalable and effective exploration strategy based on Thompson sampling for reinforcement learning (RL) We instead directly sample the Q function from its posterior distribution, by using Langevin Monte Carlo. Our approach achieves better or similar results compared with state-of-the-art deep RL algorithms on several challenging exploration tasks from the Atari57 suite.
  arXiv  Detail & Related papers  (2023-05-29T17:11:28Z)
• The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models [56.31310344616837]
  Thompson sampling (TS) has been known for its outstanding empirical performance supported by theoretical guarantees across various reward models. This study explores the impact of selecting noninformative priors, offering insights into the performance of TS when dealing with new models that lack theoretical understanding.
  arXiv  Detail & Related papers  (2023-02-28T08:42:42Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) is proposed to directly sample from the posterior distribution in contextual bandits. We prove that the proposed algorithm achieves the same sublinear regret bound as the best Thompson sampling algorithms for a special case of contextual bandits.
  arXiv  Detail & Related papers  (2022-06-22T17:58:23Z)
• Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms [14.174806471635403]
  We consider approximations of sampling algorithms, such as Gradient Langevin Dynamics (SGLD) and the Random Batch Method (RBM) for Interacting Particle Dynamcs (IPD) We observe that the noise introduced by the approximation is nearly Gaussian due to the Central Limit Theorem (CLT) while the driving Brownian motion is exactly Gaussian. We harness this structure to absorb the approximation error inside the diffusion process, and obtain improved convergence guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-06-08T10:17:40Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Diffusion Approximations for Thompson Sampling in the Small Gap Regime [6.508628820027702]
  We study the process-level dynamics of Thompson sampling in the small gap'' regime.<n>We show that the process-level dynamics of Thompson sampling converge weakly to the solutions to certain differential equations and ordinary differential equations.
  arXiv  Detail & Related papers  (2021-05-19T16:28:01Z)
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring [91.22679787578438]
  We present a novel Thompson-sampling-based algorithm for partial monitoring. We prove that the new algorithm achieves the logarithmic problem-dependent expected pseudo-regret $mathrmO(log T)$ for a linearized variant of the problem with local observability.
  arXiv  Detail & Related papers  (2020-06-17T05:48:33Z)

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.