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

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.

References in corpus (3)

• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• Near-optimal Nonmyopic Value of Information in Graphical Models
• Posterior consistency of Gaussian process prior for nonparametric binary regression

Cited by in corpus (164)

• On-the-fly Closed-loop Autonomous Materials Discovery via Bayesian Active Learning
• Simulation optimization: A review of algorithms and applications
• Gryffin: An algorithm for Bayesian optimization of categorical variables informed by expert knowledge
• Stable Gaussian Process based Tracking Control of Euler-Lagrange Systems
• Bayesian optimization of a free-electron laser
• An Efficient Batch Constrained Bayesian Optimization Approach for Analog Circuit Synthesis via Multi-objective Acquisition Ensemble
• Online learning-based Model Predictive Control with Gaussian Process Models and Stability Guarantees
• Sequential Gallery for Interactive Visual Design Optimization
• Performance-Driven Cascade Controller Tuning with Bayesian Optimization
• Successive Bayesian Reconstructor for Channel Estimation in Fluid Antenna Systems
• Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration
• Multi-Fidelity Cost-Aware Bayesian Optimization
• Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization
• Bayesian emulator optimisation for cosmology: application to the Lyman-alpha forest
• Machine Learning for Achieving Bose-Einstein Condensation of Thulium Atoms
• An Information-Theoretic Analysis of Thompson Sampling
• On the Robustness of Temporal Properties for Stochastic Models
• Gaussian Process Optimization with Mutual Information
• Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem
• Knowledge transfer across cell lines using Hybrid Gaussian Process models with entity embedding vectors
• Information-Guided Robotic Maximum Seek-and-Sample in Partially Observable Continuous Environments
• General framework for cosmological dark matter bounds using $N$-body simulations
• A Tutorial on Thompson Sampling
• Time-Varying Gaussian Process Bandit Optimization
• Batched Gaussian Process Bandit Optimization via Determinantal Point Processes
• Guaranteed Coverage Prediction Intervals with Gaussian Process Regression
• Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits
• Actively Learning Gaussian Process Dynamics
• Physics-constrained Deep Learning for Robust Inverse ECG Modeling
• Verifying Controllers Against Adversarial Examples with Bayesian Optimization
• AI-optimized detector design for the future Electron-Ion Collider: the dual-radiator RICH case
• Sample-Efficient and Surrogate-Based Design Optimization of Underwater Vehicle Hulls
• Bayesian optimization for computationally extensive probability distributions
• Personalized Optimization with User's Feedback
• Sequential Design for Ranking Response Surfaces
• Query Efficient Posterior Estimation in Scientific Experiments via Bayesian Active Learning
• An Introduction to Gaussian Process Models
• Bayesian Optimization For Multi-Objective Mixed-Variable Problems
• Reinforcement Learning in Modern Biostatistics: Constructing Optimal Adaptive Interventions
• Incorporating Expert Prior in Bayesian Optimisation via Space Warping
• Evolving Rewards to Automate Reinforcement Learning
• Stable Gaussian Process based Tracking Control of Lagrangian Systems
• Streaming kernel regression with provably adaptive mean, variance, and regularization
• Policy Gradients for Contextual Recommendations
• Automatic Document Image Binarization using Bayesian Optimization
• Interpolating Detailed Simulations of Kilonovae: Adaptive Learning and Parameter Inference Applications
• Distributed multi-agent target search and tracking with Gaussian process and reinforcement learning
• Learning Temporal Logical Properties Discriminating ECG models of Cardiac Arrhytmias
• Safe Learning for Uncertainty-Aware Planning via Interval MDP Abstraction
• Strategy Synthesis for Partially-known Switched Stochastic Systems
• Uniform Error Bounds for Gaussian Process Regression with Application to Safe Control
• Constrained Bayesian Optimization with Max-Value Entropy Search
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Modeling and Active Learning for Experiments with Quantitative-Sequence Factors
• Safe Learning-based Gradient-free Model Predictive Control Based on Cross-entropy Method
• A sequential Monte Carlo approach to Thompson sampling for Bayesian optimization
• Hierarchical Quality-Diversity for Online Damage Recovery
• Learning to Optimize Via Posterior Sampling
• GoSafeOpt: Scalable Safe Exploration for Global Optimization of Dynamical Systems
• Computational design of antimicrobial active surfaces via automated Bayesian optimization
• Exploration in Online Advertising Systems with Deep Uncertainty-Aware Learning
• Correlated Multiarmed Bandit Problem: Bayesian Algorithms and Regret Analysis
• KPC: Learning-Based Model Predictive Control with Deterministic Guarantees
• Uniform Error and Posterior Variance Bounds for Gaussian Process Regression with Application to Safe Control
• Counterfactual Explanations for Arbitrary Regression Models
• Differentially Flat Learning-based Model Predictive Control Using a Stability, State, and Input Constraining Safety Filter
• Evaluating Gaussian Process Metamodels and Sequential Designs for Noisy Level Set Estimation
• Bayesian Optimization for Dynamic Problems
• Region of Attraction for Power Systems using Gaussian Process and Converse Lyapunov Function -- Part I: Theoretical Framework and Off-line Study
• Adaptive and Collaborative Bathymetric Channel-Finding Approach for Multiple Autonomous Marine Vehicles
• Posterior Variance Analysis of Gaussian Processes with Application to Average Learning Curves
• Inverse Bayesian Optimization: Learning Human Acquisition Functions in an Exploration vs Exploitation Search Task
• Multiresolution Tensor Learning for Efficient and Interpretable Spatial Analysis
• Scaling Gaussian Processes with Derivative Information Using Variational Inference
• Optimizing with Low Budgets: a Comparison on the Black-box Optimization Benchmarking Suite and OpenAI Gym
• Bayesian optimization of electron energy from laser wakefield accelerators
• An informative path planning framework for UAV-based terrain monitoring
• PHOENICS: A universal deep Bayesian optimizer
• Trading Convergence Rate with Computational Budget in High Dimensional Bayesian Optimization
• Safe Guaranteed Exploration for Non-linear Systems
• Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration
• Safety Guarantees for Planning Based on Iterative Gaussian Processes
• Process-constrained batch Bayesian approaches for yield optimization in multi-reactor systems
• Causality-Aided Falsification
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Sampling Acquisition Functions for Batch Bayesian Optimization
• Advancing Bayesian Optimization: The Mixed-Global-Local (MGL) Kernel and Length-Scale Cool Down
• A Multi-Fidelity Bayesian Approach to Safe Controller Design
• Stochastic Process Bandits: Upper Confidence Bounds Algorithms via Generic Chaining
• NOMU: Neural Optimization-based Model Uncertainty
• Bayesian Optimization for Robust State Preparation in Quantum Many-Body Systems
• Modeling Human Decision-making in Generalized Gaussian Multi-armed Bandits
• An active learning approach for improving the performance of equilibrium based chemical simulations
• Adaptive Gaussian Process Regression for Efficient Building of Surrogate Models in Inverse Problems
• Convergence Certificate for Stochastic Derivative-Free Trust-Region Methods based on Gaussian Processes
• Bayesian Optimization that Limits Search Region to Lower Dimensions Utilizing Local GPR
• Learning-Based Safety-Stability-Driven Control for Safety-Critical Systems under Model Uncertainties
• Bayesian Optimization with Directionally Constrained Search
• Adaptive Rate of Convergence of Thompson Sampling for Gaussian Process Optimization
• Active Requirement Mining of Bounded-Time Temporal Properties of Cyber-Physical Systems
• Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning
• Discovering Valuable Items from Massive Data
• On Thompson Sampling for Smoother-than-Lipschitz Bandits
• On Batch Bayesian Optimization
• Localized active learning of Gaussian process state space models
• Safe Online Learning-based Formation Control of Multi-Agent Systems with Gaussian Processes
• Gravitational collapse at low to moderate Mach numbers: The relationship between star formation efficiency and the fraction of mass in the massive object
• Bayesian Optimization for Polynomial Time Probabilistically Complete STL Trajectory Synthesis
• A Successive-Elimination Approach to Adaptive Robotic Sensing
• Surrogate-Based Simulation Optimization
• Automated machine learning for borehole resistivity measurements
• Surrogate-based Optimization using Mutual Information for Computer Experiments (optim-MICE)
• Exploration Through Reward Biasing: Reward-Biased Maximum Likelihood Estimation for Stochastic Multi-Armed Bandits
• A Bi-Objective Optimization Based Acquisition Strategy for Batch Bayesian Global Optimization
• Bayesian Optimization for Categorical and Category-Specific Continuous Inputs
• Multiscale Gaussian Process Level Set Estimation
• A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents
• Uncertainty-aware Safe Exploratory Planning using Gaussian Process and Neural Control Contraction Metric
• Gaussian Process Uniform Error Bounds with Unknown Hyperparameters for Safety-Critical Applications
• Adaptive Batching for Gaussian Process Surrogates with Application in Noisy Level Set Estimation
• High-fidelity electronic structure and properties of InSb: $G_0{W}_0$ and Bayesian-optimized hybrid functionals and DFT+$U$ approaches
• Gaussian Process Bandit Optimization with Few Batches
• Using Distance Correlation for Efficient Bayesian Optimization
• Bayesian Optimization using Pseudo-Points
• Bridging Logic and Learning: Decoding Temporal Logic Embeddings via Transformers
• Uncertainty-Informed Active Perception for Open Vocabulary Object Goal Navigation
• PACSBO: Probably approximately correct safe Bayesian optimization
• Personalized Education at Scale
• Learning-based Event-triggered MPC with Gaussian processes under terminal constraints
• Efficient safe learning for controller tuning with experimental validation
• Multi-Robot Gaussian Process Estimation and Coverage: A Deterministic Sequencing Algorithm and Regret Analysis
• Adaptive Configuration Oracle for Online Portfolio Selection Methods
• Constrained, Global Optimization of Functions with Lipschitz Continuous Gradients
• MISO-wiLDCosts: Multi Information Source Optimization with Location Dependent Costs
• Efficient Bayesian Optimization using Multiscale Graph Correlation
• The Kalai-Smorodinski solution for many-objective Bayesian optimization
• Expedited Multi-Target Search with Guaranteed Performance via Multi-fidelity Gaussian Processes
• AutoCP: Automated Pipelines for Accurate Prediction Intervals
• On Hyper-parameter Tuning for Stochastic Optimization Algorithms
• Lightweight Distributed Gaussian Process Regression for Online Machine Learning
• Optimization for Gaussian Processes via Chaining
• Adaptive Pricing in Insurance: Generalized Linear Models and Gaussian Process Regression Approaches
• The Impact of Data on the Stability of Learning-Based Control- Extended Version
• One-parameter family of acquisition functions for efficient global optimization
• Genealogical Population-Based Training for Hyperparameter Optimization
• Designing over uncertain outcomes with stochastic sampling Bayesian optimization
• HOAX: A Hyperparameter Optimization Algorithm Explorer for Neural Networks
• Certified Multi-Fidelity Zeroth-Order Optimization
• Bayesian optimization approach for tracking the location and orientation of a moving target using far-field data
• Bayesian Unification of Gradient and Bandit-based Learning for Accelerated Global Optimisation
• Non-Linear Model-Based Sequential Decision-Making in Agriculture
• High-Dimensional Bayesian Optimization via Random Projection of Manifold Subspaces
• Accelerated Bayesian Optimization throughWeight-Prior Tuning
• Covariance Function Pre-Training with m-Kernels for Accelerated Bayesian Optimisation
• A Map of Bandits for E-commerce
• Bayesian Optimization and Deep Learning forsteering wheel angle prediction
• Gaussian Processes Model-based Control of Underactuated Balance Robots
• ${\mathcal{L}}_1$-$\mathcal{G}\mathcal{P}$: ${\mathcal{L}}_1$ Adaptive Control with Bayesian Learning
• Sequential Subspace Search for Functional Bayesian Optimization Incorporating Experimenter Intuition
• On the equivalence of probability spaces
• Learning-Based Modular Indirect Adaptive Control for a Class of Nonlinear Systems
• Dynamic Security Assessment of Small-Signal Stability for Power Systems using Windowed Online Gaussian Process
• Stable Bayesian Optimisation via Direct Stability Quantification
• Contraction ${\mathcal{L}}_1$-Adaptive Control using Gaussian Processes