assortment. The added interval is based on the Fisher information matrix of the computed MLE from the previous step. Then we solve a combinatorial optimization problem to search the assortment that maximizes the upper confidence bound. By observing the customer’s purchase action based on the offered assortment, the policy updates the estimated MLE. In this update, we propose to compute a *“local MLE”*, which requires the solution to be close enough to our pilot estimator. The local MLE plays an important role in MLE-UCB policy since it guarantees that the obtained estimator at each time period is also close to the unknown true coefficient $\theta_0$.

Under some mild assumptions on features and coefficients, we are able to establish a regret bound ${\widetilde}{O}(d \sqrt{T})$, where the ${\widetilde}{O}$ notation suppresses logarithmic dependence on $T$, $K$ (cardinality constraint), and some other problem dependent parameters[^2]. One remarkable aspect of our regret bound is that our regret has no dependence on the total number of products $N$ (not even in a logarithmic factor). This makes the result attractive to online applications where $N$ is large (e.g., online advertisement). Moreover, it is also worthwhile noting the dependence of $K$ is only through a logarithmic term.

Our 