3
$\begingroup$

I have a couple of small questions about the David Silver lecture about reinforcement learning, lecture slides (slides 23, 24). More specifically it is about the temporal difference algorithm:

$$V(s_{t}) \leftarrow V(s_t)+ \alpha \left[ G_{t+1}+\gamma V(s_{t+1})- V(s_t) \right]$$

where $\gamma$ is our discount rate and $\alpha $ the learning rate. In the example given in the lecture slides we observe the following paths:

$(A,1,B,0), (B,1), (B,1), (B,1), (B,1), (B,1), (B,1), (B,0)$

Meaning for the first trajectory we are in state $A$, get reward $1$, get to state $B$ and get reward $0$ and the game finishes. For the second trajectory we start in state $B$, get reward $1$ and the game finishes ...

Let`s say we initialize all states with value $0$ and choose $\alpha=0.1, \gamma=1$

My first question is whether the following "implementation" of the $TD(0)$ algorithm for the first two of the above observed trajectories correct?

  1. $V(a)\leftarrow0 + 0.1(1+0-0)= 0.1; \quad V(b)\leftarrow0+0.1(1+0-0)=0.1$
  2. $V(b)\leftarrow0.1+(0.1)(1+0-0.1)= 0.19$

? If so, why dont we use the updated value function for $V(b)$ to also update our value for $V(a)$?

My third question is about the statement that

$TD(0)$ converges to solution of max likelihood Markov model

this means that if we keep sampling and apply the $TD(0)$ algorithm that the thereby obtained solution converges towards the ML-estimate of that sample using the Markov Model? Why dont we just use the ML-estimate immediately?

$\endgroup$
  • 1
    $\begingroup$ You should be updating $V(s_t)$ not $V(s_{t+1})$, but your calculations seem correct. Why not update $V(b)$ with $V(a)$ ? This is only one type of the algorithm, you could use Monte Carlo algorithms to produce something similar. The idea is that you will visit each state many times not only once. Why not use ML-estimate ? Well maybe you could if you know how, there are more ways to solve a problem, this is only one way, use the method that you prefer. $\endgroup$ – Brale_ Oct 21 at 18:42
  • $\begingroup$ @Brale_ Your comment is quite close to being an answer, you should consider making it one as opposed to writing an almost-answer as a comment. However, I do disagree with you - the OP's maths is wrong IMO. $\endgroup$ – Neil Slater Oct 21 at 19:29
  • $\begingroup$ @Neil Slater It would be more helpful to say what is wrong than saying that something is wrong... $\endgroup$ – Sebastian Oct 21 at 19:57
  • 1
    $\begingroup$ @Sebastion: Indeed I have. It takes time to write an answer. Your patience is appreciated :-) $\endgroup$ – Neil Slater Oct 21 at 20:03
  • $\begingroup$ Thanks a lot! :) $\endgroup$ – Sebastian Oct 21 at 20:04
3
$\begingroup$

My first question is whether the following "implementation" of the 𝑇𝐷(0) algorithm for the first two of the above observed trajectories correct?

  1. $V(a)\leftarrow0 + 0.1(1+0-0)= 0.1; \quad V(b)\leftarrow0+0.1(1+0-0)=0.1$
  2. $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:

  1. $V(a)\leftarrow0 + 0.1(1+0-0)= 0.1; \quad V(b)\leftarrow0+0.1(0+0-0)=0.0$
  2. $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.

$\endgroup$
  • $\begingroup$ Thank you, the calculation mistake was simply a silly oversight by me but your comments on the "repeated TD" really clarified matters! $\endgroup$ – Sebastian Oct 21 at 20:19
  • $\begingroup$ if i repeat the updates for my batch is that usually done by bootstrapping? $\endgroup$ – Sebastian Oct 21 at 20:27
  • $\begingroup$ @Sebastian: If you repeat the updates for the batch, you run them just like the online updates. So, yes with TD learning you use the same bootstrapping based TD update rule. The only difference is that you don't really choose an action and take a step in the environment, just loop around the algorithm as if you had. $\endgroup$ – Neil Slater Oct 21 at 21:13

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.