∎

11institutetext: 1 Max Planck Institute for Intelligent Systems, Tübingen,
Germany
2 University of California, San Diego, CA 92093, USA
${}^{\textrm{{\char 0\relax}}}$11email<EMAIL_ADDRESS>

# Automatic discovery and description of human planning strategies

Julian Skirzyński1,2, ${}^{\textrm{{\char 0\relax}}}$ Yash Raj Jain1 Falk
Lieder1

(Received: date / Accepted: date)

###### Abstract

Scientific discovery concerns finding patterns in data and creating insightful
hypotheses that explain these patterns. Traditionally, each step of this
process required human ingenuity. But the galloping development of computer
chips and advances in artificial intelligence (AI) make it increasingly more
feasible to automate some parts of scientific discovery. Understanding human
planning is one of the fields in which AI has not yet been utilized. State-of-
the-art methods for discovering new planning strategies still rely on manual
data analysis. Data about the process of human planning is often used to group
similar behaviors together. Researchers then use this data to formulate verbal
descriptions of the strategies which might underlie those groups of behaviors.
In this work we leverage AI to automate these two steps of scientific
discovery. We introduce a method for the automatic discovery and description
of human planning strategies from process-tracing data collected with the
Mouselab-MDP paradigm. Our algorithm, called Human-Interpret, uses imitation
learning to describe data gathered in the experiment in terms of a procedural
formula and then translates that formula to natural language using a pre-
defined predicate dictionary. We test our method on a benchmark data set that
researchers have previously scrutinized manually. We find that the
descriptions of human planning strategies that we obtain automatically are
about as understandable as human-generated descriptions. They also cover a
substantial proportion of all types of human planning strategies that had been
discovered manually. Our method saves scientists’ time and effort as all the
reasoning about human planning is done automatically. This might make it
feasible to more rapidly scale up the search for yet undiscovered cognitive
strategies that people use for planning and decision-making to many new
decision environments, populations, tasks, and domains. Given these results,
we believe that the presented work may accelerate scientific discovery in
psychology, and due to its generality, extend to problems from other fields.

Keywords: automatic scientific discovery; decision making; planning;
interpretable strategy discovery; process-tracing; computational methods; data
analysis

††journal: Behavior Research Methods

##  1 Introduction

Scientific discovery is a product of scientific inquiry that allows generating
and corroborating new insightful hypotheses. In the early days, scientific
discovery has been seen as a prescriptive method for arriving at new
knowledge, by gathering information and refining it with new experiments (see
Bacon’s _Novum Organum_ (Bacon and In Fowler, 1878) or Newton’s _Philosophiae
Naturalis Principia Mathematica_ (Newton, 1687)). More established
philosophical tradition argued that there exists a clear demarcation between
the so called context of discovery and the context of justification (Whewell,
1840; Reichenbach, 1938; Popper, 1935). The former would be a product of
logically unfathomable mental process: the "eureka" moment, that if anything,
could be rather studied by psychology. The latter would concern the proper
verification and justification of the discovered theory and would indeed have
a formal structure. However, such an account leaves scientists at the mercy of
having a eureka moment. This division was thus challenged. Kuhn (1962), for
instance, saw scientific discovery as a complex process of paradigm changes
where increasing amounts of findings that disagree with the current paradigm
lead to its change. The discovery involves gathering the anomalous data and
finding a hypothesis that explains it, for instance through abduction (Hanson,
1965), so reasoning from data to the most probable, simplest explanation.
Importantly for this work, this division was also challenged by early work on
AI for problem solving (Simon and Newell, 1971; Simon, 1973). Therein,
discovery was understood as searching the problem space from the initial state
representing current knowledge to a desirable goal state. The states
transition from one to another by applying simple operators with a predefined
meaning. The process of finding the shortest sequence of applied operators
would create rules that could later be looked at by a human to determine what
search heuristic has been used. The found search heuristic would determine the
method for scientific discovery. Regardless of whether you agree with the
distinction between discovery versus justification, these works showed that
some steps involved in scientific discovery can be automated. Further work in
such automation moved beyond the philosophical debate with the main motivation
becoming to aid scientists in their research (Addis et al., 2016).

One line of research involves the field of computational scientific discovery
(Džeroski et al., 2007; Sozou et al., 2017) which models the discovery problem
mathematically and advances the discovery of laws or relations using
artificial intelligence (AI). BACON (Langley et al., 1987), for instance, was
a system for inducing numeric laws from experimental data. Having dependent
and independent variables, it created taxonomies of these variables by
clustering equally-valued dependent variables and defining new variables as
products or ratios of independent variables. Then, Langley et al. 1983)
created GLAUBHER that was formulating qualitative laws over the categories in
the taxonomy, and STAHL which produced structural theories based on the data
leading to anomalous behavior of existing theories (c.f. Kuhn (1962)). Addis
et al. (2016) suggested to represent theories as programs and use genetic
search for best theories. Other systems such as PHINEAS, COAST or IDS are
described at length in a review paper by Shrager and Langley (1990). An
overview work by Džeroski et al. (2007) shows an extension of this field to
mathematical modeling: the background knowledge is represented as generic
processes, the data takes form of time-series, and discovery takes place by
deriving sets of explanatory differential equations.

Another line of research which used AI to help scientists in their endeavors
was automatic experimental design. This approach follows the mathematical
foundations of design optimization, in which the expected information gain of
an experiment defines its usefulness in testing a hypothesis (Myung et al.,
2013). Vincent and Rainforth (2017) used this approach to automate the
creation of intertemporal choice experiments and risky choice experiments.
Ouyang et al. (2016; 2018) went a step further and created a system to
automatically find informative scientific experiments in general. Their method
expected a formal experiment space, expressed in terms of a probabilistic
program as input and returned a list of experiments ranked by their expected
information gain. The experiment that was the highest on that list would
provably provide the most information to differentiate between competing
hypotheses. Foster et al. (2019) further refined the whole idea by introducing
efficient expected information gain estimators.

In this article, we introduce a computational method for assisting scientists
in studying human planning. Understanding how people plan is a difficult and
time-consuming endeavor. Previous efforts to figure out which strategies and
processes people use to make decisions and plan usually entailed manual
analysis of the data (Payne et al., 1993; Willemsen and Johnson, 2011;
Callaway et al., 2017, 2020). The very act of finding the strategies has been
thus left to researchers’ ingenuity to discover the right patterns in the
data. Moreover, previous work has largely failed to characterize people’s
strategies in detail (but see Jain et al., 2021; Agrawal et al., 2020;
Peterson et al., 2021). The case for using AI in the quest of understanding
human planning has been made for one-shot decision-making scenarios (Agrawal
et al., 2020; Bhatia and He, 2021; Peterson et al., 2021). Agrawal et al.
(2020) fit simple models to the data and optimized them with respect to the
regret obtained by comparing simple models’ predictions to overly complex
models’ predictions. After the simple models’ predictions converged to those
of the complex models, they were used as a proper formalization of one-shot
human decision strategies. Peterson et al. (2021) employed artificial neural
networks to search for theories of one-shot decision-making. At first, they
created a taxonomy of theories that expressed relations between available
decision items (such as gambles, and whether the gambles are dependent or
independent), and which covered the entire space of possible decision-making
theories. Subsequently, they used neural networks to express those theories by
imposing different constraints on those networks. The authors gathered a very
large data set of human decisions and determined which theory is the best fit
based on the networks’ performance. To study human planning behavior, Jain et
al., (2021) used a similar approach of first collecting human data and then
finding models that best explain the human data. To address the challenge that
the cognitive operations of planning (or decision-making in general) cannot be
observed directly they used the Mouselab-MDP process-tracing paradigm to
externalize human planning operations as information gathering operations
Callaway et al.; Callaway et al.. Their approach to modeling the observed
planning behavior was to first manually go through all the click sequences
participants generated in the paradigm and then create a set of planning
strategies that the researchers subjectively found the participants to be
using. These planning strategies were then used as an input to their method
known as the Computational Microscope which then infers which strategy was
used by which participant in which trial. Here, we go two steps further
compared to the mentioned papers. We consider the issue of i) discovering
detailed human multi-step decision strategies, that is planning strategies,
ii) discovering them from data automatically without creating the initial
model , whether a complex black-box model (Agrawal et al., 2020), a taxonomy
of decision-making theories (Peterson et al., 2021), or a set of possible
planning strategies (Jain et al., 2021).

In more detail, we introduce a new computational method for automatically
discovering human planning strategies from the data collected in experiments
that externalize planning operations as information gathering111For a detailed
description of this experimental paradigm, see Section 2.2.. We call this
algorithm Human-Interpret. On a high-level Human-Interpret tries to imitate
behaviors from the data gathered in experiments measuring planning, having
specified candidates on the number of strategies to be found (from $x$ to $y$
strategies), and having a vocabulary of logical primitives for constructing
descriptions of those strategies. Specifically, it performs probabilistic
clustering on the set of planning operations observed in the experiment(s) to
obtain $n$ probability distributions that assign probabilities to planning
actions conditioned on knowledge states. Then it samples demonstrations of
planning operations from those clusters, creates a set of predicates, and uses
a method called AI-Interpret (Skirzyński et al., 2021) to describe the
demonstrated strategy by a logical formula. In the next step, Human-Interpret
uses the method from (Becker et al., 2021) to increase the interpretability of
the output by transforming it into a procedural formula written in a special
type of logic. In the penultimate step, Human-Interpret shortens the resulting
formulas with a greedy algorithm, and in the last step it translates the
formula into natural language using a predefined predicate-to-expression
dictionary. To evaluate our approach and, particularly, the Human-Interpret
algorithm, we applied it to a planning task where one has to spend money on
clicking nodes in a graph to find the most rewarding path to traverse. Our
method generated descriptions of human planning strategies that are on par
with the descriptions created through laborious manual analysis by Jain et al.
(2021). Our method automatically discovered roughly the same set of relevant
planning strategies and generated straightforward, informative descriptions of
those strategies, while saving time and effort. Our approach can be easily
extended to other problems, such as multi-alternative risky-choice (Lieder et
al., 2017; Peterson et al., 2021), by simply running new studies and creating
a new set of logical primitives. Given these results, we believe that the
presented work has the potential to greatly facilitate scientific discovery in
psychology and perhaps revolutionize scientific discovery in general.
Scientists can now use the help of AI not only for testing their hypotheses
about how people make decisions but also for generating them.

The outline of the article is as follows: We begin by providing background
information and summarizing related work pertaining to our method and the
benchmark problem used in Section 2. In the next section, we describe the
whole pipeline of our method for the automatic discovery and description of
human planning strategies. Section 4 shows the results of our test on the
benchmark problem where we compare our automated pipeline with a standard
manual approach. Lastly, Section 5 discusses opportunities for applying our
method and directions for future work.

##  2 Background and related work

In this section we present the methodology used to measure planning adapted in
our studies and a state-of-the-art approach for discovering human planning
strategies that we compared to. Additionally, we describe an important part of
our framework for automatic scientific discovery, that is an algorithm that
describes planning strategies in an interpretable way by only using
demonstrations of these strategies.

###  2.1 Definitions

Here, we introduce definitions for important notions used in the next
sections. The first definition presents a foundational concept for both our
methodology and the benchmark problem we used. Definitions 2-4 connect to the
formal definitions of planning strategies that we employed in our research.
The last 3 definitions refer to Human-Interpret: what it means to be an
imitation learning algorithm, what is the formalization of Human-Interpret’s
intermediate output, and what is the formalization of its final output.

######  Definition 1 (Markov Decision Process)

A Markov decision process (MDP) is a tuple
$(\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R},\gamma$) where $\mathcal{S}$
is a set of states; $\mathcal{A}$ is a set of actions;
$\mathcal{T}(s,a,s^{\prime})=\mathbb{P}(s_{t+1}=s^{\prime}\mid
s_{t}=s,a_{t}=a)$ for $s\neq s^{\prime}\in\mathcal{S},a\in\mathcal{A}$ is a
state transition function; $\gamma\in(0,1)$ is a discount factor;
$\mathcal{R}:\mathcal{S}\to\mathbb{R}$ is a reward function.

######  Definition 2 (Policy)

A deterministic policy $\pi$ is a function
$\pi:\mathcal{S}\rightarrow\mathcal{A}$ that controls agent’s behavior in an
MDP and a nondeterministic policy $\pi$ is a function
$\pi:\mathcal{S}\rightarrow Prob(\mathcal{A})$ that defines a probability
distribution over the actions in the MDP.

######  Definition 3 (Expected reward)

The reward $r_{t}$ represents the quality of performing action $a_{t}$ in
state $s_{t}$. The cumulative return of a policy is a sum of its discounted
rewards obtained in each step of interacting with the MDP, i.e.
$G_{t}^{\pi}=\sum\limits_{i=t}^{\infty}\gamma^{t}r_{t}$ for $\gamma\in[0,1]$.
The expected reward $J(\pi)$ of policy $\pi$ is equal to
$J(\pi)=\mathbb{E}(G_{0}^{\pi})$.

######  Definition 4 (Reinforcement learning)

Reinforcement learning (RL) is a class of methods that perform iterations over
trials and evaluation on a given MDP in order to find the optimal policy
$\pi^{*}$ which maximizes the expected reward (Sutton and Barto, 2018).

######  Definition 5 (Imitation learning)

Imitation learning (IL) is the problem of finding a policy $\hat{\pi}$ that
mimicks transitions provided in a data set of trajectories
$\mathcal{D}=\\{(s_{i},a_{i})\\}_{i=1}^{M}$ where
$s_{i}\in\mathcal{S},a_{i}\in\mathcal{A}$ (Osa et al., 2018).

######  Definition 6 (Disjunctive Normal Form)

Let $f_{i,j},h:\mathcal{X}\rightarrow\\{0,1\\},i,j\in\mathbb{N}$ be binary-
valued functions (predicates) on domain $\mathcal{X}$. We say that $h$ is in
disjunctive normal form (DNF) if the following property is satisfied:

$\displaystyle h(\bm{x})=(f_{1,1}(\bm{x})\land...\land
f_{1,n_{1}}((\bm{x}))\lor...\lor(f_{m,1}((\bm{x})\land...\land
f_{m,n_{m}}((\bm{x}))$ (1)

and $\forall i,j_{1}\neq j_{2},\ f_{i,j_{1}}\neq f_{i,j_{2}}$. In other words,
$h$ is a disjunction of conjunctions.

######  Definition 7 (Linear Temporal Logic)

Let $\mathcal{P}$ be the set of propositional variables $p$ (variables that
can be either true or false), let $\lnot,\land,\lor$ be standard logical
operators for negation, AND, and OR, respectively, and let
$\mathbf{X},\mathbf{U},\mathbf{W}$ be modal operators for NEXT, UNTIL, and
UNLESS, respectively. Linear temporal logic (LTL) is a logic defined on
(potentially infinite) sequences of truth-assignments of propositional
variables. LTL formulas are expressions that state which of the variables are
true, and when they are true in the sequences. Whenever this agrees with the
actual truth-assignment in an input sequence, then we say that a formula is
true.

Formally, for $\alpha$ and $\beta$ being LTL formulas, we define a formula to
be expressed in LTL inductively: $\psi$ is an LTL formula if
$\psi\in\mathcal{P}$ ($\psi$ states that one of the variables is true in the
first truth-assignment in the sequence), $\psi=\lnot\alpha$ ($\psi$ is a
negation of an LTL formula), $\psi=\alpha\lor\beta$ ($\psi$ is a disjunction
of two LTL formulas), $\psi=\alpha\land\beta$ ($\psi$ is a conjunction of two
LTL formulas), $\psi=\mathbf{X}\alpha$ ($\psi$ states that LTL formula
$\alpha$ is true starting from the next truth-assignment in the sequence) or
$\psi=\alpha\mathbf{U}\beta$ ($\psi$ states that LTL formula $\alpha$ is true
until some truth-assignment in the sequence where LTL formula $\beta$ becomes
true).

###  2.2 Methods for measuring how people plan

People’s planning for years has been an evanescence process that lacked
principled analysis tools. To study planning, psychologists firstly focused on
one-step decisions and most often relied on educated guesses, i.e. self-
constructed mathematical models of human behavior that captured the
relationship between inputs and outputs of decision-making (Abelson and Levi,
1985; Westenberg and Koele, 1994; Ford et al., 1989). These methods were not
error-proof because they sometimes fit conflicting models equally well to the
same data or were too limited to capture the whole decision-making process
(Ford et al., 1989; Riedl et al., 2008). To mitigate these drawbacks,
scientists have developed _process-tracing_ methods that captured the process
used in decision-making by also analyzing the context in which each of the
steps were taken before reaching a decision (Payne et al., 1978; Svenson,
1979). Among multiple process-tracing paradigms, such as verbal protocols
(e.g. in Newell et al. (1972)) or conversational protocols (e.g. in Huber et
al. (1997)), some process-tracing paradigms were computerized and followed
human choices by facing people with artificial tasks which required them to
take a series of actions before making the final decision. One such process-
tracing paradigm called the Mouselab (Payne et al., 1988) paradigm which is
used for one-step decision making tasks was later adapted for studying
planning under the name of Mouselab-MDP (Callaway et al., 2017) paradigm.
Since we used this methodology in our framework for automatic scientific
discovery for planning, we now introduce the Mouselab and Mouselab-MDP
paradigms in more detail. At the end, we also introduce a state-of-the-art
approach for scientific discovery for planning that uses Mouselab-MDP. Since
it relies on manual analysis of data, we treat it as a baseline throughout
this paper.

####  2.2.1 Mouselab

The Mouselab (Payne et al., 1988) paradigm is one of the first computerized
process-tracing paradigms. Its goal is to externalize some aspects of
cognitive processes taking part in decision-making by engaging people in
information acquisition that helps them reach a decision. Mouselab was
developed to study multi-alternative risky choice. To do so, it presents
participants with an initially occluded payoff matrix whose entries can be
(temporarily) revealed by clicking on them. An $i,j$ entry of the $n\times m$
payoff matrix either hides a value for bet $i$ under outcome $j$, or, in the
case of the first row, hides a probability for outcome $j$. The values are
expressed in terms of dollars and they indicate the payoff a participant is
expected to obtain after selecting gamble $i$ and having outcome $j$ to occur.
Participant’s task is to choose one of the available $i-1$ gambles based on
the information they gathered by revealing the entries of the matrix. The
sequence of clicks externalizes a participant’s decision-making process by
showing which information they considered. Using the Mouselab paradigm,
scientists were able to discover that people choose strategies adaptively
(Payne et al., 1988). Despite its usefulness, however, Mouselab is
inappropriate to study planning as selecting one gamble does not affect future
gambles. Mouselab-MDP was developed to mitigate this shortcoming.

####  2.2.2 Mouselab-MDP

The Mouselab-MDP paradigm is a generalization of the Mouselab process-tracing
paradigm in which participant’s information-acquisition actions affect the
availability of his or her future choices (Callaway et al., 2017). By doing so
and offering a way to externalize information-acquisition, Mouselab-MDP is
suitable to study human planning. Concretely, a single decision about choosing
a gamble is replaced with a Markov Decision Process (MDP), and the payoff
matrix is replaced with a graphical representation of the MDP, a directed
graph with initially occluded nodes. Clicking on the node reveals a numerical
reward or punishment hidden underneath it (see Figure 1). In the most commonly
used setting of the Moueslab-MDP paradigm, a participant’s goal is to find the
most rewarding path for an agent to traverse from the start node to one of the
terminal nodes (nodes without any out-going connections), by minimizing the
number of clicks (each click has an associated cost). This formulation was
used in a number of papers that studied human planning strategies (Griffiths
et al., 2019; Callaway et al., 2020) and led to the creation of cognitive
tutors that help people plan better (Lieder et al., 2019, 2020), the creation
of new, scalable and robust algorithms for hierarchical reinforcement learning
(Kemtur et al., 2020; Consul et al., 2021), and helped in creating one of the
first tools for analyzing human planning in more detail (Jain et al., 2021).

Figure 1: The Mouselab-MDP environment we used in the paper. The environment
is a connected graph of nodes (grey circles) that hide rewards or punishments.
The number hidden underneath a node can be uncovered by clicking on it and
paying a small fee. The goal is to traverse a path starting in the black node
and ending in a node at the highest level so that the sum of rewards along the
way minus the cost of clicking was as high as possible.

####  2.2.3 Categorizing planning strategies via the computational microscope

The Mouselab-MDP paradigm gives information about the planning processes used
by people (Callaway et al., 2020, 2017). Past research, similarly to the
research on describing human decision-making, employed formal planning models
(i.e. strategies) to describe the planning processes of people, and evaluated
those models on data from experiments with human participants, e.g. (Botvinick
et al., 2009; Huys et al., 2012, 2015; Callaway et al., 2018, 2020).
Researchers have come up with a number of planning models people could
hypothetically use, including classic models of planning such as Breadth First
Search, Depth First Search, models that use satisficing, etc. Recently, Jain
et al. (2021) created a new computational pipeline in which a set of manually
created planning strategies are given as an input to a computational method,
called the computational microscope, to fit them to human planning data. In
more detail, the method takes process-tracing data generated using the
Mouselab-MDP paradigm and categorizes the planning operations from trials of
the Mouselab-MDP paradigm into a sequence of these planning strategies. One of
its features is that, to categorize a trial, it incorporates all the
information from all the trials before and after it. The authors of the paper
performed manual inspection of all the process-tracing data (clicks) that
participants made in each trial. They first found out similar clicks sequences
based the trials and the features of the trial and then created generalized
strategies that replicated these click sequences. This led to the creation of
a set of 79 strategies.

One of the drawbacks of their method is the amount of time it took them to
manually go through all the participants data and the scalability of their
approach. Since our method aims to develop a method for automatic
interpretation of the process-tracing data, which includes automatic discovery
of the planning strategies, we treat their set of planning strategies and
their approach as a baseline to compare our framework to.

###  2.3 Finding interpretable descriptions of formal planning strategies
(policies): AI-Interpret

Part of our framework utilizes a variant of an algorithm developed to
interpret reinforcement learning (RL) policies: AI-Interpret (Skirzyński et
al., 2021). In contrast to existing methods for intepretability in RL that
generate complex outputs: decision trees with algebraic constraints (Liu et
al., 2018), finite-state automata (Araki et al., 2019), or programs (Verma et
al., 2018) to represent policies, AI-Interpret generates simple and shallow
disjunctive normal form formulas (DNFs; equivalent to decision trees) that
express the strategy in terms of pre-defined logical predicates. Studies
presented in Skirzyński et al. (2021) show that transforming this output into
flowcharts, which use natural language instead of the predicates, is easily
understood by people, and can even help in improving their planning skills.
Moreover, AI-Interpret is an imitation learning method and interprets policies
via their demonstrations. Due to these reasons, we decided to use it in order
to achieve our goal: find descriptions of human planning strategies by using
data from process-tracing experiments.

On a high-level, AI-Interpret uses 4 inputs. If $\mathcal{S}$ is a set of
states and $\mathcal{A}$ is a set of actions in a given environment, AI-
Interpret accepts a data set of demonstrations (state-actions pairs)
$\mathcal{D}=\\{(s_{i},a_{i})\\}_{i=1}^{N},s_{i}\in\mathcal{S},a_{i}\in\mathcal{A}$
generated by some policy $\pi$, set of predicates $\mathcal{L}$ that act as
feature detectors $f:\mathcal{S}\times\mathcal{A}\rightarrow\\{0,1\\}$, a
maximum depth of the DNF (decision tree) $d$, and the ratio of the expected
rewards $\alpha$. AI-Interpret uses $\mathcal{D}$ and $\mathcal{L}$ to find
DNF formula $\psi$ of size at most $d$ that induces a policy $\pi_{\psi}$ with
an expected reward of at least $\alpha$ of $\pi$’s expected reward. It does so
by transforming each state-action pair in $\mathcal{D}$ into a vector of
predicate valuations and clustering the set of these vectors into coherent
groups of behaviors. In each iteration, the clustered vectors are used as
positive examples for a DNF learning method and suboptimal state-action pairs
generated by looking at possible actions in existing states, serve as negative
examples. The DNF learning method is called Logical Program Policies (LPP;
(Silver et al., 2020)) and defines a prior distribution for the predicates in
$\mathcal{L}$ and uses the MAP estimation and decision-tree learning methods
to find the most probable DNF formulas that accept the positive examples and
reject the negative examples. AI-Interpret uses LPP to find DNF $\psi$ that
achieves the proper expected reward defined by $\alpha$ and has depth limited
by $d$, and in case of a failure, removes the least promising cluster (the
smallest weighted posterior) to try describing the remaining data.

##  3 A new method for discovering and describing human planning strategies

We created a method that enables (cognitive) scientists to generate
descriptions of human planning strategies using data from sequential decision-
making experiments conducted with the Mouselab-MDP paradigm (Callaway et al.,
2020, 2017). As illustrated in Figure 2, our method comprises the following
steps: 1) collecting and pre-processing process-tracing data on human
planning, 2) setting up a vocabulary of logical predicates that can be used to
describe people’s strategies, 3) running our new algorithm to automatically
discover how many different strategies people used and what those strategies
are. Our method automatically describes the discovered strategies as step-by-
step procedures. The first three subsections describe each of these three
steps in turn. We also detail the algorithm itself. The last section reports
on the technical details of setting up the initial code base for our pipeline
and can be skipped.

Figure 2: Diagram representing our method for discovering and describing human
planning strategies. The method assumes externalizing human planning first and
gathering human planning operations in an experiment. Then it assumes creating
a Domain Specific Language (DSL) to describe the environment in which
participants made decisions, and running a clustering algorithm on the
gathered data to create mathematical representations of planning strategies –
policies. Afterwards, the pipeline assumes running the AI-Interpret
(Skirzyński et al., 2021) algorithm using the constructed DSL and the found
policies, and finally transforming the found formulaic descriptions into
procedural instructions expressed in linear temporal logic.

###  3.1 Data collection and data preparation

To use our method for discovering human strategies, the data collected in the
experiments is required to meet certain criteria. Firstly, the experiment has
to externalize people’s planning by using a computerized process-tracing
paradigms for planning. In our benchmark studies we used the Mouselab-MDP
paradigm (Callaway et al., 2020, 2017), since to our knowledge, it is the only
such paradigm that is available so far. To study one-shot decision-making, on
the other hand, one could use the standard Mouselab paradigm (Payne et al.,
1988), ISLab (Cook and Swain, 1993), MouseTrace (Jasper and Shapiro, 2002) or
other similar environments. Secondly, the experiments need to gather
participants’ _planning operations_ that we define as sequences of state-
action pairs generated by each of the participants. The states are defined in
terms of the information that the participant has collected about the task
environment. The actions are the information gathering operations that the
participant performs to arrive at their plan. Thirdly, the gathered planning
operations should be saved in a CSV file that would additionally contain
labels of the experimental block they came from (e.g. ’train’ or ’test’), and
labels corresponding to participant id. In our case this data was separated
into distinct CSVs and custom Mouselab-MDP functions extracted states,
actions, blocks and ids from them into a new (Python) object.

###  3.2 Creating the Domain Specific Language

Humans build sentences by using words (and build words by using phonemes). In
order to automatically build descriptions of strategies used by people in the
planning process-tracing experiments, we also need a vocabulary of some
primitives. Due to the algorithmic setup of the method introduced in this
section, here, the required set of primitives comprises logical predicates.
Following Skirzyński et al. (2021) whose method is an important part of our
pipeline, the predicates serve as feature-detectors and are formally defined
as mappings from the set of state-action pairs to booleans, that is
$f:\mathcal{S}\times\mathcal{A}\rightarrow\\{0,1\\}$. Practically, the
predicates describe the state $s\in\mathcal{S}$, the action $a\in\mathcal{A}$
or the particular characteristic that action $a$ has in state $s$. For
instance, predicate is_observed(s,a) might denote that node number $a$ in the
Mouselab MDP paradigm has not yet been clicked and its value is hidden in
state $s$. Later, this predicate could be used to define a very simple DNF
that allows clicking all the nodes that have not yet been clicked, i.e.
not(is_observed(s,a)). The second step in our pipeline thus considers creating
a set of predicates that describe the process-tracing environment. Further in
the text we will call that set of predicates the Domain Specific Language
(DSL).

###  3.3 Obtaining interpretable descriptions of human planning strategies via
Human-Interpret

The third and final step of our method is to use the algorithm for discovering
interpretable descriptions of people’s planning strategies. This algorithm
finds a set of planning strategies people used based on the data from process-
tracing experiments and then generates interpretable descriptions of those
strategies in form of procedural formulas. Since the AI-Interpret method of
Skirzyński et al. (2021) plays a vital role in our pipeline, we call this new
algorithm Human-Interpret.

####  3.3.1 Big picture

In contrast to AI-Interpret (Skirzyński et al., 2021) which accepts
demonstrations of RL policies as input, Human-Interpret uses human data to
generate demonstrations on its own before processing them. In order to do
that, Human-Interpret first extracts a representative subset of the sequences
of information-gathering actions (clicks) along with the knowledge states in
which they were performed (see the sequence of planning operations
$(s_{i},a_{i})_{i=1}^{N}$ in Figure 2; the size of this subset ($K$) is an
input to the algorithm). This subset is selected by using a clustering
technique that represents clusters as policies. The policies obtained through
clustering are formalizations of planning strategies that originally still
lack interpretability. To make those policies understandable to humans, the
Human-Interpret algorithm utilizes AI-Interpret. AI-Interpret requires
demonstrations of what the policies do. Those demonstrations are generated by
executing the discretized versions of the policies. AI-Interpret describes
those demonstrations using the previously created interpretable DSL. The
outputs of the AI-Interpret algorithm are $K$ DNF formulas (represented by the
flowcharts in Figure 2). In the last step, Human-Interpret enhances the
interpretability of these formulas using the method from (Becker et al., 2021)
and turns the formulas into procedural descriptions mimicking the linear
temporal logic formalism (see the output in Figure 2). The pseudo code for
Human-Interpret can be found in the Algorithm 1 box; the explanation of its
parameters is shown in Table 1.

Input: Id of the experiment $exp\\_id$;

Number of participants $num\\_participants$;

Block $block$;

Number of EM clusters $num\\_clusters$;

Number of sequences generated by the EM clusters $num\\_trajs$;

Domain specific language $\mathcal{L}$;

Features for the EM softmax models $features$;

Tolerance for the EM clustering $tolerance$;

Tolerance ratio for the EM clustering $change\\_ratio$;

Maximum size of the DNF’s conjunctions in AI-Interpret $interpret\\_size$;

Tolerance for AI-Interpret $ai\\_tolerance$;

Number of rollouts for AI-Interpret $num\\_rollouts$;

Number of clusters for AI-Interpret $num\\_ai\\_clusters$;

Expert reward in the environment $expert\\_reward$;

Maximum divergence from the expert $max\\_divergence$;

Threshold for choosing the unless/until conditions $threshold$;

Allowed unless/until predicates $allowed\\_predicates$;

Redundant predicates $redundant\\_predicates$;

Output: Set of procedural formulas $\mathcal{P}$;

1: $\mathcal{P}=[]$

2: $planning\\_operations\leftarrow\text{load\\_human\\_data}(exp\\_id,\
num\\_participants,\ block)$

3:
$EM\\_clusters\leftarrow\text{cluster\\_human\\_data}(planning\\_operations,\
num\\_clusters$,

$features,\ tolerance,\ change\\_ratio)$

4: for $c$ in $EM\\_clusters$ do

5: $demos\leftarrow\text{generate\\_demonstrations}(c,\ num\\_trajs)$

6: $DNF\leftarrow\text{AI-Interpret}(demos,\ interpret\\_size,\
ai\\_tolerance,\ num\\_rollouts,$

$num\\_ai\\_clusters,\ expert\\_reward,\ max\\_divergence,\ \mathcal{L})$

7: $proc\\_formula\leftarrow\text{DNF2LTL}(DNF,\ threshold,\
allowed\\_predicates,$

$redundant\\_predicates)$

8: $pruned\\_proc\\_formula\leftarrow\text{prune}(proc\\_formula)$

9: $\mathcal{P}.\text{append}(pruned\\_proc\\_formula)$

10: end for

11: return $\mathcal{P}$

Algorithm 1 Pseudocode for the Human-Interpret algorithm. Algorithm |  Parameter |  Explanation
---|---|---
Human-Interpret |  exp_id |  Name of the experiment for which the clusters of state-action pairs will be created. The name is used to identify proper folders with the data.
num_participants |  Number of participants whose data from the experiment to consider.
block |  Part of the experiment from which the data is taken (e.g. ’test’). Depends on which identifiers have been used in the experiment.
num_clusters |  Number of probabilsitic (EM) clusters to create. We use Bayesian model selection for choosing the number of clusters automatically. In practice, we consider max_num_clusters (a hyperparameter) models where a single model posits the existence of $N$ clusters, and $N\in\\{1,...,\text{max\\_num\\_clusters}\\}$. We choose between the models based on a hyperparameter criterion which is either marginal likelihood, weighted marginal, AIC or BIC. For marginals we use the following probabilistic model: $\epsilon*uniform(\text{non-optimal-actions})+(1-\epsilon)*uniform(\text{optimal-actions})$. We use Beta functions as the prior over $\epsilon$ with alpha and beta being hyperparameters.
num_trajs |  Number of sequences of planning operations generated by the EM clusters used to find the descriptions of the clusters.
$\mathcal{L}$ |  Domain Specific Language of predicates to create descriptions from.
Expectation-Maximization |  features |  Set of functions which defines features in the environment for externalizing planning. The features are used by the softmax models that symbolize the EM clusters. Might be related or unrelated to the DSL.
tolerance |  Minimum change in the likelihood of the state-action sequences’ assignment to EM clusters that allows further iterations of the EM algorithm.
change_tolerance |  Minimum relative change between the likelihood in the previous and current iteration that allows further iterations of the EM algorithm.
AI-Interpret |  interpret_size, ai_tolerance, num_rollouts, num_ai_clusters |  See Skirzyński et al. (2021).
expert_reward |  Average reward of the optimal policy in the environment
max_divergence |  The maximum difference in formula-induced policy’s expected reward and the mean reward of the interpreted policy, measured proportionally to the expert reward
DNF2LTL |  threshold |  Proportion of demonstrations that might have a candidate until condition incompatible with the candidate conditions for other demonstrations, but still be selected as the until condition in the output formula.
allowed_predicates |  Candidates for the until and unless conditions selected from the DSL.
|  redundant_predicates |  List of unwanted predicates removed from the DNF.
Table 1: Explanation of the parameters used by Human-Interpret and other
methods utilized by Human-Interpret.

####  3.3.2 Clustering planning operations into planning strategies

Human-Interpret begins the process with extracting planning strategies out of
sequences of planning operations gathered in the process-tracing experiment.
Let
$\mathcal{D}=\\{(\tau_{1i})_{i=1}^{K_{1}},(\tau_{2i})_{i=1}^{K_{2}}\dots,(\tau_{Mi})_{i=1}^{K_{M}}\\}$
denote the set of planning operations belonging to $M$ participants where
$\tau_{ji}=((s^{ji}_{l},a^{ji}_{l}))_{l=1}^{L^{ji}}$ is the $i$-th sequence of
planning operations generated by participant $j$, and $L^{ji}$ is its length.
Human-Interpret utilizes the Expectation Maximization (EM) (Moon, 1996)
algorithm to fit a probabilistic clustering model to the state-action
sequences in $\mathcal{D}$ and extract $k$ planning strategies (the clusters
$\pi_{1},\pi_{2}....,\pi_{k}$). Each planning strategy corresponds to a
softmax policy of the form given in Equation 2.

$\pi_{i}(a\mid
s,w_{i})=\frac{\exp(\mathbf{f}(s,a)^{\intercal}w_{i})}{\sum\limits_{k=1}^{T}\exp(\mathbf{f}(s,a_{k})^{\intercal}w_{i})}$
(2)

Each softmax policy ($\pi_{i}$) is represented by weights $w_{i}$ assigned to
$P$ different features $\mathbf{f}=[\phi_{1},\phi_{2},\dots,\phi_{P}]$ of the
state-action pair where
$\phi_{i}:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{X}_{\phi}$. These
features were partially derived from the DSL and partially hand-designed.
There were 19 of them and they can be found in Appendix A.4. The aim of the EM
algorithm is to find the planning strategies by clustering the click sequences
in $\mathcal{D}$ into $k$ clusters, with each cluster being represented by a
softmax policy $\pi_{i}$. It does this by optimizing the set of weights
$W=(w_{1},w_{2},....,w_{k})$ that maximize the total likelihood
($\mathcal{M}$) of the click sequences under all the clusters. $\mathcal{M}$
is described in Equation 3.

$\mathcal{M}(\mathcal{D}\mid
W)=\sum\limits_{i=1}^{k}\sum\limits_{C\in\mathcal{D}}\sum\limits_{(s,a)\in
C}\pi_{i}(a\mid s,w_{i})$ (3)

After obtaining the policies represented by the weights $W$, they are
discretized to form new uniform policies ($\overline{\pi}_{i}$) as described
in Equation 4 that assign uniform probability to actions with the highest
probability according to $\pi_{i}$, that is to optimal actions. Policies
$\overline{\pi_{i}}$ are then used to create a data set of demonstrations
$\overline{\mathcal{D}}=\\{(s_{i},a_{i})\\}_{i=1}^{L}$ which contains $L$
planning operations generated through some fixed number of rollouts.

$\overline{\pi}_{i}(a\mid s)=\begin{cases}0,&\text{if
}\pi_{i}(s,a)\neq\max\limits_{k\leq P}\pi(s,a_{k})\\\
1/\lvert\\{a_{i}:\pi_{i}(s,a_{i})=\max\limits_{k\leq
P}\pi(s,a_{k})\\}\rvert&\text{otherwise}\end{cases}$ (4)

####  3.3.3 Finding formulaic descriptions of planning strategies

After computing policies $\overline{\pi}_{i}$ and generating the data set of
demonstrations $\overline{\mathcal{D}}$, Human-Interpret essentially runs AI-
Interpret (Skirzyński et al., 2021). The only modification to the AI-Interpret
algorithm that is introduced by Human-Interpret relates to the fact that the
input demonstrations no longer represent the optimal policy, but _some_ ,
often imperfect policy mimicking humans: $\overline{\pi}_{i}$ (further called
the interpreted policy). Because of that, the expected reward for policies
induced by candidate formulas cannot make at least $\alpha$ of the expected
reward for the interpreted policy (see the Background section), since it leads
to errors. For instance, in a situation when the interpreted policy achieves a
reward of $R$, and the optimal policy achieves a reward of $100R$, a formula
that induces a policy with reward $50R$ meets the criterion defined by
$\alpha$, but is a poor approximation to $\overline{\pi}_{i}$. Because of
that, Human-Interpret uses _divergence_ instead of the expected reward ratio.
If $\pi_{f}$ is a policy induced by formula $f$ found by AI-Interpret and
$\pi_{opt}$ is the optimal policy for the studied environment (here, the
Mouselab MDP), Human-Interpret computes the divergence of $f$ as the ratio
between the difference in rewards for the interpreted policy
$\overline{\pi}_{i}$ and $\pi_{f}$, and the expected reward of the optimal
policy, i.e.
$\text{div}(\pi_{f})=\frac{J(\pi_{f})-J(\overline{\pi}_{i})}{J(\pi_{opt})}$.
Consequently, Human-Interpret searches for solutions whose size is limited by
$d$ and for which the divergence is at most $\alpha$ (see the Background
section). Note that introducing that modification requires the modeler, or the
algorithm, to compute the optimal policy for the environment or at least know
its approximation.

####  3.3.4 Extracting procedural descriptions from logical formulas

The output produced by the modified AI-Interpret algorithm we defined above is
a DNF formula $f^{*}$. Following the finding that procedural descriptions are
easier to grasp for people than flowcharts (Becker et al., 2021), Human-
Interpret uses the method presented in Becker et al. (2021) to transform
$f^{*}$ into a logical expression written in linear temporal logic. The
DNF2LTL algorithm described in (Becker et al., 2021) produces such an
expression by separating the DNF into conjunctions, and finding the dynamics
of their changes in truth valuations using the initial set of demonstrations
inputted to AI-Interpret. The output, which we will call a _procedural
formula_ , separates the conjunctions with NEXT commands, and instructs to
follow each conjunction until some condition occurs unless another condition
occurs. The conditions are chosen among the predicates or 2-element
disjunctions of predicates from the DSL introduced in Section 3.2, or simply
read (for the UNTIL condition) “until it applies”, which denotes a special
logical operator. Since the output formula might be overly complex after that
process, in the next step the algorithm prunes some of the predicates
appearing in the conjunctions. Concretely, predicates are greedily removed one
by one so as to increase the probability of people’s planning operations under
the strategy described by the shortened formula. More details regarding the
algorithm can be found in Appendix A.5.

####  3.3.5 Translating to natural language

Once the procedural formulas are generated, it is possible to obtain fully
understandable descriptions of human planning strategies by transforming the
predicates and the operators appearing in the formulas into natural language.
This is an optional step that we have accomplished for the Mouselab-MDP
paradigm. Our procedural formulas are expressed in natural language by using a
pre-defined predicate-to-expression dictionary.

###  3.4 Technical details regarding using our method

Here, we present technical details connected to installing and using our
method for discovering and describing human planning strategies. We equipped
the initial code base written in Python 3.6 with: 1) data from 4 planning
experiments ran in different versions of the Mouselab-MDP paradigm, 2) a
Domain Specific Language (DSL) of logical primitives used to generate
procedural formulas, and 3) a dictionary of predicate-to-expression entries
for transforming a formula into natural language. Each of these elements is
either a parameter or a hyperparameter of Human-Interpret. Description of the
experiments can be found in (Jain et al., 2021), whereas the DSL is detailed
in Appendix A.2 and contained in one of the files in the code base, similarly
to the dictionary. Thanks to the initial values for those parameters it is
possible to use our method without performing prior research. Moreover, one
may extend our research by slightly modifying the DSL or running Human-
Interpret on a different data set. The steps involved in setting up the whole
method are as follows:

  1. 1.

Download data needed in the pipeline and the source code for Human-Interpret
by cloning the appropriate Github repository using the command:

git clone https://github.com/RationalityEnhancement/
InterpretableHumanPlanning.git

The repository includes four data sets that are contained in the folder
data/human. Refer to (Jain et al., 2021) for a detailed description of the
experiments they come from.

  2. 2.

Access the root directory of the downloaded source code and install the needed
Python dependencies:

pip3 install -r requirements.txt

  3. 3.

Run Human-Interpret on either of the available data sets by typing

python3 pipeline.py ---experiment <name> \---max_num_strategies <max>
\---num_participants <num_p> \---expert_reward <exp_rew> \---num_demos <demos>
\--begin <b>

Parameter experiment corresponds to the name of the experiment that resulted
in one of the four data sets. As written in Table 1, max_num_strategies
quantifies the maximum number of strategies that could exist in the data set
and should be described; parameter expert_reward defines the maximum reward
obtainable in the Mouselab MDP defining each of the experiments;
num_participants state that the data of the first <num> participants should be
extracted from the data set; num_demos controls how many strategy
demonstrations to use in Human-Interpret; begin controls which model to begin
with (how many clusters to consider in the first model to then incrementally
increase that number thus defining consecutive models). The available names,
number of all tested participants, and corresponding expert rewards are
provided in the readme file included in the source code. The output of this
command is saved in the interprets_procedure folder in a text file named
according to the following structure:

$\texttt{strategies\\_<name>\\_<max>\\_<num\\_p>\\_<demos>}.$

The files contain procedural formulas describing the clusters, their natural
language descriptions, and a set of statistics associated with those
descriptions (e.g. how well it fits the experimental data, how big it is,
etc.)

  4. 4.

To reproduce the exact set of strategies from this paper, set the parameters
like this:

python3 pipeline.py ---experiment v1.0 ---max_num_strategies 17 --begin 17
---num_participants 0 ---expert_reward 39.97 ---num_demos 128

Information regarding other parameters available for tuning the Human-
Interpret algorithm can be found in Table 1 and in the pipeline.py file. The
set of logical primitives serving for our DSL may be accessed by navigating to
RL2DT/PLP/DSL.py. Finally, the dictionary is included in the file
translation.py. To apply our method to different problems consult pipeline.py,
README.md, Section 3.1, and Section 3.2.

##  4 Evaluating our method for discovering human planning strategies

In this section, we evaluate our method on data from an experiment that used
the Mouselab-MDP paradigm to externalize planning. We show the strategies that
were automatically discovered and list their descriptive statistics. We also
compare the output of our method to the strategies that Jain et al. 2021
discovered through a laborious manual inspection of the same data set. The
first subsection focuses on each of the three steps of our method: it
describes the planning experiment, the vocabulary of logical primitives and
the parameters for Human-Interpret. The second subsection describes the
strategies discovered by Human-Interpret and compares them to strategies
discovered manually by Jain et al. (2021).

###  4.1 Setup of the benchmark problem

####  4.1.1 Planning experiment

In our benchmark problem we used a process-tracing experiment on human
planning conducted according to the Mouselab-MDP paradigm (see Section 2.2.2),
namely the first experiment presented in Jain et al. (2021). This experiment
(which we will refer to as the increasing variance experiment) used the
Mouselab-MDP environment shown in Figure 1 where the rewards hidden underneath
the nodes were different in every trial but were always drawn from the same
probability distribution. The nodes closest to the spider’s starting position
at the center of the web had rewards sampled uniformly from the set
$\\{-4,-2,2,4\\}$. Nodes one step further away from the spider’s starting
position had rewards sampled uniformly from the set $\\{-8,-4,4,8\\}$.
Finally, the nodes furthest away from the starting position of the spider
harbored rewards sampled uniformly from the set $\\{-48,-24,24,48\\}$. The fee
for clicking a node to uncover its reward was $1$. The 180 participants who
took part in this experiment were divided into 3 groups that differed in what
kind of feedback was provided during the trials. The control group received no
feedback. The second group received feedback on their first move. The third
group received feedback on every click they made that was designed to teach
them the planning strategy that is optimal for the task environment. There
were always 2 blocks: a training block and a test block, with 20 trials in the
training block and 10 trials in the test block. As stated in the previous
sections, the experiment utilized the Mouselab-MDP process-tracing paradigm
and operationalized people’s planning strategies in terms of the clicks
(planning operations) they performed.

####  4.1.2 Domain Specific Language (DSL) and translation dictionary

We adopted the DSL of predicates from our work on AI-Interpret which was also
conducted on Mouselab-MDP environments (Skirzyński et al., 2021). Generally,
the DSL consisted of over 14000 predicates generated according to a hand-made
context free grammar. The predicates were defined on state-action pairs, where
states were represented as Python objects capturing the uncovered and covered
rewards in the Mouselab-MDP, and each action denoted the ID of the node to be
clicked. The predicates described the current state of the Mouselab-MDP or the
actions available in that state. The state is described in terms of the
clicked nodes, the termination reward, and other properties. The actions are
described in graph theoretic terms, such as the depth of the clicked node,
whether it is a leaf node, whether its parents or children have been observed,
and so on. The DSL included two crucial second-order predicates: the _among_
predicate asserts that a certain condition (given by a first-order predicate)
holds among a set of nodes defined by another first-order predicate, and the
_all_ predicate asserts that all of the nodes satisfying a certain condition
also satisfy another condition. Detailed descriptions of the predicates in the
DSL we used are available in Appendix A.2.

The dictionary we used for translating the resulting procedural formulas is an
adapted version of the dictionary from Becker et al. (2021). In our
dictionary, we changed natural language translations of most predicates to use
graph theoretic jargon (such as leaves, roots, etc.). Moreover, our
translations always begin with “ _Click on the destinations satisfying all of
the following conditions:_ ” if there are any non-negated predicates in the
formula and list the non-negated predicates as conditions. The difference with
the original dictionary is also that more complex predicates (such as those
which included other predicates as their argument) are broken down into 2 or
more conditions, whereas in the original dictionary each predicate has its
unique translation. More details on how the translation was created can be
found in in our project’s repository in the translation.py file.

####  4.1.3 Parameters for the Human-Interpret algorithm

To run Human-Interpret, we used the default parameters for the AI-Interpret
algorithm, the DSL described in the previous section, the data from all of the
participants in the experiment described in Section 4.1.1 (that is 180), and
data form both blocks of the experiment (i.e., the training block and the test
block). We ran Human-Interpret with 1-20 clusters and then performed model-
order selection according to Bayesian inference with a uniform prior on the
number of clusters (Kass and Raftery, 1995). Each cluster was defined as a
mixture of two policies. The first policy was induced by the procedural
description constructed for the cluster. The second policy served as an error
model. These two policies assigned uniform probability to actions allowed and
disallowed by the procedural description constructed for the cluster,
respectively. The weights assigned to both policies were cluster-dependent
free parameters (i.e., $\epsilon_{i}\in[0,1]$). Mathematically, the clustering
model $P(\tau)$ for a sequence of planning operations
$\tau=(s_{i},a_{i})_{i=1}^{T}$, for $K$ clusters represented by $K$ policies
$\pi_{1},\dots,\pi_{K}$, and for $K$ error models
$\overline{\pi_{1}},\dots,\overline{\pi_{K}}$ took the following form:

$\displaystyle P(\tau\mid\bm{\epsilon})$
$\displaystyle=\sum\limits_{i=1}^{K}1/K*P_{i}(\tau;\epsilon_{i})$ (5)
$\displaystyle=\sum\limits_{i=1}^{K}1/K*\prod\limits_{j=1}^{T}\left(\epsilon_{i}*\overline{\pi_{i}}(s_{j},a_{j})+(1-\epsilon_{i})*\pi_{i}(s_{j},a_{j})\right).$
(6)

We performed model selection among the clustering models for which Human-
Interpret was able to produce a description for all clusters. Our rationale
for doing so was that models that do not describe all the clusters are not
useful for the purpose of understanding human planning. After imposing this
constraint, we chose the model under which the data set had the greatest
marginal likelihood that we approximated for each model using the Bayesian
Information Criterion (BIC) (Konishi and Kitagawa, 2008). We discovered that
the model with 10 clusters achieved the highest marginal likelihood (marginal
likelihoods computed for models that described all the clusters can be found
in Table 2).

Model (number of clusters) | Log Marginal | BIC | AIC
---|---|---|---
1 | -55801 | 111603 | 111466
2 | -43710 | 87420 | 87139
3 | -46094 | 92188 | 91698
4 | -44479 | 88957 | 88383
5 | -43206 | 86411 | 85720
6 | -43810 | 87620 | 86687
9 | -42601 | 85202 | 83812
10 | -41957 | 83913 | 82451
12 | -42907 | 85813 | 83770
13 | -43419 | 86838 | 84991
15 | -42755 | 85509 | 82487
16 | -43453 | 86906 | 84120
17 | -42861 | 85722 | 83196
Table 2: Logarithm of the marginal likelihood, BIC and AIC of the clustering
models analyzed by Human-Interpret.

Corroborating this result, the chosen number of clusters was identical when we
used the Akaike Information Criterion (Vrieze, 2012) as our way for selecting
the best model. The DSL we used and the predicates we used for the DNF2LTL
algorithm can also be found in Appendix A.2 and A.3. All of the parameters are
listed in Table A1 in Appendix A.1. The more elusive parameters, such as
interpret_size or num_trajs were selected based on the simulations and
interpretability experiments presented in Skirzyński et al. (2021).

###  4.2 Evaluating and comparing automatically discovered strategies to
strategies discovered through manual inspection

In this section we show the discovered descriptions of human planning
strategies, list their statistics, and compare them to the strategies that
Jain et al. 2021 found through manual inspection.

With the selected clustering model, Human-Interpret found descriptions for 10
clusters. For some of those clusters the automatically generated descriptions
were equivalent to those of one or more other clusters. This reduced the
number of discovered strategies to 7 unique descriptions. The discovered
strategies are described in Table LABEL:tab:strategies. According to the
manual analysis from (Jain et al., 2021), our automated method discovered 3 of
the 4 most common strategies (i.e. strategies used in at least 3% of all
trials). These strategies account for 53.4% of all planning operations. In
total, our method rediscovered 6 of the strategies discovered by (Jain et al.,
2021) and those strategies jointly account for 63.2% of people’s planning
operations. Other strategies discovered by Jain et al. (2021) were assimilated
into one of the 7 unique strategies discovered by our method. These strategies
were also diverse. Namely, our 7 unique strategies represent 7 out of 13
strategy types identified by Jain et al. (2021), and hence cover over 50% of
existing planning strategies variability. Finally, our automatic method
resulted in a set of strategies that describe people’s planning operations
3.03 times better than chance. In other words, the probability of a planning
operation under the strategy it was ascribed to is on average 3.03 times as
high as than its probability under a random model that always assigns the same
probability to all possible actions (including termination). In the case of
the manual inspection performed by Jain et al. (2021), the results are very
similar, and the average improvement equals 3.6 times as high as than the
random model. This means that the automatically created descriptions are
almost as accurate as the manually found descriptions, despite being more
coarse. A summary of the comparison between the performance of our automatic
strategy discovery and description method with the manual approach by Jain et
al. (2021 can be found in Table 3.

In previously mentioned Table LABEL:tab:strategies we also report descriptive
statistics about the complexity of the automatically generated descriptions,
the frequencies of the discovered strategies, how well they corresponded to
the EM clusters, and how well they explain the sequences of planning
operations they are meant to describe. These statistics suggest that our
automatic method generates reasonable solutions of a very promising quality,
especially considering that our method discovered those strategies without any
labelled training examples or human feedback. On average, the discovered
descriptions agreed with the softmax models of the clusters on 77% of the
planning operations. That quantity, which we call the _formula-cluster fit_
(FCF) is defined as the average of two proportions. The first one is the
proportion of the planning operations generated according to the inferred
description that agreed with the choices of the corresponding softmax model.
The second one is the equivalent proportion obtained by generating the
demonstrations according to the softmax models and then evaluating them
according to the descriptions. In both cases we performed 100000 rollouts.
Further, the average likelihood of the planning operations within the clusters
reached 76% of the likelihood that would have been achieved if all planning
operations perfectly followed the descriptions. We call that proportion the
_fit per operation_ (FPO). The quality of individual cluster-descriptions, as
measured in terms of the FPO, is depicted in Figure 3. To globally visualize
the quality of our method, we estimated the distribution of FPO values across
all clusters. This revealed that almost 85% of clusters would achieve FPO over
60% (see Figure 4).

The runtime of our method, that is the number of days for which the code ran,
was 45 days. In contrast, it took Jain et al. (2021) about 120 days to finish
their manual analysis. This means that our method could have accelerated the
process of strategy discovery by 75 days compared to manual inspection. That
suggests that our method can be used to speed-up research on the strategies of
human planning and decision-making.

| Method
---|---
Statistic | Automatic analysis | Manual analysis
Success rate | 100% | 100%
Runtime | 45 days | 120 days
Number of distinct strategies | 7 | 79
Likelihood per click | 0.37 | 0.44
Times better than random | 3.03 | 3.6
Table 3: Comparison between our automatic method for finding and describing
human planning strategies and the manual approach by Jain et al. (2021). The
success rate is the proportion of sequences of planning operations that the
method was able to describe. Runtime is the number of days it took to generate
the result. The likelihood per click is the average likelihood per a planning
operation. Times better than random quantifies the improvement in average
likelihood per operation over the random model which assigns equal probability
to all actions that are possible in a given step.

Table 4: The results of applying our computational method to the benchmark problem. Human-Interpret with 10 clusters found 7 unique strategies listed along with their ID, their automatically generated description, the summary we created by hand, and the name (or numbers) of the corresponding strategy (strategies) discovered manually by Jain et al. (2021). FR denotes the frequency of the strategy; FCF (fit cluster-formula) averages two proportions: formula demonstrations agreeing with the softmax clusters and vice-versa measured using 100000 demonstrations; FON (fit optimal-non-optimal) quantifies how often people’s planning operations in the cluster agreed with the description; FPO (fit per operation) is the ratio between the average likelihood per planning operation belonging to the cluster and the average likelihood per planning operation for the (policy induced by the) cluster’s description in general; C, which stands for complexity, is the number of individual predicates in the description; N is the number of clusters with the given description. Frequency (FR) is the only statistic measured for the manually found strategies. ID |  Unique descriptions | Statistics
---|---|---
FR |  FCF |  FON |  FPO |  C |  N
3 |  Description:  1. Click on a node satisfying all of the following conditions: - it is an unobserved leaf. 2. Click on the nodes satisfying all of the following conditions: - they are unobserved leaves. Click in this way as long as - the previously observed node was their sibling Repeat this step as long as possible. |  6.5% |  0.67 |  0.48 |  0.4 |  7 |  1
Summary: Click final outcomes of a random subtree.
Manual counterpart: – |  – |  |  |  |  |
5 |  Description:  1. Click on a random node or terminate. 2. Click on the nodes satisfying all of the following conditions: - they are unobserved non-roots, - they have parents with the highest values considering the parents of other unobserved non-roots. Repeat this step as long as possible. 3. GOTO step 1. |  2.7% |  0.58 |  0.83 |  0.77 |  5 |  1
Summary: Click on a node and all its successors. Repeat or terminate.
Manual counterpart: Local search strategies (strategy 20, 22, 37, 40) |  2.71% |  |  |  |  |
4 |  Description:  1. Click on the nodes satisfying all of the following conditions: - they are unobserved leaves. Repeat this step until all the leaves are observed or the previously observed node uncovers a 48. |  53% |  0.97 |  0.93 |  0.91 |  10 |  1
Summary: Search for the best possible final outcome.
Manual counterpart: Search for the best possible final outcome. |  36.59% |  |  |  |  |
7 |  Description:  1. Click on the nodes satisfying all of the following conditions: - they are unobserved roots. Repeat this step until all the roots are observed. 2. Terminate or click on some random nodes and then terminate. Repeat this step as long as possible. |  2.38% |  0.68 |  0.99 |  0.99 |  4 |  1
Summary: Click all roots, then do something random.
Manual counterpart: Various (strategy 28, 29, 30, 33, 34, 35, 36, 54, 55, 61, 70, 71, 73) |  5.68% |  |  |  |  |
6 |  Description:  1. Click on a node satisfying all of the following conditions: - it is a node on an arbitrary level but for 2 and on an arbitrary level but for 3, - it is an unobserved node that has a parent with the non-highest or unobserved value on its level, - lies on a best path. 2. Click on the nodes satisfying all of the following: - they are unobserved non-roots, - they have parents with the lowest values considering the parents of other unobserved non-roots. Click in this way as long as: - all the nodes with a 48 on their path have a parent with the same observed value. Repeat this step as long as possible. 3. GOTO step 1. |  3.68% |  0.93 |  0.7 |  0.67 |  21 |  1
Summary: Depth first search until a positive final outcome or positive leaf
node with observing its sibling or until +48.
Manual counterpart: Satisficing Depth First Search |  3.62% |  |  |  |  |
1 |  Description:  1. Terminate or click on some random nodes and then terminate. Repeat this step as long as possible. |  11.93% |  0.57 |  1.0 |  1.0 |  1 |  3
Summary: Random planning.
Manual counterpart: Random planning. |  1.19% |  |  |  |  |
2 |  Description: Do not click. |  19.81% |  1.0 |  0.61 |  0.61 |  1 |  1
Summary: No planning.
Manual counterpart: No planning. |  13.15% |  |  |  |  |

Since the average measurements over all clusters do not take into account the
importance of clusters, we decided to perform the same computations using
cluster size-dependent weighted averages. As larger clusters represent the
most often used strategies, and these are the strategies we are predominantly
interested in from a psychological standpoint, weighted averages capture the
measured statistics with higher accuracy. After weighting our statistics we
found that the descriptions achieved the formula-cluster fit (FCF) of 89%, and
the fit per planning operation (FPO) of 82%. The weighted average complexity
of the description was 7 predicates. To present a clearer picture, we excluded
the unique cluster describing the random policy, and then computed the
weighted statistics again. This cluster contains around 12% of all sequences
of planning operations and it trivially achieves the FPO of 1. Having removed
that cluster, our descriptions obtained the FCF of 93%, and the FPO of 79%.
The first number marks an increase in comparison to the previous fit between
the descriptions and the softmax models, since the random policy advocated by
the removed cluster was a bad fit for a substantial part of the planning
operations. In the second case, the new fit per operation marks a slight
decrease in comparison to the previous fit, but still amounts to a reasonable
quantity. The weighted average complexity of the description increased to 8
predicates.

Figure 3: Plot showing the quality of the clusters found by our pipeline,
measured as the fit per operation (FPO), depending on their size. Clusters are
labeled on the x-axis via their unique cluster ID (see Table
LABEL:tab:strategies for a reference). The width of the bar corresponds to the
size of the cluster. The height of the bar corresponds to the FPO measure. The
red line indicates the average FPO across all clusters. Figure 4: Density of
the fit per operation measure for clusters discovered by our pipeline. 93.5%
of the clusters achieve the fit per operation above 0.6.

##  5 General discussion

The main contribution of our research is automating the process of scientific
discovery in the area of human planning. By using our method, scientists are
no longer left at the mercy of their own ingenuity to notice and correctly
interpret the right patterns in human behavior; instead they can rely on
computational methods that do so reliably. Concretely, we developed the first
method for the automatic discovery and description of human planning
strategies. Our method’s pipeline comprises 3 steps: The first step is to run
an experiment that externalizes human planning operations. The second step is
to create a Domain Specific Language (DSL) of logical predicates that describe
the task environment and the planning operations. Finally, the third step is
to run the generative imitation learning algorithm that we created and present
in this paper, called Human-Interpret. Human-Interpret discovers the
strategies externalized in the experiment by creating generative softmax
models (the generative step) and describes them by procedural rules formulated
in the DSL by imitating their rollouts (the imitation learning step).

###  5.1 Advantages

The tests we ran on a benchmark planning problem revealed that the accuracy of
our method is akin to that of a manual human analysis. Firstly, our automated
approach found the majority of all frequently used strategies (3 out of 4), if
we assume that a strategy appears “frequently” if it is used in at least 3% of
the trials according to the manual analysis (Jain et al., 2021). Secondly,
almost all of the unique automatically discovered strategies (6 out of 7) had
either an exact manually discovered counterpart or a class of manually found
counterparts (see Table LABEL:tab:strategies). These two properties indicate
that our method discovered virtually the same strategies as scientists did
without any human supervision. Thirdly, the average fit of the automatically
found strategies with respect to human planning operations was moderately high
(FPO of 76%), meaning the descriptions were accurate representations of the
experimental data. Fourthly, these descriptions were clear and understandable
(see Table LABEL:tab:strategies), proving the effectiveness of using our
method. Last but not least, applying our computational method was faster than
manual human analysis. It took us 45 days before we obtained the final output
via our pipeline whereas studying human planning without the aid of AI took
about 120 days.

In the light of our results, the main benefit of using the introduced pipeline
is accelerating scientific discovery in research on decision-making and
planning. Rather than trying to manually discover one strategy at a time, our
method makes it possible to run many large experiments with many different
environments and discover all of the strategies people use across those
environments at once. Further, our method is more objective than the
subjective and potentially biased person-centered manual approach. Strategies
and their descriptions are assigned based on mathematical likelihood and they
are provably optimal under such probabilistic criteria, whereas people could
introduce strategies based on their preconceptions and imperfect knowledge.
Employing our pipeline in research could save precious time. A scientist
interested in human planning could invest his or her resources to other
components of their research while waiting for the computations to finish,
unlike in the manual approach where he or she needed to perform all the steps
alone. Finally, our method sometimes discovers strategies that scientists
might have otherwise overlooked; one example thereof is Strategy 3 in Table
LABEL:tab:strategies which does not have a counterpart in the broad list of
strategies found manually.

###  5.2 Limitations

The above, however, brings us to the limitations of our method for the
automatic discovery and description of human planning strategies. The softmax
clusters did not always contain planning operations that fit well together.
For instance, Strategy 3 had a poor fit score of 0.4 with respect to people’s
planning operations (FPO). Similarly, the No planning strategy (Strategy 2 in
Table LABEL:tab:strategies) had an FPO score of 0.61 despite a perfect 1.0 fit
with respect to the cluster softmax model (FCF). This discrepancy occurred
because the softmax model of the cluster for Strategy 2 performed zero
planning even though the cluster included a substantial number of human
planning operations that gathered additional information. Moreover, our method
discovered many random planning clusters – 3 out of 10. A few of those were
not random before pruning. Since pruning optimized for the likelihood of the
operations under the description, this shows that the planning operations
clustered together by the generative part of Human-Interpret were too diverse.

Furthermore, our DSL was incapable of capturing all the strategies. One of the
often used planning strategies that our method did not discover is the
“Consecutive second maximum strategy” (Jain et al., 2021) which was used in
around 6% of the trials of the planning experiment. This strategy observes the
final outcomes in a random order but stops planning after it encounters two
outcomes with the second-highest reward consecutively. It was not discovered
by our method most likely due to the lack of a predicate which described the
second-highest reward.

Table LABEL:tab:strategies shows differences in the coverage (FR) between the
same strategies found by our pipeline and manual analysis. The main
discrepancy is that the automatically discovered strategies have a higher
frequency than the human-discovered strategies. We believe those differences
stem from the generalization inherent to our method and used by AI-Interpret –
it finds a description that fits some subset of the elements. Note that since
the softmax clusters represent human planning operations, when a demonstration
(planning operation) of the softmax cluster is rejected by the algorithm, a
human operation that corresponded to this demonstration (e.g. it followed the
same planning principle) is also rejected. A rejection of a cluster-generated
planning operation in AI-Interpret might occur in two situations: 1) either it
is indescribable due to the imperfect DSL, or 2) it differs from other
operations generated by the softmax cluster due to the imperfect clustering.
In fact, we computed that AI-Interpret utilized only 56% of the cluster-
generated planning operations to find the descriptions. A part of human
planning operations were thus also rejected when finding a description, but
still counted towards the coverage of the strategy. However, the 44% of
omitted cluster planing operations do not necessarily represent the same
proportion of omitted human planning operations. Given that the FPO of the
discovered strategies, which is our measure of the quality of descriptions
with respect to human planning operations, was as high as 76%, the upper bound
for the number of human planning operations which were completely disregarded
by Human-Interpret is probably around 24%.

Finally, computational limitations make it necessary to limit the maximum
number of strategies that our method can currently consider. The main
computational bottleneck lies in Human-Interpret, and within it, in the AI-
Interpret method. Because of the considerable computation time required to run
AI-Interpret on the data of one softmax cluster (Skirzyński et al., 2021) we
could not find strategies the are as fine-grained as the manually found ones.
This is the main reason why we only considered up to 20 strategies that could
be used by people, instead of up to 80, to match the results of the hand-made
analysis.

###  5.3 Future work

As stated above, the main limitations of our method are: imperfect softmax
clustering, an incomplete DSL, and the computational bottlenecks of AI-
Interpret. We could improve the clustering by imposing a no-diversity penalty
on the models. Hypothetically, this would make the softmax models as different
as possible and they could thus capture more diverse kinds of behaviors, for
instance as in (Eysenbach et al., 2018). Alternatively, we could obtain a
better clustering by incorporating a different method for choosing which
number of softmax clusters is optimal. Here, we used the maximum marginal
likelihood or the highest AIC to differentiate between competing models
(understood as numbers of clusters), but there might be better ways for
accounting for model complexity, such as performing cross-validation. We see
improving the DSL as an iterative refinement process in which we would add the
necessary predicates to the DSL, check the results of running our
computational method with the new DSL against the manual analysis, identify
missing predicates, if any, and then return to the first step. Just a few
iterations of this process should render a DSL capable of describing most of
the strategies used by people in the Mouselab-MDP environment. Both of those
enhancements, however, would not be feasible without first making our
computational method run faster. Thus, we plan on upgrading the implementation
of AI-Interpret in one of our first next steps.

Besides ameliorating the performance of our method, a worthwhile future work
direction is to combine the strategy discovery method presented in this
article with our computational process-tracing method for measuring which
planning strategy each participant used on each trial of the experiment (Jain
et al., 2021). We hypothesize that our method could serve to establish the
basic set of strategies one could use as input to the microscope. Then, a
human planning sequence could be automatically assigned to one of the
automatically discovered strategies, instead to the manually discovered
strategies. In this way, automatic strategy discovery might make it possible
to speed up the development of equivalent computational process-tracing
methods for other tasks and domains and to improve the repertoire of
strategies that those methods use to describe the temporal evolution of
people’s cognitive strategies.

Finally, future work should seek to apply our method for the automatic
discovery and description of human strategies to other scenarios. The
methodology we presented in this paper can be easily extended to decision-
making in other domains, such as risky choice, inter-temporal choice, and
multi-attribute decision-making (Lieder et al., 2017)). Because our approach
is rather general, we believe it has the potential to accelerate scientific
discovery in several areas of the cognitive and behavioral sciences.

## Declarations

##### Funding

This project was funded by German Federal Ministry of Education and Research
(BMBF): Tübingen AI Center, FKZ: 01IS18039B.

##### Conflicts of interest/Competing interests

The authors declare that they have no conflicts of interest or competing
interests.

##### Availability of data and material (data transparency)

Anonymized data from the experiment we used as our benchmark experiment is
available at
https://github.com/RationalityEnhancement/InterpretableHumanPlanning/tree/main/data/human.

##### Code availability (software application or custom code)

The code for Human-Interpret is available at
https://github.com/RationalityEnhancement/InterpretableHumanPlanning.

##### Ethics approval

Not applicable

##### Consent to participate (include appropriate statements)

Not applicable

##### Consent for publication

Not applicable.

## References

  * Abelson and Levi (1985) Abelson R, Levi A (1985) Decision making and decision theory. In: Lindzey G, Aronson E (eds) Handbook of social psychology, Hillsdale, NJ: Erlbaum
  * Addis et al. (2016) Addis M, Sozou PD, Lane PC, Gobet F (2016) Computational scientific discovery and cognitive science theories. In: Computing and philosophy, Springer, pp 83–97
  * Agrawal et al. (2020) Agrawal M, Peterson JC, Griffiths TL (2020) Scaling up psychology via scientific regret minimization. Proceedings of the National Academy of Sciences 117(16):8825–8835
  * Araki et al. (2019) Araki B, Vodrahalli K, Leech T, Vasile CI, Donahue M, Rus D (2019) Learning to Plan with Logical Automata. In: Robotics: Science and Systems Conference (RSS), Messe Freiburg, Germany, pp 1–9
  * Bacon and In Fowler (1878) Bacon F, In Fowler T (1878) Novum organum. Oxford: Clarendon Press
  * Becker et al. (2021) Becker F, Skirzyński J, Lieder F (2021) Boosting human far-sightedness with automatically discovered planning instructions. Manuscript in preparation
  * Bhatia and He (2021) Bhatia S, He L (2021) Machine-generated theories of human decision-making. Science 372(6547):1150–1151
  * Botvinick et al. (2009) Botvinick MM, Niv Y, Barto AG (2009) Hierarchically organized behavior and its neural foundations: a reinforcement learning perspective. Cognition 113(3):262–280
  * Callaway et al. (2017) Callaway F, Lieder F, Krueger PM, Griffiths TL (2017) Mouselab-MDP: A new paradigm for tracing how people plan. In: The 3rd Multidisciplinary Conference on Reinforcement Learning and Decision Making, Ann Arbor, MI, URL https://osf.io/vmkrq/
  * Callaway et al. (2018) Callaway F, Lieder F, Das P, Gul S, Krueger PM, Griffiths T (2018) A resource-rational analysis of human planning.
  * Callaway et al. (2020) Callaway F, van Opheusden B, Gul S, Das P, Krueger P, Lieder F, Griffiths T (2020) Human planning as optimal information seeking. Manuscript under review
  * Consul et al. (2021) Consul S, Heindrich L, Stojcheski J, Lieder F (2021) Improving human decision-making by discovering efficient strategies for hierarchical planning. arXiv preprint arXiv:210200521
  * Cook and Swain (1993) Cook GJ, Swain MR (1993) A computerized approach to decision process tracing for decision support system design. Decision Sciences 24(5):931–952
  * Džeroski et al. (2007) Džeroski S, Langley P, Todorovski L (2007) Computational discovery of scientific knowledge. In: Computational Discovery of Scientific Knowledge, Springer, pp 1–14
  * Eysenbach et al. (2018) Eysenbach B, Gupta A, Ibarz J, Levine S (2018) Diversity is all you need: Learning skills without a reward function. arXiv preprint arXiv:180206070
  * Ford et al. (1989) Ford JK, Schmitt N, Schechtman SL, Hults BM, Doherty ML (1989) Process tracing methods: Contributions, problems, and neglected research questions. Organizational behavior and human decision processes 43(1):75–117
  * Foster et al. (2019) Foster A, Jankowiak M, Bingham E, Horsfall P, Teh YW, Rainforth T, Goodman N (2019) Variational bayesian optimal experimental design. arXiv preprint arXiv:190305480
  * Griffiths et al. (2019) Griffiths TL, Callaway F, Chang MB, Grant E, Krueger PM, Lieder F (2019) Doing more with less: meta-reasoning and meta-learning in humans and machines. Current Opinion in Behavioral Sciences 29:24–30
  * Hanson (1965) Hanson NR (1965) Notes toward a logic of discovery. In: Bernstein RJ (ed) Perspectives on Peirce, New Haven: Yale University Press
  * Huber et al. (1997) Huber O, Wider R, Huber OW (1997) Active information search and complete information presentation in naturalistic risky decision tasks. Acta Psychologica 95(1):15–29
  * Huys et al. (2012) Huys QJ, Eshel N, O’Nions E, Sheridan L, Dayan P, Roiser JP (2012) Bonsai trees in your head: how the Pavlovian system sculpts goal-directed choices by pruning decision trees. PLoS computational biology 8(3)
  * Huys et al. (2015) Huys QJM, Lally N, Faulkner P, Eshel N, Seifritz E, Gershman SJ, Dayan P, Roiser JP (2015) Interplay of approximate planning strategies. Proceedings of the National Academy of Sciences 112(10):3098–3103
  * Jain et al. (2021) Jain YR, Callaway F, Griffiths TL, Dayan P, Krueger PM, Lieder F (2021) A computational process-tracing method for measuring people’s planning strategies and how they change over time. Manuscript in revision
  * Jasper and Shapiro (2002) Jasper J, Shapiro J (2002) Mousetrace: A better mousetrap for catching decision processes. Behavior Research Methods, Instruments, & Computers 34(3):364–374
  * Kass and Raftery (1995) Kass RE, Raftery AE (1995) Bayes factors. Journal of the american statistical association 90(430):773–795
  * Kemtur et al. (2020) Kemtur A, Jain YR, Mehta A, Callaway F, Consul S, Stojcheski J, Lieder F (2020) Leveraging machine learning to automatically derive robust planning strategies from biased models of the environment. In: Proceedings of the 42nd Annual Conference of the Cognitive Science Society, pp 2405–2411
  * Konishi and Kitagawa (2008) Konishi S, Kitagawa G (2008) Information criteria and statistical modeling. Springer Science & Business Media
  * Kuhn (1962) Kuhn TS (1962) The structure of scientific revolutions. Chicago: University of Chicago Press
  * Langley et al. (1983) Langley P, Zytkow JM, Bradshaw GL, Simon HA (1983) Three facets of scientific discovery. In: IJCAI, Citeseer, pp 465–468
  * Langley et al. (1987) Langley P, Simon HA, Bradshaw GL, Zytkow JM (1987) Scientific discovery: Computational explorations of the creative processes. MIT press
  * Lieder et al. (2017) Lieder F, Krueger PM, Griffiths T (2017) An automatic method for discovering rational heuristics for risky choice. In: CogSci
  * Lieder et al. (2019) Lieder F, Callaway F, Jain Y, Krueger P, Das P, Gul S, Griffiths T (2019) A cognitive tutor for helping people overcome present bias. In: RLDM 2019
  * Lieder et al. (2020) Lieder F, Callaway F, Jain YR, Das P, Iwama G, Gul S, Krueger P, Griffiths TL (2020) Leveraging artificial intelligence to improve people’s planning strategies. Manuscript in revision
  * Liu et al. (2018) Liu G, Schulte O, Zhu W, Li Q (2018) Toward interpretable deep reinforcement learning with linear model u-trees. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer, pp 414–429
  * Moon (1996) Moon TK (1996) The expectation-maximization algorithm. IEEE Signal processing magazine 13(6):47–60
  * Myung et al. (2013) Myung JI, Cavagnaro DR, Pitt MA (2013) A tutorial on adaptive design optimization. Journal of mathematical psychology 57(3-4):53–67
  * Newell et al. (1972) Newell A, Simon HA, et al. (1972) Human problem solving, vol 104. Prentice-Hall Englewood Cliffs, NJ
  * Newton (1687) Newton I (1687) Philosophiae naturalis principia mathematica. William Dawson & Sons Ltd., London
  * Osa et al. (2018) Osa T, Pajarinen J, Neumann G, Bagnell JA, Abbeel P, Peters J, et al. (2018) An algorithmic perspective on imitation learning. Foundations and Trends® in Robotics 7(1-2):1–179
  * Ouyang et al. (2016) Ouyang L, Tessler MH, Ly D, Goodman N (2016) Practical optimal experiment design with probabilistic programs. arXiv preprint arXiv:160805046
  * Ouyang et al. (2018) Ouyang L, Tessler MH, Ly D, Goodman ND (2018) webppl-oed: A practical optimal experiment design system. In: CogSci
  * Payne et al. (1978) Payne JW, Braunstein ML, Carroll JS (1978) Exploring predecisional behavior: An alternative approach to decision research. Organizational Behavior and Human Performance 22(1):17–44
  * Payne et al. (1988) Payne JW, Bettman JR, Johnson EJ (1988) Adaptive strategy selection in decision making. Journal of experimental psychology: Learning, Memory, and Cognition 14(3):534
  * Payne et al. (1993) Payne JW, Bettman JR, Johnson EJ (1993) The adaptive decision maker. Cambridge University Press
  * Peterson et al. (2021) Peterson JC, Bourgin DD, Agrawal M, Reichman D, Griffiths TL (2021) Using large-scale experiments and machine learning to discover theories of human decision-making. Science 372(6547):1209–1214
  * Popper (1935) Popper K (1935) The Logic of Scientific Discovery. Routledge
  * Reichenbach (1938) Reichenbach H (1938) Experience and Prediction. An Analysis of the Foundations and the Structure of Knowledge. Chicago: The University of Chicago Press.
  * Riedl et al. (2008) Riedl R, Brandstätter E, Roithmayr F (2008) Identifying decision strategies: A process-and outcome-based classification method. Behavior research methods 40(3):795–807
  * Shrager and Langley (1990) Shrager J, Langley P (1990) Computational approaches to scientific discovery. In: Shrager J, Langley P (eds) Computational models of scientific discovery and theory formation, San Mateo, CA: Morgan Kaufmann
  * Silver et al. (2020) Silver T, Allen KR, Lew AK, Kaelbling LP, Tenenbaum J (2020) Few-shot bayesian imitation learning with logical program policies. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol 34, pp 10251–10258
  * Simon (1973) Simon HA (1973) Does scientific discovery have a logic? Philosophy of science 40(4):471–480
  * Simon and Newell (1971) Simon HA, Newell A (1971) Human problem solving: The state of the theory in 1970\. American Psychologist 26(2):145
  * Skirzyński et al. (2021) Skirzyński J, Becker F, Lieder F (2021) Automatic discovery of interpretable planning strategies. Machine Learning 110:2641–2683
  * Sozou et al. (2017) Sozou PD, Lane PC, Addis M, Gobet F (2017) Computational scientific discovery. Springer handbook of model-based science pp 719–734
  * Sutton and Barto (2018) Sutton RS, Barto AG (2018) Reinforcement learning: An introduction. MIT press
  * Svenson (1979) Svenson O (1979) Process descriptions of decision making. Organizational behavior and human performance 23(1):86–112
  * Verma et al. (2018) Verma A, Murali V, Singh R, Kohli P, Chaudhuri S (2018) Programmatically interpretable reinforcement learning. In: International Conference on Machine Learning, PMLR, pp 5045–5054
  * Vincent and Rainforth (2017) Vincent BT, Rainforth T (2017) The darc toolbox: automated, flexible, and efficient delayed and risky choice experiments using bayesian adaptive design. PsyArXiv October 20
  * Vrieze (2012) Vrieze SI (2012) Model selection and psychological theory: a discussion of the differences between the akaike information criterion (aic) and the bayesian information criterion (bic). Psychological methods 17(2):228
  * Westenberg and Koele (1994) Westenberg MR, Koele P (1994) Multi-attribute evaluation processes: Methodological and conceptual issues. Acta Psychologica 87(2-3):65–84
  * Whewell (1840) Whewell W (1840) The philosophy of the inductive sciences: founded upon their history, vol 1. JW Parker
  * Willemsen and Johnson (2011) Willemsen M, Johnson E (2011) Visiting the decision factory: observing cognition with MouselabWEB and other information acquisition Methods, pp 19 – 42

## Appendix

##  Appendix A.1 Human-Interpret parameters

Table A1 lists the values of the parameters of the Human-Interpret method that
we used in our benchmark planning environment (the Mouselab MDP). The goal of
the benchmark test was to discover and describe strategies used in this
environment by people.

Parameter | Value
---|---
exp_id | v1.0
num_participants | 180
block | train & test
num_clusters | 17
num_demos | 128
$\mathcal{L}$ | See Section A.2
features | See Section A.4
tolerance | $1\mathrm{e}{-4}$
change_tolerance | $1\mathrm{e}{-5}$
interpret_size | 5
ai_tolerance | 0.025
num_rollouts | 10000
num_ai_clusters | 4
expert_reward | 39.97
max_divergence | 0.2
threshold | 0.5
allowed_predicates | See Section A.3
redundant_predicates | See Section A.3
Table A1: Values for the parameters of Human-Interpret that were used in the
benchmark test.

##  Appendix A.2 Defining the Domain Specific Language

Our Domain Specific Language consisted of a number of logical predicates.
Every predicate we defined accepts (at least) two arguments: (belief) state of
the environment $b$ and computation/action $c$. In our case, the state relates
to the list of expected values of nodes in the Mouselab MDP, whereas the
computation is the number of the node to click, with $0$ reserved for
termination. The Mouselab MDP we used in the benchmark test had the form of a
tree, hence a lot of the predicates made use of notions used for the tree
graph structures. The meaning of the predicates, presented below in
alphabetical order, is the following:

### A

#####  all(b,c,pred1,pred2)

: All the nodes in the MDP that satisfy $pred_{1}$ also satisfy $pred_{2}$.

#####  among(b,c,pred1,pred2)

: This node is among all the nodes in the MDP that satisfy $pred_{1}$ and
inside that set it also satisfies $pred_{2}$.

#####  are_branch_leaves_observed(b,c)

: This node has successor leaves which are all observed.

#####  are_leaves_observed(b,c)

: All leaf nodes have been observed.

#####  are_roots_observed(b,c)

: All nodes on level 1 have been observed.

### D

#####  depth(b,c,d)

: This node lies on level $d$.

### H

#####  has_best_path(b,c,list)

: This node lies on a path for which the sum of expected rewards is the
highest for the paths on which other nodes in $list$ lie.

#####  has_child_highest_value(b,c,list)

: This node has a child with an observed value that is higher than any other
observed child’s value for the nodes from $list$.

#####  has_child_highest_level_value(b,c)

: This node’s child has the maximum possible value on its level.

#####  has_child_lowest_value(b,c,list)

: This node has a child with an observed value that is lower than any other
observed child’s value for the nodes from $list$.

#####  has_child_lowest_level_value(b,c)

: This node’s child has the minimum posible value of its level.

#####  has_largest_depth(b,c,list)

: This node is the deepest in the tree among the nodes from $list$.

#####  has_leaf_highest_value(b,c,list)

: This node has a successor that is a leaf with an observed value that is
higher than any other observed successor-leaf’s value for the nodes from
$list$.

#####  has_leaf_highest_level_value(b,c)

: This node leads to an uncovered leaf that has the maximum possible value on
its level.

#####  has_leaf_lowest_value(b,c,list)

: This node has a successor that is a leaf with an observed value that is
lower than any other observed successor-leaf’s value for the nodes from
$list$.

#####  has_leaf_lowest_level_value(b,c)

: This node leads to an uncovered leaf that has the minimum possible value on
its level

#####  has_most_branches(b,c,list)

: This node belongs to the largest number of paths among the nodes in $list$.

#####  has_parent_highest_value(b,c,list)

: This node has a parent with an observed value that is higher than any other
observed parent’s value for the nodes from $list$.

#####  has_parent_highest_level_value(b,c)

: This node’s parent has the maximum possible value on its level.

#####  has_parent_lowest_value(b,c,list)

: This node has a parent with an observed value that is lower than any other
observed parent’s value for the nodes from $list$.

#####  has_parent_lowest_level_value(b,c)

: This node’s parent has the minimum possible value of its level.

#####  has_root_highest_value(b,c,list)

: This node has an ancestor on level 1 with an observed value that is higher
than any other observed 1st-level ancestor’s value for the nodes from $list$.

#####  has_root_highest_level_value(b,c)

: This node can be accessed through an observed node on level 1 which has the
highest value on level 1.

#####  has_root_lowest_value(b,c,list)

: This node has an ancestor on level 1 with an observed value that is lower
than any other observed 1st-level ancestor’s value for the nodes from $list$.

#####  has_root_lowest_level_value(b,c)

: This node can be accessed through an observed node on level 1 which has the
minimum value on level 1.

#####  has_smallest_depth(b,c,list)

: This node is the shallowest in the tree among the nodes from $list$.

### I

#####  is_ancestor_max_val(b,c)

: One of the ancestors of this node is uncovered and has the maximum possible
value in the MDP.

#####  is_leaf(b,c)

: This node is a leaf.

#####  is_max_in_branch(b,c)

: This node lies on a path with an uncovered maximum possible value in the
MDP.

#####  is_2max_in_branch(b,c)

: This node lies on a path with 2 uncovered maximum possible values in the
MDP.

#####  is_observed(b,c)

: This node was already clicked and is observed.

#####  is_on_highest_expected_value_path(b,c)

: This node lies on a path that has the highest expected value.

#####  is_positive_observed(b,c)

: There is a node with a positive value observed.

#####  is_previous_observed_max(b,c)

: The previously observed node uncovered the maximum possible value in the
MDP.

#####  is_previous_observed_max_leaf(b,c)

: The previously observed node is a leaf and it uncovered the maximum possible
value in the MDP.

#####  is_previous_observed_max_level(b,c)

: The previously observed node uncovered a maximum possible value on that
level.

#####  is_previous_observed_max_nonleaf(b,c)

: The previously observed node isn’t a leaf and it uncovered the maximum
possible value in the MDP.

#####  is_previous_observed_max_root(b,c)

: The previously observed node lies on level 1 and it uncovered the maximum
possible value in the MDP.

#####  is_previous_observed_min(b,c)

: The previously observed node uncovered the minimum possible value in the
MDP.

#####  is_previous_observed_min_level(b,c)

: The previously observed node uncovered a minimum possible value on that
level.

#####  is_previous_observed_parent(b,c)

: The previously observed node is the parent of this node.

#####  is_previous_observed_sibling(b,c)

: The previously observed node is one of the siblings of this node.

#####  is_root(b,c)

: This node is one of the nodes on level 1.

#####  is_successor_max_val(b,c)

: One of the successors of this node is uncovered and has the maximum possible
value in the MDP.

### O

#####  observed_count(b,c,n)

: There are at least $n$ observed nodes.

### T

#####  termination_return(b,c,e)

: The expected reward after stopping now is $\geq e$.

The DSL we used for studying Mouselab MDP policies was generated through a
probabilistic context-free grammar with the following format:

Listing 1: Probabilistic context-free grammar that generates the predicates
used by AI-Interpret and in consequence by Human-Interpret. Probability of
each production is uniform with respect to the non-terminal symbol on its left
hand-side.

⬇

START $\rightarrow$ all(PREDS_AMONG_PRED_DEPTH)

START $\rightarrow$ all(PREDS_AMONG_PRED_LEAF)

START $\rightarrow$ all(PREDS_AMONG_PRED_ROOT)

START $\rightarrow$ all(PREDS_AMONG_PRED_PARENT)

START $\rightarrow$ all(PREDS_AMONG_PRED_CHILD)

START $\rightarrow$ all(PREDS_AMONG_PRED_PRED)

START $\rightarrow$ among(PREDS_AMONG_PRED_DEPTH)

START $\rightarrow$ among(PREDS_AMONG_PRED_LEAF)

START $\rightarrow$ among(PREDS_AMONG_PRED_ROOT)

START $\rightarrow$ among(PREDS_AMONG_PRED_PARENT)

START $\rightarrow$ among(PREDS_AMONG_PRED_CHILD)

START $\rightarrow$ among(PREDS_AMONG_PRED_PRED)

START $\rightarrow$ among(PREDS_DEPTH)

START $\rightarrow$ among(PREDS_LEAF)

START $\rightarrow$ among(PREDS_ROOT)

START $\rightarrow$ among(PREDS_PARENT)

START $\rightarrow$ among(PREDS_CHILD)

START $\rightarrow$ among(PREDS_PRED)

START $\rightarrow$ PRED

START $\rightarrow$ GENERAL_PRED

PREDS_AMONG_PRED_DEPTH $\rightarrow$ PREDS_DEPTH, AMONG_CHILD

PREDS_AMONG_PRED_DEPTH $\rightarrow$ PREDS_DEPTH, AMONG_PARENT

PREDS_AMONG_PRED_DEPTH $\rightarrow$ PREDS_DEPTH, AMONG_LEAF

PREDS_AMONG_PRED_DEPTH $\rightarrow$ PREDS_DEPTH, AMONG_ROOT

PREDS_AMONG_PRED_LEAF $\rightarrow$ PREDS_LEAF, AMONG_CHILD

PREDS_AMONG_PRED_LEAF $\rightarrow$ PREDS_LEAF, AMONG_PARENT

PREDS_AMONG_PRED_LEAF $\rightarrow$ PREDS_LEAF, AMONG_ROOT

PREDS_AMONG_PRED_LEAF $\rightarrow$ PREDS_LEAF, AMONG_PRED

PREDS_AMONG_PRED_ROOT $\rightarrow$ PREDS_ROOT, AMONG_CHILD

PREDS_AMONG_PRED_ROOT $\rightarrow$ PREDS_ROOT, AMONG_PARENT

PREDS_AMONG_PRED_ROOT $\rightarrow$ PREDS_ROOT, AMONG_LEAF

PREDS_AMONG_PRED_ROOT $\rightarrow$ PREDS_ROOT, AMONG_PRED

PREDS_AMONG_PRED_PARENT $\rightarrow$ PREDS_PARENT, AMONG_CHILD

PREDS_AMONG_PRED_PARENT $\rightarrow$ PREDS_PARENT, AMONG_LEAF

PREDS_AMONG_PRED_PARENT $\rightarrow$ PREDS_PARENT, AMONG_ROOT

PREDS_AMONG_PRED_PARENT $\rightarrow$ PREDS_PARENT, AMONG_PRED

PREDS_AMONG_PRED_CHILD $\rightarrow$ PREDS_CHILD, AMONG_PARENT

PREDS_AMONG_PRED_CHILD $\rightarrow$ PREDS_CHILD, AMONG_LEAF

PREDS_AMONG_PRED_CHILD $\rightarrow$ PREDS_CHILD, AMONG_ROOT

PREDS_AMONG_PRED_CHILD $\rightarrow$ PREDS_CHILD, AMONG_PRED

PREDS_AMONG_PRED_PRED $\rightarrow$ PREDS_PRED, AMONG_CHILD

PREDS_AMONG_PRED_PRED $\rightarrow$ PREDS_PRED, AMONG_PARENT

PREDS_AMONG_PRED_PRED $\rightarrow$ PREDS_PRED, AMONG_LEAF

PREDS_AMONG_PRED_PRED $\rightarrow$ PREDS_PRED, AMONG_ROOT

PREDS_AMONG_PRED_PRED $\rightarrow$ PREDS_PRED, AMONG_PRED

PREDS_DEPTH $\rightarrow$ DEPTH

PREDS_DEPTH $\rightarrow$ DEPTH and LEAF

PREDS_DEPTH $\rightarrow$ DEPTH and ROOT

PREDS_DEPTH $\rightarrow$ DEPTH and PARENT

PREDS_DEPTH $\rightarrow$ DEPTH and CHILD

PREDS_DEPTH $\rightarrow$ DEPTH and DEPTH

PREDS_DEPTH $\rightarrow$ DEPTH and PRED

PREDS_LEAF $\rightarrow$ LEAF

PREDS_LEAF $\rightarrow$ LEAF and LEAF

PREDS_LEAF $\rightarrow$ LEAF and ROOT

PREDS_LEAF $\rightarrow$ LEAF and PARENT

PREDS_LEAF $\rightarrow$ LEAF and CHILD

PREDS_LEAF $\rightarrow$ LEAF and PRED

PREDS_ROOT $\rightarrow$ ROOT

PREDS_ROOT $\rightarrow$ ROOT and ROOT

PREDS_ROOT $\rightarrow$ ROOT and PARENT

PREDS_ROOT $\rightarrow$ ROOT and CHILD

PREDS_ROOT $\rightarrow$ ROOT and PRED

PREDS_PARENT $\rightarrow$ PARENT

PREDS_PARENT $\rightarrow$ PARENT and PARENT

PREDS_PARENT $\rightarrow$ PARENT and CHILD

PREDS_PARENT $\rightarrow$ PARENT and PRED

PREDS_PARENT $\rightarrow$ PARENT

PREDS_PARENT $\rightarrow$ PARENT and PARENT

PREDS_PARENT $\rightarrow$ PARENT and CHILD

PREDS_PARENT $\rightarrow$ PARENT and PRED

PREDS_CHILD $\rightarrow$ CHILD

PREDS_CHILD $\rightarrow$ CHILD and CHILD

PREDS_CHILD $\rightarrow$ CHILD and PRED

PREDS_PRED $\rightarrow$ PRED

PREDS_PRED $\rightarrow$ PRED and PRED

AMONG_PRED $\rightarrow$ has_smallest_depth $\mid$ has_largest_depth

AMONG_PRED $\rightarrow$ has_best_path $\mid$ has_most_paths

AMONG_CHILD $\rightarrow$ has_child_highest_value $\mid$
has_child_lowest_value

AMONG_PARENT $\rightarrow$ has_parent_highest_value $\mid$
has_parent_lowest_value

AMONG_LEAF $\rightarrow$ has_leaf_highest_value $\mid$ has_leaf_lowest_value

AMONG_ROOT $\rightarrow$ has_root_highest_value $\mid$ has_root_lowest_value

DEPTH $\rightarrow$ depth(DEP) $\mid$ not(depth(DEP))

LEAF $\rightarrow$ has_leaf_highest_level_value $\mid$
has_leaf_lowest_level_value

LEAF $\rightarrow$ not(has_leaf_highest_level_value)

LEAF $\rightarrow$ not(has_leaf_lowest_level_value)

ROOT $\rightarrow$ has_root_highest_level_value $\mid$
has_root_lowest_level_value

ROOT $\rightarrow$ not(has_root_highest_level_value)

ROOT $\rightarrow$ not(has_root_lowest_level_value)

PARENT $\rightarrow$ has_parent_highest_level_value $\mid$
has_parent_lowest_level_value

PARENT $\rightarrow$ not(has_parent_highest_level_value)

PARENT $\rightarrow$ not(has_parent_lowest_level_value)

CHILD $\rightarrow$ has_child_highest_level_value $\mid$
has_child_lowest_level_value

CHILD $\rightarrow$ not(has_child_highest_level_value)

CHILD $\rightarrow$ not(has_child_lowest_level_value)

PRED $\rightarrow$ is_leaf $\mid$ is_root $\mid$ is_max_in_branch

PRED $\rightarrow$ is_2max_in_branch $\mid$ are_branch_leaves_observed

PRED $\rightarrow$ not(is_leaf) $\mid$ not(is_root) $\mid$
not(is_max_in_branch)

PRED $\rightarrow$ not(is_2max_in_branch)

PRED $\rightarrow$ not(are_branch_leaves_observed) $\mid$ not(is_observed)

GENERAL_PRED $\rightarrow$ is_previous_observed_max $\mid$
is_positive_observed

GENERAL_PRED $\rightarrow$ are_leaves_observed

GENERAL_PRED $\rightarrow$ are_roots_observed $\mid$
is_previous_observed_positive

GENERAL_PRED $\rightarrow$ is_previous_observed_parent

GENERAL_PRED $\rightarrow$ is_previous_observed_sibling

GENERAL_PRED $\rightarrow$ is_previous_observed_min

GENERAL_PRED $\rightarrow$ is_previous_observed_max_nonleaf

GENERAL_PRED $\rightarrow$ is_previous_observed_max_leaf

GENERAL_PRED $\rightarrow$ is_previous_observed_max_root

GENERAL_PRED $\rightarrow$ is_previous_observed_max_level(DEP)

GENERAL_PRED $\rightarrow$ is_previous_observed_min_level(DEP)

GENERAL_PRED $\rightarrow$ observed_count(NUM) $\mid$ termination_return(RET)

NUM $\rightarrow$ 1 $\mid$ 2 $\mid$ 3 $\mid$ 4 $\mid$ 5 $\mid$ 6 $\mid$ 7
$\mid$ 8

DEP $\rightarrow$ 1 $\mid$ 2 $\mid$ 3

RET $\rightarrow$ -30 $\mid$ -25 $\mid$ -15 $\mid$ -10 $\mid$ 0 $\mid$ 10
$\mid$ 15 $\mid$ 25 $\mid$ 30

##  Appendix A.3 Defining redundant and allowed predicates

The redundant_predicates parameter of Human-Interpret controls which
predicates are to be removed from the DNF formula before it is turned into
linear temporal logic formula. The allowed_predicates parameter specifies
which predicates are considered for the until and unless conditions. We used
the following values:

$\displaystyle\texttt{allowed\\_predicates}=$ $\displaystyle\ [\text{All
predicates derived from GENERAL\\_PRED in the CFG above},$ $\displaystyle\
is\\_max\\_in\\_branch,\ are\\_branch\\_leaves\\_observed]$
$\displaystyle\texttt{redundant\\_predicates}=$ $\displaystyle\ [\text{All
predicates of the type {all}(b,c,pred${}_{1}$,pred${}_{2}$)},$ $\displaystyle\
\texttt{allowed\\_predicates}]$

##  Appendix A.4 Defining features for the softmax models

The generative models created in the generative step of the Human-Interpret
algorithm take form of softmax functions shown in Equation 2. Those function
are defined on a set of features derived from the Mouselab MDP in a given
(belief) state $b$ while taking a given computation/action $c$ (node to
click). We used the following features in the benchmark test:

### C

#####  count_observed_node_branch(b,c)

: What is the minimum of the number of observed nodes on branches that pass
through the given node.

### D

#####  depth_count(b,c)

: What is the number of observed nodes on the same depth as the given node.

#####  depth(b,c)

: What is the depth of the given node.

### G

#####  get_level_observed_std(b,c)

: What is the standard deviation for the values of observed nodes at the same
level as the given node.

### H

#####  hp_0(b,c)

: Does the path that the node lies on has a value greater than 0.

### I

#####  immediate_successor_count(b,c)

: What is the number of observed children of the given node.

#####  is_leaf(b,c)

: Is the given node a leaf or not.

#####  is_previous_max(b,c)

: Did the previously observed node uncover the maximum possible value in the
MDP or not.

#####  is_root(b,c)

: Is the given node a root or not.

### M

#####  most_promising(b,c)

: Whether the given node lies on the path with the highest expected reward or
not.

### O

#####  observed_height(b,c)

: What is the maximum number of consecutively observed nodes on the path of
the given node, starting from its children.

### P

#####  parent_observed(b,c)

: Whether the parent of the given node is observed or not.

#####  previous_observed_successor(b,c)

: Whether the previously observed node was the parent of the given node or
not.

### S

#####  second_most_promising(b,c)

: Whether the given node lies on the path with the second highest expected
reward or not.

#####  siblings_count(b,c)

: What is the number of observed siblings of the given node.

#####  soft_satisficing(b,c)

: What is the expected reward of terminating now and traversing the most
promising path.

#####  successor_uncertainty(b,c)

: What is the total standard deviation for the children of the given node.

### T

#####  termination_constant(b,c)

: The value of this feature is 0 for the termination action and is -1 for all
the nodes.

### U

#####  uncertainty(b,c)

: What is the total standard deviation for the nodes on the same depth as the
given node.

##  Appendix A.5 Description of the DNF2LTL algorithm

This section describes the method for transforming the output of AI-Interpret
into a procedural description of how to plan that explicitly states which
planning operation should be performed first, second, third, and so on. This
method is called DNF2LTL and its description is taken from an upcoming paper
by Becker et al. (2021).

The original output of AI-Interpret is a Disjunctive Normal Form formula (DNF;
see Definition 8). DNF2LTL transforms such formulas into the procedural format
of Linear Temporal Logic (LTL; see Definition 9). DNF2LTL operates in 2
phases. In the first phase, it modifies the input disjunctive normal form
formula into an entity called a _procedural formula_ (see Definition 12), that
is an expression in a specific from of linear temporal logic. In the second
phase, the procedural formula is pruned to remove as many unnecessary
predicates as possible and obtain the possibly simplest procedural description
of the automatically discovered strategy. Before we delve into the nuts and
bolts of DNF2LTL, we formally define a handful of important notions.

###  A.5.1 Definitions

######  Definition 8 (Disjunctive Normal Form)

Let $f_{i},h:\mathcal{X}\rightarrow\\{0,1\\}$ for $i\in\mathbb{N}$ be binary-
valued functions (predicates) on domain $\mathcal{X}$. We call
$f_{1}(\bm{x})\lor f_{2}(\bm{x})\lor\dots\lor f_{n}(\bm{x})$ a disjunction of
predicates and $f_{1}(\bm{x})\land f_{2}(\bm{x})\land\dots\land f_{n}(\bm{x})$
a conjunction of predicates. We say that $h$ is in disjunctive normal form
(DNF) if $h$ is a conjunction of disjunctions of predicates $f_{i}$.

######  Definition 9 (Linear Temporal Logic)

Let $\mathcal{P}$ be the set of propositional variables $p$ (variables that
can be either true or false), let $\lnot,\land,\lor$ be standard logical
operators for negation, AND, and OR, respectively, and let
$\mathbf{X},\mathbf{U},\mathbf{W}$ be modal operators for NEXT, UNTIL, and
UNLESS, respectively. Linear temporal logic (LTL) is a logic defined on
(potentially infinite) sequences of truth-assignments of propositional
variables. LTL formulas are expressions that state which of the variables are
true, and when they are true in the sequence. Whenever this agrees with the
actual truth-assignment in an input sequence, then we say that a formula is
true.

Formally, for $\alpha$ and $\beta$ being LTL formulas, we define a formula to
be expressed in LTL inductively: $\psi$ is an LTL formula if
$\psi\in\mathcal{P}$ ($\psi$ states that one of the variables is true in the
first truth-assignment in the sequence), $\psi=\lnot\alpha$ ($\psi$ is a
negation of an LTL formula), $\psi=\alpha\lor\beta$ ($\psi$ is a disjunction
of two LTL formulas), $\psi=\alpha\land\beta$ ($\psi$ is a conjunction of two
LTL formulas), $\psi=\mathbf{X}\alpha$ ($\psi$ states that LTL formula
$\alpha$ is true starting from the next truth-assignment in the sequence) or
$\psi=\alpha\mathbf{U}\beta$ ($\psi$ states that LTL formula $\alpha$ is true
until some truth-assignment in the sequence where LTL formula $\beta$ becomes
true).

######  Definition 10 (Hold modal operator)

The HOLD operator $\mathbf{H}$ is a unary operator in the linear temporal
logic. LTL formula $\mathbf{H}\psi$ states that $\psi$ is true at least for
the first truth-assignment in the sequence of truth-assignments, and then
eventually becomes false. HOLD operator is the UNTIL operator with a default
until condition ("until it is no longer satisfied").

######  Definition 11 (Loop modal operator)

The LOOP operator $\mathbf{L}$ is a binary operator in the linear temporal
logic. LTL formula $\phi\mathbf{L}\psi$ states that i) part of $\phi$ is an
LTL formula $\psi$, ii) if $\psi$ is replaced with some number of NEXT $\psi$
operators $\mathbf{X}\psi\land\dots\land\ \mathbf{X}\psi$, then the new $\phi$
is true across the whole sequence of truth-assignments. In other words, the
LOOP operator states that in order for LTL formula $\phi$ to be true and
satisfy all truth-assignments in the sequence, LTL formula $\psi$ inside of
$\phi$ needs to repeated appropriate amount of times (form a “loop”). This
formula corresponds to truth-assignments in the sequence that disagree with
$\phi$.

######  Definition 12 (Procedural formula)

We say that $f$ is a procedural formula if and only if $f$ is an expression
written in linear temporal logic where the propositional variables are
predicates $h:\mathcal{S}\times\mathcal{A}\rightarrow\\{0,1\\}$ for some set
of states $\mathcal{S}$ and some set of actions $\mathcal{A}$, and where the
modal operators are $\mathbf{X}$ (NEXT), $\mathbf{U}$ (UNTIL), $\mathbf{W}$
(UNLESS), $\mathbf{H}$ (HOLD), and $\mathbf{L}$ (LOOP).

######  Definition 13 (Trajectory)

A trajectory $\tau=[\phi_{0},...,\phi_{N-1}]$ is a sequence of $N$ state-
action pairs $\phi_{i}=(s_{i},a_{i})$ with
$s_{i}\in\mathcal{S},a_{i}\in\mathcal{A},i=0,...,N-1$.

###  A.5.2 Transforming disjunctive normal form formulas into procedural
formulas

In the first phase, DNF2LTL generates a procedural formula out of a DNF
formula. To do so, our algorithm accepts four main inputs: the set of
trajectories that led to the creation of the DNF formula, a set of predicates
that could serve as the until or unless conditions, a set of predicates which
are unwanted in the procedural formula, and, naturally, the DNF formula
itself. The trajectories play the role of the sequences of truth-assignments
from Definition 9, whereas the set of predicates for until/unless conditions
and the DNF formula define the building blocks out of which the procedural
formula would be constructed. The other remaining parameter is optional, and
in case of a failure in producing an output, the algorithm is ran again
without removing the redundant predicates. On a high level, our algorithm
exploits the idea that a DNF formula is satisfied when at least one of its
conjunctions is satisfied. It iterates over the trajectories to discover the
dynamics of changes in truth values of the conjunctions, and uses the
conjunctions, the found dynamics, and the candidate until/unless conditions to
generate procedural formulas.

During the first phase DNF2LTL generates an initial procedural description in
four steps. In the first step, the algorithm extracts potential subroutines
from the inputted DNF formula. In the second step, the algorithm determines
the order in which those subroutines should be performed. In the third step,
the algorithm computes the logical conditions for transitioning from each step
to the next. Finally, in the fourth step, our method connects the subroutines
with the appropriate conditions into a complete procedural description and
outputs the result. Algorithm 2 presents a pseudo code that implements the
first phase of DNF2LTL and the following paragraph provides a technical
description of each of these four steps. Readers who are primarily interested
in the big picture and the application to boosting human planning can skip
these technical details.

  1. Step 1:

DNF2LTL starts by dividing the DNF formula into a set of conjunctions and
removing all the unwanted predicates.

  2. Step 2:

Then, it iterates over the trajectories and for each trajectory records the
sequence of conjunctions that were true for that trajectory so that the whole
DNF formula could be true across all the state-action pairs within it. Our
algorithm then creates a transition graph where conjunction $c_{i}$ is
connected with conjunction $c_{j}$ if there is at least one trajectory$\tau$
where the value of $c_{i}$ changed from true to false at the same moment when
the value of $c_{j}$ changed from false to true. The transition graph is used
to generate maximum length sequences of conjunctions $c_{i_{1}}c_{i_{2}}\dots
c_{i_{n}}$ in order to capture the possibly fullest transition evidenced in
the data. The last predicate in this sequence (i.e., $c_{i_{n}}$) either has
no outgoing connections in the transition graph or connects to one of the
$c_{i_{j}}$s in which case the sequence ends with a special loop symbol that
indicates which $i_{j}$ that is. The resulting maximum length sequences (with
potential loop symbols at the end) are used to define equivalence classes for
the trajectories. These equivalence classes represent potential dynamics of
how the conjunctions change their truth values so that the full DNF formula
was satisfied. To find a small subset of equivalences classes that is
sufficient to describe all of the trajectories, each trajectory, treated as a
sequence of conjunctions of the DNF formula, is assigned to one equivalence
class. Namely, for trajectory $\tau$, the first encountered equivalence class
is chosen, for which its sequence contains a subsequence representing $\tau$.
For instance if $\tau$ is represented by sequence $c_{1}c_{3}$, it could be
assigned to equivalence class $c_{1}c_{2}c_{3}c_{4}LOOPc_{2}$.

  3. Step 3:

Then, the algorithm selects the unempty equivalence classes, which represent
dynamics that occur in the trajectories, and tries to transform the sequences
representing the equivalence classes into procedural formulas. It does so by
using the trajectories in the class to iteratively find conditions for the
UNTIL operator (UNTIL conditions) that could separate each of the elements in
the sequence representing the class. During one iteration, DNF2LTL searches
for the UNTIL condition separating a pair of subsequent conjunctions. The
UNTIL conditions are the allowed predicates provided as an input to the method
and 2-element disjunctions of those predicates which are created on the fly.
The candidate conditions are generated by searching for conditions whose truth
value changes from constantly false, while one element of the sequence of
conjunctions is true, to true, when the next element becomes true. Since there
may be multiple conditions which conform to this criterion, we use
probabilistic reasoning to choose the best one. Concretely, we test all
candidate conditions and for each build a simplified procedural formula. The
first part of that formula connects the consecutive conjunctions from the
sequence according to the conditions selected in the previous iterations, then
connects the currently considered pair of conjunctions with one of the
candidate conditions, and ends the formula with an always $TRUE$ predicate to
capture that the rest of the steps are yet unspecified. Each such partial
formula serves to induce a probabilistic policy. DNF2LTL uses these policies
to specify the likelihood of each trajectory of planning operations under
alternative procedural formulas. Then, the algorithm utilizes the maximum
likelihood principle and selects the candidate UNTIL condition that explains
the trajectories best. If some of the trajectories have a conjunction
representation shorter than the representation of the class, the algorithm
also adds an UNLESS operator after the UNTIL operator, and searches for the
UNLESS condition in a similar way. If it fails in finding the UNTIL condition,
it runs the algorithm again without removing the redundant predicates or, if
no predicates had been removed in the first pass, it adds the HOLD operator
instead. Similarly, if it fails in finding the UNLESS condition, it either
runs the algorithm again without removing the predicates, or if nothing was
removed, it adds $FALSE$ instead. This allows to find an imperfect procedural
formula, that allows for excessive planning, in the case when the UNLESS
condition cannot be expressed in the current DNF. After finding the UNTIL (and
perhaps the UNLESS) condition, the subroutines represented by the two
conjunctions from the sequence are separated with the found condition(s) and
then connected via the NEXT operator. This process then continues. If the last
pair of conjunctions from the sequence representing the equivalence class
contains a conjunction and a loop symbol, this symbol is transformed into the
LOOP operator (see Definition 11) and the conjunction and the loop operator
are joined through the NEXT operator. If there are demonstrations that end
before the loop, the UNLESS operator is added in the same way as before.

  4. Step 4:

After generating the procedural formulas for each of the equivalence classes
the final procedural formula is returned as a disjunction of these formulas.
Note, however, that only one of the elements in the disjunction is returned by
DNF2LTL after it performs pruning (see below).

Our algorithm captures a very special type of procedural formulas. For a DNF
formula with only one conjunction, the structure of the output can be
described by the the regular expression

$\left[\mathbf{H}\ \Phi\land\mathbf{N}\ |\ \Phi\ \mathbf{U}\ P\ (\mathbf{W}\
P)\land\mathbf{N}\right]^{+}\left[\mathbf{H}\ \Phi\ |\ \Phi\ \mathbf{U}\ P\ |\
\mathbf{L}\ P\right](\mathbf{W}\ P)$ (7)

where $P$ may be substituted with either of the input allowed predicates or
their 2-element disjunction, and $\Phi$ may be substituted with an arbitrary
conjunction of those predicates. The expression given in Equation 7 thus
generates procedural formulas in the form of a sequence of NEXT operators,
where subsequent conjunctions are separated with UNTIL conditions (and/or
UNLESS conditions) or accompanied by the HOLD operator. The formula ends with
the last NEXT operator or with a LOOP operator.

Input: DNF formula $f$;

Set of $N$ trajectories
$D=\\{((s_{1j},a_{1j}))_{j=1}^{l_{1}},\dots,((s_{Nj},a_{Nj}))_{j=1}^{l_{N}}]\\}$;

Unless/until predicates $P$;

Redundant predicates $R$;

Output: Procedural formula $\psi$;

1: Transform the trajectories in $D$ into a matrix of predicate truth-
assignments $M_{D}$

2: $L\leftarrow\text{lengths of trajectories in }D$

3: Transform $f$ to a list of $m$ conjunctions $C=[p_{11}\land\dots\land
p_{1n_{1}},\dots,p_{m1}\land\dots\land p_{mn_{m}}]$.

4: Remove redundant predicates $R$ from $C$.

5: if Nothing was removed and $len(C)==1$ then

6: $\xi=C[0]$

7: return $\psi=\mathbf{H}\ \xi$

8: end if

9: $G\leftarrow\text{graph of connections between }c\in C\text{ based on }D$

10: $S\leftarrow\text{max length sequences from }G$

11: $E\leftarrow\text{equivalence classes from }S,D$

12: for $e\in E$ do

13: $e_{trajs}\leftarrow\text{Trajectories from }e$.

14: for $\beta$ in $e$ do

15: if $loop$ in $\beta$ then

16: Use the special $loop$ symbol in $\beta$ to determine the conjunction to
return to $\gamma$.

17: $\phi=\phi\ \mathbf{L}\ \gamma$

18: Go to step 29

19: end if

20: $\Theta\leftarrow\text{possible until conditions found with
}e_{trajs},M_{D},\beta$.

21: if success then

22:
$\theta^{*}\leftarrow\operatorname*{arg\,max}_{\theta\in\Theta}\text{likelihood}(e_{trajs},\phi\land\mathbf{N}\
\beta\ \mathbf{U}\ \theta)$

23: $\phi=\beta\ \mathbf{U}\ \theta$

24: else if nothing was removed from $C$ then

25: $\phi=\mathbf{H}\ \beta$

26: else

27: Run the algorithm with $R=\emptyset$

28: end if

29: Determine if some trajectories in $e_{trajs}$ differ in length and the
unless operator is necessary.

30: if necessary then

31: $\Theta\leftarrow\text{possible unless conditions found with
}e_{trajs},M_{D},\beta$.

32: if success then

33:
$\theta^{*}\leftarrow\operatorname*{arg\,max}_{\theta\in\Theta}\text{likelihood}(e_{trajs},\phi\
\mathbf{W}\ \theta)$

34: $\phi=\phi\ \mathbf{W}\ \theta$

35: else if nothing was removed from $C$ then

36: $\phi=\phi\ \mathbf{W}\ \mathbf{true}$

37: else

38: Run the algorithm with $R=\emptyset$

39: end if

40: end if

41: if $\beta$ is not last in $e$ then

42: $\phi=\phi\land\mathbf{N}$

43: end if

44: end for

45: if $\beta$ is the first element in $e$ then

46: $\psi=\phi$

47: else

48: $\psi=\psi\lor\phi$

49: end if

50: end for

51: return $\psi$

Algorithm 2 First phase of DNF2LTL which generates procedural formulas out of
DNF formulas.

###  A.5.3 Pruning

After our algorithm generates a procedural formula $\Psi$ in the first phase,
it enters the second phase. During the second phase, DNF2LTL prunes the
predicates appearing in the conjunctions of $\Psi$. Recall, however, $\Psi$ is
a disjunction of procedural formulas. Because of this reason, pruning occurs
for each element of that disjunction separetely. To do so, DNF2LTL maps each
procedural formula $\psi_{i}$ of the disjunction $\Psi$ onto a distinct binary
vector $b_{i}$. Each element of $b_{i}$ is the truth value of one of the
predicates appearing in the conjunctions making up $psi_{i}$. Our algorithm
iterates over $b_{i}$s and in each step performs a greedy optimization.
Concretely, for each consecutive predicate of $\psi_{i}$ the corresponding
entry of $b_{i}$ is set to zero if and only if removing that predicate
increases the likelihood of the trajectories under the pruned description
relative to the unpruned description. Some of the predicates increase the
likelihood and are consequently pruned. After performing this optimization for