Output details

Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations

<24>

Gaussian process bandits are powerful techniques for black-box optimization. They have impacted many academic and industrial domains, including personalization, robotics and automatic algorithm configuration. Despite great practical success, the problem of obtaining theoretical convergence rates for these algorithms was open for about fifty years. In 2009, Srinivas, Krause, Kakade and Seeger showed that the cumulative regret of these algorithms vanishes at a squared-root rate. Here, we proved that the simple regret vanishes at a much faster rate (exponential) and that the cumulative regret is in fact finite for deterministic observations. Our theoretical results provide new insights for novel algorithm design.