Technical Note: Data-driven newsvendor problem: Performance of the sample average approximation

Publication Type

Journal Article

Publication Date

6-2022

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, gamma and epsilon, where gamma denotes the minimal possible value of the density function in a small neighborhood of the optimal quantity and epsilon 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 N) and O(root 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

sample average approximation, newsvendor problem, data-driven decision making, regret analysis, finite-time performance

Discipline

Operations and Supply Chain Management | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Operations Management

Publication

Operations Research

Volume

70

Issue

4

First Page

1996

Last Page

2012

ISSN

0030-364X

Identifier

10.1287/opre.2022.2307

Publisher

Institute for Operations Research and Management Sciences

Additional URL

https://doi.org/10.1287/opre.2022.2307

This document is currently not available here.

Share

COinS