{'fraction_non_alphanumeric': 0.03001054852320675, 'fraction_numerical': 0.009731012658227848, 'mean_word_length': 4.653943640972119, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cell-Free Latent Go-Explore

In this paper, we introduce Latent Go-Explore (LGE), a simple and general approach based on the Go-Explore paradigm for exploration in reinforcement learning (RL). Go-Explore was initially introduced with a strong domain knowledge constraint for partitioning the state space into cells. However, in most real-world scenarios, drawing domain knowledge from raw observations is complex and tedious. If the cell partitioning is not informative enough, Go-Explore can completely fail to explore the environment. We argue that the Go-Explore approach can be generalized to any environment without domain knowledge and without cells by exploiting a learned latent representation. Thus, we show that LGE can be flexibly combined with any strategy for learning a latent representation. We show that LGE, although simpler than Go-Explore, is more robust and outperforms all state-of-the-art algorithms in terms of pure exploration on multiple hard-exploration environments. The LGE implementation is available as open-source at https://github.com/qgallouedec/lge.


Introduction
RL algorithms aim to learn a policy by maximizing a reward signal. In some cases, the rewards from the environment are sufficiently informative for the agent to learn a complex policy, and thus achieve impressive results, including world level in Go , StarCraft (Vinyals et al. 2019), or even learning sophisticated robotic tasks (Lee, Hwangbo, and Hutter 2019). However, many realworld environments provide extremely sparse (Bellemare et al. 2016), deceptive (Lehman and Stanley 2011) rewards, or none at all. In such environments, random exploration, on which many current RL approaches rely, may not be sufficient to collect data that is diverse and informative enough for the agent to learn anything. In these cases, the agent must adopt an efficient exploration strategy to reach high reward areas, which may require a significant amount of interaction with the environment.
Recently, Ecoffet et al. (2021) introduced a new paradigm in which a goal-conditioned agent is trained to reach states it has already encountered, and then explore from there. The agent thus iteratively pushes back the frontier of its knowledge of the environment. We call this family of algorithms return-then-explore. Ecoffet et al. (2021) provide Go-Explore, an algorithm of this new family, that outperforms by several orders of magnitude the state-of-the-art scores on the game Montezuma's Revenge, known as a hardexploration problem. Go-Explore relies on a grouping of observations into cells. These cells are used (1) to select target observations that are at the frontier of yet undiscovered states and (2) to build a subgoal trajectory that the agent follows to reach the final goal cell. As Ecoffet et al. (2021) initially spotted, the cell design is not obvious. It requires detailed knowledge of the observation space, the dynamics of the environment, and the subsequent task. If any important information about the dynamics of the environment is missing from the cell representation, the agent may fail to explore at all. For example, in Montezuma's Revenge, possession of a key is a crucial piece of information that when included in the cell representation increases exploration by several orders of magnitude. We also show in Appendix B that the cell design has a major influence on the results.
In this paper, we present Latent Go-Explore (LGE), a new algorithm derived from Go-Explore which operates without cells. This new algorithm meets the definition of a returnthen-explore family of algorithms since the agent samples a final goal state at the frontier of the achieved states, returns to it, and then explores further from it. Our main contribution consists of three major modifications.
• A latent representation is learned simultaneously with the exploration of the agent to provide the most up-to-date and informative representation possible. • Sampling of the final goal is based on a non-parametric density model in latent space. This leverages the learned latent representation for sampling the states of interest to be reached. • The subgoal path pursued by the agent is reduced using a characteristic latent distance.
These three modifications, detailed in Section 3, allow us to generalize the Go-Explore approach to any continuous high-dimensional environment. It also allows to automate the encoding of the observation into an informative latent representation, and thus get rid of the tedious work of designing by hand a cell representation. The end-to-end architecture of LGE is presented in Figure 1.
To evaluate LGE, we place ourselves in the context of reward-free exploration in two hard-exploration environments: a maze and the control of a robotic arm interacting with an object. LGE is compatible with any type of latent Store the encountered observations Figure 1: End-to-end learning architecture of LGE. The encountered observations are encoded in a latent space. A latent density is estimated. A final goal is sampled from the states already reached, by skewing the distribution with the density. A goal-conditioned agent is trained to reach this goal by pursuing a sequence of subgoals, derived from the experiment that led to the final goal. Once the agent has reached the final goal, it explores from it with any exploration strategy.
representation learning. We show two of them in this paper: one based on inverse dynamics, and the other on an auto-encoding mechanism. We show in Section 4.4 that for the two environments studied, LGE outperforms all stateof-the-art algorithms, and in particular Go-Explore for the exploration task.

Preliminaries
Markow Decision Process This paper uses the standard formalism of a discounted Markov Decision Process (MDP) defined as the tuple (S, A, P, R, γ, ρ 0 ) where S is the set of states, A is the set of actions, P : S × A → S is the (unknown) transition function providing the probability distribution of the next state given a current state and action, R : S × A × S → R is the reward function, γ is the discount factor and ρ 0 is the initial distribution of states. A policy, denoted π(·|·) : S × A → R + is the probability distribution such that π(s|a) is the probability of selecting action a ∈ A in state s ∈ S. We denote the previously defined values with discrete time t such that s t , a t and r t denote respectively the state, action, and reward at timestep t. The aim is to learn a policy π that maximises the long-term expected reward E[ +∞ t=0 γ t r t ]. Goal-conditioned MDP We note that every MDP can be augmented into a goal-conditioned MDP with a goal space G and an initial goal distribution ρ g . At each timestep, the observation is augmented with a goal and the reward function depends on this goal. A goal-conditioned policy (Kaelbling 1993), denoted π(·|·, ·) also depends on the goal.

Related Work
Exploration in RL can be divided into three types (Ładosz et al. 2022): random exploration, intrinsic rewards-based methods, and goal-based methods.
Random exploration In random exploration, the agent does not follow a specific exploration approach. The agent's actions can be purely random, or in the continuous case, augmented by exploration noise parametrized by the current state (Haarnoja et al. 2018) or not (Lillicrap et al. 2016).
Intrinsic rewards-based methods Intrinsic rewardsbased methods are inspired by intrinsic motivation from cognitive science (Oudeyer and Kaplan 2009). They consist in adding an additional reward (called intrinsic) to the reward signal from the environment (called extrinsic). This intrinsic reward is intended to foster exploration. It can be based on the state visitation count (Bellemare et al. 2016;Machado, Bellemare, and Bowling 2020) or on the prediction error of a model learned from the collected data (Houthooft et al. 2016;Pathak et al. 2017;Achiam and Sastry 2017;Pathak, Gandhi, and Gupta 2019;Burda et al. 2019;Tao, Francois-Lavet, and Pineau 2020).
Goal-based methods Methods that modify the reward of the environment provide no mechanism for distilling the knowledge gained from visiting various states. Agents visit new states, and they quickly forget them when other states become newer. In contrast, recent work suggests the use of a goal-conditioned autotelic agent specifically trained for the exploration task allows to use this knowledge for the realization of new user-specified goals (Levine 2021;Colas et al. 2022). The reward signal is ignored during the exploration phase. After the exploration phase, the data collected by the agent are used to learn one or more subsequent tasks (Jin et al. 2020). In goal-based methods, the agent is conditioned by a goal that is used to guide exploration towards unknown areas. These methods rely on a goal generator to create goals for the agent. We divide goal-based methods into two categories: exploratory goal methods and goals to explore from methods.
Exploratory goal methods follow the intuition that the agent discovers new areas of the observation space by pursuing goals that have been little or not achieved before. The challenge of these methods is to choose the goal to be neither too easy nor too hard. The literature contains several ways to approach this trade-off. Some methods sample goals that either maximize Learning Progress (Colas et al. 2019;Portelas et al. 2020) or value disagreement (Zhang, Abbeel, and Pinto 2020). Other methods sample goals from the least visited areas using a parametric density model on the visited states (Pong et al. 2020). It is also possible to imagine goals that have never been reached using a language model (Colas Build a subgoal trajectory τ g using Equation (4).

5:
while the last goal of τ g is not reached do 6: Collect interaction using π(·|·, τ g i ) and store it into dataset D.

7:
if subgoal τ g i is reached, i.e. ||φ(s t ) − φ(τ g i )|| < d then 8: Move to the next subgoal: i ← i + 1. Explore until the end of the episode with any exploration strategy.

12:
Update policy π with any off-policy algorithm and HER.

13:
Every update encoder freq timesteps, update encoder φ with any representation learning algorithm. 14: end while 15: return the goal-conditioned policy π and the dataset D.
In goals to explore from methods the agent sample a goal from previously visited states. It returns to it, either by teleportation (Ecoffet et al. 2019;Matheron, Perrin, and Sigaud 2020), or with goal-conditioned policy (Ecoffet et al. 2021). The challenge of these methods is to choose a goal that is of high exploratory interest. Similarly, some methods estimate the density of the encountered states, either with parametric methods (Pitis et al. 2020) or with non-parametric methods (Ecoffet et al. 2021;Matheron, Perrin, and Sigaud 2020), to target the low-density areas.
In summary, methods based on a goal reaching policy should facilitate scalable RL. The stunning results of Go-Explore illustrate this point but remain circumscribed to few environments and require a lot of domain knowledge to work. By bridging with concepts already used in the intrinsic reward literature, we show a way to make this approach more general and simple.

Latent Go-Explore
LGE meets the definition of the return-then-explore family of algorithms. First, a final goal state is sampled from the replay buffer, then the agent learns a goal-conditioned policy to reach this goal. When the agent reaches the goal, the agent starts to explore. LGE learns a latent representation of observations and samples the goal pursued by the goalconditioned agent in priority in low latent density areas. In Section 3.1, we present how the latent representation of observations is learned. In Section 3.2, we show how the latent density is estimated and how the final goal state pursued by the agent is sampled. Finally, in Section 3.3, we show how   to build a subgoal trajectory from the final goal to increase the agent's performance, in particular in far-away goal situations. The pseudo-code of the resulting algorithm is presented in Algorithm 1.

Learning a latent representation
The literature contains several latent representation learning methods for RL. Learning such a representation is orthogonal to our approach. Thus, LGE can be combined with any learning method without the need for further modifications.
Choosing the best representation learning method given the environment is out of the scope of this paper.
In this paper, we present two methods of representation learning that have been found to work well with our test environments. These methods are inspired by the literature on intrinsic reward-based methods.
Inverse dynamic representation learning Pathak et al. (2017) proposed an intrinsic reward calculated based on the agent's prediction error of the consequence of its own actions. The representation is learned using two submodules. The first encodes the observation into a latent representation φ(s t ). The second takes as input φ(s t ) and φ(s t + 1) and outputs the prediction of the action taken by the agent at time step t. The parameters θ of the inverse model P inv θ are optimized by minimizing the loss function: The inverse dynamics representation learning allows getting a latent representation of the states containing only the aspects of the state on which the agent can have an influence.
Forward dynamic representation learning In Achiam and Sastry (2017), the intrinsic reward is calculated based on the prediction error of a model approximating the transition probability function of the MDP. Two submodules are used. The first one encodes the observation to a latent representation φ(s t ). The second takes as input φ(s t ) and a t and outputs the prediction of the next stateŝ t+1 . The model parameters θ are optimized by minimizing the loss function:

Density estimation for intrinsic goal sampling
The success of the proposed method relies on the agent's ability to generate for itself goals that it will be able to reach and then explore from there. For the agent to progress in the exploration of the environment, these goals must be at the edge of the yet unexplored areas. To identify these areas, we use an estimator of the density of latent representations of the encountered states. Moreover, we require the goal to be reachable. The set of reachable states is a subset of the state space that we assume to be unknown. The easiest way to satisfy the previous requirement is therefore to sample among the states that have already been reached. We estimate the density of latent representations of the encountered states (called latent density) using the particlebased entropy estimator originally proposed by (Kung, Lin, and Kao 2012) and used in the literature on intrinsically motivated RLs (Liu and Abbeel 2021b,a). This estimator has the advantage of being nonparametric and thus does not hinge on the learning capabilities of a learned model. Appendix C describes the details of the implementation of this estimator, denotedf .
Denote d i =f (φ(s i )) the estimation of the latent density of s i . Following Van der Vaart (1998), we denote the order (N ) , and denote the order statistic vector by X N,(·) . Let the rank R N,i be the position of d i in the order statistic, so in the absence of ties, d i = d N,(R N,i ) . Therefore, R N,i refers to the rank of s i in the latent density sorting of the encountered states.
The sampling of the final goal state follows a geometric law on the rank in the latent density sort. The probability to draw s i as the final goal state is where G is the random variable corresponding to the final goal state, and 0 p 1 is a hyperparameter controlling the bias towards states with a low latent density.
The representation is jointly learned with the exploration of the agent. Therefore, the latent density must be regularly recomputed to take into account the most recent representation on the one hand, and the recently visited states on the other hand. However, considering the slow evolution of this value, we choose to recompute the latent density only once every 5000 timesteps. This allows us to significantly reduce the computation needs while having a low empirical impact on the results.

Subgoal trajectory
As learning progresses, the sampled final goal states are increasingly distant. However, reaching a distant goal is challenging because it implies a sparse reward problem.
To overcome this problem, we condition the agent to successive intermediate goals τ g = (g 0 , g 1 ..., g L ) that should guide it to the final goal state g L . These intermediate goals are chosen from the trajectory that led the agent to the final goal state (s 0 , s 1 , . . . , s T ).
The trajectory that led the agent to the final goal state is unlikely to be optimal. Plus, if the agent is conditioned by the whole trajectory, it may fail to reach all of them, even though some of them may not be necessary to reach the final goal state. To allow the agent to find a better path to the final goal state, we remove some subgoals from this trajectory. To decide whether a subgoal should be removed from the trajectory, we evaluate the latent distance to the previous subgoal. If the distance is less than the threshold, then the goal is removed.
In contrast to Go-Explore, we do not use the best known trajectory that leads to the sampled goal area (cell). The main reason is that the best known trajectory may be particularly difficult to reproduce, due to the dynamics and the stochasticity of the environment. Consider a game in which two paths exist to a target position. The first one is short, but the environment kills the agent 9 times out of 10. The second one is longer but succeeds every time. If the agent always chooses the shorter path (like Go-Explore), it will fail to reach the target most of the time.
Once the goal is reached, the agent explores using any exploration strategy. For the sake of simplicity, we choose a random exploration strategy for our experiments. We also impose that the agent repeats the previous action with a probability of 90%. This technique has been shown to increase the results significantly (Ecoffet et al. 2021).

Experiments
To demonstrate the effectiveness of our method, we apply it to a range of pure exploration tasks. We focus on environments for which naive random exploration is not sufficient to explore the rich variety of reachable states.
We compare the results obtained with LGE with the results obtained using several algorithms based on intrinsic curiosity and others based on goal-directed strategies.
In terms of infrastructure, each run was performed on a single worker machine equipped with one CPU and one NVIDIA® V100 GPU + RAM 16 Gb of RAM.

Environments
Continuous maze We train an agent to navigate in a continuous 2D maze. The corresponding configuration is shown in Figure 5. The agent is initially at the center of the maze. At each timestep, the agent receives the current coordinates as an observation and chooses an action that controls its location change. If the agent collides with a wall, it returns to its previous position. The reachable space is a square of 12 × 12 and the agent's action is limited to [−1, 1] horizontally and vertically. The agent can interact 100 times with the environment, after which the episode ends and the agent returns to its initial position in the center of the maze.
Robotics environment Robotic environments are interesting and challenging application cases of RL, especially since the reward is often sparse. We simulate a Franka robot under the PyBullet physics engine using panda-gym (Gallouédec et al. 2021). Figure 3 depicts a rendering of the setup. The robot can move and interact with an object. The agent has access to the position of the end-effector and the position of the object, as well as to the opening of the gripper. The agent interacts 50 times with the environment and then the object and the robot arm are reset to their initial position.

Baselines
Random exploration Most RL methods from the literature do not follow any specific exploration strategy. In a reward-free context, the performance of the latter is often equivalent to a random walk. We will take as a baseline a random agent, whose actions are uniformly sampled over the action space at each timestep, Soft Actor-Critic (SAC; Haarnoja et al. (2018)) and Deep Deterministic Policy Gradient (DDPG; Lillicrap et al. (2016)).
Intrinsic reward-based exploration In this paper, we take as reference two widely used intrinsic reward-based methods combined with either SAC or DDPG. These methods stand out from the others because, despite their simplicity, they have demonstrated good performance on a wide variety of tasks.
• Intrinsic Curiosity Module (ICM; Pathak et al. (2017)): the intrinsic reward is computed as the mean square error between the true latent representation and the one predicted by a learned dynamic model given the action taken. The encoder is trained jointly with an inverse dynamics model. • Surprise (Achiam and Sastry 2017): the intrinsic reward is the approximation of the KL divergence between the actual transition probabilities and a learned transition model.
Goal-directed exploration We use the following algorithms as a baseline.
• Go-explore (Ecoffet et al. 2021): the agent discretizes the state space into cells, selects the least visited ones, returns to them using a goal-conditioned policy, and further explores from there. We use a constant cell generation strategy during learning, like the one proposed in the original paper for robotic tasks. Go-Explore is the closest baseline to our algorithm. Appendix D details the differences between LGE and Go-Explore. • Diversity Is All You Need (DIAYN; Eysenbach et al. ( 2019)): the agent is conditioned by a skill and a discriminator predicts the skill pursued by the agent. The more the discriminator predicts with certainty the skill pursued, the bigger the reward. Conjointly, the discriminator is trained to maximize the distinguishability of skills. • Skew-Fit (Pong et al. 2020): the agent's goal sampling is skewed to maximize the entropy of a density model learned on the achieved states.
For the goal-directed methods, we use Hindsight Experience Replay (HER; Andrychowicz et al. (2017)) relabeling which has shown to significantly increase learning.
To nullify the variation in results due to different implementations, we implement all algorithms in the same framework: Stable-Baselines3. (Raffin et al. 2021).
The set of intrinsic reward-based methods and goaldirected methods are underpinned by the same off-policy algorithm. The hyperparameters for this algorithm are identical. For the Maze environment, we use SAC, while for the robotic environment, we use DDPG as it gives better results for all methods. To negate the influence of a bad choice of hyperparameter on the results, the method-specific hyperparameters are optimized. Appendix A details the optimization process for all methods and the resulting hyperparameters.

Measuring the exploration
In this paper, we focus on the agent's ability to explore its environment in a pure exploration context, i.e. in the absence of extrinsic reward. This step is particularly important because, in the case of an environment with very sparse rewards, the agent can interact a large number of times with the environment without getting any reward. It is therefore necessary to follow an efficient exploration strategy to discover the few areas of the state space where the agent can get a reward. To be able to compare the results obtained by different methods in this context, it is necessary to use a common metric for the quality of exploration.  The literature uses many different metrics. Some papers use the average reward on a hard-exploration task (Ali Taïga et al. 2020), the zero-shot performance on a predefined task (Sekar et al. 2020) or monitor specific identifiable events in the environment that indirectly informs the degree of exploration (Gülçehre et al. 2020). We argue that these indirect measures are unsatisfactory because they rely on the subsequent learning ability of an online and offline agent respectively. For the discrete case, the authors use the number of unique states encountered (Ménard et al. 2021). However, we are working in a continuous framework and must therefore extend this idea by discretizing the continuous space. For both environments, we discretize the state space into bins. For the maze environment, we use a 24 x 24 grid. The possible positions being bounded and known, we report the coverage rate of the space. For the robotic environment, we use the position of the object and the gripper position that we discretize into 0.1 m bins in each dimension. We report the raw number of explored bins. Although arbitrary, we observe empirically that the choice of the discretization parameter has hardly any impact on the results obtained.
Following the guidelines of (Agarwal et al. 2021), we use for all plots in this paper the interquartile mean (IQM) with the 95% confidence interval. We also plot the performance profile, which is the empirical tail distribution function of the score at the end of the training.

Main Results
The exploration results for the Maze environment are presented in Figure 4. A rendering of the positions explored by the agent is presented in Figure 5. We note that only LGE and Go-Explore significantly outperform the results obtained with random exploration. This demonstrates the effectiveness of the return-then-explore paradigm in this environment. We note that exploration based on intrinsic curiosity does not yield significantly better results than those obtained by random exploration. We hypothesize that this is due to the simple dynamics of the environment that quickly converges the intrinsic reward to 0.0. Surprisingly, neither Skew-Fit nor DIAYN performs significantly better than random exploration. For DIAYN, we find that most of the skills were concentrated in the initial position area of the agent. Finally, we note that, although the cell size has been optimized, LGE significantly outperforms Go-Explore. LGE manages to cover almost the entire reachable space at the end of the runs while exhibiting low variability in the results.
The exploration results for the robotic environment are presented in Figure 6. We notice that LGE significantly out-  performs all other methods. Notably, Go-Explore performs only slightly better than random exploration. We note that Go-Explore does not learn to grasp the object throughout the learning process. The results presented on a robotic environment by Ecoffet et al. (2021) are much better. We presume this is mainly due to the meticulous work done on the state space examination and the induced cell design. Here, we use a naive grid-like cell design. Although the grid parameter is optimized, it does not yield good exploration results with this environment. We thus demonstrate the benefit of using a learned representation to automatically capture important features of the environment's dynamics.

Ablation study
We conduct several ablation studies to measure the contribution of each component in LGE. Specifically, we test the three following variants: 1.
LGE without further exploration: the environment is reset once the agent reaches the final goal instead of performing the exploration random interactions. Exploratory goal methods (see Section 2.2) are designed that way. 2. LGE without skewing the final goal distribution: instead of skewing the final goal distribution in favor of low latent density areas, the final goals are sampled uniformly among the reached goals. 3. LGE without subgoals trajectory reduction: the agent is directly conditioned by the final goal state.
We perform these ablation studies on the maze environment. We use the same hyperparameters as those used in Section 4.4. The results are shown in Figure 7.
Three ablations studied have a substantial impact on the results. We show that the exploration that follows the reaching of a goal is crucial: without it, the agent reaches the frontier of its knowledge but has little chance to go beyond it. We also show that promoting the sampling of low latent density goals can significantly increase the results. In doing so, we guide exploration towards states with high exploratory value. Finally, we show that the agent faces significant difficulties in reaching distant goals. Conditioning the agent by successive subgoals greatly improves its exploration.

Limitation and future work
The initial state must remain the same across episodes The approach we propose is based on the assumption that the agent is always initialized in the same state. This assumption guarantees that at the beginning of each episode, all the states previously reached are reachable and that the subgoal trajectory starts with the initial state of the agent. However, in some environments, especially in procedurally generated environments, this assumption is not fulfilled (Küttler et al. 2020). In this situation, trying to follow the subgoal trajectory may be counterproductive in reaching the final goal. It is also possible that the final goal is not even reachable. However, note that even the pursuit of an unreachable goal can foster exploration. Future work should investigate how to tailor the algorithm to overcome this problem. We believe that an approach inspired by generative networks such as (Racanière et al. 2020) may be appropriate.
Goal-achievement functions In LGE, an agent is considered to have reached a goal (whether final or intermediate) when the latent distance between its state and the goal is below a specified threshold. This is a naive way of defining a goal achievement function (Colas et al. 2022) that depends crucially on the latent representation. We believe that the results could be improved by envisioning a more informative and suitable goal achievement function for our method.
High-dimension environments and representation learning The main contribution of our work consists in the generalization of the Go-Explore approach by using a latent representation.
LGE can be applied without further adaptation to high-dimensional environments. Our approach is particularly useful in environments where the observation is an image, and for which learning directly from the raw pixels is not desirable. Thus, representation learning is the keystone of the method. We provide a proof of concept for a forward and inverse model. We believe that these results can be greatly improved by choosing more finely the representation learning method for each environment by taking advantage of the many works dealing with this subject (Lesort et al. 2018). Future work should confirm this intuition.

Conclusion
We introduce LGE, a new exploration method for RL. In this method, our agent explores the environment by selecting its own goals based on a jointly learned latent representation.
LGE can be used as pre-training in environments where rewards are sparse or deceptive. Our main contribution is to generalize the Go-Explore algorithm, allowing us to benefit from representation learning algorithms for exploration. We present statistically robust empirical results conducted in a maze environment and in a robotic environment. These results show that our approach significantly improves exploration performance. representation in Go-Explore In Go-Explore, similar observations are grouped into cells and each cell encountered is stored in an archive. The cell representation is a critical aspect of Go-Explore. In the Montezuma's Revenge environment, a slight variation in cell representation results in an order of magnitude difference in the results. The cells are used to (1) estimate the density of states encountered in the observation space and sample a target cell against it; (2) divide this goal reaching task into a sequence of subgoals.
We argue that building a cell representation to capture the relevant components of an environment to perform the desired task requires a significant amount of domain knowledge. In general, this cell representation cannot be generalized to other tasks or to other environments.
To support our claim, we present in Figure 8 the space coverage in a continuous maze for different cell design. We show that even in this simple environment, a small variation in cell design has a significant impact on the result.
On the left, the cells are small, and the agent must visit each of them. If the agent interacts long enough with the environment, it should eventually explore the whole space. On the right, the cells are large. We can observe some detached areas, because the agent has not visited the cell enough to discover the next one, but enough so that this cell is no longer listed as a target cell.

Appendix C On the density estimation
Let s1, . . . , sn be a sample of event locations in a R d -space. Assume that the event location s follows a common distribution with density function f (s). For any sample si and sj in this sample, assume that Di(sj) = ||si − sj||, denotes the euclidian distance between si and sj. For any k n, let D (k) (si) be the distance with k-th nearest neighbors of si with respect to the euclidian distance. (Kung, Lin, and Kao 2012) propose an optimal unbiased estimatorf for the density:f where and Thus we havef We follow the recommendation of (Kung, Lin, and Kao 2012) to take k = 2n 1/d Appendix D Comparing Go-Explore and LGE The Go-Explore algorithm as presented by Ecoffet et al. (2021) has many components. All these components allow to obtain good results on test environments. In this article, we implement our own version of Go-Explore. We have tried to stick as much as possible to the initial implementation and to improve some aspects. We keep the essence of Go-Explore, but our implementation is not intended to be equivalent to the initial implementation. The main goal here is to compare LGE and Go-Explore. Thus, the two implementations differ only in the elements that make them unique. To the best of our knowledge, all the composnts that we did not implement are compatible with LGE. It is likely that they improve LGE and Go-Explore in a similar way. In this section, we describe the implementation of LGE and Go-Explore. We explain their differences if any.
Policy-based Go-Explore The initial implementation of Go-Explore distinguishes between the case where the environment can be reset to any desired state and the case where this is not possible.
In this paper, we choose the general setting where the environment can't be reset to any desired state, and we therefore work with the so-called policy-based implementation of Go-Explore.
Exploration after returning In the original implementation of Go-Explore, once a cell is returned, exploration proceeds with random actions for a certain number of timesteps. For both LGE and Go-Explore, we set this number of timesteps to 50 for all environments. Note that the agent can interrupt this exploration beforehand if the maximum number of interactions with the environment is reached. (Ecoffet et al. 2021) shows that action consistency generally allows for more effective exploration, especially in the robotic environment. For LGE and Go-Explore, we use the same trick: the agent chooses the previous action with a probability of 90%, and uniformly samples an action with a probability of 10%.
Cell design The original implementation of Go-Explore provides two methods for generating the cell representation.
1. When the observation is an image, the observation is grayscaled and downscaled. The image produced is the cell representation. The parameters to get this representation (downscaling width and height and number of shades of gray) are optimized during training to maximize an objective function that depends on a target split factor. 2. When the observation is a vector, each component of the vector is discretized separately by hand before learning.
For all the environments presented in this paper, we use a naive method of cell generation corresponding to a discretization of the observation. The granularity of the discretization is a hyperparameter. The choice of this hyperparameter is crucial, we develop it in more detail in the appendix B.
Goal-conditioning In the original implementation of Go-Explore, the agent is conditioned by the cell representation of the goal. We note that this representation can vary during learning, and even in size (see previous paragraph). It is not clear how to structure the agent's network when the size of the input varies during the learning process.
In our implementation, we choose to condition the agent by the goal observation rather than by the representation of its cell. We also condition the agent by the goal observation in LGE.

RL agent
In the original implementation of Go-Explore, the goal-conditioned agent is based on the on-policy PPO algorithm (Schulman et al. 2017). For both LGE and Go-Explore, we rather

Surprise
Reward In the original implementation of Go-Explore, the agent gets +1 reward for reaching intermediate cells and +5 reward for reaching the final cell of a path. The rest of the time, it receives a 0 reward. For both LGE and Go-Explore, following the suggestions of (Tang and Kucukelbir 2021), we rather choose the following structure for the reward: the agent gets a reward of 0 for a success (target cell reached for Go-Explore and latent distance with the goal state below the distance threshold for LGE) and −1 the rest of the time.

Method
Hyperparameter Value LGE   Table 3: Hyperparameters of the off-policy agent. These hyperparameters are identical for all methods and for all experiments. The hyperparameters related to HER relabeling only apply to the methods for which the agent is goal-conditioned (DIAYN, Go-Explore, Skew-Fit and LGE).