Inventory Balancing with Online Learning

• 成果类型: Article
• 署名作者: Cheung, Wang Chi; Ma, Will; Simchi-Levi, David; Wang, Xinshang
• 署名单位: National University of Singapore; Columbia University; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Shanghai Jiao Tong University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2021.4216
• 发表日期: 2022
• 页码: 1776-1807
• 关键词: decision analysis; Sequential; analysis of algorithms; suboptimal algorithms; INVENTORY PRODUCTION

摘要

We study a general problem of allocating limited resources to heterogeneous customers over time under model uncertainty. Each type of customer can be serviced using different actions, each of which stochastically consumes some combination of resources and returns different rewards for the resources consumed. We consider a general model in which the resource consumption distribution associated with each customer type-action combination is not known but is consistent and can be learned over time. In addition, the sequence of customer types to arrive over time is arbitrary and completely unknown. We overcome both the challenges of model uncertainty and customer heterogeneity by judiciously synthesizing two algorithmic frameworks from the literature: inventory balancing, which reserves a portion of each resource for high-reward customer types that could later arrive based on competitive ratio analysis, and online learning, which explores the resource consumption distributions for each customer type under different actions based on regret analysis. We define an auxiliary problem, which allows for existing competitive ratio and regret bounds to be seamlessly integrated. Furthermore, we propose a new variant of upper confidence bound (UCB), dubbed lazyUCB, which conducts less exploration in a bid to focus on exploitation in view of the resource scarcity. Finally, we construct an information-theoretic family of counterexamples to show that our integrated framework achieves the best possible performance guarantee. We demonstrate the efficacy of our algorithms on both synthetic instances generated for the online matching with stochastic rewards problem under unknown probabilities and a publicly available hotel data set. Our framework is highly practical in that it requires no historical data (no fitted customer choice models or forecasting of customer arrival patterns) and can be used to initialize allocation strategies in fast-changing environments.