hBcapproximation sets and functions

Fully Polynomial Time hBcApproximation Schemes for Continuous Stochastic Convex Dynamic Programs

  • Nir Halman
  • Giacomo Nannicini
    • Categories Approximation Algorithms, Dynamic Programming Tags , ,

    We develop fully polynomial time $(\Sigma,\Pi)$-approximation schemes for stochastic dynamic programs with continuous state and action spaces, when the single-period cost functions are convex Lipschitz-continuous functions that are accessed via value oracle calls. That is, for every given additive error parameter $\Sigma>0$ and multiplicative error factor $\Pi=1+\epsilon>1$, the scheme returns a feasible solution whose value … Read more

    Provably Near-Optimal Approximation Schemes for Implicit Stochastic and for Sample-Based Dynamic Programs

  • Nir Halman
    • Categories Dynamic Programming Tags , , ,

    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 … Read more