# Asymptotic Performance of Time-Varying Bayesian Optimization

arXiv: https://arxiv.org/abs/2505.13012 · HTML: https://mlsanity.com/paper/2505.13012/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 44 references that are in the map.
- First posted on arXiv 19 May 2025.

## Builds on (most cited first, 15 of 15)

- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Time-Varying Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1601.06650/) (2016)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [No-Regret Algorithms for Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2102.06296/) (2021)
- [An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge](https://mlsanity.com/paper/2205.14775/) (2022)
- [Bayesian Optimization for Dynamic Problems](https://mlsanity.com/paper/1803.03432/) (2018)
- [Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2305.19838/) (2023)
- [Band-Limited Gaussian Processes: The Sinc Kernel](https://mlsanity.com/paper/1909.07279/) (2019)
- [Near-Optimal Algorithm for Non-Stationary Kernelized Bandits](https://mlsanity.com/paper/2410.16052/) (2024)
- [Event-Triggered Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2208.10790/) (2022)
- [This Too Shall Pass: Removing Stale Observations in Dynamic Bayesian Optimization](https://mlsanity.com/paper/2405.14540/) (2024)

## Abstract (arXiv)

Time-Varying Bayesian Optimization (TVBO) is the go-to framework for optimizing a time-varying black-box objective function that may be noisy and expensive to evaluate, but its excellent empirical performance remains to be understood theoretically. Is it possible for the instantaneous regret of a TVBO algorithm to vanish asymptotically, and if so, when? We answer this question of great importance by providing upper bounds and algorithm-independent lower bounds for the cumulative regret of TVBO algorithms. In doing so, we provide important insights about the TVBO framework and derive sufficient conditions for a TVBO algorithm to have the no-regret property. To the best of our knowledge, our analysis is the first to cover all major classes of stationary kernel functions used in practice.