Body: <p>Given equation 7.3 of <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=166" rel="nofollow noreferrer">Sutton and Barto's book</a> for convergence of TD(n): </p>
  
  <blockquote>
    <p><span class="math-container">$\max_s|\mathbb{E}_\pi[G_{t:t+n}|S_t = s] - v_\pi(s)| \leqslant \gamma^n \max_s|V_{t+n-1}(s) - v_\pi(s)|$</span></p>
  </blockquote>
  
  <p><span class="math-container">$\textbf{PROBLEM 1}$</span> : Why is this error <span class="math-container">$|\mathbb{E}_\pi[G_{t:t+n}|S_t = s] - v_\pi(s)|$</span> compared with the error <span class="math-container">$|V_{t+n-1}(s) - v_\pi(s)|$</span>.</p>
  
  <p>There can be two other logical comparisons for the convergence of algorithm(<span class="math-container">$TD(n)$</span>):</p>
  
  <p>1) If we compare and say that <span class="math-container">$V_{t+n-1}(s)$</span> is more close to <span class="math-container">$v_\pi(s)$</span> than <span class="math-container">$V_{t+n-2}(s)$</span> i.e we compare <span class="math-container">$|V_{t+n-1}(s) - v_\pi(s)|$</span> with <span class="math-container">$|V_{t+n-2}(s) - v_\pi(s)|$</span> </p>
  
  <p>2) We can also compare <span class="math-container">$|\mathbb{E}_\pi[G_{t:t+n}|S_t = s] - v_\pi(s)|$</span> with <span class="math-container">$|\mathbb{E}_\pi[V_{t+n-1}(S_t)|S_t = s] - v_\pi(s)|$</span> to show that  <span class="math-container">$\mathbb{E}_\pi[G_{t:t+n}|S_t = s]$</span> is better than <span class="math-container">$\mathbb{E}_\pi[V_{t+n-1}(S_t)|S_t = s]$</span> hence moving <span class="math-container">$V_{t+n-1}(S_t)$</span> towards <span class="math-container">$G_{t:t+n}$</span>(as done in eq 7.2) can lead to convergence.</p>
  
  <p><span class="math-container">$\textbf{PROBLEM 2}$</span> : Are the above 2 methods of comparison for testing convergence correct.</p>
  
  <p>Equations for reference:</p>
  
  <p>Eq 7.1: <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>Eq 7.2: <span class="math-container">$V_{t+n}(S_t) = V_{t+n-1}(S_t) + \alpha [G_{t:t+n} - V_{t+n-1}(S_t)]$</span></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-13T11:28:06.240Z
Comments.Text: It seems that you're asking more than a question here. I suggest you ask only one question. Regarding problem 1, what is the definition of the value function? Isn't it the expected value of the return given that you are in a certain state? Doesn't that answer your first question? If not, explain why. Note that I don't really know if this answers your question because I didn't really read that part of the book and I am just trying to understand what your question/doubt really is.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-13T11:34:33.577Z
Comments.Text: Nope because $V_{t+n-1}(s)$ is the estimate of $v_\pi(s)$ hence we should compare  error $|\mathbb{E}[V_{t+n-1}(s)] - v_\pi(s)|$ and not error $|V_{t+n-1}(s) - v_\pi(s)|$
Comments.UserDisplayName: ZERO NULLS
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-13T13:39:18.837Z
Comments.Text: Ok. I was suspecting that your doubt was about that detail. Maybe you can put your main question in the title so that to clarify what you're asking.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><temporal-difference-methods><value-iteration><expectation>
Title: Problem in understanding equation given for convergence of TD(n) algorithm
UserDisplayName: ZERO NULLS
ThreadText: # Problem in understanding equation given for convergence of TD(n) algorithm
  
  (Asked by: username_0 on 2020-06-12)
  
  Given equation 7.3 of [Sutton and Barto's book](http://incompleteideas.net/book/RLbook2020.pdf#page=166) for convergence of TD(n):
  
  > $\max\_s|\mathbb{E}\_\pi[G\_{t:t+n}|S\_t = s] - v\_\pi(s)| \leqslant \gamma^n \max\_s|V\_{t+n-1}(s) - v\_\pi(s)|$
  
  $\textbf{PROBLEM 1}$ : Why is this error $|\mathbb{E}\_\pi[G\_{t:t+n}|S\_t = s] - v\_\pi(s)|$ compared with the error $|V\_{t+n-1}(s) - v\_\pi(s)|$.
  
  There can be two other logical comparisons for the convergence of algorithm($TD(n)$):
  
  1) If we compare and say that $V\_{t+n-1}(s)$ is more close to $v\_\pi(s)$ than $V\_{t+n-2}(s)$ i.e we compare $|V\_{t+n-1}(s) - v\_\pi(s)|$ with $|V\_{t+n-2}(s) - v\_\pi(s)|$
  
  2) We can also compare $|\mathbb{E}\_\pi[G\_{t:t+n}|S\_t = s] - v\_\pi(s)|$ with $|\mathbb{E}\_\pi[V\_{t+n-1}(S\_t)|S\_t = s] - v\_\pi(s)|$ to show that $\mathbb{E}\_\pi[G\_{t:t+n}|S\_t = s]$ is better than $\mathbb{E}\_\pi[V\_{t+n-1}(S\_t)|S\_t = s]$ hence moving $V\_{t+n-1}(S\_t)$ towards $G\_{t:t+n}$(as done in eq 7.2) can lead to convergence.
  
  $\textbf{PROBLEM 2}$ : Are the above 2 methods of comparison for testing convergence correct.
  
  Equations for reference:
  
  Eq 7.1: $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})$
  
  Eq 7.2: $V\_{t+n}(S\_t) = V\_{t+n-1}(S\_t) + \alpha [G\_{t:t+n} - V\_{t+n-1}(S\_t)]$
  
  **Tags:** reinforcement-learning, temporal-difference-methods, value-iteration, expectation
  
  > **Comments:**
  > **username_1**: It seems that you're asking more than a question here. I suggest you ask only one question. Regarding problem 1, what is the definition of the value function? Isn't it the expected value of the return given that you are in a certain state? Doesn't that answer your first question? If not, explain why. Note that I don't really know if this answers your question because I didn't really read that part of the book and I am just trying to understand what your question/doubt really is.  
  > **username_0**: Nope because $V_{t+n-1}(s)$ is the estimate of $v_\pi(s)$ hence we should compare  error $|\mathbb{E}[V_{t+n-1}(s)] - v_\pi(s)|$ and not error $|V_{t+n-1}(s) - v_\pi(s)|$  
  > **username_1**: Ok. I was suspecting that your doubt was about that detail. Maybe you can put your main question in the title so that to clarify what you're asking.  
  
  ---
  
  ## 0 answers
  
  