We propose Episodic Backward Update -a new algorithm to boost the performance of a deep reinforcement learning agent by fast reward propagation. In contrast to the conventional use of replay memory with uniform random sampling, our agent samples a whole episode and successively propagates the value of a state into its previous states. Our computationally efficient recursive algorithm allows sparse and delayed rewards to propagate effectively throughout the sampled episode. We evaluate our algorithm on 2D MNIST Maze Environment and 49 games of the Atari 2600 Environment and show that our agent improves sample efficiency with a competitive computational cost.
This paper proposes a new variant of DQN where the DQN targets are computed on a full episode by a « backward » update (i.e. from end to start of episode). The targets’ update rule is similar to a regular tabular Q-learning update with high learning rate beta: this allows faster propagation of rewards obtained at the end of the episode (while beta=0 corresponds to regular DQN with no such reward propagation). This mechanism is shown to improve on Q-learning in a toy 2D maze environment (with MNIST-based pixel states providing cell coordinates) with beta=1, and on DQN and its optimality tightening variant on Atari games with beta=0.5.
The intuition behind the algorithm (that one should try to speed up the propagation of rewards across multiple steps) is not new, in fact it has inspired other approaches like n-step Q-learning, eligibility traces or more recently Retrace(lambda) in deep RL. Actually the idea of replaying experiences in backward order can be traced back to the origins of experience replay («  Programming Robots Using Reinforcement Learning and Teaching », Lin, 1991), something that is not mentioned here. That being said, to the best of my knowledge the specific algorithm proposed in this submission (Alg. 2) is novel, even if Alg. 1 is not (Alg. 1 can be seen as a specific instance of Lin’s algorithm with a very high learning rate, and clearly only makes sense in toy deterministic environments).
In the absence of any theoretical analysis of the proposed approach, I would have expected an in-depth empirical validation. Unfortunately this is not the case here. In the toy environment (4.1) I am surprised by the really poor quality of the results (paths 5-10 times longer than the shortest path on average): have algorithms been run for a long enough time? Or maybe the average is a bad performance measure due to outliers? I would have also appreciated a comparison to Retrace(lambda), which is a more principled way to use multi-step rewards than n-step Q-learning (which is technically an on-policy method). Similar remarks can be made on the Atari experiments (4.2), where 10M frames is really low (the original DQN paper had results on 50M frames, and Rainbow reports 200M frames in only ~2x the training time reported here). The comparison also should have included prioritized experience replay, which has been shown to provide a significant boost in DQN, but may be tricky to combine with the proposed algorithm. Overall comparing only to vanilla DQN and its optimality tightening variant is too limited when there have been so many other meaningful improvements over DQN. This makes it really hard to tell whether the proposed algorithm would actually help when combined with a state-of-the-art method like Rainbow for instance.
A few additional small remarks and questions:
- « Second, there is no point in updating a one-step transition unless the future transitions have not been updated yet. »: should « unless » be replaced by « if »?
- In 4.1 is there a maximum number of steps per episode and can you please confirm that training is done independently for each maze?
- Typo in eq. 3: the - in the max should be a comma
- There is a good amount of typos and grammar errors, though they do not harm the readability of the paper
- Citations for « Deep Reinforcement Learning with Double Q-learning » and « Dueling Network Architectures for Deep Reinforcement Learning » could refer to their conference versions
- « epsilon starts from 1 and is annealed to 0 at 200,000 steps in a quadratic manner »: please specify the exact formula
- Fig. 7 is really confusing, there seem to be typos and it is not clear why the beta updates appear in these specific cells, please revise it if you want to keep it