The Nonstationary Newsvendor with (and Without) Predictions

Problem definition: The classic newsvendor model yields an optimal decision for a “newsvendor” selecting a quantity of inventory under the assumption that the demand is drawn from a known distribution. Motivated by applications such as cloud provisioning and staffing, we consider a setting in which newsvendor-type decisions must be made sequentially in the face of demand drawn from a stochastic process that is both unknown and nonstationary. All prior work on this problem either (a) assumes that the level of nonstationarity is known or (b) imposes additional statistical assumptions that enable accurate predictions of the unknown demand. Our research tackles the Nonstationary Newsvendor without these assumptions both with and without predictions. Methodology/results: In the setting without predictions, we first design a policy that we prove (via matching upper and lower bounds) achieves order-optimal regret; ours is the first policy to accomplish this without being given the level of nonstationarity of the underlying demand. We then, for the first time, introduce a model for generic (i.e., with no statistical assumptions) predictions with arbitrary accuracy and propose a policy that incorporates these predictions without being given their accuracy. We upper bound the regret of this policy and show that it matches the best achievable regret had the accuracy of the predictions been known. Managerial implications: Our findings provide valuable insights on inventory management. Managers can make more informed and effective decisions in dynamic environments, reducing costs and enhancing service levels despite uncertain demand patterns. This study advances understanding of sequential decision-making under uncertainty, offering robust methodologies for practical applications with nonstationary demand. We empirically validate our new policy with experiments based on three real-world data sets containing thousands of time-series, showing that it succeeds in closing approximately 74% of the gap between the best approaches based on nonstationarity and predictions alone. History: This paper was selected as part of the 1RR initiative between the M&SOM Journal and the MSOM Society. This particular paper was part of the 2024 MSOM Service Operations SIG Conference. Funding: L. An and B. Moseley were supported in part by a Google Research Award, an Infor Research Award, a Carnegie Bosch Junior Faculty Chair, NSF [Grants CCF-2121744 and CCF-1845146] and ONR [Grant N000142212702]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2024.1168 .