CaltechAUTHORS
  A Caltech Library Service

Langevin Monte Carlo for Contextual Bandits

Xu, Pan and Zheng, Hongkai and Mazumdar, Eric V. and Azizzadenesheli, Kamyar and Anandkumar, Anima (2022) Langevin Monte Carlo for Contextual Bandits. Proceedings of Machine Learning Research, 162 . pp. 24830-24850. ISSN 2640-3498. https://resolver.caltech.edu/CaltechAUTHORS:20220714-212437915

[img] PDF - Published Version
See Usage Policy.

5MB
[img] PDF - Accepted Version
See Usage Policy.

5MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220714-212437915

Abstract

We study the efficiency of Thompson sampling for contextual bandits. Existing Thompson sampling-based algorithms need to construct a Laplace approximation (i.e., a Gaussian distribution) of the posterior distribution, which is inefficient to sample in high dimensional applications for general covariance matrices. Moreover, the Gaussian approximation may not be a good surrogate for the posterior distribution for general reward generating functions. We propose an efficient posterior sampling algorithm, viz., Langevin Monte Carlo Thompson Sampling (LMC-TS), that uses Markov Chain Monte Carlo (MCMC) methods to directly sample from the posterior distribution in contextual bandits. Our method is computationally efficient since it only needs to perform noisy gradient descent updates without constructing the Laplace approximation of the posterior distribution. 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, viz., linear contextual bandits. We conduct experiments on both synthetic data and real-world datasets on different contextual bandit models, which demonstrates that directly sampling from the posterior is both computationally efficient and competitive in performance.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://proceedings.mlr.press/v162/xu22p.htmlPublisherArticle
https://doi.org/10.48550/arXiv.2206.11254arXivDiscussion Paper
ORCID:
AuthorORCID
Mazumdar, Eric V.0000-0002-1815-269X
Azizzadenesheli, Kamyar0000-0001-8507-1868
Anandkumar, Anima0000-0002-6974-6797
Additional Information:© 2022 by the author(s). The authors would like to thank the anonymous reviewers for their invaluable comments. PX is supported by PIMCO Postdoctoral Fellowship. AA is partially supported by Bren Named Chair Professorship at Caltech.
Funders:
Funding AgencyGrant Number
PIMCOUNSPECIFIED
Bren Professor of Computing and Mathematical SciencesUNSPECIFIED
Record Number:CaltechAUTHORS:20220714-212437915
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20220714-212437915
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:115574
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:15 Jul 2022 22:54
Last Modified:20 Dec 2022 22:18

Repository Staff Only: item control page