with a $d$-dimensional feature vector $v_{tj} \in \mathbb{R}^d$. To incorporate the feature information, following the classical conditional logit model [@McFa73], we assume that the mean utility of product $j$ at time $t$ (denoted by $u_{tj}$) obeys a linear model $$\label{eq:linear}
u_{tj}= v_{tj}^\top\theta_0.$$ Here, $\theta_0 \in \mathbb{R}^d$ is the unknown coefficient to be learned. Based on this linear structure of the mean utility, we adopt the MNL model as the underlying choice model (see Section \[sec:model\] and Eq.  for more details). As compared to the standard MNL, this *changing contextual MNL* model not only incorporates rich contextual information but also allows the utility to evolve over time. The changing utility is an attractive property as it captures the reality in many applications but also brings new technical challenges in learning and decision-making. For example, in existing works of [@Agrawal16MNLBandit] for plain MNL choice models, upper confidence bands are constructed by providing the same assortment repetitively to incoming customers until a no-purchase activity is observed. Such an approach, however, can no longer be applied to MNL with changing contextual information as the utility parameters of products constantly evolve with time. To overcome such challenges, we propose a policy that performs optimization at 