@inproceedings{grill2018optimistic,
abstract = {We address the problem of optimizing a Brownian motion. We consider a (random) realization W of a Brownian motion with input space in [0,1]. Given W, our goal is to return an epsilon-approximation of its maximum using the smallest possible number of function evaluations, the sample complexity of the algorithm. We provide an algorithm with sample complexity of order log2(1/epsilon). This improves over previous results of Al-Mharmah and Calvin (1996) and Calvin et al. (2017) which provided only polynomial rates. Our algorithm is adaptive---each query depends on previous values---and is an instance of the optimism-in-the-face-of-uncertainty principle.},
author = {Grill, Jean-Bastien and Valko, Michal and Munos, R{\'{e}}mi},
booktitle = {Neural Information Processing Systems},
title = {{Optimistic optimization of a Brownian}},
year = {2018}
}