Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design

Understand

Many applications require optimizing an unknown, noisy function that is expensive to evaluate.

• We formalize this task as a multi-armed bandit problem, where the payoff function is either sampled from a Gaussian process (GP) or has low RKHS norm.
• We resolve the important open problem of deriving regret bounds for this setting, which imply novel convergence rates for GP optimization.
• We analyze GP-UCB, an intuitive upper-confidence based algorithm, and bound its cumulative regret in terms of maximal information gain, establishing a novel connection between GP optimization and experimental design.