Answers.Body: <p>Since my question arose from my incomprehension of <span class="math-container">$v(S_{t + 1})$</span> and since I got clarifications on it by <a href="https://ai.stackexchange.com/users/1847/neil-slater">Neil Slater</a>, I thought I'd go back to this question and try to answer it again.</p>
  <p>So I'm assuming that <span class="math-container">$v(S_{t + 1})$</span> is a random variable made by the composition of the <em>state-value function</em> <span class="math-container">$v$</span> and the random variable <span class="math-container">$S_{t + 1}$</span>.</p>
  <p>Since <span class="math-container">$v(s) = \mathbb{E}[G_{t + 1} \mid S_{t + 1} = s]$</span>, the random variable <span class="math-container">$v(S_{t + 1})$</span> is <span class="math-container">$\mathbb{E}[G_{t + 1} \mid S_{t + 1}]$</span>. Using a corollary of the total expectation theorem we get that <span class="math-container">$\mathbb{E}[v(S_{t + 1}) \mid S_{t} = s] = \mathbb{E}[G_{t+1} \mid S_{t} = s]$</span>. This proved, we can conclude using first developments of the question.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-14T23:43:43.527Z
Answers.LastActivityDate: 2021-06-15T07:56:24.663Z
Answers.LastEditDate: 2021-06-15T07:56:24.663Z
Answers.UserDisplayName: Daviiid
Body: <p>I'd like to prove this &quot;second form&quot; of Bellman's equation: <span class="math-container">$v(s) = \mathbb{E}[R_{t + 1} + \gamma v(S_{t+1}) \mid S_{t} = s]$</span> starting from Bellman's equation: <span class="math-container">$v(s) = \mathbb{E}[G_{t} \mid S_{t} = s]$</span> where the return <span class="math-container">$G_{t}$</span> is defined as follows: <span class="math-container">$G_{t} = \sum_{k=0}^{\infty}{\gamma^{k}R_{t+k+1}}$</span>.</p>
  <p>I tried to use the linearity of the expectation as follows: <span class="math-container">$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]$</span></p>
  <p>Which gives us: <span class="math-container">$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]$</span></p>
  <p>I also tried to develop the second formula: <span class="math-container">$v(s) = \mathbb{E}[R_{t+1} \mid S_{t} = s] + \gamma\mathbb{E}[v(S_{t+1}) \mid S_{t} = s]$</span> and I'm tempted to say that <span class="math-container">$\mathbb{E}[G_{t+1} \mid S_{t} = s] = \mathbb{E}[v(S_{t+1}) \mid S_{t} = s]$</span> but that would only be right in the case that both follow conditions are verified:</p>
  <ol>
  <li>We have the value function of a particular state <span class="math-container">$s^\prime$</span> inside the expectation of the second term (something like <span class="math-container">$\mathbb{E}[v(s^\prime) \mid S_{t} = s]$</span> which would directly give <span class="math-container">$v(s^\prime)$</span> since it's a scalar) and not <span class="math-container">$v(S_{t+1})$</span>.</li>
  <li>We have <span class="math-container">$\mathbb{E}[G_{t+1} \mid S_{\textbf{t+1}} = s^\prime]$</span> in the second term.</li>
  </ol>
  <p>I'm probably not understanding something correctly especially what <span class="math-container">$v(S_{t+1})$</span> 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 <span class="math-container">$t+1$</span> to the expected return starting from that step at that time step).</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-06-14T23:33:04.057Z
Comments.Text: This seems like it would be more appropriate for cs.stackexchange.
Comments.UserDisplayName: The Pointer
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-06-14T23:44:41.350Z
Comments.Text: @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.
Comments.UserDisplayName: Daviiid
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-06-14T23:46:34.377Z
Comments.Text: 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.
Comments.UserDisplayName: The Pointer
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-06-14T23:47:16.807Z
Comments.Text: @ThePointer thank you! I'll keep that in mind for future similar questions.
Comments.UserDisplayName: Daviiid
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-06-15T06:46:25.573Z
Comments.Text: @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.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-06-15T06:50:18.980Z
Comments.Text: @NeilSlater Ok, thanks for the clarification.
Comments.UserDisplayName: The Pointer
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-06-15T11:18:44.013Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><proofs><value-functions><bellman-equations>
Title: How to prove the second form of Bellman's equation?
UserDisplayName: Daviiid
ThreadText: # How to prove the second form of Bellman's equation?
  
  (Asked by: username_0 on 2021-06-11)
  
  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).
  
  **Tags:** reinforcement-learning, proofs, value-functions, bellman-equations
  
  > **Comments:**
  > **username_1**: This seems like it would be more appropriate for cs.stackexchange.  
  > **username_0**: @username_1 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.  
  > **username_1**: 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.  
  > **username_0**: @username_1 thank you! I'll keep that in mind for future similar questions.  
  > **username_2**: @username_1 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.  
  > **username_1**: @username_2 Ok, thanks for the clarification.  
  > **username_3**: Yes, I just want to further confirm what username_2 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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2021-06-14. Score: 2 | Accepted answer
  
  Since my question arose from my incomprehension of $v(S\_{t + 1})$ and since I got clarifications on it by [username_2 username_2](https://ai.stackexchange.com/users/1847/username_2), 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.
  
  
  ---
  
  