We study sequential time-varying optimization, where the underlying reward function evolves over time and is assumed to lie in a Reproducing Kernel Hilbert Space (RKHS). While classical Gaussian Process Upper Confidence Bound (GP-UCB) algorithms achieve sublinear regret in static settings, such guarantees typically fail when the reward function drifts unpredictably, creating both theoretical and algorithmic challenges.
To address this, we propose SparQ-GP-UCB, a novel framework that handles time variations via uncertainty injection (UI), which increases the noise variance of past observations to account for drift. To mitigate the resulting information loss, we introduce a sparsification and querying mechanism that strategically updates a limited set of past observations, effectively restoring no-regret guarantees. This leads to a sparse inference problem under heteroscedastic noise, which we solve by extending sparse GP methods.
We prove that no-regret is achievable under this framework, provided a logarithmic number of side queries per time step. This offers a concrete solution to the open problem of achieving no-regret in time-varying settings. Experiments on synthetic and real-world datasets demonstrate that SparQ-GP-UCB outperforms existing baselines, achieving lower cumulative regret. Building
on this, we introduce W-SparQ-GP-UCB, which employs a windowing strategy to reduce the number of queries per iteration from O(log(T)) to o(1), and provide a lower bound on the queries required for no-regret.
These results demonstrate the theoretical rigor and practicality of our approach, making time-varying optimization broadly applicable to scenarios where continual adaptation is essential.