AI Insight
This paper introduces TS-SA, a new algorithm for multi-armed bandit problems that combines Langevin-based Thompson Sampling with stochastic approximation. Unlike traditional methods that restart a Markov chain for each new observation, TS-SA maintains a single continuing chain per arm by taking one Langevin step per reward and updating parameter estimates through decreasing weights over time. The authors prove a near-optimal regret bound of Õ(√KT) under log-concavity and smoothness conditions, and experimental results show strong performance compared to standard baselines.
Why it matters
This approach simplifies computational requirements for sequential decision-making problems where exact posterior sampling is intractable, making Thompson Sampling more practical for applications like clinical trials, online advertising, and recommendation systems. The single-step update per observation reduces computational overhead while maintaining theoretical guarantees and empirical performance.
Understand the Science
⚠️ Preprint – Noch nicht peer-reviewed
Dieser Artikel wurde noch nicht von unabhängigen Experten begutachtet. Die Ergebnisse sind vorläufig und sollten mit Vorsicht interpretiert werden.
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.
Source: Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective