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

Question

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!

Answer 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.