Answers.Body: <p>In temporal difference learning, we do not wait to collect the full trajectory before performing backups. That means at the time of performing the backup, we may be &quot;wrong&quot;. In fact that is the most common situation for all initial backups (ours and our opponent's).</p>
  <p>On the next pass through however, the successor states will have also been updated by the opponent's choice. So we may correctly predict their decision, and get a more accurate backup. That is, providing they were correct in their decision. The opponent could be facing a very similar situation. We don't actually know that the later state information they worked from is a better prediction of who will win - it is more likely to be in general, as winner data backs up from game end states - but it is not guaranteed.</p>
  <p>Using a longer &quot;real&quot; trajectory to decide what to backup doesn't fix things - although it may capture actual results, those rely on too many interim poorly-informed choices (unless you have capacity to perform a full tree search), so there is a lot of variance, whlst TD learning swaps that variance for bias. Both the bias (in TD learning) and variance (in e.g. Monte Carlo learning) reduce over time as more data is collected. In practice TD learning often performs better - although for game playing that may depend a lot on the type of game.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-27T18:11:21.833Z
Answers.Text: Ohh, so the backup is performed at the same time as we are performing the action? Does that mean that for "early actions" in the game, during the first episodes, we basically change the node values randomly since we only get real information on the states close to the only state giving us a reward (the end one, +1 if win, -1 if loss)? (Obviously in Monte-Carlo it's different, I'm talking about TD learning)
Answers.UserDisplayName: FluidMechanics Potential Flows
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-27T18:24:48.547Z
Answers.Text: @FluidMechanicsPotentialFlows Yes the most basic unaltered TD learning ends up doing a lot of zero updates in the first games, provided the reward system is simply +1 for win -1 for loss.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-28T07:16:57.803Z
Answers.Text: No problem. The delay is on purpose. There may yet be a better answer for you, so you should wait as long as you want, up to the expiry
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-27T17:17:23.323Z
Answers.LastActivityDate: 2023-07-27T17:28:47.137Z
Answers.LastEditDate: 2023-07-27T17:28:47.137Z
Answers.UserDisplayName: Neil Slater
Body: <p>I'm currently watching a RL course by David Silver and he explains the update of TD Leaf, here is the slide:</p>
  <p><a href="https://i.sstatic.net/Iz3Nb.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Iz3Nb.png" alt="enter image description here" /></a></p>
  <p>He says that if, at the next turn (after we played red and the opponent played blue) instead of the blue node the opponent played node number 1 (because the next minimax search indicated we were wrong at state St because we did not look &quot;far enough&quot;), we then pick the one in the bottom right corner for example (node number 4), we still update the blue node value on the left diagram and not the node next to the blue node (node number 1).</p>
  <p>The explanation follows a question from a student and is at this timestep:</p>
  <p><a href="https://youtu.be/kZ_AUmFcZtk?t=4346" rel="nofollow noreferrer">https://youtu.be/kZ_AUmFcZtk?t=4346</a></p>
  <p>I'm struggling to understand why we wouldn't update the value of the node next to the blue one (node number 1), since that's the action that ended up being selected.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-07-27T11:02:14.237Z
Comments.Text: I think you should indicate on a copy of the diagram which alternative nodes you are referring to. The term "next to" is ambiguous, and so is "the blue node" (there are two shown). I don't know which nodes you mean, nor in which side of diagram you are asking about changes.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-07-27T11:10:56.663Z
Comments.Text: I watched the video, but the screen is washed out on it, and it is really unclear which nodes are being discussed between the lecturer and student in that clip, even when looking a clear version of the diagram separately.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-07-27T14:09:20.153Z
Comments.Text: I added more figures to help understand what I mean, sorry if I wasn't explaining myself well!
Comments.UserDisplayName: FluidMechanics Potential Flows
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-07-27T14:12:40.390Z
Comments.Text: I hope it's clearer now, I ended up just renaming the nodes and then referring to them in the text.
Comments.UserDisplayName: FluidMechanics Potential Flows
Tags: <reinforcement-learning><temporal-difference-methods>
Title: TD Leaf value function update
UserDisplayName: FluidMechanics Potential Flows
ThreadText: # TD Leaf value function update
  
  (Asked by: username_0 on 2023-05-23)
  
  I'm currently watching a RL course by David Silver and he explains the update of TD Leaf, here is the slide:
  
  [![enter image description here](https://i.sstatic.net/Iz3Nb.png)](https://i.sstatic.net/Iz3Nb.png)
  
  He says that if, at the next turn (after we played red and the opponent played blue) instead of the blue node the opponent played node number 1 (because the next minimax search indicated we were wrong at state St because we did not look "far enough"), we then pick the one in the bottom right corner for example (node number 4), we still update the blue node value on the left diagram and not the node next to the blue node (node number 1).
  
  The explanation follows a question from a student and is at this timestep:
  
  <https://youtu.be/kZ_AUmFcZtk?t=4346>
  
  I'm struggling to understand why we wouldn't update the value of the node next to the blue one (node number 1), since that's the action that ended up being selected.
  
  **Tags:** reinforcement-learning, temporal-difference-methods
  
  > **Comments:**
  > **username_1**: I think you should indicate on a copy of the diagram which alternative nodes you are referring to. The term "next to" is ambiguous, and so is "the blue node" (there are two shown). I don't know which nodes you mean, nor in which side of diagram you are asking about changes.  
  > **username_1**: I watched the video, but the screen is washed out on it, and it is really unclear which nodes are being discussed between the lecturer and student in that clip, even when looking a clear version of the diagram separately.  
  > **username_0**: I added more figures to help understand what I mean, sorry if I wasn't explaining myself well!  
  > **username_0**: I hope it's clearer now, I ended up just renaming the nodes and then referring to them in the text.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-07-27. Score: 1 | Accepted answer
  
  In temporal difference learning, we do not wait to collect the full trajectory before performing backups. That means at the time of performing the backup, we may be "wrong". In fact that is the most common situation for all initial backups (ours and our opponent's).
  
  On the next pass through however, the successor states will have also been updated by the opponent's choice. So we may correctly predict their decision, and get a more accurate backup. That is, providing they were correct in their decision. The opponent could be facing a very similar situation. We don't actually know that the later state information they worked from is a better prediction of who will win - it is more likely to be in general, as winner data backs up from game end states - but it is not guaranteed.
  
  Using a longer "real" trajectory to decide what to backup doesn't fix things - although it may capture actual results, those rely on too many interim poorly-informed choices (unless you have capacity to perform a full tree search), so there is a lot of variance, whlst TD learning swaps that variance for bias. Both the bias (in TD learning) and variance (in e.g. Monte Carlo learning) reduce over time as more data is collected. In practice TD learning often performs better - although for game playing that may depend a lot on the type of game.
  
  > **Comments:**
  > **username_0**: Ohh, so the backup is performed at the same time as we are performing the action? Does that mean that for "early actions" in the game, during the first episodes, we basically change the node values randomly since we only get real information on the states close to the only state giving us a reward (the end one, +1 if win, -1 if loss)? (Obviously in Monte-Carlo it's different, I'm talking about TD learning)  
  > **username_1**: @username_0 Yes the most basic unaltered TD learning ends up doing a lot of zero updates in the first games, provided the reward system is simply +1 for win -1 for loss.  
  > **username_1**: No problem. The delay is on purpose. There may yet be a better answer for you, so you should wait as long as you want, up to the expiry  
  
  ---
  
  