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 $\tilde\gamma_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$.

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 $\tilde\gamma_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$.

23 pages, 1 figure. Code included as ancillary files

Machine Learning (stat.ML); Machine Learning (cs.LG)

arXiv:2608.18863 [stat.ML]

(or arXiv:2608.18863v1 [stat.ML] for this version)

https://doi.org/10.48550/arXiv.2608.18863 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

supplementary_code/README.md

supplementary_code/make_simulation_figure.py

supplementary_code/reproduce_all.py

supplementary_code/requirements.txt

supplementary_code/run_constant_beta_experiment.py

supplementary_code/run_log_beta_experiment.py

supplementary_code/tvgp_simulation.py

(2 additional files not shown) You must enabled JavaScript to view entire file list.

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

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

Related coverage