Answers.Body: <blockquote>
  <p>My first question is whether the following &quot;implementation&quot; of the (0) algorithm for the first two of the above observed trajectories correct?</p>
  <ol>
  <li><span class="math-container">$V(a)\leftarrow0 + 0.1(1+0-0)= 0.1; \quad V(b)\leftarrow0+0.1(1+0-0)=0.1$</span></li>
  <li><span class="math-container">$V(b)\leftarrow0.1+(0.1)(1+0-0.1)= 0.19$</span></li>
  </ol>
  </blockquote>
  <p>Your calculations for the first trajectory <span class="math-container">$(A,1,B,0)$</span> is incorrect for either TD or Monte Carlo. For some reason you have assigned either an immediate reward or return of <span class="math-container">$1$</span> to the second step, whilst in the example, it is <span class="math-container">$0$</span> for both the sampled return and the single-step TD target.</p>
  <p>In addition, you quote this update rule for single-step TD:</p>
  <p><span class="math-container">$$V(s_{t}) \leftarrow  V(s_t)+ \alpha \left[ G_{t+1}+\gamma V(s_{t+1})- V(s_t) \right]$$</span></p>
  <p>. . . actually that is not the usual notation. The symbol <span class="math-container">$G_t$</span> is normally used to show a &quot;return&quot; value - a sum of rewards (often weighted by some factor, such as <span class="math-container">$\gamma$</span>). The usual way of showing the TD update rule would be:</p>
  <p><span class="math-container">$$V(s_{t}) \leftarrow  V(s_t)+ \alpha \left[ r_{t+1}+\gamma V(s_{t+1})- V(s_t) \right]$$</span></p>
  <p>i.e. using the immediate reward. This might be a simple typo, however I am explaining this because it may behind your incorrect calculation.</p>
  <p>The correct calculation is not very much different from yours though:</p>
  <ol>
  <li><span class="math-container">$V(a)\leftarrow0 + 0.1(1+0-0)= 0.1; \quad V(b)\leftarrow0+0.1(0+0-0)=0.0$</span></li>
  <li><span class="math-container">$V(b)\leftarrow0.0+(0.1)(1+0-0.0)= 0.1$</span></li>
  </ol>
  <blockquote>
  <p>If so, why dont we use the updated value function for <span class="math-container">$V(b)$</span> to also update our value for <span class="math-container">$V(a)$</span>?</p>
  </blockquote>
  <p>You can, and would do this in either of the following situations:</p>
  <ul>
  <li><p>In online learning, you experience a trajectory with states in order (A,B) again</p>
  </li>
  <li><p>In offline learning, you repeat the previous experience in batch learning or using experience replay</p>
  </li>
  </ul>
  <p>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.</p>
  <blockquote>
  <p>Why dont we just use the [maximum-likelihood]-estimate immediately?</p>
  </blockquote>
  <p>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*.</p>
  <p>You could take the existing samples, and use them to generate the parameters of an MRP (Markov <em>Reward</em> Process, as there are no example actions in the trajectory) based on the observations. That &quot;best guess&quot; MRP is your maximum likelihood MDP model, and would evaluate the same as your converged repeated TD batch over the samples.</p>
  <p>The main difference explained by the slide is that Monte Carlo will converge to <span class="math-container">$V(a) = 1$</span> because the only sample with A in it has a return of 1 following state A. Whilst TD will converge to <span class="math-container">$V(a) = 1.75$</span>, because it treats the same sample as the only instance of state progression from A - e.g state A &quot;always&quot; has an immediate reward of 1 then goes to state B. Both algorithms will converge to <span class="math-container">$V(b) = 0.75$</span>.</p>
  <hr />
  <p>* 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-21T20:19:28.810Z
Answers.Text: Thank you, the calculation mistake was simply a silly oversight by me but your comments  on the "repeated TD" really clarified matters!
Answers.UserDisplayName: Sebastian
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-21T20:27:36.117Z
Answers.Text: if i repeat the updates for my batch is that usually done by bootstrapping?
Answers.UserDisplayName: Sebastian
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-21T21:13:55.303Z
Answers.Text: @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.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-21T20:02:35.117Z
Answers.LastActivityDate: 2019-10-21T20:09:46.813Z
Answers.LastEditDate: 2020-06-17T09:57:20.710Z
Answers.UserDisplayName: Neil Slater
Body: <p>I have a couple of small questions about the David Silver lecture about reinforcement learning, <a href="http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MC-TD.pdf" rel="nofollow noreferrer">lecture slides</a>  (slides 23, 24). More specifically it is about the temporal difference algorithm: </p>
  
  <p><span class="math-container">$$V(s_{t}) \leftarrow  V(s_t)+ \alpha \left[ G_{t+1}+\gamma V(s_{t+1})- V(s_t) \right]$$</span></p>
  
  <p>where <span class="math-container">$\gamma$</span> is our discount rate and <span class="math-container">$\alpha $</span> the learning rate. 
  In the example given in the lecture slides we observe the following paths: </p>
  
  <p><span class="math-container">$(A,1,B,0), (B,1), (B,1), (B,1), (B,1), (B,1), (B,1), (B,0)$</span></p>
  
  <p>Meaning for the first trajectory we are in state <span class="math-container">$A$</span>, get reward <span class="math-container">$1$</span>, get to state <span class="math-container">$B$</span> and get reward <span class="math-container">$0$</span> and the game finishes. For the second trajectory we start in state <span class="math-container">$B$</span>, get reward <span class="math-container">$1$</span> and the game finishes ...</p>
  
  <p>Let`s say we initialize all states with value <span class="math-container">$0$</span> and choose <span class="math-container">$\alpha=0.1, \gamma=1$</span></p>
  
  <p>My first question is whether the following "implementation" of the <span class="math-container">$TD(0)$</span> algorithm for the first two of the above observed trajectories correct?</p>
  
  <ol>
  <li><span class="math-container">$V(a)\leftarrow0 + 0.1(1+0-0)= 0.1; \quad V(b)\leftarrow0+0.1(1+0-0)=0.1$</span></li>
  <li><span class="math-container">$V(b)\leftarrow0.1+(0.1)(1+0-0.1)= 0.19$</span> </li>
  </ol>
  
  <p>? If so, why dont we use the updated value function for <span class="math-container">$V(b)$</span> to also update our value for <span class="math-container">$V(a)$</span>?</p>
  
  <p>My third question is about the statement that </p>
  
  <blockquote>
    <p><span class="math-container">$TD(0)$</span> converges to solution of max likelihood Markov model</p>
  </blockquote>
  
  <p>this means that if we keep sampling and apply the <span class="math-container">$TD(0)$</span> 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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-21T18:42:54.373Z
Comments.Text: 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.
Comments.UserDisplayName: Brale
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-21T19:29:48.373Z
Comments.Text: @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.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-21T19:57:44.320Z
Comments.Text: @Neil Slater It would be more helpful to say what is wrong than saying that something is wrong...
Comments.UserDisplayName: Sebastian
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-21T20:03:13.410Z
Comments.Text: @Sebastion: Indeed I have. It takes time to write an answer. Your patience is appreciated :-)
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-21T20:09:13.567Z
Comments.Text: Ah right I didn't see the reward for $V(b)$ update, sorry for wrong info.
Comments.UserDisplayName: Brale
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-23T13:44:39.900Z
Comments.Text: Please, next time, **ask only one question per post**. If you have multiple questions, ask each of them in their separate post. The reason is: people, in the future, maybe have just one of your questions, but not all at the same time. Another reason is that people may know the answer to one but not all of your questions.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><temporal-difference-methods><reinforce>
Title: Confusion about temporal difference learning
UserDisplayName: Sebastian
ThreadText: # Confusion about temporal difference learning
  
  (Asked by: username_0 on 2019-10-21)
  
  I have a couple of small questions about the David Silver lecture about reinforcement learning, [lecture slides](http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MC-TD.pdf) (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?
  
  **Tags:** reinforcement-learning, temporal-difference-methods, reinforce
  > **Comments:**
  > **username_1**: 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.  
  > **username_2**: @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.  
  > **username_0**: @Neil Slater It would be more helpful to say what is wrong than saying that something is wrong...  
  > **username_2**: @Sebastion: Indeed I have. It takes time to write an answer. Your patience is appreciated :-)  
  > **username_1**: Ah right I didn't see the reward for $V(b)$ update, sorry for wrong info.  
  > **username_3**: Please, next time, **ask only one question per post**. If you have multiple questions, ask each of them in their separate post. The reason is: people, in the future, maybe have just one of your questions, but not all at the same time. Another reason is that people may know the answer to one but not all of your questions.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-10-21. Score: 4 | Accepted answer
  
  > 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.
  
  > **Comments:**
  > **username_0**: Thank you, the calculation mistake was simply a silly oversight by me but your comments  on the "repeated TD" really clarified matters!  
  > **username_0**: if i repeat the updates for my batch is that usually done by bootstrapping?  
  > **username_2**: @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.  
  
  ---
  
  