because $F_t(\cdot)$ is a Kullback-Leibler divergence, $\theta_0$ is feasible to the local MLE formulation and ${\widehat}\theta_{t-1}$ is the optimal solution. On the other hand, it can be proved that $|F_t(\theta)-{\widehat}F_t(\theta)|$ is small for all $\theta$ with high probability, by using concentration inequalities for self-normalized empirical process (note that $\mathbb E{\widehat}f_{t'}(\theta) = f_{t'}(\theta)$ for any $\theta$). Moreover, by constructing a local quadratic approximation of $F_t(\cdot)$ around $\theta_0$, we can show that $F_t(\theta)-F_t(\theta_0)$ is large when $\theta$ is far away from $\theta_0$.

[Following the above observations, we can use proof by contradiction to prove Lemma \[lem:mle\], which essentially claims that ${\widehat}\theta_{t}$ and $\theta_0$ are close under the quadratic distance $\|\cdot\|_{I_t(\theta_0)}$. Suppose by contradiction that ${\widehat}\theta_{t}$ and $\theta_0$ are far apart, which implies that $|F_t({\widehat}\theta_{t})-F_t(\theta_0)|$ is large. On the other hand, by the fact that ${\widehat}F_t({\widehat}\theta_{t})\leq  0 = {F}_t(\theta_0) \leq F_t({\widehat}\theta_{t})$, we have $$|F_t({\widehat}\theta_{t})-F_t(\theta_0)| =    |F_t({\widehat}\theta_{t})|  \leq |F_t({\widehat}\theta_{t})-{\widehat}F_t({\widehat}\theta_{t})  |.$$ By the established concentration result, we have $|F_t(\theta)-{\widehat}F_t(\theta)|$ is small for all $\theta$ with high probability (including $\theta={\widehat}\theta_{t}$). This leads to the desired contradiction.]{}

### Analysis of upper confidence bounds

The following technical lemma shows that the upper confidence bounds constructed in Algorithm \[alg:mle-ucb\] are valid with high probability. Additionally, we establish an upper 