oracle that makes all queries at point $x^*$.

In order to construct our estimator, at any step $t$ of Algorithm \[algo\] we make along with $y_t$ and $y_t'$ the third query $y''_t=f(x_t)+\xi''_t$, where $\xi''_t$ is some noise and $x_t$ are the updates of Algorithm \[algo\]. We estimate $f(x^*)$ by $
\hat M = \frac{1}{T}\sum_{t=1}^T y''_t.
$ The properties of estimator $\hat M$ are summarized in the next theorem, which is an immediate corollary of Theorem \[thm:1\].

[theorem]{}[fththeorem]{} \[thm:min\] Let the assumptions of Theorem \[thm:1\] be satisfied. Let $\sigma>0$ and assume that $(\xi''_t)_{t=1}^T$ are independent random variables with $\mathbb{E}[\xi''_t]=0$ and $\mathbb{E}[\xi''_t]\le \sigma^2$ for $t=1,\dots, T$. If $f$ attains its minimum at point $x^*\in {\Theta}$, then $$\label{eq:boundM}
    \mathbb{E} \lvert \hat M - f(x^*) \rvert \leq \frac{\sigma}{T^{\frac{1}{2}}}+ \frac{1}{\alpha}
\left(  d^2\left(\frac{A_1}{T^{\frac{\beta-1}{\beta}}}+ \frac{A_2}{T}\right)+ 
A_3\frac{d\log T}{T} \right).$$

\[remark:min\] With three queries per step, the risk (error) of the oracle that makes all queries at point $x^*$ is $\sigma/\sqrt{3T}$. Thus, for $\beta>2$ the estimator $\hat M$ achieves asymptotically as $T\to \infty$ the oracle risk to within the $\sqrt{3}$ factor. We do not obtain such a sharp property for $\beta=2$, in which case the remainder term in Theorem \[thm:min\] accounting for the accuracy of Algorithm \[algo\] is of 