  Inventory models with lost sales and large lead times have traditionally been
considered intractable due to the curse of dimensionality. Recently, Goldberg
and co-authors 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 \emph{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.
