In this paper, we study the dynamic assortment optimization problem under a
finite selling season of length $T$. At each time period, the seller offers an
arriving customer an assortment of substitutable products under a cardinality
constraint, and the customer makes the purchase among offered products
according to a discrete choice model. Most existing work associates each
product with a real-valued fixed mean utility and assumes a multinomial logit
choice (MNL) model. In many practical applications, feature/contexutal
information of products is readily available. In this paper, we incorporate the
feature information by assuming a linear relationship between the mean utility
and the feature. In addition, we allow the feature information of products to
change over time so that the underlying choice model can also be
non-stationary. To solve the dynamic assortment optimization under this
changing contextual MNL model, we need to simultaneously learn the underlying
unknown coefficient and makes the decision on the assortment. To this end, we
develop an upper confidence bound (UCB) based policy and establish the regret
bound on the order of $\widetilde O(d\sqrt{T})$, where $d$ is the dimension of
the feature and $\widetilde O$ suppresses logarithmic dependence. We further
established the lower bound $\Omega(d\sqrt{T}/K)$ where $K$ is the cardinality
constraint of an offered assortment, which is usually small. When $K$ is a
constant, our policy is optimal up to logarithmic factors. In the exploitation
phase of the UCB algorithm, we need to solve a combinatorial optimization for
assortment optimization based on the learned information. We further develop an
approximation algorithm and an efficient greedy heuristic. The effectiveness of
the proposed policy is further demonstrated by our numerical studies.

本文研究了长度为 T 的有限销售季节下的动态组合优化问题，其中包括了具有属性信息的产品的线性关系和上置信界 (UCB) 算法，并使用组合优化法进行了解决。