Episodic memory is a psychology term which refers to the ability to recall specific events from the past. We suggest one advantage of this particular type of memory is the ability to easily assign credit to a specific state when remembered information is found to be useful. Inspired by this idea, and the increasing popularity of external memory mechanisms to handle long-term dependencies in deep learning systems, we propose a novel algorithm which uses a reservoir sampling procedure to maintain an external memory consisting of a fixed number of past states. The algorithm allows a deep reinforcement learning agent to learn online to preferentially remember those states which are found to be useful to recall later on. Critically this method allows for efficient online computation of gradient estimates with respect to the write process of the external memory. Thus unlike most prior mechanisms for external memory it is feasible to use in an online reinforcement learning setting.
Much of reinforcement learning (RL) theory is based on the assumption that the environment has the Markov property, meaning that future states are independent of past states given the present state. This implies the agent has all the information it needs to make an optimal decision at each time and therefore has no need to remember the past. This is however not realistic in general, realistic problems often require significant information from the past to make an informed decision in the present, and there is often no obvious way to incorporate the relevant information into an expanded present state. It is thus desirable to establish techniques for learning a representation of the relevant details of the past (e.g. a memory, or learned state) to facilitate decision making in the present.
A popular approach to integrate information from the past into present decision making is to use some variant of a recurrent neural network, possibly coupled to some form of external memory, trained with backpropagation through time. This can work well for many tasks, but generally requires backpropagating many steps into the past which is not practical in an online RL setting. In purely recurrent architectures one way to make online training practical is to simply truncate gradients after a fixed number of steps. In architectures which include some form of external memory however it is not clear that this is a viable option as the intent of the external memory is generally to capture long term dependencies which would be difficult for a recurrent architecture alone to handle, especially when trained with truncated gradients. Truncating gradients to the external memory would likely greatly hinder this capability.
In this work we explore a method for adding external memory to a reinforcement learning architecture which can be efficiently trained online. We liken our method to the idea of episodic memory from psychology. In this approach the information stored in memory is constrained to consist of a finite set of past states experienced by the agent. In this work, by states we mean observations explicitly provided by the environment. In general, states could be more abstract, such as the internal state of an RNN or predictions generated by something like the Horde architecture of Sutton  et al. (2011). By storing states explicitly we enforce that the information recorded also provides the context in which it was recorded. We can therefore assign credit to the recorded state without explicitly backpropagating through time between when the information proves useful and when it was recorded. If a recorded state is found to be useful we train the agent to preferentially remember similar states in the future.
The paper proposes a modified approach to RL, where an additional "episodic memory" is kept by the agent. What this means is that the agent has a reservoir of n "states" in which states encountered in the past can be stored. There are then of course two main questions to address (i) which states should be stored and how (ii) how to make use of the episodic memory when deciding what action to take. 
For the latter question, the authors propose using a "query network" that based on the current state, pulls out one state from the memory according to certain probability distribution. This network has many tunable parameters, but the main point is that the policy then can condition on this state drawn from the memory. Intuitively, one can see why this may be advantageous as one gets some information from the past. (As an aside, the authors of course acknowledge that recurrent neural networks have been used for this purpose with varying degrees of success.)
The first question, had a quite an interesting and cute answer. There is a (non-negative) importance weight associated with each state and a collection of states has weight that is simply the product of the weights. The authors claim (with some degree of mathematical backing) that sampling a memory of n states where the distribution over the subsets of past states of size n is proportional to the product of the weights is desired. And they give a cute online algorithm for this purpose. However, the weights themselves are given by a network and so weights may change (even for states that have been observed in the past). There is no easy way to fix this and for the purpose of sampling the paper simply treats the weights as immutable. 
There is also a toy example created to show that this approach works well compared to the RNN based approaches.
Positives:
- An interesting new idea that has potential to be useful in RL
- An elegant algorithm to solve at least part of the problem properly (the rest of course relies on standard SGD methods to train the various networks)
Negatives:
- The math is fudged around quite a bit with approximations that are not always justified
- While overall the writing is clear, in some places I feel it could be improved. I had a very hard time understanding the set-up of the problem in Figure 2. [In general, I also recommend against using figure captions to describe the setup.]
- The experiments only demonstrate the superiority of this method on an example chosen artificially to work well with this approach.