Tight Regret Bounds for Noisy Optimization of a Brownian Motion
We consider the problem of Bayesian optimization of a one-dimensional Brownian motion in which the $T$ adaptively chosen observations are corrupted by Gaussian noise. We show that as the smallest possible expected cumulative regret and the smallest possible expected simple regret scale as $\Omega(\sigma\sqrt{T / \log (T)}) \cap \mathcal{O}(\sigma\sqrt{T} \cdot \log T)$ and $\Omega(\sigma / \sqrt{T \log (T)}) \cap \mathcal{O}(\sigma\log T / \sqrt{T})$ respectively, where $\sigma^2$ is the noise variance. Thus, our upper and lower bounds are tight up to a factor of $\mathcal{O}( (\log T)^{1.5} )$. The upper bound uses an algorithm based on confidence bounds and the Markov property of Brownian motion (among other useful properties), and the lower bound is based on a reduction to binary hypothesis testing.
Code (0)
등록된 구현이 없습니다.
Tasks
Bayesian OptimizationTwo-sample testingSimilar Papers 제목 키워드 기반
Tight Regret Bounds for Bayesian Optimization in One Dimension
We consider the problem of Bayesian optimization (BO) in one dimension, under a Gaussian process prior and Gaussian sampling noise. We provide a theoretical analysis showing that, under fairly mild technical assumptions …
Bayesian OptimizationOptimal Online Learning using Potential Functions
We study a family of potential functions for online learning. We show that if the potential function has strictly positive derivatives of order 1-4 then the min-max optimal strategy for the adversary is Brownian motion. …
Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits
We propose novel algorithms with first- and second-order regret bounds for adversarial linear bandits. These regret bounds imply that our algorithms perform well when there is an action achieving a small cumulative loss …
A Unified Analysis Method for Online Optimization in Normed Vector Space
This paper studies online optimization from a high-level unified theoretical perspective. We not only generalize both Optimistic-DA and Optimistic-MD in normed vector space, but also unify their analysis methods for dyna…
Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
In this paper, we consider the problem of sequentially optimizing a black-box function $f$ based on noisy samples and bandit feedback. We assume that $f$ is smooth in the sense of having a bounded norm in some reproducin…