# Proof that Temporal-Difference TD(1) is Equivalent to Widrow-Hoff

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!

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.