Answers.Body: <p>The second equation is correct. In TD($\lambda$), the $\lambda$ parameter can be tuned to smoothly vary between single-step updates (essentially what Sarsa does) in the case of $\lambda = 0$, and Monte-Carlo returns (using the full episode's returns) in the case of $\lambda = 1$.</p>
  
  <p>In the first equation, $\sum_{j = i}^{N - 1} \lambda^{j - i} d_i$ could be interpreted as a... summing up exactly the same temporal-difference term $d_i$ a number of times (specifically, $N - 1 - j$ times), but multiplied by a different scalar every time. I'm not sure how that could be useful in any way.</p>
  
  <p>In the second equation, $\sum_{m = i}^{N - 1} \lambda^{m - i} d_m$ can be interpreted as a weighted combination;</p>
  
  <ul>
  <li>$1 \times d_i$: this is the difference between what we predict our returns will be at time $i + 1$, and what we previously predicted our returns would be at time $i$.</li>
  <li>$+ \lambda^1 \times d_{i + 1}$: a very similar difference between two of our own predictions, now the predictions at time $i + 2$ and $i + 1$. This time the temporal-difference term is weighted by the parameter $\lambda$ (completely ignored if $\lambda = 0$, full weight if $\lambda = 1$, somewhere in between if $0 &lt; \lambda &lt; 1$).</li>
  <li>$+ \lambda^2 \times d_{i + 2}$: again a similar temporal-difference term, now again one step further into the future. Downweighted a bit more than the previous term in cases where $0 &lt; \lambda &lt; 1$.</li>
  <li>etc.</li>
  </ul>
  
  <p>For people who are familiar with temporal-difference algorithms like TD($\lambda$), sarsa($\lambda$), eligibility traces, etc. from Reinforcement Learning literature, this makes a lot more sense. The notation is still a bit different from the standard literature on algorithms like TD($\lambda$), but in fact becomes equivalent once you note that in this paper they discuss domains where there are only rewards associated with terminal states, and no intermediate rewards.</p>
  
  <p>Intuitively, what they're doing with the $\lambda$ parameter is assigning more weight (or "credit" or "importance") to short-term predictions / short-term "expectations" (in the English sense of the word, rather than the mathematical sense of the word) or observations of rewards, over long-term predictions/observations. In the extreme case of $\lambda = 0$, you completely ignore long-term predictions/observations and only propagate observed rewards very slowly, one-by-one in single steps. In the other extreme case of $\lambda = 1$, you propagate rewards observed at the end of episodes with equal weight all the way to the beginning of the episodes, through all states that you went to, giving them all equal weight for that observed reward. With $0 &lt; \lambda &lt; 1$, you choose a balance between those two extremes.</p>
  
  <hr>
  
  <p>Also note that Equation (5) in the KnightCap paper (where they similarly discuss the extreme case of $\lambda = 1$, like I did above) is incorrect if we take the first equation from your question, but is correct if we take the second equation.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-28T17:23:06.110Z
Answers.LastActivityDate: 2018-08-28T17:23:06.110Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>Of course, it's the <strong>first</strong> equation that is correct. <em>d</em> is the temporal difference, and it's the difference between the current and next state. The current state is <strong>i</strong>, and this difference needs to stay constant inside the summation loop.</p>
  
  <p>The second equation is simply a typo mistake.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-01T14:37:42.777Z
Answers.Text: If you look at giraffe paper, there is a table at page 23. That looks like 2nd equation. He is multiplying lambda with future errors.
Answers.UserDisplayName: Shihab Shahriar Khan
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-01T14:48:20.823Z
Answers.Text: @ShihabShahriar I need little more time to get to the Giraffe paper, but I still believe my answer is correct.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-28T17:24:29.777Z
Answers.Text: No it's not correct, summing up exactly the same term multiple times, with different weights (different exponents of $\lambda$), does not really seem to have any meaning to me. The second equation, a weighted combination of different temporal-difference terms, has a clear meaning.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-28T17:59:04.543Z
Answers.Text: If you think it is in fact meaningful to sum up precisely the same term multiple times (with different weights depending on $\lambda$), it would be interesting to explain that. As I see it, the first equation will simply multiply the same temporal-difference term $d_i$ **more often** for states $i$ that are **far away temporally** from the terminal state $N$; **this is exactly the opposite of what you'll want to do in practice**, because  those long-distance returns have high variance. Also, Equation (5) in the KnightCap paper would be completely incorrect if the first equation were correct.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-28T20:41:31.283Z
Answers.Text: @DennisSoemers This is an old question, I forgot everything. I need some time to digest.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-29T08:20:20.057Z
Answers.Text: @DennisSoemers I didn’t downvote u
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-29T08:22:26.500Z
Answers.Text: @DennisSoemers as soon as you posted your answer this post bumped to the homepage. Anyone can come in and vote.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-30T12:32:50.700Z
Answers.LastActivityDate: 2017-09-30T12:32:50.700Z
Answers.UserDisplayName: SmallChess
Body: <p>Notice that, in the following formula, at the very right, the term multiplied with <span class="math-container">$\lambda$</span> is <span class="math-container">$d_i$</span></p>
  
  <p><span class="math-container">$$
  w := w + \alpha \sum_{i=1}^{N-1} \nabla r(x_i^l, w) \Big \lfloor \sum_{j=i}^{N-1} \lambda^{j-i} d_i \Big \rfloor
  $$</span></p>
  
  <p>Note that <span class="math-container">$i$</span> is the index of the first sum.</p>
  
  <p>However, in the following formula, the term is <span class="math-container">$d_m$</span>, which was <span class="math-container">$d_i$</span> in the first equation.</p>
  
  <p><span class="math-container">$$
  w_j := w_j + \alpha \sum_{i=1}^{N-1} \frac{\partial r(x_i^l, w)}{\partial w_j}  \Big \lfloor \sum_{m=i}^{N-1} \lambda^{m-i} d_m \Big \rfloor
  $$</span></p>
  
  <p>Note that <span class="math-container">$m$</span> is the index of the second sum.</p>
  
  <p>In my opinion, first equation seems reasonable. The <span class="math-container">$\lambda$</span> in second one actually seems to work like discount factor.</p>
  
  <p>In another chess engine, <a href="https://arxiv.org/pdf/1509.01549.pdf" rel="nofollow noreferrer">Giraffe</a>, the author cited same paper, noted the first equation, but then proceeded on to implement second one. See also <a href="https://arxiv.org/pdf/cs/9901002.pdf" rel="nofollow noreferrer">KnightCap Paper</a>.</p>
  
Tags: <machine-learning><reinforcement-learning><game-ai>
Title: Inconsistency in TD-Leaf algorithm in KnightCap chess engine
UserDisplayName: Shihab Shahriar Khan
ThreadText: # Inconsistency in TD-Leaf algorithm in KnightCap chess engine
  
  (Asked by: username_0 on 2017-09-28)
  
  Notice that, in the following formula, at the very right, the term multiplied with $\lambda$ is $d\_i$
  
  $$
  w := w + \alpha \sum\_{i=1}^{N-1} \nabla r(x\_i^l, w) \Big \lfloor \sum\_{j=i}^{N-1} \lambda^{j-i} d\_i \Big \rfloor
  $$
  
  Note that $i$ is the index of the first sum.
  
  However, in the following formula, the term is $d\_m$, which was $d\_i$ in the first equation.
  
  $$
  w\_j := w\_j + \alpha \sum\_{i=1}^{N-1} \frac{\partial r(x\_i^l, w)}{\partial w\_j} \Big \lfloor \sum\_{m=i}^{N-1} \lambda^{m-i} d\_m \Big \rfloor
  $$
  
  Note that $m$ is the index of the second sum.
  
  In my opinion, first equation seems reasonable. The $\lambda$ in second one actually seems to work like discount factor.
  
  In another chess engine, [Giraffe](https://arxiv.org/pdf/1509.01549.pdf), the author cited same paper, noted the first equation, but then proceeded on to implement second one. See also [KnightCap Paper](https://arxiv.org/pdf/cs/9901002.pdf).
  
  **Tags:** machine-learning, reinforcement-learning, game-ai
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2018-08-28. Score: 3
  
  The second equation is correct. In TD($\lambda$), the $\lambda$ parameter can be tuned to smoothly vary between single-step updates (essentially what Sarsa does) in the case of $\lambda = 0$, and Monte-Carlo returns (using the full episode's returns) in the case of $\lambda = 1$.
  
  In the first equation, $\sum\_{j = i}^{N - 1} \lambda^{j - i} d\_i$ could be interpreted as a... summing up exactly the same temporal-difference term $d\_i$ a number of times (specifically, $N - 1 - j$ times), but multiplied by a different scalar every time. I'm not sure how that could be useful in any way.
  
  In the second equation, $\sum\_{m = i}^{N - 1} \lambda^{m - i} d\_m$ can be interpreted as a weighted combination;
  
  * $1 \times d\_i$: this is the difference between what we predict our returns will be at time $i + 1$, and what we previously predicted our returns would be at time $i$.
  * $+ \lambda^1 \times d\_{i + 1}$: a very similar difference between two of our own predictions, now the predictions at time $i + 2$ and $i + 1$. This time the temporal-difference term is weighted by the parameter $\lambda$ (completely ignored if $\lambda = 0$, full weight if $\lambda = 1$, somewhere in between if $0 < \lambda < 1$).
  * $+ \lambda^2 \times d\_{i + 2}$: again a similar temporal-difference term, now again one step further into the future. Downweighted a bit more than the previous term in cases where $0 < \lambda < 1$.
  * etc.
  
  For people who are familiar with temporal-difference algorithms like TD($\lambda$), sarsa($\lambda$), eligibility traces, etc. from Reinforcement Learning literature, this makes a lot more sense. The notation is still a bit different from the standard literature on algorithms like TD($\lambda$), but in fact becomes equivalent once you note that in this paper they discuss domains where there are only rewards associated with terminal states, and no intermediate rewards.
  
  Intuitively, what they're doing with the $\lambda$ parameter is assigning more weight (or "credit" or "importance") to short-term predictions / short-term "expectations" (in the English sense of the word, rather than the mathematical sense of the word) or observations of rewards, over long-term predictions/observations. In the extreme case of $\lambda = 0$, you completely ignore long-term predictions/observations and only propagate observed rewards very slowly, one-by-one in single steps. In the other extreme case of $\lambda = 1$, you propagate rewards observed at the end of episodes with equal weight all the way to the beginning of the episodes, through all states that you went to, giving them all equal weight for that observed reward. With $0 < \lambda < 1$, you choose a balance between those two extremes.
  
  ---
  
  Also note that Equation (5) in the KnightCap paper (where they similarly discuss the extreme case of $\lambda = 1$, like I did above) is incorrect if we take the first equation from your question, but is correct if we take the second equation.
  
  
  ---
  
  ### Answer by username_2 on 2017-09-30. Score: 0
  
  Of course, it's the **first** equation that is correct. *d* is the temporal difference, and it's the difference between the current and next state. The current state is **i**, and this difference needs to stay constant inside the summation loop.
  
  The second equation is simply a typo mistake.
  
  > **Comments:**
  > **username_0**: If you look at giraffe paper, there is a table at page 23. That looks like 2nd equation. He is multiplying lambda with future errors.  
  > **username_2**: @ShihabShahriar I need little more time to get to the Giraffe paper, but I still believe my answer is correct.  
  > **username_1**: No it's not correct, summing up exactly the same term multiple times, with different weights (different exponents of $\lambda$), does not really seem to have any meaning to me. The second equation, a weighted combination of different temporal-difference terms, has a clear meaning.  
  > **username_1**: If you think it is in fact meaningful to sum up precisely the same term multiple times (with different weights depending on $\lambda$), it would be interesting to explain that. As I see it, the first equation will simply multiply the same temporal-difference term $d_i$ **more often** for states $i$ that are **far away temporally** from the terminal state $N$; **this is exactly the opposite of what you'll want to do in practice**, because  those long-distance returns have high variance. Also, Equation (5) in the KnightCap paper would be completely incorrect if the first equation were correct.  
  > **username_2**: @DennisSoemers This is an old question, I forgot everything. I need some time to digest.  
  > **username_2**: @DennisSoemers I didn’t downvote u  
  > **username_2**: @DennisSoemers as soon as you posted your answer this post bumped to the homepage. Anyone can come in and vote.  
  
  ---
  
  