  In this paper, we consider the time-varying Bayesian optimization problem.
The unknown function at each time is assumed to lie in an RKHS (reproducing
kernel Hilbert space) with a bounded norm. We adopt the general variation
budget model to capture the time-varying environment, and the variation is
characterized by the change of the RKHS norm. We adapt the restart and sliding
window mechanism to introduce two GP-UCB type algorithms: R-GP-UCB and
SW-GP-UCB, respectively. We derive the first (frequentist) regret guarantee on
the dynamic regret for both algorithms. Our results not only recover previous
linear bandit results when a linear kernel is used, but complement the previous
regret analysis of time-varying Gaussian process bandit under a Bayesian-type
regularity assumption, i.e., each function is a sample from a Gaussian process.
