# Stochastic dynamic programming

I am making some homework exercises at the moment and I was wondering if what I did in the following exercise was correct.

PROBLEM

Solve $E(\sum_{k=0}^{N-1}(1-u_k)X_k + X_N) \rightarrow \max$, where $N\in\mathbb{N}$ is fixed $u_k$ are control variables in $[0,1]$, $X_k$ random variables with $x_0 = 1$ and $X_{k+1} = X_k + u_kX_k + Y_k+1$ and $Y_{k+1}$ are independent exponentially distributed random variables with mean $x_k$.

MY APPROACH

I first rewrote the objective function in the following way:

$$\sum_{k=0}^{N-1}E((1-u_k)X_k) + E(X_n) \rightarrow \max$$

Also, since Y is exponentially distributed $E(Y_{k+1}) = x_k$

As for the solution, I consider first the sum for $k = 1$ to maximize.

First I compute $X_1 = X_0 + u_0X_0 + Y_1$ where $E(Y_1) = 1$ since $x_0$ is $1$.

Also, $u_0 = 0$ since we want to maximize, and for $k=0$, $u_0$ is 1 for the maximum.

Hence, we get $E(1-u_1)X_1) \rightarrow \max = E((1-u_1)2)$ hence we get $u_1 = 0$

You do this for all $k$, is this the correct approach because I don't think I am correct..

Consider $N=2$, then your expression is $$E\{X_0-u_0X_0+X_1-u_1X_1+X_2\}.$$ Now substitute $X_1=X_0+u_0X_0+Y_0+1$ and $X_2=X_1+u_1X_1+Y_1+1$ and you will see the $-u_iX_i$, $i=\{0,1\}$ terms vanishes.$$E\{X_0+X_0+u_0X_0+Y_0+1+X_1+u_1X_1+Y_1+1\}.$$ Now substitute for $X_1$ again and you get $$E\{X_0+X_0+u_0X_0+Y_0+1+X_0+u_0X_0+Y_0+1+u_1(X_0+u_0X_0+Y_0+1)+Y_1+1\}.$$ Since $X_0=1$ and $EY_k$ is always positive for exponential random variables the controls $u_k$ should all be $1$ in order to maximize the expression.
• You can easily use mathematical induction to prove for general $N$. Since above we have proved for $N=2$, assume for $N=n$ all $u_0,\dots u_{n-1}$ are $1$ and show that for $N=n+1$ we need $u_n=1$ to maximize the expression. Which is easy to you taking $X_n$ and $X_n+1$ terms like we did for $N=2$. Then by induction we have for all $N$. – triomphe Nov 6 '13 at 15:25
• Thanks but why is $X_1$ = $X_0 + u_0X_0 + Y_0 + 1$, I think it should be $X_0 + u_0X_0 + Y_1$? – Nedellyzer Nov 6 '13 at 15:53
• But you define in your problem $X_{k+1}=X_k+u_kX_k+Y_k+1$ so for $X_1$ it is $Y_0$ then you should may be define $Y_{k+1}$. Is the $+1$ part of the index of $Y$? Either way the analysis doesn't change. – triomphe Nov 6 '13 at 20:56