3
$\begingroup$

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?

$\endgroup$
  • $\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 '19 at 12:36
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Kris Nov 17 '19 at 8:29
  • $\begingroup$ I updated my answer. Momentum is not alternative of eligibility trace. Those have totally different objectives dispte similar equations. $\endgroup$ – rkjt50r983 Nov 17 '19 at 11:47
  • $\begingroup$ 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. $\endgroup$ – Kris Nov 17 '19 at 22:52
  • $\begingroup$ 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? $\endgroup$ – Kris Nov 17 '19 at 22:52
  • $\begingroup$ 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. $\endgroup$ – rkjt50r983 Nov 17 '19 at 23:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.