# Weighted Gaussian Process Bandits for Non-stationary Environments

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 36 references that are in the map.
- First posted on arXiv 6 Jul 2021.

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

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [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)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [Time-Varying Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1601.06650/) (2016)
- [Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit](https://mlsanity.com/paper/1802.03692/) (2018)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [Approximation beats concentration? An approximation view on inference with smooth radial kernels](https://mlsanity.com/paper/1801.03437/) (2018)
- [Algorithms for Non-Stationary Generalized Linear Bandits](https://mlsanity.com/paper/2003.10113/) (2020)
- [Bayesian Optimization under Heavy-tailed Payoffs](https://mlsanity.com/paper/1909.07040/) (2019)
- [No-Regret Algorithms for Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2102.06296/) (2021)
- [Randomized Exploration for Non-Stationary Stochastic Linear Bandits](https://mlsanity.com/paper/1912.05695/) (2019)
- [Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits](https://mlsanity.com/paper/1902.01575/) (2019)

## Built on by (most cited first, 30 of 30)

- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge](https://mlsanity.com/paper/2205.14775/) (2022)
- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [Time-Varying Gaussian Process Bandits with Unknown Prior](https://mlsanity.com/paper/2402.01632/) (2024)
- [uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs](https://mlsanity.com/paper/2410.03284/) (2024)
- [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)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [This Too Shall Pass: Removing Stale Observations in Dynamic Bayesian Optimization](https://mlsanity.com/paper/2405.14540/) (2024)
- [Lower Bounds for Time-Varying Kernelized Bandits](https://mlsanity.com/paper/2410.16692/) (2024)
- [Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs](https://mlsanity.com/paper/2601.01069/) (2026)
- [Safe Time-Varying Optimization based on Gaussian Processes with Spatio-Temporal Kernel](https://mlsanity.com/paper/2409.18000/) (2024)
- [Primal-Dual Contextual Bayesian Optimization for Control System Online Optimization with Time-Average Constraints](https://mlsanity.com/paper/2304.06104/) (2023)
- [Trigonometric Quadrature Fourier Features for Scalable Gaussian Process Regression](https://mlsanity.com/paper/2310.14544/) (2023)
- [Variance-Dependent Regret Bounds for Non-stationary Linear Bandits](https://mlsanity.com/paper/2403.10732/) (2024)
- [Time-Varying Bayesian Optimization Without a Metronome](https://mlsanity.com/paper/2501.18963/) (2025)
- [Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits](https://mlsanity.com/paper/2509.15073/) (2025)
- [Nearly-Optimal Algorithm for Adversarial Kernelized Bandits](https://mlsanity.com/paper/2605.10299/) (2026)
- [Revisiting Weighted Strategy for Non-stationary Parametric Bandits](https://mlsanity.com/paper/2303.02691/) (2023)
- [Weighted Sequential Bayesian Inference for Non-Stationary Linear Contextual Bandits](https://mlsanity.com/paper/2307.03587/) (2023)
- [DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Bandits](https://mlsanity.com/paper/2501.19401/) (2025)
- [Asymptotic Performance of Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2505.13012/) (2025)
- [Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Arms](https://mlsanity.com/paper/2505.24692/) (2025)
- [Counterfactual Credit Guided Bayesian Optimization](https://mlsanity.com/paper/2510.04676/) (2025)
- [No-Regret Gaussian Process Optimization of Time-Varying Functions](https://mlsanity.com/paper/2512.00517/) (2025)
- [Bandits in Flux: Adversarial Constraints in Dynamic Environments](https://mlsanity.com/paper/2601.19867/) (2026)
- [DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees](https://mlsanity.com/paper/2604.16684/) (2026)
- [Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent](https://mlsanity.com/paper/2605.25590/) (2026)
- [Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration](https://mlsanity.com/paper/2608.18863/) (2026)
- [Time-Uniform Self-Normalized Concentration for Discounted Least Squares: Limits and Corrections](https://mlsanity.com/paper/2608.19643/) (2026)

## Abstract (arXiv)

In this paper, we consider the Gaussian process (GP) bandit optimization problem in a non-stationary environment. To capture external changes, the black-box function is allowed to be time-varying within a reproducing kernel Hilbert space (RKHS). To this end, we develop WGP-UCB, a novel UCB-type algorithm based on weighted Gaussian process regression. A key challenge is how to cope with infinite-dimensional feature maps. To that end, we leverage kernel approximation techniques to prove a sublinear regret bound, which is the first (frequentist) sublinear regret guarantee on weighted time-varying bandits with general nonlinear rewards. This result generalizes both non-stationary linear bandits and standard GP-UCB algorithms. Further, a novel concentration inequality is achieved for weighted Gaussian process regression with general weights. We also provide universal upper bounds and weight-dependent upper bounds for weighted maximum information gains. These results are of independent interest for applications such as news ranking and adaptive pricing, where weights can be adopted to capture the importance or quality of data. Finally, we conduct experiments to highlight the favorable gains of the proposed algorithm in many cases when compared to existing methods.