When optimizing an expensive, black-box function $f(x)$—such as tuning a deep neural network's hyperparameters or designing a new chemical compound—we face a fundamental dilemma: should we sample where we believe the function is maximized (exploitation), or should we sample where we are highly uncertain (exploration)?
To formalize this problem, researchers often model the unknown objective function using a Gaussian Process (GP) and frame the task as a kernelized multi-armed bandit problem. As highlighted by Glowacka et al., maintaining this balance is critical for deriving theoretical performance guarantees. We measure an algorithm's performance using cumulative regret ($R_T$), which is the sum of the gaps between the true global maximum and the values actually sampled over $T$ steps:
$$R_T = \sum_{t=1}^T \left( f(x^*) - f(x_t) \right)$$
To prove that an optimization algorithm is guaranteed to find the global maximum, we must show that its cumulative regret is sublinear with respect to time ($\lim_{T \to \infty} R_T / T = 0$). This ensures that the average error vanishes as we gather more samples. For over a decade, researchers have worked to establish, tighten, and generalize these sublinear regret bounds to explain exactly why and how fast Bayesian optimization converges.
The Information-Theoretic Foundation
How can we guarantee that an algorithm won't get trapped making sub-optimal choices forever in a continuous search space? The foundational breakthrough came from Srinivas et al. and Krause et al., who introduced the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm.
GP-UCB selects the next point to evaluate by maximizing an optimistic surrogate: the predictive mean plus a scaled predictive standard deviation. The authors proved that the cumulative regret of this strategy is fundamentally constrained by an information-theoretic quantity known as the maximum information gain ($\gamma_T$).
$$\gamma_T = \max_{A \subset X, |A|=T} I(y_A; f_A)$$
The intuition behind this connection is elegant:
- The Choice: At each step, GP-UCB either chooses a point with a high function value (incurring low regret) or a point with high uncertainty (yielding high information gain).
- The Bound: The total amount of information you can possibly extract from a smooth function is limited by the properties of its kernel. Smooth kernels (like the Squared Exponential kernel) feature rapid eigenvalue decay, meaning that after a certain number of samples, the function becomes highly predictable.
- The Convergence: Because the cumulative information gain $\gamma_T$ grows sublinearly for standard kernels, the algorithm cannot continue to make large exploration mistakes indefinitely.
Early work by Grünewälder et al. confirmed this theoretical consistency for smooth, Hölder-continuous reward functions, establishing that the regret eventually vanishes as the sample size approaches infinity.
The Matérn Gap
While the information-theoretic framework provided the first "no-regret" guarantees, a significant gap persisted between theory and practice. For the widely used Matérn family of kernels—which model functions with realistic, limited smoothness—the original upper bounds on regret were highly pessimistic, sometimes failing to guarantee sublinear regret in complex or high-dimensional spaces.
Scarlett exposed this looseness in one dimension, establishing a tight lower bound of $\Omega(\sqrt{T})$ and an upper bound of $O(\sqrt{T \log T})$ for noisy Bayesian optimization. This proved that the actual regret for Matérn kernels scales near-linearly with the square root of time, matching the behavior of much smoother kernels and revealing that the existing theory was overly conservative.
The primary culprit behind these loose bounds was the width of the confidence intervals used by the algorithms. To guarantee that the true function remains trapped within the upper and lower confidence bounds with high probability across an infinite-dimensional space, early proofs relied on overly broad, conservative confidence widths.
Closing the Gap via Modern Concentration
To align theory with empirical reality, recent research has introduced tighter concentration inequalities and deeper spectral analyses of kernel matrices.
Tighter Confidence Intervals
Chowdhury et al. derived a novel concentration inequality for martingales in infinite-dimensional Hilbert spaces. By shrinking the required confidence interval width by a factor of approximately $O(\ln^{3/2} T)$, the authors accelerated the proven convergence rates for both frequentist kernelized UCB and Thompson Sampling without sacrificing safety.
Spectral Analysis of Information Gain
Instead of altering the algorithm, Vakili et al. re-examined the physics of the kernels themselves. By leveraging the spectral properties and eigenvalue decay of Matérn kernels, they derived significantly tighter bounds on the maximum information gain ($\gamma_T$), reducing the gap between the theoretical upper and lower performance bounds to a mere logarithmic factor.
Resolving Sublinear Regret
For years, it remained an open question whether standard GP-UCB was truly sublinear for rougher kernels. Whitehouse et al. resolved this by proving that GP-UCB achieves sublinear regret for any kernel with polynomial eigendecay (including the Matérn kernel). The key insight was that the algorithm's regularization parameter must be carefully tuned to match the underlying smoothness of the kernel.
Query Concentration
The final piece of the puzzle came from explaining where the algorithm samples. Iwazaki proved that GP-UCB achieves a near-optimal $\tilde{O}(\sqrt{T})$ cumulative regret bound. The mathematical breakthrough came from showing that the algorithm's queries naturally concentrate around the global maximum rather than wandering aimlessly through the search space, meaning it stops wasting information gain on irrelevant regions.
Generalizing the Guarantees
With the theoretical foundations of GP-UCB firmly secured, researchers have extended sublinear regret guarantees to other popular acquisition functions, environments, and search spaces.
Expected Improvement (EI)
Practitioners frequently prefer Expected Improvement (EI) over UCB because it requires no parameter tuning for exploration. However, proving its convergence in noisy settings was historically difficult. Tran-The provided the first convergence guarantees for EI in noisy bandit optimization by using the maximum of the predictive mean as a stable baseline (incumbent), matching the information-theoretic rates of GP-UCB. Wang et al. extended this to Constrained Expected Improvement (CEI), proving sublinear convergence rates for both Squared Exponential and Matérn kernels when the search space is restricted by unknown black-box constraints.
Alternative Frameworks and Non-Stationary Environments
Other acquisition strategies have also been validated. For instance, Contal et al. proposed GP-MI, which explicitly uses mutual information to guide exploration within a modular framework that decouples the exploration policy from the surrogate model. To handle real-world scenarios where the underlying function drifts over time, Zhou et al. introduced frequentist no-regret algorithms (R-GP-UCB and SW-GP-UCB) that utilize restarting and sliding-window mechanisms to track moving targets.
Order-Optimal and Exponential Convergence
When we only care about the quality of the final recommendation rather than the path taken, we measure simple regret. Vakili et al. refined the relationship between information gain and simple regret to achieve order-optimal bounds that match physical lower limits.
To speed up optimization, Salgia et al. developed GP-ThreDS, which uses a tree-based domain-shrinking strategy to achieve order-optimal regret while running significantly faster than standard GP-UCB. In noiseless environments, Tran-The et al. demonstrated that integrating GP models with hierarchical tree search enables an exponential decay in simple regret ($O(N^{-\sqrt{N}})$), vastly outperforming traditional sublinear rates.
Discrete and Combinatorial Spaces
Finally, these guarantees are not restricted to continuous domains. Oh et al. extended the framework to discrete combinatorial spaces (such as optimizing permutations for scheduling). By proving the positive definiteness of a position-based acquisition-weighted kernel, the authors guaranteed sublinear cumulative regret even when searching through discrete ordering spaces.
Key Foundational Work
Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting (2012) — contributed 2 concept elements to this direction.
Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design (2010) — contributed 2 concept elements to this direction.
Preface (2012) — contributed 2 concept elements to this direction.