Answers.Body: <p>Let's start by looking at:</p>
  
  <p><span class="math-container">$$\max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert.$$</span></p>
  
  <p>We can rewrite this by plugging in the definition of <span class="math-container">$G_{t:t+n}$</span>:</p>
  
  <p><span class="math-container">\begin{aligned}
  &amp; \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert \\
  %
  =&amp; \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ R_{t + 1} + \gamma R_{t + 2} + \dots + \gamma^{n - 1} R_{t + n} + \gamma^n V_{t + n - 1}(S_{t + n}) \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert \\
  %
  =&amp; \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ R_{t:t+n} + \gamma^n V_{t + n - 1}(S_{t + n}) \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert,
  \end{aligned}</span></p>
  
  <p>where <span class="math-container">$R_{t:t+n} \doteq R_{t + 1} + \gamma R_{t + 2} + \dots + \gamma^{n - 1} R_{t + n}$</span>.</p>
  
  <p>If you go all the way back to page 58 of the book, you can see the definition of <span class="math-container">$v_{\pi}(s)$</span>:</p>
  
  <p><span class="math-container">\begin{aligned}
  v_{\pi}(s) &amp;\doteq \mathbb{E}_{\pi} \left[ \sum_{k = 0}^{\infty} \gamma^k R_{t + k + 1} \mid S_t = s \right] \\
  %
  &amp;= \mathbb{E}_{\pi} \left[ R_{t:t+n} + \gamma^n \sum_{k = 0}^{\infty} \gamma^k R_{t + n + k + 1} \mid S_t = s \right] \\
  %
  &amp;= \mathbb{E}_{\pi} \left[ R_{t:t+n} \mid S_t = s \right] + \gamma^n \mathbb{E}_{\pi} \left[ \sum_{k = 0}^{\infty} \gamma^k R_{t + n + k + 1} \mid S_t = s \right]
  \end{aligned}</span></p>
  
  <p>Using this, we can continue rewriting where we left off above:</p>
  
  <p><span class="math-container">\begin{aligned}
  &amp; \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ R_{t:t+n} + \gamma^n V_{t + n - 1}(S_{t + n}) \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert \\
  %
  =&amp; \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ \gamma^n V_{t + n - 1}(S_{t + n}) \mid S_t = s \right] - \gamma^n \mathbb{E}_{\pi} \left[ \sum_{k = 0}^{\infty} \gamma^k R_{t + n + k + 1} \mid S_t = s \right] \Bigr\rvert \\
  %
  =&amp; \gamma^n \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ V_{t + n - 1}(S_{t + n}) - \sum_{k = 0}^{\infty} \gamma^k R_{t + n + k + 1} \mid S_t = s \right] \Bigr\rvert
  \end{aligned}</span></p>
  
  <p>Because the absolute value function is <a href="https://en.wikipedia.org/wiki/Convex_function" rel="noreferrer">convex</a>, we can use <a href="https://en.wikipedia.org/wiki/Jensen%27s_inequality" rel="noreferrer">Jensen's inequality</a> to show that the absolute value of an expectation is less than or equal to the expectation of the corresponding absolute value:</p>
  
  <p><span class="math-container">$$\left| \mathbb{E} \left[ X \right] \right| \leq \mathbb{E} \left[ \left| X \right| \right].$$</span></p>
  
  <p>This means that:</p>
  
  <p><span class="math-container">\begin{aligned}
  \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} - v_{\pi}(s) \mid S_t = s \right] \Bigr\rvert &amp;\leq \gamma^n \max_s \mathbb{E}_{\pi} \left[ \Bigl\lvert V_{t + n - 1}(S_{t + n}) - \sum_{k = 0}^{\infty} \gamma^k R_{t + n + k + 1} \Bigr\rvert \mid S_t = s \right] \\
  %
  \end{aligned}</span></p>
  
  <p>Now, the important trick here is to see that:</p>
  
  <p><span class="math-container">$$\max_s \mathbb{E}_{\pi} \left[ \Bigl\lvert V_{t + n - 1}(S_{t + n}) - \sum_{k = 0}^{\infty} \gamma^k R_{t + n + k + 1} \Bigr\rvert \mid S_t = s \right] \leq \max_s \mathbb{E}_{\pi} \left[ \Bigl\lvert V_{t + n - 1}(S_{t}) - \sum_{k = 0}^{\infty} \gamma^k R_{t + k + 1} \Bigr\rvert \mid S_t = s \right]$$</span></p>
  
  <p>I'm skipping the formal steps to show that this is the case to save space, but the intuition is that:</p>
  
  <ul>
  <li>The left-hand side of this inequality involves finding an <span class="math-container">$S_t = s$</span> such that some function of <span class="math-container">$S_{t + n}$</span> is maximized, whereas the right-hand side involves finding an <span class="math-container">$S_t = s$</span> such that exactly the same function of <span class="math-container">$S_{t}$</span> is maximized.</li>
  <li>In the left-hand side, selecting an <span class="math-container">$S_t = s$</span> implicitly induces a probability distribution over multiple possible states <span class="math-container">$S_{t + n}$</span>, given by <span class="math-container">$S_t$</span>, the environment's transition dynamics, and the policy <span class="math-container">$\pi$</span>. Intuitively, this is more "restrictive" for the <span class="math-container">$\max$</span> operator, it does not have the "freedom" to directly select a single state <span class="math-container">$S_{t + n}$</span> such that the function of <span class="math-container">$S_{t + n}$</span> is maximized. The right-hand side is free to choose any single state <span class="math-container">$S_t = s$</span> such that <span class="math-container">$S_t$</span> in the right-hand side were equal to an "optimal" <span class="math-container">$S_{t+n}$</span> on the left-hand side, but it is also free to make even better choices which might never be uniquely reachable after <span class="math-container">$n$</span> steps on the left-hand side.</li>
  </ul>
  
  <p>We can use this to rewrite the previous inequality we had (where we might be making the right-hand side a bit bigger than it was, but that's fine, it already was an upper bound anyway so that inequality will still hold):</p>
  
  <p><span class="math-container">\begin{aligned}
  \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} - v_{\pi}(s) \mid S_t = s \right] \Bigr\rvert &amp;\leq \gamma^n \max_s \mathbb{E}_{\pi} \left[ \Bigl\lvert V_{t + n - 1}(S_{t}) - \sum_{k = 0}^{\infty} \gamma^k R_{t + k + 1} \Bigr\rvert \mid S_t = s \right] \\
  %
  &amp;= \gamma^n \max_s \mathbb{E}_{\pi} \left[ \Bigl\lvert V_{t + n - 1}(S_{t}) - v_{\pi}(s) \Bigr\rvert \mid S_t = s \right].
  \end{aligned}</span></p>
  
  <p>After this rewriting we've got a hidden <span class="math-container">$\mathbb{E}_{\pi}$</span> "inside" another <span class="math-container">$\mathbb{E}_{\pi}$</span> (because the definition of <span class="math-container">$v_{\pi}(s)$</span> contains an <span class="math-container">$\mathbb{E}_{\pi}$</span>), which I suppose is kind of ugly... but mathematically meaningless.</p>
  
  <p>The maximum of a random variable is an upper bound on the expectation of that random variable, so we can get rid of the expectation in the right-hand side (again potentially increasing the right-hand side, which again is still fine since it's already an upper bound anyway):</p>
  
  <p><span class="math-container">\begin{aligned}
  \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} - v_{\pi}(s) \mid S_t = s \right] \Bigr\rvert &amp;\leq \gamma^n \max_s \Bigl\lvert V_{t + n - 1}(s) - v_{\pi}(s) \Bigr\rvert,
  \end{aligned}</span></p>
  
  <p>which we can finally rewrite to Equation (7.3) in the book by moving the subtraction of <span class="math-container">$v_{\pi}(s)$</span> outside of the expectation on the left-hand side of the inequality (which is fine because, as I already mentioned above, the definition of <span class="math-container">$v_{\pi}(s)$</span> itself contains another <span class="math-container">$\mathbb{E}_{\pi}$</span> anyway).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-18T09:13:10.397Z
Answers.Text: Your bullet points explaining the "trick" make intuitive sense. Could you provide a link to someone showing the formal steps?
Answers.UserDisplayName: Philip Raeisghasem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-18T19:18:00.933Z
Answers.Text: @PhilipRaeisghasem I don't know of any such links by heart, so can't provide one, sorry :(
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-18T19:50:23.123Z
Answers.Text: I'd argue that, if it's that hard to find this information, then including it in the post would greatly increase the post's value. Or maybe as a separate, linked question?
Answers.UserDisplayName: Philip Raeisghasem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-18T20:23:01.803Z
Answers.Text: @PhilipRaeisghasem Absolutely, either would be fine... maybe separate question better, since this one's already fairly long. I'm currently working towards a paper submission deadline though, so I really don't personally feel like working out the math and writing it all down any time soon.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-29T07:50:09.277Z
Answers.Text: Can we just say that s_t+1 is a subset of s therefore its max over s_t+1 must <= max over s?
Answers.UserDisplayName: Phizaz
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-29T08:15:20.570Z
Answers.Text: @Phizaz Hmmm not exactly. Close to that, I'd say "given a completely free, unrestricted choice for $S_t$, the set of possible states $S_{t+n}$ is a subset of the set of possible states $S_t$". Very often it will not be a proper subset though, very often they'll be equal. But even then, a very important other point is that the **probability distributions** over those sets will be different. When the choice of $S_t$ is unrestricted, you can assign full probability mass to whichever is "best". Even if that best state may still be possible for $S_{t+n}$, it may no longer have full probability mass
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-30T12:59:05.470Z
Answers.Text: @DennisSoemers I agree. However, will we not be able to prove without the probability mass argument?
Answers.UserDisplayName: Phizaz
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-30T13:24:33.780Z
Answers.Text: @Phizaz Ah yes I think you're completely right. Intuitively it didn't "feel" right to me to omit that... but I guess math doesn't care about my feelings :)
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-30T01:20:34.550Z
Answers.Text: how to intuitively understand the error reduction property? how does this guarantee the convergence?
Answers.UserDisplayName: FantasticAI
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-09T10:35:59.460Z
Answers.LastActivityDate: 2019-03-18T09:27:54.243Z
Answers.LastEditDate: 2019-03-18T09:27:54.243Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>In section 7.1 (about the n-step bootstrapping) of the book <em>Reinforcement Learning: An Introduction</em> (2nd edition), by Andrew Barto and Richard S. Sutton, the authors write about what they call the "n-step return error reduction property":</p>
  
  <p><a href="https://i.sstatic.net/BUSZM.png" rel="noreferrer"><img src="https://i.sstatic.net/BUSZM.png" alt="enter image description here"></a></p>
  
  <p>But they don't prove it. I was thinking it should not be too hard but how can we show this? I was thinking of using the definition of n-step return (eq. 7.1 on previous page):</p>
  
  <p><span class="math-container">$$G_{t:t+n} = R_{t+1} + \gamma*R_{t+2} + ... + \gamma^{n-1}*R_{t+n} + \gamma^{n}*V_{t+n-1}(S_{t+n})$$</span></p>
  
  <p>Because then this has the <span class="math-container">$V_{t+n-1}$</span> in it already. But in the definition above of the n-step return it uses <span class="math-container">$V_{t+n-1}(S_{t+n})$</span> but on the right side of the inequality (7.3) that we want to prove it is just little s <span class="math-container">$V_{t+n-1}(s)$</span> ? So kind of confused here which state s it is using? And then I guess after this probably pull out a <span class="math-container">$\gamma^{n}$</span> term or something, how should we go from here?</p>
  
  <p>This is the newest Sutton Barto book (book page 144, equation 7.3):
  <a href="https://drive.google.com/file/d/1opPSz5AZ_kVa1uWOdOiveNiBFiEOHjkG/view" rel="noreferrer">https://drive.google.com/file/d/1opPSz5AZ_kVa1uWOdOiveNiBFiEOHjkG/view</a></p>
  
Tags: <reinforcement-learning><q-learning><math><proofs><sutton-barto>
Title: How do we prove the n-step return error reduction property?
UserDisplayName: 123learn
ThreadText: # How do we prove the n-step return error reduction property?
  
  (Asked by: username_0 on 2018-12-08)
  
  In section 7.1 (about the n-step bootstrapping) of the book *Reinforcement Learning: An Introduction* (2nd edition), by Andrew Barto and Richard S. Sutton, the authors write about what they call the "n-step return error reduction property":
  
  [![enter image description here](https://i.sstatic.net/BUSZM.png)](https://i.sstatic.net/BUSZM.png)
  
  But they don't prove it. I was thinking it should not be too hard but how can we show this? I was thinking of using the definition of n-step return (eq. 7.1 on previous page):
  
  $$G\_{t:t+n} = R\_{t+1} + \gamma\*R\_{t+2} + ... + \gamma^{n-1}\*R\_{t+n} + \gamma^{n}\*V\_{t+n-1}(S\_{t+n})$$
  
  Because then this has the $V\_{t+n-1}$ in it already. But in the definition above of the n-step return it uses $V\_{t+n-1}(S\_{t+n})$ but on the right side of the inequality (7.3) that we want to prove it is just little s $V\_{t+n-1}(s)$ ? So kind of confused here which state s it is using? And then I guess after this probably pull out a $\gamma^{n}$ term or something, how should we go from here?
  
  This is the newest Sutton Barto book (book page 144, equation 7.3):
  <https://drive.google.com/file/d/1opPSz5AZ_kVa1uWOdOiveNiBFiEOHjkG/view>
  
  **Tags:** reinforcement-learning, q-learning, math, proofs, sutton-barto
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-12-09. Score: 10
  
  Let's start by looking at:
  
  $$\max\_s \Bigl\lvert \mathbb{E}\_{\pi} \left[ G\_{t:t+n} \mid S\_t = s \right] - v\_{\pi}(s) \Bigr\rvert.$$
  
  We can rewrite this by plugging in the definition of $G\_{t:t+n}$:
  
  \begin{aligned}
  & \max\_s \Bigl\lvert \mathbb{E}\_{\pi} \left[ G\_{t:t+n} \mid S\_t = s \right] - v\_{\pi}(s) \Bigr\rvert \\
  %
  =& \max\_s \Bigl\lvert \mathbb{E}\_{\pi} \left[ R\_{t + 1} + \gamma R\_{t + 2} + \dots + \gamma^{n - 1} R\_{t + n} + \gamma^n V\_{t + n - 1}(S\_{t + n}) \mid S\_t = s \right] - v\_{\pi}(s) \Bigr\rvert \\
  %
  =& \max\_s \Bigl\lvert \mathbb{E}\_{\pi} \left[ R\_{t:t+n} + \gamma^n V\_{t + n - 1}(S\_{t + n}) \mid S\_t = s \right] - v\_{\pi}(s) \Bigr\rvert,
  \end{aligned}
  
  where $R\_{t:t+n} \doteq R\_{t + 1} + \gamma R\_{t + 2} + \dots + \gamma^{n - 1} R\_{t + n}$.
  
  If you go all the way back to page 58 of the book, you can see the definition of $v\_{\pi}(s)$:
  
  \begin{aligned}
  v\_{\pi}(s) &\doteq \mathbb{E}\_{\pi} \left[ \sum\_{k = 0}^{\infty} \gamma^k R\_{t + k + 1} \mid S\_t = s \right] \\
  %
  &= \mathbb{E}\_{\pi} \left[ R\_{t:t+n} + \gamma^n \sum\_{k = 0}^{\infty} \gamma^k R\_{t + n + k + 1} \mid S\_t = s \right] \\
  %
  &= \mathbb{E}\_{\pi} \left[ R\_{t:t+n} \mid S\_t = s \right] + \gamma^n \mathbb{E}\_{\pi} \left[ \sum\_{k = 0}^{\infty} \gamma^k R\_{t + n + k + 1} \mid S\_t = s \right]
  \end{aligned}
  
  Using this, we can continue rewriting where we left off above:
  
  \begin{aligned}
  & \max\_s \Bigl\lvert \mathbb{E}\_{\pi} \left[ R\_{t:t+n} + \gamma^n V\_{t + n - 1}(S\_{t + n}) \mid S\_t = s \right] - v\_{\pi}(s) \Bigr\rvert \\
  %
  =& \max\_s \Bigl\lvert \mathbb{E}\_{\pi} \left[ \gamma^n V\_{t + n - 1}(S\_{t + n}) \mid S\_t = s \right] - \gamma^n \mathbb{E}\_{\pi} \left[ \sum\_{k = 0}^{\infty} \gamma^k R\_{t + n + k + 1} \mid S\_t = s \right] \Bigr\rvert \\
  %
  =& \gamma^n \max\_s \Bigl\lvert \mathbb{E}\_{\pi} \left[ V\_{t + n - 1}(S\_{t + n}) - \sum\_{k = 0}^{\infty} \gamma^k R\_{t + n + k + 1} \mid S\_t = s \right] \Bigr\rvert
  \end{aligned}
  
  Because the absolute value function is [convex](https://en.wikipedia.org/wiki/Convex_function), we can use [Jensen's inequality](https://en.wikipedia.org/wiki/Jensen%27s_inequality) to show that the absolute value of an expectation is less than or equal to the expectation of the corresponding absolute value:
  
  $$\left| \mathbb{E} \left[ X \right] \right| \leq \mathbb{E} \left[ \left| X \right| \right].$$
  
  This means that:
  
  \begin{aligned}
  \max\_s \Bigl\lvert \mathbb{E}\_{\pi} \left[ G\_{t:t+n} - v\_{\pi}(s) \mid S\_t = s \right] \Bigr\rvert &\leq \gamma^n \max\_s \mathbb{E}\_{\pi} \left[ \Bigl\lvert V\_{t + n - 1}(S\_{t + n}) - \sum\_{k = 0}^{\infty} \gamma^k R\_{t + n + k + 1} \Bigr\rvert \mid S\_t = s \right] \\
  %
  \end{aligned}
  
  Now, the important trick here is to see that:
  
  $$\max\_s \mathbb{E}\_{\pi} \left[ \Bigl\lvert V\_{t + n - 1}(S\_{t + n}) - \sum\_{k = 0}^{\infty} \gamma^k R\_{t + n + k + 1} \Bigr\rvert \mid S\_t = s \right] \leq \max\_s \mathbb{E}\_{\pi} \left[ \Bigl\lvert V\_{t + n - 1}(S\_{t}) - \sum\_{k = 0}^{\infty} \gamma^k R\_{t + k + 1} \Bigr\rvert \mid S\_t = s \right]$$
  
  I'm skipping the formal steps to show that this is the case to save space, but the intuition is that:
  
  * The left-hand side of this inequality involves finding an $S\_t = s$ such that some function of $S\_{t + n}$ is maximized, whereas the right-hand side involves finding an $S\_t = s$ such that exactly the same function of $S\_{t}$ is maximized.
  * In the left-hand side, selecting an $S\_t = s$ implicitly induces a probability distribution over multiple possible states $S\_{t + n}$, given by $S\_t$, the environment's transition dynamics, and the policy $\pi$. Intuitively, this is more "restrictive" for the $\max$ operator, it does not have the "freedom" to directly select a single state $S\_{t + n}$ such that the function of $S\_{t + n}$ is maximized. The right-hand side is free to choose any single state $S\_t = s$ such that $S\_t$ in the right-hand side were equal to an "optimal" $S\_{t+n}$ on the left-hand side, but it is also free to make even better choices which might never be uniquely reachable after $n$ steps on the left-hand side.
  
  We can use this to rewrite the previous inequality we had (where we might be making the right-hand side a bit bigger than it was, but that's fine, it already was an upper bound anyway so that inequality will still hold):
  
  \begin{aligned}
  \max\_s \Bigl\lvert \mathbb{E}\_{\pi} \left[ G\_{t:t+n} - v\_{\pi}(s) \mid S\_t = s \right] \Bigr\rvert &\leq \gamma^n \max\_s \mathbb{E}\_{\pi} \left[ \Bigl\lvert V\_{t + n - 1}(S\_{t}) - \sum\_{k = 0}^{\infty} \gamma^k R\_{t + k + 1} \Bigr\rvert \mid S\_t = s \right] \\
  %
  &= \gamma^n \max\_s \mathbb{E}\_{\pi} \left[ \Bigl\lvert V\_{t + n - 1}(S\_{t}) - v\_{\pi}(s) \Bigr\rvert \mid S\_t = s \right].
  \end{aligned}
  
  After this rewriting we've got a hidden $\mathbb{E}\_{\pi}$ "inside" another $\mathbb{E}\_{\pi}$ (because the definition of $v\_{\pi}(s)$ contains an $\mathbb{E}\_{\pi}$), which I suppose is kind of ugly... but mathematically meaningless.
  
  The maximum of a random variable is an upper bound on the expectation of that random variable, so we can get rid of the expectation in the right-hand side (again potentially increasing the right-hand side, which again is still fine since it's already an upper bound anyway):
  
  \begin{aligned}
  \max\_s \Bigl\lvert \mathbb{E}\_{\pi} \left[ G\_{t:t+n} - v\_{\pi}(s) \mid S\_t = s \right] \Bigr\rvert &\leq \gamma^n \max\_s \Bigl\lvert V\_{t + n - 1}(s) - v\_{\pi}(s) \Bigr\rvert,
  \end{aligned}
  
  which we can finally rewrite to Equation (7.3) in the book by moving the subtraction of $v\_{\pi}(s)$ outside of the expectation on the left-hand side of the inequality (which is fine because, as I already mentioned above, the definition of $v\_{\pi}(s)$ itself contains another $\mathbb{E}\_{\pi}$ anyway).
  
  > **Comments:**
  > **username_2**: Your bullet points explaining the "trick" make intuitive sense. Could you provide a link to someone showing the formal steps?  
  > **username_1**: @PhilipRaeisghasem I don't know of any such links by heart, so can't provide one, sorry :(  
  > **username_2**: I'd argue that, if it's that hard to find this information, then including it in the post would greatly increase the post's value. Or maybe as a separate, linked question?  
  > **username_1**: @PhilipRaeisghasem Absolutely, either would be fine... maybe separate question better, since this one's already fairly long. I'm currently working towards a paper submission deadline though, so I really don't personally feel like working out the math and writing it all down any time soon.  
  > **username_3**: Can we just say that s_t+1 is a subset of s therefore its max over s_t+1 must <= max over s?  
  > **username_1**: @Phizaz Hmmm not exactly. Close to that, I'd say "given a completely free, unrestricted choice for $S_t$, the set of possible states $S_{t+n}$ is a subset of the set of possible states $S_t$". Very often it will not be a proper subset though, very often they'll be equal. But even then, a very important other point is that the **probability distributions** over those sets will be different. When the choice of $S_t$ is unrestricted, you can assign full probability mass to whichever is "best". Even if that best state may still be possible for $S_{t+n}$, it may no longer have full probability mass  
  > **username_3**: @DennisSoemers I agree. However, will we not be able to prove without the probability mass argument?  
  > **username_1**: @Phizaz Ah yes I think you're completely right. Intuitively it didn't "feel" right to me to omit that... but I guess math doesn't care about my feelings :)  
  > **username_4**: how to intuitively understand the error reduction property? how does this guarantee the convergence?  
  
  ---
  
  