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.
 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. In our approach the set of states in memory at a given time is drawn from a distribution over all n-subsets (subsets of size n) of visited states, parameterized by a weight value assigned to each state by a trained model. To allow us to draw from such a distribution without maintaining all visited states in memory we introduce a reservoir sampling technique. Reservoir sampling refers to a class of algorithms for sampling from a distribution over n-subsets of items from a larger set streamed one item at a time. The goal is to ensure, through specific add and drop probabilities, that the n items in the reservoir at each time-step correspond to a sample from the desired distribution over n-subsets of all observed items. Two important examples which sample from different distributions are found in BID1 and Efraimidis & Spirakis (2006) . In this work we will define our own distribution and sampling procedure to suit our needs. Deep learning systems which make use of an external memory have received a lot of interest lately. Two prototypical examples are found in Graves et al. (2014) and the follow-up Graves et al. (2016) . These systems use an LSTM controller attached to read and write heads of a fully differentiable external memory and train the combined system to perform algorithmic tasks. Contrary to our approach, training is done entirely by backpropagation through time. See also Zaremba & Sutskever (2015) , Joulin & Mikolov (2015) , Sukhbaatar et al. (2015) , Gulcehre et al. (2017) and Kaiser et al. (2017) for more examples of deep learning systems with integrated external memory. More directly related to the present work is the application of deep RL to non-markov tasks, in particular Oh et al. (2016) . They experiment with architectures using a combination of key-value memory and a recurrent neural networks. The memory saves keys and values corresponding to the last N observations for some integer N , thus it is inherently limited in temporal extent but does not require any mechanism for information triage. They test on problems in the Minecraft domain which could provide compelling testbeds for a potential follow-up to the present work. See also BID0 , Wierstra et al. (2010 ), Zhang et al. (2016 and Hausknecht & Stone (2015) for more examples of applying deep RL to non-markov tasks. Our model is based around an advantage actor critic architecture (Mnih et al., 2016) consisting of separate value and policy networks. In addition we include an external memory M consisting of a set of n past visited states (S t0 , .., S tn−1 ) with associated importance weights (w t0 , ..., w tn−1 ). The query network q(S t ) outputs a vector of size equal to the state size with tanh activation. At each time step a single item S ti is drawn from the memory to condition the policy according to: DISPLAYFORM0 where τ is a positive learnable temperature parameter. The state, m t , selected from memory is given as input to the policy network along with the current state, both of which condition the resulting policy. Finally the write network takes the current state as input and outputs a single value with sigmoid activation. This value is used to determine how likely the present state is to be written to and subsequently retained in the memory according to the distribution in equation 7 which will be throughly explained in section 3. An illustration of this architecture is shown in figure 1. For the most part our model is trained using standard stochastic gradient descent on common RL loss functions. The value network is trained by gradient descent on the squared one step temporal different error δ 2 t where δ t = r t+1 + V (S t+1 ) − V (S t ), and the gradient is passed only through V (S t ). The policy is trained using the advantage loss −δ t log(π(a t |S t , m t )) with gradients passed only through π(a t |S t , m t ). The query network is trained similarly on the loss −δ t log(Q(m t |S t )) with gradients passed only through Q(m t |S t ). We train online, performing one update per timestep with no experience replay. The main innovation of this work is in the training method for the write network which is described in sections 3.1 and 3.2. There are two main desiderata we wish to satisfy with the write network. First we want to use the weights w(S t ) generated by the network in a reservoir sampling algorithm such that the probability of a particular state St being present in memory at any given future time t >t is proportional to the associated weight w(St). Second we want to obtain estimates of the gradient of the return with respect to the weight of each item in memory such that we can perform approximate gradient descent on the generated weights. For brevity, in this section we will use the notation E t [x] to denote E[x|S 0 , ..., S t ] i.e. the expectation conditioned on the entire history of state visitation up to time t. Similarly P t (x) will represent probability conditioned on the entire history of state visitation. All expectations and probabilities are assumed to be with respect to the current policy, query and write network. Let A represent the set of available actions and A t the action selected at time t. To introduce the idea we first present our gradient estimation procedure for the case when our memory can store just one state, and thus there is no need to query. Here m t represents the state in memory at time t and thus, in the one-state memory case, the state read from memory by the agent at time t. Assume the stored memory is drawn from a distribution parameterized as follows by a set of weights {w i |i ∈ {0, ..., t − 1}} associated with each state S i when the state is first visited: DISPLAYFORM0 We can then write the expected return R t = r t+1 + γr t+2 + ... as follows: DISPLAYFORM1 In order to perform gradient descent on the weights w i we wish to estimate the gradient of this expectation value with respect to each weight. In particular we will derive an estimate of this gradient using an actor critic method which is unbiased if the critic's evaluation is correct. Additionally our estimate will be non-zero only for the w i associated with the index i such that m t = S i . This means if our weights w i are generated by a neural network, we will only have to propagate gradients through the single stored state. This is crucial to allow our algorithm to run online, as otherwise we would need to store every visited state to compute the gradient estimate. DISPLAYFORM2 We can rewrite this as: DISPLAYFORM3 See appendix A for a detailed derivation of this expression. We will use a policy gradient approach, similar to REINFORCE (Williams, 1992) , to estimate the this gradient using an estimator DISPLAYFORM4 ∂wi , thus the second term is estimated recursively on subsequent time-steps. In the present work we will focus on the undiscounted episodic case with the start-state value objective, for which it suffices to follow the first term in the above gradient expression for each visited state. This is also true in the continuing case with an average-reward objective. See Sutton et al. (2000) for further discussion of this distinction. Consider the gradient estimator: DISPLAYFORM5 which has expectation: DISPLAYFORM6 Where the approximation is limited by the accuracy of our value function. In conventional policy gradient subtracting the state value (e.g. using DISPLAYFORM7 ) is a means of variance reduction. Here it is critical to avoid computing gradients with respect to the denominator of equation 2, which allows our algorithm to run online while computing the gradient with respect to only the weight stored in memory. Given these estimated gradients with respect to w i we apply the chain rule to compute DISPLAYFORM8 ∂θw , for each parameter θ w of the write network. This gradient estimate is used in a gradient descent procedure to emphasize retention of states which improve the return. Gradient estimates are generated based on the stored values of w i in memory but applied to the parameters of the network at the present time. With online updating, this introduces a potential multiple timescale issue which we conjecture will vanish in the limit of small learning rate, but leave further investigation to future work. There are a number of ways to extend the distribution defined in equation 2 to the case where multiple elements of a set must be selected (see for example Efraimidis & Spirakis (2006) ). We will focus on a generalization which is less explored but which we will see in the following section results in gradient estimates which are an elegant generalization of the single-state memory case. In this section and those that follow we will routinely use the notation Z n where Z is a set and n an integer to indicate the set of all n-subsets of Z. Note that We will introduce some notation to facilitate reasoning about sets of states. Let T t = {t : 0 ≤ t ≤ t − 1} be the set of all time indices from 0 to t − 1. LetT ∈ Tt n be a set of n indices chosen from T t where n is the memory size. Let ST be the set of states {St :t ∈T }. Let M t be the set of states in memory at time t. Let Q(St|ST ) be the probability of querying St given M t = ST . The probability for a particular set of states being contained in memory is defined to be the following: DISPLAYFORM0 A straightforward extension of the derivation of the equation 5 shows that this choice results in a gradient estimate which is an elegant extension of the one-state memory case. The derivation is given in appendix B, the result for DISPLAYFORM1 DISPLAYFORM2 As in the single-state memory case we recursively handle the second term. To estimate the first term we could choose the following estimator G i,t : DISPLAYFORM3 This estimator is unbiased under the assumption the critic is perfect, however it scales poorly in terms of both variance and computation time as the memory size increases. This is because it requires updating every state in memory regardless of whether it was queried, spreading credit assignment and requiring compute time proportional to the product of the number of states in memory with the number of parameters in the write network. Instead we will further approximate the second term and perform an update only for the queried item. We rewrite the first term of equation 8 as follows: DISPLAYFORM4 This approximation is accurate to the extent that our query network is able to accurately select useful states. To see this, note that if querying a state when it's in memory helps to generate a better expected return a well trained query network should do it with high probability and hence P t (m t = S i |M t S i ) will be low. On the other hand if querying a state in memory is unhelpful DISPLAYFORM5 will generally be small. With this approximation the gradient estimate becomes identical to the one-state memory case: DISPLAYFORM6 While this justification is not rigorous, this approximation should significantly improve computational and sample efficiency, and is used in our experiments in section 4. Algorithm 1 A reservoir sampling algorithm for drawing samples from equation 11 DISPLAYFORM0 Receive w t 7: DISPLAYFORM1 DISPLAYFORM2 end if 11: DISPLAYFORM3 Swap ω with W [i] and τ withT [i] with probability P 13: DISPLAYFORM4 end for 15: DISPLAYFORM5 end for 18: end functionIn the previous section we derived a gradient estimator for our desired memory distribution. in this section we introduce a method for sampling from this distribution online. Specifically we will formulate a reservoir sampling algorithm for drawing a subsetT of size n from a set of indices T = {0, ..., t − 1} according to a distribution parameterized by a weight w i for each index i ∈ T . Following equation 7 the probability for a given subsetT is defined as follows: DISPLAYFORM6 This distribution can be sampled from by selecting members sequentially for i ∈ {0, .., n − 1} with the following conditional probabilities: DISPLAYFORM7 We abuse notation slightly and useT to refer to both an ordered vector and the set of its elements. Lemma 1. Selecting elements sequentially according to equation 12 will result in a vectorT whose elements correspond to a sample drawn from equation 11.Proof. See appendix C.We use lemma 1 to derive a reservoir sampling procedure which works online to update the reservoir T at each time-step when a new index is added to T along with an associated weight. The result is algorithm 1. At each time-step UPDATE moves throughT starting from index 0 and chooses whether to swap the item and weight at each index with the ones currently contained in a buffer (τ and ω, initially set to contain the newly added item and associated weight). The probability of swapping is chosen such that it corrects the conditional probability of the item at each index (conditioned on the items before it) to compensate for the item in the buffer being added to the set of possible items for that index. After doing this sequentially at each index the overall probability ofT will be correct with the newly added item. Computing the necessary swap probabilities is nontrivial in itself, however we show that it is possible to do this in O(n) time per time-step (where here n is the memory size) by iteratively updating two vectors Ω andΩ.Theorem 1. In algorithm 1 let t refer to the parameter of the call to UPDATE,T t [i] refer to the value ofT [i] when that call is made, and T t = {t : 0 ≤ t ≤ t − 1} refer to the set of all time indices from 0 to t − 1. ∀t ≥ n, 0 ≤ i ≤ n − 1: DISPLAYFORM8 where [t 0 , ..., t i ] is any arbitrary vector of unique elements of T t .Proof. See appendix D.Corollary 1.1. At the call to UPDATE with parameter t, ∀t ≥ n,T ∈ Tt n : DISPLAYFORM9 Proof. The proof follows from theorem 1 and lemma 1.Corollary 1.1 tells us that for any given time-step algorithm 1 produces reservoirs which are a valid sample from the distribution of equation 11. Note that algorithm 1 runs in O(n) time per time-step where n is the size of the memory. We use this algorithm along with the weights generated by our write network to manage updating the memory on each new state visitation. The careful reader will notice that with the use of reservoir sampling equation 7 no longer holds explicitly. This is because certain parts of the history may strongly correlate with certain states being in memory at a particular time in the past, which under reservoir sampling will effect the distribution of the present memory. We do not account for this in this work and simply assume for the purpose of estimating gradients that the history of state visitation arises independently of the history of memory content. Further analysis of the implications of this assumption, and whether it can be weakened is left to future work. We test our algorithm on a toy problem we call "the secret informant problem". The problem is intended to highlight the kinds of sharp, long-term dependencies that are often difficult for recurrent models. The problem is such that in order to behave optimally an agent must remember specific, initially unknown past states. An instance of the problem is shown in FIG1 and a detailed explanation of the problem structure is available in the associated caption. In each training episode a new random instance of the problem is created (with the chain length, number of actions and number of decisions held fixed for a particular training run). This consists of randomly choosing the rewarding action sequence, the location of the informative state for each decision, and the implied action and decision state for each of the uninformative states. All experiments with our episodic memory architecture are run for 3 repetitions with error bars indicating standard error in the mean over these 3 runs. The architecture and hyper-parameters used in each experiment are identical. We use the architecture from section 2 with 1 hidden layer for the value, query and write networks and 2 hidden layers for policy. The value network and query network outputs each use tanh activation, the policy uses softmax, and the write network uses sigmoid. Each hidden layer has 10 units. We train using ordinary stochastic gradient descent with learning rate 0.005 and gradient estimates generated as specified in section 3. ) shows an instance of the secret informant problem with 3 actions (A = {up, f orward, down}) and 2 decision states. The start state uniquely contains all zeros. In the final 2 states of an episode (which we call decision states), the agent must select the right sequence of actions to receive a +1 reward, any other action sequence gives reward 0. At all other states the forward action leads forward along the chain while other actions keep the agent in the same state. The correct action (i.e. the one that leads towards the reward) at each decision state is indicated by a one hot encoding on bits 1-3 of a certain informative state where the pattern in bits 6 and 7 matches those of the decision state itself. Informative states are distinguished from uninformative states by bits 4 and 5. To succeed the agent must learn to remember informative states with the pattern 10 in bits 4 and 5 and subsequently query them at the associated decision state. (b) shows a particular state of the problem. The first 3 bits are action indicators, a one-hot encoding of the action the state is suggesting should be taken at the associated decision state. The next two bits are informative and uninformative indicators. If these bits are 01 the state is uninformative, meaning the decision state and associated action it suggests are uniformly random and give no indications of a correct action. If these bits are 10 then the state is informative and the associated action it suggests is on the path toward the reward at the decision state it indicates. The next two bits are decision state identifiers, in an informative state they indicate it provides information about the decision state with matching identifier, in a decision state they serve as an identifier for that decision state. Thus, the correct thing for an agent to do in each decision state is to take the action suggested by the informative state with matching values of bits 6 and 7. The next bit is a decision state indicator and will be 1 if and only if the state is a decision state. The final bit is a correct path indicator and indicates for a decision state whether all the decisions made so far have been correct. This is necessary for our current system because without it the final decision states all look the same and it is not possible to learn via one step updates which decision is correct at the first decision state, in future work we would like to investigate eliminating the need for information like this by using multi-step updates or eligibility traces. The particular state shown above is informative, it indicates that the correct action for the second decision state will be the up action. Versions of this problem can be created with variable length (which we use to refer to the number of informative states plus the number of uninformative states), number of actions, and number of decision states by modifying the above description in the obvious way. We also ran a recurrent baseline with full backpropagation through time which we found required more fine-tuning to train with online updates. To make comparison as meaningful as possible the recurrent baseline used essentially the same architecture but with the entire memory module replaced by a basic GRU BID2 network of 10 units. Stochastic gradient descent alone was found to give very poor results with the recurrent learner so RMSProp was used instead. Additionally to obtain reasonable results with the recurrent learner, and avoid catastrophic looping behavior, it was necessary to add a discount factor (γ = 0.9, applied only for learning purposes and not used in computing the plotted return) as well as entropy regularization on the policy with a relatively low weight of 0.0005. Perhaps surprisingly neither of these were necessary with the episodic memory based system as it tended to proceed quickly through the chain without significant looping even without discounting or entropy regularization. We tuned the learning rate and layer width (including the number of recurrent units) for each of the 2 environments on which a recurrent baseline was trained according to highest average performance over the last 100 episodes of a single training run of 25000 episodes for the 1 decision environment, and 50000 episodes for the 2 decision environment. In each case learning rate was selected from {0.05 · 2 −x : x ∈ {0, ..., 9}} and layer width was selected from {5, 10, 15, 20}. For the 1 decision environment we ran the recurrent baseline for 3 repeats, for the 2 decision environment due to higher variance we ran it for 10 repeats. This baseline is not intended to be representative of the performance of all possible architectures based on RNN variants trained with backpropagation through time, but merely to provide context for the main experimental results of this work. Results and descriptions of the experiments are shown in figures 3, 4 and 5, in each plot the x-axis shows number of training episodes. One additional experiment with twice the environment length is shown in appendix E. Notice that in each case the episodic memory learner was is able to learn a good query policy, drive the write weight of the uninformative states to near 0 while keeping the value for informative states much larger, and obtain close to perfect average return. Comparing figures 3 and 4 it appears that the addition of redundant memory size may accelerate initial learning though it has little effect on the overall convergence time. Comparing figures 4 and 5 the number of episodes to converge appears to roughly double from approximately 25, 000 to 50, 000 with the addition of the extra decision state but the training remains quite stable. We present a novel algorithm for integrating a form of external memory with trainable reading and writing into a RL agent. The method depends on the observation that if we restrict the information stored in memory to be a set of past visited states, the information recorded also provides the context in which it was recorded. This means it is possible to assign credit to useful information without needing to backpropagate through time to when it was recorded. To achieve this we devise a reservoir sampling technique which uses a sampling procedure we introduce to generate a distribution over memory configurations for which we can derive gradient estimates. The whole algorithm is O(n) in both the number of trainable parameters and the size of the memory. In particular neither memory required nor computation time increase with history length, making it feasible to run in an online RL setting. We show that the resulting algorithm is able to achieve good performance on a toy problem we introduce designed to have sharp long-term dependencies which can be problematic for recurrent models. Working out the second term: DISPLAYFORM0 Where we are able to drop DISPLAYFORM1 because the immediate reward is independent of the state in memory once conditioned on the action. Thus we finally arrive at: DISPLAYFORM2 Working out the second term: DISPLAYFORM3 So all together we get: DISPLAYFORM4 C PROOF OF LEMMA 1 Lemma 1. Selecting elements sequentially according to equation 12 will result in a vectorT whose elements correspond to a sample drawn from equation 11.Proof. Selecting elements sequentially according to equation 12 gives the following probability for a given vectorT . DISPLAYFORM5 T ∈( DISPLAYFORM6 To complete the proof note that this is one of n! vectors with the same set of elements in different order, each of which will have equal probability, hence to obtain the probability for the corresponding set we simply have to multiply by n! which gives us equation 11. We divide the proof into a series of lemmas. First we will define some notation to facilitate referencing algorithm 1 in the proofs below. Let T t be the set {0, ..., t − 1} andT t [0 : i − 1] be the value of T [0 : i − 1] at the call to UPDATE with parameter t. Note thatT t [0 : DISPLAYFORM0 be the values of Ω[i] andΩ[i] respectively, at the call to UPDATE with parameter t. Let P t,i be the value of P when it is set in loop index i of the loop starting at line 4 within the call to UPDATE with parameter t. Let Ω t,i and Ω t,i be the values of Ω and Ω respectively after they are set within index i of the loop starting at line 4 within the UPDATE call with parameter t. Let ω t,i and τ t,i be the values of ω and τ respectively at the beginning of loop index i of the loop starting at line 4 within the call to UPDATE with parameter t. Note that ω t,i = w τt,i . Lemma 2. DISPLAYFORM1 By design T t+1 = T t ∪ {τ t,0 }. Towards a proof by induction assume that after choosing whether or not to swapT t [i] we have: DISPLAYFORM2 Then on the next iteration either we swapT [i] for τ t,i or we don't. If we do swap then DISPLAYFORM3 On the other hand if we do not swap then DISPLAYFORM4 Which suffices to complete the inductive proof. Lemma 3. DISPLAYFORM5 Proof. The proof follows from noting that the first sum on the right side includes every term of the left sum whereT does not containt, while the second term on the right side is equivalent to summing over thoseT in the left sum that do containt. Lemma 4. For t ≥ n: DISPLAYFORM6 wt, ∀i ∈ {0, ..., n} and alsõ DISPLAYFORM7 Proof. Towards a proof by induction, assume the lemma holds at time t, a quick trace through algorithm 1 will show that the update leading to Ω t+1 [i] for i ∈ {0, ..., n − 1} is always: DISPLAYFORM8 From here we can apply lemma 3, along with lemma 2 as follows to get the desired result: DISPLAYFORM9 Now note thatΩ t [n] = 1 for all t which is also the correct value thus we have completed the induction step for the first half of the lemma. On the other hand the update leading toΩ t+1 [i] is as follows: DISPLAYFORM10 As a second level of induction assume the lemma holds forΩ t+1 [i + 1] then applying lemma 3 we get:Ω DISPLAYFORM11 As the base case for this second level of induction, note thatΩ t+1 [n − 1] = 1 for all t which is also the correct value, thus assuming Ω t+1 is correct we will also get the correct values forΩ t+1 . This completes the induction step for the lemma, it remains to prove the base case. Note that Ω[n] andΩ[n − 1] each start at 1. The beginning of the algorithm before line 19 is then intended to initialize all Ω andΩ values to have the correct value at time t = n, to see that this is the case, first note ∀i ∈ {0, ..., n}: DISPLAYFORM12 And also, by induction on the trivial i = n − 1 case, ∀i ∈ {0, ..., n − 2}: DISPLAYFORM13 Thus indeed the lemma holds at time n which serves as a base case for the rest of the proof. DISPLAYFORM14 Proof. Substituting the definition from equation 12, along with the value assigned to P t,i and simplifying slightly what we wish to show is: DISPLAYFORM15 Substituting in the values of Ω t [i] and Ω t+1 [i] from lemma 4 into the above formula, it will suffice to apply lemma 3 and lemma 4 to additionally show: DISPLAYFORM16 The first is a simple application of lemma 2. The second follows from a similar observation in addition to noting thatT t [i] has been removed from each term. For i = n − 1, Ω t,i = 1 which trivially obeys the same formula. Lemma 6. P t,i ≥ 0.Proof. DISPLAYFORM17 T ∈( DISPLAYFORM18 T ∈( DISPLAYFORM19 It is relatively straightforward to show that the lemma holds in this last form. To do so note that except for terms for whichT andT are identical on the left (which are not possible on the right), each term on the left of the inequality is also present on the right, however the number of repetitions of each term varies between the left and right. In the left sum if a term includes m values shared betweenT andT , this term will appear DISPLAYFORM20 times. This is because we can choose n − i − m non-duplicate values to be inT and place the rest inT , each of these permutations will correspond to a term in the sum. On the other hand in the left sum if a term includes m values shared betweenT andT , this term will appear 2(n−i−1−m) n−i−2−m times. Similarly this is because in this case we can choose n − i − 1 − m non-duplicate values to be inT and place the rest inT , each of these permutations will correspond to a different term in the sum. DISPLAYFORM21 N −1 , ∀N every term which is present on the right side is present on the left with more repetitions and thus the left side must be greater than the right and the lemma holds. This lemma shows that P is indeed a valid probability, which means that swapping according to it in algorithm 1 is admissible. DISPLAYFORM22 where [t 0 , ..., t i ] is an arbitrary vector of unique elements of T t .Proof. LetT i,t be the value ofT right before making the swap decision on line 12 in loop index i of the loop starting at line 4 within the call to UPDATE with parameter t. Towards a proof by induction assume that at time index t directly prior to making the swap decision forT [i] at line 12 of UPDATE we have for any arbitrary vector [t 0 , ..., t i−1 ] of unique elements of T t : DISPLAYFORM23 and for any arbitrary vector [t 0 , ..., t i−1 ] of unique elements of T t+1 : DISPLAYFORM24 That is all elements ofT from 0 to i − 1 have the desired probability conditioned on proceeding elements ofT t+1 while all elements from i to n − 1 still have the desired probability when conditioned on proceeding elements ofT t . This is a natural inductive assumption given we have already made our swap decisions up to but not including i and are just about to make our decision for i. Which completes the inductive step. To prove the base case note that we initializeT such that at time n it is filled with all available items in random order. It is easy to show that equation 12 implies that the probability of any ordering of a given setT is equal thus if the items in T exactly fillT then ordering them at random will give the desired probabilitiesP (T n [i]|T t+1 [0 : i − 1]; T t+1 , n), ∀i s.t. 0 ≤ i ≤ n − 1, which gives us the base case to complete the inductive proof. E LENGTH 20 ENVIRONMENT EXPERIMENT FIG3 shows the results of an experiment on the secret informant problem with environment length 20. Comparing figures 5 and 6 the number of episodes to convergence increases from 50, 000 to around 80, 000 with a doubling of the environment length while training still remains stable. corresponds to the uninformative indicator, to the informative indicator, • to the first decision state identifier, to the second decision state identifier. (d) shows the same thing but for the query generated in the second decision state.
External memory for online reinforcement learning based on estimating gradients over a novel reservoir sampling technique. The paper proposes a modified approach to RL, where an additional "episodic memory" is kept by the agent and use a "query network" that based on the current state.