Answers.Body: <p>The derivation is a result of manipulating sums.
  Starting with
  <span class="math-container">$$w=w+\sum_{t=1}^{m}\alpha\sum_{k=t}^{m}(P_{k+1}-P_{k})\nabla_{w}P_{t}$$</span>
  we focus on the double sum where <span class="math-container">$m=3$</span>. Then,</p>
  <p><span class="math-container">$$\sum_{t=1}^{3}\alpha\sum_{k=t}^{3}(P_{k+1}-P_{k})\nabla_{w}P_{t}$$</span>
  <span class="math-container">$$=\alpha(P_{2}-P_{1})\nabla_{w}P_{1}+\alpha(P_{3}-
  P_{2})\nabla_{w}P_{1}+\alpha(P_{4}-P_{3})\nabla_{w}P_{1}+\alpha(P_{3}-P_{2})\nabla_{w}P_{2}+\alpha(P_{4}-P_{3})\nabla_{w}P_{2}+\alpha(P_{4}-P_{3})\nabla_{w}P_{3}$$</span>
  Rearranging gives us
  <span class="math-container">$$\alpha(P_{2}-P_{1})\nabla_{w}P_{1}+\alpha(P_{3}-P_{2})\nabla_{w}(P_{1}+P_{2})+\alpha(P_{4}-P_{3})\nabla_{w}(P_{1}+P_{2}+P_{3})$$</span>
  which is the same as (leave it to you)
  <span class="math-container">$$\alpha\sum_{k=1}^{3}\sum_{t=1}^{k}(P_{k+1}-P_{k})\nabla_{w}P_{t}$$</span>
  Trivial algebra and separating the sums gives us (1) and (2). Any further doubts are welcome.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-24T22:31:56.950Z
Answers.LastActivityDate: 2024-05-24T22:34:00.737Z
Answers.LastEditDate: 2024-05-24T22:34:00.737Z
Answers.UserDisplayName: faunedepeluse
Body: <p>I'm reading Sutton's &quot;Learning to Predict by the Methods of Temporal Differences&quot; and I'm getting hung up on a derivation (p. 14).</p>
  <p>We are considering (observation-sequence, outcome) pairs. <span class="math-container">$[x_1, x_2, ... x_m]$</span> denote each observation where the subscript indicates the time step. <span class="math-container">$z$</span> is the final, actual outcome following the sequence of time-indexed observations; ie. we proceed in time with <span class="math-container">$[x_1, x_2, ... x_m, z]$</span>.</p>
  <p><span class="math-container">$P_t$</span> is the perceptron's prediction of the output at that time. In our case, for the Widrow-Hoff (linear learning method), we have that <span class="math-container">$$P_t = w^{t}x_t$$</span> where <span class="math-container">$w$</span> represents the weights of each edge in the perceptron.</p>
  <p>For our problem we are trying to update the weights of <span class="math-container">$w$</span> with each new observation <span class="math-container">$x_t$</span>. As is customary we reassign the weights with:</p>
  <p><span class="math-container">$$ w = w + \sum_{t=1}^{m}\Delta w_t $$</span>
  the equation for <span class="math-container">$\Delta w_t$</span> is given as <span class="math-container">$$\Delta w_t = \alpha (z - P_t) \nabla _w P_t$$</span>
  Where <span class="math-container">$\alpha$</span> is the learning rate and the rightmost term is the gradient with respect to timestep.</p>
  <p>The derivation begins by letting our actual targe value <span class="math-container">$z = P_{m+t}$</span> and then rewriting the term <span class="math-container">$(z - P_t)$</span> in the previous equation as <span class="math-container">$\sum_{k=t}^{m}(P_{k+1} - P_{k})$</span>. It is easy to plug in terms to see that this is a telescoping sum that reduces to <span class="math-container">$(z - P_t)$</span>.</p>
  <p>The next logical step is to plug this expression into one of our previous equations:
  <span class="math-container">$$ w = w + \sum_{t=1}^{m}\Delta w_t $$</span>
  <span class="math-container">$$ = w + \sum_{t=1}^{m} \alpha \sum_{k=t}^{m}(P_{k+1} - P_{k}) \nabla _w P_t$$</span></p>
  <p>But the next two steps of the derivation puzzle me. They are what I'm asking about and the reason I can't understand the derviation. I don't see how terms are being rearranged:</p>
  <p><span class="math-container">$$ w + \sum_{k=1}^{m} \alpha \sum_{t=1}^{k}(P_{k+1} - P_{k}) \nabla _w P_t;    (1)$$</span>
  <span class="math-container">$$ w + \sum_{t=1}^{m} \alpha (P_{t+1} - P_{t})\sum_{k=1}^{t} \nabla _w P_k;    (2)$$</span></p>
  <p>And then we see
  <span class="math-container">$$ \Delta w_t = \alpha (P_{t+1} - P_{t})\sum_{k=1}^{t} \nabla _w P_k$$</span></p>
  <p>I have tried to expand out the terms to see what is going on under the hood, but I do not have a good grip on the interchangeability of t and k. I also especially don't understand how to solve the inner summation from (1) to (2). Any help would be greatly appreciated as this is the main roadblock I am encountering in fully understanding the algorithm. Thank you very much!</p>
  
Tags: <reinforcement-learning><machine-learning><temporal-difference-methods><multilayer-perceptrons>
Title: Proof that Temporal-Difference TD(1) is Equivalent to Widrow-Hoff
UserDisplayName: Matheo Xenakis
ThreadText: # Proof that Temporal-Difference TD(1) is Equivalent to Widrow-Hoff
  
  (Asked by: username_0 on 2024-05-20)
  
  I'm reading Sutton's "Learning to Predict by the Methods of Temporal Differences" and I'm getting hung up on a derivation (p. 14).
  
  We are considering (observation-sequence, outcome) pairs. $[x\_1, x\_2, ... x\_m]$ denote each observation where the subscript indicates the time step. $z$ is the final, actual outcome following the sequence of time-indexed observations; ie. we proceed in time with $[x\_1, x\_2, ... x\_m, z]$.
  
  $P\_t$ is the perceptron's prediction of the output at that time. In our case, for the Widrow-Hoff (linear learning method), we have that $$P\_t = w^{t}x\_t$$ where $w$ represents the weights of each edge in the perceptron.
  
  For our problem we are trying to update the weights of $w$ with each new observation $x\_t$. As is customary we reassign the weights with:
  
  $$ w = w + \sum\_{t=1}^{m}\Delta w\_t $$
  the equation for $\Delta w\_t$ is given as $$\Delta w\_t = \alpha (z - P\_t) \nabla \_w P\_t$$
  Where $\alpha$ is the learning rate and the rightmost term is the gradient with respect to timestep.
  
  The derivation begins by letting our actual targe value $z = P\_{m+t}$ and then rewriting the term $(z - P\_t)$ in the previous equation as $\sum\_{k=t}^{m}(P\_{k+1} - P\_{k})$. It is easy to plug in terms to see that this is a telescoping sum that reduces to $(z - P\_t)$.
  
  The next logical step is to plug this expression into one of our previous equations:
  $$ w = w + \sum\_{t=1}^{m}\Delta w\_t $$
  $$ = w + \sum\_{t=1}^{m} \alpha \sum\_{k=t}^{m}(P\_{k+1} - P\_{k}) \nabla \_w P\_t$$
  
  But the next two steps of the derivation puzzle me. They are what I'm asking about and the reason I can't understand the derviation. I don't see how terms are being rearranged:
  
  $$ w + \sum\_{k=1}^{m} \alpha \sum\_{t=1}^{k}(P\_{k+1} - P\_{k}) \nabla \_w P\_t; (1)$$
  $$ w + \sum\_{t=1}^{m} \alpha (P\_{t+1} - P\_{t})\sum\_{k=1}^{t} \nabla \_w P\_k; (2)$$
  
  And then we see
  $$ \Delta w\_t = \alpha (P\_{t+1} - P\_{t})\sum\_{k=1}^{t} \nabla \_w P\_k$$
  
  I have tried to expand out the terms to see what is going on under the hood, but I do not have a good grip on the interchangeability of t and k. I also especially don't understand how to solve the inner summation from (1) to (2). Any help would be greatly appreciated as this is the main roadblock I am encountering in fully understanding the algorithm. Thank you very much!
  
  **Tags:** reinforcement-learning, machine-learning, temporal-difference-methods, multilayer-perceptrons
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-05-24. Score: 1
  
  The derivation is a result of manipulating sums.
  Starting with
  $$w=w+\sum\_{t=1}^{m}\alpha\sum\_{k=t}^{m}(P\_{k+1}-P\_{k})\nabla\_{w}P\_{t}$$
  we focus on the double sum where $m=3$. Then,
  
  $$\sum\_{t=1}^{3}\alpha\sum\_{k=t}^{3}(P\_{k+1}-P\_{k})\nabla\_{w}P\_{t}$$
  $$=\alpha(P\_{2}-P\_{1})\nabla\_{w}P\_{1}+\alpha(P\_{3}-
  P\_{2})\nabla\_{w}P\_{1}+\alpha(P\_{4}-P\_{3})\nabla\_{w}P\_{1}+\alpha(P\_{3}-P\_{2})\nabla\_{w}P\_{2}+\alpha(P\_{4}-P\_{3})\nabla\_{w}P\_{2}+\alpha(P\_{4}-P\_{3})\nabla\_{w}P\_{3}$$
  Rearranging gives us
  $$\alpha(P\_{2}-P\_{1})\nabla\_{w}P\_{1}+\alpha(P\_{3}-P\_{2})\nabla\_{w}(P\_{1}+P\_{2})+\alpha(P\_{4}-P\_{3})\nabla\_{w}(P\_{1}+P\_{2}+P\_{3})$$
  which is the same as (leave it to you)
  $$\alpha\sum\_{k=1}^{3}\sum\_{t=1}^{k}(P\_{k+1}-P\_{k})\nabla\_{w}P\_{t}$$
  Trivial algebra and separating the sums gives us (1) and (2). Any further doubts are welcome.
  
  
  ---
  
  