1
$\begingroup$

I came across the $TD(0)$ algorithm from Sutton and Barto: enter image description here

Clearly, the only difference of TD methods with the MC methods is that TD method is not waiting till the end of the episode to update the $V(s)$ or $Q(s,a)$, but according to David Silver's lecture (Lecture 4- ~34:00),

enter image description here

The $TD(0)$ algorithm learns from incomplete episodes, but in the earlier algorithm we can see that the loop repeats until $s$ is terminal which mean completion of episode.

So does David Silver by learning from incomplete episodes, mean learning of $V(s)$ even when the episode is not completed? Or Did I interpret the algorithm wrong? If so what is the correct interpretation?

| improve this question | |
$\endgroup$
2
$\begingroup$

The $TD(0)$ algorithm learns from incomplete episodes, but in the earlier algorithm we can see that the loop repeats until $s$ is terminal which mean completion of episode.

In the pseudocode, you have two loops: one for each episode and one (nested) for each step of the episode. The until $S$ is terminal means that you perform the updates until you end the episode (that is, you end up in a terminal state, e.g. checkmate in the game of chess). For each step of the episode, you perform the TD(0) update.

Apparently, you're confusing two things: the fact that each episode ends in a terminal state and the fact that TD learns from incomplete information. Each episode ends in a terminal state (otherwise it would not be called an episode), but this does not mean that it collects a full rollout before updating $V$. In fact, at each step of the episode, it updates $V$.

The information in the David Slider's slide is consistent with the pseudocode. TD learns from experience because it uses the given policy $\pi$ to behave.

learning from incomplete episodes, mean learning of $V(s)$ even when the episode is not completed

Yes, essentially you're updating the value function during each step of each episode.

| improve this answer | |
$\endgroup$
  • $\begingroup$ You just stated what I already said though. I more or less wanted to clarify my idea of TD(0) (one part of that is the consistency between the 2 pics) $\endgroup$ – DuttaA Jul 11 '19 at 21:26
  • 1
    $\begingroup$ @DuttaA No, I am also saying that the information in Slider's slide is consistent with the pseudocode. Also, you say "but in the earlier algorithm we can see that the loop repeats until $s$ is terminal which mean completion of episode". I am addressing this in my answer. Apparently, you're confusing two things: the fact that each episode ends in a terminal state and the fact that TD learns from incomplete information. Each episode ends in a terminal state (otherwise it would not be called an episode), but this does not mean that it collects a full rollout before updating $V$! $\endgroup$ – nbro♦ Jul 11 '19 at 21:30
  • 1
    $\begingroup$ I don't think the edit is appropriate since I only wanted to clarify the consistency rather than understanding the concept of TD $\endgroup$ – DuttaA Jul 11 '19 at 21:40
  • $\begingroup$ @DuttaA Ok, sorry for this. When I perform an edit, my intention is to improve the post, but I realize that I might also change the original intent of the user, so, in general, feel free to rollback my edits (especially when you give me some feedback back and explain why the edit wasn't appropriate). $\endgroup$ – nbro♦ Jul 11 '19 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.