Dynamic Assortment Optimization with Changing Contextual Information
Dynamic Assortment Optimization with Changing Contextual Information
复制标题
DOI：
--
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Xi Chen;Yining Wang;Yuanshuo Zhou
中科院分区：
文献类型：
--
作者：
Xi Chen;Yining Wang;Yuanshuo Zhou
本文研究了有限销售季节下的动态产品分类优化问题。在每个时间段，卖方提供一个到达客户的基数约束下的可替代产品的分类，和客户提供的产品根据离散选择模型进行购买。大多数现有的工作将每个产品与实值固定均值效用相关联，并假设多项logit选择（MNL）模型。在许多实际应用中，产品的特征/上下文信息是容易获得的。在本文中，我们通过假设平均效用和特征之间的线性关系来结合特征信息。此外，我们允许产品的特征信息随时间变化，这样潜在的选择模型也可以是非平稳的。为了解决这种变化的上下文MNL模型下的动态分类优化问题，我们需要同时学习潜在的未知系数并做出分类决策。为此，我们开发了一个上置信限（UCB）为基础的政策，并建立了遗憾界的顺序为$\widetilde O（d\sqrt{T}）$，其中$d$是维度的功能和$\widetilde O$抑制对数依赖。我们进一步建立了下界$\Omega（d\sqrt{T}/K）$，其中$K$是所提供的分类的基数约束，通常很小。当$K$是一个常数，我们的政策是最佳的对数因子。在UCB算法的开发阶段，我们需要根据学习到的信息解决分类优化的组合优化问题。我们进一步开发了一个近似算法和一个有效的贪婪启发式。我们的数值研究进一步证明了所提出的政策的有效性。
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.