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

Abstract

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 prespecified additive error of ε > 0. The proposed approximation algorithm is a generalization of the explicit-enumeration algorithm and offers us full control in the trade-off 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. Our approximation scheme is illustrated on a well-known problem in inventory theory, the single-product problem with lost sales and lead times. We demonstrate the practical value of our scheme by implementing our approximation scheme and the explicit-enumeration algorithm on instances of this inventory problem.