Stochastic simultaneous optimistic optimization

We study the problem of global maximiza-tion of a function f given a finite number of evaluations perturbed by noise. We con-sider a very weak assumption on the func-tion, namely that it is locally smooth (in some precise sense) with respect to some semi-metric, around one of its global max-ima. Compared to previous works on ban-dits in general spaces (Kleinberg et al., 2008; Bubeck et al., 2011a) our algorithm does not require the knowledge of this semi-metric. Our algorithm, StoSOO, follows an optimistic strategy to iteratively construct upper con-fidence bounds over the hierarchical parti-tions of the function domain to decide which point to sample next. A finite-time analysis of StoSOO shows that it performs almost as well as the best specifically-tuned algorithms even though the local smoothness of the func-tion is not known. 1