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?


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.


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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.