bound on the discrepancy between ${\overline}R_t(S)$ and the true value $R_t(S)$ defined in Eq. .

Suppose $\tau$ satisfies the condition in Lemma \[lem:mle\]. With probability $1-O(T^{-1})$ the following holds uniformly for all $t>T_0$ and $S\subseteq[N]$, $|S|\leq K$ such that

1.  ${\overline}R_t(S)\geq R_t(S)$;

2.  $|{\overline}R_t(S)-R_t(S)| \lesssim \min\{1,\omega\sqrt{\|I_{t-1}^{-1/2}(\theta_0) M_t(\theta_0|S) I_{t-1}^{-1/2}(\theta_0)\|_\op}\}$.

\[lem:ucb\]

At a higher level, the proof of Lemma \[lem:ucb\] can be regarded as a “finite-sample” version of the classical *Delta’s method*, which upper bounds estimation error of some functional $\varphi$ of parameters, i.e., $|\varphi({\widehat}\theta_{t-1})-\varphi(\theta_0)|$ using the estimation error of the parameters themselves ${\widehat}\theta_{t-1}-\theta_0$. The complete proof is relegated to the supplementary material.

### The elliptical potential lemma {#sec:ellipitical}

Let $S_t^*$ be the assortment that maximizes the expected revenue $R_t(\cdot)$ (defined in Eq. ) at time period $t$, and $S_t$ be the assortment selected by Algorithm \[alg:mle-ucb\]. Because $R_t(S)\leq {\overline}R_t(S)$ for all $S$ (see Lemma \[lem:ucb\]), we have the following upper bound for each term in the regret (see Eq. ): $$R_t(S_t^*)-R_t(S_t)
\leq ({\overline}R_t(S_t^*)-{\overline}R_t(S_t)) + ({\overline}R_t(S_t)-R_t(S_t)) \leq {\overline}R_t(S_t)-R_t(S_t),
\label{eq:ucb-triangle}$$ where the last inequality holds because ${\overline}R_t(S_t^*)-{\overline}R_t(S_t) \leq 0$ (note that $S_t$ maximizes ${\overline}{R}_t(\cdot)$).

Subsequently, invoking Lemma \[lem:ucb\] and the Cauchy-Schwarz inequality, we have $$\begin{aligned}
\sum_{t=T_0+1}^T& R_t(S_t^*)-R_t(S_t)
\lesssim \sqrt{d\log(\rho\nu TK)}\cdot \sum_{t=T_0+1}^T \sqrt{\min\{1,\|I_{t-1}^{-1/2}(\theta_0)M_t(\theta_0|S_t)I_{t-1}^{-1/2}(\theta_0)\|_\op\}}\nonumber\\
&\lesssim 