Optimization for Gaussian Processes via Chaining

In this paper, we consider the problem of stochastic optimiz ation under a bandit feedback model. W e generalize the GP-UCB algorithm [Srinivas and al., 2012] to arbitrary kernels and search spaces. To do so, we use a notionof localized chaining to control the supremum of a Gaussian process, and provide a n ovel optimization scheme based on the computation of covering numbers. The theoretical bounds we obtain on the cumulative regret are more generic and presentthe same convergence rates as the GP-UCB algorithm. Finally, the algorithm is sho wn to be empirically more efficient than its natural competitors on simple and complex input spaces.