Sampling-Based Approximation for Series Inventory Systems

We study inventory management of an infinite-horizon, series system with multiple stages. Each stage orders from its immediate upstream stage, and the most upstream stage orders from an external supplier. Random demand with unknown distribution occurs at the most downstream stage. Each stage incurs inventory holding cost while the most downstream stage also incurs demand backlogging cost when it experiences inventory shortage. The objective is to minimize the expected total discounted cost over the planning horizon. We apply the sample average approximation (SAA) method to obtain a heuristic policy (SAA policy) using the empirical distribution function constructed from a demand sample (of the underlying demand distribution). We derive an upper bound of sample size (viz., distribution-free bound) that guarantees that the performance of the SAA policy be close (i.e., with arbitrarily small relative error) to the optimal policy under known demand distribution with high probability. This result is obtained by first deriving a separable and tight cost upper bound of the whole system that depends on (given) echelon base-stock levels and then showing that the cost difference between the SAA and optimal policies can be measured by the distance between the empirical and the underlying demand distribution functions. We also provide a lower bound of sample size that matches the upper bound (in the order of relative error). Furthermore, when the demand distribution is continuous and has an increasing failure rate (IFR), we derive a tighter sample size upper bound (viz., distribution-dependent bound). Both distribution-free and distribution-dependent bounds for the newsvendor problem, a special case of our series system, improve the previous results. In addition, we show that both bounds increase polynomially as the number of stages increases. The performance of SAA policy and the sample size bounds are illustrated numerically. Finally, we extend the results to finite-horizon series systems. This paper was accepted by David Simchi-Levi, operations management. Funding: K. Zhang is partially supported by the National Nature Science Foundation of China [Grants 71901200 and 72471220]. X. Gao is partially supported by the Hong Kong Research Grants Council General Research Fund [Grant CUHK-14506620]. Z. Wang is partially supported by the National Nature Science Foundation of China [Grant 72401146]. S. X. Zhou is partially supported by the Hong Kong Research Grants Council General Research Fund [Grant CUHK-14500921], the National Natural Science Foundation of China [Grant 72394395], and the Asian Institute of Supply Chains and Logistics. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2022.01876 .