Optimality Gap of Constant-Order Policies Decays Exponentially in the Lead Time for Lost Sales Models

Inventory models with lost sales and large lead times have traditionally been considered intractable due to the curse of dimensionality. Recently, Goldberg and coauthors laid the foundations for a new approach to solving these models, by proving that as the lead time grows large, a simple constant-order policy is asymptotically optimal. However, the bounds proven there require the lead time to be very large before the constant-order policy becomes effective, in contrast to the good numerical performance demonstrated by Zipkin even for small lead time values. In this work, we prove that for the infinite-horizon variant of the same lost sales problem, the optimality gap of the same constant-order policy actually converges exponentially fast to zero, with the optimality gap decaying to zero at least as fast as the exponential rate of convergence of the expected waiting time in a related single-server queue to its steady-state value. We also derive simple and explicit bounds for the optimality gap, and demonstrate good numerical performance across a wide range of parameter values for the special case of exponentially distributed demand. Our main proof technique combines convexity arguments with ideas from queueing theory.