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 ε requires T = Ω(1/ε² (log1/ε)^d/2), and the average cumulative regret is at least Ω( √T(log T)^d/2 ), thus matching existing upper bounds up to the replacement of d/2 by 2d+O(1) in both cases. For the Mat\'ern-ν kernel, we give analogous bounds of the form Ω( (1/ε)^2+d/ν) and Ω( T^ν + d/2ν + d ), and discuss the resulting gaps to the existing upper bounds.