{'fraction_non_alphanumeric': 0.02827016480551289, 'fraction_numerical': 0.013118020673336377, 'mean_word_length': 4.872745002437835, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sequential Episodic Control

State of the art deep reinforcement learning algorithms are sample inefficient due to the large number of episodes they require to achieve asymptotic performance. Episodic Reinforcement Learning (ERL) algorithms, inspired by the mammalian hippocampus, typically use extended memory systems to bootstrap learning from past events to overcome this sample-inefficiency problem. However, such memory augmentations are often used as mere buffers, from which isolated past experiences are drawn to learn from in an offline fashion (e.g., replay). Here, we demonstrate that including a bias in the acquired memory content derived from the order of episodic sampling improves both the sample and memory efficiency of an episodic control algorithm. We test our Sequential Episodic Control (SEC) model in a foraging task to show that storing and using integrated episodes as event sequences leads to faster learning with fewer memory requirements as opposed to a standard ERL benchmark, Model-Free Episodic Control, that buffers isolated events only. We also study the effect of memory constraints and forgetting on the sequential and non-sequential version of the SEC algorithm. Furthermore, we discuss how a hippocampal-like fast memory system could bootstrap slow cortical and subcortical learning subserving habit formation in the mammalian brain.


Introduction
The increasing popularity of Deep Reinforcement Learning (DRL) in recent years has been driven by its ability to reach human-level performance in several domains that were traditionally considered as hallmarks of human intelligence. Beating world-champions in games like chess and Go Silver et al. [2018], or more recently, in complex real-time games like Starcraft Vinyals et al. [2019] and DOTA Berner et al. [2019] are signatures of such human-like capacity. However, in order to achieve such remarkable feats, these algorithms require orders of magnitude more data to learn from than humans Lake et al. [2017].
The sample inefficiency problem in DRL refers precisely to the huge amounts of data that these methods require to reach a comparable level of performance Marcus [2018]. In the case of the classic Atari games, DRL systems require millions of samples to reach human-level results Mnih et al. [2015]. In more recent scenarios involving complex tasks, the amounts of samples can reach up to several billion Baker et al. [2019]. Several sources of slowness have been already identified in these types of algorithms Botvinick et al. [2019]. One pertains to an intrinsic feature of such systems: the gradient-based updates that slowly drive learning of both policy and value functions limit the speed at which these systems can achieve optimal performance. Episodic Reinforcement Learning (ERL) algorithms propose a way to overcome this limitation by introducing a memory system that allows the algorithm to make use of previously successful experiences to bootstrap the learning of an optimal policy Hansen et al. [2018], Zhu et al. [2019], Lin et al. [2018], Lee et al. [2018]. Episodic Control algorithms, on the other hand, propose an alternative approach that gets rid of the gradient-based methods and directly uses the stored events in memory for action selection Blundell et al. [2016], Pritzel et al. [2017].
This form of fast episodic control is grounded in the role that the hippocampus plays in learning and decision-making Lisman and Redish [2009], Gershman and Daw [2017]. Indeed, the hippocampal memory system can be used to guide sequential decision-making Clayton and Dickinson [1998], Foster andKnierim [2012]. Further, empirical evidence also supports its role in experience replay of rewarded sequences Mattar and Daw [2018], suggesting a key role in bootstrapping and biasing learning in other subsystems. However, most ERL models do not capitalize on the sequential nature of the temporal unfolding of events that is in turn reflected in the structure of hippocampal memory Buzsáki and Tingley [2018]. Notably, states in ERL are treated as being independent of one another, instead of being experienced, stored and retrieved in a sequential manner Hansen et al. [2018], Zhu et al. [2019], Lin et al. [2018], Lee et al. [2018], Blundell et al. [2016], Pritzel et al. [2017].
Moreover, linked to the problem of sample and computational efficiency, memory-based systems also face a problem of memory efficiency. Studying the effects of imposing constraints on the memory capacity of episodic reinforcement learning models is something that previous approaches have not considered Ramani [2019], with the recent exception of Yalnizyan-Carson and Richards [2021]. The efficient use of a limited memory capacity is especially critical when embedding such algorithms in embodied systems such as robots that face strict computational and storage limitations Khamassi [2020] -a problem that human cognition also had to deal with Lisman and Idiart [1995], Jensen and Lisman [2001].
In this paper, we explore the role of sequentiality and memory capacity in Episodic Control. We demonstrate how imposing a sequential bias on the retrieval of memories for action selection favours both overall performance and sample efficiency in a foraging task. Moreover, we also show how the sequential inductive bias enhances memory efficiency by an order of magnitude compared to the same episodic control model without such a feature.

Related work
The goal of a reinforcement learning agent is to maximize reward acquisition through its interaction with the environment Sutton and Barto [2018]. This is usually operationalized as maximizing the expected discounted return R t = T k=0 γ k r t+k , where T is the length of an episode and γ (0, 1] is the discount factor. In a given state s t S, the agent takes an action a t A following a policy π(s t, a t ) which brings about a reward r t+1 R and a novel state of the environment s t+1 . In Q-learning Watkins and Dayan [1992], the agent learns the action-value function Q π (s, a) = E[R t |s t = s, a] by computing the expected rewards obtained by acting in a given state. In DQN, this function is parametrized by a deep neural network that uses previous experiences stored in a buffer to update its policy Mnih et al. [2015].
Most of the previous work on ERL has tried to improve the sample efficiency of such parametric model either by bootstrapping its learning through an extended memory system or by value propagation methods that capitalize more on the experiences that yielded higher rewards in the past. Episodic Memory Deep Q-Network (EMDQN) adds a memory buffer parallel to a Deep Q-Network, having coordinated systems that lead to faster reward propagation and higher sample efficiency than the standard Deep Q-Network Lin et al. [2018]. Episodic Backward Update propagates the value of a state to its previous states after sampling a complete episode Lee et al. [2018]. This allows achieving the same mean human normalized performance just by using 5% of the data. Episodic Reinforcement Learning with Associative Memory (ERLAM) stores the different trajectories in a graph instead of a dictionary and associates together different nodes to create an instance-based reasoning model that is more sample efficient Zhu et al. [2019].
In contrast with the previous approaches, Model-Free Episodic Control (MFEC) tries to get rid of the gradient-based methods using a non-parametric or instance-based way of learning Blundell et al. [2016]. It records highly rewarding experiences in a tabular memory and follows a policy that capitalizes on those stored events. MFEC updates its estimates by storing in memory the highest Q values experienced in that state. When given a state, the system reconsiders its memory and picks the action that gave the highest reward. For novel states, the mean of the k state neighbours is calculated. Neural Episodic Control builds upon MFEC by realizing a differentiable neural dictionary (DND) in order to give better estimates Pritzel et al. [2017].
The Sequential Episodic Control (SEC) model that we present in this paper departs from the previous literature by storing the complete sequence of state-action couplets (i.e., events) leading to rewards, instead of storing the events as isolated memory units. An exception here is ERLAM, which does not treat events as being independent. However, the main difference between the SEC and ERLAM is that whereas the latter builds a graph based on the state transitions of the stored experiences to bootstrap the learning of a parametric RL agent, the former uses the memory directly for action selection and control.
In non-parametric algorithms such as MFEC, there is no issue of bootstrapping and temporal credit assignment like in the gradient cases, nor the computationally costly tree search of model-based planning. SEC also follows a non-parametric approach to episodic control, using a sequential episodic tabular memory to store previously rewarded experiences to guide decision-making when encountering similar states. Therefore, SEC departs from the previous episodic control models in three significant ways. First, in how it deals with the perceptual similarity between states. Second, in how the action-value and the policy functions of a given state are computed based on the similar experiences stored in memory. Third, in how action selection occurs based on a memory-driven policy.

Sequential Episodic Control
The SEC model is composed of a short-term buffer E, a long-term episodic memory EC, and an action selection algorithm (see Algorithm 1). The short-term buffer transiently stores the most recent sequence of state-action couplets (i.e., events) encountered by the agent, and it is updated following a first-in, first-out rule. Upon encountering a reward, the current sequence maintained in the buffer is transmitted and stored in the EC along with its associated reward value. In this implementation, the short-term buffer has a fixed length of 50 state-action couplets.
Algorithm 1 Sequential Episodic Control E: episodic buffer EC: episodic memory for each episode do The action selection algorithm selects an action based on the recent history of observed states and performed actions. Concretely, at every time step, the observed state is compared, based on a similarity metric (i.e., Euclidean distance), to all the state representations stored in EC (see Eq. 1). The similarity scores are then weighted by a sequential bias term B, which keeps track of the recent history of selected state-action couplets (see Eq. 2). The sequential bias matrix B computes, at each timestep, the bias term for each of the state-action couplets stored in the long-term memory EC. It is initialized with values of 1 for each stored couplet. Values above one decrease by 0.0005 with every timestep. The bias term of the elements of a sequence following a previously selected couplet is increased by 0.01. This procedure increases the eligibility of the couplets that come immediately after the recently selected ones. Hence, the resulting eligibility scores G are in this way biasing the final action selection towards continuing recently visited sequences in EC. In addition, this biasing mechanism is further reinforced by behavioural feedback Verschure et al. [2003], whereby the input sampling caused by the selected action favours the storage of similar sequences of state-action couplets.
After that, a set of state-action couplets in memory is retrieved based on their eligibility scores G surpassing both absolute and proportional thresholds (see Eq. 3). Only the retrieved memories that pass both thresholds will contribute to action selection. This procedure enforces a winner-takes-all mechanism that has been shown to operate in the hippocampus de Almeida et al. [2009].
The selected set of candidate state-action couplets C is then assigned the reward values associated with their corresponding sequences, weighted by an exponential decay based on each couplet's normalized distance to the end of the sequence (see Eq. 4). This mechanism favours the selection of actions that are closer in time to bigger rewards. Moreover, the reward values assigned to each couplet are normalized to the maximum reward associated with the selected couplets, thus implementing a relative reward valuing function.
Lastly, the final action to be performed is randomly drawn from the probability distribution generated over the discrete action space by normalizing the sums of all the relative reward values associated with the actions of each selected couplet (see Eq. 5).
As in previous approaches Blundell et al. [2016], we use an embedding function φ to build compressed feature representations s t of the observations o t obtained from the environment s t = φ(o t ). In our experiments, we firstly train a convolutional autoencoder for 10.000 episodes using random exploration and then we freeze the weights for the experimental phase (see Appendix II on page 11 for more details). All models presented in this paper use the same model as the embedding function.

Results
We have implemented the SEC model on the AnimalAI testbed Beyret et al. [2019]. Agents in this setup (see Fig. 1) receive at each timestep the first-person visual observations from the environment of 84 by 84 pixels. The action space is composed of a 2-d vector of integers that allows values from 0 to 2. The first value of the vector represents the forward-backwards axis, and the second value the left-right axis. Actions are automatically repeated for 4 timesteps to reduce computational requirements.
The task is a double T-maze with a sparse reward structure. This task requires the sequential encoding and retrieval of relevant visual cues to reach the reward location in a minimal amount of time. In each episode, the agent randomly starts at one of the corners, and it must reach the centre of the maze to obtain a reward. The reward at the centre is the only positive reward (+3) available in the environment. Due to the walls of the maze, the agent does not see the reward directly and needs to explore the maze first. At each timestep, the reward value decreases by 0.001 to promote efficient trajectories. The episode finishes when the agent gets the reward or if 1000 timesteps are reached.  We ran 20 simulations of 5000 episodes comparing the SEC algorithm against a control version of the model (NSEC) that does not incorporate the sequential bias in action selection (i.e., B matrix being all 1's and not being updated), and against a baseline episodic control benchmark Blundell et al. [2016], Model-Free Episodic Control (MFEC). A standard grid parameter search was performed to set the values of SEC and NSEC models. The precise hyperparameters used in this experiment can be found in Appendix I, on page 11. For the MFEC, we followed the implementation described in Blundell et al. [2016].
The results show that SEC maximizes reward acquisition in 1.000 episodes (see Fig. 2). There is a clear improvement in the performance of the SEC model in comparison with the MFEC benchmark, as well as with its ablated version, NSEC. SEC reaches not only higher levels of reward, but also gets faster to such level of performance, thus making it more sample-efficient. Interestingly, we can also observe that NSEC reaches similar levels of reward to those of MFEC. These results also demonstrate that the significant increase in performance of SEC is due to its sequential bias term.

Effect of memory constraints on Sequential and Non-Sequential Episodic Control
To analyze the effect that memory constraints impose on the Sequential Episodic Control algorithm, we tested the standard (SEC) and ablated (NSEC) version of the model with varying limits of memory capacity (i.e., a fixed EC memory of 125, 250, 500 and 1000 sequences). Therefore, once the memory was filled, no further memories could be stored. The results show that SEC maximizes reward acquisition in around 1.000 episodes, for all tested memory conditions (see Fig.3). There is a clear improvement in the performance of the SEC model with respect to its nonsequential version, NSEC, in all conditions. As before, SEC reaches not only higher levels of reward but also gets faster to such levels of performance. The results also show how the bootstrapping effect of the behavioural feedback takes place by looking at the differences in the time it takes for each model to fill their EC memory. This difference also increases across models when the memory capacity limit is increased. In all cases, the performance plateaus shortly after reaching the memory capacity (as indicated by the vertical bars on Fig.3). Importantly, the decrease in mean entropy shows that SEC stabilizes its policy, whereas NSEC does not, maintaining a high policy entropy in all conditions despite increasing reward acquisition. Thus, the sequential bias component of SEC not only allows the agent to achieve higher rewards but also provides a behaviour stabilization mechanism. A similar conclusion can be drawn from the analysis of the entropy over the policy of the SEC model, indicating that indeed agents using this model quickly converged to a stable policy. It is also important to note that the degree and speed of convergence are significantly affected by the memory constraints. The entropy of the NSEC model is overall much higher, although in this case there is also a consistent reduction when the memory capacity is increased, indicating an improvement in the stabilization of the policy that also is reflected in the increased reward acquisition.
Finally, we systematically compare the performance of each memory condition of NSEC against SEC to have a detailed estimate of how much performance increase is obtained using the sequential bias. The last results (Fig.4) present a table comprising this analysis. The data shows that the SEC model can reach a similar level of performance than its non-sequential version, NSEC, with an order of magnitude less memory capacity. This result is key for episodic control algorithms, because sample efficiency in these models is also translated into memory efficiency and, therefore, it also has implications in terms of computational time. Importantly, this has direct implications on the capacity of these systems to scale up to more complex tasks.

Effect of forgetting on Sequential and Non-Sequential Episodic Control
The previously described models were tested with a fixed EC buffer to assess the effect of memory constraints on the performance of the models. In this experiment, we study how adding a forgetting mechanism affects the models' performance. We use a FIFO rule (first-in, first-out) on both the SEC and NSEC models, to test whether the non-sequential model with the addition of the FIFO forgetting mechanism is able to reach SEC-level performance. As we see in Fig.5, the NSEC algorithm does not yield the same results as applying a sequential bias, like in SEC, with a fixed EC buffer. It is true, however, that the addition of forgetting does increase the overall performance of both models. Its effect can also be observed in the reduced entropy observed on the policy distribution of both models.

Discussion
In this paper, we have shown how a non-parametric Sequential Episodic Control (SEC) algorithm can to reach sample-efficient performance compared to episodic controllers that stores state-action couplets as independent elements in memory (MFEC, NSEC). We have also systematically studied the effect of memory capacity constraints on such algorithms and showed how the SEC model outperforms a control version that does not incorporate a sequential inductive bias.
With this work, we seek to contribute to the available proposed solutions to the sample-inefficiency problem in reinforcement learning by taking inspiration from empirical and theoretical research from the cognitive sciences. This work also extends the possibilities of Episodic Control algorithms by showing how leveraging the sequential nature of the stored experiences improves sample and memory efficiency during learning. In contrast with standard RL methods, the main driver of policy learning in SEC is the constant acquisition and retrieval of new sequential memories. In other words, the behavioural policy of an SEC agent is implicitly updated by the memories it forms during its interaction with the environment. Precisely due to his fact, the performance of this type of model is sensible to memory constraints, and therefore can also benefit from the implementation of adequate forgetting mechanisms, as shown in this work, and also studied in Yalnizyan-Carson and Richards [2021].
Moreover, SEC emphasizes the learning of complete behavioural sequences, whereas ERL usually treats its memory units as disconnected events. The incorporation of this hippocampus-inspired architectural bias bootstraps the formation of a behavioural feedback loop Verschure et al. [2003], allowing SEC to rapidly transition from an initial exploration phase to a more exploitative phase in which the behaviour of the agent stabilizes over time while maximizing reward acquisition.
The capacity of Episodic Control algorithms like SEC to quickly exploit past successful strategies can also be very useful in multi-agent environments to help in dealing with the non-stationarity problem caused by the continually changing policies of the learning agents Papoudakis et al. [2019], Freire et al. [2020a]. Moreover, this type of sequential memory can also help in the formation of better internal models of other agents Albrecht and Stone [2018], Freire et al. [2018a,b], by building a sequential memory of past social interactions.
Although in this paper we have only shown the capacity of this model for control, it could also be implemented in combination with other learning algorithms to bootstrap their learning phase with a good set of successful samples, as shown in previous work Lin et al. [2018], Lee et al. [2018]. Moreover, those applications (control and learning) do not need to be exclusive, and the combination of both is possible. Episodic Control models could drive the behaviour during the initial stages of learning, by rapidly latching onto successful experiences, while the slow learning algorithms could use the growing set of successful samples obtained by the episodic controller to speed up the acquisition of an optimal policy.
In nature, complex organisms make use of different learning, memory and decision systems in an adaptive manner Verschure [2012]. Model-based planning requires that a model of the environment has been formed. However, planning usually takes a long time and it is not always the best solution. Also, it relies on a prior acquisition of that model. Habitual or model-free behaviours are much faster and therefore more suitable for contexts in which fast decisions need to be made. They do not rely on the acquisition of a model; however, they also take longer to be learned Daw [2018].
In situations when an animal is exploring a novel environment, and no model or habit has yet been formed, relying on fast, instance-based learning could be useful. An episodic controller operates by remembering the action that led to the best outcome in a given state. It is computationally lighter than model-based algorithms, and do not suffer from too much uncertainty or noise due to the complex calculations involved in forward search Lengyel and Dayan [2008].
Each of these learning systems has its trade-offs, derived from its intrinsic properties and inductive biases. By their very nature, these control systems have an optimal performance at different stages of the learning process of the agent and could be operating at different timescales Botvinick et al. [2019]. Understanding the regimes in which they optimally operate and how they combine to attain adaptive behaviour is of paramount importance if we aim to build complex synthetic cognitive systems able to exhibit distributed adaptive control Freire et al. [2020b].