then $\tau\|g_t\|_{\xi^t, *} \le 1/16$. Consequently, Lem. E.17 (with $x = \xi^t$, $y = \xi^{t+1}$, and $\ell = \tau g_t$) would assert that $\xi^{t+1} \in \mathcal{E}_{1/2}(\xi^t)$; and hence, $\zeta^t \in \mathcal{E}_{1/2}(\xi^t)$. It would then hold via (65) that

$$ \|g_t\|_{\zeta^t, *}^2 \le \frac{1}{(1 - \|\zeta^t - \xi^t\|_{\xi^t})^2} \|g_t\|_{\xi^t, *}^2 \le 4\|g_t\|_{\xi^t, *}^2, $$

On the other hand, via Lem. E.18 and the definitions of $\xi^1$ and $\xi^*$, we have that

$$ D_{\psi_{1b}}(\xi^*, \xi^1) \le NSA \log \dot{\delta}^{-1}. $$

Hence, conditioned on (67), we obtain the following regret bound

$$ \bar{R}_T \le \frac{NSA \log \dot{\delta}^{-1}}{\tau} + \frac{2\tau}{\delta^2} N^4 S^2 A^2 T + 4\delta LNT + 2\dot{\delta}LNT. \quad (68) $$

Setting

$$ \dot{\delta} = \frac{1}{T}, \quad \tau = \frac{\delta}{16} \sqrt{\frac{\log T}{N^3 SAT}}, \quad \text{and} \quad \delta = \min \left\{ \sqrt{\frac{17 N^{3/4} S^{3/4} A^{3/4} (\log T)^{1/4}}{4L T^{1/4}}}, 1 \right\}; $$

we obtain that

$$ \begin{aligned} \bar{R}_T &\le \frac{NSA \log T}{\tau} + \frac{2\tau}{\delta^2} N^4 S^2 A^2 T + 4\delta LNT + 2LN \\ &\le \frac{17}{\delta} \sqrt{N^5 S^3 A^3 T \log T} + 4\delta LNT + 2LN \\ &\le \max \left\{ 4\sqrt{17LN^{7/4}} (SAT)^{3/4} (\log T)^{1/4}, 34\sqrt{N^5 S^3 A^3 T \log T} \right\} + 2LN. \end{aligned} \quad (69) $$

If $T \ge NSA \log(T)$, then our choice of $\tau$ indeed satisfies (67):

$$ \tau = \frac{\delta}{16} \sqrt{\frac{\log T}{N^3 SAT}} \le \frac{\delta}{16N^2 SA}. $$

Otherwise, we can fall back to the trivial regret bound

$$ \bar{R}_T \le NT \le N^2 SA \log(T), $$

which is dominated by the bound in (69); hence, the theorem follows. $\square$