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 the 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. Recently, deep reinforcement learning (RL) has been very successful in many complex environments such as the Arcade Learning Environment (Bellemare et al., 2013) and Go . Deep Q-Network (DQN) algorithm BID11 with the help of experience replay BID8 BID9 enjoys more stable and sample-efficient learning process, so is able to achieve super-human performance on many tasks. Unlike simple online reinforcement learning, the use of experience replay with random sampling breaks down the strong ties between correlated transitions and also allows the transitions to be reused multiple times throughout the training process.Although DQN has shown impressive performances, it is still impractical in terms of data efficiency. To achieve a human-level performance in the Arcade Learning Environment, DQN requires 200 million frames of experience for training, which is approximately 39 days of game play in real time. Remind that it usually takes no more than a couple of hours for a skilled human player to get used to such games. So we notice that there is still a tremendous amount of gap between the learning process of humans and that of a deep reinforcement learning agent. This problem is even more crucial in environments such as autonomous driving, where we cannot risk many trials and errors due to the high cost of samples.One of the reasons why the DQN agent suffers from such low sample efficiency could be the sampling method over the replay memory. In many practical problems, the agent observes sparse and delayed reward signals. There are two problems when we sample one-step transitions uniformly at random from the replay memory. First, we have a very low chance of sampling the transitions with rewards for its sparsity. The transitions with rewards should always be updated, otherwise the agent cannot figure out which action maximizes its expected return in such situations. Second, there is no point in updating a one-step transition if the future transitions have not been updated yet. Without the future reward signals propagated, the sampled transition will always be trained to return a zero value.In this work, we propose Episodic Backward Update (EBU) to come up with solutions for such problems. Our idea originates from a naive human strategy to solve such RL problems. When we observe an event, we scan through our memory and seek for another event that has led to the former one. Such episodic control method is how humans normally recognize the cause and effect relationship BID7 . We can take a similar approach to train an RL agent. We can solve the first problem above by sampling transitions in an episodic manner. Then, we can be assured that at least one transition with non-zero reward is being updated. We can solve the second problem by updating transitions in a backward way in which the transitions were made. By then, we can perform an efficient reward propagation without any meaningless updates. This method faithfully follows the principle of dynamic programing.We evaluate our update algorithm on 2D MNIST Maze Environment and the Arcade Learning Environment. We observe that our algorithm outperforms other baselines in many of the environments with a notable amount of performance boosts.
We propose Episodic Backward Update, a novel deep reinforcement learning algorithm which samples transitions episode by episode and updates values recursively in a backward manner to achieve fast and stable learning. Proposes a new DQN where the targets are computed on a full episode by a backward update (end to start) for faster propagation of rewards by the episode end. The authors propose to modify the DQN algorithm by applying the max Bellman operator recursively on a trajectory with some decay to prevent accumulating errors with the nested max. In deep-Q networks, update Q values starting from the end of the episode in order to facilitate quick propagation of rewards back along the episode.