  We design and analyse variations of the classical Thompson sampling (TS)
procedure for Bayesian optimisation (BO) in settings where function evaluations
are expensive, but can be performed in parallel. Our theoretical analysis shows
that a direct application of the sequential Thompson sampling algorithm in
either synchronous or asynchronous parallel settings yields a surprisingly
powerful result: making $n$ evaluations distributed among $M$ workers is
essentially equivalent to performing $n$ evaluations in sequence. Further, by
modeling the time taken to complete a function evaluation, we show that, under
a time constraint, asynchronously parallel TS achieves asymptotically lower
regret than both the synchronous and sequential versions. These results are
complemented by an experimental analysis, showing that asynchronous TS
outperforms a suite of existing parallel BO algorithms in simulations and in a
hyper-parameter tuning application in convolutional neural networks. In
addition to these, the proposed procedure is conceptually and computationally
much simpler than existing work for parallel BO.
