Given equation 7.3 of Sutton and Barto's book 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)]$

  • $\begingroup$ 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. $\endgroup$
    – nbro
    Commented Jun 13, 2020 at 11:28
  • $\begingroup$ 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)|$ $\endgroup$
    Commented Jun 13, 2020 at 11:34
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Commented Jun 13, 2020 at 13:39


You must log in to answer this question.