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

Meichun Lin (), Woonghee Tim Huh (), Harish Krishnan () and Joline Uichanco ()
Additional contact information
Meichun Lin: Sauder School of Business, University of British Columbia, BC V6T 1Z4, Canada
Woonghee Tim Huh: Sauder School of Business, University of British Columbia, BC V6T 1Z4, Canada
Harish Krishnan: Sauder School of Business, University of British Columbia, BC V6T 1Z4, Canada
Joline Uichanco: Ross School of Business, University of Michigan, Ann Arbor, Michigan 48109

Operations Research, 2022, vol. 70, issue 4, 1996-2012

Abstract: 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 γ ε 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 N ) and O ( 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.

Keywords: Operations and Supply Chains; sample average approximation; newsvendor problem; data-driven decision making; regret analysis; finite-time performance (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2307 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:4:p:1996-2012

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().