Technical Note—Data-Driven Newsvendor Problem: Performance of the Sample Average Approximation

We consider the data-driven newsvendor problem in which a manager makes inventory decisions sequentially and learns the unknown demand distribution based on observed samples of continuous demand (no truncation). We study the widely used sample average approximation (SAA) approach and analyze its performance with respect to regret, which is the difference between its expected cost and the optimal cost of the clairvoyant who knows the underlying demand distribution. We characterize how the regret performance depends on a minimal separation assumption that restricts the local flatness of the demand distribution around the optimal order quantity. In particular, we consider two separation parameters, γ and ε, where γ denotes the minimal possible value of the density function in a small neighborhood of the optimal quantity and ε defines the size of the neighborhood. We establish a lower bound on the worst case regret of any policy that depends on the product of the separation parameters $\gamma \epsilon$ and the time horizon N. We also show a finite-time upper bound of SAA that matches the lower bound in terms of the separation parameters and the time horizon (up to a logarithmic factor of N). This illustrates the near-optimal performance of SAA with respect to not only the time horizon, but also the local flatness of the demand distribution around the optimal quantity. Our analysis also shows upper bounds of $O(\log \hspace{0.17em}N)$ and $O(\sqrt{N})$ on the worst case regret of SAA over N periods with and without the minimal separation assumption. Both bounds match the lower bounds implied by the literature, which illustrates the asymptotic optimality of the SAA approach.