Scalable Thompson Sampling using Sparse Gaussian Process Models

Understand

Thompson Sampling (TS) from Gaussian Process (GP) models is a powerful tool for the optimization of black-box functions.

• Although TS enjoys strong theoretical guarantees and convincing empirical performance, it incurs a large computational overhead that scales polynomially with the optimization budget.
• Recently, scalable TS methods based on sparse GP models have been proposed to increase the scope of TS, enabling its application to problems that are sufficiently multi-modal, noisy or combinatorial to require more than a few hundred evaluations to be solved.
• However, the approximation error introduced by sparse GPs invalidates all existing regret bounds.