统一分析数据驱动报童问题，揭示后悔值范围从1/√n到1/n
Survey of Data-driven Newsvendor: Unified Analysis and Spectrum of Achievable Regrets
- 基于聚类分布构建统一分析框架
- 证明后悔值可覆盖1/√n至1/n全部范围
- 适用于关注理论边界与实证性能的研究者
报童问题的目标是预测从某分布中抽取的数值，高估与低估的后果不对称。在数据驱动版本中，分布未知，需依赖样本进行决策。该问题在多种变体下被研究：加性与乘性后悔、高概率与期望界、不同分布类别。本文系统分析所有组合，填补文献空白并简化诸多证明。核心提出基于聚类分布的统一分析方法，结合新构造的下界，证明后悔值可在1/√n至1/n之间取任意值。在常见分布上的仿真表明，该框架能准确预测不同数据规模下的经验后悔表现。
原文摘要 · Abstract (English)
In the Newsvendor problem, the goal is to guess the number that will be drawn from some distribution, with asymmetric consequences for guessing too high vs. too low. In the data-driven version, the distribution is unknown, and one must work with samples from the distribution. Data-driven Newsvendor has been studied under many variants: additive vs. multiplicative regret, high probability vs. expectation bounds, and different distribution classes. This paper studies all combinations of these variants, filling in many gaps in the literature and simplifying many proofs. In particular, we provide a unified analysis based on the notion of clustered distributions, which in conjunction with our new lower bounds, shows that the entire spectrum of regrets between $1/\sqrt{n}$ and $1/n$ can be possible. Simulations on commonly-used distributions demonstrate that our notion is the "correct" predictor of empirical regret across varying data sizes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。