TD lambda is a way to interpolate between TD(0) - bootstrapping over a single step, and, TD(max), bootstrapping over the entire episode length, or, Monte Carlo.

Reading the link above, I see that an eligibility trace is kept for each state in order to calculate its "contribution to the future".

But, if we use an approximator, and not a table for state-values, then can we still use eligibility traces? If so, how would the loss (and thus the gradients) be calculated? Specifically, I would like to use actor-critic (or advantage actor-critic).


Eligibility traces is a method of weighting between temporal-difference "targets" and Monte-Carlo "returns". In practice, for example, instead of using the one-step TD target, $r_t + \gamma V (s_{t+1})$, as in the temporal difference update $V (s_t) \leftarrow V (s_t) + \alpha (r_t + \gamma V (s_{t+1}) − V (s_t))$, you use the so-called "lambda" ($\lambda$) target, which is a target that balances between the TD target and the Monte Carlo return. So, in practice and intuitively, eligibility traces is just a way of using a more "appropriate" target while learning. In general, you need to perform these updates (e.g., the TD update above) "online", i.e. while you explore or exploit the environment.

In theory, you could use a deep neural network to represent your value function (or your policy), while using eligibility traces. It would be similar to not using them: you would just use a different target.

However, deep RL (that is, RL which uses deep neural networks to represent e.g. value functions) training needs to be performed using i.i.d. data, in order to prevent overfitting, which often means that they can't be trained online or need to use "tricks" like the "experience replay" (used in the paper Human-level control through deep reinforcement learning). Note that, in RL, successive states are often very correlated (e.g. two successive frames of a video would be very correlated).

In theory and similarly, you would still be able to use eligibility traces with the actor-critic method, but not with the asynchronous advantage actor-critic method. See the section 2.3 of the paper "Efficient Eligibility Traces for Deep Reinforcement Learning" (2018) by Brett Daley and Christopher Amato, for more info.

In this same paper, an approach is introduced to efficiently combine eligibility traces with deep neural networks. The authors propose DQN($\lambda$), which is the DQN architecture combined with eligibility traces, where the $\lambda$ return is computed in an "efficient" (and recursive) way, instead of the "usual" way. Since they use a DQN, they also use an "experience replay" buffer (or memory), where they also store the efficiently computed $\lambda$ target (in addition to the usual rewards). Furthermore, they also eliminate the need for the "target" network used in the standard DQN. You can have a look at algorithm 1 of the same paper to see how they improve the parameters of the network, which represents the Q function, in the case of the DQN($\lambda$) model. See the section 3.1 of the same paper for more details regarding this model.

They also introduce A3C($\lambda$), which combines asynchronous advantage actor-critic (A3C) with eligibility traces. See the section 3.2 for more details.

Note that there have been other proposals for combining eligibility traces with deep learning. You can have a look at the literature.

| improve this answer | |

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.