  The Gaussian process bandit is a problem in which we want to find a maximizer
of a black-box function with the minimum number of function evaluations. If the
black-box function varies with time, then time-varying Bayesian optimization is
a promising framework. However, a drawback with current methods is in the
assumption that the evaluation time for every observation is constant, which
can be unrealistic for many practical applications, e.g., recommender systems
and environmental monitoring. As a result, the performance of current methods
can be degraded when this assumption is violated. To cope with this problem, we
propose a novel time-varying Bayesian optimization algorithm that can
effectively handle the non-constant evaluation time. Furthermore, we
theoretically establish a regret bound of our algorithm. Our bound elucidates
that a pattern of the evaluation time sequence can hugely affect the difficulty
of the problem. We also provide experimental results to validate the practical
effectiveness of the proposed method.
