  Multistage stochastic programming deals with operational and planning
problems that involve a sequence of decisions over time while responding to
realizations that are uncertain. Algorithms designed to address multistage
stochastic linear programming (MSLP) problems often rely upon scenario trees to
represent the underlying stochastic process. When this process exhibits
stagewise independence, sampling-based techniques, particularly the stochastic
dual dynamic programming (SDDP) algorithm, have received wide acceptance.
However, these sampling-based methods still operate with a deterministic
representation of the problem that uses the so-called sample average
approximation. In this work, we present a sequential sampling approach for MSLP
problems that allows the decision process to assimilate newly sampled data
recursively. We refer to this method as the stochastic dynamic linear
programming (SDLP) algorithm. Since we use sequential sampling, the algorithm
does not necessitate a priori representation of uncertainty, either through a
scenario tree or sample average approximation, both of which require a
knowledge/estimation of the underlying distribution. In this regard, SDLP is a
sequential sampling approach to address MSLP problems. This method constitutes
a generalization of the Stochastic Decomposition (SD) for two-stage SLP models.
We employ quadratic regularization for optimization problems in the
non-terminal stages. Furthermore, we introduce the notion of basic feasible
policies which provide a piecewise-affine solution discovery scheme, that is
embedded within the optimization algorithm to identify incumbent solutions used
for regularization. Finally, we show that the SDLP algorithm provides a
sequence of decisions and corresponding value function estimates along a
sequence of state trajectories that asymptotically converge to their optimal
counterparts, with probability one.
