Efficient Exploration via Fragmentation and Recall
Authors: Jaedong Hwang
Zhang-Wei Hong
Eric R Chen
Akhilan Boopathy
Pulkit Agrawal
Ila R Fiete
Venue: Submitted to ICLR 2023 (2023)
Keywords: fragmentation
recall
exploration
cognitive science
neuroscience
curiosity
reinforcement learning
spatial navigation

Abstract: Efficient exploration and model-building are critical for learning in large state- spaces. However, agents typically face problems like getting stuck locally during exploration and catastrophic forgetting in their construction of models when the environments are heterogeneous. Here, we propose and apply the concept of Fragmentation-and-Recall to solve spatial (FarMap) and reinforcement learning problems (FarCuriosity). Agents construct local maps or local models, respectively, which are used to predict the current observation. High surprisal points lead to a fragmentation event. At fracture points, we store the current map or model fragment in a long-term memory (LTM) and initialize a new fragment. On the other hand, Fragments are recalled (and thus reused) from LTM if the observations of their fracture points match the agent’s current observation during exploration. The set of fracture points defines a set of intrinsic potential subgoals. Agents choose their next subgoal from the set of near and far potential subgoals in the current fragment or LTM, respectively. Thus, local maps and model fragments guide exploration locally and avoid catastrophic forgetting in learning heterogeneous environments, while LTM promotes exploration more globally. We evaluate FarMap and FarCuriosity on complex procedurally-generated spatial environments and on reinforcement learning benchmarks and demonstrate that the proposed methods are more efficient at exploration and memory use, and in harvesting extrinsic rewards, respectively.

Under review as a conference paper at ICLR 2023
EFFICIENT EXPLORATION VIA FRAGMENTATION AND RECALL
Anonymous authors Paper under double-blind review
ABSTRACT
Efficient exploration and model-building are critical for learning in large state- spaces. However, agents face problems like getting stuck in local optima during exploration, and catastrophic forgetting when constructing models in heterogenous environments. Here, we propose and apply the concept of Fragmentation-ane Recall to solve spatial (FarMap) and reinforcement learning problems (FarCurios- ity). Agents construct local maps or local models, respectively, which are used predict the current observation. High surprisal points lead to a fragmentation event. At fracture points, we store the current map or model fragment in a long-term memory (LTM) and initialize a new fragment. On the other hand, Fragments are recalled (and thus reused) from LTM if the observations of their fracture points match the agent's current observation during exploration. The set of fracture points defines a set of intrinsic potential subgoals. Agents choose their next subgoal from the set of near and far potential subgoals in the current fragment or LTM respectively. Thus, local maps and model fragments guide exploration locally and avoid catastrophic forgetting when learning in heterogeneous environments, while LTM promotes global exploration. We evaluate FarMap and FarCuriosity on complex procedurally-genet
spatial environments and on reinforcement learning benchmarks to demonstrate that the proposed methods are more efficient from a memory usage standpoint, and achieve better task performance overall.
INTRODUCTION
Human episodic memory breaks our continuous experience of the world into episodes fragments that are divided by event boundaries that involve large changes of place, context, affordances, and perceptual inputs (Baldassano et al., 2017 Ezzyat & Davachi 2011 Newtson & Engquist 1976] Richmond & Zacks 2017: Swallow et al. 2009 Zacks Swallow] (007). The episodic nature of memory is core component of how we construct models of the world. It has been conjectured that episodic memory makes it easier to perform memory search, and to use the retrieved memories in chunks that relevant for the current context. Humans also continue learn and memorize new information throughout their lives, without needing to reconfigure all previously stored memories. These observations suggest a certain locality or fragmented nature how we model the world.
Chunking of experience has been shown to play a key role in perception, learning and cognition in humans and animals (De Groot 1946 Egan & Schwartz/ 1979. Gobet et al.] 2001] Gobet & Simon 1998 Simon| 1974). In the hippocampus, place cells appear to chunk spatial information by defining separate maps when there has been a sufficiently large change in context or in other non-spatial or spatial variables, through a process called remapping: see Colgin et al. (2008); Fyhn al.) (2007). Grid and place cells in the hippocampal formation have also been shown fragment their representations when the external world or their own behaviors have changed only gradually rather than discontinuously (Derdikman et al. 2009) Low et al., 202T). Recently, Klukas al. (202T) proposed how such remapping could occur in even during continuous navigation through a continuous environment, modeling the process as one of online clustering based on observational surprisal.
Similarly, when fitting complicated manifolds or functions, it is common to build a set of simpler local models of the manifold or function. Inspired by these ideas, here we propose building models for complicated spaces by fitting sequence of local models, and using local models obtained through an online process of fragmentation to aid in the the exploratory process of moving through a large space and building a model of the space.

---

Under review as a conference paper at ICLR 2023
Observation
oo
* Fragmentation model fragment
C
Action
DC Recall model fragment
Long-Term Memory
Environment
Agent
Figure 1: Overview of our approach. Given observation from the environment, the FarMap or FarCuriosity agent decides whether to fragment the space based on how well it can predict the observation. If frugmentation occurs, the current map (or model) fragment is stored in long-term memory (LTM)); the agent then initializes a new map (or model) fragment. Conversely, if the current observation closely matches with the observations stored in LTM, the agent loads an existing map (or model) fragment from there (recalf). Based on the current fragment, the agent selects an action to explore the environment.
We propose
framework for exploration based concept of online Fragmentation-and Recall, schematized in Figure []] This model combines two ideas: 1) when faced with a complex world, can be more efficient build and combine multiple (and implicitly simpler) local models than to build a single global (and implicitly complex) model, and 2) boundaries between local models should occur when a local model ceases be predictive.
In what follows, as an agent explores, it predicts its next observation. Based on measure of surprisal between its observation and prediction, there can be a fragmentation event, which point the agent writes the current model into long-term memory (LTM) and initiates a new local model. While exploring the space, the agent consults its LTM, and recalls an existing model observations. For the spatial domain, this is very similar to Klukas et al. (202T). The agent uses its current local model to act locally, and its LTM to act more globally. We apply this concept to solve spatial exploration and more general reinforcement learning exploration problems, and call the corresponding approaches FarMap and FarCuriosity, respectively.
matches its
We evaluate the proposed framework moocedurally-generade spatial environments and reinforce- ment learning benchmarks, Experimental results support the effectiveness of the proposed framework; FarMap explores the spatial environment with much less memory usage and is faster than its base- lines /aamacchi] 1997) by large margins, and FarCuriosity achieves better performance than the baseline fragmentation-less curiosity module (Burda et al., 2019) on standard heterogeneous Atari game benchmark The contribution of this paper is three-fold as follows:
We propose a new framework for exploration based on Fragmentatton and-Recal that di- vides the exploration space into multiple fragments and recalls previously explored ones.
We implemented our framework in spatial exploration tasks, referring to it as FarMap with short and long-term memory. Our experiments showed that FarMap reduces online memory size and wall-clock time relative to basclines.
We implemented our framework setting, referring to it FarCuriosity. FarCuriosity avoids catastrophic forgetting and achieves better performance compared to the baseline in heterogenous environments.
curiosity-driver reinforcement learning exploration
2 RELATED WORK
Frontier- based spatial exploration in SLAM SLAM (simultaneous localization and mapping) agents must efficiently explore spaces to build maps. A standard approach to exploration in SLAM to define the frontier between observed and unobserved regions of a 2d environment, and then select exploratory goal locations from the set of frontier states [Yamauchi] 1997). Frontier- Frontier-based exploration has been extended to 3d environments (Dai et al., 20200 Dornhege & Kleiner 201T)
and used as building block of more sophisticated exploration strategies (Stachniss et al. 2004).
Although conceptually simple, frontier-based exploration can be quite effective compared more sophisticated
exploration (Holz et al. 2010)) A cost of trontier-bssed exploration is
Heterogencous environment is environment that has diverse states that require the larger model capacity memorize visited states for generating intrinsic reward. Please refer Section 4.2 for more details.
2

---

Under review as a conference paper at ICLR 2023
the use of global maps and global frontiers, which makes the process memory memory-expenstee expensive and search intensive. In contrast to frontier-based exploration, our approach learns the surprising parts of an environment as intrinsic subgoals, selecting among those as the exploratory goals.
Submap-Based SLAM Submap-Based SLAM algorithms involve mapping a space by breaking it into local submaps that are connected one another via a topological graph. Such Submap-Bases SLAM methods are usually designed to avoid the problems of accruing path integration eπrors when building maps of large spaces (e.g. SegSLAM) (Fairfilld et al. 2010) and to reduce the computational cost of planning paths between a start and target position (Maffei et al. 2013; Fairfield et al.] 2010 Klukas et al. 202T). Segmented DP-SLAM (Maffei et al., 2013) adds OP-SL.AN, (Eliazar Parr 2003) to SegSLAM for reducing the search space, generating segments periodically at fixed time- intervals. Topological SLAM (Choset & Nagatani (001) generates new landmarks in an environment to build a topological graph of the landmarks, and navigates based on the graph. Our Fragmentation and Recall method, in particular FarMap, is closely related to these methods in that we build multiple submaps. However, FarMap divides space based properties of the space (how predictable the space is based on the local map or model), and does so in an online manner using surprisal.
Curiosity-Driven Reinforcement Learning Motivated by the insufficiency of rewards alone to guide exploration in sparsely rewarded RL environments, several works construct intrinsic rewards encouraging agents to explore unfamiliar parts of an environment. Count-based methods provide intrinsic rewards for reaching infrequently visited states. These methods have strong theoretical guar- antees for multi-arm bandits (Auer 2003), and can effective for reinforcement learning (Bellemare) et al. 2016; Tang et al.] 2017] Ecoffet et al. (02T). Prediction-based methods estimate where the agent cannot predict some aspect of the environment, and provide intrinsic rewards for visiting those states (Burda et al.] 2019] Choshen et al. 2018; Houthooft et al. 2017 Pathak et al.) 2017 Raileanu & Rocktäschel] (020)_ Patthak et al. (201) for instance, learns a forward model to predict the next state given the current state-action pair, and provides rewards scaling with the state's prediction error.
Memory-Basee -Based Reinforcement Learning Memory- based reinforcement learning aims to solve the long-term credit assignment problem. Hung al. (2019) combine LSTM (Hochreiter & Schmidhuber 1997) with external memory along with an encoder and decoder for the memory. Lampinen et al. (202T) use hierarchical LTM with chunks and attention for long-term recall inspired by Transform- ers /Vaswani et al.) (017); :) however, their chunks are formed periodically rather than based on content and are not used as intrinsic options for exploration. Memory also used for improving exploration: Go Explore (Ecofret et al. (02T) remembers promising states so that it can directly visit those states, where the definition of promising can include rewarded states and frontiers. Similar to our proposal, may view promising states in GoExplore as intrinsic options; however. if the promising states are frontiers, GoExplore becomes similar to fronticr- based SLAM methods without fragmentation. (Svvinvv et al.] (2019) memorizes visited states for calculating reachability to penalize an action that leads to reachable future states. While earlier memory-based exploration methods use memory as guide for evaluating the intrinsic reward of state, we augment existing exploration methods with memory, in combination with map or model fragmentation, to more efficiently explore.
3 FRAGMENIATION AND RECALL FRAMEWORK
The proposed framework is based on the notion of fragmentation and recall: While exploring an environment, an agent builds local model and uses the local model in short-term memory (STM) to compute a surprisal signal that depends on the current observation and the agent's local model-based prediction. The surprisal can be any uncertainty estimate such as negative confidence or future prediction error. When the surprisal exceeds some threshold, this corresponds to fragmentation event. At a fragmentation event, the local model is written to long-term- meem-yyeorry (LTMM building a connectivity graph that relates model fragments to each other so that it can provide information across the current local model without direct access to the stored models in LTM. The current (abstracted) observation (fracture point) is also stored, and the agent initializes an entirely new local model. On the other hand, if the current observation is sufficiently similar to a stored fracture point in LTM, the agent recalls the corresponding model fragment (local model). Hence, the agent can preserve and reuse previously acquired information. Sections 3.T and 3.2 describe two application domains; spatial exploration and durio reinforcement learning, respectively.
3

---

Under review as a conference paper at ICLR 2023
Short-Term Memory (STM)
Local Map
STM subgool
surprtool
Observation
(
Surpriaa distrbuttion
Choose
Fogamentation
Inttaaize a local map.
Previous
Recall stored local map,
Stone the current local mep.
LTM sutggoa
(0p-1)
n mut
M N
Novigation
location
Recel
Maps
Connectivity Graph
STM suiggoo
A. :LTM subgoal
Fragmentaaiion
Long-Term Memory (LTM)
fracture points
Figure 2: Illustration of the FarMap framework. Navigation (black arrow): Given the current observation which ego-centric top-down view with restricted field of view and previous action, the agent updates its short-term memory (STM) and selects subgoal from the current local map in STM the local map connectivity graph stored in LTM. The planner generates sequence of the actions for the shortest-path to the subgoal. Recall (dashed arrow): If the agent arrives at fracture point (cirele in the map), a corresponding local map is recalled from LTM and the current local map stored in LTM is updated. Fragmentation (gray arrow): If the current surprisal is higher than threshold, the current local map is stored in LTM and new local map is initialized. of is spatially transformed observation with the same size of the current local map to update the map.
3.1 FRAGMENTATION AND RECALL IN SPATIAL EXPLORATION (FARMAP)
SLAM algorithms explore space efficiently by aiming to explore frontier regions. They categorize each region (cell) as known and unknown based on whether it is previously observed or not and occupied and unoccupied (empty) based on its occupancy. Unknown cell adjacent to empty cells is called frontier. Typically frontier-based exploration involves frequent consultation of global map. The memory and search cost of finding subgoals grows rapidly with environment size; for agents exploring very large space, the computational costs could explode. Here, propose fragmentation-ant aan-oonnnnnn---aa---- based exploration strategy for spatial exploration (FarMap). In FarMap, each local model is spatially local map built in short-term memory (STM). As Figure 2 shows, given the observation and the previous action, the FarMap agent updates the current local map. The agent decides its next subgoal, selecting a point within the current local map or a fracture point with a different local map, based on the relative surprisal of the different locations and the connectivity graph of maps in LTM (described below). Given sufficiently high surprisal the current location, a fragmentation will occur. Upon fragmentation, the local map in STM is stored as an episode in LTM and then erased from STM. The STM begins new local map. Stored local maps in LTM are recalled whenever the agent reaches a location where fragmentation event had occurred. Section A and Algorithm [ provide detailed procedures.
Local Map The STM has a local predictive spatial map, M [(C+1)xHX where the size (H, W) grows as the agent extends its observations in the local region by adding newly discovered regions. The first C' channels of M." denote color and the last channel denotes the agent's confidence in each spatial cell. For simplicity, in this paper, we will focus only on the update of confidence channel (C-th channel). The local predictive map is simply temporally decaying trace of recent sensory observations, shifted by the agent's actions (movement through space) (Klukas et al. 2021):
M G.C
M M + -1-21 (1-))- oh.c.
(1)
where y is the decaying factor and 02 [CC+))xxx is the egocentric view input observation in the environment at time sized as (h, w). The last channel of the observation means visibility caused by occlusion restricted FOV; visible (1) or invisible (0) on each cell. The red region visible and others are invisible in Figure 2 of (C++))xHXW denotes spatially transformed observation to M to update the current observation to the local map in the correct position; rotation and zado-padding (Figure 3). Please refer to Section A for further details of how the local map is updated.
4

---

Under review as a conference paper at ICLR 2023
Surprisal
The scalar surprisal signal 8, =1 ct is generated using the local map in STM and the current observation, where ot quantifies the average similarity of the visible part of observation to the local predictive map M before update:
M 1-1. d,C
Ct
(2)
The agent is assumed to maintain a running estimate of the mean f and standard deviation or of past surprisals, stored part of the current map.
Fragmentation Fragmentation occurs if the z-scored current surprisal ((*t - threshold. p. Initially on each new map, the agent collects surprisal statistics and is not permitted to further fragment space until the number of samples is greater than 25 (for large sample condition). We also store the ratio qe of the number of frontier cells to the number of known cells and the distance between each fracture point in M. ge keeps updating every time step until it is stored in LTM. The ratio is used guide agents in LTM, it is connected with an adjacent map fragment that shares the same fracture point in the connectivity graph. In other words, the node of the graph model fragment and the connection denotes both fragments share fracture point.
(<t=) /at)/az) exceeds a
whether or not to move to other local maps. When M. is stored
Recall Each local map records the fracture points. At these points, there are overlaps with other map fragments. When the agent moves to the point in the current local map, corresponding local map recalled from LTM and the current one stored in LTM.
Subgoal Subgoal is decided by using either the current local map in STM or the connectivity graph in LTM. The former enlarges the current local map while the latter helps find the next local map to explore. An agent explores the local region in the environment unless the current surprisal is too low (e.g., z-score smaller than 1) and there is less explored local map nearby.
Subgoals made with the current local map are based on frontier-basee subgoals (Yamauchi 1997) for exploring the local region. In the current local map, we first find all frontiers which are unknown cells adjacent to the known unoccupied cells. A group of consecutive frontiers are called 'frontier- edge' and Yamauchi (197)) uses the nearest centroid of the frontier-edge as a subgoal. Unlike standard SLAM methods that employ the entire map, our map in STM only covers subregion of the environment. After fragmentation. the region, where the agent came from, has several frontiers (border of two local models) forming frontier-edge. It leads the agent to go back to the previous area and recall the corresponding map fragment. This would lead to the agent moving between two map fragments for long time. Hence, we prioritize the frontier-edge that is not located spatially behind the agent. The subgoal is sampled with the following weight wy for each frontier-edge Fj:
F 1(F, is not located spatially behind the agent)
Wi
(3)
dj where d, means the distance between the current position and the centroid of F, and 1(-) is the indicator function that is if the condition is true otherwise 0.
Once the agent finishes exploring the local region, it should move to different subregions. However, subgoals from the current local map misguide the already explored region since the agent does not have information beyond the map. Hence, we employ the connectivity graph of local maps stored in LTM. We leverage the discovery ratio (the ratio of the number of frontier cells to the number of known cells) mentioned above to find the most desirable subregions to explore. We also utilize the Manhattan distance between the current agent location and the fracture point between the current (c-th) local map and the connected i-th local map, di,c where d = O and dj.c = oo if j-th local map is disconnected to the current map. Then, the desirable local map selected as
arg max
(4)
di.c c
where denotes the preference of staying in the current local map: smaller value encourages staying in the current local map. If g is not equal to c, the fracture point between the current local map and g-th local map is set to the subgoal. Once the agent arrives at the fracture point, the corresponding local map is recalled and the agent recursively checks Eq. 4 until g is the arrived subregion. Note that the distances between a new location and other fracture points stored in the recalled local map are precomputed since they are fixed.
5

---

Under review as a conference paper at ICLR 2023
Short-
Short-Term Term Memory (STM)
Short Term Memory (STM)
Payyeettttio
redd
Surprical
Curlosity
Curiasity Module
Module
Camen tiseaation
Cament Diservtiion
(9c)
Store currentipuur obserator.
Siore the cureer modii.
Of
Recela nodile from UTM.
Usdats the amven modia In
Observations
Obseratiors 10
1011
Carieity Medulos
Gurlestry Modiles
Long-Torm Torm Memory (LTM)
Long-
Long-Term Term Memory (LTM)
(a) Fragmentation
Recall
Figure 3: Illustration of the proposed FarCuriosity framework. (a) Fragmentation. If the current surprisal is out-of-distribution with high value (gray arrows), the current curiosity module and its input are stored in L.TM and new module is initialized. (b) Recall, If the current observation similar to an observation in LTM, the corresponding curiosity module is recalled and update the current module in LTM.
The planner takes a subgoal and the current spatial map in STM and finds the shortest- path within the map from the current agent location to the subgoal. We use Dijkstra's 's algorithm for planning a path to the next subgoal. However, the planner can be any path planning method such as A algorithm (Hart et al. 1968) or RRT VLale 1998).
Planner
3.2 FRAGMENTATION AND RECALL IN CURIOSITY- DRIVEN RL (FARCURIOSITY)
Like in spatial map building, exploration is a critical property of good reinforcement learning systems. Unlike map building, deep RL can be applied diverse tasks including manipulation (Lee et al.)
2021: Tassa et al. 2018). game playing (Bellemare et al. 2013 Küttler et al. 2020) and also spatial foraging and navigation (Szot al. 2021p.
Intrinsic reward functions (in the form of curiosity modules) (Burda et al. 2019 Campero et al. 2021 Pathak et al. 2017 2019 Raileanu & Rocktäschel, 2020) used for exploring novel spaces of an environment by generating intrinsic rewards. The intrinsic reward can serve as the primary reward for training policies realistic scenarios where external rewards are sparse or absent. Since curiosity module is trained concurrently with the policy, it can suffer from catastrophic forgetting (French 1999 Robins 1995) over large and heterogeneous environments where the observation space is high variance such having multiple rooms/stages with different backgrounds. Hence, demanding on larger model capacity to memorize what the model has seen for generating intrinsic rewards in these environments. The catastrophic forgetting of a curiosity module leads to high prediction errors (high intrinsic rewards) for already explored states, making agents less likely to explore unseen states.
We tackle this problem by applying our fragmentation- scheme to the problem of exploration in deep RL settings, implementing multiple local models in the form of multiple curiosity modules (Far- Curiosiry). Similar to above, agent. In FarCuriosity, surprisal is based on the predictions of a curiosity module in STM in place of the predictions using local map in STM. While FarMap aims to efficiently build and use maps, the goal of FarCuriosity is to better explore states so that the agent can solve a given task.
surprisal to fragment the state space of an environment and
Fragmentation We use the prediction error generated by the curiosity module (Burda et al. 2019 Pathak et al. (017) for fragmentation. When fragmentation occurs a fracture point (high prediction error by the current curiosity module) we store the current curiosity module and its input (usually corresponding to the next observation) in LTM and initialize a new module.
Recall At every point, the agent can search LTM to select curiosity module. The curiosity module's 's input observation (or encoded feature of the current observation) is the key used to select a module: Given the current input observation, Oc, and the observations from past fracture points, of which element is oy, and a fixed feature extractor Φ(-), we define recall score geee based on cosine similarity as follows:
((ox) - )(or)
.00 = [10(o)) 2 ( 1|2 f
(5)

---

Under review as a conference paper at ICLR 2023
(i) Discrvation
(b) Small (size: 3249)
(c) Medium (size: (3669)
(d) Large (size: 23868)
Figure 4: Environments. Empty cells (that can be occupied by the agent) are black; walls are randomly colored. (a) Top-down visualization of the agent's ' local field of view (FOV) (agent: red triangle; shaded region: observation) within an environment (b). The agent has only locally restricted egocentric view. The right side is occluded by a wall. (b) Top-down view of one environment. the red box marks the region shown in (a). (c), (d) Examples of medium and large environments.
Frontier
Fronticr-
25000
4000
20000
Time
3000
15000
2000
10000
5000
1000
10
15
20
25
30
3.
20
25
30
Environment Size Ix 1000)
Eniiionnmnnt Size Ix 1000)
Figure 5: Relative memory and wall-clock time advantage of FarMap to Frontier-based baselines grows with environment size. Comparison of memory cost (left) and wall-clock time (right) as a function of environment size (circles: experimental results; line: linear regression fit). FarMap requires substantially less memory and is much faster than other methods.
If sTe " equal or greater than recall threshold for any element of. we store the current module in LTM and recall the module corresponding 0y. We choose the highest scoring if multiple modules meet the condition. The module just before recall of the module for oy becomes a new element of the modules in LTM.
EXPERIMENTS
In this section, conduct experiments for FarMap and FarCuriosity comparing their baselines on procedurally generated map environment and Atari games, respectively. Please refer to Section C for the experimental settings.
4.1 FARMAP EXPERIMENTS
We measure the map coverage and memory usage for each environment at each time step as our evaluation criteria and calculate the mean and standard deviation over all runs. The memory usage in each environment is calculated as a ratio of local map size (memory size, x W) to the environment size. Note that the local map size is the asymptotically dominant factor in the memory. We also use wall-clock time for comparison. We compare FarMap with standard frontier- based exploration (Frontier) (Yamauchi) [197). We also consider an augmented baseline with heuristics used in FarMap: prioritizing the frontier-edges not behind the agent, stochastically selecting subgoals based on the number of frontiers and the distance the centroid in each frontier-edge, mentioned in Section 3.1 (Frontier++). Our experiments are conducted in procedurally generated environments (See Section B). As shown in Figure 4 the walls in the environment are randomly colored and are composed of various narrow and wide pathways. For each trial, the agent is randomly placed before begins to explore the environment. Figure presents an example of the agent's view the small environment shown in Figure 4b] The agent is presented as a red triangle and the observed cells are shaded. The agent has the restricted field of view with occlusion (120%).
Figure aldd Table analyze memory size and wall-clock-time changes depending on the environment size. In T [ we divide the environments into three groups; small, medium and large based on their sizes. FarMap requires significantly less memory than the baselines, with small performance drop as the environment size is increased. Moreover, since our agent only refers to the subregion of the environment not using the entire map, it is much faster than other methods while planning. Especially,
7

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison of average map coverage (%), memory use (%), and wall-clock time (s) for small, medium, and large environments. The memory usage advantage of FarMap relative to its counterparts grows with environment size. Frontier++ is Frontier (Yamauchi] 1997]. augmented with head direction, and with subgoal selection weights given by the size of the frontier in each subgoal. Although RND is much faster than others, it has much worse exploration performance. The numbers in parentheses are the standard deviation.
Small (size 5,000)
Medium (5,000 g 15,000)
Large (size 2 15,000)
Model
Coverage
Memory
Coverage
Memory
Coverage
Memory
Frontier Yamauchi 1997
(9.2
(8.9) 360.5 (168.8)
(218) (19.7) 871.9 (439.0)
41.4 (20.1) 44.4 (20.1) 12610
98.8 (6.7)
81.6(7.5)
341.1 (1911)
(17.4)
(15.2)
(511.3)
60.8 (21.4)
(20.9)
1872.4 (782.7)
FarMap
(7.2)
79.1 (8.7)
(1186)
(19.8) (19.3)
(119.0)
56.6 (20.8
(11.8)
(11.7)
RND
Burda et 2019
73.7 (23.3)
50.6 32 (16.2)
48.8 (16.2)
(3.6
(43.6)))))
Relative Extrinsic Reward Improvement
3-
Improvement
Demmeend
2
Private Eye
1
Riffall
Gravitr
Bear Hider
Astorolds
River Haid
Pong
Invaders
Star Burner
Breakout
-1-
Montesume's Revenge
RouCarielt RAND Reao
(Relution Imgiooneeeny
-2
Tennis
Deteoriation
-3
10
15
20
25
30
Average Standard Deviation (Heterogeneity)
Figure 6: The relative performance improvement over RND performance (RRND) in various Atari games. The average standard deviation is measured from each pixel in trajectory generated by trained RND. FarCuriosity effective in visually high- varianee (heterogeneous) games.
in large environments, is approximately four times faster than the baseline with heuristics. We also compare with Random Network Distillation (RND) (Burda et al. 2019) trained and evaluated on each map separately without extrinsic reward. Although RND requires constant time for any size of environment, its exploration performance is worse than other methods. We additionally show how map coverage and memory usage change in exploration Section D conduct sensitivity analysis of hyperparameters in Section and confidence interval of Table in Section
4.2 FARCURIOSITY EXPERIMENTS
We present the empirical results that verify the problem of catastrophic forgetting (Section 3.2 of intrinsic rewards in curiosity- driven deep reinforcement learning in this section. We implement our FarC FarCuriosity method based on RND (Burda et al.) 2019) and compare against to the vanilla RND. Both FarCuriosity and the vanilla RND train policy using Proximal Policy Optimization (PPO) (Schulman et al. (017). Burda et al. (219) suggest. We follow the original RND paper and select Atari (Bellemare et al. 2013) as the benchmark. We perform experiments over 15 Atari games: Asteroids, Beam Rider, Boxing, Breakout, Gravitar, Jamesbond, Montezuma's Revenge, River Raid, Pitfall, Pong, Private Eye, Seaquest, Space Invaders. Star Gunner, and Tennis.
We measure the average across all pixels of the standard deviation of each pixel from trajectories generated by trained RND (Burda et al.) 2019) as the heterogeneity of each game. If the agent only explores small portion of the environment, the fragmentation not needed although the environment has hundreds of distinctive rooms. Therefore, we measure heterogeneity using our curiosity module, RND. Figure 6 shows the relative performance improvement on multiple Atari games which defined as below:
(Relative Improvement) = RFanCurioiity RRND
RRND
where RFarCurioiity and BRND denote the average extrinsic reward of FarCuriosity and RND, re- spectively. Since both Rpacunisiiy and RRND are negative in Tennis and Pitfall, we multiply the improvement by -1 here. The negative improvement denotes the performance is worsened by FarCu- riosity. FarCuriosity generally improves performance in heterogeneous environments while achieving similar even worse performance in homogeneous games. FarCuriosity achieves worse performance
8

---

Under review as a conference paper at ICLR 2023
Nomes int Roward Enor
RND
FarCuriesty
2.5
8.0
100
Leoming Prograss (milion fromsst
(a) Starting observation
(b) Intrinsic reward of starting observation
Figure 7: Intrinsic reward of the same observation (first observation in every episode) in Jamesbond during training. Each reward is normalized by the average intrinsic reward across training separately, in order to directly compare the magnitude of the change in intrinsic rewards during training. The reward from RND is increasing while one from FarCuriosity is decreasing after 15 millions steps.
in Montezuma's 's Revenge which might be due to its low heterogeneity since RND could not explore many rooms. FarCuriosity has the worst deterioration in the least heterogeneous environment, Tennis. We analyze the relationship between the number of fragments and the performance in Section G and the experiments in each environment in Section
FarCuriosity does significantly better than RND in Jamesbond; to explain this, we measure the intrinsic reward (prediction error) when the agent returns to the same observation (first frame of the episode) during training as shown in Figure 7 The error of the FarCuriosity agent at the observation remains the same after short initial increase, regardless of how much subsequent learning the agent performs elsewhere in the environment. On the other hand, RND generates a higher intrinsic reward (higher prediction error) as training progresses, implying that this method suffers from catastrophic forgetting. The prediction-bas based curiosity module assumes that infrequently visited states have high prediction error and vice versa. However, due to catastrophic forgetting, this assumption is invalid here. In summary, our fmammmmattioon-add-rrlll concept is helpful for heterogeneous environments.
5 DISCUSSION
We proposed a new framework for exploration based on local models and fragmentation, inspired by how natural agents explore space. Our framework fragments the exploration space based on the current surprisal in real time and stores the current model fragment in long-term memory (LTM), Stored fragments are recalled when the agent returns the state where the fragmentation happened so that the agent can reuse the local information. Accordingly, the agent can refer to longer-term local information. We believe that the framework can be applicable to any tasks that use streaming observations data which are reused or recurring. We applied this framework to the settings of spatial exploration (FarMap) and general reinforcement learning exploration (FarCuriosity). The surprisal is generated by short-term memory (STM) using local map in FarMap and curiosity module in FarCuriosity. Consequently, FarMap requires less memory and wall-clock time than the baseline method (Yamauchi 1997) without sacrificing exploration performance. On the other hand, FarCuriosity learns better than its baseline (Burda et al. (219)) in standard deep reinforcement learning benchmarks by appropriately recalling model fragments once fragmentation happens in the environment. In principle, as in FarMap, LTM could include a connectivity graph that describes the transition structure between recalled modules, which we believe will be useful for goal-directed reinforcement learning. However, in what follows, we use only individual stored modules in LTM for FarCuriosity and not the connectivity graph, which we leave for future work.
Our paper aims to be proof-of-coneee for fragmentation and recall; we have applied it to only two domains with relatively small number of environments, but the strong performance in these cases suggests that the concept should provide improvements in many heterogeneous sngernggneouuseeiiiommen learning problems. On the contrary, FarCuriosity is not effective in homogenous environments or frequently reset environments since the baseline agent does not suffer from catastrophic forgetting in those environments. With this effort, we intend to bring to the attention of the machine learning community the fragmentation-ani and-recall concept inspired by natural agents for heterogeneous environments. This concept can make large-scale exploration, which typically requires a huge memory size and long-ranged memory span, significantly more efficient.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Peter Auer. Using confidence bounds for exploitation-eeploraaion trade-offs. JMLR, 3:397-422, 2003.
Christopher Baldassano, Janice Chen, Asich Zadbood, Jonathan Pillow, Uni Hasson, and Kenneth A Norman. Discovering event structure in continuous narrative perception and memory. Neuron, 95 (3):709-721, 2017.
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. The arcade learning environment: An evaluation platform for general agents. JAIR, 47:253-279, 2013.
Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. NeurIPS, 2016.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In ICLR, 2019.
Andres Campero, Roberta Raileanu, Heinrich Kuttler, Joshua Tenenbaum, Tim Rocktäschel, and Edward Grefenstette. Learning with amigo: Adversarially motivated intrinsic goals. In ICLR, 2021.
Maxime Chevalier-Boisvert, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for gymnasium. https: cww. wwt.c/oo/aaaaaaaaa Foundation/Minn
2018.
Howie Choset and Keiji Nagatani. Topological simultaneous localization and mapping (slam): toward exact localization without explicit localization. TRA, 17(2):125-337, 2001.
Leshem Choshen, Lior Fox, and Yonatan Loewenstein. Dora the explorer: Directed outreaching reinforcement action-selection. In ICLR, 2018
Laura Lee Colgin, Edvard I Moser, and May-Britt Moser. Understanding memory through hippocam- pal remapping. Trends in neurosciences, 4797)7469477, 2008.
Anna Dai, Sotiris Papatheodorou, Nils Funk, Dimos Tzoumanikas, and Stefan Leutenegger. Fast frontier-based information-driven autonomous exploration with an mav. ICRA, 2020.
Adrianus Dingeman De Groot. Het denken van den schaker, een experinenttelpsychooogie studie. 1946.
Dori Derdikman, Jonathan R Whitlock, Albert Tsao, Marianne Fyhn, Torkel Hafting, May-Britt Moser, and Edvard I Moser. Fragmentation of grid cell maps in multicompartment environment. Nature Neuroscience, 12(10):1325-1332) 2009.
Christian Dornhege and Alexander Kleiner. A frontier-void-oee based approach for autonomous explo- ration in 3d. In SSRR, pp. 351-356, 2011.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return, then explore. Nature, 590(7844):580-556, 2021.
Dennis E Egan and Barry Schwartz. Chunking in recall of symbolic drawings. Memory & cognition, 142):149- 1979.
Austin Eliazar and Ronald Parr. Dp-slam: Fast, robust simultaneous localization and mapping without predetermined landmarks. In IJCAI, 2003.
Youssef Ezzyat and Lila Davachi. What constitutes episode in episodic memory? Psychological science, 2232):243-252, 2011.
Nathaniel Fairfield, David Wettergreen, and George Kantor. Segmented slam in three-dimensional environments. Journal of Field Robotics, 27(1):85-103, 2010.
Robert M French. Catastrophic forgetting in connectionist networks. Trends in cognitive sciences, 14):128-135, 1999.
10

---

Under review as a conference paper at ICLR 2023
Marianne Fyhn, Torkel Hafting, Alessandro Treves, May-Britt Moser, and Edvard I Moser. Hip- pocampal remapping and grid realignment in entorhinal cortex. Nature, 446(7132)110--194, 2007.
Fernand Gobet and Herbert Simon. Expert chess memory: Revisiting the chunking hypothesis. Memory, 6(3):225-255, 1998.
Fernand Gobet, Peter CR Lane, Steve Croker, Peter CH Cheng, Gary Jones, lain Oliver, and Julian M
Pine. Chunking mechanisms in human learning. Trends cognitive sciences, 5(6):236 011-236-443, 2001.
Peter E. Hart, Nils Nilsson, and Bertram Raphael. formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-107,, 1968.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural compulation, 9(8):
1735-1780, 1997.
Dirk Holz, Nicola Basilico, Francesco Amigoni, and Sven Behnke. Evaluating the efficiency of frontier-based exploration strategies. In ISR, pp. 1-8, 2010.
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. Vime: Variational information maximizing exploration, 2017.
Chia-Chun Hung, Timothy Lillicrap. Josh Abramson, Yan Wu, Mehdi Mirza, Federico Carnevale, Arun Ahuja, and Greg Wayne. Optimizing agent behavior over long time scales by transporting value. Nature communications, 10(1):1-12,200 2019.
Mirko Klukas, Sugandha Sharma, YiL.n Du, Tomas I Lozano-Perez, Leslie Kaelbling, and Ila Fiete. Fragmented spatial maps: State abstraction and efficient planning from surprisal. bioRxiv, 2021.
Heinrich Küttler, Nantas Nardelli, Alexander H. Miller, Roberta Raileanu, Marco Selvatici, Edward Grefenstette, and Tim Rocktäschel. The NetHack Learning Environment. In NeurlPS, 2020.
Andrew Lampinen, Stephanie Chan, Andrea Banino, and Felix Hill. Towards mental time travel: hierarchical memory for reinforcement learning agents. NewrlPS, 2021.
Steven M Lallee
Rapidly-exploring random trees: A new tool for path plan-
ning. 1998. URL https://cs. http///ss.roo...om wrown. http:///www.......ee//////////aa hww.:ppplannnnn/rrpppp......
Youngwoon Lee, Edward S Hu, and Joseph Lim. IKEA furniture assembly environment for long-horizon complex manipulation tasks. ICRA, 2021.
Isabel IC Low, Alex Williams, Malcolm Campbell, Scott Linderman, and Lisa M Giocomo. Dynamic and reversible remapping of network representations in an unchanging environment. Neuron, 109(18):2967-2)) 2980. 2021.
Renan Maffei, Vitor Jorge, Mariana Kolberg, and Edson Prestes. Segmented dp-slam. In IROS, 2013.
Darren Newtson and Gretchen Engquist. The perceptual organization of ongoing behavior. Journal of Experimental Social Psychology, 12(5):436-450 1976.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In ICML, 2017.
Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Self-supervised exploration via disagreement. In ICML, 2019.
Roberta Raileanu and Tim Rocktäschel. Ride: Rewarding impact-driven exploration for procedurally- generated environments. In ICLR, 2020.
Lauren L Richmond and Jeffrey M Zacks. Constructing experience: Event models from perception to action. Trends cognitive sciences, 21(12):9229980, 2017.
Anthony Robins. Catastrophic forgetting, rehearsal and pseudorehearsal. Connection Science. 7(2): 123-146, 1995.
11

---

Under review as a conference paper at ICLR 2023
Nikolay Savinov, Anton Raichuk, Damien Vincent, Raphael Marinier, Mare Pollefeys, Timothy Lillicrap, and Sylvain Gelly. Episodic curiosity through reachability, ICLR, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 1707.00777 2017.
Herbert A Simon. How big a chunk? by combining data from several experiments, basic human memory unit can be identified and measured. Science, 183(4124):482-444 -888, 1974.
C. Stachniss, D. Hahnel, and W. Burgard. Exploration with active loop-closing for fastslam. In IROS, 2004.
Khena M Swallow, Jeffrey M Zacks, and Richard A Abrams. Event boundaries in perception affect memory encoding and updating. Journal of Experimental Psychology: General, 138(2):236, 2009.
Andrew Szot, Alex Clegg, Eric Undersander, Erik Wijmans, Yili Zhao, John Turner, Noah Maestre, Mustafa Mukadam, Devendra Chaplot, Oleksandr Maksymets, Aaron Gokaslan, Vladimir Vondrus, Sameer Dharur, Franziska Meier, Wojeiech Galuba, Angel Chang. Zsolt Kira, Vladlen Koltun, Jitendra Malik, Manolis Savva, and Dhruv Batra. Habitat 2.0: Training home assistants rearrange their habitat. NeurlPS, 2021.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. #exploration: A study of count-based exploration for deep reinforcement learning. In NeurIPS, 2017.
Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq. Timothy Lillicrap, and Martin Riedmiller. Deepmind control suite, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. NeurIPS, 2017.
Brian Yamauchi. frontier-based approach for autonomous exploration. In CIRA, 1997.
Jeffrey M Zacks and Khena M Swallow. Event segmentation. Current directions in psychological science, 16(2):80-88 2007.
12

---

Under review as a conference paper at ICLR 2023
APPENDIX
Algorithm FarMap Procedure at time t. FarMap algorithm colored in red and heuristics are colored in blue on top of Frontier algorithm.
Require: spatial map M previous action dc-1, current observation or, short-term memory STM, long-term memory LTM
Ensure: Updated map, M and sequence of actions {a}
1: procedure STEP
2: M 7 M (1-7)-
Update the current local map
3: Calculate 8 1 - Ce following Eq
4: if current position in M. is fracture point then
Recall
5:
qe =Ntronticr /Nkoown
6:
Store M LTM.
7:
Recall corresponding map fragment in LTM to STM (i.e., change M
8:
else 2z > then
b Fragmentation
9:
Ge =-Nronttirr N
10:
Store M LTM.
11:
Initialize new map M.. in STM.
12:
end
13:
Update fr and dr.
14:
arg max; tie
4:
15:
if o then
Subgoal based on connectivity between fragments.
16:
subgoal + the fragmentation location between current fragment c and a fragment g
17:
else
18:
Find frontier-edges {Fi} and their centroids. Calculate distance between the current position and each centroid {d:}.
19:
20:
Wi- 1/d, |F,l (F, is not located spatially behind the agent) D. 1-) is 1 if the
condition is true else
21:
Select frontier-edge F, based on the weighted sampling with {wi}
subgoal + the nearest frontier E Fg from its centroid.
23:
end if
24:
A sequence of actions, {a} + Planner(subgoal: M
Dijkstra's 's algorithm.
25:
end procedure
A OVERALL PROCEDURE OF SPATIAL NAVIGATION
Algorithm I presents the overall procedure of FarMap time t. On top of Frontier algorithm Ya- mauchi| 1997), we colored heuristics that is used for Frontier++ and FarMap as blue (Line 20 and FarMap algorithm
red. Given the previous action o,-1, current observation os, local predictive
map M 1, we first update the map following Eq. and calculate the surprisal following Eq. 2 Figure 8 shows the toy illustration of how transform the current observation update the local map and how the map size grows. We first rotate the observation following the head direction of the agent in the map and then zero-pad so that it has the same size as the local map considering the agent's 's current location in the map. If the observation does not fit in the same size of the map due to the agent's location, we add zero-padding (gray the figure) to both the transformed observation and the local map. Then, we update the local map by adding the transformed observation.
the current position in M is previously fragmented location with another fragment, we calculate ge the number of frontiers (Nirrotter) over the number of known cells (Ninowa) in the map M (Line Then, we store the current map in LTM and recall the corresponding map fragment in LTM to STM. If recall is not happened and 2; is greater than threshold p. store the current map in LTM and initialize a new map in STM.
After checking recall and fragmentation, find the desirable local map fragment that is less explored compared to other fragments mentioned Section 3.1 If the current map is not the desirable map. set subgoal the fracture point between the current map and the desirable map. Otherwise,
13

---

Under review as a conference paper at ICLR 2023
127
Rotale
Agene's
Unlnown cel
W
Known cell
W
H
H
H
M
1-1,0
M
M [-1,0
M
(b)
Figure 8: Toy example illustrations how the local map is updated. In this figure, we only consider the visibility of each cell without considering occupancy and the color for simplification. (a) We first rotate the current observation Or,C based on the head direction of the agent in the local map. Then, the observation is zero-pu paro-padded have the same size as the local map. Finally, the local map is updated by adding transformed observation of (b) If the current observation does not fit in the local map due the agent's location, add zero-padding (gray) both observation and the local map. Hence, the size of the local map has increased (H has changed).
first find frontier-edges and calculate a weight of each frontier-edge F, for weighted sampling with weight we following Eq. (w; is l/d; in Frontier model).
The subgoal is defined as the nearest frontier from the centroid of sampled frontier-edge. Finally, planner generates sequence of actions go the subgoal. Note that while the agent moves based on the sequence, keeps update the map and checks fragmentation and recall.
B PROCEDURALLY-GENERATT ENVIRONMENTS
We the procedurally-generaate generated environment for the map building experiments in Section 4 the main paper. Figure 9 and Algorithm show the procedure of map generation. We first generate grid patterned square rooms and randomly connect and merge them. Then, flip boundary cells of empty or occupied multiple times for diversity. Formally. given the length of square S, the interval between square rooms, and the size of the grid, (N, M), we first generate the binary square grid map M {0 (empty), 1 (occupied)) (N- S +1)- (MM (Line Algorithm 2). Let s; be the i-th square as row-major order in M. For each of adjacent square pairs, we connect two squares with probability Poonnect width probability Pmerge (Line 11). Then, we flip all boundaries between occupied and empty cells K times with probability Pap (Line 17). After flipping boundaries, there are several isolated (i.e. not connected to other submaps) submaps in M. We only use the submaps where the sizes greater than threshold (3S2 in our implementation) (Line 20). After creating maps, we randomly colorize each occupied cell and scale up by factor of 3. Note that the proposed environment has very complex maps compared to existing environments (Chevalier- BoiieerrtBivettttt et al. 2018 Küttler et al.) 2020)
unif( 1, ...... 1} (Line 7) or merge them with
C EXPERIMENTAL DETAILS
Our models are implemented on PyTorch and the experiments are conducted on Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz for spatial exploration experiments and single NVIDIA Tesla V100 GPU for reinforcement learning experiments. We will release the entire codebase once our paper gets accepted. However, attached the code for environment generation for FarMap experiments.
14

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Spatial Exploration Environment Generation
Require: N. .V, L, S, K. Peonnect: Pmerge: Pfip
Ensure: A set of maps, {M}.
1: procedure MAPGENERATION
2: Initialize M E [0.1)WSSHHHD)DDXOOSSHHHH
(N, M) grid with interval and each > Figure (1).
Square sized (S,
3: for (8,, ) E {(82, sy]1s; and 8j are adjacent, i S do & Get adjacent grid square pairs. Connect adjacent squares with probability Peunmett-
4:
B(1, Peonmect
5:
if x then
6:
un..! S-11
7:
Connect 9, and 8y with width w. end if
b Figure (2).
8:
9:
B(1, Pmerge)
Merge adjacent squares with probability Pmerge
if x =1 then
11:
Merge and 8j by removing the interval.
b Figure 9 (3).
12:
end end for
13:
14:
for
4- to K do for E {dlc E M, xor c' =, Adj(c)) do Get boundary cells in the map. Flip the cell with probability Pmerge
15:
16:
x ~ B(1, Prip)
cxor
Figure 9 (4)-
18:
end for end for
20:
Divide M into set of isolated maps }m3}
> Figure (7).
Filter out a map in {m:}, where the size smaller than 35² Randomly colorize the occupied cell in each map.
22:
> Figure (8).
23:
Scale up each map {m.} by factor of
24:
end procedure
5+4 Ma [=1
Connect
Merge
Flip
K:9
Peren 0.25
Presp 0.25
0.06
Ramave small maps
Flip
Colorisation
(6)
(8)
Figure 9: Procedure of map generation. (1) We first set square grid where black and white denote empty and occupied, respectively. (2) We randomly connect and (3) merge adjacent grid. (4)-(6) We also randomly flip the boundaries of empty and occupied cell recursively. (7) Then, we remove small isolated subregions and (8) randomly colorize occupied cells. Finally, we increase the size of the map.
C.I FARMAP ENVIRONMENT GENERATION
To generate the environment, we run map generation (Algorithm 2 200 times and then use the 300 largest sized maps. All maps scaled up by factor of 3 after colorization for the task. On every trial, we sample and from (3, 4, 5, 6, 7] and set M = N. K, L e are sampled from [0, 10] and [1, 3), respectively. We set Peonnects Pmerge and ptip to 0. 0.25, 0.25, 0.05, respectively.
15

---

Under review as a conference paper at ICLR 2023
Erifrommens
Envronmerss
Medim Envrrommetts
Endinnments
Pas 751
00
30
00
3900
2008
3030
4000
5000
3000
2000
3000
4000
5000
1200
2009
3900
4009
5009
3300
2048
3000
4000
5006
2.0
606
1000
10
20
20-
3300
Figure 10: Growth in agent-explored map region as function of number of steps from the first step in the environment matches the performance of an augmented coonteer-based baseline with less memory use. Mean spatial map coverage performance (up) and mean memory usage (down) function of number of steps taken in various sizes of environment sets. FarMap achieves better or comparable exploration as Frontier-based exploration baseline (Frontier) (Yamauchi] [997) and an improved version of it (Frontier++) while using only about half the memory on average. The memory benefit is increased as larger environment.
C.2 FARMAP
We run the agent on 1500 different environments: 300 different maps with five random seeds and the starting position and the color of map is changed on each random seed. We set and to 0.9, 2 and 5, respectively. The observation size (h, w) (15,15). If the frontier-based exploring agent is surrounded by a large frontier-edge in an open space, the centroid of the frontier can fall in the interior of the explored space, leading to no new discovery. This causes the agent to become stuck. We improve the agent by instead selecting the nearest unoccupied cell from the nearest frontier state from the centroid. We train RND for million steps without extrinsic reward for each environment with five different random seeds, and other parameters are the same in Section
C.3 FARCURIOSITY
We run Atari experiments for 100 million frames, and we optimize in batches of 128 frames per environment across 32 parallel environments with minibatch size, 4. The learning rate is 0.0001, the reward discount factor " 0.99 and the number of epochs same values mentioned in PPO and RND: we set GAE parameter À as 0.95, value loss coefficient as 1.0, entropy loss coefficient as 0.001, and clip ratio (e Eq. (7) in [Shullann et al. (017)) as 0. We set the fragmentation parameter to 10, and the recall parameter v/ is to 0.99. The maximum size of the LTM 800, and the least recently used fragment is substituted by a new fragment if LTM fully used. For fragmentation, any observation in the fragmentation moment is higher than 0.75, we skip the fragmentation to avoid excessive fragmentation. We use fixed random network in RND feature extractor ((-) for Eq. and all curiosity modules share the same fixed network.
For other parameters, we use the
also add cosine similarity constraint: if the cosine similarity sy with
D COMPARISON ON EACH STEP IN FARMAP EXPERIMENTS
Figures TO summarizes the experimental results on 1500 environments on each step. The lines in the plots are the average of all or a group of experiments and the shaded areas are standard errors of the mean which are not visible due to large number trials. In general, FarMap uses stable amount of memory on average (40 %) over all exploration while other methods use much more memory as map coverage increases. The average memory usage of FarMap is almost consistent in any group of environments the agent explores environments while the usages of Frontier and Frontier+ keep increasing. Moreover, as we already mentioned in Section 4.1 the memory usage gap between FarMap and Frontier++ is dramatically increased while the map coverage gap is small.
16

---

Under review as a conference paper at ICLR 2023
Table 2:
Sensitivity analysis about fragmentation threshold, p in FarMap. The numbers in parentheses
are the standard deviation.
Small (size < 5,000)
Medium (5,000 < size < 15,000)
Large (size 2 15,000)
P
Coverage
Memory
Time
Coverage
Memory
Time
Coverage
Memory
Time
99.1 (7.0) 71.5 (11.3) 117.9 (34.1)
87.1 (19.4) 39.6 (13.7) 146.2 (61.5)
60.9 (19.8) 17.9 (6.6)
148.4 (36.1)
1.5
99.1 (7.1)
75.7 (9.9) 158.0 (653.5)
87.6 (19.0) 50.2 (17.2) 180.1 (60.3)
59.7 (20.1) 23.3 (9.3)
188.9 (51.3)
2.0 (ours)
99.0 (7.2)
(8.7)
278.2 (118.6)
86.4 (19.8) 62,9 (19.3) (119.0
56.6 (20.8) (11.8)
352.5 (110.7)
2.5
98.8 (6.9)
80.7
207.1 (503.4) 89.0 (18.2) 79.7 (18.0) 557.3 (336.8)
58.4 (20.3) 56.9 (19.0)
770.5 (393.0)
3.0
98.8 (6.7)
81.5 (7.6) 296.1 (154.5) 91.0 (17:5) (15.6) 698.2 (308.8)
60.9 (21.5) 67.9 (21.0) 1068.0 (413.1)
Table 3: Sensitivity analysis about decaying factor, 7 in Eq. in FarMap. The numbers in parentheses are the standard deviation.
Small (size 5,000)
Medium (5,000 size 15,000)
Large (size 15,000)
Coverage
Memory
Time
Coverage
Memory
Time
Coverage
Memory
Time
0.8
98.8 (7.2) 79.4 (8.5) 210.5 (104.2)
85.3 (20.6) 64.5 (20.7) 304.0 (228.4) 55.6 (19.7) 32.8 (11.3) 304.8 (112.1)
0.9 (ours)
99.0 (7.2) 79.1 (8.7) 278.2 (118.6)
86.4 (19.8) 62.9 (19.3)
321.4 (119.0)
56.6 (20.8) 3144 (11.)
(110.7)
99.1 (6.8) 79.0 (8.4) 178.3 (74.3)
87.3 (19.1) 61.3 (19.1)
507.5 (4564.6)
59.2 (20.2) 31.9 (12.5) 284.7 (87.7)
0.99
99.1 (6.8) 80.8 (7.9) 262.3 (232.4)
89.3 (18.3) 76.5 (18.3)
453.8 (210.3)
60.4 (20.2) 46.7 (18.4) 541.5 (231.))
E SENSITIVITY ANALYSIS FOR HYPERPARAMETERS IN FARMAP
We test FarMap with various hyperparameters: fragmentation threshold (p). decaying factor (7), and All experiments are conducted in the same environments. While comparing one hyperparamters, we fix the remaining parameters as p 2.0, 7 0.9, 5. Tables 2 presents the performance of FarMap with different fragmentation threshold, p. The smaller value makes it more prone to fragment the space, which means it can use less memory but it overly fragments the space. On the other hand, bigger threshold makes use more memory without fragmentation. Hence, we choose 2 as the threshold value (95% confidence interval if the distribution follows gaussian). On the other hand, our FarMap is robust to the decaying factor and e as shown in Table and Table respectively.
F STATISTICAL ANALYSIS OF FARMAP EXPEIRMENTS
Table shows 95 % confidence interval by using bootstrapping with one million samples on FarMap experiments. The confidence interval is very wide since our metrics map coverage, memory usage, and wall-clock time depend on the size and the complexity of the environment and each method is evaluated on many varied environments. To reduce the effect of variance in environments, we present the relative results comparing to Frontier (dividing the results of Frontier++ and FarMap by the result of Frontier) in Table of Figure [T] For Figure I] we first sort the environments based on their sizes, and then we partition the environments into groups of size 50 and calculate the average and run bootstrapping to get 95 & confidence interval for each group. The confidence intervals of map coverage for both Frontier++ and FarMap are similar. On the other hand, memory usage and wall-clock time are significantly different although there are some overlaps.
G EFFECT OF THE NUMBER OF FRAGMENTATION ON FARCURIOSITY PERFORMANCE
Figure 12 shows the relation between the relative performance improvement and the average number of fragments multiple Atari games. In most games, the number of fragments is up 50, but it reaches the maximum capacity of LTM in Beam Rider. There is no clear global tendency between performance improvement and the number of fragments.
17

---

Under review as a conference paper at ICLR 2023
Table 4: Sensitivity analysis about in Eq. in FarMap. The numbers in parentheses are the standard deviation.
Small (size < 5,000)
Medium (5,000 <. size < 15,000)
Large (sizc > 15,000)
Coverage
Memory
Time
Coverage
Memory
Time
Coverage
Memory
Time
(7.1) 79.1 (8.7) 198.0 (86.4)
86.8 (19.4) 63.0 63.0 (19.2) 275.3 (93.7)
56.6 (20.7) 31,5 (119) 294.8 (81.4)
99.0 (7.2) 79.1 (8.7) 198.1 (88.3)
86.7 (19.5) 63.0 (19.1) 271.3 (89.1)
56.5 (20.7) 31.5 (119) 294.5 (81.5)
(ours)
99.0
79.1 (8.7) 278.2 (118.6))
86.4 (19.8) 62.9 (19.3)
321.4 (119.0)
56.6 (20.8) 31.4 (1L8) 352.5 (110.7)
10
99.0
79.1 (8.7)
197.1 (91.9)
86.6 (19.5) 62.9 (19.1) 272.5 (88.2)
56.3 (20.9) 31.4 (11.8)
294.9 (82.1)
15
99.0 (7.3) 79.1 (8.7)
198.5 (94.4)
86.6 (19.5) 63.0 (19.1) 288.7 (247.9)
55.9 (20.7) 31.1 (11.6)
295.7 (84.4)
Table 5: Comparison average map coverage (%), memory use (%), and wall-clock time (s) for small, medium, and large environments. The memory usage advantage of FarMap relative to its counterparts grows with environment size. The numbers in parentheses are 95 % confidence interval generated by bootstrap with million samples.
Small Glae 5,000
Mediiam 5,000 S slze 15,000)
Large (siec 15,000)
Coverage
Memory
Time
Coverage
Memocy
Time
Coverage
Menooy
Time
Fronter
(7.2, 100,0) 50.4 (61.8 88.7) 360.5 (154, 775) 76,3 (15.6 99.5) 73.3 (13.0, 92.3) $71.9 (290, 2020)
(6.1 54.3) 48.4 (388)388833 1260.0 2211,111999 3159)
Founier
(9.5, 100,0) B1.6 (71. 88.7) 3411 (115, 852)
(1,
65.9 (12.5,
1099.5 (365,
68.1 (38,942)
1872.4 (423,
FurMap
99.0 (96.3 100,0) 79.1 (61.4, N8.0) 278.2 (13M, 538)
80.4 (15.6, 100,0) 62.9 (12.S, 90.3) 321.4 (191, $28)
56.6 16.1,
91.3)
(1.
352.5 (202, 635)
Frontier
Front
FarMap
Releettoe Memmory Usaqe
Balettvve Walt Time
Reletive Coveinge
1-
0.7
1.1
1.8
3.0
4.9
0.2 13.4
22.0
0.7
1.1
1.8
3.0
4.9
0.2 13.4
22.0
0.7
1.2
1.8
3.0
4.9 0.3 13.4
22.0
Environment Size (80
Environment Size (80
Environment Size 130
Figure 11: Relative map coverage, memory usage, and wall-clock time normalized by the results from Frontier on each environment. The mean (line) and 95% confidence interval (shade) are calculated by bootstrap with one million samples each from groups of 50 environments ordered by size.
H INDIVIDUAL PERFORMANCE IN ATARI GAMES
presents the mean cumulative extrinsic rewards (also known as extrinsic return) and its standard errors at varying number of training data (frames) three different random trials in fifteen games including four hard Atari games: Gravitar, Montezuma's 's Revenge, Pitfall and Private Eye. FarCuriosity outperforms RND in ten environments and has worse performance two environments. In Breakout and Space Invaders, FarCuriosity outperforms RND by a smaller margin. This is because the observations in those environments are more similar, and once the agent kills all enemies or hits all of the bricks, the same enemies and bricks are revived. Hence, RND does not suffer from catastrophic forgetting and achieves similar results with FarCuriosity. FarCuriosity shows similar performance in Pong, Star Gunner, and Pitfall. We believe this is because the observation space is less visually diverse in those games. In Pong for example, the only visually dynamic features are the agent, the opponent, and the ball, all of which move no fragmentations occur in Star Gunner. Consequently, catastrophic forgetting does not happen and FarCuriosity does not demonstrate significant advantage in this environment. On the other hand, FarCuriosity shows worse performance compared to RND in Tennis and Montezuma's 's Revenge. Tennis is the most homogeneous game in Atari shown in Figure and Montezuma's Revenge also one of the most homogeneous games according to our measurement since RND agent is difficult to explore many rooms. We hypothesize that this homogeneity can lead to wrong fragmentation. which degrades the performance.
Figure 13
fixed monotone background. Moreover,
18

---

Under review as a conference paper at ICLR 2023
Table 6: Average and 95% confidence interval of relative map coverage, memory usage and wall-clock time of Frontier++ and FarMap over Frontier. Confidence interval calculated by bootstrap with one million samples.
Small
Medicam
Large 15,000)
Model
Memory
Time
Coverge
Memory
Time
Memory
Time
Pronter--
(0.99 1.20) 1.03 (1,10, 1.29) 0.95 1,000
(0.9, 2.30) 1.24 2.20) 1,56 (0.08, 2.N0 LA8 (1,00, 3,990 1,28
4.80)
FuzMap
1003 (8.99 1.20)
1.00 (8.72, 1,20)
0,85 (.41, 1.70)
(0.79, 2.20)
0,90 (8.42, 140) 0.46 (0.16, 1.30)
1.56 (0,79,
0.84 (0.37, 1,70) 0.37 (9.13, 1.30
Relative Extrinsic Reward Improvement
Improvement
Pittil
Jamesbond
Astero di Hieer Raid Space Inveders Scatuea
2
Private Eye
50
Beam Rider
Breakout
Pong
Star Gunner
Montezuma's Revenge
RParCuriosity RRND
(Relative Improvement)
-2
RRND
Tennis
Deteoriation
-3
200
400
600
800
The Number of Fragments
Figure 12: The relative performance improvement over RND performance (RRDD) in various Atari games. The average number of fragments at most in most games. Buer Baid
Jamesbonnd
Deam Rider
Asterolds
15900
40000
20000
2000
1000
2.5
302
20
300
2.5
60
300
20
60
300
Grovita
Privato Eyc
Space Ircaders
6.00
4.00
2.00
2.
66
303
20
66
302
2.
66
300
20
60
300
thel
Star Gurner
2.00
30000
15:00-
5:00
47
60
45
60
Testas
Feames una)
Teames cos)
Tonris
RND FarCuriosity
-10
Tramess mm1
Tramer
Figure 13: Mean extrinsic reward of RNN-based policies: RND and FarCuriosity with extrinsic reward on fifteen Atari games. The environments are sorted by the heterogeneity measured in Section 4.2 from highest to the lowest
19

---

Under review as a conference paper at ICLR 2023
000000
2:000
AA
(a) Asteroids
(b) Beam Rider
(c) Boxing
(d) Breakout
(e) Gravitar
(l) Jameshond
Momeruma's is Revange
(h) Pirfall
Faliee
28014
ii Pong
Private Bye
(k) River Raid
(1) Seaquest
X
STPR
gyrat Talers
(m) Space Invaders
(n) Star Gunner
(0) Tennis
Figure 14: Various Atari environments used for comparing FarCuriosity and RND.
20


Reviews:
[{"review_id": "h0o7XNX8l8M", "reviewer": "Reviewer_RmS4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a function approximation framework for mapping and exploration in RL. The function approximation scheme uses multiple local models that predict the next observation, and new local models get created when a prediction error is above a user-defined threshold. The local model used at each step is determined by the similarity of the current observation to the observation stored in memory for each local model. The mapping procedure also creates a graph of the local models to allow for exploration across local regions. In the reinforcement learning setting, the local models' intended benefit is overcoming catastrophic forgetting, which occurs when using a single neural network to predict intrinsic reward signals. ", "summary_of_the_review": "The topic of the paper is worth further study, but due to poor experimentation this paper is not yet ready for publication. \n\n--update--\nAfter discussing with the authors and seeing changes to the paper, it has improved, but still lacks experiments that demonstrate the method is behaving as intended. I updated my score to a 5 marginally below the threshold. ", "strength_and_weaknesses": "The idea forgoes the current trend of having monolithic forms of function approximation and tries to address an important problem with many algorithms. However, some key issues need to be addressed before the paper is ready for publication. The primary issue is that the experiments do not substantiate the claims or provide meaningful insights into the algorithms. I will detail these below. \n\nFor the FarMap and FarCuriosity experiments, each method is run on multiple environments to show that the new methods outperform the existing ones. There are several issues with the experimental setup. The first is that only one selection of hyperparameters is considered. As has been pointed out several times (Henderson et al. 2018, Jordan et al. 2020, ml ones), this leads to arbitrary comparisons in claiming that one method outperforms another. So these experiments cannot say one method is better than another outside of these specific hyperparameter choices. This experiment is of little value because the hyperparameters need to be tuned for different environments. \n\nAnother issue in the experiments is the comparison of memory usage. The % of memory used is not an informative metric because it depends on the system's memory (more of a minor issue). It would be better to show the actual memory usage. Also, the amount of memory used by each method highly depends on the implementation. There can be numerous code optimizations to reduce the memory of each method. It is worth considering a metric independent of the actual implementation to provide a fair comparison. Showing the actual memory usage of a specific implementation in addition to the other metric would provide a realistic context of what one could expect. Similar to the other experiments, the results here also depend on the hyperparameters, and their effect must be considered. \n\nTo address the hyperparameter issues, one could consider experiments to answer other questions that would be more helpful than a performance comparison. A few possible questions: 1) how does changing the number steps before fragmentation impact the number of local maps, and 2) how sensitive is the behavior of the algorithm to epsilon? These are important questions if you want someone to be able to use the algorithm successfully. \n\nFigure 5: Standard error is not an accurate representation of confidence. Also, how was it computed because the number of trials is not 1500, as stated on page 7? The run of the algorithm on different problems is not an i.i.d sample, so you cannot lump them all together to compute the variance. \n\nIn Table 1, if you want to compare the performance of each algorithm, you should use confidence intervals to identify if one method is better than another, not the empirical measure. Based on the large standard deviations, it is unclear whether one method is better than another. Remember to correct for multiple comparisons amongst the algorithms when making these comparisons. \n\nPage 8: \"On the other hand, RND generates a higher intrinsic reward (higher prediction error) as training progresses, implying that this method suffers from catastrophic forgetting\"\nThe experiments are not a valid test of catastrophic forgetting taking place. If you want to measure catastrophic forgetting, then measure it with an experiment. This statement is simply a guess at what is going on. However, this is a great hypothesis that should be tested, i.e., does RND accurately predict the intrinsic reward signal at previously seen states later in training? Then follow it up with a question based on your approach. Does splitting the function approximator at points of high prediction error provide longer-term memory of the intrinsic reward signal? Performance-based experiments can only be used to test the differences in performance, not underlying factors like catastrophic forgetting. \n\nA few questions:\nPage 5: is the backward direction backward in time? Because the agent could be facing any direction. Defining the method with math would make things more precise and avoid confusion. \n\nIn what sort of problems is the FarMap applicable? The prediction of the observation is not a true model of what occurs, e.g., the agent could move left or right, and the local map could not predict the outcome. Additionally, would it not induce many fragmentations if the colors change in the map with a high frequency? \n\nWhat feature extractor was used in the RL experiments?\n\nReferences:\nHenderson, P., Islam, R., Bachman, P., Pineau, J., Precup, D., and Meger, D. Deep reinforcement learning that matters. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), pp. 3207–3214, 2018.\n\nJordan, S., Chandak, Y., Cohen, D., Zhang, M., & Thomas, P. (2020, November). Evaluating the performance of reinforcement learning algorithms. In International Conference on Machine Learning (pp. 4962-4973). PMLR.\n\nLucic, M., Kurach, K., Michalski, M., Gelly, S., and Bousquet, O. Are gans created equal? A large-scale study. In Advances in Neural Information Processing Systems 31., pp. 698–707, 2018.\n\nMelis, G., Dyer, C., and Blunsom, P. On the state of the art of evaluation in neural language models. In 6th International Conference on Learning Representations, ICLR. OpenReview.net, 2018.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "TToibmayfB", "reviewer": "Reviewer_FqLm", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work introduces the Fragmentation-and-Recall framework that can be applied for exploration in spatial and general reinforcement learning problems. The idea behind the proposed framework is the fragmentation of the space based on a surprising signal. In this way, agents create local maps (or curiosity modules in the case of RL)  stored in a long-term term and recalled when the agent returns to the state where the fragmentation happened. In this way, local information can be reused by the agent. Authors have applied the framework in the settings of spatial exploration (*FarMap*) and general reinforcement learning exploration (*FarCuriosity*).", "summary_of_the_review": "In general, the proposed Fragmentation-and-Recall framework is somehow novel and can be applied in both spatial exploration and general reinforcement learning exploration settings. The main limitation of this work is its clarity, as a lot of useful information is missed or doesn't present in depth. Also, the empirical analysis should be considered real maps in the case of spatial tasks and more hard-exploration environments in the RL context.\n", "strength_and_weaknesses": "**Strengths**\n\n- The proposed Fragmentation-and-Recall framework is general and can be applied in both the spatial exploration (*FarMap*)  and general reinforcement learning exploration  (*FarCuriosity*) settings. \n- By using local maps and model fragments we can avoid catastrophic forgetting in learning heterogeneous environments.\n- Experiments have been conducted in procedurally-generated spatial environments and on reinforcement learning benchmarks, showing that the proposed method is more efficient regarding memory usage.\n\n**Weaknesses**\n\n- Many of the Fragmentation-and-Recall framework components should be described in more detail.\n- The proposed *FarMap* does not outperform Frontier++. Actually, Frontier++ performs much better compared to the  *FarMap* as the map size increases.\n- Experiments at hard-exploration environments are missed (i.e. Montezuma’s revenge)\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LjOCA5VQ0H", "reviewer": "Reviewer_m2i7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work presents a framework for efficient exploration based on the idea of fragmentation and recall. An agent exploring an environment maintains a local map/model in its short-term memory (STM). At each time step, the agent can compute how well the current observation and the model's prediction of it match. If there is a high mismatch or surprise, a *fragmentation* event occurs, where the agent saves the current local model into a long-term memory (LTM) and initiates a new model. The locations where fragmentation occur are known as fracture points. At such fracture points, the agent is able to *recall* previously stored models, corresponding to overlapping fragments or local models, from its LTM and use these to guide further exploration. \n\nThis framework is applied to (i) spatial exploration (FarMap) in 2D grid world type environments , and (ii) curiosity-driven RL (FarCuriosity) in Atari games. In both these settings, the experimental results demonstrate that the fragmentation and recall approach performs better than the respective baselines. ", "summary_of_the_review": "This work presents an interesting approach to efficient exploration based on the idea of fragmentation and recall. While the initial results are promising, I find the current instantiation of the local predictive spatial map limiting. In addition, I think the presentation could be improved to make this a more engaging paper. ", "strength_and_weaknesses": "This work is a proof-of-concept for the fragmentation and recall approach to efficient exploration.\nThe empirical results presented here demonstrate the advantage of this approach. In the spatial exploration task, FarMap achieves comparable map coverage as an improved Frontier-based exploration baseline, but faster and at a substantially lower memory cost. In the RL setting, FarCuriosity obtains higher extrinsic reward than Random Network Distillation (RND) in Atari games with heterogenous environments. \n\nWhile the initial results presented here are promising, it is not clear how this approach would scale to more complex settings. For instance, in the FarMap setting, the local observation is a top-down view of the environment and has the same structure as the local predictive spatial map.  If the input observation stream is an egocentric view from a 3-D environment, how would it be handled? \n\nIt is not clear how the size of the local predictive map $(H, W)$ grows. Also, it is not clear how the observation $o_t$ is transformed to $o_t^{\\prime}$. It looks like the size of the current map and the agent's position need to be tracked for this. However, the agent's position might not always be known/cannot be tracked accurately, e.g., when actions are stochastic/noisy.  \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7wMHFmbDSu", "reviewer": "Reviewer_HdLq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose the utilization of the concept of Fragmentation-and-Recall to solve spatial and reinforcement learning problems. In the former case, which they call FarMap, they address the use case of exploration in sub-map based SLAM and in the latter case, which they call FarCuriosity, the problem of catastrophic forgetting in curiosity-driven RL.\n\nIn both cases, the exploring agent focuses on a sub-part of the map or state-space, constructing a local model of exploration (saved in a Short-Term Memory or STM). Once it encounters a novel (also termed “surprising”) new state (called a fragmentation point in the paper), it either stores the sub-map (local map) explored so far to a Long-Term Memory (LTM) or retrieves a sub-map from LTM that is consistent to the new observation. Finally, further exploration is guided through defining sub-goals for the agent either as new points in the LTM or through selecting previous fragmentation points to be reached.\n\nThe authors provide experimental results for both cases, using procedurally generated maps for the FarMap application and targeted Atari games in the FarCuriosity case, where they highlight the pros and cons of their method compared to baseline algorithms.\n", "summary_of_the_review": "The paper is well written and in a good shape although it may benefit from some re-arrangement and early explanations of crucial concepts. The experimental results on both FarCuriosity and FarMap outperform existing approaches. However, especially for FarMap I am not an expert in the field to judge related work and state of the art to use as baselines. But more importantly, I do not see a major improvement of FarMap ofer Kuskal et al. (2021). On the other side, for FarCuriosity the explanation/discussion (there are a few open questions about the design choices) and the experimental section (I would have expected some specific baselines and environments) could be more thoroughly elaborated. \n\n\n**Post-Rebuttal**\n\nI would like to thank the authors for their response. I updated my recommendation to 6 as I also share some of the criticism of the other reviewers. ", "strength_and_weaknesses": "**Strengths:**\n- The paper is well-written, and the high-quality figures and system schematics really communicate the intuition behind the paper ideas\n- There is extensive and correct use of references, as well as comparison to previous work\n- The idea of fragmentation and recall in curiosity-driven Reinforcement Learning is both novel and useful\n\n**Weaknesses:**\n- In my opinion, the authors are not clearly demonstrating the necessary novelty step over Klukas et al. (2021), with respect to the FarMap application. \n- Also, I find it confusing that two applications (FarMap and FarCuriocity) are described in parallel. Why not focusing on one (maybe the most novel is the FarCuriosity) and provide more evaluation experiments there?\n- Even though the authors provide a sensitivity analysis / ablation study for some of the hyper-parameters of the algorithm, it is not clear how these should be tuned (i.e., what would be their boundaries) in a new application / use case.  \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject