Learning Achievement Structure for Structured Exploration in Domains with Sparse Reward
Authors: Zihan Zhou
Animesh Garg
Venue: ICLR 2023 poster (2023)
Keywords: deep reinforcement learning
structured exploration

Abstract: We propose Structured Exploration with Achievements (SEA), a multi-stage reinforcement learning algorithm designed for achievement-based environments, a particular type of environment with an internal achievement set. SEA first uses offline data to learn a representation of the known achievements with a determinant loss function, then recovers the dependency graph of the learned achievements with a heuristic algorithm, and finally interacts with the environment online to learn policies that master known achievements and explore new ones with a controller built with the recovered dependency graph. We empirically demonstrate that SEA can recover the achievement structure accurately and improve exploration in hard domains such as Crafter that are procedurally generated with high-dimensional observations like images.

Published as a conference paper at ICLR 2023
LEARNING ACHIEVEMENT STRUCTURE FOR STRUC- TURED EXPLORATION IN DOMAINS WITH SPARSE RE-
WARD
Zihan Zhou
Animesh Garg
University of Toronto
University of Toronto
Vector Institute
Vector Institute ga gargecs. toronto. edu
footoredo@gmai com
ABSTRACT
We propose Structured Exploration with Achievements (SEA), a multi-stage re- inforcement learning algorithm designed for achievement-based environments, particular type of environment with an internal achievement set. SEA first uses of- fline data to learn representation of the known achievements with determinant loss function, then recovers the dependency graph of the learned achievements with heuristic algorithm, and finally interacts with the environment online learn policies that master known achievements and explore new ones with con- troller built with the recovered dependency graph. We empirically demonstrate that SEA can recover the achievement structure accurately and improve explo- ration hard domains such as Crufter that are procedurally generated with high- dimensional observations like images.
INTRODUCTION
Exploration in complex environments with long horizon and high-dimensional input such images has always been challenging in reinforcement learning. In recent years, multiple works (Stadie et al.
2015
Bellemare al. 2016 Tang et al. 2017)) Pathak et al. 2017 Burda et al. 2019a b Badia al.
2020 propose to use intrinsic motivation to encourage the agent to explore fess-freyuently visited states or transitions and gain success in some hard exploration tasks RL. Go-explore (Ecoffet al. (221]) proposes to solve the hard exploration problem by building state archive and train- ing worker policies to reach the old states and explore new states. The shared trait these two streams of RL exploration algorithms is that they are both built the idea of increasing the visiting frequency of unfamiliar states, either by providing intrinsic motivation or doing explicit planning. However, This idea can be ineffective in procedurally generated environments since states in such environments can be infinite and scattered, to the extent that the same state may never appear twice. This is why exploration in such environments rally generated environments, there will be finite underlying structure fixed in all environment instantiations. This underlying structure is essentially what makes the environment "meaningful". Therefore, discovering this structure becomes vital in solving procedurally generated environments.
be extremely hard. However, in most procedu-
In this work, we set our sight on achievement- bassd environments. Specifically, an achievement- based environment has a finite set of achievements. The agent only gets rewarded when it completes one of the achievements for the first time in an episode. Achievement- based environments are com- monly seen in video games such as Minecraft. We argue that this type of environment also models many real-life tasks. For example, when we try to learn a new dish, the recipe usually decom- poses the whole dish into multiple intermediate steps, where completing each step can be seen an achievement. A good example of achievement based environments in reinforcement learning com- munity is Crafter (Hafner 2021b. 2d open-world game with procedurally generated world maps that includes _ achievements. We introduce this environment in more detail in Sec. B.1.
Achievement-basee environments bring both benefits and challenges to reinforcement learning ploration. On one hand, the achievement structure is a perfect invariant structure procedurally generated environment. On the other hand, the reward signal in such environment is sparse since
21 in modified version.

---

Published as a conference paper at ICLR 2023
the agent is only rewarded when achievement is unlocked. The reward signal can even be con- fusing since unlocking different achievements grants the same reward.
We propose Structured Exploration with Achievements (SEA), multi-stage algorithm that effee- tively solves exploration in achievement- ment structure of the environment from collected trajectories, either from experts or other bootstrap- ping RL algorithms. With the recovered structure, SEA deploys a nonparametric meta-controller to learn set of sub-policies that reach every discovered achievement and start from there explore new ones.
environments. SEA first tries to recover the achieve-
We empirically evaluate SEA in Crafter and achievement-based environment TreeMaze that we designed based on MiniGrid can complete the hard exploration achievements consistently and reach the hardest achievement (col wwl.leec..diiii aimmndd) in the game at non-negligible frequency. None of our tested baselines can even complete any of the hard exploration achievements, and to the best of our knowledge, SEA is the first algorithm to complete this challenge. We also show that SEA can accurately recover the achievement dependency structure in both environments.
Seevalier-Boisvert et al. 2018). In Crafter. our algorithm
Although uncommon in the current RL scene, we argue that the schievement-basee reward system can be a good environment design choice. Designing a set of achievements can be easier than crafting specific rewards system for the agent to learn. With the structure recovery module in SEA, the agent can automatically discover the optimal progression route to the desired task, alleviating the need for a high-quality achievement set. Furthermore, shown in the TheeMaze experiments, the achievements can even be not semantically relevant to the tasks.
2 RELATED WORK
Exploration in reinforcement learning. Exploration in RL has long been important topic, which can date back to e-greedy and UCB algorithms in colti-aarmed-banee problems. In recent years, intrinsic motivation-base exploration algorithms (Stadie et al. [201 Bellemare et al. 2016 Tang et al. 2017 Pathak et al. 2017] Burda et al., [019a] b Badia et al. 2020) gained great success in this area. These algorithms aim to find estimation of the state transition visiting frequency and use an intrinsic reward to encourage the agent to visit the less frequently visited states. However, they can be ineffective when the environment is procedurally generated, where the number of states and transitions can be infinite and scattered.
Another line of work in this area relevant ours is the go-explore (Ecoffet et al. 2021 series. Go-explore builds an archive of explored states which are grouped into cells and learns a set of goal- conditioned policies that reach each cell. It then starts exploration from the archived cells to find new cells and updating the archive iteratively. Go-explore shows success in the hard exploration tasks in Atari games. However, go-explore can also be ineffective in procedurally generated environments since it uses image down-sampling as the default state abstraction method. Another point where our work differs from go-explore is that we don't seek to group all states into cells, but instead only group the few import ones. This is helpful since archiving all the states and learning all the coal-conditioned policies can take up huge amount of resources.
Hierarchical reinforcement learning, Hierarchical reinforcement learning (HRL) explores the idea of dividing large and complex task into smaller sub-tasks with reusable skills (Dayan & Hinton 1992 Sutton et al.; 1999; [Bcoon et al. Vezhnevess et al. 2017: Nachum et al. 2018))
Eysenbach al. (2019) and Hartikainen et (2020) propose first learn a set of unsupervised
skills then build policy with the learned skills for faster learning and better generalization; Bacon
et al. (2077) builds a set of policy options to learn. Goal-conditioned HRL (Vezhnevets et al. 2017
Nachum et al. 2018 2019) train manager policy that proposes parameterized goals and a goal- conditioned worker policy to reach the proposed goals. Kulkarni et al. (0016); Lyu et al. (2019) )
Rafati & Noelle (2019); Sohn et al. (2020); Costales et (2022) train set of sub-policies solve the subtasks provided by the environment and a meta-controller to maximize the reward. This line of work is similar to ours in that they assume the subtasks are provided by the environment. However, in our work, we don't 't assume access to any additional subgoal information such as subgoal completion signals from the environment that are typically required in this line of work. Additionally, the
2

---

Published as a conference paper at ICLR 2023
Collect Wood
Place Table
Make Wood Sword
Eat Caw
Collect Cool
Make Wood Riooee
Place Furnaco
Collect Stone
Makic Stone Sward
Delest Stidesos
Iron
Make Stone Pidaae
Maace Stane
Make tron Sword
Make ron Pickawe
Collect Sapling
Visle .p
Defest Zombee
Co lest Darmond
Place Plant
Cellect Brint
(a) Crafter environment.
(b) Crafter achievements dependency graph.
Figure 1: The Crafter environment.
problems that we are solving are more complex, namely including more tasks and being image- based and procedurally generated.
Despite being conceptually similar to the subgoal/subtask in HRL, the achievement in our work bears different meaning and serves different purpose. For extended discussion on this topic, the reader can refer to Section D.I in the appendix.
Building world models. Watter al. (2015); Karl al. (2017); Ha & Schmidhuber (2018); Hafner et al.) (2021) argue that learning a compact latent space world model is beneficial in en- vironments with dige-simensional inputs such as images. L.3p (Zhang et al., 2021) proposes to represent the world model as a graph by clustering states into nodes, similar to SEA. However, L learns the state representation with the objective to recover reachability, which is not guaranteed to be useful in exploration.
Reward machines. Reward machines (Icarte et al. 2018a b) is a concept that uses linear temporal logic language describe non-Markovian reward function. Recent works (Camacho Icarte et al. 2019 2022) exploit this concept to do structured reinforcement learning and improve performance. However, they depend on the environment providing a labeling function to learn the reward machine instead of learning one from the environment. Achievement-basse environments also feature non-Markovian reward function since completing one achievement only gets rewarded once in an episode, therefore it can be seen as special instance of the reward machines.
2019
PROBLEM SETUP
3.1 CRAFTER
To better explain the achievement-based environment, we introduce Crafte Haffer 2021 ).
Fig. Ia). Crafter is 2d open-world game featuring procedurally generated world map and 21 in-game achievements. In this game, the agent needs to control the character to explore the world by collecting materials, crafting tools, and defeating monsters. Whenever the agent completes a certain achievement for the first time in an episode, it will receive a reward of one. For any subsequent completion, the agent will not rewarded. The goal of the game is unlock as many achieve- ments possible. In Crafter, some achievements may have dependencies on others. For example, the ma wew_wodd_ppp xe achievement depends on the p1 place_tabl achievement since craft- ing wood pickaxe requires the agent be near crafting table. These achievements and their dependencies form directed acyclic graph (DAG), demonstrated in Fig.
3.2 MARKOV DECISION PROCESS WITH ACHIEVEMENTS
We formalize our definition of achievement-basee environments a Markov decision process with achievements (MDPA). A Markov decision process with achievements is defined by 5-tuple
We slightly modified version of Crafter. The detailed modification he found Appendix.
3

---

Published as a conference paper at ICLR 2023
Environment
State
Achievement
Action
Mela-conbroller
classifier
Torget Achlevement
Achievement Reword
(0) ( (ed((eeppp((kk.)])
palicp of kg)
Agent
Data Collecting
Achlevement Learning
Dependency Graph Learning
Sub-pollcy Learning and Exploration
Algorithm overview. SEA comprises of four parts. (1) It starts with collecting trajectories either from domain experts previously trained agents. (2) With the collected trajectories, SEA learns the achievement representation with Eqn. | and builds an achievement classifier by cluster- ing the learned representations. (3) SEA then recovers an achievement dependency graph with the classifier and the collected trajectories. (4) We train a set of sub-policies to reach each recognized achievement and an exploration policy for new achievements. target achievements according to the achievement dependency graph. We use the achievement clas- sifier to filter out the reward signal for the target achievement.
Figure 2:
meta-controller is used to propose
(S, A, I. , G), where S is the set of states, A is the set of actions, T' Sx.4 - A state transition function, is the of achievements, and G S Ax + [0) is the achieve- ment completion function. For any state transition tuple (st, a, St+1), the achievement completion function maps
$ is the stochastic
either one of the achievements in I, meaning that particular achievement is com- pleted at this step, or 9. meaning none of the achievements is completed. Achievement unlocking re- ward can be derived from an MDPA trajectory. Specifically, for a trajectory T (80, ag 81 ...., 87 8T), is:
the reward at step E E0,, O,..., T
F1 = 1[G(st, ae 8141) # 0]
G at s1+1) # G(sy, aysy,ar,ee sp+1)), 1!
II
where [ is the indicator function. Note that directly adding the reward function into MDPA breaks its Markovian property since the agent will only be rewarded for the first time com- pletes an achievement. We can instead derive standard MDP from MDPA by defining a set of achievement-extendee states S* = x 2 where we store the achievement completion informa- tion into the state. We can also define the corresponding state transition function T : S and reward function R. S* x AA S - R to complete the derivation.
METHOD
The advantage of learning in MDPA is that achievements, hinted by reward signals, are invariant across different environment instantiations. These achievements can therefore seen as check- points, which allow us to do sewide-and-conquee of the hard environment exploration task.
Following this argument, we propose an algorithm Structured Exploration with Achievements (SEA), which recovers the underlying achievement structure and conducts structural explorations. Specifi- cally, we use the data collected from either previously trained agents or experts to recover the known achievements and their corresponding structures. With the recovered achievement structure, then train multiple sub-policies to reach every discovered achievement and start individual searches for new achievements from there.

---

Published as a conference paper at ICLR 2023
4.1 ACHIEVEMENT LEARNING
The first step of our method is to identify the achievements in the environment by learning the representations of the achievements and then clustering the achievements with their representations. = 1} be the step set where an
For any trajectory т = (So, ao..... ,T)...,ST), we define U, == {t achievement unlocked. For representatio dimension W, we want to train a model parameterized by 0 that maps the tuple (st, ae, 8t+1) where t E Ur. to vector of size W. We achieve this by using the uniqueness property of achievements, that every two steps U, correspond to different achievements. In other words, we want to ensure the representations of each pair of steps in U,, are as distinct as possible.
Let 5, (5t, des St+1). We define the achievement representation distance matrix of trajectory T as D, := (5c,) 60( and D, == D max D,.
Normalization is used to prevent the representation from outward expanding, since expanding in- creases the pairwise distance but not the separability required for clustering. To maximize the pair- wise distance of the achievement representations, we use the following loss:
Lachi (8) = E, [- det (exp (-+D+))]
(1)
where det(-) calculates the determinant of a matrix. The loss reaches the minimum value of when every pair of achievement representations in a trajectory are sufficiently different so that the matrix close to the identity matrix. This formulation inspired by Kulesza (2012) and (Parker-Holder et al. (2020). Compared to directly maximizing the average pairwise distances, the advantage of this
formulation that it prevents the different achievement representations in an episode from forming clusters. In such case, the average pairwise distance is still high but the determinant loss is close to zero.
We then use the K-Means algorithm for clustering. Suppose we cluster the achievements into N clusters with centroids denoted as . We can now build an achievement classifier AC(() := arg min, (())(3) c1l22 However, improve the generalization of this classifier, would like it to gain the ability to recognize new achievements that are not in the dataset. To do this, we set threshold b- 0.5 min;, [|c cyl12. Let 8" arg min; (1 call2, the classifier becomes:
1' if (() ci- otherwise,
AC( =
-1
where -1 means 5 is unrecognized new achievement.
4.2 ACHIEVEMENT DEPENDENCY GRAPH
With the achievements identified, then use heuristic algorithm to build preliminary achieve- ment dependency graph. The algorithm comprises of two parts: 1) we build a complete dependency graph; 2) we trim down the complete graph into minimal DAG.
We represent both graphs with an adjacency matrix of N nodes. We first calculate two heuristics of the collected trajectories.
BEFOREij = (1r, = = A Un, =j 14 < <12 Ur VTH HAPPEN; [V; te Ur. VTH
We say is dependency of j if every time j happens, happens before j. Therefore, for the first part,
G.y == [[EEFORE,)) HHAPPEN -1-
where is account for identification emror. For small e, G is guaranteed to be DAG.
5

---

Published as a conference paper at ICLR 2023
100%
accuracy
75%
50%
25%
200k
50k
0%
# cluster
achievement
Figure Clustering accuracy with different data sizes. Clusters and achievements are sorted in descending order of prediction accuracy.
For the second part, need to remove the unnecessary edges in G to get minimal DAG while maintaining the topology of G. this case, an edge is considered unnecessary if removing it does affect the topological order of the graph. Since removing edge + f can only allow node to appear earlier in the topological order, we only need to calculate the left-most position of a node, denoted as LEFTMOST(G..2
G= = G ([LETTMoT(CA(i-oj)) LEF)MOST(G,,)]-
We point out that our recovered graph may include more dependency edges than the ground truth owing to the non-causal correlations from either agent preference or insufficient data. We will address this issue in the next section.
4.3 SUB-POLICY LEARNING AND EXPLORATION
The last part our algorithm is learn a set of sub-policies that reach every achievement node and do exploration from them. A sub-policy is parameterized achievement-conditien ow (a|s, g) where w the parameter shared among all sub-policies and g E is the target achieve- ment. Each sub-policy only receives reward of upon reaching its target achievement, which can be done using the achievement classifier in Sec. 4.1
policy
To learn the sub-policie policies, also need meta-controller (g]s) that proposes target achievement to learn. One option is to randomly select a new one when an achievement is completed. However, this can be ineffective when target achievement is proposed before all its dependencies This is because the sub-policy only has access to the reward of its target achievement, which makes the exploration much harder. Therefore, we instead use controller that topologically traverses the dependency graph. At the beginning of the episode or upon completion of any achievement, the controller randomly selects unfinished achievement whose dependent achievements have all been completed. In our implementation, we also bias the selection probability towards direct child of the last completed achievement to provide continuity.
completed.
The unnecessary dependencies introduced in the last step won't ton't affect the effectiveness of sub-policy learning since following the recovered dependency graph still guarantees the necessary topological order. To explore more accurate graph, we let the meta-controller selects the new target randomly with a small possibility. We refer the readers to Sec. C.1.I for more details on the mota-controller.
5
EXPERIMENTS
5.1 EXPERIMENT SETUP
Our experiments are designed to evaluate the three main parts of our algorithm: achievement learn- ing, graph recovery, and sub-policy learning & exploration. To better investigate different aspects of our algorithm, we design pedagogical environment based on MiniGrid (Chevalier Boitserrr et al. 2018) called TreeMaze (Fig. 5). TreeMaze has 2 columns of N rooms. Each room contains either a key that unlocks other rooms, an object that can be interacted with, or nothing. key can only unlock doors with the same color the key, while some of the rooms not locked. In TreeMaze.

---

Published as a conference paper at ICLR 2023
188%
188%
IMPALA
unlock rate
unlock rate
50%
50%
25%
IMPALA
254
8.88 0. 0.50 6 6. 1.00
1.25
1.50
8.88
0.25
0.50 6. 7.
1.00
1.25
1. 1.
episode
1e6
episode
1e6
(a) Easy set.
(b) Hard set.
Figure 4: Mean unlocking rate comparison in easy and hard achievement set.
every interaction, including opening door, picking up key, and interacting with other objects, seen as an achievement. The rooms are generated with the guarantee that it's possible to unlock all achievements. The locations of the rooms randomized but the dependency graph is fixed. We use three versions of TreeMaze in our experiments, the TreeMaze-Ean Easy which contains 4 rooms and 9 achievements, the TreeMaze-Normal which contains 10 rooms and 19 achievements and the TreeMaze- that contains 18 rooms and 30 achievements.
For the Crafter environment, we also include limited version (Crafter-Limited) which only contains 7 of the 21 achievements in the full environment.
We train a vanilla IMPALA (Espeholt et al., 2018) agent for the initial data gathering in each environment. In the full Crafter environment, the IMPALA agent discovers 17 achieve- ments (with 1% reaching rate); In all the remaining envi- ronments, the IMPALA agents discover all of the achievements. We consider the 17 achievements reachable by a vanilla IM- PALA agent the easy achievement set, and the remaining four achievements (make iron pickaxe, make iron sword, feat. zombie e, col lect di diamond) the hard achievement set. The reason why these achievements are particularly hard to complete is that crafting iron tools in Crafter has three prerequisites: the character near crafting table, the character near a furnace, the character has at least one wood, one coal, and one iron in the inventory. Of the hard achievements, to unlock as not only does it depends on the make iron sanpppicaax but also that the diamond resource extremely scarce in the game. The complete achievement list can be found in Sec. B.
Figure 5: TreeMaze.
pollect-diaamee
is objectively the hardest achievement
5.2 ACHIEVEMENT LEARNING
Latent
SEA -det
SEA
We first investigate the clustering accuracy of our algo- rithm. As an evaluation metric, we calculate both cluster purity, which is defined as the proportion of the major- ity achievement in each cluster, and achievement purity, which is defined as the proportion of the majority cluster that the achievement is clustered into. The final clustering accuracy defined as the mean purity across all clusters and achievements.
Crafter-Limited Crufter
0.755
1.000
N/A
0.966
1.000
TreeMaze-Easy
0.735
1.000
TreeMaze-Normal
N/A
0.994
TreeMaze Hand
N/A
Table 1: Clustering accuracies.
Baseline and result. We design a latent space-based baseline for achievement learning. Specif- ically, we train a neural network to predict the environmental reward and use the latent variable of the network as the achievement representation. The idea behind this baseline is that to predict a certain achievement being completed, only the necessary information in the observation will be preserved in the predictor network. To test the effectiveness of our determinant-be we add an ablation experiment that replaces the determinant in Eqn. [ with mean pairwise distances. The clustering accuracy be found in Tab. [ The latent-space baseline only manages provide meaningful clustering in two of the easiest environments, while our algorithm does almost perfect clustering in all tested environments. The mean distance variant shows slightly worse clustering
loss function,

---

Published as a conference paper at ICLR 2023
1 collect wood
Recovered
Ground Truth
2 place_table tatble
3 make_ wood _pcok__e
4 makk weo____w__odrdddddd sword
5
5 wake__p
6 collect_ston stooe
7 collect_coo coal
8 place_stone sesooe 9 eat cow
10 faaceffunace
15
make_stone, stone_pickaxe
make__tooo Baaaa__sttee__eeee sword
16
10
16
defeat_ skeleton collect iron collect_sappaaeee sapliin
12
14
17
14
17
place_plant
collect_drink
Figure 6: Recovered dependency graph comparison. Dashed lines represent differences. performance than SEA in the Crafter environment but completely fails in the TreeMaze-Hard envi- ronment, which has the largest amount of achievements.
We note here that even though the determinant loss massively outperforms the latent-space baseline in our tested environments, it has the advantage of not being dependent on the achievement reward assumption. In our preliminary testing, find out that the latent-space baseline separates different sources of reward better in some environments where the achievement reward assumption does not hold.
Sample efficient. We further investigate the sample efficiency of algorithm. We three experiments with million, 200 thousand, and 50 thousand environment steps of data, respectively. The clustering accuracy in Crafter is shown in Fig. 3 Numerically, 1 million steps of data sufficient as reaches > 99% accuracy in all clusters and achievements, while only using 200 thousand steps also reaches 90% accuracy in 16 chusters/achieveeentt out of all 17 ones.
5.3 STRUCTURE RECOVERY
In all three TreeMaze environments and Crafter-Lmmteed our algorithm successfully recovers the exact dependency graphs. In full Crafter, the graph Hamming distance (defined as the number of different entries in the adjacency matrix) between recovered graph and the ground truth graph is 11 out of 272 entries. The detailed graph comparison can found in Fig. 6
5.4 SUB-POLICY LEARNING AND EXPLORATION
180%
randon
untock rate
75%
graph
Meta-controller comparison. We first show the effec- tiveness of the dependency graph-based meta-controller in training the sub-policies. The mean easy achievement set unlocking rate compared to random controller is shown in Fig. 7 As shown in the figure, graph-based meta-controller learns the sub-policies much faster than random controller.
58%
25%
8%
100900
200000 308008 408000 episode
Figure 7: Comparison of mean achieve- ment unlocking rate with a graph-based meta-controller and a random one.
Sub-policy learning and exploration. For this part, choose IMPALA (Espeholt et al. 2018)) and PPO (Schul-) man et al.] (217)) as widely-recognized model-free base-
lines, IMPALA + RND (Burda et al., 2019b) an exploration baseline, Dreamer V2 (Hafner et al.) 2021 as the model-basee baseline since achieves the highest reward in the original Crafter pa-
per (Hafner 2021), and HAI (Costales et al. (002) as Hierarchical reinforcement learning base- line.
Note that HAT. has advantage over the other selected algorithms since it requires the environment to provide extra information of the achievements, such achievements completion and affordance signals.
8

---

Published as a conference paper at ICLR 2023
To evaluate SEA's ability to master existing tasks and explore tasks separately. compare the mean achievement unlock rate in the easy achievement set and the hard achievement set re- spectively, as shown in Fig. 4 From Fig. 4al we notice that SEA learns slightly slower than vanilla IMPALA in the easy set. This is because SEA is not designed to maximize the total reward but to master each achievement-targeter sub-policy, as meta-controller does not try learn opti- mal achievement completion route. From Fig. Mai we can see that SEA successfully discovers the hard achievements with significant reaching rate while vanilla IMPALA fails to reach any of them, which shows the exploration potential of our algorithm. The complete unlocking rate curve can be found in Fig. 8 in the Appendix.
A detailed numerical comparison with all baselines is shown in Table 2 and We observe that SEA is the only algorithm that can consistently reach the hard set achievements and the same time maintains hardest achievement in Crafter, col lect_di amond, with a non-negligible probability.
easy set achievements reaching rate. SEA is also able to reach the
Table 2: Achievement unlock rate comparison. Standard deviation shown in the parenthesis.
Easy Set
Hard Set
mean
median
mcan
median
collect .di amand
IMPAL.
% (0.1)%)
99.25 % (0.35%)
0.00% (0.00%)
0.00% (0.00%)
0.00% (0.00%)
RND
93.24% (1.08%)
98.58% (0.59%)
0.15% (0.21%) 21)
0.13% (0.18%)
0.00% (0.00%)
PPO
34.86% (2.19%%
21.13% (5.48%)
0.00% (0.00%)
0.00% (0.00%)
0.00% (0.00%)
D2eamerV2
76.21% (11.19%)
92.00% (1.41%)
0.00% (0.00%)
0.00% (0.00%)
0.00% (0.00%)
HAI.
15.76% (0.75%)
0.60% (0.57%)
0.00% (0.00%)
0.00% (0.00%)
0.00% (0.00%)
SEA
92.53% (0.54%)
96.84% (0.58%)
49.30% (2.85%)
60.70% (1.67%)
4.21 % (3.24%)
Table 3: Crafter score
Standard deviation shown in the parenthesis.
IMPALA
RND
PPO
D2eamerV2
HAL
SEA
38.54 (0.04) 39.21 (0.91)
6.31 (1.02)
24.79 (9.78) 2.41 (0.18)
75.52 (2.36)
Sample efficiency. For SEA, we use 200 million environment steps to train the original IMPALA policy for the initial data collecting and 300 million steps for the sub-policy learning and exploration. For both vanilla IMPALA and IMPALA RND, we train the agent for 1 billion steps. For PPO, only manage to run the agent for 110 million steps due to the time limit. For DreamerV2, we run the agent for 2.5 million steps. For HAL, we run the agent for 140 million steps. We also note that for PPO, D2eamerV2, and HAL, even though the environment steps do not match SEA, their training wall clock times are all longer than the 1 billion step IMPALA experiment and we don't observe significant improvement for at least the last 1/3 of the training. We refer the reader to Fig. g in the Appendix.
CONCLUSION AND DISCUSSION
Exploration in procedurally generated environments is particularly hard since state frequency-based exploration methods are often not effective in such domains. We set our sights on achievement- based environments and propose Structured Exploration with Achievements (SEA), a multi-stage algorithm specialized in exploring in such domains. Empirically, SEA successfully recovers the un- derlying structure of Crafter, a procedurally generated achievement- based environment, and uses the recovered structure to complete the hard exploration tasks in Crafter. We notice that achievement- based environments are not common in the reinforcement learning community. However, since schievement-basee environments are easy to design and can help to learn hard exploration tasks even without a particularly good choice of achievement set, we call on the community to consider this design choice more often when developing new environments.
*The unlock rate refers to the frequency unlocking certain achievement. 'ee follow the definition from Hafner (2021) h S == exp( N Dn In(1 + +))) 1, where 8; E [0, 100) is the percentage unlock rate for each achievement.

---

Published as a conference paper at ICLR 2023
REFERENCES
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. AAAI, 2017.
Adriä Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andew Bolt, and Charles Blundell. Never give up: Learning directed exploration strategies. ICLR, 2020.
Mare G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Rémi Munos. Unifying count-based exploration and intrinsic motivation. In NIPS, 2016.
Yuri Burda, Harrison Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A. Efros. Large-scale study of curiosity-driven learning. ArXiv, 05//1808.04355 2019a.
Yuri Burda, Harrison Edwards, Amos J. Storkey, and Oleg Klimov. Exploration by random network distillation. ICLR, 2019b.
Alberto Camacho, Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Anthony Valenzano, and Sheila A. Mcllraith. Ltl and beyond: Formal languages for reward function specification in rein- forcement learning. In IJCAI, 2019.
Maxime Chevalier-Boisvert Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https: / /ttp://gtttbb/.// wwtp///www//////c/t///oo cateee///////////ggee/gggeemme minigrid 2018.
Robby Costales, Shariq lqbal, and Fei Sha. Possibility before utility: Learning and using hierarchical affordances. ICLR, 2022.
Peter Dayan and Geoffrey E. Hinton. Feudal reinforcement learning. In NIPS, 1992.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. First return then explore. Nature, 590 7847:580-586, 2021.
Lasse Espeholt, Hubert Soyer, Rémi Munos, Karen Simonyan, Volodymyr Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. ICMI,, 2018.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. ArXiv, abs/1 2019.
David R Ha and Jürgen Schmidhuber. World models. ArXiv,
2018.
Danijar Hafner. Benchmarking the spectrum of agent capabilities. arXiv preprint 2rX0v:2109.067800 2021.
Danijar Hafner, Timothy P. Lillicrap, Mohammad Norouzi, and Jimmy Ba. Mastering atari with discrete world models. ICLR, 2021.
Kristian Hartikainen, Xinyang Geng, Tuomas Haarnoja, and Sergey Levine. Dynamical distance learning for semi-supervised and unsupervised skill discovery. ICLR, 2020.
Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Anthony Valenzano, and Sheila A. Mcllraith. Teach- agent using Itl. In AAMAS, 2018a.
ing multiple tasks
Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Anthony Valenzano, and Sheila Mcllraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In ICMI,, 2018b.
Rodrigo Toro Icarte, Ethan Waldie, Toryn Q Klassen, Richard Anthony Valenzano, Margarita P. Castro, and Sheila A. McIlraith. Learning reward machines for partially observable reinforcement learning. In NeurlPS, 2019.
Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Anthony Valenzano, and Sheila A. McIlraith. Re- ward machines: Exploiting reward function structure in reinforcement learning. J. Artif. Intell. Res., 73:173-208, 2022.
10

---

Published as a conference paper at ICLR 2023
Maximilian Karl, Maximilian Sölch, Justin Bayer, and Patrick van der Smagt. Deep variational bayes filters: Unsupervised learning of state space models from raw data. ArXiv, abs/ 06442, 2017.
Alex Kulesza. Determinantal point processes for machine learning. Foundations and Trends@ in Machine Learning, 122-3):22--266 2012. doi: 10.1561/2200000444 htttps///d/oi.
Tejas D. Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Joshua Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In NIPS, 2016.
Daoming Lyu, Fangkai Yang, Bo Liu, and Steven M. Gustafson. Sdrl: Interpretable and data- efficient deep reinforcement learning leveraging symbolic planning. In AAAI, 2019.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hicrarchical reinforcement learning. In NeurIPS, 2018.
Ofir Nachum, Shixiang Shane Gu, Honglak I Lee, and Sergey Levine. Near-optimal representation learning for bierarchical reinforcement learning. ICI.R, 2019.
Jack Parker-Holder Aldo Pacchiano, Krzysztof Choromanski, and Stephen Roberts. Effective diversity in population- based reinforcement learning. ArXiv, abs/2002.00632,, 2020.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. 2017 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 188-489, 2017.
Jacob Rafati and David C. Noelle, Learning representations in model-free hierarchical reinforcement learning. AAAI, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv, 0ans/107..6633 2017.
Sungryull Sohn, Hyunjae Woo, Jongwook Choi, and Honglak Lee. Meta reinforcement learning with autonomous inference of subtask dependencies. ICLR, 2020.
Bradly C. Stadie, Sergey Levine, and P. Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. ArXiv, 0bs/1507.nn 1107000844, 14, 2015.
Richard S. Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction reinforcement learning. Artif. Intell., 1 1211111 1999.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Abbeel. #exploration: A study of count-based exploration for deep rein- forcement learning. NIPS, 2017.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Manfred Otto Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. ICML, 2017.
Manuel Watter, Jost Tobias Springenberg. Joschka Boedecker, and Martin A. Riedmiller. Embed to control: A locally linear latent dynamics model for control from raw images. NIPS, 2015.
Lunjun Zhang, Ge Yang, and Bradly C. Stadie. World model as a graph: Learning latent landmarks for planning. In ICML, 2021.
11

---

Published as a conference paper at ICLR 2023
A
ADDITIONAL EXPERIMENT RESULTS
A.1
CRAFTER INDIVIDUAL ACHIEVEMENT LEARNING CURVE
collect
collect
collect
collect
50
untock unTock
collect_sapling
collect stone
collect wood
defeat skeleton
defeat zonble
eat caw
make iron pickaxe
make iron sward
100
unTock
make__ Bakk__stoe__re
make_stone see__stoe__sve__ _word
make wood_pickaxe
nake_ wood wood_sword sword
100
50
untock
place_ furnace
place_ptie_ plant
place_store stone
place_tabb table
180
50
unco
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
episode
episode
episade
wakee_up up
180
unlock rate
SEA
IMPALA
50
IMPALA+RND
PPO
HAL
0.0
0.5
1.0
1.5
episode
1e6
Figure 8: Achievement unlock rate curve for each individual task in Crafter, excluding Dreamer V2.
12

---

Published as a conference paper at ICLR 2023
collect_oo _oaa
collect diamond
collect drink
collect_ iron
un rate *
100
50
collect collect_sapling
collect stone
collect wood
defeat_skeletue skeleton
un rate *
100
50
0-
defeat_
eat ltcpirroonnnaapp_e
make iron
nake i sword
unlock rate *
100
50
make__ sttone_pickane
make sttteestteee__e stone_sword
make wood pickaxe
make wood sword
unLock rate *
100
50
0
Llace_furnae
place_ple _alatt
place stone
place_table
100
unkock rate
2000 4990 6999 episode
2009 4600 ep sode
2008 4808 6998 seee episode
wake up
untock rate %
100
50
DreanerV2
0
2800
4869 epis
6800
8669
Figure Achievement unlock rate curve for each individual task in Crafter, DreamerV2.
B ENVIRONMENT DETAILS
B. COMPLETE CRAFTER ACHIEVEMENT LIST
di dimondd. The complete list of Crafter achievements are [collect.coal, collect.stone, collect.drink, collect.wood. defeat.skeleton. defeat.zombie, eat_cow, make.iron.pickax.. make iron sword, make stone pickaxe, make stone sword, make wood pickaxe, make wood sword, place furnace, place plant, place stone, place table.
collect.iron,
collect.sapling,
13

---

Published as a conference paper at ICLR 2023
wake.up). Of those the 17 achievements fcollect.coal, collect.drink, collect.iron, collect.sapling defeat skeleton, eat cow, eat plant, make stone pickaxe, make stone sword, make wood pickaxe, make wood sword, place furnace, place plant, place_stone, place_table, wake_up) the easy set since they solvable by the vanilla IMPALA agent. The remaining tasks (collect.diamone de defeat.zombie, make.iron.pickarx make like_irro_sworrg are the hard set.
collect.stone,
collect.wood,
B.2 MODIFICATIONS TO THE ORIGINAL CRAFTER ENVIRONMENT
We make some modifications to the original Crafter environment to make it better suits our setting. The complete change list is:
The health reward is removed since it does into our achievement reward assumption. Consequently, the character won't lose health point in any way.
The game ends if no achievement has been unlocked in the last 100 steps.
When creature (including cow, a zombie and a skeleton) gets attacked by the char- acter, it will not lose health point unless the attacking point of the character is greater than or equal to the health point of that creature. With this modification, the eat cow, de seffetsske leton defeett.. feafttembbiiie achievements can be connected to the main dependency graph instead of being independent nodes.
C REPRODUCEBILITY
C.I ADDITIONAL. ALGORITHM DETAILS
C.I.1 META-CONTROOLER DETAILS
Let the dependency graph be G. The meta-controller maintains of the completed achievements that are initialized to 0. At the beginning of an episode and whenever an achievement has been unlocked, the meta-controller (re)generates
target achievement.
To generate a new target achievement, if it is the beginning of an episode, the meta-controller ran- domly selects an achievement with dependencies according the dependency graph; Otherwise, suppose the just completed achievement is Let V = {r & S E S, Vu + E G} be the available achievements set. Let CONT( u) (r EVE u + e G} be the subset of V that are direct descendants of u. Let NGHB = {u V Ew V.t. v + w E G} be the subset that are neighbours u (i.e. on which one or more w's direct descendants are depended). Let JUM (v E V & CONT(u) A & NGHB be the remaining achievements. Notice these three subsets partitions V. The mota-controller stochastically chooses the target achievement according to the following probabilities:
With probability 40%, the meta-controller chooses the exploration task;
With probability 48%, the meta-controller uniformly randomly chooses an achievement from CONT(u);
With probability 6%, the meta-controller uniformly randomly chooses an achievement from NGHB(u);
With probability 6%, the meta-controller uniformly randomly chooses an achievement from JUMP(u).
After selecting the next target, the meta-controller updates the completed achievements set + S U (u).
14

---

Published as a conference paper at ICLR 2023
C.2 IMPLEMENTATION
Our code is adapted from an open-source implementation of IMPALA, torchbeas 6 The complete code be found here
C.3 HYPERPARAMETERS
Table 4: IMPALA hyperparameters for different experiments.
Hyperparameters
Crafter
TreeMaze
Network structure
CNN+LSTM
CNN+LSTM
Hidden size
256
256
Initial learning rate
0.0002
0.0002
Batch size
32
32
Unroll length
80
80
Gradient clipping
40
40
RMSProp
0.99
0.99
RMSProp momentem
0
0
RMSProp
0.01
0.01
Discountt rate (7)
0.99
0.99
Normalize reward
Yes
Yes
C.4 IMPLEMENTATION OF ACHIEVEMENT REPRESENTATION FUNCTION Ø
á uses the two networks to encode the states, one for the current state one for the next state $t+1- The network structure is the same as the policy network. The encoding of the two states are con- catenated into the observation vector Tobs. Jobs is then concatenated with the one-hot representation of the current action a₃ The concatenated vector is then fed into cully-connected layer, resulting in Trep- The final output of Φ is Tohs Trep.
D ADDITIONAL DISCUSSIONS
D.1 COMPARISON WITH HRL
Despite sharing similar concepts (achievements and subgoals/subtasks) with HRL, our work has a different focus. Subgoals and subtasks in HRL normally refer to the intermediate steps that lead to an ultimate goal/task. Achievements are all equal in nature, although some achievements can be the subgoals to other achievements. Our algorithm can be useful (potentially as subgoals) to other achievements. This lowers the standard for the achievement design as there no need to carefully craft series of intermediate steps that help the agent to learn. Our achievement setting also allows for multiple ultimate tasks that our algorithm can solve for in one go.
automatically determine which achievements
"http://gitub..cm/fuuchhh http://hhh..m///cccccccc//////ee hhans://ggtthaaccm///oooorrdd/d/
15


Reviews:
[{"review_id": "qu2jeWgP6q", "reviewer": "Reviewer_uoYd", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 an structured exploration approach by learning the structure of the achievement task in procedural generated environments and using that structure to explicitly control for which achievement to pursue and learning an achievement conditional policies. The paper shows promising results in Crafter and TreeMaze.\n", "summary_of_the_review": "This paper provides a meaningful contribution to the exploration community it provides interesting results in procedurally generated environments. The paper could benefit from further clarification on the above points.\n", "strength_and_weaknesses": "Strengths: \nThis paper introduces to the best of my knowledge a structured exploration strategy based on hard clustering of achievements and uses its learned graph representation to make meaningful exploration. The idea is novel and relevant to the exploration community.\nWeaknesses:\nThe main weakness of this paper is reproducibility since little information is provided regarding the meta controller policies learned (what model is used/architecture choices/ how it was trained/etc).The authors claim the meta controller is biased towards continuing achievements but how exactly is this biasing being done?\nHow are the nodes related to the clusters 1-1? how are the edges being estimated are they weighted?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "pWM7C1Emm9", "reviewer": "Reviewer_kuVW", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 paper looks at a specific class of RL problems where the reward structure of the underlying MDP can be specified in terms of achievements. The paper proposes a multi-stage method that tries to uncover the structure of the problem, by learning an achievement dependency class, which is then used to learn a meta-controller that can be used to explore the various achievements (by leveraging the dependency relationships between the achievements). The authors also argue for the fact that these structures once learned could be used across various instances that share the same achievement structures.\n", "summary_of_the_review": "Even with all the reservations I mentioned above, in general I am leaning towards accepting the paper. However, I would definitely urge the authors to see if they could include additional experiments that compare against baselines that can actually leverage the traces in some meaningful way (using an IRL-based method for reward shaping signal could be one such way). \n", "strength_and_weaknesses": "I mostly want to highlight two aspects, how easy it is to receive the assumed trajectories and whether the work is making more assumptions about the achievements than what is listed. \n\nTrajectories: So one of the underlying assumptions of the method is access to trajectories that reflect the underlying achievement structure. The effectiveness of the method relies on how well these trajectories capture the underlying structure. The work mostly mentions that these trajectories could come from experts or other previously trained agents. However, this is built on the assumption that there exists a small/easy enough instance which shares the same structure, but where the exploration can be performed effectively (or where the expert can give the traces). This need not be true and the simplest problem instance may still be too hard to effectively specify all the trajectories. One possibility the authors might want to consider is, how easy would be for domain experts to directly specify, at least an incomplete version of the achievement dependency graph. This is a common practice in many fields like causal inference and learning. Also if a set of trajectories is available, a possibility that should have been considered was whether you could have used an inverse reinforcement learning algorithm to learn a potentially informative reward function. Provided these reward functions are represented in parametric form, it should be possible to apply them within other instances at least as a way to provide shaping information.\n\nAssumptions about achievement structures: The heuristic algorithm seems to imply that the algorithm would only consider an ordering to be valid if it holds in every trajectory. While this is a reasonable starting point, this would overlook cases when there are disjunctive relationships between parents and children. A common case could be one when a specific fact could be achieved in a different way (For example, you can enter a room by either unlocking the door or by breaking down the door). Similarly the current method also seems to make the assumption that all transitions that correspond to a specific achievement would be equivalent in how good they are with respect to the ease with which future achievements can be reached from the resulting state. This is a common assumption shared by a lot of works that tries to break down the problem into subgoals and then solve subgoals independently. You can look at [1] to see an example of a recent work that tries to address this issue.\n\n[1] Guan, Lin, Sarath Sreedharan, and Subbarao Kambhampati. \"Leveraging Approximate Symbolic Models for Reinforcement Learning via Skill Diversity.\" ICML (2022).\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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "n4vq68Gmac", "reviewer": "Reviewer_Jys6", "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 method for learning the “achievement” (i.e. subtask) structure of an environment from offline data, with sparse rewards indicating when achievements are attained. First, an achievement representation is learned using a contrastive-learning type procedure over the transitions where achievements were attained in the offline data. Next, using an achievement classifier constructed from the learned representation, a dependency structure of achievements is built, represented as a DAG. This dependency structure is used to inform more effective exploration over achievements, as opposed to the default random exploration of the meta-controller. The authors demonstrate the efficacy of their approach on tasks within two achievement-oriented environments, relative to baselines that do not take advantage of the achievement structure.", "summary_of_the_review": "The work is well-motivated and generally clearly written, but is missing key details, citations and corresponding discussion, and comparisons/ablations in the evaluation.", "strength_and_weaknesses": "Strengths: \n\n* The motivation is good, and the method is very intuitive given the problem statement. \n\n* The paper is generally well-written and the method is clearly explained. \n\n* The chosen evaluation environments are appropriate given the motivation, and the method appears to significantly outperform the baselines, especially on the more challenging (longer-horizon) tasks. \n\nWeaknesses/questions:\n\n* A number of crucial details are missing (and are not to be found even in the Appendix). For example, the authors state they “use a controller that topologically traverses the dependency graph. Specifically, at the beginning of the episode or upon completion of any achievement, the controller randomly selects a unfinished achievement whose dependent achievements have all been completed. In our implementation, we also bias the selection probability towards a direct child of the last completed achievement to provide continuity.” How is this bias implemented/parameterized? Another example is that $\\phi$ does not appear to be discussed in detail; i.e. how it is implemented/parameterized. \n\n  * Apart from knowing these kinds of implementation details, it would also be useful to see how robust the method is to them in the evaluation section (e.g. varying the hyperparameter controlling how the selection probability is biased). \n\n* There are a number of crucial missing related works that should be at the very least be discussed, and potentially included in the evaluation section: \n\n  * [1] This is a highly relevant work with a very similar setting, motivation, and evaluation environments. They use environment “milestone signals” (similar to sparse rewards in this work) to learn an an “affordance classifier” (like the achievement classifier in this work) to improve exploration at the meta-controller level. Even a similar contrastively-learned representation is used, which they dub an “achievement context” (like the achievement representation in this work). Given the striking similarities, adequate discussion of [1] is crucial to understanding the contributions of the current work, and the comparative limitations/benefits.\n\n  * [2] This is just one example of another relevant work that similarly autonomously learns a subtask dependency structure from experience and utilizes it for better performance. The current work lacks comparison to these types of relevant works in the literature. How does the present approach compare to other works that have also thought about subtask dependency structures? What are the limitations/benefits of the present work in comparison?\n\n  * [3] This work is cited, but improperly so—-the authors in the same sentence mention that reward machines must be hand-specified, but this work learns them from experience. A clearer/more faithful explanation of the differences to the present work should be included. \n\n* The method diagram was more confusing than helpful to me; for example:\n\n  * “Filtered reward” is a phrase that appears nowhere in the text, but it seems to indicate that only achievement-specific rewards are used (as determined by the achievement classifier) to train each subpolicy. \n\n  * Why is the goal/achievement being passed to the achievement classifier in the diagram? My understanding is that the achievement classifier takes in a transition and outputs which achievements are afforded. \n\n  * Minor, but the term “goal” is used in the diagram, which is inconsistent with the terminology in the paper (should be “achievement”). \n\n* In the evaluation there are no comparisons to other HRL approaches, much less other approaches that take advantage of achievement/subtask structure (e.g. [1]). This makes the results less compelling. Without the proper comparisons, it is difficult to judge the contributions of the present work. For example, a simple baseline/ablation would be to perform the clustering to identify achievements, and then use the standard random exploration in the meta-controller, and compare this to the full approach which uses the inferred dependency graph to guide exploration. This would help disentangle the factors leading to performance gains on the evaluation environments. \n\n\n\n[1] Possibility Before Utility: Learning And Using Hierarchical Affordances (Costales et al., 2022)\n\n[2] Meta reinforcement learning with autonomous inference of subtask dependencies (Sohn et al., 2020) \n\n[3] Learning Reward Machines for Partially Observable Reinforcement Learning (Icarte et al., 2019)\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": "iBdWetvjAa-", "reviewer": "Reviewer_wFTY", "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 focuses on the exploration issue for a reinforcement learning (RL) agent in an environment with a long horizon and high-dimensional input, particularly the procedurally generated environment. To address the issue, this work proposes a structured exploration with achievements (SEA) method by discovering the finite and fixed underlying structure in the procedurally generated environment. Finally, experiments were conducted on Crafter and TreeMaze, with results demonstrating its effectiveness in terms of achievement learning, graph recovery, and sub-policy learning and exploration.", "summary_of_the_review": "According to my comments in both the main Weaknesses and the section of Clarity, Quality, Novelty, I feel this is a paper where reasons to reject outweigh reasons to accept. But I would like to change my score if there is a misunderstanding.", "strength_and_weaknesses": "Strengths:\n- Exploration in a complex environment with long horizon and high-dimensional input can be challenging for RL. This is an interesting work where it learns achievements representation in the procedurally generated environment, builds the achievement dependency graph based on clustered achievements, and learn sub-policies for each achievement with the meta-controller. It would be intriguing to the community of representation learning in RL.\n\n\n\nWeaknesses:\n- The presentation of the paper could be improved. For example, what are the differences between the procedurally generated environment and the partially observable environment? Or are they the same? What is an finite internal achievement system? Does this require the task to be well-defined? What's the difference between the setting of achievement-based environments and \"sparse and delayed reward signals\" setting in [1]? Is the achievements design equivalent to the subgoal/subtask design? What's the unlock rate? How does the learned representation & clustering performance affect the sub-policy learning? There lacks more details for this.\n- The literature review should include some of previous work regarding subgoal/subtask learning with Hierarchical RL, such as [1,2,3]. All the work of [1,2,3] divides a complex task into sub-tasks, but they did in different ways. There are some shared intuitions in common between this work and [1,2,3], such as task decomposition, goal-directed policy, meta-controller, etc. In particularly, [3] used unsupervised learning method for learning the representation and there needs a discussion on the differences.\n- Its current novelty is somewhat incremental to me. \n\n\nReferences:\n- [1] Kulkarni, T. D., Narasimhan, K., Saeedi, A., & Tenenbaum, J. (2016). Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. Advances in neural information processing systems, 29.\n- [2] Lyu, D., Yang, F., Liu, B., & Gustafson, S. (2019, July). SDRL: interpretable and data-efficient deep reinforcement learning leveraging symbolic planning. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, No. 01, pp. 2970-2977).\n- [3] Rafati, J., & Noelle, D. C. (2019, July). Learning representations in model-free hierarchical reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, No. 01, pp. 10009-10010).", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster