Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting

Many applications require optimizing an unknown, noisy function that is expensive to evaluate. We formalize this task as a multiarmed bandit problem, where the payoff function is either sampled from a Gaussian process (GP) or has low norm in a reproducing kernel Hilbert space. We resolve the important open problem of deriving regret bounds for this setting, which imply novel convergence rates for GP optimization. We analyze an intuitive Gaussian process upper confidence bound (GP-UCB) algorithm, and bound its cumulative regret in terms of maximal in- formation gain, establishing a novel connection between GP optimization and experimental design. Moreover, by bounding the latter in terms of operator spectra, we…

• NS
  National Science Foundation

  Awards: 0932392, 0953413
• M
  Microsoft
• DF
  Deutsche Forschungsgemeinschaft
• OO
  Office of Naval Research

  Awards: N00014-09-1-1044, N00014