mlsanityData to 14 Oct 2026

No-Regret Algorithms for Time-Varying Bayesian Optimization

arXiv 2102.06296 ↗First posted 11 Feb 2021cs.LGcited by 19

Not on the map. Why?

Abstract (arXiv)

In this paper, we consider the time-varying Bayesian optimization problem. The unknown function at each time is assumed to lie in an RKHS (reproducing kernel Hilbert space) with a bounded norm. We adopt the general variation budget model to capture the time-varying environment, and the variation is characterized by the change of the RKHS norm. We adapt the restart and sliding window mechanism to introduce two GP-UCB type algorithms: R-GP-UCB and SW-GP-UCB, respectively. We derive the first (frequentist) regret guarantee on the dynamic regret for both algorithms. Our results not only recover previous linear bandit results when a linear kernel is used, but complement the previous regret analysis of time-varying Gaussian process bandit under a Bayesian-type regularity assumption, i.e., each function is a sample from a Gaussian process.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). Builds on 9 of its 18 references that are in the map. First posted on arXiv 11 Feb 2021.

Builds on

9 of 18 references.

References · 9

  1. 2017On Kernelized Multi-armed Banditscited by 352
  2. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 192
  3. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 86
  4. 2018Learning to Optimize under Non-Stationaritycited by 85
  5. 2016Time-Varying Gaussian Process Bandit Optimizationcited by 50
  6. 2014Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewardscited by 42
  7. 2020Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programmingcited by 28
  8. 2019Bayesian Optimization under Heavy-tailed Payoffscited by 21
  9. 2020Local Differential Privacy for Bayesian Optimizationcited by 19

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 4; 2023: 0; 2024: 4; 2025: 5; 2026: 5.

19 papers.

Sort:

By area:

  1. 2022Recent Advances in Bayesian Optimizationcited by 76
  2. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  3. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  4. 2024Time-Varying Gaussian Process Bandits with Unknown Priorcited by 11
  5. 2022Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraintscited by 9
  6. 2022Event-Triggered Time-Varying Bayesian Optimizationcited by 7
  7. 2024This Too Shall Pass: Removing Stale Observations in Dynamic Bayesian Optimizationcited by 6
  8. 2024Lower Bounds for Time-Varying Kernelized Banditscited by 5
  9. 2024Safe Time-Varying Optimization based on Gaussian Processes with Spatio-Temporal Kernelcited by 4
  10. 2025Time-Varying Bayesian Optimization Without a Metronomecited by 1
  11. 2026Model-Based Reinforcement Learning for Control under Time-Varying Dynamicscited by 1
  12. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
7 more
  1. 2025DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Banditscited by 0
  2. 2025Asymptotic Performance of Time-Varying Bayesian Optimizationcited by 0
  3. 2025Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Armscited by 0
  4. 2025No-Regret Gaussian Process Optimization of Time-Varying Functionscited by 0
  5. 2026Bandits in Flux: Adversarial Constraints in Dynamic Environmentscited by 0
  6. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescited by 0
  7. 2026Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Explorationcited by 0