# 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, 2021 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, 2021 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, 2021 at 23:46
• @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, 2021 at 6:46
• Yes, I just want to further confirm what Neil already said: this type of question is perfectly fine for our site. Actually, I would like to see more and more questions of this type here. I will soon delete these comments.
– nbro
Jun 15, 2021 at 11:18

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.