# Tight Regret Bounds for Noisy Optimization of a Brownian Motion

arXiv: https://arxiv.org/abs/2001.09327 · HTML: https://mlsanity.com/paper/2001.09327/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2020.

## Built on by (most cited first, 4 of 4)

- [Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization](https://mlsanity.com/paper/2506.01393/) (2025)
- [Multi-Fidelity Bayesian Optimization With Across-Task Transferable Max-Value Entropy Search](https://mlsanity.com/paper/2403.09570/) (2024)
- [Infinite-Dimensional Operator/Block Kaczmarz Algorithms: Regret Bounds and λ-Effectiveness](https://mlsanity.com/paper/2511.07604/) (2025)
- [Robust Bayesian Optimization via Localized Online Conformal Prediction](https://mlsanity.com/paper/2411.17387/) (2024)

## Abstract (arXiv)

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.