Shilin Yuan

Jiameng Lyu, Shilin Yuan, Bingkun Zhou et al.

We study the regret performance of Sample Average Approximation (SAA) for data-driven newsvendor problems with general convex inventory costs. In literature, the optimality of SAA has not been fully established under both α-global strong convexity and (α,β)-local strong convexity (α-strongly convex within the β-neighborhood of the optimal quantity) conditions. This paper closes the gaps between regret upper and lower bounds for both conditions. Under the (α,β)-local strong convexity condition, we prove the optimal regret bound of Θ(\log T/α+ 1/ (αβ)) for SAA. This upper bound result demonstrates that the regret performance of SAA is only influenced by αand not by βin the long run, enhancing our understanding about how local properties affect the long-term regret performance of decision-making strategies. Under the α-global strong convexity condition, we demonstrate that the worst-case regret of any data-driven method is lower bounded by Ω(\log T/α), which is the first lower bound result that matches the existing upper bound with respect to both parameter αand time horizon T. Along the way, we propose to analyze the SAA regret via a new gradient approximation technique, as well as a new class of smooth inverted-hat-shaped hard problem instances that might be of independent interest for the lower bounds of broader data-driven problems.

Xin Chen, Jiameng Lyu, Shilin Yuan et al.

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.