Adaptive Rate of Convergence of Thompson Sampling for Gaussian Process Optimization
arXiv:1705.06808
Abstract
We consider the problem of global optimization of a function over a continuous domain. In our setup, we can evaluate the function sequentially at points of our choice and the evaluations are noisy. We frame it as a continuum-armed bandit problem with a Gaussian Process prior on the function. In this regime, most algorithms have been developed to minimize some form of regret. In this paper, we study the convergence of the sequential point to the global optimizer for the Thompson Sampling approach. Under some assumptions and regularity conditions, we prove concentration bounds for where the probability that is bounded away from decays exponentially fast in . Moreover, the result allows us to derive adaptive convergence rates depending on the function structure.
arXiv comment25 Pages, 7 Figures
References in corpus (10)
- Practical Bayesian Optimization of Machine Learning Algorithms
- Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design
- Analysis of Thompson Sampling for the multi-armed bandit problem
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Predictive Entropy Search for Efficient Global Optimization of Black-box Functions
- Further Optimal Regret Bounds for Thompson Sampling
- A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences
- Finite-Time Analysis of Kernelised Contextual Bandits
- Bayesian Modeling with Gaussian Processes using the GPstuff Toolbox
- A sequential Monte Carlo approach to Thompson sampling for Bayesian optimization