Search papers, labs, and topics across Lattice.
This paper investigates Bayesian optimization in dynamic environments where the reward function is modeled as a time-varying Gaussian process. By employing per-round local confidence events, the authors demonstrate that the GP-UCB algorithm can maintain a constant exploration parameter while achieving a sharper expected-regret bound that is influenced by the drift rate of the reward function. The findings reveal that in the persistent-drift regime, the expected average regret can be significantly reduced to $\widetilde{\mathcal O}(ε^{1/4})$, outperforming traditional methods that require increasing exploration parameters over time.
Constant exploration in time-varying Gaussian process bandits can yield sharper regret bounds, challenging the need for increasing exploration parameters with horizon length.
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 $\tildeγ_T/T=\widetilde{\mathcal O}(ε^{1/2})$ and expected average regret $\widetilde{\mathcal O}(ε^{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/ε$.
