Closing the Gap : A Learning Algorithm for the Lost-Sales Inventory System with Lead Times

We consider a periodic-review single-product inventory system with lost-sales and positive lead times under censored demand. In contrast to the classical inventory literature, we assume the firm does not know the demand distribution a priori, and makes adaptive inventory ordering decision in each period based only on the past sales (censored demand) data. The standard performance measure is regret, which is the cost difference between a feasible learning algorithm and the clairvoyant (full-information) benchmark. When the benchmark is chosen to be the (full-information) optimal base-stock policy, Huh et al. [Mathematics of Operations Research 34(2): 397-416 (2009)] developed a nonparametric learning algorithm with a cubic-root convergence rate on regret. An important open question is whether there exists a nonparametric learning algorithm whose regret rate matches the theoretical lower bound of any learning algorithms. In this work, we provide an affirmative answer to the above question. More precisely, we propose a new nonparametric algorithm termed the simulated cycle-update policy, and establish a square-root convergence rate on regret, which is proven to be the lower bound of any learning algorithms. Our algorithm uses a random cycle-updating rule based on an auxiliary simulated system running in parallel, and also involves two new concepts, namely, the withheld on-hand inventory and the double-phase cycle gradient estimation. The techniques developed are effective for learning a stochastic system with complex systems dynamics and lasting impact of decisions