the regret upper bound established in Theorem \[thm:mle-ucb\] has two terms. The first term, $d\sqrt{T}\cdot \log(\lambda_0^{-1}\rho\nu TK)$, is the main regret term that scales as ${\widetilde}O(d\sqrt{T})$ dropping logarithmic dependency. The second $d^2\lambda_0^{-2}\rho^4\nu^2K^2\log T$ term is a minor term, because it only scales logarithmically with the time horizon $T$. One remarkable aspect of Theorem \[thm:mle-ucb\] is the fact that the regret upper bound has *no* dependency on the total number of items $N$ (even in a logarithmic term). This is an attractive property of the proposed policy, which allows $N$ to be very large, even exponentially large in $d$ and $K$.

Proof sketch of Theorem \[thm:mle-ucb\]
---------------------------------------

We provide a proof sketch of Theorem \[thm:mle-ucb\] in this section. The proofs of technical lemmas are relegated to the online supplement.

The proof is divided into four steps. In the first step, we analyze the pilot estimator $\theta^*$ obtained from the pure exploration phase of Algorithm \[alg:mle-ucb\], and show as a corollary that the true model $\theta_0$ is feasible to all subsequent local MLE formulations with high probability (see Corollary \[cor:tau\]). In the second step, we use an $\varepsilon$-net argument to analyze the estimation error of the local MLE. Afterwards, we show in 