$\lambda_{\min}(\mathbb E_\mu vv^\top) \geq \lambda_0$ for some constant $\lambda_0>0$;

2.  There exists a constant $\rho<\infty$ such that for all $t\in[T]$ and $S\subseteq[N]$ [with $|S|\leq K$]{}, $\frac{p_{\theta_0,t}(j|S)}{p_{\theta_0,t}(j'|S)} \leq \rho$ for all $j,j'\in S\cup\{0\}$.

The item (A1) assumes that the contextual information vectors $\{v_{tj}\}$ in the pure-exploration phase with $t \leq T_0$ are *randomly generated* from a non-degenerate density. It also places a standard boundedness condition on $\{v_{tj}\}$ for all time periods $t$. Note that after the pure-exploration phase, we allow the contextual vectors $\{v_{tj}\}$ to be adversarially chosen, only subject to boundedness conditions. (A2) additionally assumes a bounded ratio between the probability of choosing any two different items in an arbitrary assortment set. [We remark that if $\|\theta_0\|_2\leq C$, then the boundedness assumption in (A1) implies (A2) with $\rho\leq e^{2 \max\{1,C\nu\}}$.]{}

We are now ready to state our main result that upper bounds the worst-case accumulated regret of the proposed MLE-UCB policy in Algorithm \[alg:mle-ucb\].

Suppose that $T_0\asymp \max\{\nu^2d\log T/\lambda_0^2, \rho^2(d+\log T)/(\tau^2\lambda_0)\}$ and $\tau\asymp 1/\sqrt{\rho^2\nu^2K^2}$ in Algorithm \[alg:mle-ucb\], then the regret of the MLE-UCB policy is upper bounded by $$\label{eq:thm-main}
    C_1\left[ d\sqrt{T}\cdot \log(\lambda_0^{-1}\rho\nu TK)+ {d^2\lambda_0^{-2}\rho^4\nu^2 K^2\log T}\right] + C_2,$$ where $C_1, C_2>0$ are universal constants. \[thm:mle-ucb\]

In addition to universal constants, 