Tight Regret Bounds for Noisy Optimization of a Brownian Motion
This provides tight regret bounds for a specific noisy optimization problem, which is incremental as it refines existing theoretical results in Bayesian optimization.
The paper tackles the problem of Bayesian optimization of a one-dimensional Brownian motion with noisy observations, showing that the expected cumulative regret scales as Ω(σ√(T/log T)) ∩ O(σ√T · log T) and the expected simple regret as Ω(σ/√(T log T)) ∩ O(σ log T/√T), with bounds tight up to a factor of O((log T)^1.5).
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 $Ω(σ\sqrt{T / \log (T)}) \cap \mathcal{O}(σ\sqrt{T} \cdot \log T)$ and $Ω(σ/ \sqrt{T \log (T)}) \cap \mathcal{O}(σ\log T / \sqrt{T})$ respectively, where $σ^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.