My first question is whether the following "implementation" of the 𝑇𝐷(0) algorithm for the first two of the above observed trajectories correct?
- $V(a)\leftarrow0 + 0.1(1+0-0)= 0.1; \quad V(b)\leftarrow0+0.1(1+0-0)=0.1$
- $V(b)\leftarrow0.1+(0.1)(1+0-0.1)= 0.19$
Your calculations for the first trajectory $(A,1,B,0)$ is incorrect for either TD or Monte Carlo. For some reason you have assigned either an immediate reward or return of $1$ to the second step, whilst in the example, it is $0$ for both the sampled return and the single-step TD target.
In addition, you quote this update rule for single-step TD:
$$V(s_{t}) \leftarrow V(s_t)+ \alpha \left[ G_{t+1}+\gamma V(s_{t+1})- V(s_t) \right]$$
. . . actually that is not the usual notation. The symbol $G_t$ is normally used to show a "return" value - a sum of rewards (often weighted by some factor, such as $\gamma$). The usual way of showing the TD update rule would be:
$$V(s_{t}) \leftarrow V(s_t)+ \alpha \left[ r_{t+1}+\gamma V(s_{t+1})- V(s_t) \right]$$
i.e. using the immediate reward. This might be a simple typo, however I am explaining this because it may behind your incorrect calculation.
The correct calculation is not very much different from yours though:
- $V(a)\leftarrow0 + 0.1(1+0-0)= 0.1; \quad V(b)\leftarrow0+0.1(0+0-0)=0.0$
- $V(b)\leftarrow0.0+(0.1)(1+0-0.0)= 0.1$
If so, why dont we use the updated value function for $V(b)$ to also update our value for $V(a)$?
You can, and would do this in either of the following situations:
In online learning, you experience a trajectory with states in order (A,B) again
In offline learning, you repeat the previous experience in batch learning or using experience replay
It is worth noting that if you take a small batch of data and repeat it again and again to update the value functions, that they will converge to values depending on your data set. That is what the slide is explaining in the lecture - highlighting the difference that TD and MonteCarlo will make when you do this. However, if that data set is a very small subsample of possible random behaviour in the environment, then you may not create an accurate value function, but instead it will be the best one that you can given the limited data. If it is easy to collect more experience, then that is often preferable.
Why dont we just use the [maximum-likelihood]-estimate immediately?
Because it is not directly useful for a value prediction task, and you would need some mechanism to use that maximum likelihood MDP model to generate value predictions. With TD, you are already in the process of making this estimate*.
You could take the existing samples, and use them to generate the parameters of an MRP (Markov Reward Process, as there are no example actions in the trajectory) based on the observations. That "best guess" MRP is your maximum likelihood MDP model, and would evaluate the same as your converged repeated TD batch over the samples.
The main difference explained by the slide is that Monte Carlo will converge to $V(a) = 1$ because the only sample with A in it has a return of 1 following state A. Whilst TD will converge to $V(a) = 1.75$, because it treats the same sample as the only instance of state progression from A - e.g state A "always" has an immediate reward of 1 then goes to state B. Both algorithms will converge to $V(b) = 0.75$.
* There are algorithms, such as Dyna-Q, which partially do this, using experience gathered so far to create a model of the environment dynamics. Sometimes this is useful and effective. However, it is not always possible or the best approach.
