Closing the Gaps: Optimality of Sample Average Approximation for Data-Driven Newsvendor Problems
This provides theoretical guarantees for inventory management algorithms, though it's an incremental theoretical analysis of an existing method.
This paper establishes optimal regret bounds for Sample Average Approximation (SAA) in data-driven newsvendor problems, proving Θ(log T/α + 1/(αβ)) regret under local strong convexity and Ω(log T/α) lower bounds under global strong convexity.
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.