$f\in\mathcal{F}_{\alpha,\beta}(L)$ scales as $c(\alpha,d)T^{-{(\beta-1)}/{\beta}}$, where $c(\alpha,d)$ is an unspecified function of $\alpha$ and $d$ (for $d=1$ an upper bound of the same order was earlier established in [@Fabian]). The issue of establishing non-asymptotic fundamental limits as function of the main parameters of the problem ($\alpha$, $d$ and $T$) was first addressed in [@jamieson2012] giving a lower bound $\Omega(\sqrt{d/T})$ for $\beta=2$. This was improved to $\Omega(d/\sqrt{T})$ when $\alpha\asymp 1$ by Shamir [@Shamir13] who conjectured that the rate $d/\sqrt{T}$ is optimal for $\beta=2$, which indeed follows from our Theorem \[th6.3\] (although [@Shamir13] claims the optimality as proved fact by referring to results in [@agarwal2010], such results cannot be applied in setting (iii) because the noise cannot be considered as Lipschitz). A result similar to Theorem \[th6.3\] is stated without proof in Bach and Perchet [@BP2016 Proposition 7] but not for the cumilative regret and with a suboptimal rate in the non-noisy case. For integer $\beta\ge 3$, Bach and Perchet [@BP2016] present explicit upper bounds as functions of $\alpha$, $d$ and $T$ with, however, suboptimal dependency on $T$ except for their Proposition 8 that is problematic (see Appendix \[app:D\] for the details). Finally, by slightly modifying the proof of Theorem \[thm:1\] we get 