sequentially [@belitser; @mokkadem]. In the fist case, $f(x^*)$ cannot be estimated better than at the slow rate $(T/\log T)^{-\beta/(2\beta+d)}$ (see, [@Ibra] for $d=1$). For the second case, which is our setting, the best result so far is obtained in [@belitser]. The estimator of $f(x
^*)$ in [@belitser] is defined via a multi-stage procedure whose complexity increases exponentially with the dimension $d$ and it is shown to achieve (asymptotically, for $T$ greater than an exponent of $d$) the $c(d, \alpha)/\sqrt{T}$ rate for functions in $\mathcal{F}_{\alpha,\beta}(L)$ with $\beta> 2$. Here, $c(d,\alpha)$ is some constant depending on $d$ and $\alpha$ in an unspecified way.

Observe that $f(\bar x_T)$ is not an estimator since it depends on the unknown $f$, so Theorem \[thm:1\] does not provide a result about estimation of $f(x^*)$. In this section, we show that using the computationally simple Algorithm \[algo\] and making one more query per step (that is, having three queries per step in total) allows us to achieve the $1/\sqrt{T}$ rate for all $\beta\ge 2$ with no dependency on the dimension in the main term. Note that the $1/\sqrt{T}$ rate cannot be improved. Indeed, one cannot estimate $f(x^*)$ with a better rate even using the ideal but non-realizable 