# How to prove the second form of Bellman's equation?

I'd like to prove this "second form" of Bellman's equation: $$v(s) = \mathbb{E}[R_{t + 1} + \gamma v(S_{t+1}) \mid S_{t} = s]$$ starting from Bellman's equation: $$v(s) = \mathbb{E}[G_{t} \mid S_{t} = s]$$ where the return $$G_{t}$$ is defined as follows: $$G_{t} = \sum_{k=0}^{\infty}{\gamma^{k}R_{t+k+1}}$$.

I tried to use the linearity of the expectation as follows: $$v(s) = \mathbb{E}[R_{t+1} \mid S_{t} = s] + \mathbb{E}[\sum_{k = 1}^{\infty}{\gamma^{k}R_{t+k+1}} \mid S_{t} = s]$$

Which gives us: $$v(s) = \mathbb{E}[R_{t+1} \mid S_{t} = s] + \gamma\mathbb{E}[\sum_{k = 0}^{\infty}{\gamma^{k}R_{(t + 1) + k + 1}} \mid S_{t} = s] = \mathbb{E}[R_{t+1} \mid S_{t} = s] + \gamma\mathbb{E}[G_{t + 1} \mid S_{t} = s]$$

I also tried to develop the second formula: $$v(s) = \mathbb{E}[R_{t+1} \mid S_{t} = s] + \gamma\mathbb{E}[v(S_{t+1}) \mid S_{t} = s]$$ and I'm tempted to say that $$\mathbb{E}[G_{t+1} \mid S_{t} = s] = \mathbb{E}[v(S_{t+1}) \mid S_{t} = s]$$ but that would only be right in the case that both follow conditions are verified:

1. We have the value function of a particular state $$s^\prime$$ inside the expectation of the second term (something like $$\mathbb{E}[v(s^\prime) \mid S_{t} = s]$$ which would directly give $$v(s^\prime)$$ since it's a scalar) and not $$v(S_{t+1})$$.
2. We have $$\mathbb{E}[G_{t+1} \mid S_{\textbf{t+1}} = s^\prime]$$ in the second term.

I'm probably not understanding something correctly especially what $$v(S_{t+1})$$ would mean (that wasn't covered in the material I'm following but for me it would be just a function that maps the possible states at time step $$t+1$$ to the expected return starting from that step at that time step).

• This seems like it would be more appropriate for cs.stackexchange. Jun 14 at 23:33
• @ThePointer thank you for your comment. I'm sorry I didn't see it earlier, I've already solved my question and posted it as an answer. I wonder if I should just delete the question if it's irrelevant to this forum. Jun 14 at 23:44
• It might not be irrelevant (there's a tag for the Bellman equations in the context of reinforcement learning), but cs.stackexchange might have been the better place for this question. Nonetheless, I suggest you leave it, so that others may benefit from it in the future. And close your question by accepting your answer when the system allows. Jun 14 at 23:46
• @ThePointer thank you! I'll keep that in mind for future similar questions. Jun 14 at 23:47
• @ThePointer I disagree, in as much as questions about the maths behind reinforcement learning - or any AI-related topic - are very much on-topic here. It is more often the coding problems that get marked as off-topic here. When the coding issue is regardling theory comprehension (as opposed to more obvious bug or programming language issue) then I believe that should be on topic here too. If you'd like to clarify or debate further, then you could take it to meta. Jun 15 at 6:46

Since my question arose from my incomprehension of $$v(S_{t + 1})$$ and since I got clarifications on it by Neil Slater, I thought I'd go back to this question and try to answer it again.
So I'm assuming that $$v(S_{t + 1})$$ is a random variable made by the composition of the state-value function $$v$$ and the random variable $$S_{t + 1}$$.
Since $$v(s) = \mathbb{E}[G_{t + 1} \mid S_{t + 1} = s]$$, the random variable $$v(S_{t + 1})$$ is $$\mathbb{E}[G_{t + 1} \mid S_{t + 1}]$$. Using a corollary of the total expectation theorem we get that $$\mathbb{E}[v(S_{t + 1}) \mid S_{t} = s] = \mathbb{E}[G_{t+1} \mid S_{t} = s]$$. This proved, we can conclude using first developments of the question.