idea of local search by greedy swapping, with more details described in Sec. \[subsec:heuristic\].

Related work {#sec:related}
------------

Due to the popularity of data-driven revenue management, dynamic assortment optimization, which adaptively learns unknown customers’ choice behavior, has received increasing attention in the past few years. Motivated by fast-fashion retailing, the work by [@Caro2007] first studied dynamic assortment optimization problem, but it makes a strong assumption that the demands for different product are independent. Recent works by [@Rusmevichientong2010; @Saure2013; @Agrawal16MNLBandit; @Agrawal17Thompson; @Chen:18tight; @Chen:18near] incorporated MNL models into dynamic assortment optimization and formulated the problem into a online regret minimization problem. In particular, for capacitated MNL, [@Agrawal16MNLBandit] and [@Agrawal17Thompson] proposed UCB and Thompson sampling techniques and established the regret bound ${\widetilde}{O}(\sqrt{NT})$ (when $T  \gg N^2$). [@Chen:18tight] further established a matching lower bound of $\Omega(\sqrt{NT})$. It is interesting to compare our regret to the bound for the standard MNL case. When the total number of products $N$ is much larger than $d$ (i.e., $N > d^2$), by incorporating the contextual information, the regret reduces from ${\widetilde}{O}(\sqrt{NT})$ to ${\widetilde}{O}(d \sqrt{T})$. The latter one only depends on $d$ and is completely independent of the total number of products $N$, which also demonstrates the usefulness of 