Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding

Bayesian optimization is a powerful framework for global search, using maximum a posteriori updates instead of simulated annealing. We cast it as a multiarmed bandit problem with a Gaussian process (GP) for the payoff function. Action selections rely on upper confidence bound (UCB) or expected improvement (EI). Prior works with GPs faced challenges for large iteration horizons (<inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula>) due to cubic scaling in posterior computation. To address this, we propose a simple thresholding: incorporating an action into the GP posterior only when its conditional entropy surpasses <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>. Doing so permits us to precisely characterize the tradeoff between regret bounds of GP bandit algorithms and complexity of the posterior distributions depending on the compression parameter <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula> for both discrete and continuous action sets. To best of our knowledge, this is the first result which allows us to obtain sublinear regret bounds while still maintaining sublinear growth rate of the complexity of the posterior which is linear in the existing literature. Moreover, a provably finite bound on the complexity could be achieved but the algorithm would result in <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-regret which means <inline-formula><tex-math notation="LaTeX">$\textbf{Reg}_{T}/T\rightarrow\mathcal{O}(\epsilon)$</tex-math></inline-formula> as <inline-formula><tex-math notation="LaTeX">$T\rightarrow\infty$</tex-math></inline-formula>. Experiments demonstrate state-of-the-art accuracy and complexity tradeoffs for GP bandit algorithms in global optimization, highlighting the benefits of compressed GPs in bandit settings.