Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

Abstract

In this paper, we consider the problem of sequentially optimizing a black-box function $f$ based on noisy samples and bandit feedback. We assume that $f$ is smooth in the sense of having a bounded norm in some reproducing kernel Hilbert space (RKHS), yielding a commonly-considered non-Bayesian form of Gaussian process bandit optimization. We provide algorithm-independent lower bounds on the simple regret, measuring the suboptimality of a single point reported after $T$ rounds, and on the cumulative regret, measuring the sum of regrets over the $T$ chosen points. For the isotropic squared-exponential kernel in $d$ dimensions, we find that an average simple regret of $\epsilon$ requires $T=\Omega (\frac{1}{{\epsilon }^2}(\log \frac{1}{\epsilon }{)}^{d/2})$, and the average cumulative regret is at least $\Omega \left(\sqrt{T(\log T{)}^{d/2}}\right)$, thus matching existing upper bounds up to the replacement of $d/2$ by $2d+O(1)$ in both cases. For the Matérn-$\nu$ kernel, we give analogous bounds of the form $\Omega ((\frac{1}{\epsilon }{)}^{2+d/\nu })$ and $\Omega \left(T^{\frac{\nu +d}{2\nu +d}}\right)$, and discuss the resulting gaps to the existing upper bounds.

Appearing in COLT 2017. This version corrects a few minor mistakes in Table I, which summarizes the new and existing regret bounds

Cited by in corpus (25)

• Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces
• Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization
• Bandit optimisation of functions in the Matérn kernel RKHS
• Corruption-Tolerant Gaussian Process Bandit Optimization
• Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
• Gaussian Process Optimization with Adaptive Sketching: Scalable and No Regret
• On Information Gain and Regret Bounds in Gaussian Process Bandits
• Kernel Methods for Cooperative Multi-Agent Contextual Bandits
• Tight Regret Bounds for Bayesian Optimization in One Dimension
• Local Differential Privacy for Bayesian Optimization
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Optimal Order Simple Regret for Gaussian Process Bandits
• Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes
• No-regret Algorithms for Multi-task Bayesian Optimization
• Continuum-Armed Bandits: A Function Space Perspective
• Lenient Regret and Good-Action Identification in Gaussian Process Bandits
• No-Regret Algorithms for Private Gaussian Process Bandit Optimization
• Gaussian Process Bandit Optimization with Few Batches
• Multiscale Gaussian Process Level Set Estimation
• Approximation Theory Based Methods for RKHS Bandits
• Mixed Strategies for Robust Optimization of Unknown Objectives
• Contraction methods for continuous optimization
• How to gamble with non-stationary $\mathcal{X}$-armed bandits and have no regrets
• Neural Contextual Bandits without Regret