Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration

arXiv:2608.18863v1 Announce Type: cross Abstract: We study Bayesian optimization in a time-varying environment where the unknown reward function evolves according to a Gaussian process drift model. Existing GP-UCB analyses in this setting typically require the exploration parameter to grow with the horizon to maintain uniform confidence bounds. Using per-round local confidence events, we show that GP-UCB can instead be run with a constant exploration parameter and obtain an expected-regret bound whose coefficient depends on the drift rate. We also derive a sharper time-varying maximum-information-gain bound. For the squared exponential kernel, it yields ildegamma_T/T=widetilde{mathcal O}(epsilon^{1/2}) and expected average regret widetilde{mathcal O}(epsilon^{1/4}) in the persistent-drift regime. The same constant-exploration analysis also yields realized-regret guarantees. Simulations support the predicted logarithmic dependence of the bound-suggested exploration parameter on 1/epsilon.

Related

• Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
• Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits
• Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards

Source: arXiv cs.LG | 2026-08-20