# No-Regret Gaussian Process Optimization of Time-Varying Functions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 31 references that are in the map.
- First posted on arXiv 29 Nov 2025.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Reinforcement Learning in Economics and Finance](https://mlsanity.com/paper/2003.10014/) (2020)
- [Convergence of Sparse Variational Inference in Gaussian Processes Regression](https://mlsanity.com/paper/2008.00323/) (2020)
- [Time-Varying Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1601.06650/) (2016)
- [An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation](https://mlsanity.com/paper/1901.00555/) (2019)
- [A Tutorial on Sparse Gaussian Processes and Variational Inference](https://mlsanity.com/paper/2012.13962/) (2020)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [No-Regret Algorithms for Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2102.06296/) (2021)
- [Risk-averse Heteroscedastic Bayesian Optimization](https://mlsanity.com/paper/2111.03637/) (2021)
- [Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance](https://mlsanity.com/paper/2502.06363/) (2025)
- [On Controller Tuning with Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2207.11120/) (2022)
- [Time-varying Gaussian Process Bandit Optimization with Non-constant Evaluation Time](https://mlsanity.com/paper/2003.04691/) (2020)
- [Time-varying Gaussian Process Bandit Optimization with Experts: no-regret in logarithmically-many side queries](https://mlsanity.com/paper/2510.21274/) (2025)

## Abstract (arXiv)

Sequential optimization of black-box functions from noisy evaluations has been widely studied, with Gaussian Process bandit algorithms such as GP-UCB guaranteeing no-regret in stationary settings. However, for time-varying objectives, no-regret is unattainable under pure bandit feedback unless strong and often unrealistic assumptions are imposed. We propose a novel method for optimizing time-varying rewards in the frequentist setting, where the objective has bounded RKHS norm almost surely. Time variations are captured through uncertainty injection, enabling heteroscedastic Gaussian process regression that adapts past observations to the current time step. As no-regret is unattainable in general in the strict bandit setting, we relax the latter allowing additional queries on previously observed points. Building on sparse inference and the effect of uncertainty injection on regret, we propose W-SparQ-GP-UCB, an online algorithm that achieves no-regret with a vanishing number of additional queries per iteration. To assess the theoretical limits of this approach, we establish a lower bound on the number of additional queries required for no-regret, proving the efficiency of our method. Finally, we provide a comprehensive analysis linking the temporal regime of the function to achievable regret rates, together with upper and lower bounds on the number of additional queries needed in each regime.