Time-Varying Gaussian Process Bandits with Unknown Prior

Juliusz Ziomek, Masaki Adachi, Michael A. Osborne

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:

  1. 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).
  2. 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.
Figure 1: Intuition behind the prior elimination. Solid lines represent the mean functions of two models - GP1 and GP2, produced by fitting the observed points while assuming different prior, and shaded regions are confidence intervals. The point marked by the star lies in the confidence intervals of both models, whereas the point marked by the diamond lies in the one of GP1.

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.
Regret results on the toy problem (left) and the Intel temperature dataset (right). PE-GP-UCB (orange dashed line) consistently achieves the lowest regret.

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

Abstract

Bayesian optimisation requires fitting a Gaussian process model, which in turn requires specifying prior on the unknown black-box function -- most of the theoretical literature assumes this prior is known. However, it is common to have more than one possible prior for a given black-box function, for example suggested by domain experts with differing opinions. In some cases, the type-II maximum likelihood estimator for selecting prior enjoys the consistency guarantee, but it does not universally apply to all types of priors. If the problem is stationary, one could rely on the Regret Balancing scheme to conduct the optimisation, but in the case of time-varying problems, such a scheme cannot be used. To address this gap in existing research, we propose a novel algorithm, PE-GP-UCB, which is capable of solving time-varying Bayesian optimisation problems even without the exact knowledge of the function's prior. The algorithm relies on the fact that either the observed function values are consistent with some of the priors, in which case it is easy to reject the wrong priors, or the observations are consistent with all candidate priors, in which case it does not matter which prior our model relies on. We provide a regret bound on the proposed algorithm. Finally, we empirically evaluate our algorithm on toy and real-world time-varying problems and show that it outperforms the maximum likelihood estimator, fully Bayesian treatment of unknown prior and Regret Balancing.
BibTeX
@inproceedings{ziomek2025time,
  author = {Juliusz Ziomek and Masaki Adachi and Michael A. Osborne},
  title = {{Time-Varying Gaussian Process Bandits with Unknown Prior}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=IG44SrW8l9},
}
Figure