Time-Varying Gaussian Process Bandit Optimization

Abstract

We consider the sequential Bayesian optimization problem with bandit feedback, adopting a formulation that allows for the reward function to vary with time. We model the reward function using a Gaussian process whose evolution obeys a simple Markov model. We introduce two natural extensions of the classical Gaussian process upper confidence bound (GP-UCB) algorithm. The first, R-GP-UCB, resets GP-UCB at regular intervals. The second, TV-GP-UCB, instead forgets about old data in a smooth fashion. Our main contribution comprises of novel regret bounds for these algorithms, providing an explicit characterization of the trade-off between the time horizon and the rate at which the function varies. We illustrate the performance of the algorithms on both synthetic and real data, and we find the gradual forgetting of TV-GP-UCB to perform favorably compared to the sharp resetting of R-GP-UCB. Moreover, both algorithms significantly outperform classical GP-UCB, since it treats stale and fresh data equally.

To appear in AISTATS 2016

References in corpus (4)

• Practical Bayesian Optimization of Machine Learning Algorithms
• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• Bayesian Online Changepoint Detection
• High Dimensional Bayesian Optimisation and Bandits via Additive Models

Cited by in corpus (18)

• Personalized Optimization with User's Feedback
• Distributionally Robust Bayesian Optimization
• Provably Efficient Online Hyperparameter Optimization with Population-Based Bandits
• Bayesian Optimization for Dynamic Problems
• Corruption-Tolerant Gaussian Process Bandit Optimization
• Tight Regret Bounds for Bayesian Optimization in One Dimension
• Dynamic Causal Bayesian Optimization
• Tuning Mixed Input Hyperparameters on the Fly for Efficient Population Based AutoRL
• Gaussian Process Bandit Optimization of the Thermodynamic Variational Objective
• Weighted Gaussian Process Bandits for Non-stationary Environments
• Mixed Strategies for Robust Optimization of Unknown Objectives
• Lookahead Acquisition Functions for Finite-Horizon Time-Dependent Bayesian Optimization and Application to Quantum Optimal Control
• Recursive Two-Step Lookahead Expected Payoff for Time-Dependent Bayesian Optimization
• Fast Physical Activity Suggestions: Efficient Hyperparameter Learning in Mobile Health
• Cost-Efficient Online Hyperparameter Optimization
• Exploiting Class Learnability in Noisy Data
• Streamlined Empirical Bayes Fitting of Linear Mixed Models in Mobile Health
• No-Regret Algorithms for Time-Varying Bayesian Optimization