# Deep Explainable Relational Reinforcement Learning: A Neuro-Symbolic
Approach

Rishi Hazra 1Centre for Applied Autonomous Sensor Systems (AASS),
Örebro University, Sweden 1 Luc De Raedt 1Centre for Applied Autonomous Sensor
Systems (AASS),
Örebro University, Sweden 12Department of Computer Science, KU Leuven, Belgium
<EMAIL_ADDRESS>
###### Abstract

Despite numerous successes in Deep Reinforcement Learning (DRL), the learned
policies are not interpretable. Moreover, since DRL does not exploit symbolic
relational representations, it has difficulties in coping with structural
changes in its environment (such as increasing the number of objects).
Relational Reinforcement Learning, on the other hand, inherits the relational
representations from symbolic planning to learn reusable policies. However, it
has so far been unable to scale up and exploit the power of deep neural
networks. We propose Deep Explainable Relational Reinforcement Learning
(DERRL), a framework that exploits the best of both – neural and symbolic
worlds. By resorting to a neuro-symbolic approach, DERRL combines relational
representations and constraints from symbolic planning with deep learning to
extract interpretable policies. These policies are in the form of logical
rules that explain how each decision (or action) is arrived at. Through
several experiments, in setups like the Countdown Game, Blocks World,
Gridworld, and Traffic, we show that the policies learned by DERRL can be
applied to different configurations and contexts, hence generalizing to
environmental modifications††footnotetext: Accepted in ECML PKDD 2023.

###### Keywords:

Neuro-Symbolic AI Relational Reinforcement Learning Deep Reinforcement
Learning, Explainability.

##  1 Introduction

Deep Reinforcement Learning (DRL) [2] has gained great success in many
domains. However, so far, it has had limited success in relational domains,
which are typically used in symbolic planning [40]. In the prototypical blocks
world game (Figure 1), one goal is to place block $a$ on block $b$. An obvious
plan for achieving this is to unstack the blocks until both blocks $a$ and $b$
are at the top, upon which block $a$ can be moved atop block $b$. Standard DRL
approaches struggle to adapt to out-of-domain data, such as placing block $c$
on $d$, or applying the learned strategies to changes in the stack size or the
number of stacks, thus failing to learn generalized policies. Furthermore, the
black-box nature of the learned policies makes it difficult to interpret
action choices, especially in domains involving transparency and safety [33,
47, 22]. Understanding a machine’s decision-making is crucial for human
operators to eliminate irrational reasoning [51, 17].

Relational Reinforcement Learning (RRL) [7, 49] combines symbolic planning and
reinforcement learning and has origins in Statistical Relational AI and
Inductive Logic Programming (ILP) [39, 5]. RRL uses logic programs to
represent interpretable policies that are similar to symbolic planning
languages [11, 16, 15]. These policies use relations and objects, rather than
specific states and actions, allowing agents to reason about their actions at
a higher level of abstraction, and applying the learned knowledge to different
situations. Earlier RRL approaches were purely symbolic [7, 6, 26, 38],
searching policy spaces guided by performance estimates, but did not exploit
deep learning advancements and were not robust to noisy data. Recent
approaches [56] use neural networks for scalability and improved internal
representations, but learned policies are not human-readable.

Figure 1: Learned rules in all environments. [Row 1]left to right. Countdown
Game: select operations (addition, subtraction, null) to make accumulated $=$
target; Blocks World: place a specific block on another; DoorKey: unlock a
door with a matching key to reach a goal. [Row 2] Traffic: minimize traffic at
grid intersections. The figure shows a 5-agent grid with intersections $0$ and
$1$ connected by lane $a$; Gridworld: navigate a grid to reach the goal.
Descriptions in Section 5.1.

We introduce Deep Explainable Relational Reinforcement Learning (DERRL: neural
DRL + symbolic RRL), a neuro-symbolic RRL approach that combines the strengths
of neural (differentiability and representational power) and symbolic methods
(generalizability and interpretability) while addressing their respective
shortcomings. More specifically, DERRL uses a neural network to search the
space of policies represented using First-Order Logic (FOL)-based
rules111DERRL uses a relational representation akin to Quinlan’s FOIL[42] with
background knowledge comprising ground facts and non-recursive Datalog-
formulated rules.. Like other ILP methods, our framework provides
interpretable solutions. However, instead of using search-based methods, we
leverage the representational capacity of neural networks to generate
interpretations of actions (called rules), while entirely bypassing the need
to interpret the network itself. To be specific, we propose a parameterized
rule generation framework where a neural network learns to generate a set of
generalized discriminative rules that are representations of the policy. For
instance, as shown in the blocks world manipulation game in Figure 1, the two
rules corresponding to $move$ action are – $move(X,Y)\leftarrow
top(X),on(X,Z),isFloor(Y)$, which triggers an unstacking process, and
$move(X,Y)\leftarrow top(X),top(Y),goal\\_on(X,Y)$, which puts block $a$ on
$b$ when both are top blocks in the stacks. Note, that the same rules are
applicable for a new goal (say $goal\\_on(c,d)$) or when blocks are increased
to $10$.

Additionally, we formulate a semantic loss [53] to guide the rule learning and
restrict the hypothesis space of rules. This loss enforces semantic
constraints on rule structure through a differentiable relaxation of semantic
refinement [4] allowing users to encode background knowledge as axioms to
mitigate rule redundancy. For example, in the rule $r\leftarrow
less(X,Y),less(Y,Z),less(X,Z)$, due to the transitive relation
$less(X,Z)\leftarrow less(X,Y),less(Y,Z)$, the term $less(X,Z)$ is redundant.
DERRL enables predefining such knowledge as axioms, penalizing models that
violate them. We compare our framework with that of Neural Logic Reinforcement
Learning (NLRL) [25] which uses FOL to represent reinforcement learning
policies and is based on Differentiable Inductive Logic Programming
($\partial$ILP) [10]. Much like DERRL, NLRL uses policy gradients to train a
differentiable ILP module by assigning learnable weights to rules. The authors
demonstrate interpretability and generalizability of policies to different
problem configurations. We demonstrate DERRL’s advantages over NLRL in terms
of computational efficiency, policy accuracy, and semantic constraint
enforcement.

Contributions. (i) A neuro-symbolic framework DERRL for learning interpretable
RL policies in on-policy, model-free settings, demonstrating their
adaptability to environmental changes; (ii) A differentiable relaxation of
semantic refinement for guiding rule generation and constraining the
hypothesis space.

##  2 Related Works

Integrating Symbolic Planning and RL. Recent research has sought to merge
symbolic planning with deep reinforcement learning (DRL) to improve data
efficiency and performance, as seen in works like PEORL [55], RePReL [30], and
SDRL [36]. These approaches aim to integrate a high-level planner that
suggests sub-goals to be executed by a low-level DRL model, thus relying on
predefined environment dynamics, such as high-level action schemas with pre
and postconditions. DERRL differs from planning-based methods as it is purely
a RL approach, i.e. it does not have access to precise handcrafted action
schemas or the reward function, and instead learns suitable control policies
through trial-and-error interactions with the environment. Therefore, we only
compare DERRL with other RL baselines. Explainable RL. Previous studies on
interpretable RL have utilized decision trees for their ease of
interpretation. Standard decision trees consist of nested if-then rules, are
non-differentiable, and cannot be trained using gradient descent methods. The
online nature of RL problems, combined with the non-stationarity introduced by
an improving policy, presents additional challenges for decision trees as the
agent interacts with the environment. One straightforward but inefficient
solution is to re-learn the decision trees from scratch [8]. More recently,
researchers have explored the use of differentiable functions in decision
trees [12]. Differentiable Decision Trees have also been adapted for the RL
framework [44, 34], although their performance does not match that of deep
neural networks. Concurrent Works. Our work on integrating differentiable
logic programming into RL is concurrent with efforts such as NLRL [25] and
dNL-ILP [41]. While dNL-ILP lacks goal generalization, we use the recent NLRL
as our baseline. Recent research has also employed Graph Neural Networks [29]
to capture relational representations [13, 14] with applications to DRL [24]
demonstrating zero-shot generalization to varying problem sizes. DERRL
additionally learns interpretable policies. Adjusting Language Bias The
possible hypothesis space expands exponentially with input space,
necessitating user adjustments to language biases based on domain knowledge.
Relational learning systems use declarative bias via semantic refinement [4].
Differentiable rule learning methods like $\partial$ILP [10] and NLRL [25] use
rule templates to limit rule body atoms to $2$. However, these methods
overlook background knowledge and face redundancies. DERRL mitigates
redundancies and shrinks the search space through a differentiable relaxation
of semantic refinement.

##  3 Preliminaries

###  3.1 Logic Programming:

Logic Programming [35] rules are written as clauses of the form
$\alpha\leftarrow\alpha_{1},\dots,\alpha_{m}$ composed of a head atom $\alpha$
and a body $\alpha_{1},\dots,\alpha_{m}$. These clauses are defined using the
standard if-then rules, wherein, if the body is satisfied, the head is true.
Each atom is a tuple $p(v_{1},\dots,v_{n})$ where $p$ is a n-ary predicate and
$v_{1},\dots,v_{n}$ are either variables or constants. A ground atom is one
that contains only constants. A predicate can either be extensional when it is
defined by a set of ground atoms, or target (intensional) when it is defined
by a set of clauses.

An alphabet $\mathcal{L}$ is defined by the tuple
$\mathcal{L}:=(\mathrm{P}_{\text{tar}},\mathrm{P}_{\text{ext}},arity,C,V)$
where, $\mathrm{P}_{\text{tar}}$ is a set of target predicates,
$\mathrm{P}_{\text{ext}}$ is a set of extensional predicates,
$arity:\mathrm{P}_{\text{ext}}\cup\mathrm{P}_{\text{tar}}\mapsto\mathbb{N}$ is
the number of arguments (variables or constants) that the predicate can take,
$C$ is a set of constants and $V$ is a set of variables allowed in the clause.
For the blocks world game in Figure 1, $\mathrm{P}_{\text{tar}}=\\{move/2\\}$,
$\mathrm{P}_{\text{ext}}=\\{top/1,on/2,$
$goal\\_on/2,isFloor/1\\},V=\\{X,Y,Z\\}$, $C=\\{a,b,c\\}$.

###  3.2 Relational Markov Decision Process:

We model our problem as a Relational MDP (RMDP) given by the tuple
$\mathcal{E}:=(S,\mathcal{B},A,\delta,r,\gamma)$ which is just like a regular
MDP, but with relational states and actions. Here, $S$ is a set of states,
where each state is represented as a set of ground atoms consisting of
predicates in $\mathrm{P}_{\text{ext}}$ and constants in $C$; $\mathcal{B}$ is
the background knowledge also represented in form of ground atoms consisting
of predicates and constants, but unlike the state, it remains fixed over the
episode; $A$ is a set of actions consisting of ground atoms from predicates in
$\mathrm{P}_{\text{tar}}$ and constants in $C$; $\delta:S\times A\mapsto S$ is
an unknown transition function; $r:S\times A\mapsto R$ is an unknown real-
valued reward function; $\gamma$ is the discount factor. In the blocks world
game (Figure 1), for the tuple $((a,b,c))$222Here, the outer tuple denotes
stacks and the inner tuples denote the blocks in the stack. For e.g.,
$((a,b),(c,d))$ has two stacks: $(a,b)$ is stack 1 and $(c,d)$ is stack 2.,
the initial state $s_{0}$ and $\mathcal{B}$ are
$\\{top(c),on(c,b),on(b,a),on(a,floor)\\}$ and
$\\{isFloor(floor),goal\\_on(a,b)\\}$, respectively. The actions are
$move(X,Y)$ where variables $X$ and $Y$ can be substituted with constants in
$C$. Although underlying models often use logical transition and reward rules
[27], our approach is model-free, so we ignore them here.

###  3.3 Problem Statement:

Given, a tuple $(\mathcal{L},\mathcal{E})$ where $\mathcal{L}$ is an alphabet,
and $\mathcal{E}$ is an RMDP;
Find an optimal policy $\pi_{\theta}:S\cup\mathcal{B}\mapsto A$ as a set of
clauses (also called rules) that maximizes the expected reward
$\mathbb{E}_{\tau\sim\pi_{\theta}}\big{[}R_{\tau}\big{]}$, where
$R_{\tau}:=\sum_{k=t+1}^{T-1}\gamma^{k-t-1}R_{k}$. Here, an episode trajectory
is denoted by $\tau$.

More formally, the rules are selected from the hypotheses space, which is the
set of all possible clauses. The head atom of each such rule is an action and
the body is the definition of the action. As shown in Figure 1, a rule for
$move(X,Y)$ in the blocks world environment is given as $move(X,Y)\leftarrow
top(X),on(X,Z),$ $isFloor(Y)$ which states that $move(X,Y)$ is triggered when
the rule definition (i.e., the body) is satisfied. Thus, if the policy selects
the action $move(c,floor)$, one can quickly inspect the body to find out how
that action was taken. The rules are _discriminative_ (i.e. that help select
the correct action by distinguishing it from alternative actions) and together
provide an interpretation of the policy. A set of rules is learned for each
action. Once trained, the rules for actions do not change and the rule body
decides which action should be triggered at each time-step. In what follows,
we provide a detailed explanation of rule generation and inference for each
time-step of an episode. For simplicity, we expunge the time-step notation
(for e.g., state at $t^{th}$ time-step $s_{t}$ is now $s$).

##  4 Proposed Approach

Consider an alphabet $\mathcal{L}$ where
$\mathrm{P}_{\text{tar}}=\\{r/0,s/0\\},\mathrm{P}_{\text{ext}}=\\{p/1,q/2\\},V=\\{X,Y\\},\\\
C=\\{a,b\\}$. The set of all ground atoms $G$ formed from the predicates in
$\mathrm{P}_{\text{ext}}$ and constants in $C$ is
$\\{p(a),p(b),q(a,a),q(a,b),q(b,a),q(b,b)\\}$. We represent each ground atom
$g_{j}\in G$ along with its index $j$ in Table 1.

Recall, that both state $s$ and background knowledge $\mathcal{B}$ are
represented using ground atoms. Given a state $s=\\{p(a),q(a,a),q(a,b)\\}$ at
each time-step, and an empty background knowledge $\mathcal{B}$, we encode it
to a state vector $\bm{v}$, such that each element
$v_{j}=1\;\text{if}\;g_{j}\in\\{s,\mathcal{B}\\}$ (i.e. if the current state
$s$ or the background knowledge $\mathcal{B}$ contains the ground atom
$g_{j}$), else $0$. Let us now consider the set of all atoms $K$ formed from
the predicates in $\mathrm{P}_{\text{ext}}$ and variables in $V$ (instead of
the constants in $C$). Table 2 lists the atoms $k_{j}\in K$ and the
corresponding $\bm{v}$.

Table 1: Table of all ground atoms $G$ and their indices $j$. $j$ | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---
$g_{j}$ | $\mathbf{p(a)}$ | $p(b)$ | $\mathbf{q(a,a)}$ | $\mathbf{q(a,b)}$ | $q(b,a)$ | $q(b,b)$ | $s=\\{p(a),q(a,a),q(a,b)\\}$
$v_{j}$ | 1 | 0 | 1 | 1 | 0 | 0 | $\bm{v}=[1,0,1,1,0,0]$
Table 2: All atoms $K$, their indices $j$, the generated rule vectors ${\bm{b}^{r},\bm{b}^{s}}$, and corresponding probability vectors ${\bm{P}^{r},\bm{P}^{s}}$ for target actions $\mathrm{P}_{\text{tar}}={r/0,s/0}$. $j$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ |
---|---|---|---|---|---|---|---
$k_{j}$ | ${\color[rgb]{0,0,1}p(X)}$ | ${\color[rgb]{1,0,0}p(Y)}$ | $q(X,X)$ | $q(X,Y)$ | ${\color[rgb]{1,0,0}q(Y,X)}$ | ${\color[rgb]{0,0,1}q(Y,Y)}$ |
$b_{j}^{r}$ | 0 | 1 | 0 | 0 | 1 | 0 | $r\leftarrow{\color[rgb]{1,0,0}p(Y),q(Y,X)}$
$P_{j}^{r}$ | 0.1 | 0.8 | 0.3 | 0.4 | 0.7 | 0.2 | $\bm{w}^{r}=[{\color[rgb]{1,0,0}0.8,0.7}]^{\top}$
$b_{j}^{s}$ | 1 | 0 | 0 | 0 | 0 | 1 | $s\leftarrow{\color[rgb]{0,0,1}p(X),q(Y,Y)}$
$P_{j}^{s}$ | 0.6 | 0.3 | 0.4 | 0.2 | 0.1 | 0.9 | $\bm{w}^{s}=[{\color[rgb]{0,0,1}0.6,0.9}]^{\top}$

We represent rules using rule vectors. As shown in Table 2, the rule vector
for each action $i\in A$ is given as $\bm{b}^{i}\in\\{0,1\\}^{m}$, where
$m=\mid K\mid$ (i.e. the cardinality of the set of all atoms formed from the
predicates in $\mathrm{P}_{\text{ext}}$ and variables in $V$). Here,
$b_{j}^{i}=1$, if the $j^{th}$ atom is in the body of the $i^{th}$ rule. From
Table 2,
$\bm{b}^{r}=[0,{\color[rgb]{1,0,0}1},0,0,{\color[rgb]{1,0,0}1},0]^{\top}$
corresponds to the rule $r\leftarrow{\color[rgb]{1,0,0}p(Y),q(Y,X)}$.

We impose the Object Identity (OI) assumption [28] which states that during
grounding and unification, distinct variables must be mapped to distinct
constants. For instance, ground rules for $r\leftarrow p(Y),q(Y,X)$ are
$r\leftarrow p(b),q(b,a)$ and $r\leftarrow p(a),q(a,b)$ under substitutions
$\phi_{0}=\\{a/X,b/Y\\}$ and $\phi_{1}=\\{b/X,a/Y\\}$, respectively, but a
substitution $\phi_{2}=\\{a/X,a/Y\\}$ is not allowed. Without loss of
generality, one can model nullary predicates and negated atoms, by simply
including additional dimensions (corresponding to atoms in $K$) in the vector
$\bm{b}^{i}$.

The DERRL framework learns a rule vector $\bm{b}^{i}$ for each action $i\in A$
by associating it with a trainable weight vector $\bm{w}^{i}$. Each element
$w_{j}^{i}\in\bm{w}^{i}$ indicates the membership of the corresponding atom in
the rule definition (i.e., if the weight of the atom is high, it is more
likely to belong to the rule definition). Given the state vector $\bm{v}$,
action probabilities $\pi_{\theta}(i\mid s,\mathcal{B})$ are calculated by
performing a fuzzy conjunction on the rules (Section 4.2.1). The whole
framework is trained end-to-end using the REINFORCE algorithm [52], with the
loss function given as
$J(\pi_{\theta})=-\mathbb{E}_{\tau\sim\pi_{\theta}}\big{[}R_{\tau}\big{]}$.
Here, $R_{\tau}$ is the discounted sum of rewards over trajectory $\tau$, and
$\theta$ is the set of trainable parameters.

Algorithm 1 summarizes the DERRL framework. The two main components of DERRL
are (i) Rule Generator (Section 4.1), which at every time-step $t$ and for
each action $i\in A$, generates a rule vector $\bm{b}^{i}$, and a weight
vector $\bm{w}^{i}$; (ii) Forward chaining Inference (Section 4.2) that takes
the generated rules vectors for all actions $\\{\bm{b}^{i}\\}_{i=1}^{\mid
A\mid}$, the corresponding weight vectors $\\{\bm{w}^{i}\\}_{i=1}^{\mid
A\mid}$, and the state valuation vector $\bm{v}$ for the $t^{th}$ time-step,
and returns the action probabilities $\pi_{\theta}(.\mid s,\mathcal{B})$.
Note, that the rule generator parameters $\theta$ are trained by calculating
the gradients of the loss function with respect to weight vectors
$\bm{w^{i}}$.

###  4.1 Rule Generation

The rule $\mathcal{R}_{\theta}:i\mapsto\bm{b}^{i},\bm{w}^{i}$ uses a
parameterized network $\mathcal{R}_{\theta}$ to map each action (index) $i$ to
a rule vector $\bm{b}^{i}$ and weight vector $\bm{w}^{i}$. Here, $b_{j}^{i}=1$
indicates the $j^{th}$ atom is in the rule body. The rule generator outputs a
probability vector $\bm{P}^{i}$ where $P_{j}^{i}$ represents the probability
of the $j^{th}$ atom in $K$ belonging to the rule body. We use the Gumbel-max
trick [23] on $\bm{P}^{i}$ to sample the binary vector $\bm{b}^{i}$.

$b_{j}^{i}=\operatorname*{arg\,max}(\log(P_{j}^{i})+u_{0},\log(1-P_{j}^{i})+u_{1})\;\text{where}\;u\sim\operatorname*{Gumbel}(0,1)$

Here, $\operatorname*{Gumbel}(0,1)$ is the standard Gumbel distribution given
by the probability density function $f(x)=e^{-(x+e^{-x})}$. During evaluation,
we use $\operatorname*{arg\,max}(.)$ operation without sampling. From
$\bm{P}^{i}$, we also obtain the weight vector
$\bm{w}^{i}\in\mathbb{R}^{\|\bm{b}^{i}\|_{1}}$ comprising the probabilities of
only those atoms which have $b_{j}^{i}=1$. From Table 2, the generated rule
vector
$\bm{b}^{r}=[0,{\color[rgb]{1,0,0}1},0,0,{\color[rgb]{1,0,0}1},0]^{\top}$, the
probability vector
$\bm{P}^{r}=[0.1,{\color[rgb]{1,0,0}0.8},0.3,0.4,{\color[rgb]{1,0,0}0.7},0.2]^{\top}$,
and the corresponding weight vector
$\bm{w}^{r}=[{\color[rgb]{1,0,0}0.8},{\color[rgb]{1,0,0}0.7}]^{\top}$.

###  4.2 Inference

$i$ | $\mathbf{X}^{i}$ | $\mathbf{Y}^{i}$ | $\bm{w}^{i}$ | $\bm{z}^{i}$ | $\mathcal{F}^{i}$ | $\pi_{\theta}(i\mid s,\mathcal{B})$
---|---|---|---|---|---|---
$r\leftarrow{\color[rgb]{1,0,0}p(Y),q(Y,X)}$ | $\begin{bmatrix}0,3\\\ 1,4\end{bmatrix}$ | $\begin{bmatrix}1,1\\\ 0,0\end{bmatrix}$ | $\begin{bmatrix}0.8\\\ 0.7\end{bmatrix}$ | $\begin{bmatrix}0.5\\\ 0\end{bmatrix}$ | $0.5$ | $0.62$
$s\leftarrow{\color[rgb]{0,0,1}p(X),q(Y,Y)}$ | $\begin{bmatrix}0,5\\\ 1,2\end{bmatrix}$ | $\begin{bmatrix}1,0\\\ 0,1\end{bmatrix}$ | $\begin{bmatrix}0.6\\\ 0.9\end{bmatrix}$ | $\begin{bmatrix}0\\\ 0\end{bmatrix}$ | $0$ | $0.38$

Consider the following rules generated by the rule generator. Each rule is
passed through a substitution $\phi:V\mapsto C$ to produce ground rules. Let,
$\mathbf{X}^{i}\in\mathbb{Z}_{\geq 0}^{N(\phi)\times\|\bm{b^{i}}\|_{1}}$ be
the matrix representation of the ground rules. Here, $\mathbb{Z}_{\geq 0}$ and
$N(\phi)$ are the set of non-negative integers and the number of possible
substitutions, respectively. Each row in $\mathbf{X}^{i}$ is a vector of
ground atom indices that belong to the ground rules. Using a substitution
$\phi=\\{b/X,a/Y\\}$, we obtain the ground rule $r\leftarrow p(a),q(a,b)$.
From Table 1, this rule definition can be written as the vector $[0,3]$ (i.e.,
indices of $p(a)$ and $q(a,b)$ are 0, 3, respectively). Similarly, the
substitution $\phi=\\{a/X,b/Y\\}$ gives us $r\leftarrow p(b),q(b,a)$, and the
vector $[1,4]$.

Next, the $\operatorname*{value}(.)$ operation takes each element
$\mathbf{X}^{i}_{j}$ and returns its state value $v_{j}$. From Table 1,
$\mathbf{Y}^{r}=\operatorname*{value}(\mathbf{X}^{r})=\operatorname*{value}(\begin{bmatrix}0,3\\\
1,4\end{bmatrix})=\begin{bmatrix}v_{0},v_{3}\\\
v_{1},v_{4}\end{bmatrix}=\begin{bmatrix}1,1\\\ 0,0\end{bmatrix}$. The row
vectors of
$\mathbf{Y}^{i}=[\bm{y}_{1}^{i},\dots,\bm{y}_{N(\phi)}^{i}]\in\mathbb{R}^{N(\phi)\times\|\bm{b^{i}}\|_{1}}$
can be regarded as truth values of the grounded rule (i.e., for each
substitution $\phi$), based on $\\{s,\mathcal{B}\\}$. If the rule definition
is not satisfied, the corresponding row vectors will have sparse entries. To
ensure differentiability, we use fuzzy norms for our rules.

####  4.2.1 Fuzzy Conjunction Operators.

Fuzzy norms integrate logic reasoning with deep learning by approximating the
truth values of predicates [10, 37]. Fuzzy conjunction operators
$*:[0,1]^{\|\bm{b^{i}}\|_{1}}\mapsto[0,1]$ can be of various types like Godel
t-norm and Product t-norm (refer Section 11). We use Lukasiewicz t-norm
($\top_{\text{Luk}}(a,b):=\operatorname*{max}\\{0,a+b-1\\}$) to compute the
action values for each rule333More generally, given a vector
$\bm{y}\in[0,1]^{n}$, Lukasiewicz t-norm
$\top_{\text{Luk}}\bm{y}:=\operatorname*{max}(0,\langle\bm{y},\mathbb{1}\rangle-n+1)$.
For the proof, refer Section 11.. To encourage the rule generator to generate
more precise rules with higher probability, we calculate a valuation vector by
weighing each row $\bm{y}_{k}^{i}\in\mathbb{R}^{\|\bm{b^{i}}\|_{1}}$ with the
weight vector $\bm{w}^{i}\in\mathbb{R}^{\|\bm{b^{i}}\|_{1}}$, and using the
Lukasiewicz operator as
$z_{k}^{i}=\operatorname*{max}(0,\langle\bm{y}_{k}^{i},\bm{w}^{i}\rangle-\mid\bm{w}^{i}\mid+1)$.
Intuitively, the inner product $\langle\bm{y}_{k}^{i},\bm{w}^{i}\rangle$ is a
weighted sum over all atoms in the rule body that are true in
$s\cup\mathcal{B}$. This is akin to performing $(a+b)$ in t-norm operator. For
$\bm{y}_{0}^{r}=[1,1]^{\top},\bm{w}^{r}=[0.8,0.7]$:

$z_{0}^{r}=\operatorname*{max}(0,\langle\begin{bmatrix}1\\\
1\end{bmatrix},\begin{bmatrix}0.8\\\ 0.7\end{bmatrix}\rangle-1)=0.5$

With multiple substitutions (or groundings) for a generated rule, we find the
maximum valuation as $\mathcal{F}^{i}=\operatorname*{max}(\bm{z}^{i})$. The
final action probability is calculated as $\pi_{\theta}(i\mid
s,\mathcal{B})=\operatorname*{softmax}(\mathcal{F}^{i})$. Note, that if the
generated rule is not satisfied for any substitution (i.e., has a sparse row
vector in the matrix $\mathbf{Y}^{i}$), the valuation of the generated rule is
lower (for e.g., from the above table $\mathcal{F}^{s}<\mathcal{F}^{r}$).

####  4.2.2 Multiple rules for a single action.

We generalize DERRL to learn policies with multiple rules for each action,
allowing it to switch between rules based on input (for e.g. in the blocks
world game, the "move" action uses two rules executed at different steps
depending on the goal blocks’ position). We allow multiple rule networks per
action, adjusting the final computation step to determine action probabilities
based on the best-satisfied rule. Given $\mathcal{F}_{1}^{i}$ and
$\mathcal{F}_{2}^{i}$ for two different rules for the same action, we first
compute
$\tilde{\mathcal{F}^{i}}=\operatorname*{max}(\mathcal{F}_{1}^{i},\mathcal{F}_{2}^{i})$
to determine which rule is more appropriate at a given time-step. Consider two
different rules generated for action $r$ with arbitrary $\mathbf{Y}^{i}$:

$i$ | $\mathbf{Y}^{i}$ | $\bm{w}^{i}$ | $\bm{z}^{i}$ | $\mathcal{F}^{i}$
---|---|---|---|---
$r_{1}\leftarrow p(Y),q(Y,X)$ | $\begin{bmatrix}1,1\\\ 0,0\end{bmatrix}$ | $\begin{bmatrix}0.8\\\ 0.7\end{bmatrix}$ | $\begin{bmatrix}0.5\\\ 0\end{bmatrix}$ | $0.5$
$r_{2}\leftarrow p(X),p(Y),q(X,X)$ | $\begin{bmatrix}1,0,1\\\ 0,1,1\end{bmatrix}$ | $\begin{bmatrix}0.6\\\ 0.8\\\ 0.8\end{bmatrix}$ | $\begin{bmatrix}0\\\ 0\\\ 0\end{bmatrix}$ | $0$

Here, $\tilde{\mathcal{F}^{r}}=\operatorname*{max}(0.5,0)=0.5$ is the
valuation for rule $r$. Intuitively, depending on the current state $s$ and
background knowledge $\mathcal{B}$, one of the rules will be more appropriate
(i.e., lower sparsity in rows of $\mathbf{Y}^{i}$) than the others, prompting
the policy to switch to that rule for decision making444This assumes a
specified upper bound on the number of rules for each action, similar to
selecting the number of clusters in a clustering algorithm [54]..

Algorithm 1 Deep Explainable Relational Reinforcement Learning (DERRL)

Input: Alphabet: $\mathcal{L}$, RMDP: $\mathcal{E}$
Output: (set of) rules that encode the policy $\pi_{\theta}$

Initialize rule generator parameters $\theta$

for each episode do

for $t=0$ to $T-1$ do

$\bm{v}=\operatorname*{encode}(s,\mathcal{B})$ $\triangleright$ state vector

for each action $i$ do

$\bm{b}^{i},\bm{w}^{i}\sim\mathcal{R}_{\theta}(i)$ $\triangleright$ Rule
Generation (Section 4.1)

end for

$\pi_{\theta}(.\mid s,\mathcal{B})$ =
$Inference(\bm{v},\\{\bm{b}^{i}\\}_{i=1}^{\mid
A\mid},\\{\bm{w}^{i}\\}_{i=1}^{\mid A\mid})$ $\triangleright$ (Section 4.2)

$a\sim\pi_{\theta}{(.\mid s,\mathcal{B})}$

$s^{\prime}\leftarrow\delta(s,a)$; $R_{t}\leftarrow r(s,a)$

end for

$R_{\tau}\leftarrow\sum_{t+1}^{T-1}\gamma^{k-t-1}R_{k}$

$\theta\leftarrow\theta-\eta\nabla_{\theta}\mathbb{E}_{\tau\sim\pi_{\theta}}[R_{\tau}]$

end for

###  4.3 Semantic Constraints

The set of possible rules to consider grows exponentially with the number of
predicates and their arity. While traditional relational learning systems have
used declarative bias in form of semantic refinement [4], prior works in
differentiable rule learning [10, 25] employ rule templates to restrict the
hypothesis space (e.g. rules of size $2$). However, these methods frequently
encounter redundancies. For example, rules $r\leftarrow
less(X,Y),less(Y,Z),less(X,Z)$ and $s\leftarrow equal(X,Y),equal(Y,X)$ exhibit
transitive and symmetric relations, respectively, making some atoms redundant.
A rule $r$ is redundant w.r.t. a constraint $h\leftarrow b_{1},...,b_{n}$ if
the rule $false\leftarrow h,b_{1},...,b_{n}$ subsumes the rule $r$. To avoid
redundancies, generated rule vectors with $b^{i}_{j}=1$ for both atoms
$equal(X,Y)$ and $equal(Y,X)$ should be penalized. To this end, we propose a
differentiable relaxation of semantic refinement by applying a supervised loss
on probability vectors $\\{\bm{P}^{i}\\}_{i=1}^{\mid A\mid}$. We declare
semantic constraints $\mathcal{S}_{c}$ as axioms which can either be a
relation (symmetric or transitive), or some background fact (like
$false\leftarrow on(X,Y),on(Y,X)$). Then we calculate the semantic loss as
$\mathcal{L}_{sem}=\sum_{x\in\mathcal{S}_{c}}\sum_{i\in A}\prod_{j\in
x}P^{i}_{j}$.

Here, the outer summation is over each semantic constraint
$x\in\mathcal{S}_{c}$, and the inner summation is over each generated rule
$i\in A$. The product is over the probability of each atom (with index $j$) in
the body of axiom $x$. For instance, given a single axiom $false\leftarrow
p(Y),q(Y,X)$, for the generated rule $r\leftarrow p(Y),q(Y,X)$, from Table 2,
the loss is $\mathcal{L}_{sem}=P^{i}_{1}\times P^{i}_{4}=0.56$. Here, the loss
is high because according to the given constraint, $p(Y)$ and $q(Y,X)$ should
not appear together in the body of the rule. Intuitively, the loss is highest
if the membership probabilities of both atoms are high warranting a
penalization. $\mathcal{L}_{sem}$ is summed over the entire episode and the
final loss is given as
$\bar{J}(\pi_{\theta})=J(\pi_{\theta})+\lambda_{sem}\mathcal{L}_{sem}$. Here,
$\lambda_{sem}$ is a regularization term. See Appendix 8 for constraints in
all environments.

##  5 Experiments

Through our experiments, we aim to answer the following questions: (1) Can the
proposed approach learn interpretable policies while performing on par with
neural-based baselines? (Section 6.1); (2) Are the learned rules agnostic to
modifications in the environment? (Section 6.2); (3) How efficient and
scalable is the proposed approach compared to the current state-of-the-art
NLRL? (Section 6.3)

###  5.1 Experimental Setup

The Countdown Game. The agent manipulates a stack of numbers and an initial
accumulated value $acc(X)$ to match a target number $goal(X)$ by applying
operations like addition ($add$), subtraction ($sub$), or no operation
($null$). The stack comprises of the top number ($curr(X)$), number below it
($next(X,Y)$), and bottom-most number ($last(X)$). From Figure 1, the state
$s_{t}$ includes the stack, accumulated number, and goal number. Operations
are performed between the accumulated value and the top number of the
stack555$add$: acc $\mathrel{+}=$ top, $sub$: acc $\mathrel{-}=$ top, $null$:
acc. The background knowledge $\mathcal{B}$ comprises the target
number666$goal(X)$ is provided as background since it does not change during
the episode., and atoms of the form $less(X,Y)$ which denote that number $X$
is less than $Y$. A reward of $r=1$ is given when the target and accumulated
values match at the end of the episode, otherwise $r=-\frac{|goal-
acc|}{N_{1}}$ where $N_{1}$ is a normalizing constant. An initial range of
numbers $[-4,6]$ and stack of length$=2$ is used for training. The learned
models are tested for generalization on the following tasks (i) dynamic stack
lengths of $\\{3,4,5\\}$; (ii) held-out target unseen during training; (iii)
held-out initial stack sequences. We also train a stochastic game version with
$10\%$ probability of altering an action to null.

Blocks World Manipulation. Given an initial configuration of blocks, the goal
is to put a specified block atop another specified block (Figure 1). Stacks
are represented using predicates: $top(X)$ means that block $X$ is the top
block, $on(X,Y)$ means that block $X$ is on top of block $Y$. The actions are
$move(X,Y)$ with $X=\\{a,b,c\\}$ and $Y=\\{a,b,c,floor\\}$. A reward $r=1$ is
provided if the task is achieved. To enforce optimal planning, we impose a
penalty of $r=-0.02$ for every action. Training includes a fixed number of
blocks $=3$ and a fixed goal – to stack block $a$ on block $b$
($goal\\_on(a,b)$). We train it with initial configurations:
$((a,b,c));((c,a,b));((a,c),(b));((b,c),(a))$. Here, each tuple is a stack.
For generalization, we use variations like (i) held-out configuration unseen
during training like $((a,b),(c));((b,c,a));((b,a,c))$; (ii) dynamic (number
of) blocks $\\{4,5\\}$; (iii) dynamic (number of) stacks $\\{2,3,4\\}$; (iv)
unseen goals like $goal\\_on(b,a)$ and $goal\\_on(a,c)$.

Gridworld. The agent navigates a grid with obstacles to reach the goal (Figure
1). The agent can move vertically ($up/down$) or sideways ($left/right$). The
state information consists of the current position of the agent $curr(X,Y)$
where $X$ and $Y$ are the coordinates, and the compass direction of the target
(North, South, East, West, Northeast, Northwest, Southeast, Southwest). The
background information consists of target coordinates ($target(X,Y)$),
obstacle coordinates ($obs(X,Y)$), and successor information $succ(X,Y)$ where
$Y=X+1$. The action space is $\\{up,down,left,right\\}$. The agent receives a
reward of $r=1$ for reaching the target, otherwise
$r=-\frac{\|position_{goal}-position_{agent}\|_{2}}{N_{2}}$. Here $N_{2}$ is a
normalizing constant. During training, a fixed size grid of $3\times 3$ and
$5\times 5$ is used with the number of obstacles being fixed $=2$. For
generalization, we use the following variations: (i) dynamic (number of)
obstacles $\\{3,4\\}$; (ii) held-out (agent-goal) configurations. Unlike graph
search algorithms like $\mathrm{A}^{\ast}$ that assume access to the dynamics
model, DERRL learns actions through exploration.

Traffic. We used the Simulation of Urban MObility (SUMO) traffic simulator
[31] to simulate traffic flow, where intersections (3-way and 4-way) function
as agents denoted by $intersection(Y)$, and are connected by a network of
2-way lanes represented as $between(X,Y,Z)$, indicating a connection between
intersections $Y$ and $Z$ by lane $X$. The goal is to minimize the traffic at
the intersections, hence reward is the negative queue length at each
intersection. Each agent is provided with the lane that has the highest
traffic, labeled as $highest(X)$ for lane $X$, and is responsible for
controlling the traffic lights for that lane, enabling them to turn the lights
green ($green(X)$) for a specific lane $X$. Therefore, 3 and 4-way
intersections have an action space of size $3,4$ respectively. Although only
two models (one for all 3-way intersections and another for all 4-way
intersections) suffice, we train each intersection independently to
demonstrate the scalability of DERRL to multi-agent setups, and also for
future developments in cooperative multi-agent setups [57, 21]. We train on a
grid comprising 5 agents and transfer the learned rules to an 8-agent grid. We
show the mean rewards of all agents in Table 3 – note, that the best possible
reward $\approx 0$.

DoorKey Minigrid. The agent task is to unlock a locked door ($locked(Y),\\\
door(Y)$) and reach a goal ($goal(Z)$). Various colored keys ($key(X)$) are
scattered throughout the room, and the agent must select the key that matches
the color of the door ($samecolor(X,Y)$) to unlock it. We use high-level
actions. The agent is only allowed to carry one key at a time and can navigate
to and pick up a key $X$ using the $pick(X)$ action if it is not carrying any
keys ($notcarrying$), otherwise, it drops the key before picking the new one.
The $open(X)$ action enables it to unlock a door $X$ if it carries the key
that matches the door’s color. The $goto(X)$ action enables the agent to
navigate to a specific object $X$. The reward $=1$ for successfully reaching
the goal, else $0$. The learned model is tested for generalization with
additional doors and keys of varying colors.

We evaluate our DERRL against Neural Logic Reinforcement Learning
(NLRL) baseline. We also compare with model-free DRL approaches with
variations in the deep learning module like (i) Graph Convolution Network
(GCN) [29] that perform well at relational learning [32], and are invariant to
the number of nodes in the graph; (ii) Multilayer Perceptron (MLP). Finally,
we compare with a Random (Random) baseline where the weights of the MLP are
randomized to set a lower limit on the performance. We use a single-layer
neural network for our rule generator (2$m$ parameters). For the GCN and MLP
baselines, we experimented with 2-layer networks (O($m^{3}$) parameters).

Table 3: Generalization Scores (average rewards over 50 episodes across 3 runs) compare DERRL to other baselines. DERRL outperforms baselines, including the state-of-the-art NLRL. In Traffic, the mean reward for all agents is reported. Setup |  |  DERRL |  NLRL |  GCN |  MLP |  Random
---|---|---|---|---|---|---
Countdown Game |  |  training |  0.98 |  0.95 |  0.98 |  1.00 |  0.30
---|---|---|---|---|---
dynamic stack |  0.98 |  0.95 |  0.95 |  0.54 |  0.38
held-out target |  0.98 |  0.85 |  0.95 |  0.35 |  0.33
held-out initial |  0.98 |  0.55 |  1.00 |  0.35 |  0.18
|  |  |  |
Countdown Game(stochastic) |  |  training |  0.98 |  0.95 |  0.98 |  1.00 |  0.15
---|---|---|---|---|---
|  |  |  |
Blocks World Manipulation |  |  training |  0.97 |  0.97 |  0.97 |  0.97 |  -0.18
---|---|---|---|---|---
held-out config. |  0.97 |  0.70 |  0.55 |  0.45 |  -0.18
dynamic blocks |  0.92 |  0.51 |  -0.20 |  -0.21 |  -0.22
dynamic stacks |  0.96 |  0.90 |  0.90 |  0.85 |  -0.18
unseen goal |  0.96 |  0.45 |  -0.18 |  -0.18 |  -0.18
|  |  |  |
DoorKey Minigrid |  |  training |  0.80 |  0.45 |  0.75 |  0.90 |  0.10
---|---|---|---|---|---
dynamic keys/doors |  0.78 |  0.25 |  0.35 |  0.20 |  0.05
|  |  |  |
Traffic |  |  training (5-agents) |  -0.76 |  -0.91 |  -0.90 |  -0.95 |  -1.54
---|---|---|---|---|---
8-agents |  -1.02 |  -1.28 |  -1.45 |  -1.75 |  -2.17
|  |  |  |
Gridworld Game |  |  training |  0.75 |  0.72 |  0.70 |  0.81 |  0.03
---|---|---|---|---|---
dynamic obstacles |  0.70 |  0.55 |  0.46 |  0.51 |  -0.15
held-out config. |  0.81 |  0.70 |  0.17 |  -0.61 |  -0.70
|  |  |  |

##  6 Results

###  6.1 Interpretation of policies (Q1)

In this section, we provide interpretations of the learned rules in each
training environment, as shown in Figure 1. The Countdown Game. The policy
selects $add$ action when $acc(X)<goal(Y)$, $sub$ action when
$acc(X)>goal(Y)$, and null action when both are equal. Blocks World
Manipulation. The policy learns two rules for $move(X,Y)$. Given a goal to put
block $a$ atop block $b$, the first rule is applicable when at least one of
the blocks is not the top block. Hence, the policy learns to unstack the
blocks – the top block $X$ of the stack is moved to the floor $Y$. The second
rule is applied when both $a$ and $b$ are at the top. Traffic. The general
rule for each intersection is $green(X)\leftarrow
highest(X),between(X,Y,Z),intersection(Y),intersection(Z)$. Intuitively, the
lights corresponding to the lane with the highest traffic $X$, connecting
intersections $Y$ and $Z$, are turned green. DoorKey Minigrid. The learned
rule for action $pickup(X)$ tells the agent to pickup the key $X$ that matches
the color of the door $Y$, provided that it is not carrying any other items
($notcarrying$). Similarly, for $open(X)$, the learned rule states that the
agent can unlock a locked door $X$ using the key $Y$ only if the colors of the
door and the key match. The $goto(X)$ action directs the agent to navigate to
the goal object $X$ when the door is $unlocked$. Gridworld Game. In this
setting, the policy learns two rules for each action. The first is used for
navigation to the target, such as moving $up$ if the target is to the north
(or northeast and northwest) of the grid. The second helps navigate around
obstacles, e.g. move $up$ if the obstacle (given by $(Z,Y)$) is to the
immediate right of the agent (given by $(X,Y)$). However, the policy may not
follow the shortest path777When the target is to the southeast, and the agent
encounters a target to its right, it will travel north ($up$) rather than
south ($down$). or have consistent traversal strategies, resulting in varied
rules for different instances without performance loss.

DERRL also bears similarities with Program Synthesis [48, 3, 20], which
involves finding a program that meets user specifications and constraints.
Learned policies can be rewritten as programs (see Appendix 10). For example,
a program to solve the countdown game involves operating on current and
accumulated values (using $add,sub,null$ operations) until accumulated value
$=$ goal value.

Figure 2: [Best viewed in color] Comparison of training rewards at convergence
for different baselines plotted by averaging the rewards over 3 independent
runs. [Left to right] Countdown Game, Blocks World, and Gridworld.

###  6.2 Generalization performance (Q2)

From Table 3, we observe that DERRL learns general rules, generalizing to
environment modifications, and outperforms baselines in generalization tasks.
Unlike symbolic planning, DERRL’s performance remains unaffected by noisy
training, such as stochastic Countdown. Secondly, although GCNs perform well
in relational learning, their generalization is marginally better than MLP,
potentially failing to capture task agnostic relational patterns. However, GCN
surpasses MLP and NLRL in the countdown game. Lastly, DERRL’s training
performance is comparable to MLP, but it outperforms MLP in generalization
tasks, where MLP is similar to the Random baseline. Additionally, DERRL’s
convergence speed is on par with MLP, as shown in Figure 2.

###  6.3 Comparison with NLRL (Q3)

Computational Complexity. NLRL assigns trainable weights to all possible rules
with a body size of 2, while DERRL allocates weights to each atom in the rule
body. Given, $m$ atoms from $\mathrm{P}_{\text{ext}}$ and $V$, NLRL has C(m,2)
learnable weights, while DERRL has 2m. Therefore, the training reduces from
learning the best set of rules (in NLRL) to learning the best membership of
the rules (in DERRL), leading to a lower computation time in DERRL. The
computation time per episode is reduced by a factor of $\approx 10$ (Figure
3).
Comparing Learned Rules. NLRL learned rules in blocksworld are:

$\displaystyle move(X,Y)\leftarrow top(X),pred(X,Y);\;\;\;move(X,Y)\leftarrow
top(X),goal\\_on(X,Y)$ $\displaystyle pred(X,Y)\leftarrow
isFloor(Y),pred2(X);\;\;\;pred2(X)\leftarrow on(X,Y),on(Y,Z)$

With invented predicates $pred$ and $pred2$, this plan differs from DERRL in
that the second rule doesn’t verify if both X and Y are movable, failing to
solve configurations where block b is below block a. Size of hypothesis space.
DERRL restricts the hypothesis space through the use of semantic constraints
in the optimization problem, whereas large hypothesis space in NLRL limits its
convergence in DoorKey and Traffic domains. The convergence in DERRL is slower
without semantic constraints (see Appendix 9 for ablations on DERRL with and
without semantic constraints). Expressiveness. NLRL can learn recursive rules
by using templates as in meta-interpretive learning and predicate invention.
While this is expressive, it can be hard to master. In contrast, DERRL learns
non-recursive Datalog as Quinlan’s FOIL [42] but combines it with constraints
that can be recursive to rule out redundancies.

Figure 3: Run-time comparison per episode between DERRL and NLRL as problems
scale. Left to right: Countdown game (stack size), Countdown game (range of
numbers), Blocks World (number of blocks). Y-axis in log scale. Plots show
NLRL takes approximately 10 times longer per episode compared to DERRL. See
additional plots in Appendix 9.

##  7 Conclusion

We proposed a neuro-symbolic approach to learn interpretable policies that are
also generalizable. The representations that DERRL and RRL use are very
similar to those used in the planning community. We also significantly improve
upon the scalability of existing state-of-the-art NLRL. Upgrading the approach
to enable automatic learning of the required number of rules can be a
potential research direction. Also, as a part of future work, it will be
interesting to explore ways in which the proposed approach can be scaled to
real-life applications requiring the need to process raw sensory inputs.

## Acknowledgement

This work was partially supported by the Wallenberg AI, Autonomous Systems and
Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.

## References

  * [1] Alur, R., Bodik, R., Juniwal, G., Martin, M.M.K., Raghothaman, M., Seshia, S.A., Singh, R., Solar-Lezama, A., Torlak, E., Udupa, A.: Syntax-guided synthesis. In: 2013 Formal Methods in Computer-Aided Design. pp. 1–8 (2013), https://ieeexplore.ieee.org/document/6679385
  * [2] Arulkumaran, K., Deisenroth, M.P., Brundage, M., Bharath, A.A.: Deep reinforcement learning: A brief survey. IEEE Signal Processing Magazine 34(6), 26–38 (2017)
  * [3] Biermann, A.W.: The inference of regular lisp programs from examples. IEEE Transactions on Systems, Man, and Cybernetics 8(8), 585–600 (1978), https://ieeexplore.ieee.org/document/4310035
  * [4] De Raedt, L.: Logical and relational learning. In: Zaverucha, G., da Costa, A.L. (eds.) Advances in Artificial Intelligence - SBIA 2008. pp. 1–1. Springer Berlin Heidelberg, Berlin, Heidelberg (2008)
  * [5] De Raedt, L., Kersting, K., Natarajan, S., Poole, D.: Statistical Relational Artificial Intelligence: Logic, Probability, and Computation, Synthesis Lectures on Artificial Intelligence and Machine Learning, vol. 32. Morgan & Claypool, San Rafael, CA (2016)
  * [6] Driessens, K., Džeroski, S.: Integrating guidance into relational reinforcement learning. Machine Learning 57(3), 271–304 (2004)
  * [7] Dzeroski, S., Raedt, L.D., Blockeel, H.: Relational reinforcement learning. In: Proceedings of the Fifteenth International Conference on Machine Learning. p. 136–143. ICML ’98, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1998)
  * [8] Ernst, D., Geurts, P., Wehenkel, L.: Tree-based batch mode reinforcement learning. Journal of Machine Learning Research 6(18), 503–556 (2005), http://jmlr.org/papers/v6/ernst05a.html
  * [9] Esteva, F., Godo, L.: Monoidal t-norm based logic:towards a logic for left-continuous t-norms. Fuzzy Sets and Systems 124(3), 271–288 (2001). https://doi.org/https://doi.org/10.1016/S0165-0114(01)00098-7, https://www.sciencedirect.com/science/article/pii/S0165011401000987, fuzzy Logic
  * [10] Evans, R., Grefenstette, E.: Learning explanatory rules from noisy data. J. Artif. Int. Res. 61(1), 1–64 (jan 2018)
  * [11] Fikes, R.E., Nilsson, N.J.: Strips: A new approach to the application of theorem proving to problem solving. Artificial Intelligence 2(3), 189–208 (1971), https://www.sciencedirect.com/science/article/pii/0004370271900105
  * [12] Frosst, N., Hinton, G.E.: Distilling a neural network into a soft decision tree. CoRR abs/1711.09784 (2017), http://arxiv.org/abs/1711.09784
  * [13] Garg, S., Bajpai, A., et al.: Size independent neural transfer for rddl planning. In: Proceedings of the International Conference on Automated Planning and Scheduling. vol. 29, pp. 631–636 (2019)
  * [14] Garg, S., Bajpai, A., et al.: Symbolic network: generalized neural policies for relational mdps. In: International Conference on Machine Learning. pp. 3397–3407. PMLR (2020)
  * [15] Gelfond, M., Lifschitz, V.: Action languages. Electronic Transactions on Artificial Intelligence 3, 195–210 (1998), http://www.cs.utexas.edu/users/ai-lab?gel98
  * [16] Ghallab, M., Howe, A., Knoblock, C., Mcdermott, D., Ram, A., Veloso, M., Weld, D., Wilkins, D.: PDDL—The Planning Domain Definition Language (1998), http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.212
  * [17] Gilpin, L.H., Bau, D., Yuan, B.Z., Bajwa, A., Specter, M.A., Kagal, L.: Explaining explanations: An approach to evaluating interpretability of machine learning. CoRR abs/1806.00069 (2018), http://arxiv.org/abs/1806.00069
  * [18] Graves, A., Wayne, G., Danihelka, I.: Neural turing machines (2014), http://arxiv.org/abs/1410.5401, cite arxiv:1410.5401
  * [19] Gulwani, S., Harris, W.R., Singh, R.: Spreadsheet data manipulation using examples. Commun. ACM 55(8), 97–105 (aug 2012), https://doi.org/10.1145/2240236.2240260
  * [20] Gulwani, S., Polozov, O., Singh, R.: Program synthesis. Foundations and Trends® in Programming Languages 4(1-2), 1–119 (2017), http://dx.doi.org/10.1561/2500000010
  * [21] Gupta, S., Hazra, R., Dukkipati, A.: Networked multi-agent reinforcement learning with emergent communication. arXiv preprint arXiv:2004.02780 (2020)
  * [22] Iyer, R., Li, Y., Li, H., Lewis, M., Sundar, R., Sycara, K.: Transparency and explanation in deep reinforcement learning neural networks. In: Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society. p. 144–150. AIES ’18, Association for Computing Machinery, New York, NY, USA (2018), https://doi.org/10.1145/3278721.3278776
  * [23] Jang, E., Gu, S., Poole, B.: Categorical reparameterization with gumbel-softmax. In: 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. p. 0. OpenReview.net, Palais des Congrès Neptune, Toulon, France (2017), https://openreview.net/forum?id=rkE3y85ee
  * [24] Janisch, J., Pevnỳ, T., Lisỳ, V.: Symbolic relational deep reinforcement learning based on graph neural networks. arXiv preprint arXiv:2009.12462 (2020)
  * [25] Jiang, Z., Luo, S.: Neural logic reinforcement learning. In: Proceedings of the 36th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 97, pp. 3110–3119. PMLR, Long Beach, USA (09–15 Jun 2019), https://proceedings.mlr.press/v97/jiang19a.html
  * [26] Kersting, K., Driessens, K.: Non-parametric policy gradients: A unified treatment of propositional and relational domains. In: Proceedings of the 25th International Conference on Machine learning. pp. 456–463 (2008)
  * [27] Kersting, K., Otterlo, M.V., De Raedt, L.: Bellman goes relational. In: Proceedings of the twenty-first international conference on Machine learning. p. 59 (2004)
  * [28] Khoshafian, S.N., Copeland, G.P.: Object identity. ACM SIGPLAN Notices 21(11), 406–416 (1986)
  * [29] Kipf, T.N., Welling, M.: Semi-Supervised Classification with Graph Convolutional Networks. In: Proceedings of the 5th International Conference on Learning Representations. ICLR ’17 (2017), https://openreview.net/forum?id=SJU4ayYgl
  * [30] Kokel, H., Manoharan, A., Natarajan, S., Ravindran, B., Tadepalli, P.: Reprel: Integrating relational planning and reinforcement learning for effective abstraction. In: Proceedings of the International Conference on Automated Planning and Scheduling. vol. 31, pp. 533–541 (2021)
  * [31] Krajzewicz, D., Erdmann, J., Behrisch, M., Bieker, L.: Recent development and applications of sumo-simulation of urban mobility. International journal on advances in systems and measurements 5(3&4) (2012)
  * [32] Lamb, L.C., Garcez, A.d., Gori, M., Prates, M.O., Avelar, P.H., Vardi, M.Y.: Graph neural networks meet neural-symbolic computing: A survey and perspective. In: Bessiere, C. (ed.) Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20. pp. 4877–4884. International Joint Conferences on Artificial Intelligence Organization, Yokohama, Japan (7 2020), https://doi.org/10.24963/ijcai.2020/679, survey track
  * [33] Lee, J.D., See, K.A.: Trust in automation: Designing for appropriate reliance. Human factors 46 1, 50–80 (2004)
  * [34] Liu, G., Schulte, O., Zhu, W., Li, Q.: Toward interpretable deep reinforcement learning with linear model u-trees. In: ECML/PKDD (2018)
  * [35] Lloyd, J.W.: Foundations of Logic Programming. Springer-Verlag, Berlin, Heidelberg (1984)
  * [36] Lyu, D., Yang, F., Liu, B., Gustafson, S.: Sdrl: Interpretable and data-efficient deep reinforcement learning leveraging symbolic planning. In: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence. AAAI’19/IAAI’19/EAAI’19, AAAI Press, Honolulu, Hawaii, USA (2019), https://doi.org/10.1609/aaai.v33i01.33012970
  * [37] Marra, G., Giannini, F., Diligenti, M., Maggini, M., Gori, M.: T-norms driven loss functions for machine learning. arXiv: Artificial Intelligence (2019)
  * [38] Martínez, D., Alenya, G., Torras, C.: Relational reinforcement learning with guided demonstrations. Artificial Intelligence 247, 295–312 (2017)
  * [39] Muggleton, S., De Raedt, L.: Inductive logic programming: Theory and methods. Journal Of Logic Programming 19(20), 629–679 (1994)
  * [40] Nau, D., Ghallab, M., Traverso, P.: Automated Planning: Theory & Practice. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2004)
  * [41] Payani, A., Fekri, F.: Incorporating relational background knowledge into reinforcement learning via differentiable inductive logic programming. arXiv preprint arXiv:2003.10386 (2020)
  * [42] Quinlan, J.R.: Learning logical definitions from relations. Mach. Learn. 5(3), 239–266 (sep 1990). https://doi.org/10.1023/A:1022699322624, https://doi.org/10.1023/A:1022699322624
  * [43] Schkufza, E., Sharma, R., Aiken, A.: Stochastic superoptimization. In: Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems. p. 305–316. ASPLOS ’13, Association for Computing Machinery, New York, NY, USA (2013), https://doi.org/10.1145/2451116.2451150
  * [44] Silva, A., Gombolay, M., Killian, T., Jimenez, I., Son, S.H.: Optimization methods for interpretable differentiable decision trees applied to reinforcement learning. In: Chiappa, S., Calandra, R. (eds.) Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 108, pp. 1855–1865. PMLR, Palermo, Italy (26–28 Aug 2020), https://proceedings.mlr.press/v108/silva20a.html
  * [45] Singh, R., Kohli, P.: Ap: Artificial programming. In: 2nd Summit on Advances in Programming Languages (SNAPL 2017) (April 2017), https://www.microsoft.com/en-us/research/publication/ap-artificial-programming/
  * [46] Solar-Lezama, A.: Program Synthesis by Sketching. Ph.D. thesis, University of California at Berkeley, USA (2008), https://dl.acm.org/doi/10.5555/1714168, aAI3353225
  * [47] Stowers, K., Kasdaglis, N., Newton, O.B., Lakhmani, S.G., Wohleber, R.W., Chen, J.Y.: Intelligent agent transparency. Proceedings of the Human Factors and Ergonomics Society Annual Meeting 60, 1706 – 1710 (2016)
  * [48] Summers, P.D.: A methodology for lisp program construction from examples. J. ACM 24(1), 161–175 (jan 1977), https://doi.org/10.1145/321992.322002
  * [49] Tadepalli, P., Givan, R., Driessens, K.: Relational reinforcement learning: An overview. In: In: Proceedings of the ICML’04 Workshop on Relational Reinforcement Learning (2004)
  * [50] Udupa, A., Raghavan, A., Deshmukh, J.V., Mador-Haim, S., Martin, M.M., Alur, R.: Transit: Specifying protocols with concolic snippets. SIGPLAN Not. 48(6), 287–296 (jun 2013), https://doi.org/10.1145/2499370.2462174
  * [51] de Visser, E.J., Cohen, M., Freedy, A., Parasuraman, R.: A design methodology for trust cue calibration in cognitive agents. In: Shumaker, R., Lackey, S. (eds.) Virtual, Augmented and Mixed Reality. Designing and Developing Virtual and Augmented Environments. pp. 251–262. Springer International Publishing, Cham (2014)
  * [52] Williams, R.J.: Simple statistical gradient following algorithms for connectionist reinforcement learning. Machine Learning 8, 229–256 (1992), https://doi.org/10.1007/BF00992696
  * [53] Xu, J., Zhang, Z., Friedman, T., Liang, Y., Broeck, G.: A semantic loss function for deep learning with symbolic knowledge. In: International conference on machine learning. pp. 5502–5511. PMLR (2018)
  * [54] Xu, R., Wunsch, D.: Survey of clustering algorithms. IEEE Transactions on Neural Networks 16(3), 645–678 (2005). https://doi.org/10.1109/TNN.2005.845141
  * [55] Yang, F., Lyu, D., Liu, B., Gustafson, S.: Peorl: Integrating symbolic planning and hierarchical reinforcement learning for robust decision-making. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. p. 4860–4866. IJCAI’18, AAAI Press, Stockholm, Sweden (2018)
  * [56] Zambaldi, V.F., Raposo, D., Santoro, A., Bapst, V., Li, Y., Babuschkin, I., Tuyls, K., Reichert, D.P., Lillicrap, T.P., Lockhart, E., Shanahan, M., Langston, V., Pascanu, R., Botvinick, M., Vinyals, O., Battaglia, P.W.: Relational deep reinforcement learning. CoRR abs/1806.01830 (2018), http://arxiv.org/abs/1806.01830
  * [57] Zhang, K., Yang, Z., Liu, H., Zhang, T., Basar, T.: Fully decentralized multi-agent reinforcement learning with networked agents. In: International Conference on Machine Learning. pp. 5872–5881. PMLR (2018)

Appendix for “Deep Explainable Relational Reinforcement Learning: A Neuro-
Symbolic Approach"

##  8 Semantic Constraints

Following are the semantic constraints used for each setup

####  8.0.1 The Countdown Game.

$\displaystyle false\leftarrow goal(X),goal(Y)$ $\displaystyle false\leftarrow
less(X,Y),less(Y,X)$ $\displaystyle less(X,Z)\leftarrow less(X,Y),less(Y,Z)$
$\displaystyle false\leftarrow acc(X),acc(Y)$ $\displaystyle false\leftarrow
curr(X),curr(Y)$

####  8.0.2 Blocks World Manipulation.

$\displaystyle false\leftarrow isFloor(X),isFloor(Y)$ $\displaystyle
false\leftarrow on(X,Y),on(Y,X)$ $\displaystyle false\leftarrow
on(X,Y),on(X,Z)$ $\displaystyle false\leftarrow top(X),on(Y,X)$ $\displaystyle
false\leftarrow top(Y),isFloor(Y)$ $\displaystyle false\leftarrow
goal(X,Y),goal(Y,X)$

####  8.0.3 DoorKey Minigrid.

$\displaystyle false\leftarrow carrying(X),notcarrying$ $\displaystyle
samecolor(X,Y)\leftarrow samecolor(Y,Z),samecolor(Z,X)$ $\displaystyle
samecolor(X,Y)\leftarrow samecolor(Y,X)$ $\displaystyle false\leftarrow
carrying(X),carrying(Y)$ $\displaystyle false\leftarrow locked(X),unlocked$

####  8.0.4 Traffic

$\displaystyle between(X,Y,Z)\leftarrow between(X,Z,Y)$ $\displaystyle
false\leftarrow highest(X),highest(Y),highest(Z)$

####  8.0.5 Gridworld Game

$\displaystyle false\leftarrow curr(X,Y),curr(Y,X)$ $\displaystyle
false\leftarrow succ(X,Y),succ(Y,X)$

##  9 Computation Time comparison

Figure 4: Comparison of run-time per episode of DERRL and NLRL with problem
scaling: From left tor right: Gridworld (grid-size), DoorKey (number of keys),
Traffic (number of intersections). The Y-axis is represented in log scale. The
plots show that time taken per episode is significantly higher for NLRL,
compared to DERRL. Figure 5: Ablations on semantic constraints. Figure shows
how the use of semantic constraints lead to faster convergence in the Traffic
(Left) and the DoorKey Minigrid (Right) domains.

See Figure 4 for run-time comparison of DERRL and NLRL for Gridworld, DoorKey,
and Traffic domains. Additionally, as shown in Figure 5, without the use of
semantic constraints, the convergence in DERRL is slower and the learned rules
are redundant.

##  10 Analogies with Program Synthesis

In many ways, program synthesis techniques exhibit the same challenges as that
of interpretable policy learning, wherein, programs generated using neural
methods cannot generalize to new problems [18, 45], and symbolic methods
employing search-based methods are faced with the curse of dimensionality [46,
43, 50]. Our exploratory study indicates that our rule generation framework is
closely related to the paradigm of rule-based program synthesis [19, 1]. The
specification here is – one needs to find a sequence of instructions (a
program or a policy) that transforms the given state into a target state.
However, in program synthesis, the instructions are usually deterministic,
while in RRL they can be stochastic. Note, that DERRL selects at every time
step the next action and moves to the next position and iterates. Although
DERRL uses non-recursive rules, the learned policies are applied iteratively,
which results in programs as shown in Figure 6.

Figure 6: Programs for different environments: [Row 1]: from left to right,
Countdown Game, Gridworld, DoorKey Minigrid. [Row 2]: from left to right,
Traffic and Blocksworld.

##  11 Fuzzy Conjunction Operators

A fuzzy conjunction operator $*:[0,1]^{e}\mapsto[0,1]$ must satisfy the
following conditions on a t-norm [9] (here, $e$ is the number of atoms in the
rule body):

  * •

commutativity: $a\ast b=b\ast a$

  * •

associativity: $(a\ast b)\ast c=a\ast(b\ast c)$

  * •

monotonicity:

    1. 1.

$a_{1}\leq a_{2}$ implies $a_{1}\ast b\leq a_{2}\ast b$

    2. 2.

$b_{1}\leq b_{2}$ implies $a\ast b_{1}\leq a\ast b_{2}$

  * •

unit:

    1. 1.

$a\ast 1=a$

    2. 2.

$a\ast 0=0$

The operators that satisfy the aforementioned conditions are:

  * •

Godel t-norm: $a\ast b:=\operatorname*{min}(a,b)$

  * •

Lukasiewicz t-norm $\top_{\text{Luk}}(a,b):=\operatorname*{max}\\{0,a+b-1\\}$

  * •

Product t-norm: $a\ast b:=a\cdot b$ (ordinary product of real numbers)

Lukasiewicz t-norm was experimentally found to perform better than other
alternatives.

###### Proposition 11.1

More generally, given a vector $\bm{y}\in[0,1]^{n}$, Lukasiewicz t-norm

$\top_{\text{Luk}}\bm{y}:=\operatorname*{max}(0,\langle\bm{y},\mathbb{1}\rangle-n+1)$
(1)

###### Proof

. We prove it using mathematical induction.
Base Case: For $\bm{y}=[a,b]$, eq. 1 is clearly true.

$\top_{\text{Luk}}(a,b):=\operatorname*{max}(0,a+b-2+1)$

Inductive Step: Let, $\top_{\text{Luk}}\bm{y}$ hold for $\bm{y}\in[0,1]^{k}$.
We denote it as,

$\top_{\text{Luk}}\bm{y}:=\operatorname*{max}(0,\langle\bm{y},\mathbb{1}\rangle-k+1)$
(2)

Now let $\tilde{y}\in[0,1]^{k+1}$. Using the associativity property:

$\displaystyle\top_{\text{Luk}}\tilde{\bm{y}}$
$\displaystyle:=\operatorname*{max}(0,\top_{\text{Luk}}\bm{y}+y_{k+1}-1)$
$\displaystyle:=\operatorname*{max}(0,\operatorname*{max}(0,\langle\bm{y},\mathbb{1}\rangle-k+1)+y_{k+1}-1)$

  * •

Case 1: $\langle\bm{y},\mathbb{1}\rangle>(k-1)$. It follows that
$\operatorname*{max}(0,\langle\bm{y},\mathbb{1}\rangle-k+1)=\langle\bm{y},\mathbb{1}\rangle-k+1$

$\displaystyle\top_{\text{Luk}}\tilde{\bm{y}}$
$\displaystyle:=\operatorname*{max}(0,\langle\bm{y},\mathbb{1}\rangle-k+1+y_{k+1}-1)$
$\displaystyle:=\operatorname*{max}(0,y_{1}+\dots+y_{k}-k+1+y_{k+1}-1)$
$\displaystyle:=\operatorname*{max}(0,\langle\tilde{\bm{y}},\mathbb{1}\rangle-(k+1)-1)$

Thus, eqn. 1 is true.

  * •

Case 2: $\langle\bm{y},\mathbb{1}\rangle\leq(k-1)$. It follows that
$\operatorname*{max}(0,\langle\bm{y},\mathbb{1}\rangle-k+1)=0$

$\displaystyle\top_{\text{Luk}}\tilde{\bm{y}}$
$\displaystyle:=\operatorname*{max}(0,y_{k+1}-1)$ $\displaystyle:=0$
$\displaystyle\text{since }y_{k+1}\in[0,1]$

Also,
$\langle\bm{y},\mathbb{1}\rangle\leq(k-1)\implies\langle\tilde{\bm{y}},\mathbb{1}\rangle\leq
k$ since $y_{k+1}\in[0,1]$.
$\therefore$ from eqn. 1, $\top_{\text{Luk}}\tilde{\bm{y}}:=0$

##  12 Code

All models were run on CPU nodes. The codes will be made available soon.