Fast, Precise Thompson Sampling for Bayesian Optimization

Thompson sampling (TS) has optimal regret and excellent empirical performance in multi-armed bandit problems. Yet, in Bayesian optimization, TS underperforms popular acquisition functions (ex., EI, UCB). TS samples arms according to the probability that they are optimal. A recent algorithm, P-Star Sampler, implements such a sampling, but does not scale well with arm dimension or number of measurements. We present an algorithm, Stagger Thompson Sampler (STS), that produces similar quality samples but with better scaling. We show that STS outperforms traditional Thompson sampling and other acquisition methods in numerical experiments of several test functions across a broad range of dimensions.