Bayesian Optimization (BO) is a powerful tool for finding the global maximum of expensive "black-box" functions. However, its success hinges on a critical assumption: that we have a good "prior" model for the function we are trying to optimize. In practice, we often have multiple competing guesses for this prior—perhaps from different experts—and to make matters worse, the function itself might be changing over time.
A new paper from researchers at the University of Oxford and Toyota Motor Corporation, titled "Time-Varying Gaussian Process Bandits with Unknown Prior," introduces a novel algorithm called PE-GP-UCB to tackle this exact challenge.
TL;DR
The authors propose PE-GP-UCB, the first Gaussian Process-based bandit algorithm that handles both time-varying functions and unknown priors with theoretical regret guarantees. By combining a "doubly optimistic" selection strategy with a robust prior elimination mechanism, it significantly outperforms standard methods like Maximum Likelihood Estimation (MLE) in dynamic environments.
What Problem Does This Paper Address?
Standard BO algorithms typically assume the prior (the Gaussian Process kernel and mean function) is known. When it's not, practitioners often use Type-II Maximum Likelihood Estimation (MLE) to pick the "best" prior on the fly. However, MLE lacks universal consistency guarantees, especially for non-stationary problems.
Another approach, Regret Balancing, works by comparing the performance of different models. But in a time-varying setting—where the function changes at every step—this fails. If you get a low value, is it because your prior is wrong, or because the function just dropped? Regret Balancing can't tell the difference, leading to poor performance in dynamic real-world tasks like environment monitoring or hyperparameter tuning for reinforcement learning.
Methods
The core contribution is the PE-GP-UCB (Prior Elimination GP-UCB) algorithm. It operates on two main principles:
- Double Optimism: At each step, the algorithm doesn't just pick the point that looks best; it picks the point and the candidate prior that together yield the highest Upper Confidence Bound (UCB).
- Prior Elimination: This is the "secret sauce." Instead of just looking at which prior gives the best values, the algorithm monitors the prediction errors of each candidate prior.
As shown in Figure 1, if a new observation (the diamond) falls far outside a model's confidence interval, that model's prior is likely wrong and is eliminated. If an observation (the star) is consistent with multiple models, it doesn't matter which one we use—both are "good enough" for now. The authors prove that the true prior will almost never be rejected, and the cumulative regret is bounded, scaling gracefully with the square root of the number of candidate priors.
Datasets
The authors evaluated PE-GP-UCB against several baselines (MLE, Fully Bayesian, and Regret Balancing) on two main setups:
- Toy Problem: A synthetic 1D optimization task where the search space changes at every step. This forces the algorithm to adapt to a non-stationary environment even though the underlying function is fixed. They used 11 candidate priors with different "hill" locations.
- Intel Temperature Dataset: A real-world dataset containing temperature readings from 54 sensors in an office. The goal is to find the hottest sensor at each 10-minute interval. Priors were constructed using data from different previous days, creating a set of 13 candidate models.
Key Insights and Ideas
- Error vs. Value: The fundamental shift is moving from "which prior gives me the best results?" to "which prior's predictions are consistent with reality?" Prediction error is a much more reliable signal for model misspecification in non-stationary settings.
- Double Optimism as Exploration: Being optimistic about the model itself naturally encourages the algorithm to explore different priors until the incorrect ones reveal themselves through large prediction errors.
- Theoretical Robustness: The algorithm provides a provable regret bound in time-varying settings, a first for GP-based BO with unknown priors. It shows that even if we don't find the "perfect" prior, we can still perform nearly as well as if we had it, provided the true prior is in our candidate set.
Key Results
In both experiments, PE-GP-UCB outperformed the competition:
- Toy Problem: PE-GP-UCB achieved significantly lower cumulative regret. While MLE often got stuck on a plausible-looking but incorrect prior, PE-GP-UCB quickly eliminated wrong models and committed to the true one.
- Intel Dataset: PE-GP-UCB showed superior performance, especially in the early stages of optimization. It successfully identified and relied on priors from days that were most representative of the current day's patterns, whereas MLE committed to a "Sunday" prior that turned out to be a poor match for the actual data.
Limitations and Future Work
While powerful, the authors note a few areas for improvement:
- Scaling: The regret bound scales with $\sqrt{|U|}$ (the number of priors). If you have thousands of candidate priors, the initial exploration phase might be too costly.
- Over-optimism: The "doubly optimistic" approach might be overly aggressive in some scenarios, potentially leading to high initial regret before priors are eliminated.
- Discrete Set of Priors: The current algorithm requires a finite set of candidate priors. A natural next step is extending this to continuous hyperparameter spaces, which would allow for even more flexible model learning during optimization.
Summary updated