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!


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .