# EXPIL: Explanatory Predicate Invention for Learning in Games

Jingyuan Sha1 Hikaru Shindo1 Quentin Delfosse 1
Kristian Kersting1,2,3 Devendra Singh Dhami4
1Technical University of Darmstadt
2Hessian Center for Artificial Intelligence(hessian.AI)
3German Research Centre for Artificial Intelligence (DFKI)
4Eindhoven University of Technology
{jingyuan.sha, hikaru.shindo, quentin.delfosse<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Reinforcement learning (RL) has proven to be a powerful tool for training
agents that excel in various games. However, the black-box nature of neural
network models often hinders our ability to understand the reasoning behind
the agent’s actions. Recent research has attempted to address this issue by
using the guidance of pretrained neural agents to encode logic-based policies,
allowing for interpretable decisions. A drawback of such approaches is the
requirement of large amounts of predefined background knowledge in the form of
predicates, limiting its applicability and scalability. In this work, we
propose a novel approach, _Explanatory Predicate Invention for Learning in
Games (EXPIL)_ , that identifies and extracts predicates from a pretrained
neural agent, later used in the logic-based agents, reducing the dependency on
predefined background knowledge. Our experimental evaluation on various games
demonstrate the effectiveness of EXPIL in achieving explainable behavior in
logic agents while requiring less background knowledge.

##  1 Introduction

Deep reinforcement learning (RL) agents have revolutionized the field by
employing neural networks to make decisions based on unstructured input state
spaces, thereby removing the necessity for manual feature engineering Mnih et
al. (2015); Silver et al. (2016); Sutton and Barto (2018). This advancement
allows these agents to autonomously learn complex tasks. However, despite
their impressive capabilities, these black-box policies present significant
challenges. One major issue is their lack of _interpretability_ Rudin (2019),
which refers to their inability to provide a clear and understandable
explanation of the reasoning behind their action selections. This opaqueness
makes it difficult for humans to trust and verify the decision-making
processes of these agents. Furthermore, these policies often exhibit a lack of
robustness when faced with small environmental changes Pinto et al. (2017);
Wulfmeier, Posner, and Abbeel (2017). This fragility can lead to suboptimal
policies or even catastrophic performance drops when the agents encounter
situations that differ from their training conditions di Langosco et al.
(2022); Delfosse et al. (2024a); Kohler et al. (2024), and their inherent lack
of interpretability prevents human experts from identifying and correcting
potentially misaligned behaviors Delfosse et al. (2024b).

To address this limitation, neuro-symbolic RL (NeSy-RL) combines the learning
power of neural networks with the interpretable nature of symbolic logic and
reasoning. NeSy-RL policies are not only transparent, but can enhance
performances, surpassing purely neural agents and improving generalization
capability Jiang and Luo (2019); Delfosse et al. (2023b). Their policies
encode a weighted set of action rules (_e.g._ distilled from a pretrained
neural policy). These rules combine a set of state-facts (such as the agent is
close to the enemy or the agent above from the treasure) by applying
predefined concepts (_e.g._ closeby, above) to the detected entities. At
inference, these state-facts are evaluated in each weighted rule to select an
action.

Figure 1: EXPIL introduces predicate invention within neuro-symbolic RL
agents. EXPIL extracts concepts from a replay buffer, lated employed to
compute optimal actions through neuro-symbolic policies. In contrast to neural
policies, EXPIL generates highly interpretable policies using logic and
requires few hand-crafted priors compared to conventional neuro-symbolic
policies.

The major flaw of such existing NeSy-RL systems is their reliance on complex,
hand-crafted priors (in the form of concepts) provided to the reasoning
agents. Logic based agents need pre-defined state evaluation functions to
evaluate interpretable concepts. Consequently, this severely limits the
applicability of the NeSy-RL systems across various domains, in contrast to
deep RL agents that require a minimal prior knowledge and achieve high
performance by learning from data Schrittwieser et al. (2019). This raises the
question: _How can we develop NeSy-RL agents that can autonomously discover
new concepts while learning how to solve tasks?_

To mitigate this issue, we propose EXplanatory Predicate Invention for
Learning (EXPIL, _cf._ Figure 1). EXPIL integrates _Predicate Invention (PI)_
, a set of techniques to automatically discover new predicates for logic-based
machine learning. By inventing new predicates from available data, PI
significantly reduces the amount of required priors Muggleton and Buntine
(1988); Kok and Domingos (2007). To perform PI in RL, EXPIL identifies new
predicates using general physical concepts and demonstrations of a trained
neural agent. These predicates can then be integrated first-order logic
policies, thus producing interpretable neuro-symbolic policies without
requiring hand-crafted knowledge.

Overall, we make the following contributions:

  * •

We propose EXPIL111https://github.com/ml-research/EXPIL, a NeSy-RL framework
incorporating predicate invention, that produces interpretable policies
(compared to deep ones), requiring little background knowledge (compared to
conventional NeSy-RL ones).

  * •

We empirically show that EXPIL outperforms both purely neural and state-of-
the-art NeSy agents in logically challenging RL environments.

  * •

We propose two predicate evaluation metrics – _Necessity_ and _Sufficiency_ to
quantify the probability that a particular observed fact leads to a choice of
action.

Hereafter, we introduce the necessary background on Logic, RL and PI for
understanding EXPIL.

##  2 Background

Before delving into the EXPIL pipeline, let us establish the formal background
of the framework.

###  2.1 First-Order Logic (FOL)

In FOL, a Language $\mathcal{L}$ is a tuple
$(\mathcal{P},\mathcal{D},\mathcal{F},\mathcal{V})$, where $\mathcal{P}$ is a
set of predicates, $\mathcal{D}$ a set of constants, $\mathcal{F}$ a set of
function symbols (functors), and $\mathcal{V}$ a set of variables. A term is
either a constant (_e.g._ $\texttt{obj1},\texttt{agent}$), a variable (_e.g._
O1), or a term which consists of a function symbol. An atom is a formula ${\tt
p(t_{1},\ldots,t_{n})}$, where ${\tt p}$ is a predicate symbol (_e.g._
closeby) and ${\tt t_{1},\ldots,t_{n}}$ are terms. A ground atom or simply a
fact is an atom with no variables (_e.g._ closeby(obj1,obj2)). A literal is an
atom ($A$) or its negation ($\lnot A$). A clause is a finite disjunction
($\lor$) of literals. A ground clause is a clause with no variables. A
definite clause is a clause with exactly one positive literal. If
$A,B_{1},\ldots,B_{n}$ are atoms, then $A\lor\lnot B_{1}\lor\ldots\lor\lnot
B_{n}$ is a definite clause. We write definite clauses in the form of
$A~{}\mbox{:-}~{}B_{1},\ldots,B_{n}$. Atom $A$ is called the head, and set of
negative atoms $\\{B_{1},\ldots,B_{n}\\}$ is called the body. We sometimes
refer to clauses as _rules_. _Differentiable Forward Reasoning_ is a data-
driven approach of reasoning in FOL Russell and Norvig (2010). In forward
reasoning, given evaluated facts and rules, new facts are deduced by applying
the facts to the rules. Differentiable forward reasoning Evans and
Grefenstette (2018); Shindo et al. (2023a) is a differentiable implementation
of forward reasoning using tensor operations.

###  2.2 Reinforcement Learning (RL)

In RL, the task is modelled as a Markov decision process,
$\mathcal{M}\\!=<\\!\\!\mathcal{S},\mathcal{A},P,R\\!\\!>$, where, at every
timestep $t$, an agent in a state $s_{t}\in\mathcal{S}$, takes action
$a_{t}\in\\!\mathcal{A}$, receives a reward $r_{t}=R(s_{t},a_{t})$ and a
transition to the next state $s_{t+1}$, according to environment dynamics
$P(s_{t+1}|s_{t},a_{t})$. Deep agents attempt to learn a parametric policy,
$\pi_{\theta}(a_{t}|s_{t})$, to maximize the return (_i.e._
$\sum_{t}\gamma^{t}r_{t}$, with $\gamma\in[0,1]$). However, The desired input-
to-output distribution (_i.e._ state to action) is not directly accessible, as
RL agents only observe returns. The value $V_{\pi_{\theta}}(s_{t})$ (resp.
Q-value $Q_{\pi_{\theta}}(s_{t},a_{t})$) function provides the expected return
of the state (resp. state/action pair) following the policy $\pi_{\theta}$.
Policy-based methods directly optimize $\pi_{\theta}$ using the noisy return
signal, which can lead to potentially unstable learning. Value-based methods
learn to approximate value functions $\hat{V}_{\phi}$ or $\hat{Q}_{\phi}$,
implicitly encoding the policy (_e.g._ by selecting actions with the highest
Q-value with high probability) Mnih et al. (2015).

###  2.3 FOL for RL

Following Delfosse et al. (2023b), FOL policies can be created to solve RL
challenges. To do so, the set of predicates $\mathcal{P}$ can be divided into
a set of action predicates and $\mathcal{P}_{A}$, and a set of state
predicates $\mathcal{P}_{S}$. These are used to form action rules. Let $X_{A}$
be an action atom and $X_{S}^{(1)},\ldots,X_{S}^{(n)}$ be state atoms. An
action rule is a rule, written as $X_{A}\ \texttt{:-}\ \
X_{S}^{(1)},\ldots,X_{S}^{(n)}$. For instance, the action atom could
correspond to the environment action jump, while the state ones could encode
the agent is close to the enemy. The policy is then encoded as a set of
weighted action rules. At inference time, each action atom is evaluated using
forward reasoning on the facts, which provides an environmental action
probability for each action.

###  2.4 Predicate Invention

_Predicate invention (PI)_ systems find new predicates to describe or analyze
various aspects of a subject or domain. Thereby expanding the system’s
language and reducing reliance on human experts Stahl (1993); Athakravi,
Broda, and Russo (2012). NeSy-$\boldsymbol{\pi}$ Sha et al. (2024) is a neuro-
symbolic system that integrates predicate invention with differentiable rule
learners Shindo et al. (2023a) to discover useful relations from complex
visual scenes. NeSy-$\pi$ invents new predicates to describe observations
better using only primitive concepts which are then utilized by the learner to
solve classification tasks on complex visual scenes.

Figure 2:  EXPIL Architecture. Top: EXPIL uses a state/action game buffer of
pretrained agents to extract logical states $\mathcal{S}$, invents necessity
predicates $\mathcal{P}_{\mathit{ness}}$ and sufficiency predicates
$\mathcal{P}_{\mathit{suff}}$, deduces policy clauses $\mathcal{C}$, and
finally learns an optimized policy $\pi_{\mathcal{C}}$ through interaction
with the game environment. Bottom: At inference time, the logic agent uses the
optimized policy and game states as input, evaluates valid policy clauses from
the environment, and selects the action corresponding to the rule with the
highest evaluation.

##  3 EXPIL

EXPIL produces logic agents capable of deducing weighted policy clauses
$\mathcal{C}_{w}$ from a replay buffer $\mathcal{B}$, using limited background
knowledge. Its architecture, depicted in Figure 2, consists of five major
components:
(1) Logical State Extraction. The object-centric game states-action pairs
$\mathcal{S}$ are extracted from the provided replay game buffer,
$\mathcal{B}$, from pretrained agents.
(2) Necessity Predicate Invention. Necessity predicates
$\mathcal{P}_{\mathit{ness}}$ are invented using $\mathcal{B}$ to capture
essential properties or relationships for certain actions in the game.
(3) Rule Reasoning. The invented predicates are utilized to infer policy
clauses $\mathcal{C}_{w}$ that provide better explanations for the behaviors
observed in the replay buffer. Simultaneously, the rule scores $\mu$ are
evaluated using the game buffer.
(4) Sufficiency Predicate Invention. Based on the reasoned policy clauses,
sufficiency predicates $\mathcal{P}_{\mathit{suff}}$ are invented with the aim
of enriching predicate expressiveness. These predicates capture additional
conditions or factors that contribute to the sufficiency of certain actions.
(5) Strategy Learning. Through gameplay, the weights $w$ of the policy clauses
$\mathcal{C}_{w}$ are learned to improve the performance of the agent.
Let us now describe each step in detail.

###  3.1 Logical State Extraction

To perform PI, we first generate a labeled dataset, corresponding to a game
buffer, of human experts or pretrained neural agents rollouts. As object-
detection is not our focus, we do not use object discovery techniques Delfosse
et al. (2023c); Luo et al. (2024) to train logic agents, we directly make use
of object-centric representations, similar to ones from Delfosse et al.
(2023a). Every state directly consists of a set of objects with their
attributes. For example, an enemy in a game state can be represented by its
position and a distinctive identifier.

Let $\mathcal{S}$ denote the game buffer, _i.e._ the set of pairs of a state
and an action, and $\mathcal{A}$ denote the action space of the game. For each
action $a\in\mathcal{A}$, we decompose $\mathcal{S}$ to positive and negative
sets:
$\mathcal{S}_{a}^{+}=\\{(s,a^{\prime})~{}|~{}(s,a^{\prime})\in\mathcal{S}\land
a^{\prime}=a\\}$ and
$\mathcal{S}_{a}^{-}=\\{(s,a^{\prime})~{}|~{}(s,a^{\prime})\in\mathcal{S}\land
a^{\prime}\neq a\\}$. Throughout the paper, we refer to $\mathcal{S}_{a}^{+}$
as a set of positive states of action $a$, and $\mathcal{S}_{a}^{-}$ as a set
of negative states of action $a$.

###  3.2 Necessity Predicate Invention

EXPIL discovers new predicates automatically by using pre-defined physical
concepts. A pre-defined physical concept refers to a pre-defined function that
maps pairs of objects to specific values or ranges. EXPIL uses two pre-defined
physical concepts: _distance_ and _direction_. The distance calculates the
space between two objects, while the direction determines the angle of one
object relative to another.

To discover useful task-specific concepts using the pre-defined physical
concepts, we consider parameterized predicates representing various degrees of
distance and direction. For this, we introduce reference range, which is
defined as a valid range of values of distance and direction. If the relation
or property of the objects locates lies within the reference range, the
predicate is evaluated as true, otherwise, it is evaluated as false. For
example, consider a reference range [0,1) associated with the concept
distance. In this case, a predicate Distance_[0,1) can be interpreted as a
function to determine whether the distance between two objects is between 0
and 1 (inclusive of 0 but exclusive of 1).

Using the reference range, EXPIL first generates candidates of predicate and
selects only promising ones by evaluating them with a heuristic. To cover
various degrees of distance and directions, EXPIL generates new predicates
efficiently by increasing intervals of reference range uniformly. For example,
suppose we want to specify the distance from $1$ meter to $100$. This can be
achieved by considering the truth value of one of the following predicates:

⬇

Predicate 0: Distance_[0,1)

Predicate 1: Distance_[1,2)

...

Predicate 99: Distance_[99,100)

_e.g._ Distance_[0,1)(agent,enemy) represents the fact that the agent and the
enemy are distant of less than $1$ meter _i.e._ they are very close to each
other.

Figure 3:  The Predicate Invention module of EXPIL. EXPIL utilizes an object-
centric state-action buffer as input for predicate invention and rule
reasoning. Candidate predicates are invented to serve and combined within
clauses of the policy. The reasoned policy clauses are evaluated, and
promising rules are selected as output to the logical agent.

In practice, most of the newly generated predicates are not critical for
solving a specific task. For example, the predicate Distance_[0,1), _i.e._ the
concept of being closeby, would be more important than the predicate
Distance_[99,100), _i.e._ the concept of being distant of one specific long
distance, since the former can contribute to effective action taking to
survive longer (_e.g._ avoiding enemies). We consider such important
predicates as _necessary_ predicates to solve the environment. In this steps,
EXPIL invents such predicates. We follow the NeSy-$\pi$ Sha et al. (2024)
approach to evaluate the necessity of each predicate. Let us now devise a
formal definition.

#### Necessity:

The necessity of a logical expression $e$ on action $a$, denoted as
$\mu_{e}(\mathcal{S}_{a}^{+})$, measures the cumulative confidence of the
logical expression across all states in $\mathcal{S}_{a}^{+}$. Higher
necessity values indicate that more states of $\mathcal{S}_{a}^{+}$ evaluate
to $true$ for $e$.

$\mu_{e}(\mathcal{S}_{a}^{+})=\frac{1}{|\mathcal{S}_{a}^{+}|}\sum_{s\in\mathcal{S}_{a}^{+}}r_{e}(s)$
(1)

where $\mathcal{S}_{a}^{+}$ represents the buffered game states resulting from
taking action $a$, $r_{e}(s)$ is a differentiable forward reasoning function
Shindo et al. (2023a) with respect to logical expression, which returns the
confidence of the evaluation result of the expression $p$ for state $s$. In
this paper, the logical expression includes predicates and policy clauses.

For example, in the environment depicted in Figure 2, let us consider an
action jump ($\uparrow$), and let $\mathcal{S}^{+}_{\uparrow}$ be a set of
positive states in the game buffer where a pretrained agent selected the
action to jump $\uparrow$. Well-trained agents would jump to avoid enemies
when they get close to the agent, and thus, the concept of closeby would often
be observed in the positive states $\mathcal{S}^{+}_{\uparrow}$. To this end,
predicates that are relevant to the concept of _closeby_ (_e.g._
Distance_[0,1)) would get high evaluation scores by Eq. 1.

###  3.3 Rule Reasoning

Using the invented necessary predicates, EXPIL searches a set of promising
action rules by performing beam search. Intuitively, EXPIL extensively
generates new candidates of action rules using the invented necessary
predicates and evaluates them with heuristics to select only promising ones.
EXPIL iterates this rule generation until it gets sufficiently complex action
rules to solve the environment.

The necessity predicates $\mathcal{P}_{\mathit{ness}}$ are invented to
evaluate the facts within the game states and are utilized as fundamental
components of the policy clauses $\mathcal{C}$. Let $\mathcal{L}$ represent a
language containing all the invented predicates $\mathcal{P}$. By combining
multiple predicates $P_{1}(X),P_{2}(X),...,P_{n}(X)$ as the antecedents and
the action $A(X)$ as the consequent, a game rule $C$ can be constructed as
follows:

⬇

C: A(X):-P1(X),P2(X),...,Pn(X).

The rules are searched action by action. They are interpreted as if the
antecedents $P_{1}(X)$, $P_{2}(X)$, …, $P_{n}(X)$ are true, then take the
action $a$. For each action $a$, rules are generated incrementally and stored
in a rule set $\mathcal{C}_{a}$. These rules are searched in a top-down
manner. Initially, the rule set $\mathcal{C}_{a}$ contains only one initial
rule with no atoms in its body, which evaluates to $true$ for any state.
Subsequently, in each step, each rule in $\mathcal{C}_{a}$ is extended with
each of the atoms in the language $\mathcal{L}$.

For example, the initial rule set for the action Left is represented as
$\mathcal{C}_{0}=\\{C_{0}\\}$, with

⬇

C_0 Left(X):-.

which is interpreted as take action left if true. If $\mathcal{L}$ contains
atoms Dir_[0,1)(enemy, player) and Dir_[1,2)(enemy, player), the first step of
extension generates a new rule set $\mathcal{C}_{1}=\\{C_{1},C_{2}\\}$

⬇

C_1 Left(X):-Dir_[0,1)(enemy,player).

C_2 Left(X):-Dir_[1,2)(enemy,player).

Similarly, the second step of extension further extends each rule from
$\mathcal{C}_{1}$ using each of the atoms in the language $\mathcal{L}$. This
process is repeated for $N$ steps to collect rules with bodies of varying
lengths.

Each reasoned rules $C\in\mathcal{C}_{i},1\leq i\leq N$, is then evaluated for
its necessity $\mu_{C}(\mathcal{S}_{a}^{+})$ and sufficiency
$\mu_{C}(\mathcal{S}_{a}^{-})$ (_cf._ Section 3.4). These evaluations
determine how necessary and sufficient the rules are for the given actions.
The rules are then ranked based on their necessity, and the Top-$k$ rules are
selected for strategy learning as described in Section 3.5.

###  3.4 Sufficiency Predicate Invention

To enhance the performance of logic-based agents, EXPIL combines invented
necessary predicates to compose more expressive predicates. This can be
achieved by computing the disjunction of rules produced by the rule reasoning
step, as described in Sec. 3.3. For each action $a\in\mathcal{A}$, EXPIL aims
to invent predicates that are less correlated to other actions $a^{\prime}$
$(a^{\prime}\in\mathcal{A},a^{\prime}\neq a)$. We call the resulted predicates
_sufficiency predicates_ , as such predicates are motivated by searching for a
sufficient condition of the action.

Given a set of rules $\mathcal{C}_{a}$ for an action $a$. Any subset
$\mathcal{C}_{p}\subset\mathcal{C}_{a}$, such that
$2\leq|\mathcal{C}_{p}|\leq|\mathcal{C}_{a}|$ defines a new predicate $p$.
This subset, $\mathcal{C}_{p}$, is referred to as the explanation clause set
of the predicate $p$. The meaning of $p$ is interpreted as the disjunction of
the clauses within $\mathcal{C}_{p}$.

For example, consider the rules set $\mathcal{C}=\\{C_{1},C_{2},C_{3}\\}$:

⬇

C1: Jump(X):-Dist_[0,1)(enemy,player,X).

C2: Jump(X):-Dist_[1,2)(enemy,player,X).

C3: Jump(X):-Dist_[2,3)(enemy,player,X).

A sufficiency predicate SuffPred can be invented by taking the disjunction of
these three clauses, i.e. $\texttt{SuffPred}=C_{1}\lor C_{2}\lor C_{3}$.

⬇

SuffPred(X):-Dist_[0,1)(enemy,player,X).

SuffPred(X):-Dist_[1,2)(enemy,player,X).

SuffPred(X):-Dist_[2,3)(enemy,player,X).

The invented predicate, SuffPred, interprets the concepts that if the distance
between the enemy and the player is in the range of $0$ to $3$. Each clause in
$\mathcal{C}_{p}$ represents a variation of the invented predicate. By taking
the disjunction of multiple clauses, the invented predicate can expand its
range to cover more states (_e.g._ measuring distances from $0$ to $3$ by
taking three individual predicates) and thereby becomes much more expressive.

Theoretically, there are $2^{|\mathcal{C}_{a}|-1-|\mathcal{C}_{a}|}$
predicates that can be invented from a clause set $\mathcal{C}_{a}$, ensuring
that any sufficient predicate includes at least two clauses. Due to this
exponential growth rate, it is crucial to evaluate the invented predicates
appropriately to select the most useful ones.

EXPIL evaluates these predicates considering their sufficiency. The
sufficiency of a logical expression, as proposed by Sha et al. (2024), is
defined as follows.

#### Sufficiency:

The sufficiency of a logical expression $e$, denoted as
$\mu_{e}(\mathcal{S}_{a}^{-})$, measure the inverse of the cumulative
confidence of $e$ in all the states in $\mathcal{S}_{a}^{-}$. The higher the
sufficiency of $e$, the fewer states in $\mathcal{S}_{a}^{-}$ for which it
holds true.

$\mu_{e}(\mathcal{S}_{a}^{-})=\frac{1}{|\mathcal{S}_{a}^{-}|}\sum_{s\in\mathcal{S}_{a}^{-}}(1-r_{e}(s))$
(2)

For a clause set $\mathcal{C}_{a}$, EXPIL clusters the set into multiple
clusters based on the relations and the objects involved. Only the rules with
same objects and same relations but different reference ranges are combined.
For example, if $C_{4}$ and $C_{5}$ are two rules in $\mathcal{C}_{a}$ as
follows:

⬇

C4(X):-Dist_[0,1)(enemy,player,X).

C5(X):-Dist_[1,2)(key,player,X).

they are not combined as the same cluster since they have different objects in
the predicate.

The necessity scores of disjunctive clusters are typically high because they
combine the reference ranges. For example, a predicate can be invented by
clustering all the clauses that evaluate the distance between the player and
the enemy, which can be written as Dist_[0,100)(enemy, player). If $100$ is
the maximum distance in the game and the player and the enemy exist in all
states, this predicate can always be true, thus reaching a necessity score of
$1$ according to Equation 1. However, its sufficiency score would be $0$
according to Equation 2 because it is also true in all negative states.

By inventing sufficiency predicates from disjunction, EXPIL first clusters the
clauses with the same objects and relations, but different reference ranges,
resulting in high necessity for the clusters. Then, to increase their
sufficiency, clauses are gradually removed from the cluster until the
sufficiency of the cluster reaches a given threshold. The clause removed in
each step is chosen as the least sufficient one (i.e. the clause with removing
it can improve the efficiency most) to ensure the remaining clauses provide
the best possible increment in sufficiency. As clauses are removed from the
cluster, its necessity will also decrease; however, as long as it remains
above zero, it is valuable for the rule reasoning. By refining the predicates
through disjunction and selective reduction, the system effectively balances
the necessity and sufficiency to enhance the expressiveness and utility of the
predicates in rule reasoning.

For example, Figure 4 illustrates a step in the process of inventing a
sufficiency predicate. The evaluation result of $3$ different predicates are
shown in the left column. Each individual predicate has a low necessity but
high sufficiency. Their disjunction achieves a high necessity but low
sufficiency (see the value at the bottom). When the third predicate is removed
(second column of Figure 4), the disjunction of the remaining two predicates
attains a higher sufficiency.

Figure 4: An example step for sufficiency predicate invention. In each
rectangle box: the $8$ circles above the dashed line indicate the states
taking the action Jump, while the remaining circles indicate the states taking
other actions. Boxes $1,2,3$ shows the evaluation results of three different
predicates, with blue circles of box $i\in[1,2,3]$ representing the positive
states that satisfy the predicate $i$ and purple circles of box $i\in[1,2,3]$
representing the negative states that satisfy the predicate $i$. The
$\mu_{p}(\mathcal{S}_{a}^{+})$ and $\mu_{p}(\mathcal{S}_{a}^{-})$ at the
bottom indicate the scores of the invented sufficiency predicate.

###  3.5 Strategy Learning

After the extraction of a set of good candidate rules to form the policy, a
set of randomly initialized weights $W$ is assigned to each policy clause in
$\mathcal{C}$. These weights are optimized based on an actor-critic method
Konda and Tsitsiklis (1999) that back propagates the gradients from the critic
to the differentiable logic actors, allowing an update of each weight.
Following Delfosse et al. (2023b), we update both the rule weights and the
critic-network weights in each iteration. To obtain a probabilistic
distribution, softmax over the evaluation of all actions is taken.

Algorithm 1 Predicate Invention in EXPIL

Input:
$\mathcal{L}_{0},\mathcal{S},\mathcal{B},\mathcal{A}=[\mathtt{left},\mathtt{right},...]$
Parameter: $N_{\mathit{max\\_c\\_length}},$
Output: $\mathcal{L}$

1:for $a\leftarrow\mathcal{A}$ do

2:
$\mathcal{S}^{+}_{a},\mathcal{S}^{-}_{a}=\mathtt{split\\_states}(\mathcal{S},a)$

3: // Nessicity Predicate Invention

4:
$\mathcal{P}_{\mathit{ness}}\leftarrow\mathtt{ness\\_inv}(\mathcal{L}_{0},\mathcal{B})$

5:
$\mu_{\mathit{ness}}\leftarrow\mathtt{eval}(\mathcal{P}_{\mathit{ness}},\mathcal{S}_{a}^{+})$

6:
$\mathcal{P}_{\mathit{ness}}^{*}\leftarrow\mathtt{top\\_k}(\mathcal{P}_{\mathit{ness}},\mu_{\mathit{ness}})$

7:
$\mathcal{L}\leftarrow\mathtt{update}(\mathcal{L}_{0},\mathcal{P}_{\mathit{ness}}^{*})$

8: for
$N_{\mathit{step\\_max}}\leftarrow[1,2,...,N_{\mathit{max\\_c\\_length}}]$ do

9: // Clause Searching

10: $\mathcal{C}=\mathtt{init\\_clause}(a)$

11: $\mathcal{C}\\_\mathit{step}=$ []

12: for $N_{\mathit{step}}\leftarrow[1,2,...,N_{\mathit{step\\_max}}]$ do

13: $\mathcal{C}\leftarrow\mathtt{extend}(\mathcal{C},\mathcal{L})$

14:
$\mu_{\mathit{ness}},\mu_{\mathit{suff}}\leftarrow\mathtt{eval\\_c}(\mathcal{C},\mathcal{S}^{+}_{a},\mathcal{S}^{-}_{a})$

15:
$\mathcal{C}\\_\mathit{step}\leftarrow\mathtt{top\\_k}(\mathcal{C},\mu_{\mathit{ness}})$

16: end for

17: // Sufficiency Predicate Invention

18:
$\mathcal{P}_{\mathit{suff}}\leftarrow\mathtt{suff\\_inv}(\mathcal{C}\\_\mathit{step},t_{s})$

19:
$\mathcal{P}_{\mathit{suff}}^{*}\leftarrow\mathtt{top\\_k}(\mathcal{P}_{\mathit{suff}},\mu_{\mathit{ness}})$

20:
$\mathcal{L}\leftarrow\mathtt{update}(\mathcal{L},\mathcal{P}_{\mathit{suff}}^{*})$

21: end for

22:end for

23:return $\mathcal{L}$

###  3.6 Algorithm for Predicate Invention in EXPIL

Algorithm 1 shows the pseudocode of predicate invention process in EXPIL. The
algorithm takes as input an initial language $\mathcal{L}_{0}$, game state-
action buffer $\mathcal{S}$, predefined physical concepts $\mathcal{B}$, and
the game action space $\mathcal{A}=[\texttt{left},\texttt{right},...]$, which
depends on the specific game environment. It outputs the language
$\mathcal{L}$ with invented predicates. (Line 1-2) For each action
$a\in\mathcal{A}$, predicate invention and rule reasoning are performed
separately. The replay buffer $\mathcal{S}$ is spit into two groups:
$\mathcal{S}^{+}_{a}$ contains states with action $a$ and
$\mathcal{S}^{-}_{a}$ contains states with other actions. (Line 3-7) Necessity
predicates are invented using predefined physical concepts $\mathcal{B}$. The
predicate necessity scores $\mu_{\mathit{ness}}$ are calculated over the
positive states $\mathcal{S}^{+}_{a}$. The Top-$k$ predicates
$\mathcal{P}^{*}_{\mathit{ness}}$ are selected, and the language $\mathcal{L}$
is updated accordingly. (Line 8-16) policy clauses are searched starting from
the most general clause. For example, to search rules with action left, the
init_clause() returns the initial clause set
$\mathcal{C}=\\{\texttt{left(X):-.}\\}$. The clauses are extended with
predicates from the language $\mathcal{L}$ in each step, updating the clause
set $\mathcal{C}$. Clauses are extended for a maximum of
$N_{\mathit{step\\_max}}$ iterations. During the first iteration, the initial
clause in $\mathcal{C}$ is extended with new atoms and evaluated against the
game buffer $\mathcal{S}$. The Top-$k$ scoring clauses are retained, while the
others are pruned. (Line 17-20) Sufficiency predicates
$\mathcal{P}_{\mathit{suff}}$ are invented based on the extended clauses in
$\mathcal{C}_{\mathit{step}}$ and a given threshold $t_{s}$ to ensure the
sufficiency is above $t_{s}$. The number of sufficiency predicates is limited
by retaining only the top $k$. These invented predicates are then added to the
language $\mathcal{L}$.

##  4 Experiments

To evaluate the performance of predicate invention in the RL setting, we
employ _three_ established logically challenging environments, which have been
used to evaluate state-of-the-art neuro-symbolic RL agents Delfosse et al.
(2023b). Exemplary states from each environment are shown in Figure 5, and let
us describe each environment in detail. Getout is a game that involves the
agent moving on a $1.5$D map with taking the actions left, right and jump. The
agent can move freely along $x$-axis but has limited movement along the
$y$-axis, which is controlled by the action jump. The objective is to collect
a key on the ground and then go to the door while avoiding an enemy that moves
around the map. In each new epoch, the positions of all objects are randomly
placed. In Loot, the agent moves on a $2$D map, taking actions left, right, up
and down. The agent can move freely along both the $x$ and $y$ axes. There are
one or two pairs of locks and keys randomly generated in each new game. Locks
and keys have IDs, and a key can only open the lock with the corresponding ID.
The objective is to collect keys and open corresponding locks until no locks
remain. In Threefish, the agent moves on a $2$D map, taking actions left,
right, up, down and noop. The agent can move freely along both the $x$ and $y$
axes. The objective is to eat smaller fish while avoiding the bigger fish than
the player.

For baselines, we used the standard neural PPO Schulman et al. (2017) and
NUDGE Delfosse et al. (2023b), a SOTA NeSy-RL agent. For a fair comparison, we
did not provide the task-specific predicates to the models, and thus they need
to acquire them by learning in the environments.

(a) Getout

(b) Loot

(c) Threefish

Figure 5: Environments used to evaluate EXPIL and baselines.

Preliminaries. Two physics concepts are given as background knowledge for
predicate invention. distance measures the distance between two given objects.
direction measures the direction of one object with respect to another object.
Additionally, the absence of an object is evaluated by the predicate
NotExist(O1), which is particularly required for the game Getout and Loot. The
predicate is used to determine whether a specific object is present in a game
state. Besides, no further game-specific knowledge is given.

Symbolic States Extraction. To facilitate predicate invention and rule
reasoning, a teacher agent plays the game and collects a game buffer
containing symbolic game states and corresponding actions. For each game, we
randomly select $800$ state-action pairs for each action. Each state records
the existence of objects and their positions on the $x$ and $y$ axes. A state
is saved in a matrix with shape of $(n+2)\times n$, where $n$ is the number of
objects in the game. For the $i$-th object in the state: its existence is
saved at position $(i,i)$, its $x$ position is saved at $(i,n+1)$, its $y$
position is saved at $(i,n+2)$. The action for each state is recorded as its
index in the action space. This structured data serves as the learning
material for the EXPIL system to invent predicates and reason about the policy
clauses.

Figure 6: Necessity Predicate Scores. The evaluation results of the invented
necessity predicates for the game Getout (Only the Top-50 predicates ranked by
necessity score are displayed). Red: scores for the action Left; Yellow:
scores for the action Jump; Green: scores for the action Right. For each
action, the necessity scores are ranked in descending order. The corresponding
sufficiency scores are aligned with the rank of the necessity scores for the
same action.

Necessity Predicate Invention. We firstly set out to verify the efficiency of
using necessity and sufficiency as metrics for predicate evaluation. Figure 6
displays the scores of the invented necessity predicates for the game Getout.
The predicates are invented for each action individually. By using an interval
unit with $1\%$ of the maximum distance and $4\%$ of the maximum direction.
Over $800$ necessity predicates are invented to evaluate different distances
and directions between the agent and other three objects (door, enemy, key).
The figure only shows the top 50 predicates ranked by necessity scores.

Predicates with high necessity scores (above 0.1) are selected as promising
candidates based on their high necessity and can further be used for the game
rule reasoning. Although the reference range is chosen to be very small,
dividing the distance into $100$ sections and the direction into up to $90$
sections, most of the necessity predicates achieve high sufficiency (close to
1) and low necessity (close to 0) eventually. This indicates that most of the
predicates are rarely evaluated as true in both positive and negative states,
thus can be pruned to reduce computation complexity.

Table 1 shows the percentage of necessity predicates that exceed various
thresholds in the game Getout. By diving the distance and direction into $100$
and $90$ sections respectively, only $22.3\%$ of the predicates have necessity
scores greater than $0.01$, implying that around $78\%$ of the predicates are
rarely present in the positive training states.

| $s>0.001$ | $s>0.01$ | $s>0.1$
---|---|---|---
left | $100\%$ | $22.3\%$ | $0.9\%$
right | $100\%$ | $25.1\%$ | $1.0\%$
jump | $100\%$ | $15.0\%$ | $1.7\%$
Table 1: Percentage of the necessity predicates that have necessity score $s$
greater than a given threshold from game Getout. The number of reference
ranges for distance and direction are $100$ and $90$, respectively. $\uparrow$
necessity threshold = $\downarrow$ remaining predicates.

Sufficiency Predicate Invention. The sufficiency predicates are invented by
taking the disjunction of the rules and removing the clauses with the least
contribution to the sufficiency score one by one. This process aims to improve
the sufficiency score of the resulting predicate while maintaining a
reasonable necessity score. Figure 7 illustrates the score changes at each
step as clauses are removed. Initially, the clusters have high necessity but
low sufficiency, because the reference ranges are combined. By excluding the
clause that contributes the least to sufficiency, the sufficiency score
increases step by step.

Some clusters remain their necessity scores even as the steps progress (such
as SuffPred0), whereas some clusters attain their necessity scores close to 0
(SuffPred3). Clusters that fail to maintain a proper necessity score are
pruned.

Figure 7: Sufficient Predicate Scores. The line charts show the scores of the clusters at each step in sufficiency predicate invention for the game Getout. Each chart displays the sufficiency score (blue dot line), necessity score (red asterisks * line) and their sum (green crosses x line) at each step of cluster reduction. From step to step, the necessity scores decrease while sufficiency scores increase. The process stops when the necessity (red line) is above the threshold (0.9 in these figures.) | High Necessity | Low Necessity
---|---|---
High Sufficiency | ✓ | ✗
Low Sufficiency | ✓ |  ✓/✗
Table 2: Pruning necessity predicates based on their scores.

Predicate Selection Strategy. Based on the evaluation results, the predicates
kept for further use are shown in Table 2. Predicates with high necessity and
high sufficiency are common in positive states $\mathcal{S}_{a}^{+}$ of action
$a$ and relatively rare in negative states $\mathcal{S}_{a}^{-}$, indicating
their significant role in action decision-making. Predicate with high
necessity, but low sufficiency appear frequently in both positive and negative
states and are retained for potential usage in sufficiency invention. High
sufficiency and low necessity predicates are rare in both state types, while
low sufficiency and low necessity predicates, which are often true in negative
states but not positive states, can be considered for future work involving
negated reasoning.

#### Example for invented predicates.

The following list shows an example of an invented sufficiency predicate for
the game Getout,

Listing 1: An invented sufficiency predicate for the game Getout

⬇

InvP1(X):-Dist_[0.04,0.05)(enemy,player,X).

InvP1(X):-Dist_[0.05,0.06)(enemy,player,X).

InvP1(X):-Dist_[0.06,0.07)(enemy,player,X).

InvP1(X):-Dist_[0.07,0.08)(enemy,player,X).

which can be interpreted as if the distance between the enemy and the player
is in range of 0.04 to 0.08. The predicate InvP1 evaluates a safe jumping
distance with the enemy. The corresponding rules have been searched using this
predicate for take the action Jump:

Listing 2: Rules using predicate InvP1

⬇

Jump(X):-InvP1(X),NotExist(key,X),

Dir_[0,4)(enemy,player,X).

Jump(X):-InvP1(X),Dir_[4,8)(enemy,player,X).

Jump(X):-InvP1(X),NotExist(key,X),

Dir_[184,188)(door,player,X).

Jump(X):-InvP1(X),Dir_[184,188)(door,player,

X),Dir_[184,188)(enemy,player,X).

Figure 8:  The average reward during the training. The rewards are tracked and smoothed over the last $40,000$ steps to provide a clear trend of performance improvement over time. The red line represents the reward of EXPIL, the green line represents the reward of NUDGE. The gray dash line represents the average reward of a random model, and the green dash line represents the average reward of a human player.  Game | $|\mathcal{A}|$ | M. | #Obj. | #N.P. | #S.P. | #R. | #Dir. | #Dist. | Rand. | Hu. | PPO | NUDGE | EXPIL
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Getout | 3 | 1.3% | 4 | 10 | 1 | 27 | 90 | 100 | -22.5 | 13.5 | 3.8 | -26.1 | 13.7
Loot | 4 | 7.3% | 5 | 32 | 6 | 101 | 8 | / | 0.6 | 5.7 | 4.5 | -0.2 | 4.3
Threefish | 5 | 14.8% | 3 | 20 | 5 | 59 | 10 | / | -0.7 | 2.5 | -0.4 | -0.5 | 0.4
Table 3: Model Performance. $|\mathcal{A}|$ denotes the number of actions of
each game. $M.$ denotes the average relative magnitude of objects in the game
map. $\\#O$ denotes the number of objects of each game. $\\#$N.P. denotes the
number of necessity predicates used in the policy clauses. $\\#$S.P. denotes
the number of sufficiency predicates used in the policy clauses. $\\#R.$
denotes the number of reasoned rules. $\\#$Dir. denotes the number of
reference ranges for direction. $\\#$Dist. denotes the number of reference
ranges for distance. Rand. shows the average score of a model taking random
actions. Hu. shows the average score of human players. Higher scores indicate
better performance.

Figure 8 shows the average game rewards during the weight learning on three
logic games. EXPIL achieves similar score as human player on Getout, a
distinguishable higher score compared to NUDGE player on Loot and Threefish.
Table 3 shows the performance of EXPIL in detail. Our results shows that the
EXPIL can invent efficient predicates using predefined physical concepts as
background knowledge and further reason rules that achieve high rewards in
various logic games. Getout utilizes a largser number of reference range in
both direction and distance since the magnitude of objects in this game are
relatively small whereas the objects in other games have larger scale (1.3% in
Getout compare to 14.8% in Threefish). It also invents less predicates and
rules since the action space is smaller. Loot has reasoned the most rules over
three games since it has more objects and 2D map. Threefish has the largest
action space, but with a relatively simpler objective and largest average
object magnitude, it remains fewer predicates and rules. We compared our model
against a random agent, human player, and a no predicate invention NeSy-RL
model. The average reward scores of each game are shown in the right half of
Table 3.

#### Discussions and Limitations

Although the reasoned rules are fully explainable, rule selection in states
with multiple valid rules is based on neurally learned weights. For example,
if both jump because of enemy and right because of key are valid, the agent
chooses based on the weights of these rules. A more explainable agent should
logically explain why it selects one action over another. Such strategy
reasoning requires more background knowledge and causal reasoning. This is a
potential future direction. Besides, our focus has been on the concepts of
direction and distance. Exploring other physical concepts like temperature,
time and weight for parameter-based predicate generation is also an
interesting future work.

##  5 Related Work

We revisit relevant studies of EXPIL. Predicate Invention Inductive Logic
Programming (ILP) Muggleton (1991, 1995); Nienhuys-Cheng et al. (1997);
Cropper et al. (2022) has emerged at the intersection of machine learning and
logic programming. ILP learns generalized logic rules given positive and
negative examples using background knowledge and language biases. Predicate
invention (PI) has been a long-standing problem for ILP and many methods have
been developed Stahl (1993); Athakravi, Broda, and Russo (2012); Cropper,
Morel, and Muggleton (2019); Hocquette and Muggleton (2020); Kramer (2007);
Cropper, Morel, and Muggleton (2020); Cropper and Morel (2021), and extended
to the statistical ILP systems Kok and Domingos (2005, 2007). Recently,
differentiable ILP frameworks have been developed to integrate DNNs with logic
reasoning Evans and Grefenstette (2018); Shindo, Nishino, and Yamamoto (2021),
and applied to complex visual scenes Shindo et al. (2023a, b). NeSy-$\pi$ Sha
et al. (2024) integrates PI with the differentiable ILP systems. EXPIL is the
first PI system on neuro-symbolic RL agents. Neuro-Symbolic RL. Relational RL
Dzeroski, Raedt, and Driessens (2001); Kersting, van Otterlo, and Raedt
(2004); Kersting and Driessens (2008); Lang, Toussaint, and Kersting (2012)
has been developed to tackle RL tasks in relational domains. Relational RL
frameworks incorporate logical representations and use probabilistic
reasoning. In contrast, EXPIL uses differentiable logic programming. Symbolic
programs within RL have been investigated, _e.g._ program guided agent Sun,
Wu, and Lim (2020), program synthesis Zhu et al. (2019), PIRL Verma et al.
(2018), SDRL Lyu et al. (2019), deep symbolic policy Landajuela et al. (2021),
and DiffSES Zheng et al. (2021). These approaches use domain-specific
languages or propositional logic and address either the interpretability.
NUDGE Delfosse et al. (2023b) effectively performs a neural-guided search for
differentiable logic-based policies to solve complex relational environments,
achieving both interpretability and explainability. EXPIL extends NUDGE,
integrating a predicate invention component.

##  6 Conclusion

In this paper, we have proposed EXPIL, a neuro-symbolic framework capable of
discovering new concepts while learning to solve RL tasks. We have introduced
two metrics – necessity and sufficiency – for EXPIL to invent predicates
efficiently from replay buffers recorded by pretrained agents. By using the
invented predicates, EXPIL achieves high-quality logic-based policies with
less background knowledge than conventional approaches, making it applicable
to various domains. In our experiments, across three challenging environments
where agents need to reason about objects and their relations, EXPIL
outperforms neural and state-of-the-art neuro-symbolic baselines with zero
background knowledge. We believe that EXPIL would be a basis for intelligent
agents that can reason logically and learn with fewer priors, overcoming the
bottlenecks of the current neural and neuro-symbolic approaches.

## References

  * Athakravi, Broda, and Russo (2012) Athakravi, D.; Broda, K.; and Russo, A.  2012\.  Predicate Invention in Inductive Logic Programming.  In 2012 Imperial College Computing Student Workshop.  Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * Cropper and Morel (2021) Cropper, A., and Morel, R.  2021\.  Predicate invention by learning from failures.  arXiv Preprint:2104.14426.
  * Cropper et al. (2022) Cropper, A.; Dumancic, S.; Evans, R.; and Muggleton, S. H.  2022\.  Inductive logic programming at 30.  Mach. Learn.
  * Cropper, Morel, and Muggleton (2019) Cropper, A.; Morel, R.; and Muggleton, S.  2019\.  Learning higher-order logic programs.  Mach. Learn.
  * Cropper, Morel, and Muggleton (2020) Cropper, A.; Morel, R.; and Muggleton, S. H.  2020\.  Learning higher-order programs through predicate invention.  Proceedings of the AAAI Conference on Artificial Intelligence (AAAI).
  * Delfosse et al. (2023a) Delfosse, Q.; Blüml, J.; Gregori, B.; Sztwiertnia, S.; and Kersting, K.  2023a.  Ocatari: Object-centric atari 2600 reinforcement learning environments.  arXiv Preprint: 2306.08649.
  * Delfosse et al. (2023b) Delfosse, Q.; Shindo, H.; Dhami, D. S.; and Kersting, K.  2023b.  Interpretable and explainable logical policies via neurally guided symbolic abstraction.  In NeurIPS.
  * Delfosse et al. (2023c) Delfosse, Q.; Stammer, W.; Rothenbächer, T.; Vittal, D.; and Kersting, K.  2023c.  Boosting object representation learning via motion and object continuity.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases.
  * Delfosse et al. (2024a) Delfosse, Q.; Blüml, J.; Gregori, B.; and Kersting, K.  2024a.  Hackatari: Atari learning environments for robust and continual reinforcement learning.  In Workshop on Interpretable Policies in Reinforcement Learning@ RLC-2024.
  * Delfosse et al. (2024b) Delfosse, Q.; Sztwiertnia, S.; Stammer, W.; Rothermel, M.; and Kersting, K.  2024b.  Interpretable concept bottlenecks to align reinforcement learning agents.  arXiv.
  * di Langosco et al. (2022) di Langosco, L. L.; Koch, J.; Sharkey, L. D.; Pfau, J.; and Krueger, D.  2022\.  Goal misgeneralization in deep reinforcement learning.  In International Conference on Machine Learning ICML.
  * Dzeroski, Raedt, and Driessens (2001) Dzeroski, S.; Raedt, L. D.; and Driessens, K.  2001\.  Relational reinforcement learning.  Mach. Learn.
  * Evans and Grefenstette (2018) Evans, R., and Grefenstette, E.  2018\.  Learning explanatory rules from noisy data.  Journal of Artificial Intelligence Research (JAIR).
  * Hocquette and Muggleton (2020) Hocquette, C., and Muggleton, S. H.  2020\.  Complete bottom-up predicate invention in meta-interpretive learning.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, (IJCAI).  International Joint Conferences on Artificial Intelligence Organization.
  * Jiang and Luo (2019) Jiang, Z., and Luo, S.  2019\.  Neural logic reinforcement learning.  In Chaudhuri, K., and Salakhutdinov, R., eds., International Conference on Machine Learning.
  * Kersting and Driessens (2008) Kersting, K., and Driessens, K.  2008\.  Non-parametric policy gradients: a unified treatment of propositional and relational domains.  In International Conference on Machine Learning.
  * Kersting, van Otterlo, and Raedt (2004) Kersting, K.; van Otterlo, M.; and Raedt, L. D.  2004\.  Bellman goes relational.  In Brodley, C. E., ed., International Conference on Machine Learning.
  * Kohler et al. (2024) Kohler, H.; Delfosse, Q.; Akrour, R.; Kersting, K.; and Preux, P.  2024\.  Interpretable and editable programmatic tree policies for reinforcement learning.  In Workshop on Interpretable Policies in Reinforcement Learning@ RLC-2024.
  * Kok and Domingos (2005) Kok, S., and Domingos, P.  2005\.  Learning the structure of markov logic networks.  In International Conference on Machine Learning.
  * Kok and Domingos (2007) Kok, S., and Domingos, P. M.  2007\.  Statistical predicate invention.  In International Conference on Machine Learning (ICML).
  * Konda and Tsitsiklis (1999) Konda, V. R., and Tsitsiklis, J. N.  1999\.  Actor-critic algorithms.  In Solla, S. A.; Leen, T. K.; and Müller, K., eds., Advances in Neural Information Processing Systems 12.
  * Kramer (2007) Kramer, S.  2007\.  Predicate invention : A comprehensive view 1.
  * Landajuela et al. (2021) Landajuela, M.; Petersen, B. K.; Kim, S.; Santiago, C. P.; Glatt, R.; Mundhenk, N.; Pettit, J. F.; and Faissol, D.  2021\.  Discovering symbolic policies with deep reinforcement learning.  In International Conference on Machine Learning.
  * Lang, Toussaint, and Kersting (2012) Lang, T.; Toussaint, M.; and Kersting, K.  2012\.  Exploration in relational domains for model-based reinforcement learning.  J. Mach. Learn. Res.
  * Luo et al. (2024) Luo, L.; Zhang, G.; Xu, H.; Yang, Y.; Fang, C.; and Li, Q.  2024\.  Insight: End-to-end neuro-symbolic visual reinforcement learning with language explanations.  arXiv.
  * Lyu et al. (2019) Lyu, D.; Yang, F.; Liu, B.; and Gustafson, S.  2019\.  SDRL: interpretable and data-efficient deep reinforcement learning leveraging symbolic planning.  In The Thirty-Third AAAI Conference on Artificial Intelligence.
  * Mnih et al. (2015) Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A. A.; Veness, J.; Bellemare, M. G.; Graves, A.; Riedmiller, M. A.; Fidjeland, A.; Ostrovski, G.; Petersen, S.; Beattie, C.; Sadik, A.; Antonoglou, I.; King, H.; Kumaran, D.; Wierstra, D.; Legg, S.; and Hassabis, D.  2015\.  Human-level control through deep reinforcement learning.  Nature.
  * Muggleton and Buntine (1988) Muggleton, S., and Buntine, W. L.  1988\.  Machine invention of first order predicates by inverting resolution.  In Proceedings of the Fifth International Conference on Machine Learning.  San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.
  * Muggleton (1991) Muggleton, S. H.  1991\.  Inductive logic programming.  New Gener. Comput.
  * Muggleton (1995) Muggleton, S.  1995\.  Inverse Entailment and Progol.  New Generation Computing, Special issue on Inductive Logic Programming.
  * Nienhuys-Cheng et al. (1997) Nienhuys-Cheng, S.-H.; Wolf, R. d.; Siekmann, J.; and Carbonell, J. G.  1997\.  Foundations of Inductive Logic Programming.
  * Pinto et al. (2017) Pinto, L.; Davidson, J.; Sukthankar, R.; and Gupta, A.  2017\.  Robust adversarial reinforcement learning.  In Precup, D., and Teh, Y. W., eds., International Conference on Machine Learning.
  * Rudin (2019) Rudin, C.  2019\.  Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead.  Nat. Mach. Intell.
  * Russell and Norvig (2010) Russell, S., and Norvig, P.  2010\.  Artificial Intelligence: A Modern Approach.  Prentice Hall, 3 edition.
  * Schrittwieser et al. (2019) Schrittwieser, J.; Antonoglou, I.; Hubert, T.; Simonyan, K.; Sifre, L.; Schmitt, S.; Guez, A.; Lockhart, E.; Hassabis, D.; Graepel, T.; Lillicrap, T. P.; and Silver, D.  2019\.  Mastering atari, go, chess and shogi by planning with a learned model.  Nature.
  * Schulman et al. (2017) Schulman, J.; Wolski, F.; Dhariwal, P.; Radford, A.; and Klimov, O.  2017\.  Proximal policy optimization algorithms.  CoRR.
  * Sha et al. (2024) Sha, J.; SHindo, H.; Kersting, K.; and Dhami, D. S.  2024\.  Neuro-symbolic predicate invention: Learning relational concepts from visual scenes.  Neurosymbolic Artificial Intelligence.
  * Shindo et al. (2023a) Shindo, H.; Pfanschilling, V.; Dhami, D. S.; and Kersting, K.  2023a.  $\alpha$ilp: thinking visual scenes as differentiable logic programs.  Mach. Learn.
  * Shindo et al. (2023b) Shindo, H.; Pfanschilling, V.; Dhami, D. S.; and Kersting, K.  2023b.  Learning differentiable logic programs for abstract visual reasoning.  arXiv Preprint: 2307.00928.
  * Shindo, Nishino, and Yamamoto (2021) Shindo, H.; Nishino, M.; and Yamamoto, A.  2021\.  Differentiable inductive logic programming for structured examples.  In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI).
  * Silver et al. (2016) Silver, D.; Huang, A.; Maddison, C. J.; Guez, A.; Sifre, L.; van den Driessche, G.; Schrittwieser, J.; Antonoglou, I.; Panneershelvam, V.; Lanctot, M.; Dieleman, S.; Grewe, D.; Nham, J.; Kalchbrenner, N.; Sutskever, I.; Lillicrap, T.; Leach, M.; Kavukcuoglu, K.; Graepel, T.; and Hassabis, D.  2016\.  Mastering the game of Go with deep neural networks and tree search.  Nature.
  * Stahl (1993) Stahl, I.  1993\.  Predicate invention in ilp — an overview.  In Brazdil, P. B., ed., Machine Learning: ECML-93.  Berlin, Heidelberg: Springer Berlin Heidelberg.
  * Sun, Wu, and Lim (2020) Sun, S.; Wu, T.; and Lim, J. J.  2020\.  Program guided agent.  In International Conference on Learning Representations.
  * Sutton and Barto (2018) Sutton, R. S., and Barto, A. G.  2018\.  Reinforcement Learning: An Introduction.  Cambridge, MA, USA: A Bradford Book.
  * Verma et al. (2018) Verma, A.; Murali, V.; Singh, R.; Kohli, P.; and Chaudhuri, S.  2018\.  Programmatically interpretable reinforcement learning.  In International Conference on Machine Learning.
  * Wulfmeier, Posner, and Abbeel (2017) Wulfmeier, M.; Posner, I.; and Abbeel, P.  2017\.  Mutual alignment transfer learning.  In Conference on Robot Learning.
  * Zheng et al. (2021) Zheng, W.; Sharan, S. P.; Fan, Z.; Wang, K.; Xi, Y.; and Wang, Z.  2021\.  Symbolic visual reinforcement learning: A scalable framework with object-level abstraction and differentiable expression search.  CoRR.
  * Zhu et al. (2019) Zhu, H.; Xiong, Z.; Magill, S.; and Jagannathan, S.  2019\.  An inductive synthesis framework for verifiable reinforcement learning.  In ACM-SIGPLAN Symposium on Programming Language Design and Implementation.