基于被截断的销售数据,优化订货量以降低库存成本。
The Data-Driven Censored Newsvendor Problem
- 用分布鲁棒优化框架分析数据截断对学习算法的影响
- 揭示截断程度决定算法能否逼近最优,否则存在不可逾越的性能下限
- 提出自适应鲁棒算法,在真实与合成数据上表现稳健
我们研究了一种数据驱动的新手问题变体,其中决策者只能基于离线的截断销售数据(而非历史需求真实值)选择订货量,以最小化期望过剩与短缺成本。目标是理解历史需求截断程度如何影响任意学习算法的性能。为此,采用分布鲁棒优化框架,评估策略在不确定性分布集上的最坏情形后悔值。该集合由历史最大订货量定义,包含所有在该点前与真实需求分布一致、之后可任意变化的分布。我们推导出一个自然的充要条件,表明在何种情况下可实现渐近零后悔。当不满足时,精确刻画了截断带来的信息损失:即使拥有无限样本,任何策略性能仍存在不可逾越的下界。据此提出一种能自适应历史截断水平的鲁棒算法,并给出所有截断情形下的有限样本保证,证明其近乎最优(上下界仅差多对数因子)。大量数值实验验证了其在合成与真实数据集上的稳健表现。
原文摘要 · Abstract (English)
We study a censored variant of the data-driven newsvendor problem, where the decision-maker must select an ordering quantity that minimizes expected overage and underage costs based only on offline censored sales data, rather than historical demand realizations. Our goal is to understand how the degree of historical demand censoring affects the performance of any learning algorithm for this problem. To isolate this impact, we adopt a distributionally robust optimization framework, evaluating policies according to their worst-case regret over an ambiguity set of distributions. This set is defined by the largest historical order quantity (the observable boundary of the dataset), and contains all distributions matching the true demand distribution up to this boundary, while allowing them to be arbitrary afterwards. We demonstrate a spectrum of achievability under demand censoring by deriving a natural necessary and sufficient condition under which vanishing regret is an achievable goal. In regimes in which it is not, we exactly characterize the information loss due to censoring: an insurmountable lower bound on the performance of any policy, even when the decision-maker has access to infinitely many demand samples. We then leverage these sharp characterizations to propose a natural robust algorithm that adapts to the historical level of demand censoring. We derive finite-sample guarantees for this algorithm across all possible censoring regimes and show its near-optimality with matching lower bounds (up to polylogarithmic factors). We moreover demonstrate its robust performance via extensive numerical experiments on both synthetic and real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。