In this paper, we consider the problem of sequentially optimizing a black-box function based on noisy samples and bandit feedback. We assume that 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 rounds, and on the cumulative regret, measuring the sum of regrets over the chosen points. For the isotropic squared-exponential kernel in dimensions, we find that an average simple regret of requires , and the average cumulative regret is at least , thus matching existing upper bounds up to the replacement of by in both cases. For the Mat'ern- kernel, we give analogous bounds of the form and , and discuss the resulting gaps to the existing upper bounds.
Florent Gérard Krzakala, Lenka Zdeborová, Hugo Chao Cui
Yves-Marie François Ducimetière