  We propose a Fully Polynomial-Time Approximation Scheme (FPTAS) for
stochastic dynamic programs with multidimensional action, scalar state, convex
costs and linear state transition function. The action spaces are polyhedral
and described by parametric linear programs. This type of problems finds
applications in the area of optimal planning under uncertainty, and can be
thought of as the problem of optimally managing a single non-discrete resource
over a finite time horizon. We show that under a value oracle model for the
cost functions this result for one-dimensional state space is "best possible",
because a similar dynamic programming model with two-dimensional state space
does not admit a PTAS.
  The FPTAS relies on the solution of polynomial-sized linear programs to
recursively compute an approximation of the value function at each stage. Our
paper enlarges the class of dynamic programs that admit an FPTAS by showing,
under suitable conditions, how to deal with multidimensional action spaces and
with vectors of continuous random variables with bounded support. These results
bring us one step closer to overcoming the curse of dimensionality of dynamic
programming.
