Learning About Progress From Experts
Authors: Jake Bruce
Ankit Anand
Bogdan Mazoure
Rob Fergus
Venue: ICLR 2023 notable top 25% (2023)
Keywords: learning from demonstrations
reinforcement learning
exploration
nethack

Abstract: Many important tasks involve some notion of long-term progress in multiple phases: e.g. to clean a shelf it must be cleared of items, cleaning products applied, and then the items placed back on the shelf. In this work, we explore the use of expert demonstrations in long-horizon tasks to learn a monotonically increasing function that summarizes progress. This function can then be used to aid agent exploration in environments with sparse rewards. As a case study we consider the NetHack environment, which requires long-term progress at a variety of scales and is far from being solved by existing approaches. In this environment, we demonstrate that by learning a model of long-term progress from expert data containing only observations, we can achieve efficient exploration in challenging sparse tasks, well beyond what is possible with current state-of-the-art approaches. We have made the curated gameplay dataset used in this work available at https://github.com/deepmind/nao_top10.

Published as a conference paper at ICLR 2023
LEARNING ABOUT PROGRESS FROM EXPERTS
Jake Bruce DeepMind
Ankit Anand DeepMind
Bogdan Mazoure" McGill University
Rob Fergus DeepMind
ABSTRACT
Many important tasks involve some notion of long-term progress in multiple phases: e.g- to clean a shelf it must be cleared items, cleaning products applied, and then the items placed back the shelf. In this work, explore the use of expert demonstrations in long-horizon tasks to learn a monotonically increasing function that summarizes progress. This function can then be used to aid agent exploration in environments with sparse rewards. As a case study we consider the NetHack environment, which requires long-term progress
variety of scales and far from being solved by existing approaches. In this environment, we demonstrate that by learning model of long-term progress from expert data containing only observations, we can achieve efficient exploration in challenging sparse tasks, well beyond what is possible with current state-of-the-ae approaches. We have made the curated gameplay dataset used in this work available at attttps: htttps://githbb.. comp deepmind/ nao topl0
INTRODUCTION
Complex real-world tasks often involve long time dependencies, and require decision making across multiple phases of progress. This class of problems can be challenging to solve due to the fact that the effects of multiple decisions are intertwined together across timesteps. Moreover, the sparsity of the learning signal in many tasks can result in challenging exploration problem. which motivates the use of intrinsic sources of feedback, c.g. curiosity (Pathak al. 2017 Raileanu & Rocktäschel (020). information-gatheen
(Kim et al. 2018 Ecoffet et al.] 2019) Guo et al. 2022). diversity- seeking (Hong
al. 2018 Seo et al. [021] Yarats
2021) and many others.
The internal structure of some environments implicitly advantages certain types of intrinsic motivation. For example, Go-Explore (Ecoffet et al. 2019) excels on Montezuma's Revenge by enforcing spatio-temporally consistent exploration, while ProtoRI. (Yarats et al.) (20TT) achieves high returns in continuous control domains. Nevertheless, some challenging tasks that do not have this structure remain unsolved due to complex dynamics and large action spaces. For instance, in this work we study the game of NetHack (Küttler et al., 2020), which manifests a mixture of long task horizon, sparse or uninformative learning signal and complex dynamics, making it an ideal testbed for building agents. The complexity of NetHack prevents agents from efficiently exploring the action space, and even computing meaningful curiosity objectives can be challenging.
Instead of training agents on NetHack tabula rasa, a challenging prospect for efficient exploration, we take inspiration from recent advances in another hard exploration benchmark, Minecraft (Baker et al. 2022 Fan et al. 2022). and leverage plentiful offline human demonstration data available in the wild. Equipping learning agents with human priors has successfully been done in the context of deep reinforcement
learning Siiverr et al. 2016 Cruz Jr et al. 2017 Abramson et al. 2021 Shah et al. 2021 Baker et al.
2022 Fan al. 2022) and robotic manipulation Mandlekar et 2021).
One of the salient features of domains such as NetHack (Küitler et al. 2020) is the lack of an explicit signal for monotonic progress. The objective of the game is to descend through the dungeon obtaining equipment, finding food & gold, battling monsters and collecting several critical items along the way, before returning to the beginning of the game with one particular item. A full game can take even experienced players upward of 24 hours of real time and more than 30k actions, and the game can be punishingly difficuult for all but the best players. In addition, the in-game score is not a meaningful measure of progress, and maximizing it does not lead agents toward completing the game (Küttler et al. 2020). Correspondingly. agents trained via reinforcement learning methods fail to make significant long-tern progress (Hambro et al. 2022a).
This work was done while the author was doing intemship DeepMind. Author is now at Apple.

---

Published as a conference paper at ICLR 2023
Cumulaativ Progress over an Spicode
Progress
400
Selected Frames
300
Cumuutive
100
Timestop
Selii
19315111 Inst 2013 xput// 1213
inteedy
pau eent man1 19s1 71)
NNLL the sellast
06-13 -33 bui 0u-20 Ja.3 Mi:a0 di:23 Landal
Aaea de ualles
30:13 8x.10 du130 axc wasld chil0 Lenful 9:46
Figure 1: In this work, we learn model of task progress from expert demonstrations and it an exploration reward. This figure shows an example cumulative progress curve over the first 300 steps of representative episode, alongside three frames taken over the course of the sequence. In the course of a typical episode, the player will explore a procedurally-genee
dungeon, interact with objects open locked and unlocked doors search for the stairs to the next level and more.
Many tasks of interest combine long horizons, complex temporal dependencies and sparse feedback, but demonstrations with actions are often difficult to obtain: we focus on these settings where abundant unlabeled data is available in the wild. To address these problems we propose Explore Like Experts (ELE), a simple way to use progress estimates from expert demonstrations as an exploration reward. We estimate progress by training model to predict the temporal distance between any two observations; the model is pre- trained on offline human demonstrations and does not require actions. Maximizing an exploration objective based on this progress model leads to new state-of sfate-of-the-art the-art performance complex NetHack tasks known for their difficulty, including four tasks on which other competing methods achieve no reward at all. While we focus NetHack in this work, the method is not specific to that domain, and can in principle be applied to any challenging exploration task with demonstration data that incorporates a notion of long-term progress.
2 RELATED WORKS
Intrinsic motivation: In complex domains with sparse extrinsic feedback, agents may resort to intrinsic motivation. Existing intrinsic motivation objectives can be informally categorized into curiosity- driven (Pathak et al. 2017 Zhang et al. 22000) Raileanu & Rocktäschel 2020). information-gatthring (Kim)
2021 Guo al. (002)), diversity-secking (Bellemare al. Seo et al. 2021: Yarats et al. 2021). These works propose various intrinsic motivation objectives which result more efficient exploration than using random actions. A simple yet effective approach is Random Network Distillation (RND) (Burda et al., (019) where the the predictions of frozen network are used as distillation target for an online network, and the prediction error acts as an exploration reward. One significant drawback of intrinsic motivation methods is that they may need to cover large regions of sub-optimal state-action space before encountering extrinsic feedback. To mitigate this, approaches like Go-Explore (Ecoffet et al. 2019) reset to promising states and resume exploration from there, but this requires that the environment can be reset to desired states, or that arbitrary states can be reached via behavior (Ecoffet al. 2021). Unfortunately, the ability to instantiate arbitrary states in the environment is not feasible in many domains interest including Nethack, and particular configurations of the environment not always reachable from all states.
al. 2018 [coffet al.
2019] Seurin et al.
2016 Hong et al. 2018
2

---

Published as a conference paper at ICLR 2023
Learning from human demonstrations: Equipping learning agents with priors derived from human demonstrations has long been an important direction of research. Behavior cloning has proven effective in
complex tasks, for example, in the case of Minecraft (Shah et al. 2021 Baker et al. 2022 Fan et al. (022)... Video Pretraining (VPT, Baker et al. 2022) first trains an inverse dynamics model on a small dataset anno- tated by humans, and uses to infer the actions in large-scale unlabeled dataset. While drastically improv- ing performance of RL agents on Minecraft, VPT does require an external source of supervision to provide labels. By contrast, incremental approaches first involve reward-free or action-free pre-training phase, which can be used to gather missing actions or rewards, and then used to label the offline dataset or fine-tune the representations found during the first phase (Torabi et al. 2018a Yu et al. 202T] Seo et al.. 2022).
Another leading approach to learn from demonstrations is Generative Adversarial Imitation Learning (GAIL)) (Ho & Ermon 2016) where discriminator model learns to distinguish expert and agent behavior, and the RI. agent is incentivized to make its own distribution indistinguishable from the expert's. This was further extended to GAIfO [Torabi et al. 2018b) which learns to distinguish two consecutive observations instead of state-action distributions, for cases in which actions are not available. Similarly, BCO (Torabi ct al. 2018a) extends behavior cloning to the action-fire case, by learning an inverse model for action labeling from the agent's online data. ILPO (Edwards et al., 2019) extends BCO by factoring the action labeling problem into forward modelling conditioned on a latent action followed by remapping to the primitive action space. The learning process for ILPO involves making a prediction for each possible latent action in order to take the maximum likelihood prediction for estimating latent action labels, which can be computationally expensive for large state and action spaces, and is challenging when environment dynamics are stochastic. FORM (Jaegle et al. (021) is another recently proposed approach that learns forward generative model of dynamics from demonstrations without actions and rewards the agent for producing transitions that are likely under the model. Other approaches like R2D3 (Gülgehre et al. (020) and DQND (Hester et al. 2018)) mix demonstrations and online data in the replay, but they require access to actions and rewards in the offline data, which is also the case in offline reinforcement learning (Fujimoto) (et al. 2019] Prudencio et al., 2022). As the demonstration data used in our experiments doesn't tt include any actions, we compare approach with GAIfO, BCO, and FORM in this work.
The game of NetHack (Küttler et al. 2020 is a complex pre-existing environment with a very sparse ultimate objective, large degrees of procedural generation and stochasticity, long-term dependencies, a strong notion of implicit monotonic progress, and a large state-action space. This makes tabula rasa learning on NetHack challenging. as recently emphasized by the results of the 2021 NetHack competition (Hambro et al., 2022a). Notably, symbolic and rule-based agents still outperform reinforcement learning methods on many metrics. In this work, we demonstrate that by leveraging openly available recorded gameplay from NetHack players in the wild (Hambro et al. 2022b), we can outperform state-of-the-art imitation and exploration approaches on a variety of hard NetHack tasks.
NetHack:
3
METHODOLOGY
Our method, which we refer to as Explore Like Experts (ELE), consists of two phases: i) learning a progress model offline, and ii) using the learned progress model as an auxiliary reward in reinforcement learning- The first phase of learning a progress model uses the expert data to learn a regressor which predicts a scalar progress reward given two observations from the same episode. The second phase simply uses the fixed weights of learned progress model to provide an auxiliary reward from the current observation and another past observation within this episode, and the underlying agent optimizes a weighted sum of the auxiliary and extrinsic reward while training.
Given a set of demonstrations D. the goal of the progress model to predict the temporal distance between two observations within the same demonstration. Formally, let (s",.") be observations at the ith and jith position in the demonstration trajectory Ta. We predict (4:0) denoting the temporal distance between si and sy in the trajectory. Expert demonstrations can have very long episodes, so we predict the distance between these observations in signed log-space, y = sgn(j j - model is trained by minimizing the mean squared error between the true value s// in transformed space and (( The resulting progress model (l:f) captures a monotonic increasing function of progress within the expert trajectories. In NetHack, this corresponds to behaviors such as increasing the character's 's level, revealing tiles in the dungeon, discovering new dungeon levels, finding gold, and improving the hero's armor See Fig. and Section 4.5 for visualizations of the progress model example trajectories.
The progress
3

---

Published as a conference paper at ICLR 2023
The second phase uses the learned progress model f(:0") with reinforcement learning algorithm A. In this phase, the extrinsic reward of the environment is augmented with the auxiliary reward from the progress model. To calculate the reward, we transform the progress estimates back to linear space: (s,,s,; sgn((f(( (( (ef(rr)y;)))) +1). While the auxiliary reward could be computed in many ways using the progress model, such as computing the temporal distance between the initial state and the current state, or computing the relative progress against the initial observation for consecutive states, we empirically observe that computing progress over small distances is significantly more effective (see (o44ion/A.4forr performance of the different variants). Hence in this work, we compute an auxiliary reward rg - - (,+-0000)))) to measure progress between the current state (s) and a state from A steps in the past ($:=a) where k is hyperparameter. The reward pottal is computed as weighted sum of auxiliary reward rf and extrinsic environment reward ry: total + (s
where w >0 is hyperparameter. See Algorithm
I for pseudocode description.
3.1 GRID WORLD EXAMPLE
To illustrate the progress model in simple case, we consider a tabular grid-world environment with a Markov decision process as follows: a 2D state space E [1,200] x [12200, where at each timestep the agent can move in any of the eight cardinal and diagonal directions. The agent begins the episode at 80 (0,,11) and receives a reward of 1000 when it reaches 8 = (200, and zero otherwise. The reward and termination conditions are designed to be similar to the NetHack tasks that investigate in Section In this toy example we employ a tabular Q-leariin approach, with the the vanilla RL agent only receiving extrinsic reward, while our ELE agent additionally receives exploration reward from the progress model. The progress model in this case is also tabular with an input space of 8; X 8.. It is trained estimate progress
set of demonstrations from a sub-optimal c-greedy oracle policy, where action is chosen uniformly at random with probability e= 0.975 and the optimal action is chosen with probability 1 --005005. In other words, the demonsstrtiin agent performs biased random walk toward the goal.
We demonstrate in Fig. 2 that the paths taken by the tabular Q-learnigg agent without an exploration reward do not approach the shortest path even after 20k episodes, whereas the same agent with the addition of the ELE objective achieves much more direct paths despite learning from highly sub-optimal demonstrations. As shown in Fig. 2 even trained only on extremely noisy demonstrations, the progress model forms smooth and consistent flow field toward the goal, due to the non-local nature of our approach. In contrast, most existing imitation learning approaches are purely local, and their models incorporate information only in the near vicinity of the current state. See Section A.8 for more details on the tabular case and a theoretical analysis in terms of stochastic processes.
In the rest of the paper, we take Het as the domain of interest. It is also grid-based, but is much more complex environment than the toy example, is a pre-existing domain that humans have found engaging to play for over 30 years, and is still far from solved by any existing approach (Küttlrr et al. 20000 Hambro et al. 2022a). The method is not specific to NetHack and applies in principle to other domains that admit notion of long-term progress, where demonstration data is available.
EXPERIMENTS
In this work, we consider NetHack as the primary environment for evaluating our proposed approach. ELE and all baselines are implemented as auxiliary rewards and/or losses on top of an underlying reinforcement learning agent. We use Muesli (Hessel et al. 1021a) as the agent, which a lightweight modification of MuZero (Schrittwieser et al.) 2020) that does not involve deep tree search. In these experiments we use a progress reward scale w = 0.01 and progress history length 8==8; see Section A. for more details about the implementation. All reported results aggregated over 5 seeds. The progress model takes the form of a neural network with the same structure as the feed-forward component of the underlying agent, but weights are not shared with the agent. See for implementation details about the architecture.
For all NetHack experiments, we remove the explicit timer from the observations, as it provides a shortcut to predicting timing differences that does not reflect the important elements of progress in the game (a common practice in exploration- focuseed work (Bellemare et al. (2016). See Section A.6 more informa- tion on timer sensitivity. All methods were implemented using the Jax ecosystem for scalable differentiable
4

---

Published as a conference paper at ICLR 2023
Tejector es
200
50
100
10
23
BLC
150
End
125 379
Toy grid environment: 200 200 grid with tabular Q-learning agent and ELE. The agent can move in 8 directions, starts at (1, 100) and receives a reward of 1000 when reaching (200, 100). See Section[[.33 for more details. Left: 10 example trajectories from each method: ELE discovers paths that reach the goal more directly than either pure RL with e-greedy random exploration or the demonstrations that it learned from. Right: Visualization of the ELE progress model f (*(s),))) for 8; = (100,100) against all possible successor states 8y. The model has learned that expert progress tends to be positive (bright) to the right of 8; and negative (dark) to the left.
Figure 2:
programming (Babuschkin et al. 2020 Hessel et al. 2021b Yang et al. 2021). We use demonstrations from the publically available expert trajectories recorded at http: http://nethace htw///tthhcc...ce alt. org
4.1 TASKS
We evaluate our approach on three standard tasks: Score, Scout, and Oracle (Küttler et al. 2020). as well as four new sparse tasks that represent important subtasks in the full NetHack game. Importantly, for all of these tasks we do not use the reduced action space presented in (Küttler et al. (020).. but instead use the entire unrestricted NetHack action space of 121 discrete actions, and we do not skip any messages or menu states. In addition, the hero role is chosen uniformly at random from the entire pool every episode, which a challenging setting even for humans, who often exhibit a preference for particular roles. These settings ensure that the tasks that we investigate represent the entire complexity of the early game. For every task, episodes are terminated after 1M environment steps or when the agent dies, except as described below. All agents are all trained for total of IB environment steps, the standard frame budget established in the literature (Küttler et al. 2020). To convey a sense of the relative time horizon of each task, we list the average episode lengths as achieved by our method in Table
In the Score task, the reward function is the difference in the in-game score from the previous timestep, as commonly done in game-based environments (Bellemare al. 2013).. This a relatively dense reward signal: score in NetHack is obtained for killing monsters, obtaining gold, identifying wands and potions, descending into deeper dungeon levels, reading novels, purchasing consultations from the oracle, and more.
In the Scout task, the agent is given reward of 1 for every tile revealed in the dungeon. This is the densest task that we consider in this work, and provides an explicit signal for learning spatial exploration behavior.
The objective of the Oracle task is to find the Oracle in the dungeon, which is a non-player character that is always located in a distinct location between 4 and 8 dungeon levels below the starting level. Once the agent moves to tile adjacent to the Oracle, it receives reward of 1000 and the episode is terminated. This a very sparse and fairly challenging task: in our human baselines, we find that intermediate human players are only able to reach the Oracle in approximately 48% of episodes.
addition to these standard tasks, we study four more tasks of increasing sparsity to provide a continuum of challenge between the Score and Oracle tasks. For the Depth 2 and Depth 4 tasks, the objective is to reach dungeon level or 4 levels below the surface. The initial level at depth 1, so these tasks require navigating I and 3 dungeon levels to find the stairs, respectively. As with Oracle, the agent is given reward of 1000 when reaching the target depth, and the episode is terminated. The Exp Level N tasks reward the agent for reaching target experience level. The hero begins the game level 1, so Exp Level 2 and Exp Level 4 require defeating enough monsters to gain and 3 levels, respectively. As with the previous sparse tasks, the agent receives reward of 1000 once the target experience level is reached, and the episode is terminated.
5

---

Published as a conference paper at ICLR 2023
In order to facilitate comparison between tasks, we normalize episode returns to lie approximately in the range [0.1]. In the sparse tasks, we simply scale the reward down from 1000 to 1. For Score and Scout, we divide all reported returns by the 80th percentile of the episode returns of all methods (1410 and 3425, respec- tively). Note that this is for reporting purposes only: the agents optimize the true underlying task objective.
Task
Length
II
Task
Length
Task
Length
[Std] Scout 596.2
Depth 2
76.1
Depth 4
1 183.7
[Std] Score 511.5
Exp Level 2
133.4
Exp Level 386.6
[Std] Oracle
547.2
Table 1:
Average episode length for each task as achieved by ELE; tasks marked with [Std] indicate standard tasks that were defined in (Küttler et al. 20220). Since the action space of NetHack consists of 121 different actions, sparse tasks with horizons as long as these are very challenging to solve without dedicated exploration strategy, and many are still challenging even with access to human demonstrations (see Section 4.4) Unlike real-time games with high frame rates, the turn- turn-based based nature of NetHack means that even relatively short episodes such as those in the Depth task can correspond multiple minutes of human gameplay. and the Oracle task can take intermediate human players more than 30 minutes of real time to complete (see Section A.3 for details).
4.2 DATASETS
We leverage the data recorded and made publically available by the owners of http 7 7/nethack. .alt org (Hambro al.) (0226) in order to provide demonstrations for learning to play NetHack. The data poses at least three distinct challenges: 1) the recordings do not include actions rewards, so straightforward behavior cloning GAIL cannot be applied: 2) users play with a wide variety of interface settings, including but not limited to character and color remapping, user interface element repositioning, and auto-pickup and other game settings (Hambro al., (022b): and 3) the gameplay varies widely in quality: many beginners use the server as their primary platform for playing the game, and the data also includes scripted bots that do not play at high levels competence or at all (e.g. behaviors such as aavesscumming (Hambro et al. (2022])). However, as the server is the most popular platform for playing the game, it also contains large amounts of highly skilful play. As the data was recorded over the last 14 years, the players were not aiming to solve the tasks we consider in this work; however, the tasks represent common milestones encountered in natural gameplay.
Our method addresses 1) and 2) by not relying actions sensitive discriminator to function. 3) remains an issue, since large proportions of deliberately bad gameplay are likely to impact any learning algorithm that attempts to leverage demonstrations to improve performance. To mitigate this, use data from only the top 10 users ranked by quantity called Z-score (nethackwiki.com) 2022) that rewards decreasing values for each win, which is calculated as Zuser = Exar Mat where Mote is the total number of games the user has won with that role. The Z-score metric has been designed by the community to incentivize winning the game with a wide selection of character roles, which aligns with our goal for a dataset to contain as much high-quality gameplay across the entire space of the game as possible.
To empower further research using high-quality NetHack demonstrations, we have released curated dataset of gameplay from the top 10 users in the form of easily accessible compressed data at httpps / //github. com. deepmi wemiiinn/eeee wwwpnn//nnnoooooo top10 In total, this amounts 16478 sessions of gameplay with a total of upproximately 184M transitions, and is approximately 12 GB in size. See Section AA.2 |A22for for more information on the datasets. The resulting dataset is much smaller than the entire dataset in its oriinaal form.
4.3 BASELINES
We compare our method against variety of popular baselines that are focused on exploration and learning from demonstrations without access to actions, as well as the underlying Muesli agent without any explicit exploration objectives. All baselines use the same curated demonstration set that use for ELE. We performed a hyperparameter search for each baseline; see Section A.I [ for implementation details and hyperparameter search results.

---

Published as a conference paper at ICLR 2023
FORM (Jaegle al. 2021): action-free imitation learning approach that leams passive dynamics model PD (s++1 (t)) from expert demonstrations, and uses the log- likelihood ratio of the expert dynamics model to an online estimator of its own transition dynamics log (st) logpr (s++1 1 (sx) as imitation reward.
BCO Torabi et al. 201 Say: an approach to behavior cloning without access to actions in which an inverse dynamics model p St,5t+1) is trained the agent's transitions, and used to label the action-free expert data to enable a behavior cloning objective. It should be noted that although the demonstrations are not recorded for tasks considered in this work, the BCO loss acts as a policy regularizer toward the types of behavior that are generally useful for the game. We also add the extrinsic reward as an objective to all baselines: the purpose of the imitation losses to encourage exploration.
GAIFO (Torabi et al. 2018b): an adversarial approach to action-free imitation learning in which a discriminator p (Expert(ss St,5t+1) is trained distinguish agent and expert transitions, and the probability of the agent's transitions being classified as expert behavior is used as an imitation reward.
RND (Burda et al. 2019): ; a demonstration- free exploration reward in which a randomly initialized feature encoder [nowen(s)) is used as target for distillation into an online trained encoder foaline (St), and the prediction error between the online and target encoders is used as an intrinsic reward.
4.4 RESULTS
Algorithm X
Algorithm
1.8
SUE 10urs
Muesi
GATO
RCD
0.1
BND
870
M01M
Mueci
101M
PAD
F09M
CAT)
2014
B1: (CW5)
Mues
Biz (005)
M&
DL [Cuns]
0.2
BL: (Durs
800
BL: (Durs)
0.4
0.5
0/8 00.
07.8
0.3
1.0
1960 Score
[560) Scout
Deort
Lxg Lovel
Depdy
Eea Lovel4 (314) Grasle
-00
Figure 3: Left: Median normalized episode return achieved by each approach after 1B frames of training, with error bars denoting the range from the 25th to 75th percentile over 5 sceds. Tasks marked as [Std] are existing tasks from the literature. The sparse task reward is scaled down by 1000 to lie in the range [0.1]: for Score and Scout normalize the return by the 80th percentile over all approaches (1410 and 3425, respectively) for ease of comparison. Right: Permutation test comparing all pairs of algorithms on randomly sampled runs, to quantify the probability that each algorithm outperforms the others on any given task (Agarwal et al. 2021). ELE outperforms all approaches with a wide margin, except FORM which outperform in 70% of samples.
We evaluate our approach on the tasks in Section 4.1 Fig. (left) shows the total episode return achieved by each approach on all of the tasks we investigate after training for IB steps, which is an established frame budget for NetH-ack (Küttler al. 2020). Figure (right) shows the permutation test comparing all pair of algorithms and statistically evaluating if one algorithm is better than other as proposed in Agarwal al, (202I). See Section A.5 for further comparison on aggregate metrics based on the mean, median. IQM and optimality gap.
The baseline approaches do well on the denser tasks, but struggle to discover the extrinsic reward on the sparse tasks. By contrast, ELE succeeds even on the very sparse tasks, and achieves similar results to the other approaches on the dense tasks. Note that the Oracle task is challenging even for human players: in our human baseline gameplay, intermediate human players achieve approximately 48% success on average. See Sections 4.2 and A.6 for more details about the demonstrations and further analysis.
4.5 ANALYSIS
In Fig. 4 we plot the (left) cumulative local progress and (right) instantancous progress with respect to the initial state, for 100 different episodes from a variety of different data sources. As expected, progress increases consistently for all datasets except for the uniform random policy. These plots demonstrate that
7

---

Published as a conference paper at ICLR 2023
agents are able to optimize progress more aggressively than either the source data human baseline recordings, which we also observe qualitatively in the relatively reckless behavior the agents agents-hurmans -hmmans tend to be much more careful and conservative. The high variance of the instantaneous progress plot shows the difficulty of estimating temporal differences for long timescales, and justifies the use of cumulative local progress exploration objective instead.
Cumulaaive Progress
500
Instantancous Progress Against Initial
NAO Top 10
Dracle Task
Oracle
1750
Scout Task
Task
400
Human Baseline: Oradle Task
ELE: Scout Task
1300
veeentareecc Progress
Rendom
1250
300
3000
200
100
250
0
Timistap
Trmestop
Figure 4: Example progress curves on the first steps of recorded episodes. Fach curve shows the median and middle 50% of the data over 100 episodes. Left) Cumulative progress: the sum of f (st-8,8t) over the episode. The agents pursue progress much more aggressively than either the NAO experts human baseline. Right) Instantaneous progress against the initial frame: f (Su,.)). Instantaneous progress estimates against the initial frame much noisier than the cumulative sum of local progress, in part because long-range progress estimates are much more difficult due to the many possible paths between distant states.
on-task
Fig. 5 shows the instantaneous progress estimates (s( for a single representative episode, with the peak of maximum progress indicated in red, alongside rendering of the two frames for the transition corresponding to this peak, and an example saliency map of the progress model on the bottom two statistics lines in the observation. Fig. [S (hottom) shows the sensitivity of the progress model features including character and dungeon level, score, gold, and armor class. In other words, ELE has learned that revealing tiles in the dungeon, increasing its ability scores, and descending deeper levels all reflect expert progress. Despite the procedural generation and stochasticity of the underlying environment, some aspects of the observations reliably indicate progress the game. These measures indicate that ELE's progress model captures many of these subtle indicators from even such a diverse set of demonstrations.
Instentaneou Progress over an Episoce
Progress
1000
200
600
409
209
Trnestep
Tariru the Conjurer
St: Dx: 12 Co: 14 In:20 Wi:12 Ch:10 Chaotic 9:940
Dlv1:5
5:246 HP (28)
Pw: 34 (53) AC:9
Xp: 4/113 T:1736 Burdened
Figure 5: Left: Instantaneous progress (5) (" for representative episode where k= 8, with peak progress indicated in red. Right: Cropped frames st-k and corresponding to the peak progress estimate. This transition demonstrates how dungeon exploration results high progress estimates. Bottom: Example saliency map over the bottom two lines of the observation, with brighter colors corresponding to higher sensitivity of the output to that cell in the observation. The progress model has learned to be sensitive to dungeon and experience levels, character ability scores, gold, magic power, armor class, and game score. See Fig. 17 for more saliency visualizations.
8

---

Published as a conference paper at ICLR 2023
Figure shows the results of experiments using different history offsets and dataset sizes for ELE. On the left, the learned progress model is evaluated using different offsets into the recent past for the progress reward Oracle, the most challenging task. While ELE is robust to a variety of history lengths, observe that horizon length 8 performs best for sparse tasks. On the right, we evaluate the performance of ELE with increasing dataset size by using demonstrations from the top N experts by Z-score. While large datasets perform well on the dense Score task, we find that the top 10 experts provide the best dataset for the challenging Oracle task. Section A.2 we provide an analysis of the datasets and demonstrate that Top 10 provides the best balance between dataset size and coverage of the early game, which is where the tasks we investigate in this paper take place.
ELE K-2
ELE
Norallzed Epicode Return
Normatizdd Epiedd Returrn
ELE Top
ELE K-16
ELE Top 10
K=32
ELE
ELE K-128
ELE Top 100
0.6
0.4
0.0
Score
Oracle
0.0
Score
Gracle
Figure 6: Comparison of ELE using different hyperparameters. Left: Hyperparameter sweep for history length where 8=8 performs best. Right: Performance of ELE using demonstration datasets of increasing size. We find that the top 10 experts provide the best dataset for our most challenging task (see Section A.2 for further analysis).
CONCLUSION
In this work, we hypothesize that a collection of expert demonstrations implicitly defines a set of monotonic progress functions, and that increasing these progress functions over time results efficient exploration in challenging environments. We propose method for approximating one simple class of such monotonic progress functions: the temporal difference between frames. All else being equal, exploration that looks like positive temporal difference under the expert distribution is likely discover extrinsic task feedback more efficiently than unguided exploration. We demonstrate in the NetHack environment that following progress model is an effective way discover rewards in even very sparse tasks, and even when the demonstrations in question consist of noisy, action-free data captured in the wild.
When the observations contain explicit timing information, effort is required mitigate the tendency of the progress model to focus solely on these features to the exclusion of more semantically meaningful information. In this work we explicitly remove the timer from the input, which is easy do in NetHack observations. However, for other environments where the explicit timing information is more subtle and difficult to remove explicitly, there are promising research directions involving unsupervised approaches to factor these features out.
The issue with explicit time observations an instance of a more general challenge in applying this sort of method. Consider tasks with cyclic dynamics, or state maintenance tasks such as balancing a pole: maximizing predicted temporal distances would not be sufficient, and this situation an explicit timer in the observation may actually help rather than hurt. Thus, when applying method such ELE, some care warranted to ensure that the observations will encourage the model to learn a notion of progress that is appropriate to the task.
The temporal difference between frames is a simple monotonic function that we have chosen to focus on in this work. However, we hypothesize that demonstrations implicitly define a large set of such functions, and discovering latent progress functions not directly tied to temporal differences is another important area that deserves further investigation beyond the scope of this report.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We would like to thank Duncan Williams, Surya Bhupatiraju, Dan Horgan and Richard Powell for developing the underlying Muesli agent for NetHack, including hyperparameter and architecture tuning. We would like to thank Adam Santoro, Doina Precup and Tim Rocktäschel for feedback on the paper, which improved the manuscript substantially. We would also like to thank the anonymous reviewers for detailed reviews and feedback on the paper. Additionally, we are grateful to M. Drew Streib, the host of the nethack.alt.org server for recording 14 years of gameplay, without which this work would not have been possible. Last but not the least, we would like to extend our heartfelt thanks to the 10 experts in the NetHack community whose gameplay data helped us to make scientific advances in this domain, in order of increasing Z-score: stenno, 78291, Fek, Yum Yum, rschaff, oh6, Luxidream, Tariru, stth, and Stroller.
ETHICS STATEMENT
This work is made possible by expert data generated by the NetHack community and made publically available by the owners the form of terminal recordings, and these recordings include the usernames of the humans that generated the data. This data is already publically available and permissively licensed; we train on the existing data and release curated subset.
httt:::///thack.... wwt.cck.at..... .rt.org The data includes full human gameplay in
REPRODUCIBILITY STATEMENT
We have made an effort to ensure reproducibility via a) releasing the dataset that used for our main results to empower the community to conduct further research using this curated subset of high-quality play, and b) exhaustively detailing the hyperparameters and implementation details of our approach, our network architecture, and the computational resources used for our experiments in Section A.1 We also detail several potential variations of our approach in Section A.4
REFERENCES
Josh Abramson, Arun Ahuja, Arthur Brussee, Federico Carnevale, Mary Cassin, Felix Fischer, Petko Georgiev, Alex Goldin, Tim Harley, et al. Creating multimodal interactive agents with imitation and self-supervised learning. arXiv preprint arXiv:2112.03766 2021.
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C Courville, and Mare Bellemare. Deep reinforcement learning at the edge of the statistical precipice. Advances in neural information processing systems, 34:29304 29320, 2021.
Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Claudio Fantacci, Jonathan Godwin, Chris Jones, Ross Hemsley, Tom Hennigan, Matteo Hessel, Shaobo Hou, Steven Kapturowski, Thomas Keck, Iurüi Kemaev, Michael King, Markus Kunesch, Lena Martens, Hamza Merzic, Vladimir Mikulik, Tamara Norman, John Quan, George Papamakarios, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Luyu Wang, Wojeiech Stokowiec, and Fabio Viola. The DeepMind JAX Ecosystem, 2020. URL http::ttt//te /tttt::://gttbb.bb com/ deepmii ic]
Bowen Baker, Ilge Akkaya, Peter Zhokhov, Joost Huizinga, Jie Tang, Adrien Ecoffet, Brandon Houghton, Raul Sampedro, and Jeff Clune. Video PreTraining (VPT); Learning Act by Watching Unlabeled Online Videos. arXiv preprint arXiv:2206. 11795, 2022.
Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying sount-based exploration and intrinsic motivation. Advances in neural information processing systems, 29, 2016.
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
Yuri Burda, Harrison Edwards, Amos J. Storkey, and Oleg Klimov. Exploration by ran- dom network distillation. In 7th International Conference on Learning Representations,
10

---

Published as a conference paper at ICLR 2023
ICLR 2019, New Orleans, LA. USA, May 6-9, 2019. OpenReview.net, 2019.
URL
net/ wttt://oooumnndiiiooee Hort:t
Gabriel V Cruz Jr, Yunshu Du, and Matthew E Taylor. Pre-training neural networks with human demonstrations for deep reinforcement learnin. arXiv preprint 1rXi::1709.04400 2017.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth Stanley, and Jeff Clune. Go-explore: new approach for hard-exploration problems. arXiv preprint arXiv: arXiv:/901. /99999919999. 2019.
Adrien Ecoffet, Joost Huizinga, Joel I Lehman, Kenneth O Stanley, and Jeff Clune. First return, then explore. Nature, 590(7847):580-586) 2021.
Ashley Edwards, Himanshu Sahni, Yannick Schroecker, and Charles Isbell. Imitating latent policies from observation. In International conference on machine learning, pp. 1755-1763 PMLR, 2019.
Linxi Fan, Guanzhi Wang, Yunfan Jiang, Ajay Mandlekar, Yuncong Yang, Haoyi Zhu, Andrew Tang, De-An Huang, Yuke Zhu, and Anima Anandkumar. Minedojo: Building open-ended embodied agents with internet-scale knowledge. arXiv preprini arXiv:2206. 08853,, 2022.
James C Fu and Tung-Lung Wu. Linear and nonlinear boundary crossing probabilities for brownian motion and related processes. Journal of Applied Probability, 47(4):0058-107 2010.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. Internationaa conference on machine learning, pp. 2052-2062. PMLR, 2019.
Çaglar Gülçehree Tom Le Paine, Bobak Shahriari, Misha Denil, Matt Hoffmann, Hubert Soyer, Richard Tanbur, Steven Kapturowski, Neil C. Rabinowitz, Duncan Williams, Gabriel Barth-Maron, Ziyu Wang, Nando de Freitas, and Worlds Team. Making efficient use of demonstrations to solve hard exploration problems. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Zhaohan Daniel Guo, Shantanu Thakoor, Miruna Pislar, Bernardo Avila Pires, Florent Altché, Corentin Tallec, Alaa Saade, Daniele Calandriello, Exploration by Bootstrapped Prediction. arXiv preprint arXiv:2206008332, 2022.
Grill, Yunhao Tang, al. BYOL-Explore:
Eric Hambro, Sharada Mohanty, Dmitri Babaev, Minwoo Byeon, Dipam Chakraborty, Edward Grefenstette, Minqi Jiang, Jo Daejin, Anssi Kanervisto, Jongmin Kim, et al. Insights from the NeurlPS 2021 NetHack challenge. In NewrlPS 2021 Competitions and Demonstrations Track, pp. 41-52. PMLR, 2022a.
Eric Hambro, Roberta Raileanu, Danielle Rothermel, Vegard Mella, Tim Rocktäschel, Heinrich Kuttler, and Naila Murray. Dungeons and data: A large-scale nethack dataset. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022b. URL
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and patlern recognition, pp. 770-778, 2016.
Matteo Hessel, Ivo Danihelka, Fabio Viola, Arthur Guez, Simon Schmitt, Laurent Sifre, Theophane Weber, David Silver, and Hado Van Hasselt. Muesli: Combining improvements in policy optimization. In International Conference on Machine Learning, pp. 4214 4226. PMLR, 2021a.
Matteo Hessel, Manuel Kroiss, Aidan Clark, Iurii Kemaev, John Quan, Thomas Keck, Fabio Viola, and Hado van Hasselt. Podracer architectures for scalable reinforcement learning. arXiv preprint arXiv:2104.06272 2021b.
Todd Hester, Matej Vecerik, Olivier Pietquin, Marc Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, et al. Deep Q-learnin from demonstrations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural
information processing systems, 29, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 98) 1997.
11

---

Published as a conference paper at ICLR 2023
Zhang- Wei Hong, Tzu- Yun Shann, Shih- Yang Su, Yi-Hsiang Chang, Tsu-Jui Fu, and Chun- Yi Lee. Diversity-driven exploration strategy for deep reinforcement leamning Advances neural information processing systems, 31, 2018.
Andrew Jaegle, Yury Sulsky, Arun Ahuja, Jake Bruce, Rob Fergus, and Greg Wayne. Imitation by predicting observations. In International Conference on Machine Learning, pp. 4665-4676, PMLR, 2021.
Hyoungseok Kim, Jackyeom Kim, Yeonwoo Jeong, Sergey Levine, and Hyun Oh Song. EMI: Exploration with mutual information. arXiv preprint 1rXiv:1810.01166, 2018.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:111.699800 2014.
Heinrich Küttler, Nantas Nardelli, Alexander Miller, Roberta Raileanu, Marco Selvatici, Edward Grefenstette, and Tim Rocktäschel. The NetHack Learning Environment. Advances in Neural Information Processing Systems, 33:7671-7684, 2020.
Ajay Mandlekar, Danfei Xu, Josiah Wong, Soroush Nasiriany, Chen Wang, Rohun Kulkarni, Li Fei-Fei, Silvio Savarese, Yuke Zhu, and Roberto Martin-Martin. What matters in learning from offline human demonstrations for robot manipulation. arXiv preprint arXiv:2108.032295 2021.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off- reinforcement learning. Advances in neural proceesni
processing systems, 29, 2016.
nethackwiki.com. Nethack wiki, 2022. URL
com
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrll.. Curiosity-drive exploration by self- supervised prediction. In International conference on machine leamning pp. 2778-2787. PMLR, 2017.
Rafael Figueiredo Prudencio, Marcos R. A. Máximo, and Esther Luna Colombini. A survey on offline reinforcement learning: Taxonomy, review, and open problems. CoRR, abs/2203.01387, 2022. doi: 10.485500arxx1:2220..13.3 URL htt.tttpp////oo.ooeeeeeeetee wtt.:///............5555000/0... 40w0::0043000101111 2203. C1387
Roberta Raileanu and Tim Rocktäschel. Ride: Rewarding impact-driven exploration for procedurally- generated environments. arXiv preprint arXiv:2002.11299 2020.
Herbert Robbins and David Siegmund. Boundary crossing probabilities for the wiener process and sample sums. The Annals of Mathematical Statistics, pp. 1410-1429, 1970.
René Schilling and Lothar Partzsch. Brownian Motion: An Introduction to Stochastic Processes, 2012.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering Atari, Go. Chess and Shogi by planning with a learned model. Nature, 588(7839):604-66 609, 2020.
Younggyo Seo, Lili Chen, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lee. State entropy maximization with random encoders for efficient exploration. International Conference on Machine Learning, pp. 9443-9454. PMLR, 2021.
Younggyo Seo, Kimin Lee, Stephen L James, and Pieter Abbeel. Reinforcement learning with action- freee pre-training from videos. In International Conference on Machine Learning, pp. 19561-19579, PMLR, 2022.
Mathieu Seurin, Florian Strub, Philippe Preux, and Olivier Pietquin. Don't do what doesn't matter: Intrinsic motivation with action usefulness. arXiv preprint arXiv:2105.0999) 2021.
Rohin Shah, Cody Wild, Steven H Wang, Neel Alex, Brandon Houghton, William Guss, Sharada Mohanty, Anssi Kanervisto, Stephanie Milani, Nicholay Topin, al. The MineRL BASALT competition learning from human feedback. arXiv preprint arXiv:2107.01963 2021.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
12

---

Published as a conference paper at ICLR 2023
Faraz Torabi, Garrett Wareel,, and Peter Stone. Behavioral cloning from observation. arXiv preprint arXi:: 2018a.
Faraz Torabi, Garrett Warnell, and Peter Stone. Generative adwersaail adveraail imitation from observation. CoRR, abs/1807.06 181180...11, 2018b. URL UtL.pccee////aa....rr/////////// 06158
Fan Yang, Gabriel Barth-Maron, Piotr Stańczyk, Matthew Hoffiman, Siqi Liu, Manuel Kroiss, Acdan Pope. and Alban Rrustemi. Launchpad: A programming model for distributed machine learning research. arXiv preprint arXiv:2106.04:: 16516, 2021. httttttts///xxiii/ org/ abs:://b//2// 211.22116.....1.
Denis Yarats, Rob Fergus, Alessandro azaric, and Lerrel Pinto. Reinforcement learning with prototypical representations. In International Conference on Machine Learning pp. 11920-11931. PMLR, 2021.
Tianhe Yu, Aviral Kumar, Yevgen Chebotar, Chelsea Finn, Sergey Levine, and Karol Hausman. Data sharing without rewards in multi-task offline reinforcement learning. 2021.
Tianjun Zhang, Huazhe Xu, Xiaolong Wang, Yi Wu, Kurt Keutzer, Joseph E Gonzalez, and Yuandong Tian. Bebold: Exploration beyond the boundary of explored regions. arXiv preprint arXiv:2012.0862/ 2020.
A APPENDIX
A.1
IMPLEMENTATION DETAILS
Architecture diagrams for all approaches are shown in Fig. The architecture of the agent composed of feedforward ResNet (He et al. 2016) torso without normalization layers, followed by an LSTM (Hochreiter) Schmidhuber 1997) and residual connection from the torso. The BCO baseline uses the same architecture as the agent. The GAIfO and RND baselines use only the feedforward network, with each hidden layer reduced to 16 channels to minimize overfitting, FORM requires full state predictions, and so use the fully-comvolutional architecture shown in Fig.
Hyperparameters for all experiments are shown Table Where hyperparameters differ between approaches, the differences shown in Table 3 We anneal the learning rate linearly toward its final value over the course 1B frames. Each experiment was run on TPUv3 accelerators using a podracer provides a pseudocode description of the algorithm. Results of hyperparameter sweeps for each approach are shown in Fig.
configuration (Hessel al., (021b). Algorithm [
Hyperparameter
Value
Optimizer
Adam
Kingma & Ba 2014
Adam
8
Initial learning rate
6x10
Final learning rate (linear anneal)
10-5
Maximum absolute parameter update
1.0
Discount factor
0.997
Policy unroll length
35
Model unroll length
5
Retrace X (Munos et al. 2016
0.95
Batch size
960 sequences
Replay proportion in batch Replay buffer capacity
50%
4000 frames
Replay max samples per insert
Target network update rate
0.1
Muesli regularization weight (uniform prior)
0,003
Muesli regularization weight (target network prior)
0.03
Value loss weight
0.25
Reward loss weight Policy loss weight
1.0
3.0
Table 2: Muesli hyperparameters that are consistent between methods.
13

---

Published as a conference paper at ICLR 2023
Architecture
Agent uses
FORM Architecture
GAIrO, 8CO, Progress Model and RND use Restict LSTM
250-24-80
1024 9,4
x64
1024
Flatten
Conv
x128
Conv
Residual
Conv
x128
Conv
2x2 downsample Conv
Cony
Conv
Residual
x128
Conv
X64
2x2 downsample
Conv
X64
Residual
x120
Conv
x64
3x9 kamal
Feature planes
Bibit characters
Feature planes
B-sit colors
2x236
1-tot cursor
24
Input
Input
5,
80
Figure 7: Left: RL agent architecture. Right: FORM model architecture.
Hyperparameter
Value
ELE reward weight w"
0.01
BCO loss weight
0.01
FORM batch size
576 sequences
FORM reward weight
0.1
GAIfO reward weight
1.0
RND reward weight
0.1
Table 3: Hyperparameters that differ between methods. Note that the large prediction network FORM requires smaller batch size in order to fit in accelerator memory.
A.2 DATASET SIZE
The full dataset from http:://ethhce alt. (Hambro et al. 2022b) contains approximately 7M sequences at the time of this writing. However, the data varies widely in quality from beginners and scripted bots all the way world-class gameplay from the top NetHack experts. In addition, the full dataset is too large to fit comfortably on most storage hardware. As result, would be desirable to reduce the size of the dataset just curated sample of the highest quality play. To generate a curated subset of the highest quality data, we filter the dataset to include only the sessions from the top N users as ranked by Zeooor. From the NetHack wiki (nethackwiki.com 2022):
Z-score is meant to provide an alternative to using score to rank players, since score is not reliable measure of ability. It is compiled by looking at all of player's
14

---

Published as a conference paper at ICLR 2023
Algorithm 1: Pseudocode description of Explore Like Experts (ELE)
Input Dataaset DD hyperparameters and w
for epoch = MM do
Sample minibatch {())))))>>>
* Update the parameters of the progress model 0m+1 Om + In.j,. - for epoch j 1,2,... do Sample a trajectory 7 TET from current actor policy for (4) do
* Compute auxiliary reward using the progress model
= ((((-=+);000))
Update the total reward by linear
combination of environment reward and auxiliary reward +r
Update agent parameters with using new reward
ELC
FOOm WHEAL
LLC
poda
Gaso Widum
0010 Weddun
BCD yorko
16
0000 W0-1.
SC3T
septe
66
Figure 8: Hyperparameter sweeps for each method on a dense and sparse task. Where there ambiguity over which hyperparameter value to use for the final experiments, we choose the hyperparameter that performs best the sparse task over the dense task.
ascensions and assigning 1 point for the first ascension of a role, 1/2 point for the second ascension, 1/3 for the third, and so on. Z-score encourages playing the complete set of roles rather than repeatedly ascending the same role.
In addition to filtering by Z-score, we include only episodes where the screen contains only standard ASCII characters (i.c. sessions that the standard NetHack interface). we eliminate any episodes where we cannot identify the dungeon grid on the screen (as this indicates the user may be using a non-standard user interface layout), and consider only episodes that contain at least 100 timesteps minimize the number of episodes that involve save-scumming (Hambro et al. (022b).
In order determine how many the top experts are sufficient use as a demonstration dataset we evaluate our method on Score, the most popular NetHack task, and Oracle, the most challenging of the sparse tasks in this paper, using demonstrations from the top users
the 1,,,
results are shown in Fig. 6 (right). Dataset sizes are shown in Table 4 All else being equal, one might expect larger datasets to better. actuality, we find that the top experts works best for the sparse for all of the experiments in this work that use demonstrations,
tasks, and this is the dataset and this is the dataset we release alongside the paper.
In order explain why increasing dataset size does not yield better results on these tasks, consider two analyses. Fig. shows, for each dataset, the proportion of the timesteps in the dataset that correspond the early game of NetHack, i.e. the portion of the game that is most relevant to all of the tasks
15

---

Published as a conference paper at ICLR 2023
Dataset
Sequences
Timesteps
Top
4703
54.2 M
Top 2
8336
112.1 M
Top
11887
136.3 M
Top 5
11962
136.5 M
Top 10
16478
184.2 M
Top 20
33882
282.2 M
Top 50
62300
421.3 M
Top 100
98614
567.5 M
Table 4: Size of each dataset considered in this section.
consider. Specifically, this experience levels 1-5, dungeon levels 1-10, and dungeon number (i.e. main dungeon). We in these results that the top-10 dataset which we find yields the best results is also the dataset that includes the most gameplay covering the early dungeon and experience levels.
Figure 9: Proportion of transitions that cover the early game in each dataset; higher better. The top-10 dataset contains the largest proportion of early game data in terms of both dungeon level and experience level, and is only marginally behind top-2 in terms of time spent in the main branch of the dungeon (dungeon number zero).
In order to attempt quantify the degree which each dataset covers the distribution of the game, also analyze the difference between each dataset and all of the others as measured by the total symmetric KL divergence between distributions over. character alignment, role, dungeon number, dungeon level, and experience level (See Fig. TOP. We see with this analysis that the top- 10 dataset is closest to all of the other datasets by most of the quantities question, which suggests that top- 10 may have the best general coverage of the game.
Figure 10: Total KL between distributions over alignment, role, dungeon number, level number, and experience level, as the sum over the KL between the dataset in question and all others. Lower values indicate that the dataset coverage closer the others.
16

---

Published as a conference paper at ICLR 2023
A.3 HUMAN BASELINE FOR ORACLE TASK
To convey a sense of the difficulty of the Oracle task, we collected 170 episodes of gameplay from an intermediate NetHack player. Table 5 reports some statistics of these human games. In particular, our human baseline finds the Oracle in 48.2% of episodes, taking an average of 899.2 timesteps to do so on a successful episode, which corresponds to an average of 8.9 minutes of gameplay. This longer than a typical episode from our agent, which completes the task in an average of 547.2 steps as reported in Table [ On average the human player performed 1.9 steps per second, which highlights how much longer a game of NetHack can be, compared to environments with high frequency real-time frame rates such as Atari.
Number of games
170
Success rate
48.2%
Number of timesteps (All)
863.5 + 584.8 steps
Number of timesteps (Successful)
899.2 + 662.9 steps
Maximum number of timesteps
4663 steps
Real time length (All)
8.2 = 5.9 minutes
Real time length (Successful)
8.9 7.0 minutes
Maximum real time length
35.1 minutes
Steps per second
1.9 0.5
Table 5: Statistics of intermediate human gameplay the challenging Oracle task.
A.4 PROGRESS REWARD VARIANTS
Given a progress model /* (81,88) that estimates the temporal distance between two states, there are a variety of ways that an exploration reward can be formulated. In this section, we explore three potential approaches. With the Initial Absolute reward function, we give an exploration reward to the agent equal to the estimated temporal distance between the current state and the initial state r3 = f (s),s)). The Local Absolute reward function corresponds to reward function equal to the estimated temporal distance between the current state and a frame i: steps in the past r; = f (s)- Finally, the Local Relative approach rewards the agent based on the difference in local progress between adjacent states r; = (* -f= (st-
Fig. II shows the performance of the agent using each of the variants on Depth and Oracle, two of the more challenging sparse tasks. We can see that the local absolute progress performs best, with local relative progress achieving reasonable performance, but worse than local absolute. Progress against the initial frame, on the other hand, performs quite poorly- see Fig. 4 for visualization of the initial absolute progress over the course of an episode: it has very high variance, indicating that it is difficult to make absolute progress predictions over such long timescales.
Prggess Mozel Mariento. Dryrt
Tregnaa Modal Vartarta Druchl
Local Abuakio butter Abcutate
Ratativs
0.8
MIA
0.35
0.3
1.3 0.50
0.3
6:2
6-6 3.5 0.6
0.8
Figure 11: Performance of three variants of the progress reward: Local Absolute refers to the approach that we in the paper where the reward r; = ( with == Local Relative corresponds to reward based on the difference between local progress for adjacent states T f (st (( 1); and Initial Absolute refers to rewarding progress against the initial state of the episode re = (so.st). This figure shows the performance of the three variants on two of the challenging sparse tasks: Depth 4 (Left) and Oracle (Right).
17

---

Published as a conference paper at ICLR 2023
A.5 STATISTICAL ANALYSIS OF RESULTS
In this section we conduct statistical analysis of the performance of our approach using the methouds outlined in (Agarwal et al. 2021). Fig. 12 shows evaluation metrics aggregated across all tasks in order to produce larger statistical sample. As mentioned in Section 4.1 we normalize the returns of the dense tasks Score and Scout by the 80th percentile across all approaches so they lie approximately in comparable range [0.1] to the sparse tasks. See Fig. 3 (right) for permutation tests that demonstrate that our method outperforms RND, GAIfO, BCO, and vanilla Muesli at confidence levels of at least 85% on this benchmark, while since FORM performs well on Depth well as the dense tasks, ELE only outperforms FORM with confidence of approximately 70%.
Mean
Neckan
CNN
Optimally Gap
Mucsi
800
FORM
Figure 12: Aggregate metrics on 9 NetHack tasks with 95% Cls based on 5 random seeds. Higher mean, median and IQM scores and lower optimality gap are better. Our method ELE significantly outperforms the baselines according to all measures of central tendency.
A.6 ANALYSIS OF THE PROGRESS MODEL
In order to visualize the sort of transitions that result in large progress events, we include a representative example of an instantaneous progress curve (*(())888)) for a typical episode generated by our ELE agent. Fig. 13 shows the progress values with the top 4 progress events highlighted in red, and Fig. [4 shows the specific transitions that correspond to those events. The progress model has learned that, in this episode, revealing tiles in the dungeon, leveling up, and descending to new dungeon levels are the most prominent indicators of progress.
Progress_t
1500
1250
1000
Figure 13: Peaks of the progress estimate during a representative episode.
In the latest version of the NetHack learning environment, the in-game timer is visible in the observations. This is an issue for our approach, where if trivial timing information is available, the progress model is not required to learn semantically meaningful representations of progress. Therefore, for all methods evaluated in this work, we mask the timer feature with zeros to reduce reliance on this trivial information. See Fig. [5 for a) the loss curve of the supervised regressor in the offline training phase for the model with and without access to the timer feature, and b) the sensitivity of the model to the timer feature as a proportion of the total gradient with respect to the input. In Fig, [6 we show the performance of the resulting agent when trained against progress model with and without access to the timer.
18

---

Published as a conference paper at ICLR 2023
Rgnen the Steippingg
Duxte/01 Part3 Dorts Trr1d wi16 Chi towtel trsh
Rgeee cae teripling
26-78A0 5x:133 O6176 Taxt0 Mild Chis Sowteil 0:13
He aicipping
11/1/1 mex13 oucte trund will eu. neafull xv28 a018 3p:8/33
hyme 1-b Aitree
-1ult 1a:13 our touid will clul tweffll ax78
acce Xp:3/43 Hangss
Sxppet 1st the mmady) Receee
the ativeidee
ai-1t/01 ouuld wilh 8 seeful
11/00 ou.16 tavid wi.s ch. teed.1
nleiie 5:302 shv1 tw (b acvé 2u/8/93 T:3225
clvlid 8:3 my 182h Tw-88 aC-i 8/88 To3250
DESINN BEe MEASES Mocs
Ins dost 30 Aockomi
ilat Si1E 19:2 22) 8616 30/0/31 1:007
shelid a:27t 19:39 mwi7 6616 9n/2/33 T:865
Figure 14: Visualization of the pair of frames corresponding to each peak in Fig. 13 Differences
highlighted in red: this episode, the progress model estimates large amounts of progress for (Top) exploring the dungeon, (Middle) leveling up, and (Bottom) descending the next dungeon level.
Fig. 17 shows saliency map of the learned progress model a) with access to the timer, and b) without access to the timer. The magnitude of the gradient of the absolute progress estimate is represented by the brightness of the red highlight. Where explicit timing information is available, the model will focus almost exclusively on this feature. We find that this hurts the ability ELE to explore, as even meaningless random behavior usually results in advancement of the in te-game time, in this work. Some real-wor rerl-world environments contain explicit timing information like this, so factoring these features in way that requires less domain knowledge is promising objective for further work.
remove it from the observation
19

---

Published as a conference paper at ICLR 2023
Froguess Model Trasing Loos
Prageess Medel Sensiliiyy to Timer
Without Timer
0.30
Without Timer
Croaeer PrEeO 10 Tave
15.0
0.20
g 12.5
0.15
0.05
5.0
0.00
2.5
SOD0100
S2Ap S00000
Figure 15: Left: Median learning curve for the supervised regressor over three seeds in the offline training phase. Note that with access to the timer, the loss curve reaches a much lower value, indicating that the timer feature is extremely useful for the prediction task, despite not conveying much information about progress. Right: The sensitivity of the progress model to the timer feature, as proportion of the total gradient with respect to the input: when the model has access to the timer, it concentrates a disproportionate amount of its weights on that part of the imput.
Depth
Without Timer
With
With Timer
Without Timer
EShodd Catter
0.4
8.15
0.10
0.2
0.0
0.4 0.5
3.0
0.2
0.4
Figure 16: Episode return achieved by ELE using progress models with and without access the timer on two of the sparse tasks: (Left) Depth 4 and (Right) Oracle. The progress model with access to the timer results in poor exploration, since the estimate considers primarily the in-game time passing, rather than making meaningful progress in exploring the dungeon.
In addition to the saliency analysis, we provide accuracy plot in Fig. [8 that demonstrates the accuracy of the trained progress model over a variety of tolerances around the target value. The models trained on each of the datasets do not differ significantly in their accuracy, and perhaps surprisingly, the accuracy itself is apparently not very high (for example, only approximately 55% of predictions are within 50% of the target value). This is likely because of the difficulty of predicting distances over very long trajectories: we sample a maximum distance of 10K timesteps during training, and for long intervals like this, there are very many different paths that could lead between two states. Nonetheless, the progress model appears to be effective as an exploration reward despite the difficulty of making accurate predictions.
A.7 FORM AND STOCHASTICITY
Despite performing well compared to the other baselines, FORM struggles to solve the hardest tasks where ELE still succeeds. The core mechanism of FORM is to learn a predictor pD(+;) -t-1 of state transitions under a demonstrator policy, independent of actions. This prediction task is difficuult when a) the demonstration policies result in inconsistent transitions, and b) the environment dynamics are themselves highly stochastic. In our case, the demonstration policies are quite diverse: we ten different experts who will each have different play styles, and they may not even take the same action each time they themselves encounter the same state, due differences in mood, motivation, etc.
20

---

Published as a conference paper at ICLR 2023
cLaris bocavaos 28:18/04 bec54 0o:28 1n:12 wi:lt the14 Nectral 5:87066
Tazico Svotec
56:33 De-11 Cor15 a0:13 W1:30 Ch:10
Chaotic
Screlt Nut (1817)71 7:11
22:13 30:80 00:54 18:39 N5.12 Ch23
Nuttral 517382
2n13 VILLE ch: Seuceal
Figure 17: Saliency map the progress model over input calculated as V. s,, ( (top) with and (bottom) without access to the timer observation. Top: When the timer is available, the saliency map consistently strongest in that part of the input. Bottom: with the timer feature explicitly masked, the model is required to pay attention to more semantically interesting parts of the input such as the dungeon, and the character statistics.
Progress Model Accuracy
0.8
Top
Top
tercnntage
0.7
Top
Top
0.5
Top
Top
0.4
Top 100
Accuracy
0.3
0.1
0.0
20
40
60
80
100
Parcentaga of Target Valua
variety of tolerances around the target value. Since the progress model is regression model, it is not easy to provide an intuitive summary in single accuracy value. Instead, show how many predictions from the model lie within a particular percentage of the target value.
Figure 18: Accuracy of the progress model for each dataset
Beyond this, NetHack is stochastic and partially observed: it is not possible to predict accurately what the next dungeon level will look like, or what will be revealed behind a closed door. Both of these factors make for challenging prediction task, and the resulting rewards from FORM may be highly inconsistent. In addition, while the FORM model is trained on dataset of pairs (s,,) the ELE progress model trained on pairs (tt,8t+8) for &e
As result, the effective size of the progress model dataset much larger. See Fig, 19 for example predictions and likelihood visualizations from the FORM model, demonstrating the difficulty of the prediction task.
21

---

Hoblibbd as conderueee a
paper at ICLR 2023
1E-2 ROLLS RESTRRL
1 LE
Vigure 19: Peedicionn and vieaiiooe
from the FORM model: (Left) Avenge of 256 samplee Note that due to the mhheren fuzzy in regions
rechastte of
from the FORKY model
plet 16641/1
the Traiinng data.
the quite are Predcchiin
experti
of the input hidder the from player. by The Reatmmnn (Right)
oright bigallihee indicatte higghty surprising actual next franee st-11 with The
the
the meeiiere sumprsaii under
demeerta of the inteevvttionn nnestts
gemeral in Ristruuutiio are not
protici in vivannee due to the aucurriiiii in both the exporri polley play (s8) and the iifioomnne
which
possitoo to
po Mise i (e.0)).
CONNECCTION AND COTTANTONN SKAMPLL DERVATION
TO DOCCLASTI PROCESSSE
4.8
The predauttian at the cone of ELLE consiat in segurnggg an averuge dinevttin of (owvant pregees from Faiinng the
That conoraaiiiiiii
compeznn Offiiiee
is. that nnowingg
pessmmbi from data is Cominng
its sapoungg overall trana model in innggugge and using this
that implics polley
duberrnne even ummiineeddd will intervatiooo
by the mimperten
mumaraiiiio imuunnad
model for
project
the RL aggent onto
can amplrrriio gneatty improve the iitesttuuuiii of the agent aboout the worl.. paths.
subpppcc spanned
In dhis
veviaaiioon the
are receenrraiie along sueaonaal
as
22

---

Published as a conference paper at ICLR 2023
In this section, we dissect the notion of forward progress by showing how it is analogous to the concept of drift in stochastic process theory. We begin by constructing a simple I-dimensional environment where the notion of forward progress corresponds to the drift of the stochastic process.
Suppose an agent begins an episode at the origin of the real line, and allowed to take independent, Gaussian steps either to the left to the right of the starting position. Moreover, the agent receives positive reward the first time it crosses a boundary specified by = c for c>> O within at most 7 steps. This hypothetical example can be formulated as maximizing the number of boundary crossings Wiener process (Fu & Wu 2010).
The idea for solving this I-dimensional walk the real line summarized as follows: if we estimate the progress (i.e. expected direction) of sample paths which are deemed successful according to some criteria (in this case, reaching a specific region the line), then we can use this information guide our learning by projecting the problem into simpler space s.t. even random deviations of the RL. agent from demonstrations can lead improving the agent's performance.
Lemma A.1 Let A) be the value function at t 0 of the policy W W(t) + At, where (W [0,2]} is a Wiener process on [0,T", deployed in the 1-dimensional example above. Then,
T = argamax (0,A)
AERR
Since the angle between the expected values of the optimal policy W At and W(t) in the time domain given by 0 t=tan -aan--(G (G)) A can be interpreted as a measure of alignment of the current policy with respect the optimal one. Pre-training progress model data which has a high 0 will provide an initial alignment, while pre-training on data closer to random has a lower and hence lower value. Our approach aims to use demonstrations to learn progress model which, when used as an auxiliary reward, yields behavior which is more closely aligned to the optimal behavior than random exploration would be.
Optimal value function depends on the drift Let (007)) be a Wiener process R. Then the expected reward collected by the policy W(1) = ( + A (i.e. Wiener process with drift A) over the time interval [0,7) is
T
T
V(0:A)= = V (W
(3)
where A/2 can be upper-bounded using the martingale result of Robbins & Siegmund (1970)
C +VTTT) 22-2220 AVT VT
PW(()+A+2d<FFF sup W(t)+At2d=1- rE(O,T]
(4)
VT
This implies that for A A 0, (O0,A) VO0.22), the process ((t) is symmetrically around Specifically, sample paths reaching are more likely for higher values of A. This can be shown by writing the above probability
( 11110 C +AVT
te 2nd
AVT
C VT
(5)
VT
Since sp is smooth A, solving the following optimization problem using Leibniz's rule
d v
=0}
(6)
dA
23

---

Published as a conference paper at ICLR 2023
yields the following relationship between path length, boundary position and drift parameter:
2
c
T=
A A
If. matching our 1-D experiments, we let 200 and T = 2000, then the estimated drift A= 1o 1ov10 00131 Given that [[ and (tW =t. the process (()) rotates according the angle specified by A, and the number of boundary crossings increases when A o0.
If we wish to further and let the agent's trajectories end withing an e-ball of the goal c, the corresponding success probability be computed follows:
C+E
+AVT
- 2(cte)A
AVT CtE
VT
VT
(8)
+
C-E
+AVT
- 2(c-e)
AVT C-E
-1
Maximizing the above probability as a function A using Leibniz's 's rule yields A T, which agrees with results of Schiiling & Partzsch (2012).
Wiener process (iT))
prosass
Wiener process 191 At+ WCD where à 0.13
10
150
100
50
250
300
750
1000
1000 1290 1902 10d 2002
750 1000 1250 2310 2/50 2000
Figure 20: 100 sample paths from the Wiener process with drift A, for various values of A. Paths which end in the region [190,210] after 2000 timesteps are highlighted in red, and the mean of W Al is shown green.
Fraction of paths from W()) which fall into the region [c - 10,c + 10]
1.0
0.8
Fraction of paths
0.6
0.2
0.00
0.05
0.10
0.20
0.25
Figure 21: Fraction of sample paths which land in the region [190,210) after 2000 timesteps as a function of drift parameter A. A =.11 is the value for which (()) has the most paths landing in the goal region, and thus corresponds to maximal progress.
24

---

Published as a conference paper at ICLR 2023
Epicodo Retum
Demonstration
10000
ELCC Optimal
800
0000
800
6000
4000
200
2000
Optimal
2500
5000
7500
10000
13500
15000
17500
20000
2500
$000
7500
10600
32500
15009
17580
20000
Trajectories
200
150
125
125
50
ELE
Optimal
Start
175
End
25 50
75
100
125
150
175
200
Figure 22: Toy grid environment: 200 200 square grid with tabular Q-learning agent and ELE. The agent can move in the 8 orthogonal and diagonal directions, starts at (1,100) and receives a reward of 1000 and episode termination when reaching (200,100). (Top Left) Episode returm: the demonstrations achieve approximately 950 reward on average, while ELE receives nearly 1000, and tabular Q-learning on its own reaches approximately 700 by the time the experiment ends after 20K episodes. (Top Right) Episode length: the demonstrations and Q-learning agent take suboptimal paths to the goal, whereas tabular Q-learning the ELE objective rapidly reaches near-optimal path lengths. (Bottom Left) 10 example trajectories from each method: ELE discovers paths that more directly approach the goal than the demonstrations that it learned from. (Bottom Right) Visualization of the ELE progress model f (St,3144) for (100, 100) against all possible 8t4k- The model has learned that expert progress tends to be positive to the right of s, and negative to the left.
25

---

Published as a conference paper at ICLR 2023
50
90
50
75
75
130
150
150
100
175
25
100
125
125
25
30
30
30
79
125
125
100
150
375
100
12%
175
100
125
150
25
23
25
100
125
125
125
100 125 350
373
50 100
325
130
175
23
100 125 150
375
Figure 23: Progress model estimates (*,,88+44) from nine different states 8, = (x.y) the toy tabular environment. Rows: x == 50, x 100, and x == 150. Columns: y= 50, y = 100, and y= 150. Progress estimates are generally high the direction the goal, and low in the opposite direction. Points near the y = 100 line the most densely represented in the demonstration data, the progress estimates toward the center the grid are the most well-defined.
26


Reviews:
[{"review_id": "PRUoYi9cbvB", "reviewer": "Reviewer_iUvn", "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": "This paper presents an approach for improving agent exploration in reinforcement learning tasks using a learned distance model from an unlabelled dataset of human plays. The training paradigm has two steps. First, the authors train a distance predictor for each pair of states. The distance is used to help agents to explore as an intrinsic reward signal.", "summary_of_the_review": "Overall the paper presented an interesting idea and promising results.", "strength_and_weaknesses": "The paper presented a simple but promising approach to learning intrinsic rewards for exploration. The model can be learned from unlabelled offline data, which contain human expert demonstrations on possibly irrelevant tasks. The model outperforms several baselines on tasks in the NetHack environment.\n\nOverall I think the paper presentation is clear, and the comparisons are sufficient. There are a few points for potential improvements.\n\n1. Is there any way that we can test the accuracy of the pretrained distance prediction model? How does that really translate into performance?\n2. I am not familiar with the NetHack environment. a. Is the map fixed? b. Do the tested tasks require handling partial observability? I am asking because If the map is not fixed how can you model learn the distance function between different \"levels?\"\n3. How similar are the demonstrations to the testing tasks? Are expert demonstrations exactly for the task (e.g., oracle)?\n4. My understanding of the answer to Q3 is no. But then, I don't understand how the baseline BCO works. \n5. Also, while I understand that there will be a lot of \"noise\" in such a large-scale dataset, Figure 6 makes me very worried: it seems that the authors have just used data from 10 players. Do you have any guesses about why model performance drops when you have more data? Is it because the larger dataset requires a larger model? Or is it because of the \"noises?\" If so, what is exactly the \"noises?\" Or is it an issue with the proposed method? (e.g., the proposed objective is too hard to be learned from Internet data).\n6. The authors should consider comparing with works on \"subgoal generation.\" For example,\nCzechowski, Konrad, et al. \"Subgoal search for complex reasoning tasks.\" Advances in Neural Information Processing Systems 34 (2021): 624-638.\n7. Is the state-only setting a real constraint of the environment/dataset? That is, is there any way to obtain large-scale data with actions?\n8. How will the model compare with other exploration strategies, such as Go-Explore (Ecoffet et al., 2019)?\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": "KqXVP7lOVJw", "reviewer": "Reviewer_hMhc", "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": "This paper studies the question of how to leverage expert demonstrations when explicit actions are not present in RL environments which have long timescales and sparse rewards, but for which there exists a notion of monotone increasing progress over time. The central idea of this paper is to use the (incomplete) expert demonstration data to estimate a function which predicts the temporal distance between two states. Then, this function is used to define a weighted auxillary reward which measures the progress between the current state and the state $k$ steps in the past; $k$ is a hyper-parameter which is tuned. RL algorithms without this additional signal are then compared to RL algorithms which use this modified reward function, this meta-algorithm is referred to as ELE, and experiments are conducted both in a toy gridworld setting and in the first 1M steps of the game NetHack, a challenging environment with long timescales and sparse rewards that has been previously studied for which incomplete expert demonstrations are available. Compared to other learning algorithms which work over the same information, ELE outperforms (in some cases, quite significantly) the other methods on a variety of sparse signal long-horizon tasks. A curated dataset of expert demonstrations on Nethack (subsampled from an existing dataset) is also planned to be released.", "summary_of_the_review": "Overall, the paper seems interesting and clear. I would lean towards accepting the paper.\n\n====== POST-REBUTTAL =======\n\nHaving read the other reviews and responses, I remain convinced that the paper should be accepted.", "strength_and_weaknesses": "* Strengths: \n   * The paper considers a highly relevant and interesting setting involving expert information, long timescales, and sparse reward signals.\n   * The paper proposes the interesting (and apparently novel) idea of estimating a temporal progress function (while controlling for removing trivial signals from which progress can be deduced), and finds that with some specific choices of how the progress function estimation is implemented and used as an auxillary reward, that it is quite beneficial. This seems like quite a nice simple principle to uncover if it was previously unknown. \n   * The paper provides extensive experiments and comparisons on their domain of choice (which seems to be a reasonable stand-in for any setting with incomplete expert demonstrations), and they examine performance on several tasks with uncertainty estimates for the performance of their algorithm beating existing algorithms.\n   * An open-source curated dataset will be released for the NetHack environment, which may prove useful for further work on long timescale with sparse reward and incomplete demonstration information. \n   * Some useful empirical choices in the estimation of the progress function were uncovered as a result of this work: shorter timescale prediction of progress performs better than not, and log scaling during the training of the progress function was also useful.\n   * A fairly thorough related work section is provided.\n\n* Weaknesses:\n   * It would be very useful to additionally examine a setting where the expert demonstrations are not incomplete; in such settings (still with long time horizons and sparse rewards), how does ELE fair against standard imitation learning algorithms like Behavior Cloning and DAgger (and more recent variants)? That would help disambiguate whether ELE is useful only in the context of missing demonstration information, or whether the idea is more broadly useful even when you have full expert demonstrations.\n   * It would be nice to provide a clearer justification and understanding (empirical or theoretical) of why estimating the progress function is helpful; likewise with the insight that shorter time horizons are more useful to train on. \n   * Only one underlying RL algorithm was tested (Muesli) unless I missed something -- it would be quite valuable to understand whether the underlying RL algorithm being used affects the utility of the augmented reward signal.\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "9OZt9QXHesm", "reviewer": "Reviewer_8ZSu", "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 authors propose a method (ELE) to incorporate information from expert (observation-only) demonstrations into an RL agent by first learning an estimate of \"progress\" and using this estimate as an intrinsic reward. Progress in this case is defined to be the temporal distance between two states.\n\nResults are first shown on a toy grid-world environment, where demonstrations are epsilon-greedy oracle policies (choosing the optimal action 2.5% of the time). Further experiments on 7 different tasks in the NetHack environment shows that ELE is competitive against a wide variety of baselines, and is particularly effective in sparse reward settings. \n\nFinally, qualitative visualizations of the progress function, an episode from a trained policy, and saliency maps are presented, as well as ablations on the expert demonstrations dataset size and the \"history length\" hyperparameter.", "summary_of_the_review": "The paper is well written, the idea is novel, and experiments are fairly comprehensive. Only reservations I have are in the fact that there is only one environment and the lack of analysis comparing ELE to FORM (see weaknesses section).", "strength_and_weaknesses": "Strengths:\n\nWell written paper with the main idea presented very clearly and with good motivation. The method is novel (to the best of my knowledge) and clever, the experiments and baselines are comprehensive, and the toy grid-world experiment is succinct and didactic. The conclusion includes candid discussion of the limitations of this approach, which I appreciated.\n\nWeaknesses:\n\nI can see empirically that ELE outperforms FORM on the sparse reward tasks (figure 3), but I think some analysis of why this is the case would be helpful. Both methods get access to the same demonstration data and both are just intrinsic rewards on top of the same RL algorithm (from what I understand). So what makes ELE better than FORM? \n\nThe ablations in figure 6 shows empirically why we would want to use only demonstrations from the top 10 users, but I don't understand fundamentally why more demonstrations would hurt. For example, what about the top 10 players makes it so different from the next 10 players?\n\nThe experiments section could be improved by demonstrating the method on more than just the NetHack environment.\n\nFor which task is the right side of figure 3 plotting? ", "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": "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": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%