Survey of Data-driven Newsvendor: Unified Analysis and Spectrum of Achievable Regrets
This work addresses the Newsvendor problem for operations research and inventory management, offering incremental improvements through a comprehensive survey and unified framework.
The paper tackles the data-driven Newsvendor problem by providing a unified analysis that fills gaps in the literature and shows that regrets can range from 1/√n to 1/n, with simulations confirming the analysis as an accurate predictor of empirical regret.
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.