problem (see, e.g., [@li2017provably]) with $N$ arms, it is assumed that a context vector $v_{tj}$ is revealed at time $t$ for each arm $j \in [N]$. Given a selected arm $i_t \in [N]$ at time $t$, the expected reward follows Eq. , i.e., $\mathbb{E}[r_t | v_{t,i_t} ]=\sigma(v_{t,i_t}^\top\theta_0)$. At first glance, our contextual MNL model is a natural extension of the generalized linear bandit to the MNL choice model. However, when the size of an assortment $K\geq 2$, the contextual MNL *cannot* be written in the form of Eq. (\[eq:glm\]) and the denominator in the choice probability (see Eq.  in the next section) has a more complicated structure. Therefore, our problem is technically *not* a generalized linear model and is therefore more challenging. Moreover, in contextual bandit problems, only one arm is selected by the decision-maker at each time period. In contrast, each action in an assortment optimization problem involves a set of items, which makes the action space more complicated.]{}

Notations and paper organization
--------------------------------

Throughout the paper, we adopt the standard asymptotic notations. In particular, we use $f(\cdot) \lesssim g(\cdot)$ to denote that $f(\cdot) = O(g(\cdot))$. Similarly, by $f(\cdot) \gtrsim g(\cdot)$, we denote $f(\cdot) = \Omega(g(\cdot))$. We also use 