2
$\begingroup$

For me the evolution of TD Algorithms looks like this:

1-step TD: problematic with sparse rewards => Inefficient use of experience

n-step TD: better than 1-step, but what is the best n? (nobody knows without trying)

n-step TD(lambda): combine all n-step returns and build a weighted average over all returns => Q/V function can only be updated at the end of an episode

n-step TD(lambda) with eligibility traces: elegibility traces allow the Q/V function to be updated online/on the fly without waiting till an episode is over

What I don't understand is why we need an eligibility trace at all?
I think we could just ignore the eligibility trace because states which weren't visited frequently will have a small TD error so they won't be updated much anyway.

Update rule:
$Q(s_t,a_t)=Q(s_t,a_t)+\alpha \delta(s_t,a_t) et(s_t,a_t))$

TD error:
$\delta (s_t,a_t)=R_t+ \gamma Q(s_{t+1},a_{t+1})−Q(s_t,a_t)$

$\endgroup$
1
  • $\begingroup$ Could you clarify why you think that "states which weren't visited frequently will have a small TD error"? In general, I would expect the opposite, since estimates for the current value of those rare states are likely to have higher standard error, due to low sample number. I don't think frequency of state/action pairs is relevant here anyway, and putting an answer together. $\endgroup$ Apr 4, 2018 at 16:46

1 Answer 1

1
$\begingroup$

What I don't understand is why we need an eligibility trace at all?

It specifically calculates an equivalent to the n-step return that can be applied immediately to all previous visited states.

Without the eligibility trace, you would be left with two possibilities (depending on how you intend to remove it):

  • If you only apply corrections to most recent state/action value, effectively single-step returns (same as $\lambda = 0$)

  • If you remember all previous state/action pairs in the trajectory and update them all, very similar to Monte Carlo (same as $\lambda = 1, \gamma = 1$), but with updates applied immediately based on best bootstrapped estimate so far.

Why do eligibility traces assign higher values to recently/frequently visited states?

This is a direct consequence of the weighting of the different n-step returns that sum into a full $\lambda$ return, and the same thing happens in the forward view without eligibility traces (just the sums and updates occur in a different order).

The most recently-visited state is being adjusted for the n=1 term, plus an estimate of all remaining terms that will be cancelled out over time depending on value of $\lambda$. When $\lambda = 0$, then you only ever use the n=1 term, it has all the weight, since the eligibility trace for the current state goes to zero on next iteration. When $\lambda = 1$, effectively the previous estimate is continuously over-written with the next one, as the eligibility trace doesn't reset.

When the same state appears multiple times in a single trajectory (say it occurs twice, $k$ steps apart), then an $x$ steps after the second occurrence must update for the n-step return for $n=x$ and $n=x+k$. So the extra weighting is is not due to frequency of occurring so much as actually occurring on the trajectory that is being updated - there are literally two returns to calculate and sum into the estimate when a state happens twice.

I think we could just ignore the eligibility trace because states which weren't visited frequently will have a small TD error so they won't be updated much anyway.

Eligibility traces do not correct for frequencies of anything (maybe you are thinking of importance sampling here?). Instead, they effectively calculate [a correction for] $\lambda$ return, the weighted sum of 1..n step return, that can be shown to be an estimate of that same $\lambda$ return taken at the end of an episode. The actual trajectory taken matters, irrespective of the probability of it happening.

Corrections for frequency of states and actions occur in the long term due to sampling, and are not directly related to what the trace is doing. One way to see this: Provided there are no cycles going back to earlier states (where the eligibility-trace version may have updated the policy already), you can suppose that an agent interacting with the same policy and environment and same RNG seed would behave the same and collect the same raw data of rewards and successor states for making updates. At the end of an episode, the goal for eligibility trace version is, given these same trajectories, that its updates are the same numerically as the version without eligibility trace where all the updates are calculated at the end. You can see this number does not take frequencies of states directly into account (they have an effect on the long-term value function, but not on the current set of updates).

In Q($\lambda$) the probabilities of the policy do matter - trajectories that include exploratory actions have their eligibility trace (and thus estimates of long-term return) reset when taking non-maximising actions, so as not to feed back later non-maximising returns to earlier states.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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