No-Regret Algorithms for Time-Varying Bayesian Optimization
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Bayesian OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Asymptotic Performance of Time-Varying Bayesian Optimization
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. Is it possible for the instantaneous regret of a TV…
Bayesian OptimizationOptimizing Through Change: Bounds and Recommendations for Time-Varying Bayesian Optimization Algorithms
Time-Varying Bayesian Optimization (TVBO) is the go-to framework for optimizing a time-varying, expensive, noisy black-box function. However, most of the solutions proposed so far either rely on unrealistic assumptions o…
Bayesian OptimizationEvent-Triggered Time-Varying Bayesian Optimization
We consider the problem of sequentially optimizing a time-varying objective function using time-varying Bayesian optimization (TVBO). To cope with stale data arising from time variations, current approaches to TVBO requi…
Bayesian OptimizationThe Traveling Bandit: A Framework for Bayesian Optimization with Movement Costs
This paper introduces a framework for Bayesian Optimization (BO) with metric movement costs, addressing a critical challenge in practical applications where input alterations incur varying costs. Our approach is a conven…
Bayesian OptimizationTraveling Salesman ProblemSharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration
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 explorati…