On Information Gain and Regret Bounds in Gaussian Process Bandits

Abstract

Consider the sequential optimization of an expensive to evaluate and possibly non-convex objective function $f$ from noisy feedback, that can be considered as a continuum-armed bandit problem. Upper bounds on the regret performance of several learning algorithms (GP-UCB, GP-TS, and their variants) are known under both a Bayesian (when $f$ is a sample from a Gaussian process (GP)) and a frequentist (when $f$ lives in a reproducing kernel Hilbert space) setting. The regret bounds often rely on the maximal information gain ${\gamma }_T$ between $T$ observations and the underlying GP (surrogate) model. We provide general bounds on ${\gamma }_T$ based on the decay rate of the eigenvalues of the GP kernel, whose specialisation for commonly used kernels, improves the existing bounds on ${\gamma }_T$, and subsequently the regret bounds relying on ${\gamma }_T$ under numerous settings. For the Matérn family of kernels, where the lower bounds on ${\gamma }_T$, and regret under the frequentist setting, are known, our results close a huge polynomial in $T$ gap between the upper and lower bounds (up to logarithmic in $T$ factors).

References in corpus (14)

• Practical Bayesian Optimization of Machine Learning Algorithms
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
• Finite-Time Analysis of Kernelised Contextual Bandits
• Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programming
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Information Theoretic Regret Bounds for Online Nonlinear Control
• Bandit optimisation of functions in the Matérn kernel RKHS
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
• Corruption-Tolerant Gaussian Process Bandit Optimization
• Tight Regret Bounds for Bayesian Optimization in One Dimension
• Ordinal Bayesian Optimisation
• Regret bounds for meta Bayesian optimization with an unknown Gaussian process prior
• Online learning with kernel losses

Cited by in corpus (5)

• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Optimal Order Simple Regret for Gaussian Process Bandits
• Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradients
• Adversarial Attacks on Gaussian Process Bandits
• Neural Contextual Bandits without Regret