Regret Optimality of Sample Average Approximation for Data-Driven Newsvendor Problems: A General Optimization Perspective

Abstract:Numerous existing studies have examined the performance of Sample Average Approximation (SAA) in the fundamental newsvendor problem. Despite these advances, critical gaps remain in two aspects. First, existing works focus on the linear-cost newsvendor problem and heavily rely on the quantile expression of the optimal solution. As a result, their analytical methods limit generalizability to more general inventory problems, where the optimal solution is not a quantile of the demand distribution. Second, even within the linear-cost setting, notable gaps exist between the state-of-the-art regret lower bound and upper bound for SAA under various conditions. In this paper, we generalize the structure of the newsvendor problem to generic convexity conditions and provide a unified regret analysis of SAA for general sequential stochastic optimization problems. Our approach provides further insights to a broader range of data-driven inventory problems, improves both the upper and lower regret bounds, and establishes the regret rate optimality of SAA. Our lower bound identifies the performance limit achievable by any policy for sequential stochastic optimization and inventory management problems, offering important guidance for future policy design in this area. Moreover, in empirical studies, SAA's performance is frequently used as a benchmark for evaluating new algorithms. The regret rate optimality result provides strong support for its role in assessing other data-driven methods, benefiting both practitioners and researchers. Our new analysis techniques enrich the analysis tools for regret upper and lower bounds for data-driven decision-making problems and other general stochastic optimization problems.

Machine Learning (cs.LG); Optimization and Control (math.OC)

arXiv:2407.04900 [cs.LG]

(or arXiv:2407.04900v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2407.04900 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.