Answers.Body: <p>Note that for a general policy <span class="math-container">$\pi$</span> we have that <span class="math-container">$q_{\pi}(s,a) = \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a]$</span>, where in state <span class="math-container">$S_t$</span> we take action <span class="math-container">$a$</span> and thereafter following policy <span class="math-container">$\pi$</span>. Note that the expectation is taken with respect to the reward transition distribution <span class="math-container">$\mathbb{P}(R_{t+1} = r, S_{t+1} = s' | A_t = a, S_t = s)$</span> which I will denote as <span class="math-container">$p(s',r,|s,a)$</span>. </p>
  
  <p>We can then rewrite the expectation as follows</p>
  
  <p><span class="math-container">\begin{align} q_{\pi}(s,a) &amp;= \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a] \\ &amp; = \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a] \\ &amp; = \sum_{r,s'}p(s',r|s,a)(r + \gamma \mathbb{E}_\pi[G_{t+1} | S_{t+1} = s']) \\ &amp; = \sum_{r,s'}p(s',r|s,a)(r + \gamma v_{\pi}(s')) \; .
  \end{align}</span></p>
  
  <p>The key thing to note is that these two terms, <span class="math-container">$G_{t+1}$</span> and <span class="math-container">$v_{\pi}(s')$</span>, are only equal <em>in expectation</em>, which is why in the equation you can exchange the terms because we are taking the expectation. </p>
  
  <p>Note that I have shown this for a general policy <span class="math-container">$\pi$</span> not just the optimal policy.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-05T11:34:27.100Z
Answers.LastActivityDate: 2020-06-05T11:34:27.100Z
Answers.UserDisplayName: David
Answers.Body: <blockquote>
    <p>Can someone provide the reasoning behind why <span class="math-container">$G_{t+1}$</span> is equal to <span class="math-container">$v_*(S_{t+1})$</span>?</p>
  </blockquote>
  
  <p>The two things are not usually exactly equal, because <span class="math-container">$G_{t+1}$</span> is a probability distribution over all possible future returns whilst <span class="math-container">$v_*(S_{t+1})$</span> is a probability distribution derived over all possible values of <span class="math-container">$S_{t+1}$</span>. These will be different distributions much of the time, but their <em>expectations</em> are equal, provided the conditions of the expectation match.</p>
  
  <p>In other words, </p>
  
  <p><span class="math-container">$$G_{t+1} \neq v_*(S_{t+1})$$</span></p>
  
  <p>But</p>
  
  <p><span class="math-container">$$\mathbb{E}[G_{t+1}] = \mathbb{E}[v_*(S_{t+1})]$$</span></p>
  
  <p>. . . when the conditions that apply to the expectations on each side are compatible. The relevant conditions are </p>
  
  <ul>
  <li><p>Same initial state or state/action at given timestep <span class="math-container">$t$</span> (or you could pick any earlier timestep)</p></li>
  <li><p>Same state progression rules and reward structure (i.e. same MDP)</p></li>
  <li><p>Same policy</p></li>
  </ul>
  
  <p><strong>More details</strong></p>
  
  <p>The definition of <span class="math-container">$v(s)$</span> can be given as</p>
  
  <p><span class="math-container">$$v(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$$</span></p>
  
  <p>If you substitute step s' and index <span class="math-container">$t+1$</span> you get</p>
  
  <p><span class="math-container">$$v(s') = \mathbb{E}_\pi[G_{t+1} \mid S_{t+1} = s']$$</span></p>
  
  <p>(This is the same equation, true by definition, the substitution just shows you how it fits).</p>
  
  <p>In order to put this into equation 3.17, you need to note that:</p>
  
  <ul>
  <li><p>It is OK to substitute terms <em>inside</em> an expectation if they are equal in separate expections, amd  the conditions <span class="math-container">$c$</span> and <span class="math-container">$Y$</span> apply to both (or are irrelevant to either one or both). So if for example <span class="math-container">$\mathbb{E}_c[Z] = \mathbb{E}_c[X \mid Y]$</span> where <span class="math-container">$X$</span> and <span class="math-container">$Z$</span> are random variables, and you know <span class="math-container">$Z$</span> is independent of <span class="math-container">$Y$</span> then you can say <span class="math-container">$\mathbb{E}_c[W + 2X \mid Y] = \mathbb{E}_c[W + 2Z \mid Y]$</span> even if <span class="math-container">$X$</span> and <span class="math-container">$Z$</span> are different distributions.</p></li>
  <li><p><span class="math-container">$A_{t+1} = a'$</span> does not need to be specified because it is decided by the same <span class="math-container">$\pi$</span> in both <span class="math-container">$q(s,a)$</span> and <span class="math-container">$v(s')$</span>, making the conditions on the expectation compatible already. So the condition of following <span class="math-container">$\pi$</span> is compatible with <span class="math-container">$\mathbb{E}_\pi[G_{t+1} \mid S_{t} = s, A_{t}=a] = \mathbb{E}_\pi[v_*(S_{t+1}) \mid S_{t} = s, A_{t}=a]$</span></p></li>
  <li><p>The expectation over possible <span class="math-container">$s'$</span> in <span class="math-container">$\mathbb{E}_\pi[v_*(S_{t+1})|S_t=s, A_t=a] = \sum p(s'|s,a)v_*(s')$</span> is already implied by conditions on the original expectation that the functions are evaluating the same environment - something that is not usually shown in the notation.</p></li>
  </ul>
  
  <p>Also worth noting, in 3.17 <span class="math-container">$\pi$</span> is the optimal policy <span class="math-container">$\pi^*$</span>, but actually the equation holds for any fixed policy.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-04T20:45:36.110Z
Answers.LastActivityDate: 2020-06-05T17:08:02.957Z
Answers.LastEditDate: 2020-06-05T17:08:02.957Z
Answers.UserDisplayName: Neil Slater
Body: <p>In <a href="http://incompleteideas.net/book/bookdraft2017nov5.pdf#page=68" rel="nofollow noreferrer">equation 3.17 of Sutton and Barto's book</a>: </p>
  
  <p><span class="math-container">$$q_*(s, a)=\mathbb{E}[R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t = s, A_t = a]$$</span></p>
  
  <p><span class="math-container">$G_{t+1}$</span> here have been replaced with <span class="math-container">$v_*(S_{t+1})$</span>, but no reason has been provided for why this step has been taken. </p>
  
  <p>Can someone provide the reasoning behind why <span class="math-container">$G_{t+1}$</span> is equal to <span class="math-container">$v_*(S_{t+1})$</span>?</p>
  
Tags: <reinforcement-learning><value-functions><expectation><return><bellman-equations>
Title: Why is $G_{t+1}$ is replaced with $v_*(S_{t+1})$ in the Bellman optimality equation?
UserDisplayName: ZERO NULLS
ThreadText: # Why is $G_{t+1}$ is replaced with $v_*(S_{t+1})$ in the Bellman optimality equation?
  
  (Asked by: username_0 on 2020-06-04)
  
  In [equation 3.17 of Sutton and Barto's book](http://incompleteideas.net/book/bookdraft2017nov5.pdf#page=68):
  
  $$q\_\*(s, a)=\mathbb{E}[R\_{t+1} + \gamma v\_\*(S\_{t+1}) \mid S\_t = s, A\_t = a]$$
  
  $G\_{t+1}$ here have been replaced with $v\_\*(S\_{t+1})$, but no reason has been provided for why this step has been taken.
  
  Can someone provide the reasoning behind why $G\_{t+1}$ is equal to $v\_\*(S\_{t+1})$?
  
  **Tags:** reinforcement-learning, value-functions, expectation, return, bellman-equations
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-06-04. Score: 3 | Accepted answer
  
  > Can someone provide the reasoning behind why $G\_{t+1}$ is equal to $v\_\*(S\_{t+1})$?
  
  The two things are not usually exactly equal, because $G\_{t+1}$ is a probability distribution over all possible future returns whilst $v\_\*(S\_{t+1})$ is a probability distribution derived over all possible values of $S\_{t+1}$. These will be different distributions much of the time, but their *expectations* are equal, provided the conditions of the expectation match.
  
  In other words,
  
  $$G\_{t+1} \neq v\_\*(S\_{t+1})$$
  
  But
  
  $$\mathbb{E}[G\_{t+1}] = \mathbb{E}[v\_\*(S\_{t+1})]$$
  
  . . . when the conditions that apply to the expectations on each side are compatible. The relevant conditions are
  
  * Same initial state or state/action at given timestep $t$ (or you could pick any earlier timestep)
  * Same state progression rules and reward structure (i.e. same MDP)
  * Same policy
  
  **More details**
  
  The definition of $v(s)$ can be given as
  
  $$v(s) = \mathbb{E}\_\pi[G\_t \mid S\_t = s]$$
  
  If you substitute step s' and index $t+1$ you get
  
  $$v(s') = \mathbb{E}\_\pi[G\_{t+1} \mid S\_{t+1} = s']$$
  
  (This is the same equation, true by definition, the substitution just shows you how it fits).
  
  In order to put this into equation 3.17, you need to note that:
  
  * It is OK to substitute terms *inside* an expectation if they are equal in separate expections, amd the conditions $c$ and $Y$ apply to both (or are irrelevant to either one or both). So if for example $\mathbb{E}\_c[Z] = \mathbb{E}\_c[X \mid Y]$ where $X$ and $Z$ are random variables, and you know $Z$ is independent of $Y$ then you can say $\mathbb{E}\_c[W + 2X \mid Y] = \mathbb{E}\_c[W + 2Z \mid Y]$ even if $X$ and $Z$ are different distributions.
  * $A\_{t+1} = a'$ does not need to be specified because it is decided by the same $\pi$ in both $q(s,a)$ and $v(s')$, making the conditions on the expectation compatible already. So the condition of following $\pi$ is compatible with $\mathbb{E}\_\pi[G\_{t+1} \mid S\_{t} = s, A\_{t}=a] = \mathbb{E}\_\pi[v\_\*(S\_{t+1}) \mid S\_{t} = s, A\_{t}=a]$
  * The expectation over possible $s'$ in $\mathbb{E}\_\pi[v\_\*(S\_{t+1})|S\_t=s, A\_t=a] = \sum p(s'|s,a)v\_\*(s')$ is already implied by conditions on the original expectation that the functions are evaluating the same environment - something that is not usually shown in the notation.
  
  Also worth noting, in 3.17 $\pi$ is the optimal policy $\pi^\*$, but actually the equation holds for any fixed policy.
  
  
  ---
  
  ### Answer by username_1 on 2020-06-05. Score: 2
  
  Note that for a general policy $\pi$ we have that $q\_{\pi}(s,a) = \mathbb{E}\_{\pi}[G\_t | S\_t = s, A\_t = a]$, where in state $S\_t$ we take action $a$ and thereafter following policy $\pi$. Note that the expectation is taken with respect to the reward transition distribution $\mathbb{P}(R\_{t+1} = r, S\_{t+1} = s' | A\_t = a, S\_t = s)$ which I will denote as $p(s',r,|s,a)$.
  
  We can then rewrite the expectation as follows
  
  \begin{align} q\_{\pi}(s,a) &= \mathbb{E}\_{\pi}[G\_t | S\_t = s, A\_t = a] \\ & = \mathbb{E}\_{\pi}[R\_{t+1} + \gamma G\_{t+1} | S\_t = s, A\_t = a] \\ & = \sum\_{r,s'}p(s',r|s,a)(r + \gamma \mathbb{E}\_\pi[G\_{t+1} | S\_{t+1} = s']) \\ & = \sum\_{r,s'}p(s',r|s,a)(r + \gamma v\_{\pi}(s')) \; .
  \end{align}
  
  The key thing to note is that these two terms, $G\_{t+1}$ and $v\_{\pi}(s')$, are only equal *in expectation*, which is why in the equation you can exchange the terms because we are taking the expectation.
  
  Note that I have shown this for a general policy $\pi$ not just the optimal policy.
  
  
  ---
  
  