# 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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 23, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7329638004302979, "perplexity": 312.1637132628124}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-39/segments/1631780057227.73/warc/CC-MAIN-20210921191451-20210921221451-00479.warc.gz"}