Home > Research > Publications & Outputs > On Thompson Sampling for Smoother-than-Lipschit...

Electronic data

  • TSSmootherThanLipschitz

    Accepted author manuscript, 615 KB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

  • 2001.02323v1

    Final published version, 712 KB, PDF document

Links

Keywords

View graph of relations

On Thompson Sampling for Smoother-than-Lipschitz Bandits

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Published
Publication date26/08/2020
Host publication23rd International Conference on Artificial Intelligence and Statistics
PublisherProceedings of Machine Learning Research
Pages2612-2622
Number of pages11
<mark>Original language</mark>English

Publication series

NameProceedings of Machine Learning Research
Volume108
ISSN (Print)1938-7228

Abstract

Thompson Sampling is a well established approach to bandit and reinforcement learning problems. However its use in continuum armed bandit problems has received relatively little attention. We provide the first bounds on the regret of Thompson Sampling for continuum armed bandits under weak conditions on the function class containing the true function and sub-exponential observation noise. Our bounds are realised by analysis of the eluder dimension, a recently proposed measure of the complexity of a function class, which has been demonstrated to be useful in bounding the Bayesian regret of Thompson Sampling for simpler bandit problems under sub-Gaussian observation noise. We derive a new bound on the eluder dimension for classes of functions with Lipschitz derivatives, and generalise previous analyses in multiple regards.