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(σ√T / log (T)) cap O(σ√T · log T) and Omega(σ / √T log (T)) cap O(σlog T / √T) respectively, where σ2 is the noise variance. Thus, our upper and lower bounds are tight up to a factor of 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.