Xi Chen, Yining Wang, Yuan Zhou
arXiv 31 Oct 2018 · Econometrics · 27 citations (OpenAlex)
arXiv:1810.13069 · PDF · DOI · OpenAlex · Extracted main text
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.
appendix boundary found by appendix_command · 56% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Dani, V., Hayes, T. P., & Kakade, S. M (2008) Stochastic Linear Optimization under Bandit Feedback | 0.928 | 4 | 3 | 100% |
| 2 | Li, L., Lu, Y., & Zhou, D (2017) Provably optimal algorithms for generalized linear contextual bandits self | 0.920 | 9 | 3 | 78% |
| 3 | Agrawal, S., Avadhanula, V., Goyal, V., & Zeevi, A (2017) MNL-bandit: A dynamic learning approach to assortment selection | 0.874 | 6 | 2 | 100% |
| 4 | Chen, X., & Wang, Y (2018) A note on tight lower bound for mnl-bandit assortment selection models self | 0.811 | 4 | 2 | 100% |
| 5 | Rusmevichientong, P., Shen, Z.-J., & Shmoys, D (2010) Dynamic assortment optimization with a multinomial logit choice model and capacity constraint | 0.811 | 4 | 2 | 100% |
| 6 | Filippi, S., Cappe, O., Garivier, A., & Szepesvári, C (2010) Parametric bandits: The generalized linear case | 0.811 | 4 | 2 | 100% |
| 7 | Van der Vaart, A. W (2000) Asymptotic statistics\/ | 0.737 | 4 | 2 | 75% |
| 8 | Cheung, W. C., & Simchi-Levi, D (2017) Thompson sampling for online personalized assortment optimization problems with multinomial logit choice models | 0.693 | 7 | 1 | 100% |
| 9 | Agrawal, S., Avandhanula, V., Goyal, V., & Zeevi, A (2017) Thompson sampling for MNL-bandit | 0.644 | 4 | 1 | 100% |
| 10 | Saure, D., & Zeevi, A (2013) Optimal dynamic assortment planning with demand learning | 0.585 | 3 | 1 | 100% |
Showing the top 10 of 27 scored citations.
arXiv econ.EM papers that cite this one, ranked by how heavily they lean on it.
| Citing paper | Intensity | Mentions | Sections | |
|---|---|---|---|---|
| 1 | Zero-Inflated Bandits | 0.000 | 1 | 1 |