# 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 of bootstrapped. By convention, hatted quantities like $$\hat{v}_t$$ depend in the parameters $$\theta$$.

One 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 at 12:36