# STARLING: Self-supervised Training of Text-based Reinforcement Learning
Agent with Large Language Models

Shreyas Basavatia
Georgia Institute of Technology
<EMAIL_ADDRESS>
&Keerthiram Murugesan11footnotemark: 1
IBM Research
<EMAIL_ADDRESS>
&Shivam Ratnakar11footnotemark: 1
IBM Consulting
<EMAIL_ADDRESS>Equal ContributionsWork done while SB was
a high school student at Pelham Memorial High School. Code and data can be
found at https://github.com/IBM/starling-agent.

###### Abstract

Interactive fiction games have emerged as an important application to improve
the generalization capabilities of language-based reinforcement learning (RL)
agents. Existing environments for interactive fiction games are domain-
specific or time-consuming to generate and do not train the RL agents to
master a specific set of skills. In this work, we introduce an interactive
environment for self-supervised RL, STARLING, for text-based games that
bootstraps the text-based RL agents with automatically generated games (based
on the seed set of game ideas) to boost the performance and generalization
capabilities to reach a goal of the target environment. These games let the
agent hone their skills on a predefined set of tasks. We create and test an
environment with $100$ games, generated using this automated framework that
uses large language models (GPT3) and an interactive fiction game engine
(based on Inform7) to provide the user with the ability to generate more games
under minimal human supervision. Experimental results based on both the human
participants and baseline text-based RL agents reveal that current state-of-
the-art text-based RL agents cannot use previously learned skills in new
situations at the level humans can. These results enforce STARLING’s potential
to serve as a sandbox environment for further research in self-supervised
text-based RL.

STARLING: Self-supervised Training of Text-based Reinforcement Learning Agent
with Large Language Models

Shreyas Basavatia††thanks: Equal Contributions††thanks: Work done while SB was
a high school student at Pelham Memorial High School. Code and data can be
found at https://github.com/IBM/starling-agent. Georgia Institute of
Technology<EMAIL_ADDRESS>Keerthiram Murugesan11footnotemark: 1 IBM
Research<EMAIL_ADDRESS>Shivam Ratnakar11footnotemark: 1 IBM
Consulting<EMAIL_ADDRESS>

##  1 Introduction

Figure 1: Architecture diagram for Self-supervised Text-based Reinforcement
Learning using LLM (STARLING).

Interactive fiction games such as Zork can be utilized as an important test-
bed to improve the generalization capabilities of text-based reinforcement
learning (TBRL) agents Hausknecht et al. (2020); Jansen (2022). In these
games, both the observed state of the game and the actions taken are in
natural language. To play these games, the agents (or human players) need to
understand the observed text from the environment and take relevant action
toward the goal. These games encourage agents to understand the underlying
state of the game and take actions to interact with the environment. In order
to be successful, agents must use previously learned skills in new situations
to complete an overarching goal. Current environments of interactive fiction
games suffer from two major problems. First, environments such as TextWorld
Commonsense measure simple commonsense reasoning based on one-hop
relationships between entities (e.g., apple $\rightarrow$ refrigerator)
Murugesan et al. (2021a) but lack game complexity (besides a fewer number of
games) to learn skills and generalize to novel domains. Second, environments
such as ScienceWorld (even though many variations of task-based games are
available) and Jericho are domain-specific so agents that play these
environments may perform well while conducting specific tasks like completing
science experiments but lack generalized skills to apply them to other
situations Wang et al. (2022); Hausknecht et al. (2020). Most importantly, in
order to generate a large number of games to train the RL agents to master
skills in these environments, we will have to employ human annotators to
manually design, generate, and deploy the game. Therefore, the purpose of this
work is to develop an efficient approach that generates a large amount of
text-based games to train the RL agents to master the desired skills and excel
at the target environments such as TWC, ScienceWorld, etc.

As developing a set of text-based games is a time-intensive manual process, we
propose Self-supervised Text-bAsed RL learnING, "STARLING", an interactive
environment that utilizes Large Language Models (LLM) and an integrated
interactive fiction game engine (Inform7 Nelson (2006)) to easily produce
games in any domain. We generate a set of $100$ text-based games using GPT3
Brown et al. (2020) based on the input game ideas (seed list) that emphasize
the need for the everyday skills such as boiling water, cooking pasta, etc. in
(pre-)training text-based RL agents. These games require agents to use a
specific sequence of actions to achieve the goal and successfully complete the
game. For example, while cooking pasta, an agent must first gather the
ingredients, fill pot with water, boil the water, and put the pasta in the
pot. We then deploy the pre-trained RL agent on the target environments. This
novel game-generation method can easily be used by others to create their own
games and be adapted for future applications to build challenging RL agents in
various domains. Figure 1 shows the overview of the proposed approach for
self-supervised text-based reinforcement learning using LLM.

##  2 Self-supervised Text-based RL

Self-supervised RL involves bootstrapping RL agents with auxiliary tasks in an
unsupervised or semi-supervised setting to accelerate learning and generalize
in the target tasks. With the recent interest in LLMs, in this paper, we
consider LLMs as an alternative option to pre-train an RL agent with minimal
human supervision. Unlike in the other text-based environments such as
TextWorld Côté et al. (2019), TextWorld Commonsense (TWC) Murugesan et al.
(2021a), Jericho Hausknecht et al. (2020), ScienceWorld Wang et al. (2022), we
utilize the skill generation capability of the large language models Huang et
al. (2022) to automatically generate text-based games based on the input game
ideas with minimal human supervision.Our proposed approach for self-supervised
TBRL, STARLING is an interactive text-based environment with assistance from
LLM and enables the text-based RL agent to hone their extra-curricular skills
111In this work, we define the skills based on the auxiliary task such as
”boil $<$object$>$”, ”fill $<$container$>$”, ”cook $<$object$>$”, etc. We
assume that LLM such as GPT3 has the necessary knowledge to generate text-
based games based on these basic skills.. In this paper, we assume a seed list
of game ideas is already available as input to STARLING. These game ideas are
chosen to exhibit specific skills either for creating a generalized agent or
targeting domain-specific environments. Optionally, the RL agent can generate
a new set of game ideas during training, specific to the target domain to
improve its performance.

###  2.1 Constructing Pre-training Games

Figure 2: Workflow of the STARLING Game Generator using large language model
(GPT3).  Figure 3: (A) GPT3 input prompt for cooking games with one action
example. The actual prompt contains four action examples. (B) GPT3 output for
cooking pasta game idea. GPT3 reliably outputs accurate and necessary game
information very similar to the input.

In this section, we briefly describe how we generate the pre-training games
from the game ideas using LLM and Inform7. Given the set of game ideas (seed)
to LLM Brown et al. (2020), we design a method that procedurally generates
text-based games based on the interactive fiction game engine. In this paper,
we use GPT3 as our LLM. Inform7 is an interactive fiction programming language
that allows users to create interactive fiction games using natural language
instructions Nelson (2006). Previous text-based environments such as
TextWorld, Jericho, ScienceWorld, etc. use Inform7 (in the backend) to
generate a handful of text-based games manually that require agents to explore
the environment and take a sequence of actions to complete a goal such as
cooking a pasta. Based on our observation from these environments, we find
that the game generation can be modularized into four parts: setup, object
creation, custom action, and reward assignment:

  1. 1.

Setup \- defines basic properties about the game such as the room, entity
types, any external libraries (Inform7), etc.

  2. 2.

Object Creation \- creates in-game entities such as bread or jelly. Each
entity is placed in its proper location like the refrigerator or cabinet and
assigned properties such as portable, open, or closed.

  3. 3.

Custom actions \- defines actions not native to Inform7. Each custom action
checks for the pre-conditions and then executes the action by initiating the
relevant state changes, and returning the proper observations to the agent. We
utilize predefined action templates to incorporate custom actions during the
game generation.

  4. 4.

Rewards - assigns reward value for gathering the necessary entities and
completing custom actions to achieve the goal. Once all the rewards are
collected for each game, the game ends.

Figure 4: Training curves for pre-training step of STARLING depicting the
normalized scores (left) and number of moves taken (right) of text-based
reinforcement learning agents.

Figure 2 shows the overview of the game generation using STARLING. When we
feed a game idea from the seed list, STARLING prepares a prompt using natural
language instruction and example game metadata as shown in Figure 3(a), with
information about the setup, objects, custom actions, and rewards required for
the game idea. We input this prompt to an LLM which generates the requested
information as shown in Figure 3(b). We initiate each prompt for a game idea
with the necessary objects that the agent needs and agents must collect those
objects and use them to cook, clean, build, or complete the high-level task.
In order to be successful in these games, agents must understand the
properties, location, and affordances of objects in addition to the specific
sequence of actions needed to accomplish the task.

Next, we write the output from the GPT3 output into a JSON file as shown in
Figure 13 (supplementary). The objects, actions, and tasks from the GPT3
output correspond to the entities, custom actions, and verbs sections of the
JSON file respectively. At this stage, the user may update or change game
information in the JSON file. If the user approves the game-related data in
the JSON file, we write the Inform7 code based on the JSON file. We then
convert this code into an Inform7 game for a given game idea using the Glulx
222https://en.wikipedia.org/wiki/Glulx interpreter for interactive fiction
games.

###  2.2 Parsing LLM Response

Since the response generated by LLM may not strictly follow the desired
format, we follow additional steps to mitigate the irrelevant content in the
response from LLM. First, we request a specific set of game-related data from
LLM in a slot-filling style text generation to reduce the amount of long
unstructured text generation Rakotonirina et al. (2022). Since LLM are good at
instruction-following when few-shot examples (input-output pairs) of a similar
problem are given as a part of the prompt input, we add k-shot examples (k=3)
to guide the LLM to generate a response. Figure 3(a) shows one of the three
examples given as a part of the input prompt. Finally, during game
compilation, the Glulx interpreter verifies whether the information extracted
from the response adheres to the Inform7 programming language syntax. In
addition, the pipeline for game generation provides an option for users to
review the generated JSON file. When the generated game files still contain
irrelevant content, we repeat the text generation multiple times to get the
desired response from LLM.

###  2.3 Game Insights

Using the above approach repeatedly, we built a set of $100$ games with
minimal human supervision for training and evaluating the text-based RL agents
with skills. These games have on average $2$ skills and $4$ rewarded states
per game. These games have multiple sub-tasks which indicate that agents must
utilize at least 2 skills (on average) for each game in the correct order.

Agents | Mean Normalized Score | Mean Moves Taken
---|---|---
Random | 0.050 $\pm$ 0.01 | 50 $\pm$ 0.0
Pre-training | 0.72 $\pm$ 0.063 | 28.105 $\pm$ 1.876
Human | 1.000 $\pm$ 0.000 | 9.640 $\pm$ 5.620

Table 1:  Performance of random and pre-trained agents on a set of 25 unseen
pre-training games after training on 75 pre-training games over 100 episodes.
Mean Norm. Score (higher is better, normalized with maximum score achievable
per game) and Mean Moves Taken (to achieve the goal, lower is better).

Agents must take approximately $7$ actions on average to complete each game,
though some of these actions do not necessarily have to be completed in order
(e.g. the agent can "turn on the stove" before "fill the pot with water" and
vice versa). Games in TWC only require agents to gather objects and take
actions to place them in their commonsense locations. These actions can often
be completed in any order, whereas generated games, such as cooking pasta,
require agents to gather objects and use other related skills in a specific
sequence to achieve the final goal.

##  3 Experiments

In this section, we report the experimental results of the proposed approach:
STARLING. We pre-train the RL agent on the generated $100$ games (train
split). We evaluate the pre-trained agent (STARLING) on three benchmark
environments for text-based games: TextWorld Commonsense (TWC) with easy,
medium, and hard difficulty levels Murugesan et al. (2021a) 2) ScienceWorld
with 4 tasks and variations Wang et al. (2022). 3) Zork1 from Jericho.

Figure 5: Training curves for TWC easy (left), medium (middle), and hard
(right) games depicting the normalized scores (top) and number of moves
(bottom) of both vanilla TBRL and STARLING agents.

Agents | Textworld Commonsense
---|---
| Easy | Medium | Hard
Vanilla TBRL | 0.99 $\pm$ 0.0 | 0.81 $\pm$ 0.06 | 0.57 $\pm$ 0.03
STARLING | 1.0 $\pm$ 0.0 | 0.85 $\pm$ 0.04 | 0.64 $\pm$ 0.05

Table 2: Performance comparison of vanilla TBRL (without pre-training) and
STARLING on the test set with the three difficulty levels of Textworld
Commonsense (TWC). All the scores and moves are averaged over $3$ runs.

###  3.1 Text-based RL Agent

In this section, we briefly describe the text-based agent used for all the
experiments. Based on the recent observation that using LLM to learn the
underlying representation of text in the environment does not necessarily
improve the performance (Wang et al., 2022), we follow previous works He et
al. (2016); Murugesan et al. (2021a); Ammanabrolu and Hausknecht ; Yao et al.
(2020); Atzeni et al. (2022) and use GRU-based Vanilla TBRL agent to evaluate
our proposed approach (Figure 11 supplementary). We use individual GRUs Cho et
al. (2014) for the information from the text-based environment such as
observed text, the content of the inventory, the description of the room where
the agent currently is located, and a valid list of actions. We learn the
state representation by concatenating the individual representations from
their GRUs Cho et al. (2014). We compute the action probability from both the
state and action representations. We use Advantage Action-critic (A2C) to
train the network Mnih et al. (2016). In order to limit the impact of
architecture and text-based RL algorithms, we consider these standard
architectures for representation learning and RL algorithms that have proven
to work well in text-based environments. We plan to study the impacts of
different RL algorithms and diverse sets of representation learning approaches
in our future work. All the results reported in this paper are averaged over
$3$ runs.

###  3.2 Pre-training Text-based RL Agent

Figure 6: (left) Performance of TBRL agents on Zork1. (right) Sample
trajectory from STARLING showing the bonus points of (+4 scores) for
collecting the painting in the art gallery within the first few episodes.

We generate $100$ games that demonstrate basic skills in these environments
such as cooking pasta, painting the living room, boiling water, lighting a
candle, etc. We split these $100$ games into $75$ games for training and $25$
for evaluation. We trained the vanilla TBRL agent on these $75$ pre-training
games over $100$ episodes ($50$ max. steps per episode) and evaluated it on
$25$ held-out games. We compare the performance of the vanilla TBRL agent
(pre-training) against both the random agent (picks random action at each
step) and the Human performance. We use the mean normalized score and mean
moves/steps taken by the agent for comparison. We collect the Human
performance results based on the $48$ participants (Section B). Figure 4 shows
the training performance and Table 1 shows the evaluation results. We can see
that human participants (high-school students) solved these games with a
perfect normalized score of $1.0$ indicating that these games are easy to
solve. In order to successfully finish a game, an agent needs to take certain
actions in a particular order. The order of actions taken decides the future
states of the entities involved in the game.

###  3.3 Self-supervised Training of Text-based RL Agent

Next, we deploy the TBRL agent pre-trained on $75$ games generated by LLM on
different environments. We call the pre-trained TBRL agent STARLING. We expect
that STARLING will outperform the vanilla TBRL agent by utilizing the skills
learned using LLM and boosting the performance and generalization capabilities
to reach the goal of the target environments: ScienceWorld, TWC, and Zork1.

####  3.3.1 TextWorld Commonsense Environment

TextWorld Commonsense environment evaluates the agent on commonsense reasoning
about everyday objects such as toothbrush, dirty towel, etc. The environment,
based on Textworld engine Côté et al. (2019), includes three difficulty
levels: easy, medium, and hard depending on the number of objects to find and
the number of rooms to explore. Each difficulty level includes $5$ training
games and $5$ evaluation games similar to the distribution of the training
games333In addition to the $5$ evaluation games, TWC includes $5$ test games
from out-of-distribution. Since these games require external knowledge such as
ConceptNet Speer et al. (2017), ATOMIC Hwang et al. (2021) etc., we exclude
them from our experiments. for a total of $30$ games with a batch size of $1$
for this experiment. We train the STARLING agent on these $15$ games for 100
episodes with a maximum of $50$ steps.

Figure 5 shows the training curves of the three difficulty levels in the TWC
environment. We can see that the STARLING agent gets a boost in performance
both in the scores achieved and the moves taken compared to the vanilla TBRL.
This shows that the pre-training step using LLM in STARLING leverages the
basic skills mastered using the $75$ generated games. Table 2 confirms our
hypothesis that the pre-training step in STARLING improves the overall
performance across different difficulty levels.

Figure 7: Training curves for ScienceWorld - Boil Substance (Matter), Find a living thing (Classification), Find a non-living thing (Classification), and Grow a fruit (Biology) games depicting the scores (left) and number of moves (right) of text-based reinforcement learning agents.  Theme | Task | Random-Valid* | DRRN* | KG-A2C | CALM | BC* | TDT* | STARLING*
---|---|---|---|---|---|---|---|---
Model Types | – | GRU | GRU | GPT2 | T5 (base) | T5 (base) | GRU
Param. Count $\times 10^{6}$ |  | 1.5 | 5.5 | 131 | 11,000 | 11,000 | 0.2
Matter | Changes of State (Boiling) | 0.00 | 0.03 | 0.00 | 0.00 | 0.00 | 0.00 | 0.04
Matter | Changes of State (Melting) | 0.00 | 0.04 | 0.00 | 0.00 | 0.00 | 0.01 | 0.05
Matter | Changes of State (Freezing) | 0.00 | 0.01 | 0.04 | 0.00 | 0.01 | 0.00 | 0.10
Matter | Changes of State (Any) | 0.00 | 0.03 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00
Measurement | Use Thermometer | 0.00 | 0.10 | 0.06 | 0.01 | 0.04 | 0.04 | 0.19
Measurement | Measuring Boiling Point (known) | 0.00 | 0.08 | 0.11 | 0.01 | 0.01 | 0.02 | 0.11
Measurement | Measuring Boiling Point (unknown) | 0.00 | 0.06 | 0.04 | 0.01 | 0.01 | 0.02 | 0.10
Electricity | Create a circuit | 0.01 | 0.13 | 0.07 | 0.05 | 0.03 | 0.07 | 0.13
Electricity | Renewable vs Non-renewable Energy | 0.01 | 0.10 | 0.04 | 0.07 | 0.02 | 0.05 | 0.11
Electricity | Test Conductivity (known) | 0.01 | 0.07 | 0.04 | 0.02 | 0.05 | 0.05 | 0.09
Electricity | Test Conductivity (unknown) | 0.00 | 0.20 | 0.04 | 0.02 | 0.04 | 0.05 | 0.14
Classification | Find a living thing | 0.03 | 0.26 | 0.18 | 0.10 | 0.29 | 0.16 | 0.25
Classification | Find a non-living thing | 0.63 | 0.56 | 0.44 | 0.54 | 0.19 | 0.17 | 0.94
Classification | Find a plant | 0.01 | 0.19 | 0.16 | 0.10 | 0.17 | 0.19 | 0.25
Classification | Find an animal | 0.01 | 0.19 | 0.15 | 0.08 | 0.21 | 0.19 | 0.25
Biology | Grow a plant | 0.07 | 0.09 | 0.06 | 0.02 | 0.08 | 0.03 | 0.12
Biology | Grow a fruit | 0.02 | 0.16 | 0.11 | 0.04 | 0.03 | 0.05 | 0.09
Chemistry | Mixing (generic) | 0.01 | 0.20 | 0.17 | 0.03 | 0.06 | 0.10 | 0.22
Chemistry | Mixing paints (secondary colours) | 0.01 | 0.29 | 0.19 | 0.06 | 0.16 | 0.20 | 0.30
Chemistry | Mixing paints (tertiary colours) | 0.00 | 0.11 | 0.04 | 0.03 | 0.05 | 0.07 | 0.14
Biology | Identify longest-lived animal | 0.02 | 0.48 | 0.43 | 0.06 | 0.26 | 0.20 | 0.48
Biology | Identify shortest-lived animal | 0.03 | 0.47 | 0.32 | 0.10 | 0.14 | 0.16 | 0.35
Biology | Identify longest-then-shortest-lived animal | 0.01 | 0.31 | 0.23 | 0.04 | 0.02 | 0.20 | 0.31
Biology | Identify life stages (plant) | 0.00 | 0.09 | 0.05 | 0.04 | 0.04 | 0.02 | 0.21
Biology | Identify life stages (animal) | 0.00 | 0.10 | 0.10 | 0.00 | 0.02 | 0.07 | 0.18
Forces | Inclined Planes (determine angle) | 0.01 | 0.13 | 0.04 | 0.00 | 0.05 | 0.04 | 0.12
Forces | Friction (known surfaces) | 0.00 | 0.13 | 0.04 | 0.03 | 0.05 | 0.04 | 0.09
Forces | Friction (unknown surfaces) | 0.01 | 0.13 | 0.04 | 0.02 | 0.04 | 0.04 | 0.27
Biology | Mendelian Genetics (known plants) | 0.01 | 0.19 | 0.11 | 0.02 | 0.06 | 0.06 | 0.18
Biology | Mendelian Genetics (unknown plants) | 0.01 | 0.17 | 0.11 | 0.02 | 0.13 | 0.05 | 0.16
Table 3: Performance comparison of STARLING against other GRU-based and LLM-
based agents on test variations from ScienceWorld. ∗ indicates the reliance on
a valid action list during evaluation.

####  3.3.2 ZORK1 Environment

Zork1 is a human-made interactive fictional game environment and one of the
earliest known text-based games created based on the underworld characters
with dark themes and characters such as dungeon, grue, elvish sword, etc.
Zork1 is one of the 33 interactive games released as a part of the Jericho
game suite. Unlike TWC and ScienceWorld, Zork1 includes a diverse set of
locations (over $200$ locations), larger action space, sparser rewards, and
longer trajectories, making it a challenging environment.

In order to evaluate the effect of pre-training in the Zork1 environment, we
simplified the game with "killing troll" as a final goal Zahavy et al. (2018).
The agent needs to find the lantern and sword from the house, locate the
hidden passageway to the underworld, light the lantern, and kill the troll.
Without the lantern and sword, the agent entering the troll room reaches the
failure state with negative rewards. In addition to these intermediate
rewards, the game includes additional rewards when the agent collects a jewel-
encrusted golden egg from the tall tree in the forest (+5 score) and a
painting from the art gallery in the house (+4 score). We train the agents on
$100$ episodes with a maximum step of $100$ steps per episode.

Figure 6 (left) shows the performance of both the STARLING and vanilla TBRL on
the Zork1 environment. As in TWC, we can see that the pre-training step boosts
the performance of STARLING in the first few episodes compared to the vanilla
TBRL agent. As in ScienceWorld, STARLING successfully avoids the failure state
compared to the vanilla TBRL agent.

####  3.3.3 ScienceWorld Environment

ScienceWorld environment evaluates the science reasoning abilities of the TBRL
agents. It consists of several tasks from topics such as change of state,
biology, classification, etc. We choose all the 30 science-domain tasks from
the themes. Each of these tasks contains $10-1400$ variations of the game and
are split into $50\%$ training, $25\%$ for evaluation set, and $25\%$ for test
set. We train the STARLING agent with $100k$ maximum steps on a single
environment (with a maximum of $100$ steps per game play)444Unlike in the
”number of moves taken” metric in the pre-training results, the number of
moves taken in the ScienceWorld measures how long the agent survived without
reaching the failure state. An agent may reach a failure state if it takes an
action that results in abruptly ending the game such as pouring water on the
floor for the boiling task, etc.

Figure 7 shows the training curves for both the scores received and moves
taken on the 4 tasks. We can see that STARLING outperforms vanilla TBRL on all
the tasks. We notice that the pre-training steps improved the performance of
STARLING in the first few episodes of the classification task (find a living
thing). On the other hand, pre-training games such as boiling water, cooking
pasta, planting a tree, etc. may have influenced the performance of STARLING
in the later episodes of tasks: change of state - boiling and grow a fruit, by
adapting the learned skills during pre-training to the target environment.

Table 3 shows the performance comparison of GRU-based and LLM-based models
against STARLING on the test variations of the ScienceWorld. We compare the
STARLING against the state-of-the-art LLM-based models Behavior cloning (BC),
Text Decision Transformers (TDT), CALM-GPT2, etc Wang et al. (2023a);
Ammanabrolu and Hausknecht ; Yao et al. (2020). We notice that our pretraining
strategy has generally improved the performance of STARLING in the majority of
the tasks. We outperform both GRU-based and LLM-based models. It is worth
noting that both BC and TDT use T5-base (11 billion parameters) initialized
with Macaw, CALM uses GPT2 with 131 million parameters, whereas, GRU-based
STARLING uses approx 200K parameters.

###  3.4 Discussion

Our experiments on three text-based game environments show that pre-training
these agents using LLM-generated games as auxiliary tasks generally boosts the
performance of the agent. We notice that most of the performance gain achieved
in the first few episodes of the gameplay on some game instances (e.g.,
training curves in ScienceWorld tasks find a living thing, TWC Easy, and Hard,
Zork1), whereas, STARLING adapts the basic skills learned during the pre-
training to the target environment to improve the final scores (e.g., training
curves in ScienceWorld tasks: change of state - boiling and grow a fruit). We
notice that STARLING avoids the failure states better than vanilla TBRL as can
be seen in Zork1 and ScienceWorld. Similarly, STARLING tends to choose valid
actions from the action space more effectively than vanilla TBRL (for example,
see Figure 12 supplementary for the sample trajectories from ScienceWorld
taken by vanilla TBRL and STARLING within the first few episodes for the task:
changes of state - boiling).

Since these pre-training games lack navigational complexity that elicits
skills such as planning, we observe that STARLING tends to suffer in games
that require navigational skills (e.g., example, in ScienceWorld task find a
non-living thing, TWC hard difficulty and Zork1). Since the pre-training games
involve fewer sequences of actions (short trajectories) to collect the reward
and reach the final goal, STARLING struggles when the target environment has
longer trajectories to reach the goal. On the other hand, STARLING tends to
collect bonus scores in Zork1 that are reachable within fewer steps instead of
just chasing the larger rewarded states (e.g., see Figure 6 right).

##  4 Related Work

###  4.1 Text-based Games

Text-based games provide a challenging benchmark for RL agents interacting
with the environment in natural language. The common challenges for text-based
RL are partial observability, combinatorial action space, sparse rewards,
long-horizon planning, etc. To circumvent some of these challenges, it is
typical that the games are often manually curated to evaluate a specific set
of skills such as commonsense reasoning Murugesan et al. (2021a), knowledge
graphs Ammanabrolu and Hausknecht ; Murugesan et al. (2021b), exploration
strategies Côté et al. (2019), etc. Environments such as TextWorld Commonsense
Murugesan et al. (2021a) measure simple commonsense reasoning based on the
one-hop relationship between a pair of everyday objects such (apple and
refrigerator, dirty towel and laundry basket), but lacks diversity and
complexity to learn a general set of skills.

Environments such as ScienceWorld Wang et al. (2022) are often domain-specific
environments that require domain knowledge to perform well in these
environments. Jericho Hausknecht et al. (2020), on the other hand, includes
human-generated games that require a complex set of skills to show any
progress in the gameplay. These environments are manually created by humans
with very limited automation in the variations of game generation by replacing
similar or related objects, changing the layout/orientation of the
environment, etc. Unlike these environments, STARLING provides an approach to
leverage the skill generation capability of LLMs Huang et al. (2022) to
automatically generate text-based games based on the input game ideas with
minimal human supervision. These games are generated automatically by
requesting a specific set of game-related facts from LLM in a slot-filling
style text generation Rakotonirina et al. (2022).

###  4.2 Self-supervised RL

Self-supervised RL has been a popular topic in vision-based RL and robotic
environments Sekar et al. (2020); Li et al. (2022). To the best of our
knowledge, we are the first to utilize LLM to generate the games to train
text-based RL agents555Several LLM-based interactive fictional environments
for entertainment purposes exist AID (2019).. Previous works have utilized LLM
for action generation Yao et al. (2020), play interactive fictional game Tsai
et al. (2023), build a world model Ammanabrolu et al. (2020); Wang et al.
(2023b), etc. These works showed that using LLM to learn the underlying
representation of text in the environment does not necessarily improve the
performance (Wang et al., 2022). It is shown that novel exploration strategies
and efficient RL algorithms along with the learning model similar to the one
in Figure 11 outperform all the other LLM-based agents Tuyls et al. (2021). On
the other hand, generalist agents have been recently explored to generalize
across multiple environments Reed et al. (2022), but the performance of these
agents on a diverse set of environments is less convincing Cobbe et al.
(2019).

##  5 Conclusion

In this paper, we proposed a novel self-supervised training for a text-based
reinforcement learning agent, STARLING, with the help of the generalized skill
generation capability of large language models like GPT3. We generated a set
of text-based games that require agents to learn basic skills such as cooking
pasta, boiling water, etc., and utilize sequential decision-making over the
modality of text. The proposed STARLING uses the GPT3 pre-trained language
model to automatically generate these games. This approach can be used to
create additional games or adapted to build games for new domains with minimal
human intervention. We showed that the STARLING agent pre-trained on the games
generated by LLM outperforms vanilla TBRL. We evaluated STARLING on three
environments: ScienceWorld, TWC, and Zork1. In all these environments,
STARLING showed enhanced skills in the target environment.

##  6 Limitations

Human participants were volunteers from a local High School that agreed to
participate in this study. This may have introduced a bias into the human
participant data since all participants were high school educated, from one
geographic region, between the ages of 15 and 18, and volunteers. Many of
these participants complete homework assignments and assessments often which
may make their reasoning skills better than potential participants outside of
school. In the future, testing human participants from various geographic
locations, age groups, and levels of education may reduce bias. The STARLING
currently requires human intervention and/or the Game Validator (from the
glulx compiler) to build functioning games. We will continue to work on
building an end-to-end version of the STARLING, that can take a game idea and
turn it into an interactive fiction game without any human intervention. This
would speed up development time so a larger set of games can be created.

Large language models such as ChatGPT have been developed recently with the
ability to interact with users in a manner conversationally similar to the
interactions found in interactive fiction games. From our experimentation,
ChatGPT struggles to keep track of the states of all in-game objects and the
pre-conditions necessary to use those actions (e.g. ChatGPT does not always
require the player to turn on the stove before using it) as well as
Inform7-based games. In addition, it suffers from small factual errors, and is
hard to reproduce the same result, through this could also be seen as a
benefit. Despite these challenges exploring the use of models such as ChatGPT
to interact with agents shows promise in the future.

##  7 Ethical Impact

We asked the human participants to play the games generated by STARLING to
evaluate the game’s complexity and clarity. After receiving IRB approval from
a local High School and informed consent from each of the $48$ human
participants, we asked the participants to play five randomly assigned games
via iplayif.com, an online interactive fiction game player. Players received
the goal of the game and the list of admissible actions. We collected the
number of steps that each player took and the score received for each game via
Google form. We did not collect any personal information or personally
identifiable information as a part of this study.

Since we use large language models such as GPT3 to generate a set of text-
based games, the bias and other fairness/ethical concerns that come with the
LLM may unintentionally transfer to the pre-trained agent. Additional
mitigation steps may be required to filter harmful contents from the generated
response.

##  8 Reproducibility

As an effort to encourage further research in self-supervised text-based RL,
we plan to release the $100$ games generated as a part of this paper, the
source code for STARLING, script to generate game-related files based on a set
of game ideas and LLM (including game templates and metadata) as an open-
source project.

## References

  * AID (2019) 2019\.  Ai dungeon (https://play.aidungeon.io).
  * (2) Prithviraj Ammanabrolu and Matthew Hausknecht.  Graph constrained reinforcement learning for natural language action spaces.  In _International Conference on Learning Representations_.
  * Ammanabrolu et al. (2020) Prithviraj Ammanabrolu, Ethan Tien, Matthew Hausknecht, and Mark O Riedl. 2020.  How to avoid being eaten by a grue: Structured exploration strategies for textual worlds.  _arXiv preprint arXiv:2006.07409_.
  * Atzeni et al. (2022) Mattia Atzeni, Shehzaad Dhuliawala, Keerthiram Murugesan, and Mrinmaya Sachan. 2022.  Case-based reasoning for better generalization in text-adventure games.  In _ICLR 2022_.
  * Brockman et al. (2016) Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. 2016.  Openai gym.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, …, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc.
  * Cho et al. (2014) Kyunghyun Cho, Bart van Merrienboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014.  Learning phrase representations using rnn encoder–decoder for statistical machine translation.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1724–1734.
  * Cobbe et al. (2019) Karl Cobbe, Oleg Klimov, Chris Hesse, Taehoon Kim, and John Schulman. 2019.  Quantifying generalization in reinforcement learning.  In _International Conference on Machine Learning_ , pages 1282–1289. PMLR.
  * Côté et al. (2019) Marc-Alexandre Côté, Akos Kádár, Xingdi Yuan, Ben Kybartas, Tavian Barnes, Emery Fine, James Moore, Matthew Hausknecht, Layla El Asri, Mahmoud Adada, et al. 2019.  Textworld: A learning environment for text-based games.  In _Computer Games: 7th Workshop, CGW 2018, Held in Conjunction with the 27th International Conference on Artificial Intelligence, IJCAI 2018, Stockholm, Sweden, July 13, 2018, Revised Selected Papers 7_ , pages 41–75. Springer.
  * Hausknecht et al. (2020) Matthew Hausknecht, Prithviraj Ammanabrolu, Marc-Alexandre Côté, and Xingdi Yuan. 2020.  Interactive fiction games: A colossal adventure.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 7903–7910.
  * He et al. (2016) Ji He, Jianshu Chen, Xiaodong He, Jianfeng Gao, Lihong Li, Li Deng, and Mari Ostendorf. 2016.  Deep reinforcement learning with a natural language action space.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1621–1630.
  * Huang et al. (2022) Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch. 2022.  Language models as zero-shot planners: Extracting actionable knowledge for embodied agents.  In _International Conference on Machine Learning_ , pages 9118–9147. PMLR.
  * Hwang et al. (2021) Jena D Hwang, Chandra Bhagavatula, Ronan Le Bras, Jeff Da, Keisuke Sakaguchi, Antoine Bosselut, and Yejin Choi. 2021.  (comet-) atomic 2020: on symbolic and neural commonsense knowledge graphs.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 6384–6392.
  * Jansen (2022) Peter Jansen. 2022.  A systematic survey of text worlds as embodied natural language environments.  In _Proceedings of the 3rd Wordplay: When Language Meets Games Workshop (Wordplay 2022)_ , pages 1–15, Seattle, United States. Association for Computational Linguistics.
  * Li et al. (2022) Xiang Li, Jinghuan Shang, Srijan Das, and Michael Ryoo. 2022.  Does self-supervised learning really improve reinforcement learning from pixels?  _Advances in Neural Information Processing Systems_ , 35:30865–30881.
  * Mnih et al. (2016) Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. 2016.  Asynchronous methods for deep reinforcement learning.  In _International conference on machine learning_ , pages 1928–1937. PMLR.
  * Murugesan et al. (2021a) Keerthiram Murugesan, Mattia Atzeni, Pavan Kapanipathi, Pushkar Shukla, Sadhana Kumaravel, Gerald Tesauro, Kartik Talamadupula, Mrinmaya Sachan, and Murray Campbell. 2021a.  Text-based rl agents with commonsense knowledge: New challenges, environments and baselines.  In _AAAI_ , pages 9018–9027.
  * Murugesan et al. (2021b) Keerthiram Murugesan, Mattia Atzeni, Pavan Kapanipathi, Kartik Talamadupula, Mrinmaya Sachan, and Murray Campbell. 2021b.  Efficient text-based reinforcement learning by jointly leveraging state and commonsense graph representations.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing_ , volume 2, pages 719–725. Association for Computational Linguistics.
  * Nelson (2006) Graham Nelson. 2006.  Inform7.
  * Rakotonirina et al. (2022) Nathanaël Carraz Rakotonirina, Roberto Dessi, Fabio Petroni, Sebastian Riedel, and Marco Baroni. 2022.  Can discrete information extraction prompts generalize across language models?  In _The Eleventh International Conference on Learning Representations_.
  * Reed et al. (2022) Scott Reed, Konrad Zolna, Emilio Parisotto, Sergio Gómez Colmenarejo, Alexander Novikov, Gabriel Barth-maron, Mai Giménez, Yury Sulsky, Jackie Kay, Jost Tobias Springenberg, et al. 2022.  A generalist agent.  _Transactions on Machine Learning Research_.
  * Sekar et al. (2020) Ramanan Sekar, Oleh Rybkin, Kostas Daniilidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. 2020.  Planning to explore via self-supervised world models.  In _International Conference on Machine Learning_ , pages 8583–8592. PMLR.
  * Speer et al. (2017) Robyn Speer, Joshua Chin, and Catherine Havasi. 2017.  Conceptnet 5.5: An open multilingual graph of general knowledge.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 31.
  * Tsai et al. (2023) Chen Feng Tsai, Xiaochen Zhou, Sierra S Liu, Jing Li, Mo Yu, and Hongyuan Mei. 2023.  Can large language models play text games well? current state-of-the-art and open questions.  _arXiv preprint arXiv:2304.02868_.
  * Tuyls et al. (2021) Jens Tuyls, Shunyu Yao, Sham M Kakade, and Karthik R Narasimhan. 2021.  Multi-stage episodic control for strategic exploration in text games.  In _International Conference on Learning Representations_.
  * Wang et al. (2022) Ruoyao Wang, Peter Jansen, Marc-Alexandre Côté, and Prithviraj Ammanabrolu. 2022.  Scienceworld: Is your agent smarter than a 5th grader?  _arXiv preprint arXiv:2203.07540_.
  * Wang et al. (2023a) Ruoyao Wang, Peter Jansen, Marc-Alexandre Côté, and Prithviraj Ammanabrolu. 2023a.  Behavior cloned transformers are neurosymbolic reasoners.  In _Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics_ , pages 2769–2780.
  * Wang et al. (2023b) Ruoyao Wang, Graham Todd, Eric Yuan, Ziang Xiao, Marc-Alexandre Côté, and Peter Jansen. 2023b.  Bytesized32: A corpus and challenge task for generating task-specific world models expressed as text games.  _arXiv e-prints_ , pages arXiv–2305.
  * Yao et al. (2020) Shunyu Yao, Rohan Rao, Matthew Hausknecht, and Karthik Narasimhan. 2020.  Keep calm and explore: Language models for action generation in text-based games.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 8736–8754.
  * Zahavy et al. (2018) Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel J Mankowitz, and Shie Mannor. 2018.  Learn what not to learn: Action elimination with deep reinforcement learning.  _Advances in neural information processing systems_ , 31.

Figure 8: (Left) shows the overview of the proposed self-supervised text-based
reinforcement learning with large language model. (Right) shows the sample
text-only agent play through of cooking pasta game. Players must use the boil
skill at the correct time to be successful. Figure 9: Architecture diagram for
Self-supervised Text-based Reinforcement Learning using LLM (STARLING).

##  Appendix A Additional Details

In order to generate games that require composing previously learned skills,
we take inspiration from household chores, cooking, and maintenance tasks. We
generate $100$ game ideas and use the STARLING to generate a set of $100$
games. We choose the game ideas carefully for the learning agent to utilize
similar skills (ex. baking, mixing, spreading, using a hammer, etc) in new
situations therefore forcing the agent to generalize skills and compose them
with other skills. For example, while cooking pasta, an agent must learn how
to boil water which is a skill that can be applied for a related game idea
"brewing tea".

LLMs such as GPT-3 are prone to making factual and grammatical errors, in
addition to violating the specified format. We check for any errors in the
generated game(s) using a Game Validator as a part of glulx compiler which
uses depth first search (DFS) to explore all the possible trajectories in the
game. To correct for minor errors and inconsistencies in each game,
information from GPT-3 can also be optionally verified by the human authors in
the JSON file. We found that, in cases when the created game has errors,
restarting the game generation a few times usually results in a playable game.

###  A.1 From GPT3 output to game JSON

We extract the information from GPT-3 using Python simple regular expression
rules by first splitting the output into three sections: task sequence (ex.
Open cabinet, take pot), objects (ex. Pot), and actions (ex. Fill pot with
water). We add the task sequence to the list of admissible actions the player
could execute within the game. We store the objects internally with a type, a
location, a name, and a set of properties. We further split the actions
section into default actions and custom actions which are actions native and
non-native to inform7 respectively. Similar to the objects, we store each
custom action internally with a name, a declaration, a definition, a set of
constraints, a set of prerequisites, and a set of post-requisites.

###  A.2 Inform7 Code Generator

We wrote a simple script based on the JSON structure and the action templates
to generate the Inform7 Code for a given game idea. This script along with the
other code & data will be shared to the public in the near future.

###  A.3 Modifying TextWorld Gym for STARLING

OpenAI Gym is a general reinforcement learning framework that acts as an
interface between RL agents and Inform7-based STARLING game engine Brockman et
al. (2016). Gym connects environments with agents by using a monitor to keep
track of every step, state of the game, the final score of agents, and the
sample complexity or the amount of time an agent takes to learn. Most default
environments in Gym support a continuous or discrete action space although
interactive fiction games require combinatorial action spaces in natural
language Hausknecht et al. (2020). The TextWorld Gym customized the OpenAI Gym
for interactive fiction games. In this work, we repurpose the custom Gym
environment created for TextWorld environment with Inform7 object and action
types.

TextWorld’s Gym environment only supports TextWorld-generated games which
includes a Glulx compiled game file and a TextWorld-generated JSON file with
game metadata defined in proprietary TextWorld classes. This restricted our
ability to create games with objects and actions previously undefined in
TextWorld environment. These objects and actions must be defined according to
TextWorld’s grammar and logic rules. This is a time consuming process and is
prone to many errors. The goal of the STARLING Game Generator is to allow
users to automate the game creation using LLM, and most importantly, create
games without learning a new programming language or familiarizing themselves
with any grammar rules.

To get rid of these restrictions, an entirely new wrapper was created which
acted as an interface between the game engine and TextWorld Gym environment.
This wrapper ensures that the user to freely define any object or action type
and the environment works with any Glulx compiled game file without dependence
on the TextWorld-generated metadata to track the state of objects throughout
the game. The wrapper does this by parsing the observation state returned by
game engine after every step to generate certain data-points like admissible
commands, current score, last action, number of steps taken and inventory
required by the TextWorld Gym environment.

##  Appendix B Human Participants

Humans are considered to have exemplary compositional skill learning so
comparing their performance to pre-trained agent’s performance is valuable to
validate generated games’s difficulty and effectiveness as a pre-training
task. After receiving IRB approval from a local High School and informed
consent from each of the $48$ human participants, we asked the participants to
play five randomly assigned games via iplayif.com, an online interactive
fiction game player. Players received the goal of the game and the list of
admissible actions. We collected the number of steps that each player took and
the score received for each game via Google form. 666No personal information
was collected as a part of this study.

##  Appendix C Pretraining Game Statistics

Game-specific Statistics
---
Min. # Actions | 7.36 $\pm$ 2.53
Avg. Rewards across games | 4.08 $\pm$ 1.57
Num. Skills per game | 2 $\pm$ 1

Figure 10: Composition of skills needed to complete the game "Cooking Pasta"
as Flow diagram. A line between two skills represent that one skill needs to
be executed before executing the other one (E.g., Open cabinet
$\longrightarrow$ Take pot). A box with multiple skills represent that skills
within the box can be executed in any order (E.g., Boil water in pot
$\parallel$ Take pasta). Figure 11: Vanilla Text-based RL agent used in this
paper.  Figure 12: Sample Trajectories taken by STARLING and Vanilla TBRL for
the task: change of state (boiling) task in ScienceWorld. Figure 13: Example
JSON file produced for cooking pasta game idea. The libraries, modules, and
room sections were part of the setup, the custom entities and entities
sections correspond to object creation, the actions correspond to the custom
actions, and the scoring and end game correspond to the rewards sections of
each game. The entities section describes names, types, and properties of
entities present in the game. The actions section defines custom actions
including their declaration, alias, and constraints not part of Inform7 by
default. The end-game section defines the maximum score and the list of
admissible actions that the user can take.


# Heavy-dense QCD, sign optimization and Lefschetz thimbles

Gökçe Başar<EMAIL_ADDRESS>Joseph Marincel<EMAIL_ADDRESS>Department of
Physics and Astronomy, University of North Carolina, Chapel Hill, North
Carolina 27599, USA

###### Abstract

We study the heavy-dense limit of QCD on the lattice with heavy quarks at high
density. The effective three dimensional theory has a sign problem which is
alleviated by sign optimization where the path integration domain is deformed
in complex space in a way that minimizes the phase oscillations. We simulate
the theory via a Hybrid-Monte-Carlo, for different volumes, both to leading
order and next-to-next-to leading order in the hopping expansion, and show
that sign optimization successfully mitigates the sign problem at large enough
volumes where usual re-weighting methods fail. Finally we show that there is a
significant overlap between the complex manifold generated by sign
optimization and the Lefschetz thimbles associated with the theory.

##  I Introduction

Mapping the phase diagram of Quantum Chromo Dynamics (QCD), the theory that
governs the strong nuclear force, has been an outstanding problem for many
decades. The main challenge in a nutshell is that such a task requires non-
perturbative methods which almost always involve a numerical stochastic,
“Monte-Carlo” component where the path integral is sampled statistically. Even
though such non-perturbative methods have been very successful in computing
the thermodynamic properties of QCD at small densities HotQCD:2014kol ;
BORSANYI201499 , for most theories at finite density, including QCD, their
applicability is severely limited by the “sign-problem” which arises when path
integral measure is not positive definite and therefore cannot be interpreted
as a probability measure. In many cases such as QCD at finite density, the
underlying action is complex and the Boltzmann weight, $e^{-S}$, leads to
severe phase oscillations in the path integral which become exponentially
rapid in the large volume / low temperature limit deForcrandreview ;
Philipsen:2007aa ; KARSCH200014 ; Aarts_2016 . These oscillations make the
numerical computation of the path integral practically impossible.

Over the years, there has been many attempts to tackle the sign problem. One
set of ideas stem from complexification of fields where instead of sampling
the configurations on the original domain of the path integral (for example
$SU(N_{C})$ for QCD), one samples on a complexified domain (a subset of
$SL(N_{C})$ for QCD) where the phase oscillations are milder and therefore can
be dealt with using conventional methods. Of course, the deformation to the
complexified fields must not change the value of the path integral. An example
of a complex domain over which the path integral has milder phase oscillations
is the Lefschetz thimble decomposition, which is a multi-dimensional
generalization of expressing a one-dimensional integral as a linear
combination of steepest descent contours pham ; Lefschetz:1975ta . Just like
steepest descent contours, the phase over each Lefschetz thimble is
stationary, rendering the phase oscillations milder Cristoforetti:2012su ;
Cristoforetti:2012uv ; Fujii:2013sra . However finding the correct linear
combination of thimbles for a given set of parameters in the theory and
sampling is generally challenging. To overcome these difficulties various
methods have been proposed where instead of the thimbles, one samples over
other complex domains which still have milder phase oscillations than the
original domain but easier to construct and sample compared to thimbles
Alexandru:2020wrj .

A more direct approach to mitigating the sign problem by complexification is
to convert it into an optimization the problem where one minimizes the sign
oscillations within a family of complex domains parameterized by a set of
auxiliary variables. In a nutshell, an observable, such as the average phase,
that measures the strength of the sign oscillations is minimized within that
set of parameters that describe the complexified domain. The set of ideas that
stem from this approach goes under the name “sign optimization” and has been
applied to various QCD-like models Mori:2017pne ; Alexandru:2018fqp ;
Kashiwa:2019lkv . More broadly, this idea has also been used to mitigate
signal-to-noise problems in gauge theories even in the absence of a sign
problem Detmold:2021ulb

In this paper, we implement sign optimization in the heavy-dense limit of QCD
which is captured by an effective theory whose degrees of freedom describe
heavy quarks at very high density. Even though this is a somewhat academic
limit of QCD, it does inherit the sign problem from QCD which becomes
exponentially severe with the volume/inverse temperature. Furthermore the
degrees of freedom are elements of $SU(N_{C})$ the complexification of which
can be generalized to QCD. Furthermore, the simplified mathematical structure
of the theory in this limit allows analytical expressions which can be
directly compared with the Monte-Carlo results obtained from sign optimized
lattice simulations. Finally, because of the same reason, the simulations are
not as demanding as QCD in terms of computational resources. All these factors
combined make heavy dense QCD an ideal test ground for implementing sign
optimization with the goal of applying it to QCD in the future. Along similar
lines to this work, it has been studied via Lefschetz thimbles
Zambello:2018ibq  and Complex Langevin Attanasio:2015Cg ; Aarts:2016qrv  in
the context of the sign problem.

In Ref. Basar:2022cef  we studied the one-dimensional limit of QCD in the
context of sign optimization. This paper is a natural continuation of the work
along those lines. One crucial difference, however, is that heavy-dense QCD is
a three-dimensional effective theory where the sign problem grows
exponentially with the volume, allowing us to analyze the performance of sign
optimization as a function of volume; which was not possible in one-
dimensional QCD. At the same time, as we discuss further in the paper, the
existence of complex saddle points and the relations between the Lefschetz
thimbles attached to these saddles and the sign optimized manifolds is similar
to what we have observed in one-dimensional QCD.

The rest of the paper is organized as follows. In Sections II and III we
briefly recapitulate the heavy-dense effective theory of QCD, and sign
optimization respectively. Our results are presented in Section IV. We then
compare the complexified domains obtained by sign optimization to Lefschetz
Thimbles in Section V. Finally we discuss our results and present our
conclusions in Section VI.

##  II Heavy Dense QCD

We consider the cold and dense limit of QCD with heavy quarks Fromm:2011qi ;
Fromm:2012eb ; Langelage:2014vpa . In this limit, the quarks cannot move due
their large mass, but do not decouple entirely either, due to their high
density. The resulting effective theory is three dimensional whose degrees of
freedom are Polyakov loops, $P({\bf x})$, that describe these stationary
quarks. More precisely, to leading order in this heavy-dense limit, the Dirac
determinant (for Wilson fermions on the lattice) limit reduces to Fromm:2011qi

$\displaystyle\det Q_{f}=\prod_{{\bf x}}\det(1+h{\rm Tr}P_{\bf
x})^{2}\det(1+\bar{h}{\rm Tr}P^{\dagger}_{\bf x})^{2}$ (1)

where $P_{\bf x}=\prod_{x_{0}=1}^{N_{t}}U_{0}(x_{0},{\bf x})$ is the Polyakov
loop (in the temporal gauge) that is an element of $SU(3)$ and

$\displaystyle h=e^{(\mu-m)/T}=(2\kappa e^{\mu
a})^{N_{t}},\quad\bar{h}=e^{(-\mu-m)/T}=(2\kappa e^{-\mu a})^{N_{t}}$ (2)

are the quark and anti-quark fugacities with $a$, $\mu$ and $m$ being the
lattice spacing, quark chemical potential and constituent quark mass. It is
also useful to define the “hopping parameter” $\kappa=e^{-ma}/2$. In the
heavy-dense limit

$\displaystyle ma\rightarrow\infty,\mu a\rightarrow\infty\text{ such that
}\kappa e^{\mu a}=\text{finite}\,.$ (3)

At high densities the quarks have much larger fugacity than anti-quarks,
$h\gg\bar{h}$ and the second term in Eq. (1) can be neglected, which simply
means that the anti-quark contribution to the effective action is negligible.
We further take the lattice strong coupling limit where the gauge field
dynamics can be neglected as well. This turns out to be a fairly good
approximation for $g^{2}_{YM}\gtrsim 1$ because as explained in Ref.
Fromm:2012eb , the effective gauge coupling, $\lambda$, vanishes rapidly as
$\lambda\sim(2N_{c}/g^{2}_{YM})^{N_{t}}$ for an $SU(N_{c})$ gauge group with
coupling $g^{2}_{YM}$. Finally, for $N_{c}=3$, the Dirac determinant can be
expressed in terms of ${\rm Tr}P$ as

$\displaystyle\det(1+hP_{\bf x})=(1+h{\rm Tr}P_{\bf x}+h^{2}{\rm
Tr}P^{\dagger}_{\bf x}+h^{3})$ (4)

Putting everything together, to leading order in the heavy-dense limit, the
partition function of the effective theory is obtained as

$\displaystyle Z=\int[{\mathcal{D}}P]\prod_{\bf x}(1+h{\rm Tr}P_{\bf
x}+h^{2}{\rm Tr}P^{\dagger}_{\bf x}+h^{3})^{2}\,.$ (5)

Apart from $h=0$ (zero density) or $h=1$ (half-filling), $P_{\bf x}$ and
$P^{\dagger}_{\bf x}$ have different weights, therefore the Dirac determinant
is complex and the theory has a sign problem. Furthermore the sign problem
grows exponentially with volume,

$\displaystyle\sigma=\sigma_{0}^{V}\text{ where
}\sigma_{0}=\frac{1+4h^{3}+h^{6}}{1+h^{2}+2h^{3}+h^{4}+h^{6}}$ (6)

which follows from the fact only non-vanishing group integrals are
$\int[{\mathcal{D}}P]=\int[{\mathcal{D}}P]P^{\dagger}P=1$, and the path
integral factorizes for each ${\bf x}$.

Beyond leading order, the dynamics of fermions can be systematically
incorporated in the theory as interaction between the Polyakov loops at
different spatial points and can be organized in a hopping expansion
controlled by the hopping parameter $\kappa$ Langelage:2014vpa . These
interactions further simplify in the limit $N_{t}\gg 1$, which we assume, and
lead to the following next-to-next-to-leading order (NNLO) effective action
Langelage:2014vpa

$\begin{split}S_{NNLO}=&-2\sum_{{\bf x}}\text{Tr log}(1+hP_{{\bf
x}})+\eta\sum_{{\bf x},\hat{i}}\text{Tr}\frac{hP_{{\bf x}}}{1+hP_{{\bf
x}}}\text{Tr}\frac{hP_{{\bf x}+\hat{i}}}{1+hP_{{\bf x}+\hat{i}}}\\\
&-\eta^{2}\sum_{{\bf x},\hat{i}}\text{Tr}\frac{hP_{{\bf x}}}{(1+hP_{{\bf
x}})^{2}}\text{Tr}\frac{hP_{{\bf x}+\hat{i}}}{(1+hP_{{\bf
x}+\hat{i}})^{2}}-\eta^{2}\sum_{{\bf
x},\hat{i},\hat{j}}\text{Tr}\frac{hP_{{\bf x}}}{(1+hP_{{\bf
x}})^{2}}\text{Tr}\frac{hP_{{\bf x}+\hat{i}}}{(1+hP_{{\bf
x}+\hat{i}})}\text{Tr}\frac{hP_{{\bf x}+\hat{j}}}{(1+hP_{{\bf
x}+\hat{j}})}\,.\end{split}$ (7)

Here $\hat{i},\hat{j}$ denote the nearest neighbors of ${\bf x}$ and the sums
over $\hat{i}$ and $\hat{j}$ run over each direction (${\bf x}+\hat{1},{\bf
x}-\hat{1}$, etc…). The effective coupling that controls the hopping expansion
is

$\displaystyle\eta=\frac{\kappa^{2}N_{t}}{N_{c}}$ (8)

We have simulated the leading order as well as NNLO theory by using sign
optimization.

##  III Complexification and Sign optimization

In this section we summarize the idea of sign optimization Mori:2017pne ;
Alexandru:2018ddf ; Alexandru:2018fqp ; Kashiwa:2019lkv ; Mori:2019tux , and
detail how we implement in heavy dense QCD. As mentioned in the Introduction,
our strategy is to complexify the path integral, without changing its value,
in a way that the sign oscillations in the complexified domain are milder than
the original domain. Let us denote a generic complex space whose shape depends
on a set of parameters, $\vec{\lambda}$, as ${{\cal M}_{\vec{\lambda}}}$. Our
first requirement is that complexification does not change the value of the
path integral:

$\displaystyle Z=\int_{SU(3)}[{\mathcal{D}}P]e^{-S[P]}=\int_{{\cal
M}_{\vec{\lambda}}}[{\mathcal{D}}P]e^{-S[P]}\,.$ (9)

This is ensured by Cauchy’s theorem as long as the deformation from $SU(3)$ to
${{\cal M}_{\vec{\lambda}}}$ does not cross any singularities. The strength of
the sign oscillations are captured by the average phase,

$\displaystyle\sigma_{\vec{\lambda}}=\frac{\int_{{\cal
M}_{\vec{\lambda}}}[{\mathcal{D}}P]|e^{-S[P]}|e^{-i{\rm Im}S[P]}}{\int_{{\cal
M}_{\vec{\lambda}}}[{\mathcal{D}}P]|e^{-S[P]}|}=\frac{\int_{{\cal
M}_{\vec{\lambda}}}[{\mathcal{D}}P]e^{-S[P]}}{\int_{{\cal
M}_{\vec{\lambda}}}[{\mathcal{D}}P]e^{-{\rm Re}S[P]}\,.}$ (10)

When the sign oscillations are strong $|\sigma_{\vec{\lambda}}|\approx 0$ due
to the phase cancellations and when they are mild
$|\sigma_{{\vec{\lambda}}}|\approx 1$. Notice that even though the path
integral remains unchanged with the deformation, the average sign does change,
since the integrand in the denominator involves a non-holomorphic term ${\rm
Re}S$. Therefore our goal is to find a set of ${\vec{\lambda}}$s which
maximizes $|\sigma_{{\vec{\lambda}}}|$. To do this, we follow a gradient
descent trajectory where we start from $SU(3)$ (which corresponds to
$\lambda_{i}=0$) and update ${\vec{\lambda}}$ according to

${\vec{\lambda}}(\tau+1)={\vec{\lambda}}(\tau)+\delta\nabla_{{\vec{\lambda}}}\log|\sigma_{{\vec{\lambda}}(\tau)}|$
(11)

where $\tau$ denotes the gradient ascent step. With an appropriate choice of
the step size $\delta$ that is determined empirically, this procedure
converges to a local maximum of $|\sigma_{\vec{\lambda}}|$.

It is clear that the complexified path integration domain, ${\cal
M}\equiv{{\cal M}_{\vec{\lambda}}}^{V}$, must have the same dimensions as
$SU(3)^{V}$, meaning it is a middle dimensional complex manifold embedded in
$SL(3)^{V}$. To parameterize ${{\cal M}_{\vec{\lambda}}}$ we first express
$P\in SU(3)$, with 8 angles a lá Bronzan Bronzan:1988wa :

$P(\theta)=\begin{pmatrix}c_{1}c_{2}e^{i\theta_{4}}&s_{1}e^{i\theta_{6}}&c_{1}s_{2}e^{i\theta_{7}}\\\
s_{2}s_{3}e^{-i(\theta_{7}+\theta_{8})}-s_{1}c_{2}c_{3}e^{i(\theta_{4}+\theta_{5}-\theta_{6})}&c_{1}c_{3}e^{i\theta_{5}}&-c_{2}s_{3}e^{-i(\theta_{4}+\theta_{8})}-s_{1}s_{2}c_{3}e^{i(\theta_{5}-\theta_{6}+\theta_{7})}\\\
-s_{1}c_{2}s_{3}e^{i(\theta_{4}-\theta_{6}+\theta_{8})}-s_{2}c_{3}e^{-i(\theta_{5}+\theta_{7})}&c_{1}s_{3}e^{i\theta_{8}}&c_{2}c_{3}e^{-i(\theta_{4}+\theta_{5})}-s_{1}s_{2}s_{3}e^{i(-\theta_{6}+\theta_{7}+\theta_{8})}\\\
\end{pmatrix}$ (12)

The path integral is evaluated on the domain $\theta_{i}\in[0,\pi/2]$ for
$i=1,2,3$ and $\theta_{i}\in[0,2\pi]$ for $i=4,\dots,8$. In this
representation, the group measure is explicitly written as

$\displaystyle dP=H(\theta)d^{8}\theta$ (13)

where $H(\theta)$ is the Haar measure, identified with the invariant measure
over the $SU(3)$ manifold

$\displaystyle H(\theta)=\sqrt{\det
g}=\frac{1}{2\pi^{5}}s_{1}c_{1}^{3}s_{2}c_{2}s_{3}c_{3}\,.$ (14)

Here $g$ is the invariant $SU(3)$ metric defined as $g_{ij}={\rm
Tr}\left(P^{-1}\frac{\partial P}{\partial\theta_{i}}P^{-1}\frac{\partial
P}{\partial\theta_{j}}\right)$ up to an arbitrary normalization that can be
fixed by demanding $\int d^{8}\theta H=1$. The path integral in terms of the
$\theta$ variables can be written as

$\displaystyle Z=\int[{\mathcal{D}}p]e^{-S[P]}=\int d^{8V}\theta
e^{-S_{eff}(\theta)}$ (15)

where

$\displaystyle S_{eff}(\theta)=S[P(\theta)]-\sum_{\bf x}\log H(\theta_{\bf
x})$ (16)

We can now express ${{\cal M}_{\vec{\lambda}}}$ in terms of complex $\theta$s,
which we denote as ${\tilde{\theta}}$. It is convenient to express the
${\tilde{\theta}}$ in terms of its real part, which we simply call $\theta$,
as

$\displaystyle{\tilde{\theta}}_{i}(\theta)=\theta_{i}+if_{i}(\theta)$ (17)

where $f_{i}(\theta)$ are non-singular, real functions that generically
depends on a set of parameters ${\vec{\lambda}}$. By construction
$P({\tilde{\theta}}(\theta))$ is an element of a middle-dimensional manifold
${{\cal M}_{\vec{\lambda}}}\subset SL(3)$ since it is still parameterized by
eight variables. Furthermore the path integral over this manifold ${{\cal
M}_{\vec{\lambda}}}$ is equal to the original path integral over $SU(3)$. This
is because $\theta$ can be smoothly deformed into ${\tilde{\theta}}$ say by
considering a set of intermediate surfaces parameterized by
$\theta_{i}+isf_{i}$ with $s\in[0,1]$ without crossing any singularities in
the integrand. By Cauchy’s theorem this deformation does not change the value
of $Z$ Alexandru:2018ddf .

One advantage of the ansatz Eq. (17) is that we can express the path integral
over ${{\cal M}_{\vec{\lambda}}}$ using the original real variables $\theta$

$\displaystyle Z=\int_{{{\cal
M}_{\vec{\lambda}}}}[{\mathcal{D}}P]e^{-S[P]}=\int
d^{8V}{\tilde{\theta}}e^{-S_{eff}({\tilde{\theta}})}=\int d^{8V}\theta\det
Je^{-S_{eff}\left({\tilde{\theta}}(\theta)\right)}=\int d^{8V}\theta
e^{-\tilde{S}(\theta)}$ (18)

where

$\displaystyle
J=\frac{\partial{\tilde{\theta}}_{i}}{\partial\theta_{j}}=\delta_{ij}+i\frac{\partial
f_{i}}{\partial\theta_{j}}$ (19)

is the Jacobian of the transformation, and the effective action is given as

$\displaystyle\tilde{S}(\theta)=S_{eff}({\tilde{\theta}}(\theta))-\sum_{\bf
x}\left[\log\det J(\theta_{\bf x})+\log H\left({\tilde{\theta}}(\theta_{\bf
x})\right)\right]$ (20)

We shall consider a class of complex fields generated by the so-called
“mixing” ansatz :

$\displaystyle f_{i}(\theta)=\begin{cases}0\quad\text{for }i=1,2,3\\\
\sum_{m,n=0}^{N}\lambda_{m,n}^{(i)}\cos(m\theta_{4}+n\theta_{5})\quad\text{for
}i=4,5\\\ \lambda^{(i)}\quad\text{for }i=6,7,8\end{cases}$ (21)

This ansatz was introduced in the study of the one-dimensional QCD and it was
observed to perform better than the “diagonal” ansatz where ${\rm
Im}\tilde{\theta}_{i}$ is only a function of $\theta_{i}$, i.e.
$f_{i}(\theta)\equiv f_{i}(\theta_{i})$ Basar:2022cef . The heuristic reason
for the better performance is that the mixing between $\theta_{i}$s capture
the fluctuations around complex saddle points more accurately than the
diagonal ansatz. We will elaborate more on this in Section V when we compare
the manifold created via sign optimization to Lefschetz thimbles.

We note that since the only degrees of freedom of the heavy-dense effective
theory are Polyakov loops, ${\rm Tr}P$, we could have used the two independent
eigenvalues of ${\rm Tr}P$ to parameterize the path integration domain instead
of using the full $SU(3)$ parameterized by eight variables. Instead we choose
to work with the full $SU(3)$, even though it is redundant to do so, in order
to keep the discussion general and pave the way for more realistic cases where
the degrees of freedom are the full $SU(3)$. That said, in this case, one
would likely need to work with a more general ansatz for the complexified
fields than Eq. (21) , which can easily be realized by, for instance, taking
into account the Fourier coefficient of all the $\theta_{i}$s. A more detailed
analysis of the computational performance of different choices of the anstaze
is left for future work.

Being equipped with the representation of the path integral over ${{\cal
M}_{\vec{\lambda}}}$ in terms of real $\theta_{i}$ given in Eq. (18) , it is
straightforward to simulate the theory using standard Monte-Carlo techniques
by using the effective action given in Eq. (20) . The Markov chain on the
complex field space, ${{\cal M}_{\vec{\lambda}}}$ is generated by using real
$\theta$s that parameterize ${{\cal M}_{\vec{\lambda}}}$ with respect to the
probability distribution $e^{-{\rm Re}\tilde{S}}$, and the remaining phase is
reweighted. In other words the expectation value of an operator is computed as

$\langle{\cal O}\rangle=\frac{1}{Z}{\int
d^{8V}\theta\,e^{-S_{eff}(\theta)}\,{\cal
O}}=\frac{1}{\sigma_{\vec{\lambda}}}\frac{1}{Z}_{pq}{\int
d^{8V}\theta\,e^{-{\rm Re}\tilde{S}}\,{\cal O}e^{-i{\rm
Im}\tilde{S}}}=\frac{1}{\sigma_{{\vec{\lambda}}}}{\langle{\cal O}e^{-i{\rm
Im}\tilde{S}}\rangle_{{\rm Re}\tilde{S}}}$ (22)

where $\langle\dots\rangle_{{\rm Re}\tilde{S}}$ denotes the average with
respect to the Boltzmann factor $e^{-{\rm Re}\tilde{S}}$, and the phase
quenched partition function and the average phase are given as

$\displaystyle Z_{pq}=\int d^{8V}\theta\,e^{-{\rm
Re}\tilde{S}},\quad\sigma_{\vec{\lambda}}=\langle e^{-i{\rm
Im}\tilde{S}}\rangle_{{\rm Re}\tilde{S}}\equiv\frac{\int
d^{8V}\theta\,e^{-\tilde{S}}}{\int d^{8V}\theta\,e^{-{\rm Re}\tilde{S}}}\,.$
(23)

We kept the subscript ${\vec{\lambda}}$ in the average phase to emphasize that
it explicitly depends on ${\vec{\lambda}}$, even though the partition
function, and therefore the expectation values of physical quantities do not.
We now come back to the problem of choosing the optimal manifold within our
ansatz that maximizes $\sigma_{\vec{\lambda}}$ and hence alleviates the sign
problem. As mentioned earlier, the optimal choice of ${\vec{\lambda}}$ is
determined via gradient ascent. We start from $SU(3)$ ($\lambda_{i}=0$) and
update ${\vec{\lambda}}$ according to Eq. (11) . The gradient in Eq. (11) can
be explicitly calculated as Alexandru:2018ddf

$\displaystyle{\nabla_{\vec{\lambda}}}\log|\sigma_{\vec{\lambda}}|$
$\displaystyle=$ $\displaystyle-\left\langle\int
d^{8V}\theta\,{\nabla_{\vec{\lambda}}}e^{-{\rm
Re}\tilde{S}}\right\rangle_{{\rm
Re}\tilde{S}}=\left\langle{\nabla_{\vec{\lambda}}}{\rm Re}(S_{eff}-{\rm
Tr}\log J)\right\rangle_{{\rm Re}\tilde{S}}$ (24) $\displaystyle=$
$\displaystyle\left\langle{\rm Re}\left(i\frac{\partial
S_{eff}}{\partial{\tilde{\theta}}_{i}}{\nabla_{\vec{\lambda}}}f_{i}-{\rm
Tr}(J^{-1}{\nabla_{\vec{\lambda}}}J)\right)\right\rangle_{{\rm Re}\tilde{S}}$
(25)

Therefore each gradient ascent step includes the Monte-Carlo computation of
the expectation value above which, notably, can be carried out without a sign
problem. We have simulated the theory for various parameters, both to leading
order and next-to-next-to leading order using sign optimization as outlined
above. In the next section we present our results.

##  IV Results

As explained in the previous section, the configurations on the sign optimized
manifold can be sampled by using the effective action Eq. (20) whose argument
are real $\theta_{i}$s, and reweighing the remaining phase, Eq. (22) , as
usual. We simulated the theory using a Hybrid-Monte-Carlo (HMC) algorithm hmc
where we used a standard leapfrog integrator for the evolution of the
Hamiltonian $h(\theta,p)=\tilde{S}(\theta)+p^{2}/2$, and used reflective
boundary conditions for $\theta_{1,2,3}$ chevallier:hal-01919855 . We fixed
the number of points in the Euclidean time direction to be $N_{t}=100$ which
corresponds to the cold limit. We simulated the theory both to leading order
and to next-to-next-to leading order in hopping expansion. In the former case,
we fixed the hopping parameter to $\kappa=0.01$ and in the latter we varied it
between $0$ and $0.05$. Note that the range of the chemical potential where
the fugacity, $h$, varies between $0$ and $1$ is roughly $|1-\mu|\sim 1/N_{t}$
that can be seen from Eq. (2) .

Figure 1: The average sign (left) and the Polyakov loop (right) as a function
of volume computed on the real plane and sign optimized manifold, ${\cal
M}_{\lambda}$, with 250 and 1000 gradient ascent steps. The dashed gray line
on the left denotes the exact value of the Polyakov loop.

In Fig. 1 (left) we show the average sign as a function of volume for
$\mu=0.998$, $\kappa=0.01$ and $N_{t}=100$ (which corresponds to fugacity
$h=0.45$) to leading order in the hopping expansion. Especially for larger
volumes $V=5^{3}$, and $6^{3}$ the original sign problem is bad enough where
reweighting is practically not possible anymore. With sign optimization, it is
lifted to values where reweighting is possible. To illustrate this, we plotted
the Polyakov loop for the same values on the right. The result after sign
optimization agrees with that on the real manifold, albeit with significantly
smaller error bars. The improvement in the sign problem as a function of
gradient ascent is shown in Fig. 2 where we used the same parameters as above
with volume $V=4^{3}$. Similarly, the value of the average Polyakov loop as a
function of the ascent step is shown on the right. Notice that initially the
statistical uncertainty is quite substantial due to due to the severe sign
problem. Gradient ascent indeed stabilizes the sign which in turn decreases
the statistical uncertainty in the physical observable, $\langle P\rangle$.

Figure 2:  The average sign (left) and Polyakov loop (right) as a function of
gradient ascent step for $h=0.45$ ($\kappa=0.01,\mu=0.998,N_{t}=100$) and
$V=4^{3}$. The solid lines denote the exact values of $\sigma_{SU(3)}$ and
$\langle P\rangle$.

The average sign, equation of state and the Polyakov loop as a function of the
chemical potential for volumes $5^{3}$ and $6^{3}$ are shown in Fig 3. For
both volumes without sign optimization, the sign problem is too severe as seen
from both directly from the top figures, or the error bars in the physical
observables below, density and Polyakov loop. For both volumes sign
optimization works as expected by stabilizing the sign and therefore
significantly reducing the statistical uncertainty for all values of $\mu$.
Note that the Silver Blaze phenomenon Cohen:2003kd , where the density sharply
rises when the (baryon) chemical potential reaches the baryon mass, is
correctly reproduced via sign optimization, in line with previous work on
heavy-dense QCD Langelage:2014vpa ; Attanasio:2015Cg . In our case this
happens at $\mu=1$, where recall that that the chemical potential is measured
in units of constituent quark mass.

Figure 3: The average sign, density and Polyakov loop as a function of
chemical potential for volumes $V=5^{3}$ and $6^{3}$.

Finally, in figures 4 and 5 we show the average sign, density, and Polyakov
loop as a function of $\kappa$, before (right) and after (left) sign
optimization to next-to-next-to leading order in hopping expansion. For these
simulations, we used the same form of the effective action given in Eq. (20)
and Eq. (16) where in this case $S[P(\theta)]$ in Eq. (16) is identified with
the NNLO action, $S_{NNLO}[P(\theta)]$ given in Eq. (7) .

Figure 4: The average sign as a function of the hopping parameter, next-to-
next-to leading order in the hopping expansion with (left) and without (right)
sign optimization for different values of $\mu$, $V=4^{3}$ and $N_{t}=100$.

Note that for different values of the chemical potential, the sign problem
becomes severe for different values of the hopping parameter $\kappa$ as seen
in Fig. 4. As seen from the same figure, sign optimization alleviates the sign
problem as expected even in the presence of the hopping terms. This is in
contrast with the case where the sign problem can be solved by the worm
algorithm only in to leading order (free) in hopping expansion and in parallel
with Complex Langevin which also works in either case.

Figure 5: The density and Polyakov loop as function of the hopping parameter,
next-to-next-to leading order in the hopping expansion with (left) and without
(right) sign optimization for different values of $\mu$, $V=4^{3}$ and
$N_{t}=100$.

Finally in Fig. 5 we show the dependence of the density and Polyakov loop to
the hopping parameter for the same values of the chemical potential as above.
Similar with the free case, the statistical uncertainties that arise from the
sign problem are significantly reduced by sign optimization. In order to check
the validity of our results we compared them with second order perturbation
theory. The dashed/solid lines show analytic results to first/second order
perturbation theory. These analytic results were calculated by expanding
$e^{-S_{NNLO}}$ to first (second) order in $\eta$ and evaluating the integrals
over $L_{\bf x}=\text{Tr}P_{\bf x}$ and $L^{*}_{\bf x}=\text{Tr}P_{\bf
x}^{\dagger}$ by the help of the relations

$\displaystyle\text{Tr}\frac{hP_{\vec{x}}}{1+hP_{\vec{x}}}$ $\displaystyle=$
$\displaystyle\frac{hL_{\vec{x}}+2h^{2}L^{*}_{\vec{x}}+3h^{3}}{1+hL_{\vec{x}}+h^{2}L^{*}_{\vec{x}}+h^{3}}$
(26) $\displaystyle\text{Tr}\frac{hP_{\vec{x}}}{(1+hP_{\vec{x}})^{2}}$
$\displaystyle=$
$\displaystyle\frac{hL_{\vec{x}}+4h^{2}L^{*}_{\vec{x}}+9h^{3}}{1+hL_{\vec{x}}+h^{2}L^{*}_{\vec{x}}+h^{3}}-\left(\frac{hL_{\vec{x}}+2h^{2}L^{*}_{\vec{x}}+3h^{3}}{1+hL_{\vec{x}}+h^{2}L^{*}_{\vec{x}}+h^{3}}\right)^{2}$
(27)

As expected the agreement between the sign optimized Monte-Carlo computations
and the perturbative calculations is fairly good for small values of $\kappa$.

##  V Connection with Lefschetz thimbles

Although being computationally very effective, by construction sign
optimization does not provide much physical insight in how it alleviates the
sign problem. In this section we provide a physical interpretation of the
results we presented by making a connection between the sign optimized
manifold, ${{\cal M}_{\vec{\lambda}}}$, and the Lefschetz thimbles associated
with the theory. In order to construct the Lefschetz thimbles associated with
the path integral, Eq. (5) , to compare and contrast with ${{\cal
M}_{\vec{\lambda}}}$, we first express the path integral in terms of the
eigenvalues of the Polyakov loop, $\alpha_{1}$, $\alpha_{2}$. We choose to
work with $\alpha$s instead of $\theta$s in order to visualize the connection
with the thimbles easily. The Polyakov loop in the diagonal form is given as
$P={\rm
diag}\\{e^{i\alpha_{1}},e^{i\alpha_{2}},e^{-i(\alpha_{1}+\alpha_{2})}\\}$. The
group measure for the $\alpha$ variables is a Vandermonde determinant:

$\displaystyle
V(\vec{\alpha})=\prod_{i<j}|e^{i\alpha_{i}}-e^{i\alpha_{j}}|=\sin^{2}\left(\frac{\alpha_{1}-\alpha_{2}}{2}\right)\sin^{2}\left(\frac{\alpha_{1}+2\alpha_{2}}{2}\right)\sin^{2}\left(\frac{2\alpha_{1}+\alpha_{2}}{2}\right)$
(28)

such that the partition function is expressed as

$\displaystyle Z=\int\prod_{{\bf x}}\left[d\alpha_{1,{\bf x}}d\alpha_{2,{\bf
x}}V(\alpha_{{\bf x}})\right]e^{-S[P(\vec{\alpha}_{\bf x})]}=\int
d^{2V}\alpha\,\,e^{-S_{e}[\vec{\alpha}_{\bf x}]}\,.$ (29)

Here the effective action is defined as

$\displaystyle S_{e}[\vec{\alpha}_{\bf x}]=\sum_{{\bf
x}}\left[-2\log\left(1+h{\rm Tr}P(\vec{\alpha}_{\bf
x})+h^{2}P^{\dagger}(\vec{\alpha}_{\bf x})+h^{3}\right)+\log
V(\vec{\alpha}_{\bf x})\right]$ (30)

and the Polyakov loop takes the form ${\rm
Tr}P(\vec{\alpha})=e^{i\alpha_{1}}+e^{i\alpha_{2}}+e^{-i(\alpha_{1}+\alpha_{2})}$.

The Lefschetz thimble decomposition of $Z$ can be constructed by evaluating
the holomorphic gradient flow

$\displaystyle\frac{d\alpha_{i,{\bf x}}}{d\tau}=\overline{\frac{\partial
S[\vec{\alpha}_{\bf x}]}{\partial\alpha_{i,{\bf x}}}}$ (31)

starting from $\alpha_{i,{\bf x}}\in[0,2\pi]$ and taking the formal limit
$\tau\rightarrow\infty$. Finite values of $\tau$ are associated with a family
of complex manifolds that interpolate between the original domain,
$[0,2\pi]^{2V}$, and the thimble decomposition. Following Alexandru:2015sua ,
we shall call these manifolds ”generalized thimbles”.

Since there are no interactions between different spatial points in the
leading order in hopping expansion given in Eq. (5) , the flow equation, Eq.
(31) can be solved for each spatial point, ${\bf x}$, independently. Therefore
each generalized thimble is $V$ dimensional direct product of a two
dimensional complex manifold. We solve the flow equation to generate this two
dimensional manifold for different flow times.

In order to visualize the generalized thimble, we then take a projection on
the subspace defined by $\alpha_{1}+\alpha_{2}^{*}=0$. Notably, this quantity
is “conserved” under the flow, namely

$\displaystyle\frac{d}{d\tau}(\alpha_{1}+\alpha_{2}^{*})=0\,.$ (32)

This can be seen by observing that the action, $S_{e}$, given in Eq. (30) is a
real function of $x$ and $y$ where $\alpha_{1}=-\alpha_{2}^{*}=x+iy$. The
conservation equation, Eq. (32) , then follows directly from the flow
equation, Eq. (31) .

Figure 6: The histogram of the eigenvalues of the Polyakov loop averaged over
the volume. The green stars denote the saddle points and the dashed line
represents the subspace defined by $\alpha_{1}+\alpha_{2}^{*}=0$ which we plot
the Lefschetz thimble on.

We now compare the sign optimized manifold and the generalized thimbles on the
projection on the subspace $\alpha_{1}+\alpha_{2}^{*}=0$ denoted by the dashed
black line in Fig. 6. Projections of the generalized thimbles as well as the
sign optimized manifold on this subspace are one-dimensional, which we show in
Fig. 7.

Figure 7: The comparison between the surfaces generated by holomorphic
gradient flow, approaching the Lefschetz thimble at large flow times, and the
sign optimized manifold, plotted on the subspace defined by
$\alpha_{1}+\alpha_{2}^{*}=0$. The stars denote the saddle points that lie on
this subspace (see Fig 6)

Firstly, it can be seen that the generalized thimbles converge into the the
thimble decomposition with increasing flow time as expected. Secondly, there
are multiple complex saddle points, hence multiple thimbles, which contribute
to the thimble decomposition. There are two saddle points on the subspace that
we focus on (those that intersect the dashed line in Fig. 6), but the other
saddle points contribute equally as well since ${\rm Re}\,S_{e}$ (hence the
path integral weight) on each saddle point is equal. Thirdly, the sign
optimized manifold approximately reconstructs the thimble, especially around
the saddle points where most of the contribution to the path integral comes
from.

We would like to point out that in general, sampling multi-model distributions
like this could be present challenges as the Markov chain could get stuck in a
local minimum. The generalized thimble approach is susceptible to this
phenomenon as the relevant support of each thimble in the sampled field space,
${\rm Re}\,\alpha$, shrinks with increasing flow time as pictured in Fig. 8.
As a result transitioning from one such region to another becomes more
difficult. The sign optimization, however, does not. This follows directly
from the form of the parameterization given in Eq. (21) as ${\rm
Im}\,\alpha_{i}$ is expressed as a function of ${\rm Re}\,\alpha_{i}$, so that
the size of the relevant region in the sampled field space remains the same
Alexandru:2020wrj . Finally, the Jacobian associated with the sign
optimization ansatz, Eq. (19), is fairly simple and can be analytically
calculated, as opposed to the Jacobian associated with holomorphic gradient
flow which has to be numerically evaluated, introducing extra computational
cost.

Figure 8: The parameterization of the generalized thimbles (left) and the sign
optimized manifold (right) in terms of the real fields (bars). For thimbles,
with increasing flow time the relevant region in the real filed space that is
sampled shrinks into small, disconnected regions leading to multimodal
distribution in contrast to sign optimization.

##  VI Conclusions

We simulated the heavy-dense effective theory of QCD at finite density by
using sign optimization to alleviate the sign problem. The optimal complex
domain for the path integral is chosen within a family of anstaze via a
gradient ascent algorithm. Building up on our previous observation from one-
dimensional QCD, we used the “mixing” ansatz for the complexified manifold
which is constructed to capture the fluctuations of fields around the complex
saddle points. We have simulated the theory for different values of the
hopping parameter, volume and chemical potential both to leading order and
next-to-next-to leading order in the hopping expansion. Notably the sign
problem in the latter case cannot be solved via worm algorithm as opposed to
the former case DelgadoMercado:2012gta . We observed that the sign
optimization method can handle both cases with comparable amount of
computational resources. We also demonstrated that sign optimization works
successfully for volumes $4^{3}$, $5^{3}$, and $6^{3}$ where the sign problem
is too severe to overcome with usual reweighing.

Even though sign optimization is demonstrated to be an efficient way to
alleviate the sign problem, it is not transparent how it does it; i.e. it does
not provide much of physical insight. This is, of course, a generic property
of optimization algorithms. We showed that sign optimization in fact in a way
reconstructs the Lefschetz thimbles (a multi-dimensional generalization of
stationary phase contours) around the complex saddle points of the theory.
Similar phenomena has been observed before Alexandru:2018fqp . In this paper
we explicitly compared the Lefschetz thimble and the sign optimized manifold
and showed that they indeed overlap especially in the vicinity of the saddle
points. This comparison further solidifies the observation of the similarity
between the Lefschetz thimbles emanating from the complex saddles of the
theory and the sign optimized manifold made in one-dimensional QCD
Basar:2022cef . As a result, one might view sign optimization is a method to
construct an approximation to the Lefschetz thimbles. However, the there are
advantages of using sign optimization instead of directly sampling the
(generalized) Lefschetz thimbles. Firstly, the parameterization of the sign
optimized manifold does not require a numerical computation of the Jacobian as
opposed to thimbles as it can be performed analytically, reducing the
computational cost. Secondly sampling the sign optimized manifold does not
lead to severe multi-modal distributions, which are difficult to sample as
opposed to the thimbles.

We performed sign optimization within a family of complex manifolds which are
parameterized by a fairly generic ansatz that can in principle be applied to
an arbitrary theory whose degrees of freedom take value in $SU(3)$. This
generality comes with a cost, however. Finding a generic solution to the sign
problem is an NP hard problem Troyer:2004ge , therefore any generic ansatz,
such as we used, will still lead to an exponentially hard problem. Of course,
even reducing the exponent lead be practically useful results as we
demonstrated here. At the same time, by using certain properties of the
underlying theory such as symmetries or perhaps some other knowledge such as
complex saddle points, one could consider a more specific ansatz tailored for
the specific theory in mind. In this case, there is no a-priori reason for the
sign problem to be exponentially hard. Here, we took the first step in
relating the sign optimized manifolds to the complex saddle points and the
fluctuations around them. The natural next step is to improve the
complexification ansatz by using some analytical information based on these
observations, which is left for future work.

###### Acknowledgements.

GB is supported by the National Science Foundation CAREER Award PHY-2143149.

## References

  * (1) HotQCD Collaboration, A. Bazavov et al., “Equation of state in ( 2+1 )-flavor QCD,” Phys. Rev. D 90 (2014) 094503, arXiv:1407.6387 [hep-lat].
  * (2) S. Borsányi, Z. Fodor, C. Hoelbling, S. D. Katz, S. Krieg, and K. K. Szabó, “Full result for the qcd equation of state with 2+1 flavors,” Physics Letters B 730 (2014) 99–104. https://www.sciencedirect.com/science/article/pii/S0370269314000197.
  * (3) P. de Forcrand, “Simulating qcd at finite density,” 2010.
  * (4) O. Philipsen, “Lattice qcd at finite temperature and density,” The European Physical Journal Special Topics 152 no. 1, (2007) 29–60. https://doi.org/10.1140/epjst/e2007-00376-3.
  * (5) F. Karsch, “Lattice qcd at finite temperature and density,” Nuclear Physics B - Proceedings Supplements 83-84 (2000) 14 – 23. http://www.sciencedirect.com/science/article/pii/S0920563200915913. Proceedings of the XVIIth International Symposium on Lattice Field Theory.
  * (6) G. Aarts, “Introductory lectures on lattice qcd at nonzero baryon number,” Journal of Physics: Conference Series 706 (Apr, 2016) 022004. http://dx.doi.org/10.1088/1742-6596/706/2/022004.
  * (7) F. Pham, “Vanishing homologies and the n variable saddlepoint method,” Methods Appl. Anal. 1 Part 2 (1983) .
  * (8) S. Lefschetz, Applications of Algebraic Topology. Graphs and Networks. the Picard-Lefschetz Theory and Feynman Integrals.  1, 1975.
  * (9) AuroraScience Collaboration, M. Cristoforetti, F. Di Renzo, and L. Scorzato, “New approach to the sign problem in quantum field theories: High density QCD on a Lefschetz thimble,” Phys. Rev. D 86 (2012) 074506, arXiv:1205.3996 [hep-lat].
  * (10) M. Cristoforetti, L. Scorzato, and F. Di Renzo, “The sign problem and the Lefschetz thimble,” arXiv:1210.8026 [hep-lat]. [J. Phys. Conf. Ser.432,012025(2013)].
  * (11) H. Fujii, D. Honda, M. Kato, Y. Kikukawa, S. Komatsu, and T. Sano, “Hybrid Monte Carlo on Lefschetz thimbles - A study of the residual sign problem,” JHEP 10 (2013) 147, arXiv:1309.4371 [hep-lat].
  * (12) A. Alexandru, G. Basar, P. F. Bedaque, and N. C. Warrington, “Complex paths around the sign problem,” Rev. Mod. Phys. 94 no. 1, (2022) 015006, arXiv:2007.05436 [hep-lat].
  * (13) Y. Mori, K. Kashiwa, and A. Ohnishi, “Toward solving the sign problem with path optimization method,” Phys. Rev. D 96 no. 11, (2017) 111501, arXiv:1705.05605 [hep-lat].
  * (14) A. Alexandru, P. F. Bedaque, H. Lamm, and S. Lawrence, “Finite-Density Monte Carlo Calculations on Sign-Optimized Manifolds,” Phys. Rev. D 97 no. 9, (2018) 094510, arXiv:1804.00697 [hep-lat].
  * (15) K. Kashiwa, Y. Mori, and A. Ohnishi, “Application of the path optimization method to the sign problem in an effective model of QCD with a repulsive vector-type interaction,” Phys. Rev. D99 no. 11, (2019) 114005, arXiv:1903.03679 [hep-lat].
  * (16) W. Detmold, G. Kanwar, H. Lamm, M. L. Wagman, and N. C. Warrington, “Path integral contour deformations for observables in $SU(N)$ gauge theory,” Phys. Rev. D 103 no. 9, (2021) 094517, arXiv:2101.12668 [hep-lat].
  * (17) K. Zambello and F. Di Renzo, “Towards Lefschetz thimbles regularization of heavy-dense QCD,” PoS LATTICE2018 (2018) 148, arXiv:1811.03605 [hep-lat].
  * (18) F. Attanasio, G. Aarts, B. Jaeger, E. Seiler, D. Sexty, and I.-O. Stamatescu, “Exploring the phase diagram of QCD with complex Langevin simulations,” PoS LATTICE2014 (2015) 200.
  * (19) G. Aarts, F. Attanasio, B. Jäger, and D. Sexty, “The QCD phase diagram in the limit of heavy quarks using complex Langevin dynamics,” JHEP 09 (2016) 087, arXiv:1606.05561 [hep-lat].
  * (20) G. Basar and J. Marincel, “Sign optimization and complex saddle points in one-dimensional QCD,” Phys. Rev. D 106 no. 9, (2022) L091503, arXiv:2208.02072 [hep-lat].
  * (21) M. Fromm, J. Langelage, S. Lottini, and O. Philipsen, “The QCD deconfinement transition for heavy quarks and all baryon chemical potentials,” JHEP 01 (2012) 042, arXiv:1111.4953 [hep-lat].
  * (22) M. Fromm, J. Langelage, S. Lottini, M. Neuman, and O. Philipsen, “Onset Transition to Cold Nuclear Matter from Lattice QCD with Heavy Quarks,” Phys. Rev. Lett. 110 no. 12, (2013) 122001, arXiv:1207.3005 [hep-lat].
  * (23) J. Langelage, M. Neuman, and O. Philipsen, “Heavy dense QCD and nuclear matter from an effective lattice theory,” JHEP 09 (2014) 131, arXiv:1403.4162 [hep-lat].
  * (24) A. Alexandru, P. F. Bedaque, H. Lamm, S. Lawrence, and N. C. Warrington, “Fermions at Finite Density in 2+1 Dimensions with Sign-Optimized Manifolds,” Phys. Rev. Lett. 121 no. 19, (2018) 191602, arXiv:1808.09799 [hep-lat].
  * (25) Y. Mori, K. Kashiwa, and A. Ohnishi, “Path optimization in $0+1$D QCD at finite density,” PTEP 2019 no. 11, (2019) 113B01, arXiv:1904.11140 [hep-lat].
  * (26) J. B. Bronzan, “Parametrization of SU(3),” Phys. Rev. D 38 (1988) 1994.
  * (27) S. Brooks, A. Gelman, G. Jones, and X.-L. Meng, eds., Handbook of Markov Chain Monte Carlo.  Chapman and Hall/CRC, May, 2011.  https://doi.org/10.1201%2Fb10905.
  * (28) A. Chevallier, S. Pion, and F. Cazals, “Hamiltonian Monte Carlo with boundary reflections, and application to polytope volume calculations,” Research Report RR-9222, INRIA Sophia Antipolis, France, Nov., 2018.  https://hal.science/hal-01919855.
  * (29) T. D. Cohen, “Functional integrals for QCD at nonzero chemical potential and zero density,” Phys. Rev. Lett. 91 (2003) 222001, arXiv:hep-ph/0307089 [hep-ph].
  * (30) A. Alexandru, G. Basar, P. F. Bedaque, G. W. Ridgway, and N. C. Warrington, “Sign problem and Monte Carlo calculations beyond Lefschetz thimbles,” JHEP 05 (2016) 053, arXiv:1512.08764 [hep-lat].
  * (31) Y. Delgado Mercado and C. Gattringer, “Monte Carlo simulation of the SU(3) spin model with chemical potential in a flux representation,” Nucl. Phys. B 862 (2012) 737–750, arXiv:1204.6074 [hep-lat].
  * (32) M. Troyer and U.-J. Wiese, “Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations,” Phys. Rev. Lett. 94 (2005) 170201, arXiv:cond-mat/0408370 [cond-mat].