1
$\begingroup$

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

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jul 27, 2023 at 11:02
  • $\begingroup$ 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. $\endgroup$ Jul 27, 2023 at 11:10
  • $\begingroup$ I added more figures to help understand what I mean, sorry if I wasn't explaining myself well! $\endgroup$ Jul 27, 2023 at 14:09
  • $\begingroup$ I hope it's clearer now, I ended up just renaming the nodes and then referring to them in the text. $\endgroup$ Jul 27, 2023 at 14:12

1 Answer 1

1
+50
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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) $\endgroup$ Jul 27, 2023 at 18:11
  • $\begingroup$ @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. $\endgroup$ Jul 27, 2023 at 18:24
  • $\begingroup$ 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 $\endgroup$ Jul 28, 2023 at 7:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .