In this paper we address two models of non-deterministic discrete-time finite-horizon dynamic programs (DPs): implicit stochastic DPs – the information about the random events is given by value oracles to their CDFs; and sample-based DPs – the information about the random events is deduced via samples. In both models the single period cost functions are accessed via value oracle calls and are assumed to possess either monotone or convex structure. We develop the first near-optimal relative approximation schemes for each of the two models. Applications in stochastic inventory control, i.e., several variants of the so called Newsvendor problem are discussed in detail. Our results are achieved by a combination of Bellman equation calculations, density estimation results, and extensions of the technique of K- approximation sets and functions introduced by Halman et al. [Math. Oper. Res., 34, (2009), pp. 674–685].
Citation
This paper has been acccepted for publication by Informs Journal on Computing and is available online at the author's personal webpage. Parts of this work were first presented in April 23rd 2014 in the annual meeting of the Israel OR society as "Approximation Schemes for Sample-Based Non-linear Newsvendor", see: http://ie.technion.ac.il/Labs/Orsis/kenes_2014/ORSIS_2014_program.pdf First full version appeared on June 8th 2015 under the title: "Provably Near-Optimal Approximation Schemes for Sample-Based Dynamic Programs with emphasis on stochastic inventory control models".