# Common-Knowledge Concept Recognition for SEVA

Jitin Krishnan1, Patrick Coronado2, Hemant Purohit3, Huzefa Rangwala4
1,4Department of Computer Science, George Mason University
2Instrument Development Center, NASA Goddard Space Flight Center
3Information Sciences & Technology Department, George Mason University
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We build a common-knowledge concept recognition system for a Systems
Engineer’s Virtual Assistant (SEVA) which can be used for downstream tasks
such as relation extraction, knowledge graph construction, and question-
answering. The problem is formulated as a token classification task similar to
named entity extraction. With the help of a domain expert and text processing
methods, we construct a dataset annotated at the word-level by carefully
defining a labelling scheme to train a sequence model to recognize systems
engineering concepts. We use a pre-trained language model and fine-tune it
with the labeled dataset of concepts. In addition, we also create some
essential datasets for information such as abbreviations and definitions from
the systems engineering domain. Finally, we construct a simple knowledge graph
using these extracted concepts along with some hyponym relations.

#### Keywords:

Natural Language Processing, Named Entity Recognition, Concept Recognition,
Relation Extraction, Systems Engineering.

## INTRODUCTION

The Systems Engineer’s Virtual Assistant (SEVA) (?) was introduced with the
goal to assist systems engineers (SE) in their problem-solving abilities by
keeping track of large amounts of information of a NASA-specific project and
using the information to answer queries from the user. In this work, we
address a system element by constructing a common-knowledge concept
recognition system for improving the performance of SEVA, using the static
knowledge collected from the Systems Engineering Handbook (?) that is widely
used in projects across the organization as domain-specific commonsense
knowledge. At NASA, although there exists knowledge engines and ontologies for
the SE domain such as MBSE (?), IMCE (?), and OpenCaesar (?), generic
commonsense acquisition is rarely discussed; we aim to address this challenge.

SE commonsense comes from years of experience and learning which involves
background knowledge that goes beyond any handbook. Although constructing an
assistant like SEVA system is the overarching objective, a key problem to
first address is to extract elementary common-knowledge concepts using the SE
handbook and domain experts. We use the term ‘common-knowledge’ as the
‘commonsense’ knowledge of a specific domain. This knowledge can be seen as a
pivot that can be used later to collect ‘commonsense’ knowledge for the SE
domain. We propose a preliminary research study that can pave a path towards a
comprehensive commonsense knowledge acquisition for an effective Artificial
Intelligence (AI) application for the SE domain. Overall structure of this
work is summarized in Figure 1. Implementation with demo and dataset is
available at:  https://github.com/jitinkrishnan/NASA-SE .

Figure 1: Common-knowledge concept recognition and simple relation extraction

## BACKGROUND AND MOTIVATION

Creating commonsense AI still remains an important and challenging task in AI
research today. Some of the inspiring works are the CYC project (?) that tries
to serve as a foundational knowledge to all systems with millions of everyday
life commonsense assertions, Mosaic Commonsense Knowledge Graphs and Reasoning
(?) that addresses aspects like social situations, mental states, and causal
relationships, and Aristo System (?) that focuses on basic science knowledge.
In NASA’s context, systems engineering combines several engineering
disciplines requiring extreme coordination and is prone to human errors. This,
in combination with the lack of efficient knowledge transfer of generic
lessons-learned makes most technology-based missions risk-averse. Thus, a
comprehensive commonsense engine can significantly enhance the productivity of
any mission by letting the experts focus on what they do best.

Concept Recognition (CR) is a task identical to the traditional Named Entity
Recognition (NER) problem. A typical NER task seeks to identify entities like
name of a person such as ‘Shakespeare’, a geographical location such as
‘London’, or name of an organisation such as ‘NASA’ from unstructured text. A
supervised NER dataset consists of the above mentioned entities annotated at
the word-token level using labelling schemes such as BIO which provides
beginning (B), continuation or inside (I), and outside (O) representation for
each word of an entity. (?) is the current top-performing NER model for
CoNLL-2003 shared task (?). Off-the-shelf named entity extractors do not
suffice in the SE common-knowledge scenario because the entities we want to
extract are domain-specific concepts such as ‘system architecture’ or
‘functional requirements’ rather than physical entities such as ‘Shakespeare’
or ‘London’. This requires defining new labels and fine-tuning.

Relation extraction tasks extract semantic relationships from text. These
extractors aim to connect named entities such as ‘Shakespeare’ and ‘England’
using relations such as ‘born-in’. Relations can be as simple as using hand-
built patterns or as challenging as using unsupervised methods like Open IE
(?); with bootstrapping, supervised, and semi-supervised methods in between.
(?) and (?) are some of the high performing models that extract relations from
New York Times Corpus (?) and TACRED challenges (?) respectively. Hyponyms
represent hierarchical connection between entities of a domain and represent
important relationships. For instance, a well-known work by (?) uses syntactic
patterns such as [Y such as A, B, C], [Y including X], or [Y, including X] to
extract hyponyms. Our goal is to extract preliminary hyponym relations from
the concepts extracted by the CR and to connect the entities through verb
phrases.

## CONCEPT RECOGNITION

SE concepts are less ambiguous as compared to generic natural language text. A
word usually means one concept. For example, the word ‘system’ usually means
the same when referring to a ‘complex system’, ‘system structure’, or
‘management system’ in the SE domain. In generic text, the meaning of terms
like ‘evaluation’, ‘requirement’, or ‘analysis’ may contextually differ. We
would like domain specific phrases such as ‘system evaluation’, ‘performance
requirement’, or ‘system analysis’ to be single entities. Based on the
operational and system concepts described in (?), we carefully construct a set
of concept-labels for the SE handbook which is shown in the next section.

### BIO Labelling Scheme

  1. 1.

abb: represents abbreviations such as TRL representing Technology Readiness
Level.

  2. 2.

grp: represents a group of people or an individual such as Electrical
Engineers, Systems Engineers or a Project Manager.

  3. 3.

syscon: represents any system concepts such as engineering unit, product,
hardware, software, etc. They mostly represent physical concepts.

  4. 4.

opcon: represents operational concepts such as decision analysis process,
technology maturity assessment, system requirements review, etc.

  5. 5.

seterm: represents generic terms that are frequently used in SE text and those
that do not fall under syscon or opcon such as project, mission, key
performance parameter, audit etc.

  6. 6.

event: represents event-like information in SE text such as Pre-Phase A, Phase
A, Phase B, etc.

  7. 7.

org: represents an organization such as ‘NASA’, ‘aerospace industry’, etc.

  8. 8.

art: represents names of artifacts or instruments such as ‘AS1300’

  9. 9.

cardinal: represents numerical values such as ‘1’, ‘100’, ’one’ etc.

  10. 10.

loc: represents location-like entities such as component facilities or
centralized facility.

  11. 11.

mea: represents measures, features, or behaviors such as cost, risk, or
feasibility.

### Abbreviations

Abbreviations are used frequently in SE text. We automatically extract
abbreviations using simple pattern-matching around parentheses. Given below is
a sample regex that matches most abbreviations in the SE handbook.

r"\\([ ]*[A-Z][A-Za-z]*[ ]*\\)"An iterative regex matching procedure using
this pattern over the preceding words will produce the full phrase of the
abbreviation. ‘A process to determine a system’s technological maturity based
on Technology Readiness Levels (TRLs)’ produces the abbreviation TRL which
stands for Technology Readiness Levels. ‘Define one or more initial Concept of
Operations (ConOps) scenarios’ produces the abbreviation ConOps which stands
for Concept of Operations. We pre-label these abbreviations as concept
entities. Many of these abbreviations are also provided in the Appendix
section of the handbook which is also extracted and used as concepts.

### Common-Knowledge Definitions

Various locations of the handbook and the glossary provide definitions of
several SE concepts. We collect these and compile a comprehensive definitions
document which is also used for the concept recognition task. An example
definition and its description is shown below:
Definition: Acceptable Risk
Description: The risk that is understood and agreed to by the program/project,
governing authority, mission directorate, and other customer(s) such that no
further specific mitigating action is required.

### CR Dataset Construction and Pre-processing

Using python tools such as PyPDF2, NLTK, and RegEx we build a pipeline to
convert PDF to raw text along with extensive pre-processing which includes
joining sentences that are split, removing URLs, shortening duplicate non-
alpha characters, and replacing full forms of abbreviations with their
shortened forms. We assume that the SE text is free of spelling errors. For
the CR dataset, we select coherent paragraphs and full sentences by avoiding
headers and short blurbs. Using domain keywords and a domain expert, we
annotate roughly $3700$ sentences at the word-token level. An example is shown
in Figure 2 and the unique tag count is shown in Table 1.

Figure 2: A Snippet of the concept-labelled dataset O | 73944 | B-cardinal | 414 | I-grp | 132
---|---|---|---|---|---
B-opcon | 5530 | B-abb | 354 | B-org | 87
B-syscon | 1640 | B-event | 350 | I-seterm | 26
B-seterm | 1431 | I-event | 218 | B-art | 17
I-opcon | 1334 | I-syscon | 201 | I-org | 12
B-mea | 1117 | I-abb | 156 | I-loc | 3
B-grp | 499 | I-mea | 145 | B-loc | 2
Table 1: Unique Tag Count from the CR dataset

### Fine tuning with BERT

Any language model can be used for the purpose of customizing an NER problem
to CR. We choose to go with BERT (?) because of its general-purpose nature and
usage of contextualized word embeddings.

In the hand-labelled dataset, each word gets a label. The idea is to perform
multi-class classification using BERT’s pre-trained cased language model. We
use pytorch transformers and hugging face as per the tutorial by (?) which
uses $BertForTokenClassification$. The text is embedded as tokens and masks
with a maximum token length. This embedded tokens are provided as the input to
the pre-trained BERT model for a full fine-tuning. The model gives an F1-score
of $0.89$ for the concept recognition task. An 80-20 data split is used for
training and evaluation. Detailed performance of the CR is shown in Table 2
and 3. Additionally, we also implemented CR using spaCy (?) which also
produced similar results.

| precision | recall | f1-score | support
---|---|---|---|---
syscon | 0.94 | 0.89 | 0.91 | 320
opcon | 0.87 | 0.91 | 0.89 | 1154
seterm | 0.98 | 0.94 | 0.96 | 287
mea | 0.91 | 0.90 | 0.90 | 248
grp | 0.94 | 0.93 | 0.94 | 89
org | 1.00 | 0.11 | 0.21 | 26
cardinal | 0.90 | 0.92 | 0.91 | 71
event | 0.71 | 0.78 | 0.76 | 77
abb | 0.82 | 0.58 | 0.68 | 79
art | 0.00 | 0.00 | 0.00 | 4
loc | 0.00 | 0.00 | 0.00 | 1
micro/macro-avg | 0.90 | 0.88 | 0.88 | 2356
Table 2: Performance of different labels F1-Score |  Accuracy |  Accuracy without ‘O’-tag
---|---|---
0.89 |  0.97 |  0.86
Table 3: Overall Performance of CR; For fairness, we also provide the accuracy
when the most common ‘O’-tag is excluded from the analysis.

## RELATION EXTRACTION

In this work, for relation extraction, we focus on hyponyms and verb phrase
chunking. Hyponyms are more specific concepts such as earth to planet or rose
to flower. Verb phrase chunking connects the named entities recognized by the
CR model through verbs.

### Hyponyms from Definitions

The definition document consists of $241$ SE definitions and their
descriptions. We iteratively construct entities in increasing order of number
of words in the definitions with the help of their parts-of-speech tags. This
helps in creating subset-of relation between a lower-word entity and a higher-
word entity. Each root entity is lemmatized such that entities like processes
and process appear only once.

### Hyponyms from POS tags

Using the words (especially nouns) that surround an already identified named
entity, more specific entities can be identified. This is performed on a few
selected entity tags such as opcon and syscon. For example, consider the
sentence ‘SE functions should be performed’. ‘SE’ has tag NNP and ‘functions’
has tag NNS. We create a relation called subset-of between ‘SE functions’ and
‘SE’.

### Relations from Abbreviations

Relations from abbreviations are simple direct connections between the
abbreviation and its full form described in the abbreviations dataset. Figure
3 shows a snippet of knowledge graph constructed using stands-for and subset-
of relationships. Larger graphs are shown in the demo.

Figure 3: A snippet of the knowledge graph generated

### Relation Extraction using Verb Phrase Chunking

Finally, we explore creating contextual triples from sentences using all the
entities extracted using the CR model and entities from definitions. Only
those phrases that connect two entities are selected for verb phrase
extraction. Using NLTK’s regex parser and chunker, a grammar such as

VP:
{(<MD>|<R.*>|<I.*>|<VB.*>|<JJ.*>|<TO>)*<VB.*>+(<MD>|<R.*>|<I.*>|<VB.*>|<JJ.*>|<TO>)*}with
at least one verb, can extract relation-like phrases from the phrase that
links two concepts. An example is shown in Figure 4. Further investigation of
relation extraction from SE handbook is left as future work.

Figure 4: Relation Extraction using Verb Phrase

## CONCLUSION AND FUTURE WORK

We presented a common-knowledge concept extractor for the Systems Engineer’s
Virtual Assistant (SEVA) system and showed how it can be beneficial for
downstream tasks such as relation extraction and knowledge graph construction.
We construct a word-level annotated dataset with the help of a domain expert
by carefully defining a labelling scheme to train a sequence labelling task to
recognize SE concepts. Further, we also construct some essential datasets from
the SE domain which can be used for future research. Future directions include
constructing a comprehensive common-knowledge relation extractor from SE
handbook and incorporating such human knowledge into a more comprehensive
machine-processable commonsense knowledge base for the SE domain.

## References

  * [AI2 Allen Institute for AI ] AI2 Allen Institute for AI.  Aristo: An intelligent system that reads, learns, and reasons about science.  https://allenai.org/aristo/.  Accessed: 2019-08-12.
  * [Baevski et al. 2019] Baevski, A.; Edunov, S.; Liu, Y.; Zettlemoyer, L.; and Auli, M.  2019\.  Cloze-driven pretraining of self-attention networks.  arXiv preprint arXiv:1903.07785.
  * [Devlin et al. 2018] Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K.  2018\.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805.
  * [Elaasar 2019] Elaasar, M.  2019\.  Open casesar; the case for integrated model centric engineering.
  * [Etzioni et al. 2011] Etzioni, O.; Fader, A.; Christensen, J.; Soderland, S.; and Mausam.  2011\.  Open information extraction: the second generation.  IJCAI 3–10.
  * [Hart 2015] Hart, L. E.  2015\.  Introduction to model-based system engineering (mbse) and sysml.  http://www.incose.org/docs/default-source/delaware-valley/mbse-overview-incose-30-july-2015.pdf.  Accessed: 11-09-2017.
  * [Hearst 1992] Hearst, M. A.  1992\.  Automatic acquisition of hyponyms from large text corpora.  In Proceedings of the 14th conference on Computational linguistics-Vol. 2, 539–545.  ACL.
  * [Honnibal and Johnson 2015] Honnibal, M., and Johnson, M.  2015\.  An improved non-monotonic transition system for dependency parsing.  In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, 1373–1378.  ACL.
  * [Huang 2019] Huang, B.  2019\.  Ner with bert in action.
  * [JPL 2016] JPL.  2016\.  Imce ontological modeling framework.
  * [Krishnan, Coronado, and Reed 2019] Krishnan, J.; Coronado, P.; and Reed, T.  2019\.  Seva: A systems engineer’s virtual assistant.  In AAAI-MAKE Spring Symposium.
  * [NASA 2017] NASA.  2017\.  Nasa systems engineering handbook.
  * [Panton et al. 2006] Panton, K.; Matuszek, C.; Lenat, D.; Schneider, D.; Witbrock, M.; Siegel, N.; and Shepard, B.  2006\.  Common Sense Reasoning – From Cyc to Intelligent Assistant.  Berlin, Heidelberg: Springer Berlin Heidelberg.  1–31.
  * [Riedel, Yao, and McCallum 2010] Riedel, S.; Yao, L.; and McCallum, A.  2010\.  Modeling relations and their mentions without labeled text.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 148–163.  Springer.
  * [Sang and De Meulder 2003] Sang, E. F., and De Meulder, F.  2003\.  Introduction to the conll-2003 shared task: Language-independent named entity recognition.  arXiv preprint cs/0306050.
  * [Soares et al. 2019] Soares, L. B.; FitzGerald, N.; Ling, J.; and Kwiatkowski, T.  2019\.  Matching the blanks: Distributional similarity for relation learning.  arXiv preprint arXiv:1906.03158.
  * [Xu and Barbosa 2019] Xu, P., and Barbosa, D.  2019\.  Connecting language and knowledge with heterogeneous representations for neural relation extraction.  arXiv preprint arXiv:1903.10126.
  * [Zellers et al. 2018] Zellers, R.; Bisk, Y.; Schwartz, R.; and Choi, Y.  2018\.  Swag: A large-scale adversarial dataset for grounded commonsense inference.  CoRR abs/1808.05326.
  * [Zhang et al. 2017] Zhang, Y.; Zhong, V.; Chen, D.; Angeli, G.; and Manning, C. D.  2017\.  Position-aware attention and supervised data improve slot filling.  In EMNLP, 35–45.


figuret

# Intelligent Go-Explore: Standing on the
Shoulders of Giant Foundation Models

Cong Lu1,2
<EMAIL_ADDRESS>Shengran Hu1,2
<EMAIL_ADDRESS>Jeff Clune1,2,3
<EMAIL_ADDRESS>
1University of British Columbia
2Vector Institute
3Canada CIFAR AI Chair

###### Abstract

Go-Explore is a powerful family of algorithms designed to solve hard-
exploration problems built on the principle of archiving discovered states,
and iteratively returning to and exploring from the most promising states.
This approach has led to superhuman performance across a wide variety of
challenging problems including Atari games and robotic control, but requires
manually designing heuristics to guide exploration (i.e. determine which
states to save and explore from, and what actions to consider next), which is
time-consuming and infeasible in general. To resolve this, we propose
Intelligent Go-Explore (IGE) which greatly extends the scope of the original
Go-Explore by replacing these handcrafted heuristics with the intelligence and
internalized human notions of interestingness captured by giant pretrained
foundation models (FMs). This provides IGE with a human-like ability to
instinctively identify how interesting or promising any new state is (e.g.
discovering new objects, locations, or behaviors), even in complex
environments where heuristics are hard to define. Moreover, IGE offers the
exciting and previously impossible opportunity to _recognize and capitalize on
serendipitous discoveries that cannot be predicted ahead of time_. We evaluate
our algorithm on a diverse range of language-based tasks that require search
and exploration. In Game of 24, a problem testing multistep mathematical
reasoning, IGE reaches 100% success rate 70.8% faster than the best classic
graph search baseline. Next, in BabyAI-Text, a challenging partially
observable gridworld where an agent has to follow language instructions, IGE
exceeds the previous state-of-the-art with orders of magnitude fewer online
samples. Finally, in TextWorld, a rich text game, we show the unique ability
of IGE to succeed in settings requiring long-horizon exploration where prior
state-of-the-art FM agents like Reflexion completely fail. Overall,
Intelligent Go-Explore combines the tremendous strengths of FMs and the
powerful Go-Explore algorithm, opening up a new frontier of research into
creating more generally capable agents with impressive exploration
capabilities. All our code is open-sourced at:
https://github.com/conglu1997/intelligent-go-explore.

##  1 Introduction

Foundation models (FMs, [5, 32, 7, 37, 39]) trained on giant internet-scale
datasets have demonstrated strong general capabilities in reasoning [41] and
understanding [9]. As such, these models have been increasingly employed as
autonomous agents [28, 44, 40, 43, 34, 4] in decision-making tasks, showcasing
the ability to adapt in-context [12, 31] to unseen tasks. However, a
significant challenge remains: foundation model agents often struggle in
environments that require deep exploration over extended time horizons [28].
Overcoming this limitation would enable us to realize their potential as
autonomous assistants in more open-ended domains like scientific discovery and
innovation [20]. This paper introduces Intelligent Go-Explore (IGE), a novel
approach that combines the intelligence foundation models with the powerful
Go-Explore [13, 14] framework to substantially increase the exploration
capabilities of FM and reinforcement learning (RL, [35]) agents.

Figure 1:  Intelligent Go-Explore (IGE) integrates the intelligence and
internalized human notions of interestingness from giant pretrained FMs into
all stages of the Go-Explore [13, 14] algorithm, enabling FM agents to
robustly explore in complex environments. Bottom: Classic Go-Explore solved
hard exploration problems by archiving novel discovered states, resetting to
promising ones via domain-specific heuristics, and then performing random
exploration. Top: Our approach, Intelligent Go-Explore, enables Go-Explore to
tackle virtually any type of problem that is representable in the context of a
large language or multimodal model. Instead of manually defining heuristics,
we query the foundation model at all stages, enabling our approach to
automatically catch and return to serendipitous discoveries, and harness the
power of FM agents to explore. The environment shown is the BabyAI-Text game
used in Section 4.2.

Go-Explore is a popular family of algorithms in deep RL based on maintaining
an archive of “interestingly new” discovered states and then iteratively
returning to and exploring from the most promising states (see Figure 1 for an
overview of the three stages). This framework has led to superhuman
performance in a range of hard-exploration problems, including long-horizon
Atari games and robotic control. However, the algorithm’s success _largely
relies on carefully hand-designed heuristics_ at all three stages to guide
exploration [29, 30]. For example, in Montezuma’s Revenge [2], an Atari game
that was the previous grand challenge of exploration in deep RL, (1) saved
states in the archive were returned to with probability proportional to
factors like the number of times a state has been sampled before, (2)
exploration was purely via random action sampling, and (3) the criteria for
which states were considered interestingly new enough to be added to the
archive depended on domain-specific factors like whether the agent visited a
new location, or did so with more keys. Without this pre-specified knowledge,
the quality of discovered trajectories is typically significantly worse [14].

These rigid, domain-specific choices are in stark contrast to human-like
exploration of a new game, where players can often intuitively judge the value
or interestingness of any particular state [10]. More importantly, _it is
often impossible to know what is interesting or possible ahead of time_ in
complex domains. In the words of Isaac Asimov— _The most exciting phrase to
hear in science, the one that heralds new discoveries, is not “Eureka!” but
“That’s funny.”._ With this motivation, IGE stands on the shoulders of giant
foundation models, and uses their intelligence to (1) act as a judge to
identify the most promising states to return to and explore from, (2) to
select the best actions to take to explore from a selected state, and (3) to
identify serendipitous discoveries when they happen (e.g. finding new objects,
locations, or other novelties) and decide whether a new state is interestingly
new enough to be added to the archive as a stepping stone for future
exploration (Figure 1, top).

We demonstrate IGE’s ability to reliably improve the exploration capabilities
of FM agents on a diverse range of language-based tasks that require search
and exploration. These settings include tasks that require _commonsense
reasoning, long-term planning and memory, and handling partial observability_.
IGE integrates well with various agent strategies, including few-shot and
chain-of-thought-based prompting; and _will only get better_ as the
capabilities of foundation models improve further. While IGE performs strongly
all-around, some highlights from our evaluation include: IGE reaches 100%
success rate on Game of 24 [43], a standard mathematical reasoning and search
problem, 70.8% faster than classic graph search. Moreover, on the TextWorld
[11] Coin Collector domain, IGE is the only algorithm that succeeds in
discovering long-horizon optimal solution paths, where prior state-of-the-art
FM agent frameworks like Reflexion [34] fail.

Intelligent Go-Explore simultaneously empowers foundation model agents to
_reliably explore_ , and reimagines the scope of Go-Explore to tackle
virtually any type of problem, without being limited to hand-designed
heuristics. These abilities will substantially improve our ability to develop
more generally capable agents, and increase the range of tasks they can learn
how to solve.

##  2 Background

###  2.1 Go-Explore for Hard-Exploration Problems

Go-Explore [14, 13] is a family of algorithms designed to solve hard-
exploration [24] problems based on the principle of remembering and returning
reliably to promising states. The classic setting builds an “archive” of novel
states it discovers in an environment, where similar states are grouped in a
single “cell”. These cells are defined by heuristics like having the same
visual observation when downsampled to low resolution. In the beginning, the
archive only contains the initial state. We describe the overall structure of
the algorithm in the same order as Figure 1 (bottom): At each iteration, (1)
promising states are selected from the archive through domain-specific
heuristics, e.g. probabilistically sampling states proportional to their
progress through the environment or potential to lead to new states. The agent
returns to that state, by resetting using the simulator or via a goal-
conditioned policy, and (2) a sequence of random actions is taken to explore
from that state. (3) All discovered states deemed interestingly new by the
cell representation heuristics are added to the archive, and the process
repeats. The strength of Go-Explore is due to addressing two critical
impediments to exploration: forgetting how to reach previously visited states
(detachment) and failing to first return to a state before exploring from it
(derailment) [13].

This approach leads to a collection of high-return trajectories being
discovered, which may then be fed into an imitation learning [19] algorithm to
produce a policy that generalizes and is robust to stochasticity. We adopt
similar assumptions as the original setting, by assuming an agent can return
to a previously discovered state by restoring in the simulator. This
assumption may readily be relaxed by training a policy to return to a given
state, or in the foundation model case, by simply prompting the model with a
past trajectory.

###  2.2 Large Language and Multimodal Foundation Models

The combination of model scaling and training over internet-scale data has
resulted in a wide variety of foundation models [5] that exhibit generalist
capabilities. In this paper, we consider autoregressive large language models
(LLMs, [7, 32, 39]) which learn to generate text completions by modeling the
conditional probability of a new token given the preceding tokens,
$p(x_{t}|x_{<t};\theta)$. This framework enables LLMs to not only generate
coherent text but crucially also exhibit human-like abilities, including on
commonsense knowledge questions [36] and complex reasoning tasks [41]. These
models may also be extended to other input modalities such as images by
tokenizing these inputs into the same space as the text [49]. When prompting
an FM with an instruction, the user may decide to do so with no related
examples (zero-shot), with a few successful examples in related problems (few-
shot, [7]), or ask for a chain of reasoning (chain-of-thought, [41]) before
responding.

##  3 Driving Exploration with Giant Foundation Models

In this section, we propose Intelligent Go-Explore (IGE) which reimagines the
classic Go-Explore algorithm as described in Section 2 with the intelligence
of giant pretrained foundation models. Specifically, we introduce FM
intelligence to selecting which archived state to return to and explore from,
which action to take from each state, and deciding whether a state is
interestingly new and should be archived. IGE’s use of foundation models is
closely related to FM-as-a-judge [48], which shows that foundation models are
a good proxy for human judgment to evaluate the output of generative models.
Here, instead of judging synthetic output, the foundation model makes choices
to determine the best way to explore an environment. We illustrate our
resultant algorithm at the top of Figure 1 and provide full pseudocode in
Algorithm 1.

Wherever we query the foundation model, we introduce the overall strategy of
Go-Explore alongside a brief description of the current environment in the
“system message” (high-level directive) displayed below. The brief
descriptions for each environment we evaluate on in Section 4 are listed in
Appendix B. In the following sections, we detail our prompting techniques at
each stage of IGE. The previous prompt history is visible to the agent, which
enables each component of IGE to communicate with each other. We provide
precise details on how we parse responses in Section C.1.

System Prompt. [Brief Description Of Environment] You will be prompted to
perform systematic exploration in the style of Go-Explore. An archive will be
maintained of interesting states found. You will be prompted to:
\- Select a state from the archive that is the most promising, i.e., likely to
lead to a solution or more novel states.
\- Explore from states intelligently, by picking new actions.
\- For each new state, determine if the state is interestingly new and should
be added to the archive.

###  3.1 Select State From Archive

The power to easily store and return to promising discovered states is crucial
to Go-Explore’s ability to reliably solve long-horizon exploration problems.
IGE leverages the foundation model’s internalized notions of interestingness
[45] to select the most promising state to return to from the archive (Figure
1, left). This is far more flexible than classic Go-Explore, which relied on
hardcoded hand-crafted heuristics to determine cell sampling probabilities. An
example prompt is shown below.

State Selection Prompt. Current state archive:
[Discovered states]
Select the most promising state.

Examples of the discovered states are given in Table 1. We assign indices to
these states in a list and ask the FM to select a numerical index. We define a
budget of $N_{\text{state}}$ “state-expansions”. Each state expansion is
followed by a sequence of exploratory actions, which we describe in the next
section.

###  3.2 Explore From State

In order to effectively explore from a state selected in the previous section,
we leverage the power of foundation model agents [28, 18] to choose how to act
in an environment. This vastly improves on the original Go-Explore’s use of
random action sampling. One of the key strengths of IGE is that it is a strict
improvement on top of any FM agent framework, _including zero-shot, few-shot,
or even chain-of-thought-based prompting_ [44]. We demonstrate this
flexibility in Section 4.

Action Selection Prompt. [Agent-Specific Prompt] Current state:
[Current State]
Previously tried actions:
[Previous Action History]
Output the next action.

One point of departure from the classic Go-Explore is that we additionally
maintain a state-conditional action history for each archived state, so that
IGE can avoid repeating previously tested options. While this information may
already be available in the entire history, this helps _avoid any recency bias
that can occur with longer contexts_ [46]. The action history can be easily
reiterated in the prompt, or the prompt could display the remaining untested
actions. We define a budget of exploratory actions per state expansion
$N_{\text{action}}$, which is typically far shorter than the full horizon of
the environment and represents a small number of trial actions. An example
prompt is shown here.

###  3.3 Update Archive

IGE queries the foundation model to judge whether any newly discovered state
is interestingly new and sufficiently different from prior states to qualify
to be added to the archive. Intuitively, we should only save the most relevant
stepping stones, and discard those that are unlikely to lead to new
discoveries.

Archive Filtering Prompt. Current state archive: [State Archive]
New state: [Current State]
Is this state interestingly new (relevant to the task or could lead to further
stepping stones, and not close to the existing states) and should be added to
the archive?

Whilst the original Go-Explore required extensive domain knowledge to
determine interestingness, IGE avoids this requirement and manual labor,
critically gaining the ability to recognize serendipitous discoveries that
could not have been predicted ahead of time. In practice, we propose two
options to filter discovered states after a sequence of exploratory actions.
The first is to iterate through every new state and ask whether each one is
interestingly new and should be added to the archive. The second is to first
add all states, and then ask the foundation model to remove the uninteresting
states. We discuss this choice later in Section 4.3; the second form is
preferable in larger environments where there is more need to explicitly
deprecate earlier discoveries that have become irrelevant to not overload the
archive. An example prompt for the first option is shown below.

By default, IGE implements the foundation model at all three stages of Go-
Explore, but we rigorously analyze the relative importance of each component
in Section 5. In this paper, we focus on the discovery of solutions to hard-
exploration problems. However, these solutions could easily then subsequently
be used for downstream reinforcement learning or even improve the foundation
model in the next task by in-context learning—thus allowing an agent to
bootstrap its own learning indefinitely.

##  4 Empirical Evaluation

In this section, we evaluate Intelligent Go-Explore across a diverse set of
text environments that require search and exploration. We demonstrate IGE’s
ability to handle partially observable and complex observation spaces,
discover solutions involving long chains of actions, and effectively improve
the ability of FM agents to explore. For all our experiments, we use GPT-4
[32], one of the current SOTA LLMs, as our foundation model. We compare IGE to
random action sampling, a naïve LLM baseline, and two SOTA FM agents, ReAct
[44] and Reflexion [34]. All methods use the same amount of environment steps
and receive the same observations for a fair comparison. Naïve LLM simply
queries the LLM for an action conditional on the interaction history. ReAct
prompts the agent to output its reasoning before making a decision. Based on
ReAct, Reflexion further conditions the agent on the previous attempted
episode, asking the agent to learn from its mistakes. We provide an overview
of our environments in Table 1. Full hyperparameters are detailed in Appendix
D.

Table 1:  We show that Intelligent Go-Explore can efficiently explore over a
diverse set of environments with increasing difficulty. The problems we
consider all use text-based observations, but in general, IGE may be extended
to virtually any environment that can be embedded in the context of a
multimodal foundation model. For each environment, we provide an example
observation, samples from the action space, and the horizon of the task in the
environment.

| Game of 24 | BabyAI-Text | TextWorld
---|---|---|---
Problem Type |  mathematical reasoning and search |  partially observable gridworld with language instructions |  partially observable game requiring long-term memory and planning, exploration, and common sense
Text Observation |  "Current state: (2 8 8 14)" |  "Goal: unlock the red door. You see a wall 4 steps forward, You see a yellow box 2 steps left." |  "You arrive in a pantry… You see a shelf. The shelf is wooden. On the shelf you can see flour…"
Next Actions |  \- 2 + 8 = 10 Next: (8 10 14) \- 8 / 2 = 4 Next: (4 8 14) \- 14 + 2 = 16 Next: (8 8 16) … |  \- turn left \- turn right \- go forward … |  \- go east \- cook potato with oven \- unlock door with key …
Task Horizon | 3 | 64 or 128 | 25, 40 or 80

###  4.1 Game Of 24

We first demonstrate the effectiveness of IGE in a mathematical reasoning
task, Game of 24 [43]. The goal is to perform basic arithmetic operations
$(+,-,\times,/)$ starting from 4 numbers to obtain 24. For example, given
input $(4,9,10,13)$, a possible solution could be $(10-4)\times(13-9)=24$. We
formulate the problem as an MDP [35], where actions represent a reduction of
two numbers by an arithmetic operation—i.e., the above solution would be
represented as the sequence of state transitions
$(4,9,10,13)\xrightarrow{10-4=6}(6,9,13)\xrightarrow{13-9=4}(6,4)\xrightarrow{6\times
4=24}(24)$. Therefore, IGE uses the FM to iteratively expand possible solution
paths and archive promising ones to return to. The action space is the range
of possible next operations, displayed in the same manner as in Yao et al.
[43].

Figure 2:  IGE explores the Game of 24 with the intelligence of FMs and
reaches 100% success rate on average 70.8% quicker than DFS, the next best
baseline. IGE completes all problems within 150 environment operations. Our
use of archiving and intelligent action selection allows us to greatly
outperform prior LLM agents with an equal number of operations performed. The
success rate is computed over 100 test problems.

We evaluate IGE across 100 hard test problems in Figure 2, and additionally
include the standard (unweighted) graph search algorithms depth-first search
(DFS) and breadth-first search (BFS) as reference. Since the combinatorial
complexity of the problem is at most $\binom{4}{2}\cdot\binom{3}{2}\cdot
4^{3}=1152$, graph search is guaranteed to find a solution within that many
actions. The system prompts for both IGE and the LLM baselines contain _few-
shot examples_ with correct calculations on different starting numbers. IGE
rapidly reaches 100% success rate, on average 70.8% quicker than the next best
baseline, depth-first search (DFS)— this improvement is statistically
significant ($\chi^{2}$ test, $p<0.05$) at 150 operations, where IGE has
solved all problems. This success may be attributed to the fact that language
models have internalized mathematical intuition and are likely to be able to
identify promising pairs like $(6,4)$ that could easily be multiplied together
for a solution.

All LLM agent baselines (naïve LLM, ReAct, Reflexion) eventually plateau and
even get beaten by the unintelligent DFS. This highlights the need for diverse
action selection, which IGE enables. A final point of comparison we make is to
Tree of Thoughts (ToT, [43]) which achieved 74% on Game of 24 within their
evaluation budget. We emphasize that our evaluation setting is very different
as IGE selects from the list of valid options rather than doing the math in
context. However, we note the key difference to our method is that ToT
evaluates and expands multiple reasoning paths following a tree structure,
whereas IGE can easily jump around the search space—this is a crucial
advantage in more complex environments (like those in the following sections),
where it takes many coordinated actions to get from one state to another
interesting state.

###  4.2 BabyAI-Text

Figure 3:  IGE can find solutions to challenging tasks in the BabyAI-Text
environment more effectively and with orders of magnitude fewer online steps
than prior RL-trained baselines (GLAM, [8]). Task types are in order of
difficulty. As tasks become more difficult, the performance gap of IGE v.s.
the LLM baselines grows. We show the mean and 95% bootstrap confidence
interval [50] over 25 seeds per environment type. _Here, and elsewhere,
confidence intervals are obtained by bootstrapped resampling 10,000 times._

Next, we show that IGE scales to the BabyAI-Text domain from Carta et al. [8],
which is a procedurally-generated partially-observable 2D gridworld with text-
based observations. The agent is given a textual goal instruction which could
correspond to one or more instructions in a sequence, e.g. “pick up X and then
go to Y”. As we can see from the observations in Table 1, the task is
challenging even for humans to complete and requires forming a model of the
world from partial text descriptions. This kind of state observation would
make it _hard to define heuristics to determine how good any particular state
is_ , as in classic Go-Explore. The optimal path to a solution may include
moving blocking objects as well as finding keys to open doors. We consider 5
different task families of increasing difficulty: “go to”, “pick up”, ‘pick up
then go to”, “open door”, and “put next to”, which are described fully in
Section B.2.

We omit the Reflexion baseline in this environment due to the high cost of
querying GPT-4 with 128-step episodes in the context. Due to the complexity of
this environment, we use _chain-of-thought prompting in all three components_
of IGE. This allows the FM to deliberate on the state of the game before
making decisions. We show that IGE can find solutions to these problems with
only a tiny budget of 250 environment steps per task (divided into rollouts of
10 exploratory actions each) and visualize the final performance in Figure 3.
IGE and ReAct vastly outperform the prior RL-trained language model approach,
GLAM [8], with orders of magnitude fewer samples (GLAM used 1.5M online steps)
and requiring no training whatsoever. IGE achieves the best or close to the
best performance in every task. The gap between IGE and the second-best method
grows with task difficulty, with a statistically significant 36% improvement
($\chi^{2}$ test, $p<0.05$) on ‘put next to’.

###  4.3 TextWorld

Finally, we show IGE’s ability to tackle tasks requiring long-horizon memory
and planning, exploration, and commonsense in TextWorld [11], a classic text-
based agent benchmark. We consider three challenging games in Textworld:
Treasure Hunter, The Cooking Game, and Coin Collector. In each game, the agent
needs to complete the task while navigating a maze of different rooms, while
only seeing the current room’s description in text. The agent interacts with
the world using free-form natural language commands, such as “go east” or
“cook potato with oven.” In Treasure Hunter [33], the agent has to find a
specific item by exploring, finding keys, and unlocking doors and containers.
In The Cooking Game, the agent must find a recipe, locate and process (e.g.,
dice, cut, chop) ingredients, and cook them according to the recipe using
various kitchen appliances (e.g., oven, pan). In Coin Collector, the agent
must find a coin randomly located in the maze, testing its navigation and
exploration skills. We set each game to hard difficulty, details on game
customizations are provided in Section B.3. As in the previous section, we use
chain-of-thought prompting in all three components of IGE. Because the state
archive in this environment grows significantly, we implement rejection-based
archive filtering, which we describe in Section C.2.

Figure 4:  IGE outperforms state-of-the-art FM agents in three challenging
text games in TextWorld. These results illustrate the powerful capabilities of
planning, commonsense reasoning, and exploration of IGE (Section 4.3).
Notably, in the Coin Collector game where hard exploration is required, we
observe BFS-like search behavior emerge in IGE, enabling it to find the most
efficient solution where all other approaches exhaust the environment horizon.
We show the mean and 95% bootstrap confidence interval over 25 seeds for each
game.

We present success rates achieved on the three games using IGE and the
baselines in Figure 4. We observe that IGE outperforms all other baselines,
with a statistically significant ($\chi^{2}$ test, $p<0.05$) performance gap
between IGE and the second-best method in the harder Cooking Game and Coin
Collector. In The Cooking Game, IGE outperforms the second-best agent, ReAct,
by a large margin of 36%, demonstrating IGE’s advantage in hard-exploration
problems. In Coin Collector, IGE _is the only method that can find the
solution in the maze_ , with all other methods completely failing.
Interestingly, we observe that IGE exhibits BFS-like behavior, and
intelligently selects rooms with unexplored directions and iteratively removes
rooms with exhausted directions. This results in IGE almost always finding the
shortest path to the target, while other methods fail to navigate the maze.

We highlight that Reflexion does not improve over ReAct in all the games we
tested. Although Reflexion should in theory be an improvement over ReAct with
the experience from previous attempts, it tends to decrease performance. We
hypothesize that in long-horizon environments, the history becomes too long
after the initial episode, and prevents Reflexion from effectively utilizing
knowledge from the previous episode. In contrast, IGE uses the FM to
iteratively filter interesting states in the archive, which ends up
_controlling the context length_. This helps IGE truly make use of the
cumulative knowledge gained through exploration.

##  5 Analysis

In this section, we analyze (1) the importance of FM intelligence for each of
the three key components of Go-Explore, (2) how IGE’s selectivity produces a
smaller (and thus more efficient) archive, and (3) how IGE’s performance
improves as the FM’s size/intelligence increases. We take a representative
sample of environments from the previous section of Game of 24, Put Next To
(PN) from BabyAI-Text, and The Cooking Game (CG) from TextWorld.
Hyperparameters are listed in Appendix D.

Table 2:  We rigorously ablate the design choices in IGE and analyze the importance of intelligent selection at each stage. Game of 24 performance is taken at 150 environment steps, over 100 evaluation seeds. BabyAI-Text performance is taken at 250 environment steps, over 25 evaluation seeds. TextWorld performance is taken at 240 environment steps, over 25 evaluation seeds. ‘Standard’ is mirrored from Section 4. We show the mean and 95% bootstrap confidence interval for the success rate.  Variant of IGE |  Success Rate (%)
---|---
Game of 24 | BabyAI (PN) | TextWorld (CG)
Standard | 100 $\pm$ 0.0 | 84 $\pm$ 14 | 92 $\pm$ 10
✗ Intelligent action selection |  068 $\pm$ 9.0 |  24 $\pm$ 16 |  00 $\pm$ 00
✗ Intelligent state selection |  096 $\pm$ 3.5 |  48 $\pm$ 20 |  76 $\pm$ 16
✗ Intelligent archive filtering |  093 $\pm$ 5.0 |  64 $\pm$ 20 |  64 $\pm$ 20
✗ All 3 above |  061 $\pm$ 9.5 |  4 $\pm$ 6 |  00 $\pm$ 00
✗ State-conditional action history |  033 $\pm$ 9.0 |  72 $\pm$ 16 |  72 $\pm$ 16

How Important is Foundation Model Intelligence at Each Step? First, we analyze
the impact of FM intelligence on each component of Intelligent Go-Explore. We
ablate replacing state and action selection with uniform random sampling,
archive filtering with saving everything to the archive, and not maintaining a
state-conditional action history. We use these unintelligent choices, as _it
would be very time-consuming to attempt to design the right heuristics_ based
on the rich text observations in Table 1. In Table 2, we observe that where
the intelligence of FMs is more valuable varies by environment. Since the
environment horizon is only 3 in the Game of 24, the most important factor is
ensuring that the actions tried are diverse and intelligently selected. This
hypothesis is confirmed: the largest performance drops occur when removing
either FM action selection or the action history. Different IGE components are
most helpful in both of the longer-horizon BabyAI-Text and TextWorld
environments: intelligent state selection and archive filtering make a big
impact, showcasing the strength of enabling IGE to return to promising
discovered states. There are smaller performance drops when removing the
action history; likely because in larger environments, many more unique states
are discovered, so there is less gain from preventing taking the same actions
from frequently returned to states. In both environments, we also observe a
drastic decrease when switching to random actions, as in classic Go-Explore.
This underscores the substantial benefits IGE provides in harnessing FMs for
action selection.

Finally, we elucidate the need for intelligent archive filtering across all
our environments. Not only does archive filtering improve performance, but it
also drastically cuts down the number of uninteresting states in the archive,
as shown in Table 3 (left). As we use rejection-based archive filtering on
TextWorld, we quote the average size of the archive throughout each episode.
In BabyAI-Text, we observe the archive becoming around $8\times$ larger
without filtering. These metrics demonstrate IGE’s innate ability to capture
promising discoveries as they occur and focus attention on them, without the
need for any manual heuristics.

Table 3:  Left: We show that intelligent filtering in IGE can drastically
reduce the size of the archive, and help the algorithm focus on the most
interesting states. Without intelligent filtering in BabyAI-Text and
TextWorld, the archive becomes over $5\times$ larger. Right: We show that IGE
scales with the capabilities of the underlying foundation model. We follow the
same settings with Table 2 and show the mean and 95% bootstrap confidence
interval for the number of states and success rate.

Archive Filtering | Number of States
---|---
Game of 24 | BabyAI (PN) | TextWorld (CG)
No Filter |  18.5 $\pm$ 3.2 |  203.5 $\pm$ 56.7 |  22.4 $\pm$ 15.3
With Filter | 15.6 $\pm$ 2.3 | 25.5 $\pm$ 5.2 |  04.4 $\pm$ 2.80

Foundation Model | Success Rate (%)
---|---
Game of 24 | BabyAI (PN) | TextWorld (CG)
GPT-4 | 100 $\pm$ 00 | 84 $\pm$ 14 | 92 $\pm$ 10
GPT-3.5 |  057 $\pm$ 10 |  0 $\pm$ 0 |  00 $\pm$ 00

What is the Effect of Foundation Model Choice? We also analyze the dependence
of our algorithm on the strength of the foundation model by replacing GPT-4
with an earlier variant, GPT-3.5 in Table 3 (right). There is a considerable
difference between the two, which suggests that our environments are non-
trivial to solve, and that future advancements in foundation models are likely
to readily scale the performance of IGE to even harder problems.

##  6 Related Work

FM-as-judge. We employ FM guidance at all stages of IGE to drive exploration.
FMs as judges [47, 6] have already seen use in decision-making tasks: OMNI
[45] considers FM guidance in multi-task settings to select the most promising
next task to train on. However, focusing on the broader task could miss out on
interesting behavior that happens at a more granular level, and thus IGE
greatly expands on the integration of FM intelligence into decision-making. RL
from AI Feedback [1, 25, 21] considers training RL agents using reward
functions derived from FM preferences. This similarly guides agents towards
preferred states, but without the intelligence of FMs for action selection.

FM Agents. One of the key strengths of IGE is that it is agnostic to the
precise agent formulation and thus strictly additive on top of a wide variety
of strategies. A common strategy is chain-of-thought-based methods [44, 17],
which prompts the FM to output a set of reasoning steps before the answer. We
integrate this into the FM guidance in our experiments in Sections 4.2 and
4.3. Reflexion [34] enables an agent to improve over multiple episodes by
asking it to reflect on the previous attempted episode, and learn from its
mistakes. However, we show this can break down in tasks with long horizons,
whilst IGE proposes a more efficient way to filter out the vast majority of
uninteresting interactions. Another set of agent frameworks that are related
to the idea of exploring diverse solution paths via state-connectivity is Tree
of Thoughts [43] and Graph of Thoughts [3]. In contrast, IGE can exploit
search strategies that are not tied to any connectivity between states and can
readily jump across the archive of promising saved states. This is
particularly important for long-horizon tasks with larger state spaces, as we
show in Sections 4.2 and 4.3.

Closely related to exploration, FM agents have also begun to see use in
search-based tasks. Stream of Search [16] considers a similar mathematical
reasoning task to the Game of 24, and seeks to initially clone the actions of
graph search algorithms, then use RL to self-improve. In contrast, IGE already
greatly outperforms classic graph search—an exciting future direction could be
to first clone the exploratory behavior of Go-Explore and then self-improve
with RL, enabling the FM to learn to select better. Lehnert et al. [26]
analogously train a language model to mimic the A∗ algorithm. Finally,
Krishnamurthy et al. [22] also consider bootstrapping exploration with an
externally summarized action-history in bandit problems; our focus is more on
the detection of interesting states.

Go-Explore. The original Go-Explore [13, 14] framework enabled superhuman
performance in a variety of hard-exploration problems, including applications
as diverse as automated game testing [29]. Gallouédec and Dellandréa [15]
propose Latent Go-Explore which similarly aims to address the difficulty of
designing exploration heuristics by automatically learning a latent
representation and sampling states with a low latent density. However, this
requires periodic retraining and could easily miss out on rare serendipitous
discoveries. HuGE [38] guides Go-Explore with humans in the loop by asking for
pair-wise feedback on which goal to select. On the other hand, we take humans
out entirely and apply intelligent FM guidance at all components of Go-
Explore.

##  7 Conclusion and Limitations

In this paper, we demonstrate a new approach to robust exploration in complex
environments, Intelligent Go-Explore, reimagining Go-Explore in the era of
giant foundation models. We show that IGE can drive exploration for a diverse
set of FM agents, including few-shot and chain-of-thought prompting, across a
variety of challenging text-based games. While we only evaluate IGE on
simulated text-based environments in this paper, a particularly exciting
direction for future work would be domains with multimodal search spaces. This
could unlock applications as wide as scientific discovery in synthetic biology
(designing novel drugs or proteins) or material science. IGE could be readily
adapted to these areas, as there is already precedent for multimodal FMs as
judges [42]. A further direction that could break the limits of the current
state-of-the-art in autonomous decision-making is the (hitherto unsolved by
intelligent agents) dungeon crawler, NetHack [23]. NetHack requires the
discovery of complex strategies, deep game knowledge, and coherent behavior
over an extremely long horizon. Küttler et al. [23] noted that for NetHack,
classic Go-Explore’s “heuristic of downsampling images of states to measure
their similarity to be used as an exploration bonus will likely not work for
large symbolic and procedurally generated environments.” IGE represents a
sharp departure from these limitations, by replacing hard-coded and inflexible
exploration heuristics with the dynamic intelligence of giant foundation
models.

There remain exciting opportunities to improve IGE’s capabilities to explore
vast state spaces. For example, we currently recall and compare against the
entire archive whenever we discover a new state. This could be made much more
efficient by using techniques like retrieval augmented generation [27] and
only comparing to the closest previously discovered states. As we consider IGE
for real-world settings, we should take steps to ensure the responsible
deployment of FMs [5]. Our approach opens up the road to safe and
interpretable exploration: through careful prompt engineering or techniques
like constitutional AI [1], we could steer the agent away from unsafe
behaviors. Furthermore, if we ask or train the FM to explain its choices in
each part of IGE, we could gain insight into its rationale for exploring
particular paths through an environment [41, 17]; improving safety,
interpretability, and perhaps one day even our own understanding of how best
to explore.

## Acknowledgments and Disclosure of Funding

This work was supported by the Vector Institute, the Canada CIFAR AI Chairs
program, grants from Schmidt Futures and Open Philanthropy, an NSERC Discovery
Grant, the Center for AI Safety Compute Cluster, and a generous donation from
Rafael Cosman. We thank Aaron Dharna, Ben Norman, and Jenny Zhang from our lab
at the University of British Columbia for insightful discussions for
insightful discussions and/or feedback on early drafts of this work. Any
opinions, findings, and conclusions or recommendations expressed in this
material are those of the author(s) and do not necessarily reflect the views
of the sponsors.

## References

  * Bai et al. [2022] Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Carol Chen, Catherine Olsson, Christopher Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran-Johnson, Ethan Perez, Jamie Kerr, Jared Mueller, Jeffrey Ladish, Joshua Landau, Kamal Ndousse, Kamile Lukosuite, Liane Lovitt, Michael Sellitto, Nelson Elhage, Nicholas Schiefer, Noemi Mercado, Nova DasSarma, Robert Lasenby, Robin Larson, Sam Ringer, Scott Johnston, Shauna Kravec, Sheer El Showk, Stanislav Fort, Tamera Lanham, Timothy Telleen-Lawton, Tom Conerly, Tom Henighan, Tristan Hume, Samuel R. Bowman, Zac Hatfield-Dodds, Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, and Jared Kaplan.  Constitutional ai: Harmlessness from ai feedback, 2022.
  * Bellemare et al. [2013] M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling.  The arcade learning environment: An evaluation platform for general agents.  _Journal of Artificial Intelligence Research_ , 47:253–279, June 2013.  ISSN 1076-9757.  doi: 10.1613/jair.3912.  URL http://dx.doi.org/10.1613/jair.3912.
  * Besta et al. [2024a] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler.  Graph of thoughts: Solving elaborate problems with large language models.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 38(16):17682–17690, March 2024a.  ISSN 2159-5399.  doi: 10.1609/aaai.v38i16.29720.  URL http://dx.doi.org/10.1609/aaai.v38i16.29720.
  * Besta et al. [2024b] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al.  Graph of thoughts: Solving elaborate problems with large language models.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2024b.
  * Bommasani et al. [2021] Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, S. Buch, Dallas Card, Rodrigo Castellon, Niladri S. Chatterji, Annie S. Chen, Kathleen A. Creel, Jared Davis, Dora Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren E. Gillespie, Karan Goel, Noah D. Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas F. Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, O. Khattab, Pang Wei Koh, Mark S. Krass, Ranjay Krishna, Rohith Kuditipudi, Ananya Kumar, Faisal Ladhak, Mina Lee, Tony Lee, Jure Leskovec, Isabelle Levent, Xiang Lisa Li, Xuechen Li, Tengyu Ma, Ali Malik, Christopher D. Manning, Suvir P. Mirchandani, Eric Mitchell, Zanele Munyikwa, Suraj Nair, Avanika Narayan, Deepak Narayanan, Benjamin Newman, Allen Nie, Juan Carlos Niebles, Hamed Nilforoshan, J. F. Nyarko, Giray Ogut, Laurel Orr, Isabel Papadimitriou, Joon Sung Park, Chris Piech, Eva Portelance, Christopher Potts, Aditi Raghunathan, Robert Reich, Hongyu Ren, Frieda Rong, Yusuf H. Roohani, Camilo Ruiz, Jack Ryan, Christopher R’e, Dorsa Sadigh, Shiori Sagawa, Keshav Santhanam, Andy Shih, Krishna Parasuram Srinivasan, Alex Tamkin, Rohan Taori, Armin W. Thomas, Florian Tramèr, Rose E. Wang, William Wang, Bohan Wu, Jiajun Wu, Yuhuai Wu, Sang Michael Xie, Michihiro Yasunaga, Jiaxuan You, Matei A. Zaharia, Michael Zhang, Tianyi Zhang, Xikun Zhang, Yuhui Zhang, Lucia Zheng, Kaitlyn Zhou, and Percy Liang.  On the opportunities and risks of foundation models.  _ArXiv_ , 2021.  URL https://crfm.stanford.edu/assets/report.pdf.
  * Bradley et al. [2023] Herbie Bradley, Andrew Dai, Hannah Teufel, Jenny Zhang, Koen Oostermeijer, Marco Bellagente, Jeff Clune, Kenneth Stanley, Grégory Schott, and Joel Lehman.  Quality-diversity through ai feedback, 2023.
  * Brown et al. [2020] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners, 2020.
  * Carta et al. [2023] Thomas Carta, Clément Romac, Thomas Wolf, Sylvain Lamprier, Olivier Sigaud, and Pierre-Yves Oudeyer.  Grounding large language models in interactive environments with online reinforcement learning.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 3676–3713. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/carta23a.html.
  * Chang et al. [2024] Yupeng Chang, Xu Wang, Jindong Wang, Yuan Wu, Linyi Yang, Kaijie Zhu, Hao Chen, Xiaoyuan Yi, Cunxiang Wang, Yidong Wang, et al.  A survey on evaluation of large language models.  _ACM Transactions on Intelligent Systems and Technology_ , 15(3):1–45, 2024.
  * Cooper [2014] Seth Cooper.  _A framework for scientific discovery through video games_.  Morgan & Claypool, 2014.
  * Côté et al. [2018] Marc-Alexandre Côté, Ákos Kádár, Xingdi Yuan, Ben Kybartas, Tavian Barnes, Emery Fine, James Moore, Ruo Yu Tao, Matthew Hausknecht, Layla El Asri, Mahmoud Adada, Wendy Tay, and Adam Trischler.  Textworld: A learning environment for text-based games.  _CoRR_ , abs/1806.11532, 2018.
  * Dong et al. [2022] Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, and Zhifang Sui.  A survey on in-context learning.  _arXiv preprint arXiv:2301.00234_ , 2022.
  * Ecoffet et al. [2021a] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth Stanley, and Jeff Clune.  First return, then explore.  _Nature_ , 590:580–586, 02 2021a.  doi: 10.1038/s41586-020-03157-9.
  * Ecoffet et al. [2021b] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, and Jeff Clune.  Go-explore: a new approach for hard-exploration problems, 2021b.
  * Gallouédec and Dellandréa [2023] Quentin Gallouédec and Emmanuel Dellandréa.  Cell-free latent go-explore, 2023.
  * Gandhi et al. [2024] Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D. Goodman.  Stream of search (sos): Learning to search in language, 2024.
  * Hu and Clune [2024] Shengran Hu and Jeff Clune.  Thought Cloning: Learning to think while acting by imitating human thinking.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Huang et al. [2022] Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch.  Language models as zero-shot planners: Extracting actionable knowledge for embodied agents, 2022.
  * Hussein et al. [2017] Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne.  Imitation learning: A survey of learning methods.  _ACM Comput. Surv._ , 50(2), apr 2017.  ISSN 0360-0300.  doi: 10.1145/3054912.  URL https://doi.org/10.1145/3054912.
  * Jiang et al. [2023] Minqi Jiang, Tim Rocktäschel, and Edward Grefenstette.  General intelligence requires rethinking exploration.  _Royal Society Open Science_ , 10(6):230539, 2023.
  * Klissarov et al. [2023] Martin Klissarov, Pierluca D’Oro, Shagun Sodhani, Roberta Raileanu, Pierre-Luc Bacon, Pascal Vincent, Amy Zhang, and Mikael Henaff.  Motif: Intrinsic motivation from artificial intelligence feedback, 2023.
  * Krishnamurthy et al. [2024] Akshay Krishnamurthy, Keegan Harris, Dylan J. Foster, Cyril Zhang, and Aleksandrs Slivkins.  Can large language models explore in-context?, 2024.
  * Küttler et al. [2020] 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.
  * Ladosz et al. [2022] Pawel Ladosz, Lilian Weng, Minwoo Kim, and Hyondong Oh.  Exploration in deep reinforcement learning: A survey.  _Information Fusion_ , 85:1–22, 2022.
  * Lee et al. [2024] Harrison Lee, Samrat Phatale, Hassan Mansoor, Kellie Ren Lu, Thomas Mesnard, Johan Ferret, Colton Bishop, Ethan Hall, Victor Carbune, and Abhinav Rastogi.  RLAIF: Scaling reinforcement learning from human feedback with AI feedback, 2024.  URL https://openreview.net/forum?id=AAxIs3D2ZZ.
  * Lehnert et al. [2024] Lucas Lehnert, Sainbayar Sukhbaatar, DiJia Su, Qinqing Zheng, Paul Mcvay, Michael Rabbat, and Yuandong Tian.  Beyond a*: Better planning with transformers via search dynamics bootstrapping, 2024.
  * Lewis et al. [2020] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 9459–9474. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/6b493230205f780e1bc26945df7481e5-Paper.pdf.
  * Liu et al. [2023] Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang, Shudan Zhang, Xiang Deng, Aohan Zeng, Zhengxiao Du, Chenhui Zhang, Sheng Shen, Tianjun Zhang, Yu Su, Huan Sun, Minlie Huang, Yuxiao Dong, and Jie Tang.  Agentbench: Evaluating llms as agents, 2023.
  * Lu et al. [2024] Cong Lu, Raluca Georgescu, and Johan Verwey.  Go-explore complex 3-d game environments for automated reachability testing.  _IEEE Transactions on Games_ , 16(1):235–240, 2024.  doi: 10.1109/TG.2022.3228401.
  * Madotto et al. [2020] Andrea Madotto, Mahdi Namazifar, Joost Huizinga, Piero Molino, Adrien Ecoffet, Huaixiu Zheng, Alexandros Papangelis, Dian Yu, Chandra Khatri, and Gokhan Tur.  Exploration based language learning for text-based games.  _arXiv preprint arXiv:2001.08868_ , 2020.
  * Olsson et al. [2022] Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al.  In-context learning and induction heads.  _arXiv preprint arXiv:2209.11895_ , 2022.
  * OpenAI [2024] OpenAI.  Gpt-4 technical report, 2024.
  * Parisotto and Salakhutdinov [2018] Emilio Parisotto and Ruslan Salakhutdinov.  Neural map: Structured memory for deep reinforcement learning.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=Bk9zbyZCZ.
  * Shinn et al. [2023] Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao.  Reflexion: Language agents with verbal reinforcement learning, 2023.
  * Sutton and Barto [2018] Richard S. Sutton and Andrew G. Barto.  _Reinforcement Learning: An Introduction_.  The MIT Press, second edition, 2018.  URL http://incompleteideas.net/book/the-book-2nd.html.
  * Talmor et al. [2019] Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant.  CommonsenseQA: A question answering challenge targeting commonsense knowledge.  In Jill Burstein, Christy Doran, and Thamar Solorio, editors, _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4149–4158, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1421.  URL https://aclanthology.org/N19-1421.
  * Team [2024] Gemini Team.  Gemini: A family of highly capable multimodal models, 2024.
  * Torne Villasevil et al. [2023] Marcel Torne Villasevil, Max Balsells I Pamies, Zihan Wang, Samedh Desai, Tao Chen, Pulkit Agrawal, and Abhishek Gupta.  Breadcrumbs to the goal: Goal-conditioned exploration from human-in-the-loop feedback.  In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, _Advances in Neural Information Processing Systems_ , volume 36, pages 63222–63258. Curran Associates, Inc., 2023.  URL https://proceedings.neurips.cc/paper_files/paper/2023/file/c7c7cf10082e454b9662a686ce6f1b6f-Paper-Conference.pdf.
  * Touvron et al. [2023] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023.
  * Wang et al. [2024] Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al.  A survey on large language model based autonomous agents.  _Frontiers of Computer Science_ , 18(6):1–26, 2024.
  * Wei et al. [2022] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in neural information processing systems_ , 35:24824–24837, 2022.
  * Wu et al. [2024] Tianhe Wu, Kede Ma, Jie Liang, Yujiu Yang, and Lei Zhang.  A comprehensive study of multimodal large language models for image quality assessment.  _arXiv preprint arXiv:2403.10854_ , 2024.
  * Yao et al. [2023a] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan.  Tree of Thoughts: Deliberate problem solving with large language models, 2023a.
  * Yao et al. [2023b] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao.  React: Synergizing reasoning and acting in language models.  In _The Eleventh International Conference on Learning Representations_ , 2023b.  URL https://openreview.net/forum?id=WE_vluYUL-X.
  * Zhang et al. [2024] Jenny Zhang, Joel Lehman, Kenneth Stanley, and Jeff Clune.  OMNI: Open-endedness via models of human notions of interestingness.  In _The Twelfth International Conference on Learning Representations_ , 2024.  URL https://openreview.net/forum?id=AgM3MzT99c.
  * Zhao et al. [2021] Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh.  Calibrate before use: Improving few-shot performance of language models.  In _International conference on machine learning_ , pages 12697–12706. PMLR, 2021.
  * Zheng et al. [2023a] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, Hao Zhang, Joseph E Gonzalez, and Ion Stoica.  Judging llm-as-a-judge with mt-bench and chatbot arena.  In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, _Advances in Neural Information Processing Systems_ , volume 36, pages 46595–46623. Curran Associates, Inc., 2023a.  URL https://proceedings.neurips.cc/paper_files/paper/2023/file/91f18a1287b398d378ef22505bf41832-Paper-Datasets_and_Benchmarks.pdf.
  * Zheng et al. [2023b] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica.  Judging llm-as-a-judge with mt-bench and chatbot arena, 2023b.
  * Zhu et al. [2023] Deyao Zhu, Jun Chen, Xiaoqian Shen, Xiang Li, and Mohamed Elhoseiny.  Minigpt-4: Enhancing vision-language understanding with advanced large language models.  _arXiv preprint arXiv:2304.10592_ , 2023.
  * Zoubir and Iskandler [2007] Abdefihak M Zoubir and D Robert Iskandler.  Bootstrap methods and applications.  _IEEE Signal Processing Magazine_ , 24(4):10–19, 2007.

## Supplementary Material

## Table of Contents

[sections] [sections]l1

##  Appendix A Algorithm Pseudocode

We provide full pseudocode for Intelligent Go-Explore in Algorithm 1. This
complements the discussion in Section 3.

Algorithm 1 Intelligent Go-Explore

1:Hyperparameters: no. state expansions $N_{\text{state}}$, no. exploratory
actions $N_{\text{action}}$, foundation model $\mathcal{M}$

2:Initialize: archive of states $\mathcal{S}_{\textrm{archive}}=\emptyset$,
state-conditional action history $\mathcal{A}(\cdot)=\emptyset$

3:$\mathcal{S}_{\textrm{archive}}\leftarrow s_{0}$ $\triangleright$ Add
initial state to archive

4:for $i=1,\dots,N_{\textrm{state}}$ do

5: Query $\mathcal{M}$ for the next state $s_{i,1}$, from
$\mathcal{S}_{\textrm{archive}}$ $\triangleright$ See Section 3.1

6: for $j=1,\dots,N_{\textrm{action}}$ do

7: Query $\mathcal{M}$ for the next action $a_{i,j}$ from $s_{i,j}$
conditional on $\mathcal{A}(s_{i,j})$ $\triangleright$ See Section 3.2

8: $s_{i,j+1}\sim P(s_{i,j},a_{i,j})$, $\mathcal{A}(s_{i,j})\leftarrow
a_{i,j}$ $\triangleright$ Take action and update history

9: if $\mathcal{M}$ determines that $s_{i,j+1}$ is interesting w.r.t
$\mathcal{S}_{\textrm{archive}}$ then $\triangleright$ See Section 3.3

10: $\mathcal{S}_{\textrm{archive}}\leftarrow s_{i,j+1}$

11: end if

12: end for

13:end for

14:Return best discovered trajectory

##  Appendix B Further Details on Environments

We provide further details for each of the environments used in the empirical
evaluation in Section 4, and the environment-specific descriptions appended to
the system prompts. Each environment description may include high-level
information about the task and a description of the action space.

###  B.1 Game of 24

We use the environment and set of evaluation tasks from
https://github.com/princeton-nlp/tree-of-thought-llm which is released under
the MIT License. We include the environment-specific prompt that is appended
to the system prompt in Section 3 below. The system prompt contains examples
of correct reasoning paths on different problems (few-shot prompting).

Environment Description. You are given 4 numbers and must use basic arithmetic
operations (+ - * /) to obtain 24. At each step, you are only allowed to
choose two of the remaining numbers to obtain a new number. A correct answer
is one that uses each input exactly once and no other numbers. Reaching 24
before the last step does not count as a correct answer. Follow the convention
that division is integer division, and never by zero. Some examples of correct
reasoning traces are as follows:
Initial state: (4 4 6 8)
Steps:
4 + 8 = 12. Next: (4 6 12)
6 - 4 = 2. Next: (2 12)
2 * 12 = 24. Next: (24)
Answer: (6 - 4) * (4 + 8) = 24
Initial state: (2 9 10 12)
Steps:
12 * 2 = 24. Next: (9 10 24)
10 - 9 = 1. Next: (1 24)
24 * 1 = 24. Next: (24)
Answer: (12 * 2) * (10 - 9) = 24
Initial state: (4 9 10 13)
Steps:
13 - 10 = 3. Next: (3 4 9)
9 - 3 = 6. Next: (4 6)
4 * 6 = 24. Next: (24)
Answer: 4 * (9 - (13 - 10)) = 24

The action space at each step is all the valid arithmetic operations,
presented in an analogous way as the ‘propose’ step in Yao et al. [43].

###  B.2 BabyAI-Text

The BabyAI-Text [8] environment comes with five task types, which we list here
and visualize in order in Figure 5:

  * •

Go to <object>, a simple navigation task that requires reasoning abilities to
choose the right plan given the object’s position;

  * •

Pick up <object>, a reasoning task that combines navigation tasks;

  * •

Pick up <object A> then go to <object B> and Go to <object B> after pickup
<object A>, both serving to test reasoning abilities on temporal sequences;

  * •

Unlock <door>, a task that includes inferring that a key is needed to unlock
the door, finding the right key (i.e. the one colored as the door), and
eventually using the toggle action with the key on the door;

  * •

Put <object A> next to <object B>, which requires first reaching <object A>,
picking it up, reaching <object B> and finally dropping <object A> next to
<object B>.

Figure 5:  We visualize the 5 types of tasks that BabyAI-Text consists of for
our evaluation in Section 4.2. IGE receives only partial text-based
observations corresponding to the view in the figure.

We use the codebase from
https://github.com/flowersteam/Grounding_LLMs_with_online_RL which is released
under the MIT License. The action space is discrete and composed of 6 possible
actions: turn left, turn right, go forward, pick up, drop, and toggle. The ‘go
to’ and ‘pick up’ tasks have a shorter environment horizon of $H=64$, whereas
the rest have a horizon of $H=128$. We include the environment-specific prompt
that is appended to the system prompt in Section 3 below.

Environment Description. You are an agent in an 8x8 partially-observable 2D
text-based environment. You see the 6x6 grid in front of you, and can face
north, south, east, or west. The possible actions are turn left, turn right,
go forward, pick up, drop, and toggle. At each turn, you will receive a
history of the last observations and actions. Your aim is to complete the task
described in the goal. Each tile in the grid can only contain at most one
object. Objects cannot be crossed, and may need to be bypassed or moved. You
can only move onto an empty tile or on a tile containing an open door. You can
only hold one object at a time, using pick up when they are one step in front.
Objects are dropped one tile in front and cannot be dropped when there is
another object in front. Doors are unlocked with keys of the same color using
the toggle action. Actions are deterministic, do not repeat actions if they
have no effect. You have H steps to complete the task.

###  B.3 TextWorld

We evaluate IGE on ‘Treasure Hunter’, ‘The Cooking Game’, and ‘Coin Collector’
from the TextWorld [11] domain. We use the environment code from
https://github.com/microsoft/TextWorld which is released under the MIT
License.

####  B.3.1 Treasure Hunter

For Treasure Hunter, we set the ‘level’ option to the maximum value of 30,
resulting in a maze with 20 rooms. Locked doors and containers are added,
which may need to be unlocked and opened to find the target object. To further
increase the difficulty, we remove the solution description from the original
game and filter out tasks that can be completed with 20 steps in the optimal
solution. We include the environment-specific prompt that is appended to the
system prompt in Section 3 below.

Environment Description for Treasure Hunter. You are an agent playing
TextWorld, a text-based adventure game where you are in a randomly generated
maze and must find a specific object. You need to explore different rooms to
find the target object. Here are the available commands: look: describe the
current room. goal: print the goal of this game inventory: print the player’s
inventory go <dir>: move the player north, east, south, or west. You can only
go in the direction indicated with an exit or a door. open …: open a door or a
container. You need to open a closed door before you want to go through it.
drop …: drop an object on the floor take …: take an object that is visible.
Make sure the object is visible to take. put … on …: place an object on a
supporter take … from …: take an object from a container or a supporter insert
… into …: place an object into a container unlock … with …: unlock a door or a
container with a key. You need to unlock a locked door with a matched key in
your inventory before you want to open it. \- The target object might be
located in a closed or locked container. \- The adjective is useful for
determining whether the key is matched with the lock (e.g. non-euclidean
keycard is matched with non-euclidean safe). Make sure it is matched to
unlock! \- The key required to unlock the door may be in another room or
locked inside a container. \- Take the key whenever you can. \- After
unlocking a locked door or container, it will remain closed. You will then
need to open it. You have 40 steps to complete the task. Restarting is
forbidden.

####  B.3.2 The Cooking Game

In The Cooking Game, we set the number of ingredients to a maximum of 5 and
the number of rooms to 13. We enable all challenging additional options: doors
need to be opened, food must be processed (e.g., cut, diced, chopped with a
knife), and cooked (e.g., grilled with a BBQ, fried on a stove, roasted in an
oven). We include the environment-specific prompt that is appended to the
system prompt in Section 3 below.

Environment Description for The Cooking Game. You are an agent playing
TextWorld, a text-based adventure game where you navigate through different
rooms, interact with objects, and solve puzzles. Your goal is to first find
the recipe, find and prepare food according to the recipe, and finally prepare
and eat the meal. Here are the available commands: look: describe the current
room goal: print the goal of this game inventory: print player’s inventory go
<dir>: move the player north, east, south or west. You can only go to
directions indicated with an exit or a door. examine …: examine something more
closely eat …: eat edible food open …: open a door or a container. You need to
open a closed door before you can go through it. drop …: drop an object onto
the floor take …: take an object that is visible put … on …: place an object
on a supporter take … from …: take an object from a container or a supporter
insert … into …: place an object into a container lock … with …: lock a door
or a container with a key unlock … with …: unlock a door or a container with a
key cook … with …: cook cookable food with something providing heat slice …
with …: slice cuttable food with something sharp chop … with …: chop cuttable
food with something sharp dice … with …: dice cuttable food with something
sharp prepare meal: combine ingredients from inventory into a meal. You can
only prepare meals in the Kitchen. \- You can examine the cookbook to see the
recipe when it is visible. \- The BBQ is for grilling things, the stove is for
frying things, the oven is for roasting things. Cooking ingredients in the
wrong way will lead to a failure of the game. \- Once you have got processed
ingredients and the appropriate cooking tool ready, cook all of them according
to the recipe. \- There are two conditions to correctly cook something
(grill/fry/roast): a) the ingredient you want to cook is in your inventory and
b) there is a suitable cooking tool in the room, and then use ‘cook … with …’
command. \- When you need to chop/slice/dice ingredients, you need to take the
knife and the ingredient in your inventory and then ‘slice/chop/dice … with
knife’ \- Make sure to first process the food (chop/slice/dice) before you try
to cook them. \- When you have all the ingredients (that got processed or
cooked according to the menu), you can ‘prepare meal’ in the kitchen and then
‘eat meal’ to win the game. \- The ingredients should EXACTLY match the color
in the recipe, but if the recipe doesn’t specify color, any color would be
fine. When you ‘take … with …’, use the EXACT name you see. \- You don’t need
to examine the container/supporter (e.g. toolbox) when it says something like
"there isn’t a thing on it"/"has nothing on it" You have 80 steps to complete
the task. Restarting is forbidden.

We show a successful example trajectory found by IGE below, from our
evaluation in Section 4.3.

Example trajectory found by IGE in The Cooking Game. You are hungry! Let’s
cook a delicious meal. Check the cookbook in the kitchen for the recipe. Once
done, enjoy your meal! -= Backyard =- You find yourself in a backyard. A
normal kind of place. You can see a patio table. But oh no! there’s nothing on
this piece of garbage. This always happens! You make out a patio chair. But oh
no! there’s nothing on this piece of trash. You can make out a BBQ, so there’s
that. There is a closed barn door leading north. There is a closed sliding
patio door leading west. There is an exit to the east. Don’t worry, there is
no door. > open sliding patio door You open sliding patio door. > go west -=
Kitchen =- You find yourself in a kitchen. An ordinary kind of place. The room
is well lit. You can make out a fridge. You hear a noise behind you and spin
around, but you can’t see anything other than an oven. Were you looking for a
table? Because look over there, it’s a table. On the table you see a cookbook.
You can’t wait to tell the folks at home about this! Look out! It’s a- oh,
never mind, it’s just a counter. Now why would someone leave that there? You
see a red apple, a raw purple potato, a red onion, a yellow apple and a knife
on the counter. You can see a stove. You shudder, but continue examining the
stove. Unfortunately, there isn’t a thing on it. Hm. Oh well There is an open
sliding patio door leading east. There is a closed plain door leading north.
You don’t like doors? Why not try going west, that entranceway is not blocked
by one. > examine cookbook You open the copy of "Cooking: A Modern Approach
(3rd Ed.)" and start reading: Recipe #1 ——— Gather all following ingredients
and follow the directions to prepare this tasty meal. Ingredients: block of
cheese carrot orange bell pepper red apple tomato Directions: chop the block
of cheese fry the block of cheese dice the carrot grill the carrot chop the
orange bell pepper fry the orange bell pepper chop the red apple grill the red
apple slice the tomato grill the tomato prepare meal > take red apple You take
the red apple from the counter. Your score has just gone up by one point. >
open fridge You open the fridge, revealing a block of cheese, a carrot, a
white onion and a yellow bell pepper. > take block of cheese You take the
block of cheese from the fridge. Your score has just gone up by one point. >
take carrot You take the carrot from the fridge. Your score has just gone up
by one point. > examine counter The counter is solid. On the counter are a raw
purple potato, a red onion, a yellow apple and a knife. > go west -=
Livingroom =- You arrive in a livingroom… … (skip 30 steps) > cook tomato with
BBQ You grilled the tomato. Your score has just gone up by one point. > go
west -= Kitchen =- You find yourself in a kitchen… > prepare meal Adding the
meal to your inventory. Your score has just gone up by one point. > eat meal
You eat the meal. Not bad. Your score has just gone up by one point. *** The
End *** You scored 17 out of a possible 17, in 44 turns.

####  B.3.3 Coin Collector

In Coin Collector, we set the number of rooms to 40 and allow distractor rooms
to be added along the way. Similar to Treasure Hunter, we remove the solution
description from the original game, and the optimal path from the agent’s
starting point to the target is set to 20 steps. We include the environment-
specific prompt that is appended to the system prompt in Section 3 below.

Environment Description for Coin Collector. You are an agent playing
TextWorld, a text-based adventure game where you are in a randomly generated
maze and must find the coin. You need to explore different rooms to find the
target object. Here are the available commands: goal: print the goal of this
game go <dir>: move the player north, east, south, or west. You can only go in
the direction indicated with something like an exit or a door. take coin: 2in
the game by ‘take coin’ if you see the coin in the room The only action you
can do is go <dir> to explore the maze and ‘take coin’ when you see the coin
in the room. You have 25 steps to complete the task. Restarting is forbidden.

##  Appendix C Further Prompt Discussion

###  C.1 Extracting Choices

By default, in Section 4.1, we prompt the FM to return a JSON object
containing just the numerical index of the choice. We choose this because of
the ease of parsing the response and validating it lies within the correct
bounds. An example prompt is displayed below.

JSON Choice Prompt. Reply concisely and exactly with the following JSON
format:
{“choice”: X}
where X is the index of the desired choice.

When using chain-of-thought as in Section 4.2, we use the following prompt:

JSON Choice Prompt (Chain of Thought). First, briefly reason about your plan.
Reply concisely and exactly with the following JSON format:
{“thought”: X, “choice”: Y}
where X is your reasoning and Y is the index of the desired choice. Make sure
Y is a parsable integer.

For the TextWorld environment in Section 4.3, since the action space is much
larger, we ask the FM to directly output a text action that we automatically
parse.

Decision Making Prompt. Please briefly reason about your plan and then output
the command in the format ‘> command’. Ensure only one command is included.

We use the regex “> (.*?)(?:|̇$)” (in Perl notation) to parse the command. We
note that the failure rate for both of these options is very low, less than
0.1% across our evaluation. Despite this, we include a failsafe that returns a
random choice in case of an invalid output.

###  C.2 Rejection-based Archive Filtering

The ‘acceptance-based’ archive filter in Section 3.3 iterates through every
new state and asks whether each one is interestingly new and should be added
to the archive. This can break down in larger environments where there is more
need to explicitly deprecate earlier discoveries that have become irrelevant
to not overload the archive, for example, in Section 4.3. In this environment,
we use an alternate version of the prompt which first adds all states, and
then asks the foundation model to remove the uninteresting states. An example
prompt is shown below.

Rejection-based Archive Filtering Prompt. Current state archive:
[State Archive]
Remove outdated states that are no longer relevant to the task, have had all
interesting explorations attempted, or have similar states in the archive that
show more progress.

##  Appendix D Hyperparameters

In this section, we provide the hyperparameters for our empirical evaluation
in Section 4. We list the hyperparameters for IGE in Table 4. We choose the
values for exploratory rollout length based on the average number of steps
needed to make ‘reasonable progress’ in the environment.

Table 4: IGE Sampling Parameters. TH, TCG, and CC are abbreviations for Treasure Hunter, The Cooking Game, and Coin Collector in TextWorld. Hyperparameter | Value(s)
---|---
Game of 24 | BabyAI-Text | TH | TCG | CC
No. state expansions, $N_{\text{state}}$ | 50 | 25 | 24 | 48 | 125
No. exploratory actions, $N_{\text{action}}$ | 3 | 10 | 5 | 5 | 1

We list the sampling parameters for GPT-4 [32] passed via the OpenAI API in
Table 5.

Table 5: GPT-4 Sampling Parameters Hyperparameter |  Value
---|---
Game of 24 |  BabyAI-Text |  TextWorld
Temperature |  0.7 |  0.7 |  0.3
Max new tokens |  1000 |  1000 |  1000
Response format |  JSON Object |  JSON Object |  Text
Version |  Turbo-2024-04-09 |  o-2024-05-13 |  o-2024-05-13

We used GPT-4-Turbo for Game of 24 and GPT-4o for BabyAI and TextWorld. This
was purely done to select the version of GPT-4 that was available and the
cheapest at the time of running the experiments. The version of GPT-4 is
consistent per environment. We use a reduced temperature for the TextWorld
domain to reduce the possibility of generating malformed responses, as actions
are output in free-form natural language. In our ablations in Section 5, we
use the ‘turbo-0125’ variant of GPT-3.5.

###  D.1 Cost of Experiments

We provide the average cost per task for our algorithm per environment (the
number of seeds is specified in Section 4):

Table 6: Per task API cost for IGE using GPT-4 listed in USD. Environment |  API Cost (USD)
---|---
Game of 24 |  1.04
BabyAI-Text |  2.01
TextWorld |  1.28

We note that the price per token of the ‘o-2024-05-13’ option is half that of
‘Turbo-2024-04-09’, so we could expect to achieve the same level of results on
the Game of 24 with half the price. The total cost of API access required to
perform the final experiments in this paper was under 2,000 USD. During
development, we iterated on IGE with a smaller number of seeds, which
represents a small fraction of this cost added on top.