Imagine there is some unknown $L$-Lipschitz function $f\colon [0,1] \to \mathbb R$ that, for the sake of simplicity, has a unique maximizer $x^\star$.
Are there algorithms that, for any given budget of evaluations $n$, query $n$ points $x_1, \dots, x_n \in [0,1]$ and, after observing the corresponding values $f(x_1),\dots,f(x_n)$, recommend a point $x^\star_n \in [0,1]$ with the goal of minimizing the distance from the maximizer $| x^\star - x^\star_n |$?
Note that this is different from the usual black-box (or 0th order) optimization, where the goal is to minimize the optimization error $f(x^\star) - f(x^\star_n)$ of the recommendation. I know there is a vast literature on this other problem but I have no clue if any exists for the one I am requesting.
I can see that if a function $f$ is very flat, like constant everywhere except for a tiny little bump of height $\varepsilon \ll 1$, then it would be extremely easy to (approximately) maximize it, but nearly impossible to recommend a point that is close to $x^\star$. Then, probably, query complexity results should depend on the variation of $f$ (around $x^\star$?).
Anyway, I am wondering if anybody knows if this problem has been studied or not. Thanks!