Eligibility Traces vs Experience Replay

Question

I am currently using the OpenAI Baselines implementation of DeepQ (paper found here). I am also utilizing Prioritized Experience Replay (paper found here).

My problem involves sparse delayed rewards and therefore I believe adding eligibility traces will help speed up learning.

I have not seen Experience Replay implemented along with Eligibility Traces. Is this possible?

I realize ER is intended to remove the adverse effects of autocorrelation when training neurel networks. However, with this we lose the ability to take advantage of the proven success of eligibility traces when dealing with sparse delayed rewards.

Any insight into why ER is the accepted standard would be greatly appreciated. Especially when a key problem in RL is sparse delayed rewards.

Answer 1

You are correct that experience replay (ER) makes the implementation of eligibility traces impossible. States are not processed in the order they are visited, which is a requirement for the backward view of TD(λ). Yet it would be nice to somehow achieve the benefits of eligibility traces in sparse-reward environments when using DQN, as you suggest. This problem has been the primary focus of my own research.

In my paper Reconciling λ-Returns with Experience Replay, I propose a solution that uses offline λ-return calculation (aka the forward view) to emulate eligibility traces. I describe a procedure that allows this to be done efficiently for DQN while retaining ER. I found that learning speed could be increased compared to n-step returns when playing Atari games, and I expect these results to generalize to other domains. My code can be found here.

You can also read this paper for another approach to rectifying eligibility traces with Deep Q-learning. However, its major limitations are that it is compatible only with Deep Recurrent Q-Networks (DRQN) and that the λ-return calculation must be truncated to the length of the RNN training sequence.

Finally, it is important to note that there are other benefits to ER than just decorrelating the training experience. For example, ER can greatly improve sample efficiency, which is explored in this paper. However, ER cannot be called an "accepted standard." Many policy gradient methods like TRPO, PPO, and ACKTR do not use ER. In the case of DQN, ER was primarily a design decision to help prevent overfitting when estimating Q-values and yield superior empirical performance.

Answer 2

After performing some additional research:

After demonstrating the significant improvements of Experience Replay when training deep neurel networks in this paper, DeepMind wanted to remove the limiting architecture Experience Replay required. Instead, in they're next generation (A3C) (paper here) they decided to utilize asynchronous parellel agents to achieve the same purpose of Experience Replay (autocorrelation removal). Without Experience Replay they were free to implement N-Step returns.

The following is explained in the paper Asynchronous Methods for Deep Reinforcement Learning 2:

Instead of experience replay, we asynchronously execute multiple agents in parallel, on multiple instances of the environment. This parallelism also decorrelates the agents’ data into a more stationary process, since at any given time-step the parallel agents will be experiencing a variety of different states. This simple idea enables a much larger spectrum of fundamental on-policy RL algorithms, such as Sarsa, n-step methods, and actorcritic methods, as well as off-policy RL algorithms such as Q-learning, to be applied robustly and effectively using deep neural networks.