Stochastic dynamic programming
The dynamic programming algorithm is
JN = g(xT)
Jk(xk) = umax
k^2 Uk
E(uk(xk,uk,ξk)+Jk+ 1 (xk+ 1 )j Fk)
= umax
k^2 Uk
E(uk(xk,uk,ξk)+Jk+ 1 (f(xk,uk,ξk))j Fk).
This is a principle and not a general theorem. The usual interpretation of
the conditional expectation is that we know the value ofξ 0 ,ξ 1 ,.. .,ξkand
consider their valuess 0 ,s 1 ,.. .,skas a parameter of the optimization in
stagek+ 1 .To simplify the problem one generally assumes that to solve
thek-th problem it is su¢ cient to knowxk,including the determination of
the distribution ofξk+ 1 ,that is the distribution ofξk+ 1 depends only on
xk.This is the Markovian assumption about the random factor.
