# Eligibility traces and function approximators.

I'm looking at Sutton & Barto's use of eligibility traces combined with function approximation (e.g. sections 13.5, 13.6) and I noticed that it looks a whole lot like ordinary SGD with momentum. I'm wondering, what's the essential difference between the two?

# Context

Let's focus on value-function updates to keep things simple. The updates for the state-value function is of the form: \begin{align} \text{eligibility traces:}&&\mathbf{z}\ &\leftarrow\ \gamma\lambda\,\mathbf{z} + \nabla \hat{v}_t \\ &&\boldsymbol{\theta}\ &\leftarrow\ \boldsymbol{\theta}+\alpha\,\delta_t\,\mathbf{z} \end{align} Here, $$\delta_t=G_t-\hat{v}_t$$ is the TD error, where the target $$G_t$$ is either sampled or bootstrapped. By convention, hatted quantities like $$\hat{v}_t$$ depend in the parameters $$\theta$$.

On the other hand, here's how I would implement standard SGD with momentum: \begin{align} \text{SGD with momentum:}&&\mathbf{u}\ &\leftarrow\ \eta\,\mathbf{u} + (1-\eta)\,\alpha\,\delta_t\nabla \hat{v}_t\\ &&\boldsymbol{\theta}\ &\leftarrow\ \boldsymbol{\theta}+\mathbf{u} \end{align} where I used $$\nabla L^\text{mse}_t=-\delta_t\nabla \hat{v}_t$$ (chain rule).

From the looks of it, the only difference between eligibility traces and momentum updates is the inclusion / exclusion of the TD error factor $$\delta_t$$ in the momentum ($$\mathbf{z}$$ or $$\mathbf{u}$$).

In fact, let's sharpen the comparison by introducing the rescaled momentum $$\mathbf{z}'=\mathbf{u}\,/\,(1-\eta)\alpha$$. The same momentum update then looks like: \begin{align} \text{SGD with momentum:}&&\mathbf{z}'\ &\leftarrow\ \gamma\lambda'\,\mathbf{z}' + \delta_t\nabla \hat{v}_t\\ &&\boldsymbol{\theta}\ &\leftarrow\ \boldsymbol{\theta}+\alpha'\,\mathbf{z}' \end{align} with $$\lambda'=\eta/\gamma$$ and $$\alpha'=(1-\eta)\,\alpha$$ introduced for convenience. Indeed we see that the only real difference between momentum and eligibility traces is whether we include $$\delta_t$$ in the momentum or whether we mix it in later.

# Question

Is there a reason to prefer accumulating $$\nabla v_t$$ (eligibility traces) over accumulating the full gradient $$\delta_t\nabla v_t$$ (momentum)?

If so, what would be the intuition behind it?

Also, are there examples in deep RL of successful uses of eligibility traces?

• I think your last question "Also, are there examples in deep RL of successful uses of eligibility traces?" should be separate. – Neil Slater May 13 '19 at 12:36

For simplicity, let us consider the case of no discount ($$\gamma = 1$$). This setting is sufficient to understand the difference between eligibility trace and momentum.

Then, $$\mathbf{z}_t$$ appeared in eligibility trace is the sum of the history of the gradients $$\nabla \hat{v}_t$$: $$\mathbf{z}_t = \sum_{k=0}^t \nabla \hat{v}_{t-k} .$$ This quantity is the (short-term) memory in order to enable us to update $$\mathbf{w}$$ for the previous states because the update rule is $$\boldsymbol{\theta}\ \leftarrow\ \boldsymbol{\theta}+\alpha\,\delta_t\,\mathbf{z} = \boldsymbol{\theta}+\alpha\,\delta_t \sum_{k=0}^t \nabla \hat{v}_{t-k} = \boldsymbol{\theta}+\alpha\,\delta_t \nabla \hat{v}_{t} + \delta_t \nabla\hat{v}_{t-1} + \delta_t \nabla\hat{v}_{t-2} + \cdots$$

Please notice that $$\hat{v}_{t-k}$$ represents the value function of $$S_{t-k}$$.

By this rule of eligibility trace, the current reward embedded in $$\delta_t$$ is transferred to the states in the past. (e.g. information about the result of a play of Go has to be transferred to the states appeared on that game.)

On the other hand, $$\mathbf{u}$$ in momentum is the historical direction of $$\theta$$'s movement. That's why this method is called momentum.

$$\mathbf{u}\ =\sum_{k=1}^t \delta_k\nabla \hat{v}_k \ (\alpha = \eta = 1\ \text{for simplicity})$$ The momentum rule can be used to determine the direction of next $$\theta$$ with considering the historical $$\theta$$'s movement by avoiding sudden direction change. The sudden change of update direction is risky because the information obtained from the current state is probabilistic and might be wrong.

### Update

Although equations are similar each other, the objective of momentum is totally different from one of eligibility trace.

Momentum is used to avoid noise of mini-batch SGD and raven effect. See this post.

On the other hand, eligibility trace is used to add the reward $$R_t$$ to the values of the previous $$\{v_{t-k}\}_{k=1,2,\cdots}$$. In order to transfer reward to backward, you can not use momentum.

Say, for TD($$\lambda$$), it is necessary to send the reward to the previous states. If you are not familiar with TD($$\lambda$$), I recommend you to read 12.2 of Sutton's text book. PDF version is free to download.

• Thank you for thinking along. Do I understand correctly that you're saying that the difference is whether or not you mix in $\delta_t$ with each momentum update? If so, I was aware of that. I guess I was looking for an intuitive reason why you might prefer to use eligibility traces over momentum (or vice versa). – Kris Nov 17 '19 at 8:29
• I updated my answer. Momentum is not alternative of eligibility trace. Those have totally different objectives dispte similar equations. – rkjt50r983 Nov 17 '19 at 11:47
• Thanks for the update. I am familiar with TD($\lambda$) and with the S&B book. I acknowledge that the motivation for momentum and eligibility traces are different, but I don't think the motivation is very important. I care more about the actual difference in weight updates. You say that I "cannot use momentum", but I don't see a very good reason why not. – Kris Nov 17 '19 at 22:52
• In fact, intuitively I'd say that momentum might work better because it accumulates the full gradient $\nabla L$ rather than only the subgradient $\nabla v$. It therefore reduces noise on the full update, not only on the $\nabla v$ factor. In TD language this means that momentum doesn't only transfer a partial signal (the reward) back to previous time steps, but it transfers back the full update signal. What do you think? – Kris Nov 17 '19 at 22:52
• You can not use momentum to transfer a reward backward (that is necessary to realize TD($\lambda$)) because the sum of previous movements (momentum) does not hold the information of the gradients of each step on a episode. – rkjt50r983 Nov 17 '19 at 23:32