Learning When to Restart: Nonstationary Newsvendor from Uncensored to Censored Demand
It provides a practical solution for decision-making under nonstationarity in stochastic optimization, applicable to domains like healthcare and supply chain, but is incremental as it builds on existing nonstationary methods.
The paper tackles the nonstationary newsvendor problem with unknown demand nonstationarity and censoring by proposing a distributional-detection-and-restart framework, resulting in algorithms with matching regret bounds and superior performance on real-world datasets like nurse staffing and COVID-19 test demand.
We study nonstationary newsvendor problems under nonparametric demand models and general distributional measures of nonstationarity, addressing the practical challenges of unknown degree of nonstationarity and demand censoring. We propose a novel distributional-detection-and-restart framework for learning in nonstationary environments, and instantiate it through two efficient algorithms for the uncensored and censored demand settings. The algorithms are fully adaptive, requiring no prior knowledge of the degree and type of nonstationarity, and offer a flexible yet powerful approach to handling both abrupt and gradual changes in nonstationary environments. We establish a comprehensive optimality theory for our algorithms by deriving matching regret upper and lower bounds under both general and refined structural conditions with nontrivial proof techniques that are of independent interest. Numerical experiments using real-world datasets, including nurse staffing data for emergency departments and COVID-19 test demand data, showcase the algorithms' superior and robust empirical performance. While motivated by the newsvendor problem, the distributional-detection-and-restart framework applies broadly to a wide class of nonstationary stochastic optimization problems. Managerially, our framework provides a practical, easy-to-deploy, and theoretically grounded solution for decision-making under nonstationarity.