imply the desired upper bound for $\sum_{t=1}^{T}\mathbb{E} [ f(x_t) - f(x)  \hspace{.03truecm}|\hspace{.03truecm} x_t]$ due to a recursive argument in the spirit of [@bartlett-hazan-rakhlin].

In the non-noisy case ($\sigma=0$) we get the rate $\frac{d}{\alpha} \log T$ for the cumulative regret, and $\frac{d}{\alpha} \frac{\log T}{T}$ for the optimization error. In what concerns the optimization error, this rate is not optimal since one can achieve much faster rate under strong convexity [@NS17]. However, for the cumulative regret in our derivative-free setting it remains an open question whether the result of Theorem \[thm:1\] can be improved. Previous papers on derivative-free online methods with no noise [@agarwal2010; @duchi2015; @flaxman2004] provide slower rates than $({d}/{\alpha}) \log T$. The best known so far is $({d^2}/{\alpha})\log T$, cf. [@agarwal2010 Corollary 5]. We may also notice that the cumulative regret bounds of Theorem \[thm:1\] trivially extend to the case when we query functions $f_t$ depending on $t$ rather than a single $f$. Another immediate fact is that on the r.h.s. of inequalities and we can take the minimum with $GBT$ and $GB$, respectively, where $B$ is the Euclidean diameter of ${\Theta}$. Finally, the factor $\log T$ in the bounds for the optimization error can be eliminated by considering averaging 