Fixed-Dimensional Stochastic Dynamic Programs : An Approximation Scheme and an Inventory Application

We study fixed-dimensional stochastic dynamic programs in a discrete setting over a finite horizon. Under the primary assumption that the cost-to-go functions are discrete L♮-convex, we propose a pseudo-polynomial time approximation scheme that solves this problem to within an arbitrary pre-specified additive error of ε>0. The proposed approximation algorithm is a generalization of the explicit-enumeration algorithm and offers us full control in the tradeoff between accuracy and running time. The main technique we develop for obtaining our scheme is approximation of a fixed-dimensional L♮-convex function on a bounded rectangular set, using only a selected number of points in its domain. Furthermore, we prove that the approximation function preserves L♮-convexity. Finally, to apply the approximate functions in a dynamic program, we bound the error propagation of the approximation. The usefulness of our approximation scheme is illustrated by applying it to a well-known problem in inventory theory, namely the single-product problem with lost sales and lead times (Morton 1969, Zipkin 2008)