Online Learning for Constrained Assortment Optimization Under Markov Chain Choice Model

• 成果类型: Article; Early Access
• 署名作者: Li, Shukai; Luo, Qi; Huang, Zhiyuan; Shi, Cong
• 署名单位: Northwestern University; University of Iowa; Tongji University; University of Miami
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0693
• 发表日期: 2024
• 页码: 1-30
• 关键词: management; algorithm

摘要

We study a dynamic assortment selection problem where arriving customers make purchase decisions among offered products from a universe of products under a Markov chain choice (MCC) model. The retailer only observes the assortment and the customer's single choice per period. Given limited display capacity, resource constraints, and no a priori knowledge of problem parameters, the retailer's objective is to sequentially learn the choice model and optimize cumulative revenues over a finite selling horizon. We develop a fast linear system based explore-then-commit (FastLinETC for short) learning algorithm that balances the tradeoff between exploration and exploitation. The algorithm can simultaneously estimate the arrival and transition probabilities in the MCC model by solving a linear system of equations and determining the near-optimal assortment based on these estimates. Furthermore, our consistent estimators offer superior computational times compared with existing heuristic estimation methods, which often suffer from inconsistency or a significant computational burden.