Langevin Monte Carlo for Contextual Bandits

  • 2022-06-22 18:58:23
  • Pan Xu, Hongkai Zheng, Eric Mazumdar, Kamyar Azizzadenesheli, Anima Anandkumar
  • 0

Abstract

We study the efficiency of Thompson sampling for contextual bandits. ExistingThompson sampling-based algorithms need to construct a Laplace approximation(i.e., a Gaussian distribution) of the posterior distribution, which isinefficient to sample in high dimensional applications for general covariancematrices. Moreover, the Gaussian approximation may not be a good surrogate forthe posterior distribution for general reward generating functions. We proposean efficient posterior sampling algorithm, viz., Langevin Monte Carlo ThompsonSampling (LMC-TS), that uses Markov Chain Monte Carlo (MCMC) methods todirectly sample from the posterior distribution in contextual bandits. Ourmethod is computationally efficient since it only needs to perform noisygradient descent updates without constructing the Laplace approximation of theposterior distribution. We prove that the proposed algorithm achieves the samesublinear regret bound as the best Thompson sampling algorithms for a specialcase of contextual bandits, viz., linear contextual bandits. We conductexperiments on both synthetic data and real-world datasets on differentcontextual bandit models, which demonstrates that directly sampling from theposterior is both computationally efficient and competitive in performance.

 

Quick Read (beta)

loading the full paper ...