Regret and Belief Complexity Tradeoff 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 ($T$) 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 $\epsilon$. 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 $\epsilon$ 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 $\epsilon$-regret which means $\textbf{Reg}_{T}/T\rightarrow\mathcal{O}(\epsilon)$ as $T\rightarrow\infty$. 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.

I. Introduction

Bayesian optimization is a framework for global optimization of a black box function via noisy evaluations [2] and provides an alternative to simulated annealing [3], [4] or exhaustive search [5]. These methods have proven adept at hyper-parameter tuning of machine learning models [6], [7], nonlinear system identification [8], experimental design [9], [10], and semantic mapping [11]. More specifically, it denote the function we seek to optimize through noisy samples, i.e., for a given choice , we observe sequentially. We make no assumptions for now on the convexity, smoothness, or other properties of , other than each function evaluation must be selected judiciously. Our goal is to select a sequence of actions that eventuate in competitive performance with respect to the optimal selection . For sequential decision making, a canonical performance metric is regret, which quantifies the performance of a sequence of decisions as compared with the optimal action : \begin{align*} \textbf{Reg}_{T}:=\sum_{t=1}^{T}(f({\mathbf{x}}^{*})-f({\mathbf{x}}_{t})).\tag{I.1} \end{align*}