Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2012 | public
Journal Article

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

Abstract

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 obtain explicit sublinear regret bounds for many commonly used covariance functions. In some important cases, our bounds have surprisingly weak dependence on the dimensionality. In our experiments on real sensor data, GP-UCB compares favorably with other heuristical GP optimization approaches.

Additional Information

© 2012 IEEE. Manuscript received October 17, 2010; accepted September 27, 2011. Date of publication January 24, 2012; date of current version April 17, 2012. This work was supported in part by the Office of Naval Research under Grant N00014-09-1-1044, in part by the National Science Foundation under Grants CNS-0932392 and IIS-0953413, in part by a gift from Microsoft Corporation, and in part by the Excellence Initiative of the German Research Foundation (DFG). This manuscript is an extended version of our paper that appeared in ICML 2010 [1]. The authors thank M. Hutter for insightful comments on an earlier version of this paper. The authors also thank the anonymous reviewers for detailed feedback.

Additional details

Created:
August 22, 2023
Modified:
October 17, 2023