Optimal Order Simple Regret for Gaussian Process Bandits

2021/08/20 by Sattar Vakili, Vakili, Sattar, Nacime Bouziani +7 · 7 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Advanced Multi-Objective Optimization Algorithms #Gaussian Processes and Bayesian Inference #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2108.09262

arxiv created 2021/08/20 · arxiv updated 2021/08/23

Abstract

Consider the sequential optimization of a continuous, possibly non-convex, and expensive to evaluate objective function f. The problem can be cast as a Gaussian Process (GP) bandit where f lives in a reproducing kernel Hilbert space (RKHS). The state of the art analysis of several learning algorithms shows a significant gap between the lower and upper bounds on the simple regret performance. When N is the number of exploration trials and γ_N is the maximal information gain, we prove an O(√(γ_N/N)) bound on the simple regret performance of a pure exploration algorithm that is significantly tighter than the existing bounds. We show that this bound is order optimal up to logarithmic factors for the cases where a lower bound on regret is known. To establish these results, we prove novel and sharp confidence intervals for GP models applicable to RKHS elements which may be of broader interest.

Citations

• Simple regret for infinitely many armed bandits
• Practical Bayesian Optimization of Machine Learning Algorithms
• Bayesian Optimization with Exponential Convergence
• Taking the Human Out of the Loop: A Review of Bayesian Optimization
• Regret bounds for meta Bayesian optimization with an unknown Gaussian process prior
• Bandit optimisation of functions in the Matérn kernel RKHS

Cited by

• Gaussian Process Bandit Optimization with Few Batches
• Uniform Generalization Bounds for Overparameterized Neural Networks
• Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization
• Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards
• Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization
• Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Arms
• Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds

Related

• On Information Gain and Regret Bounds in Gaussian Process Bandits
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Regret Bounds for Deterministic Gaussian Process Bandits
• Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance
• Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations