Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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.
Yves-Marie François Ducimetière
, ,