  In this paper, we consider the Gaussian process (GP) bandit optimization
problem in a non-stationary environment. To capture external changes, the
black-box function is allowed to be time-varying within a reproducing kernel
Hilbert space (RKHS). To this end, we develop WGP-UCB, a novel UCB-type
algorithm based on weighted Gaussian process regression. A key challenge is how
to cope with infinite-dimensional feature maps. To that end, we leverage kernel
approximation techniques to prove a sublinear regret bound, which is the first
(frequentist) sublinear regret guarantee on weighted time-varying bandits with
general nonlinear rewards. This result generalizes both non-stationary linear
bandits and standard GP-UCB algorithms. Further, a novel concentration
inequality is achieved for weighted Gaussian process regression with general
weights. We also provide universal upper bounds and weight-dependent upper
bounds for weighted maximum information gains. These results are of independent
interest for applications such as news ranking and adaptive pricing, where
weights can be adopted to capture the importance or quality of data. Finally,
we conduct experiments to highlight the favorable gains of the proposed
algorithm in many cases when compared to existing methods.
