Stochastic dynamic programming

Authors: Bo Yuan, Ali Amadeh, Max Greenberg, Raquel Sarabia Soto and Claudia Valero De la Flor (CHEME/SYSEN 6800, Fall 2021)

Theory, methodology and algorithm discussion

Theory

Stochastic dynamic programming combines stochastic programming and dynamic programming. Therefore, to understand better what it is, it is better first to give two definitions:

• Stochastic programming. Unlike in a deterministic problem, where a decision’s outcome is only determined by the decision itself and all the parameters are known, in stochastic programming there is uncertainty and the decision results in a distribution of transformations.
• Dynamic programming. It is an optimization method that consists in dividing a complex problem into easier subprobems and solving them recursively to find the optimal sub-solutions which lead to the complex problem optima.

In any stochastic dynamic programming problem, we must define the following concepts:

• Policy, which is the set of rules used to make a decision.
• Initial vector, $p$ where $p\in \ D$ and $D$ is a finite closed region.
• Choice made, $q$ where $q\in \ S$ and $S$ is a set of possible choices.
• Stochastic vector, $z$.
• Distribution function $dG_{q}(p,z)$, associated with $z$ and dependent on $p$ and $q$.
• Return, which is the expected value of the function after the final stage.

In a stochastic dynamic programming problem, we assume that $z$ is known after the decision of stage $n-1$ has been made and before the decision of stage $n$ has to be made.

Methodology and algorithm

First, we define the N-stage return obtained using the optimal policy and starting with vector $p$:

$f_{N}\left(p\right)=\max {R\left(p_{N}\right)}$ where $R\left(p_{N}\right)$ is the function of the final state $p_{N}$

Second, we define the initial transformation as $T_{q}$, and $z$, as the state resulting from it. The return after $N-1$ stages will be $f_{N-1}(z)$ using the optimal policy. Therefore, we can formulate the expected return due to the initial choice made in $T_{q}$:

$\int _{z\in D}{f_{N-1}\left(z\right)dG_{q}(p,z)}$

Having defined that, the recurrence relation can be expressed as:

$f_{N}\left(p\right)=max\ \int _{z\in D}{f_{N-1}\left(z\right)\ dG_{q}\left(p,z\right)\ }$