are presented in Eq.  in Sec. \[sec:ana\_local\]. These quantities play an essential role in classical statistical analysis of maximum likelihood estimators (see, e.g., [@van1998asymptotic]).

The proposed MLE-UCB policy has three hyper-parameters: the coefficient $\omega>0$ that controls the lengths of confidence intervals of $R_t(S)$, the number of pure exploration iterations $T_0$, and the radius $\tau_0$ in the local MLE formulation. While theoretical values of $\omega,T_0$ and $\tau$ are given in Theorem \[thm:mle-ucb\], which potentially depend on several unknown problem parameters, in practice we recommend the usage of $T_0=\max\{d\log T, T^{1/4}\}$, $\omega=\sqrt{d\log T}$ and $\tau=1/K$.

In the rest of this section, we give a regret analysis that shows an ${\widetilde}O(d\sqrt{T})$ upper bound on the regret of the MLE-UCB policy. Additionally, we prove a lower bound of ${\widetilde}O(d\sqrt{T}/K)$ in Sec. \[sec:negative\] and show how the combinatorial optimization in Step 7 can be approximately computed efficiently in Sec. \[sec:comb\].

Regret analysis {#subsec:regret}
---------------

To establish rigorous regret upper bounds on Algorithm \[alg:mle-ucb\], we impose the following assumptions:

1.  There exists a constant $\nu$ such that $\|v_{tj}\|_2\leq\nu$ for all $t$ and $j$. Moreover, for all $t\leq T_0$ and $j \in [N]$, $v_{tj}$ are i.i.d. generated from an unknown distribution with the density $\mu$ satisfying that 