Provably Near-Optimal Approximation Schemes for Implicit Stochastic and for Sample-Based Dynamic Programs
Nir Halman (halmanhuji.ac.il)
Abstract: 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].
Keywords: Approximation algorithms, inventory control, $K$-approximation sets and functions, sample average approximation
Category 1: Other Topics (Dynamic Programming )
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".
Entry Submitted: 06/08/2015
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|