On Thompson Sampling with Langevin Algorithms

Abstract

Thompson sampling for multi-armed bandit problems is known to enjoy favorable performance in both theory and practice. However, it suffers from a significant limitation computationally, arising from the need for samples from posterior distributions at every iteration. We propose two Markov Chain Monte Carlo (MCMC) methods tailored to Thompson sampling to address this issue. We construct quickly converging Langevin algorithms to generate approximate samples that have accuracy guarantees, and we leverage novel posterior concentration rates to analyze the regret of the resulting approximate Thompson sampling algorithm. Further, we specify the necessary hyperparameters for the MCMC procedure to guarantee optimal instance-dependent frequentist regret while having low computational complexity. In particular, our algorithms take advantage of both posterior concentration and a sample reuse mechanism to ensure that only a constant number of iterations and a constant amount of data is needed in each round. The resulting approximate Thompson sampling algorithm has logarithmic regret and its computational complexity does not scale with the time horizon of the algorithm.

References in corpus (12)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Rates of contraction of posterior distributions based on Gaussian process priors
• Further Optimal Regret Bounds for Thompson Sampling
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• A Complete Recipe for Stochastic Gradient MCMC
• Sampling Can Be Faster Than Optimization
• Convergence of Langevin MCMC in KL-divergence
• A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
• Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices
• Variational inference for the multi-armed contextual bandit
• A Diffusion Process Perspective on Posterior Contraction Rates for Parameters

Cited by in corpus (3)

• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
• Optimal Order Simple Regret for Gaussian Process Bandits
• Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification