Tight Regret Bounds for Noisy Optimization of a Brownian Motion

Abstract

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

Tasks

Reproductions