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

2009/12/31 by Niranjan Srinivas, Andreas Krause, Sham M. Kakade +1 · 1 citation
Computer Science · #cs.LG

paper · pdf · doi:10.1109/tit.2011.2182033

arxiv created 2010/06/09 · arxiv updated 2015/03/13

Abstract

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. 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.

Cited by

• FigBO: A Generalized Acquisition Function Framework with Look-Ahead Capability for Bayesian Optimization
• Learning-based decentralized control with collision avoidance for multi-agent systems
• Measure Theory of Conditionally Independent Random Function Evaluation

Related

• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Misspecified Gaussian Process Bandit Optimization
• Optimization as Estimation with Gaussian Processes in Bandit Settings
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding