# Language-Based Causal Representation Learning

Blai Bonet,1 Hector Geffner2,3

###### Abstract

Consider the finite state graph that results from a simple, discrete,
dynamical system in which an agent moves in a rectangular grid picking up and
dropping packages. Can the state variables of the problem, namely, the agent
location and the package locations, be recovered from the structure of the
state graph alone without having access to information about the objects, the
structure of the states, or any background knowledge? We show that this is
possible provided that the dynamics is learned over a suitable domain-
independent _first-order causal language_ that makes room for objects and
relations that are not assumed to be known. The preference for the most
compact representation in the language that is compatible with the data
provides a strong and meaningful learning bias that makes this possible. The
language of structured causal models (SCMs) is the standard language for
representing (static) causal models but in dynamic worlds populated by
objects, first-order causal languages such as those used in “classical AI
planning” are required. While “classical AI” requires handcrafted
representations, similar representations can be learned from unstructured data
over the same languages. Indeed, it is the languages and the preference for
compact representations in those languages that provide structure to the
world, uncovering objects, relations, and causes.∗00footnotetext: The paper
was written for a workshop on causal representation learning. A valid
criticism of “classical AI”, mentioned in the call, from the perspective of
the “new AI” based on deep learning, is that representations should be learned
and not handcrafted. One of the aims of the paper was to distinguish
representation _languages_ from the actual representations that they support,
as it is only the latter that should be learned. Another aim was to emphasize
that structural causal models (SCMs) provide one language to talk about causal
models but not the only one. Action and planning languages have been used to
describe causal models in AI for a long time too. Our attempt, however, was
not successful, as the paper was rejected. Not clear if reviewers agreed with
these two premises, or found them irrelevant or vacuous. For us, the two
premises are direct but their implications, explored in this and other papers,
are not.

## Introduction

Two important challenges in causal representation learning are learning the
state variables of a dynamical system from unstructured data, and learning a
representation of the dynamics that is general and reusable (Schölkopf et al.
2021; Schölkopf and von Kügelgen 2022). For example, a system may involve an
agent moving in a $n{\times}m$ grid, picking up and dropping packages.
Learning the causal structure of the domain means to learn the structure of
the states, given by the agent and the package locations, and the structure of
the actions, so that they can be used to plan in other instances of this
general domain. The question is what are the ideas and principles that are
required for uncovering these structures in a crisp and well-founded manner,
without involving prior domain knowledge.

For addressing this and other challenges, deep learning approaches usually
follow a methodology that goes from intuitions about inductive biases to deep
learning architectures and loss functions, and from there to experimental
results and comparisons with baselines (Goyal and Bengio 2020; Goyal et al.
2020, 2021; Aniket Didolkar et al. 2021). The methodology can be applied
broadly and the results show experimental gains, yet the understanding that
follows from them is not always crisp.

In this paper, we articulate a different approach for learning _general causal
representations_ , and two other representations that exploit causal
representations: general policies, and subgoals (“intrinsic rewards”). The
idea is to learn the representations over suitable _domain-independent
languages_ with a known structure (syntax) and known semantics, but without
relying on prior knowledge.

For learning representations of general deterministic, discrete dynamics, we
appeal to a language that has been in use in “classical AI” since the early
70s; namely, lifted (first-order) STRIPS, in its modern version, where a
planning domain is expressed by a number of _action schemas_ with
preconditions and effects given by logical atoms that encode the state
variables and their values. In “classical AI”, these action schemas are
crafted by hand, but as it has been pointed out by Schölkopf and von Kügelgen
(2022), this approach does not scale up as modeling is hard. The “classical”
approach does not explain where models come from either.

---
|  ⬇ Move(?to, ?from): Static Pre: neq(?to, ?from), p5(?to, ?from) Pre: p2(?from), -p2(?to) Eff: -p2(?from), p2(?to) Pick(?p, ?x): Pre: p2(?x), p1, -p3(?p), p4(?p, ?x) Eff: -p1, p3(?p), -p4(?p, ?x) Drop(?p, ?x): Pre: p2(?x), -p1, p3(?p), -p4(?p, ?x) Eff: p1, -p3(?p), p4(?p, ?x) |  |  Interpretation of learned domain predicates: – $p_{1}$ is true iff agent holds no package (i.e., gripper empty), – $p_{2}(x)$ is true iff agent is at cell $x$, – $p_{3}(p)$ is true iff agent holds package $p$, – $p_{4}(p,x)$ is true iff package $p$ is in cell $x$, and – $p_{5}(x,y)$ is true if cell $x$ is adjacent to cell $y$.

---|---|---
Figure 1: Top: Labeled state graph $G$ for agent that can move in $1{\times}3$
grid picking up and dropping two different packages. The graph $G$ has 45
nodes, assumed to be black-box states with no internal structure known (shown
in small circles), and 96 edges, which are labeled with the actions Move,
Pick, and Drop. Bottom left: STRIPS representation $P=\langle D,I\rangle$
learned from $G$: domain $D$ has 3 action schemas over 5 predicates, and $I$
involves 3 objects (only $D$ is shown). $P$ is the _most compact_ STRIPS
encoding that yields a graph $G(P)$ that is isomorphic to $G$. The bijection
$f$ that underlies this isomorphism gives structure to the nodes: black-box
node $n$ in $G$ becomes a planning state $f(n)$ in $G(P)$ that assigns a
truth-value to each of the ground atoms in $P$. Action schemas shown in terms
of their preconditions and effects. Static preconditions that involve
predicates whose denotation does not change are learned as well. The domain
$D$ learned from the $1{\times}3$ instance with two packages works for _any_
grid dimensions and _any_ number of packages. Bottom right: Interpretation of
the learned predicates.

There are, however, _two dimensions_ about knowledge representations that need
to be distinguished: the _representation languages_ , such as STRIPS, that are
domain-independent, and _encodings_ in such languages that have traditionally
been crafted by hand. The representation languages have been designed with the
right goals in mind, including transparency and reuse (McCarthy 1987; Haslum
et al. 2019), and there is no need to throw them away unless other types of
dynamics need to be captured. It is the encodings in the language that
constitute the _representation bottleneck,_ and it is thus the encodings that
should be learned from data. We will see that this is possible when we look
for the most compact representation in the language that explains the data; a
simple a form of Occam’s learning that takes advantage of the powerful and
meaningful inductive bias that results from the syntax and the semantics of
the language.

In the paper we develop this idea of language-based representation learning
and apply it to three related problems: learning general dynamics, learning
general policies, and learning general subgoal structures. The first is about
uncovering the causal structure of a domain; the latter two are about
exploiting it. While the paper is original and written for the “causal
representation learning” audience, the general approach has been developed
elsewhere, as described.

## Preview

The top part of Fig. 1 shows the state graph that results from a simple,
discrete dynamical system that involves an agent that moves on a $1{\times}3$
grid, that can pick and drop two different packages, one at a time. The number
of states, 45, results of adding the number of configurations where the agent
holds no package ($27=3^{3}$) with the number of configurations where the
agent holds one of the packages ($18=2{\times}3^{2}$). The number of edges is
96. An edge $(s,s^{\prime})$ labeled with an action
$a\in\\{\textit{Move},\textit{Pick},\textit{Drop}\\}$ means that the action
$a$ transforms state $s$ into $s^{\prime}$. In recent work it has been shown
that the internal structure of the states can be recovered from state graphs
where the states are black-boxes with no known structure. This is achieved by
learning such representations over a first-order causal language able to
represent objects and relations, which are not assumed to be known, and
seeking the most compact encoding that generates the observed data (i.e., the
given state graph). The language is the modern version of the “classical”
planning language STRIPS where a planning instance $P$ is encoded as a pair
$P=\langle D,I\rangle$ with the domain $D$ being a collection of general
action schemas, involving a set of predicates, and $I$ representing specific
instance information.

Since a planning instance $P$ defines a unique state graph $G(P)$, the
learning task becomes an _inverse problem:_ given an observed state graph $G$,
find the “simplest” planning instance $P=\langle D,I\rangle$ such that the
observed and the generated graphs $G$ and $G(P)$ “match” (are isomorphic).
When the graphs match, every _black-box state_ (node) in $G$ is mapped into an
_structured state_ in $G(P)$ given by the set of ground atoms obtained from
the predicates in $D$ and the set of objects in $I$. The atoms encode the
state variables and their values.

The most compact STRIPS representation $P=\langle D,I\rangle$ for the state
graph shown in Fig. 1 has the domain $D$ shown in the bottom part of the
figure. The learned domain consists of 5 predicates and 3 action schemas that
_generalize_ to any instance of the domain, involving _any_ grid dimensions
and _any_ number of packages. _Objects, relations, and causal structure all
emerge from the flat graph shown. The learned structure is a result of the
data, the target language, and Occam’s razor._

Interestingly, while the state graph $G$ of a single $1{\times}3$ instance
involving two packages yields a domain $D$ that generalizes to any grid size
and any number of packages, smaller training instances yield domains that do
not generalize in the same way. For example, a $1{\times}3$ instance with _one
package_ yields a model with a unary predicate $p_{4}(x)$ that tracks the
position of the unique package and which does not generalize to instances with
multiple packages. Likewise, a $1{\times}2$ instance yields a model with no
$p_{5}(x,y)$ predicate as there is no need then to represent the topology of
the grid (cell adjacency).

## Planning Language

A (classical) planning instance or problem is expressed as a pair
$P\,{=}\,\langle D,I\rangle$ where the domain $D$ contains a set of action
schemas with _preconditions_ and _effects_ given by atoms
$p(x_{1},\ldots,x_{k})$ in term of predicates symbols $p$ and variables
$x_{i}$ that are arguments of the action schema, and the tuple
$I\,{=}\,\langle Objs,\textit{Init},\textit{Goal}\rangle$ specifies the
constants $c_{i}$ in the _instance_ (object names), and the initial and goal
conditions; the latter in terms of _ground atoms_ $p(c_{1},\ldots,c_{k})$
obtained from the domain predicates and the constants (Geffner and Bonet 2013;
Haslum et al. 2019). Modern planners usually replace the action schemas by
their possible instantiations where variables are replaced by constants.
Static preconditions are normally compiled away after pruning the set of
instantiations. A precondition is _static_ when it involves a predicate which
does not appear in an action effect. E.g., predicate $p_{5}$ in Fig. 1 is a
static predicate which captures the adjacency relation among grid cells.

A classical problem $P\,{=}\,\langle D,I\rangle$ encodes a unique state graph
$G(P)$ whose nodes are the states that are reachable in $P$ from the initial
state $s_{0}$. A state $s$ is a collection of ground atoms $q$ from $P$ that
encode truth-valuations ($q$ is true in $s$ iff $q\in s$), and the initial
state $s_{0}$ is $Init$. The graph $G(P)$ contains a labeled edge
$(s,a,s^{\prime})$ if there is a ground instance $a^{\prime}$ of an action
schema $a$ in $D$ that maps the state $s$ into $s^{\prime}$. A ground instance
$a^{\prime}$ replaces the schema parameters with constants, and transforms a
state $s$ into $s^{\prime}$ if the preconditions of $a^{\prime}$ are true in
$s$, the effects of $a^{\prime}$ are true in $s^{\prime}$, and all ground
atoms not affected by $a^{\prime}$ have the same truth value in $s$ and
$s^{\prime}$.

The distinction between the general domain given by $D$ and the specific
information given by $I$ in an instance $P=\langle D,I\rangle$ is particularly
relevant in the learning setting where learning the structure of $P$ will mean
to learn a general domain $D$ that applies to an infinite number of instances
$P^{\prime}=\langle D,I^{\prime}\rangle$ that differ from $P$ in the number of
objects, or in their initial or goal configurations, but not in the vocabulary
(predicates) that captures the structure of the states, or in the action
schemas that capture the possible state trajectories. In other words, the
domain $D$ expresses in a compact way what is common (invariant) over all
these instances.

## Learning Planning Models

The problem of learning general action models from states graphs where states
are black boxes has been formulated as follows (Bonet and Geffner 2020):

Learning action models. Given observed graphs $G_{1},\ldots,G_{n}$, find the
simplest domain $D$ and instances $P_{i}=\langle D,I_{i}\rangle$ such that the
graphs $G_{i}$ and $G(P_{i})$ are isomorphic for $i=1,\ldots,n$.

The complexity of a domain is measured in terms of the number and arity of the
action schemas and predicates involved. Once these numbers are bounded, the
learning problem becomes a _combinatorial optimization task_ that has been
expressed and solved using SAT and answer set solvers (Bonet and Geffner 2020;
Rodriguez et al. 2021). Variations of this basic problem have also been
considered like dealing with noisy and incomplete traces as opposed to fully
known graphs (Rodriguez et al. 2021).

The domains that have been learned in this way include several benchmark
domains in planning, from Blocks and Logistics, to IPC-Grid (a domain similar
to Minigrid (Chevalier-Boisvert et al. 2019)) and Sokoban. In all cases, one
does not only learn the internal structure of the nodes in the given graphs
(i.e., the atoms encoding the state variables and their values), but a general
domain representation that can be applied to other instances. This is the
result of the strong and meaningful bias that follows from aiming at the most
compact language-based model that matches the data. A crucial part of this is
the use of a _first-order target language_ for learning. One action schema
represents a potentially infinite set of ground instances. If rather than
looking for the most compact _lifted_ STRIPS representation, we look for the
most compact _propositional_ STRIPS representation, very different
representations would result.

This is a vanilla solution method, inherently incapable of learning domains
dynamics that cannot be expressed in compact form in lifted STRIPS, but it is
a crisp formulation based on general principles and ideas; namely, Occam’s
learning (Kearns and Vazirani 1994) over an hypothesis space spanned by the
target language. If one wants to learn general dynamics of domains with
continuous, exogenous, or non-deterministic changes, a different target
language for learning must be used. STRIPS is a simple language for modeling
deterministic actions, but there are more expressive planning (action)
languages (Lifschitz 1999; Haslum et al. 2019), some of which are used to
specify MDPs and POMDPs in compact form using action schemas, objects, and
relations (Younes et al. 2005; Sanner 2011).

The general idea of language-based representation learning has been used to
learn first-order planning representations from _gray-box states_ represented
as objects in 2D grids. In this case, the learned state representations are
_grounded_ in the 2D scenes, meaning that there is a 1-to-1 correspondence
between scenes and planning states that generalizes to new scenes (Liberman et
al. 2022).

## Learning General Policies

The languages for learning representations can be taken off the shelf in many
cases, but in others, new domain-independent languages may be needed. For
example, in the Minigrid benchmark (Chevalier-Boisvert et al. 2019), DRL
approaches are not after general dynamic models, but after _general policies_
: policies that can deal with _any_ instance of the domain. What is then a
good domain-independent language for representing such policies? This question
has been considered in the area of _generalized planning_ , and the language
below follows the one introduced by Bonet and Geffner (2018).

A general policy $\pi$ for a (possibly infinite) class of instances
$\mathcal{Q}$ drawn from a domain $D$ is given by a set of _policy rules_ of
the form $C\mapsto E$ where $C$ contains boolean conditions of the form $p$,
$\neg p$, $n=0$, or $n>0$, and $E$ contains effects of the form $p$, $\neg p$,
$p?$, $n\raisebox{0.6458pt}{$\downarrow$}$,
$n\raisebox{0.6458pt}{$\uparrow$}$, $n?$, over boolean and numerical
_features_ $p$ and $n$ that are well-defined over the states $s$ of any
instance from $\mathcal{Q}$. The action prescribed by the policy $\pi$ in a
state $s$ is any action that maps $s$ into a state $s^{\prime}$ such that the
state transition $(s,s^{\prime})$ satisfies some policy rule $C\mapsto E$ in
$\pi$; namely, $s$ makes $C$ true, and the transition $(s,s^{\prime})$ makes
the change expressed by $E$ true as well.

For example, with features $\Phi=\\{H,p,t,n\\}$ for “holding a package”,
“distances to nearest package and to the target”, and “number of undelivered
packages”, the following policy solves _any_ instance of the domain displayed
in Fig. 1 when the goal is to take all the packages, one by one, to a target
cell in the grid:

$\displaystyle\\{\neg
H,p{\,>\,}0\\}\mapsto\\{p\raisebox{0.6458pt}{$\downarrow$},t?\\}\,;$ go to
nearest pkg, $\displaystyle\\{\neg H,p{\,=\,}0\\}\mapsto\\{H\\}\,;$ pick it
up,
$\displaystyle\\{H,t{\,>\,}0\\}\mapsto\\{t\raisebox{0.6458pt}{$\downarrow$}\\}\,;$
go to target, $\displaystyle\\{H,n{\,>\,}0,t{\,=\,}0\\}\mapsto\\{\neg
H,n\raisebox{0.6458pt}{$\downarrow$},p?\\}\,;$ drop pkg.

The first rule says to do any action that decreases the distance $p$ to the
nearest package ($p\raisebox{0.6458pt}{$\downarrow$}$) when not holding a
package and the distance is positive ($\neg H$ and $p{\,>\,}0)$, whatever the
effect on the distance $t$ to the target ($t?$). The reading of the other
rules is similar with $x\raisebox{0.6458pt}{$\downarrow$}$ standing for
decrements of feature $x$, and $x?$ for any change in $x$. Features not
mentioned in the right-hand side of a policy rule must keep their values
unchanged.

This is a policy written by hand, and the question is how such policies can be
learned. As before, the learning problem has been formulated and solved as a
combinatorial optimization problem by creating a large but finite set of
possible boolean and numerical features _from the domain predicates_ , using a
description logic grammar that captures a decidable fragment of first-order
logic, $\mathcal{C}_{2}$, where the number of variables is limited to two
(Baader et al. 2008). Provided with this pool of features, where each feature
is given a cost (the number of grammar rules used to derive it), the task of
learning a general policy becomes (Francès et al. 2021):

Learning general policies. Given a known domain $D$, training instances
$P_{1},\ldots,P_{n}$, over $D$, and a finite pool of domain features ${\cal
F}$, each with a cost, find the simplest policy $\pi$ over $\cal F$ such that
$\pi$ solves all $P_{i}$, $i=1,\ldots,n$.

Once again, the _language_ in which policy representations are sought provides
a _strongly biased hypothesis space_ where policies that involve few simple
features (in terms of the domain predicates) are preferred. The simplest
policies are those that minimize the complexity of the the features involved.
General policies for a number of benchmark planning domains have been derived
in this way and proved to be correct (Francès et al. 2021). More recently, an
alternative learning scheme has been introduced which does _not_ require a
predefined pool of features (Stählberg et al. 2022a, b). This is achieved by
introducing two variations. First, general value functions $V$ are learned
instead of general policies, so that the resulting policies are those which
are greedy in $V$. Second, the value functions are expressed in terms of graph
neural networks (GNNs) which are known to capture $\mathcal{C}_{2}$ features
(Barceló et al. 2020; Grohe 2020). Interestingly, the resulting policies
generalize equally well (100% generalization in rich, combinatorial domains)
and yield close-to-optimal policies even in domains where one can prove that
there are no general policies that are optimal (Gupta and Nau 1992). One point
in common with recent deep learning approaches for computing general policies
that appeal to _causal considerations_ (Zhang et al. 2020; Sonar et al. 2021)
is that the learned features are functions of the domain predicates; namely,
the predicates that are used to capture the causal dynamics of the domain.

## Learning Subgoal Structure

The problem of expressing and using the common subgoal structure of a
collection of planning problems has been important in AI since the 1960s,
while the problem of _learning_ such structure has become important in recent
RL research where useful subgoals are expressed via intrinsic rewards
(Chentanez et al. 2004; Zheng et al. 2020). We are interested in a similar
problem but want to learn subgoal structures over a _suitable language._ The
questions, from the perspective of language-based representation learning, are
1) what is an adequate language for representing subgoal structure, 2) what is
its semantics, and 3) how representations over such language can be learned. A
general compact language for representing subgoal structures has been
developed recently whose syntax is the syntax of the general policies
considered above. The change is in the semantics (Bonet and Geffner 2021).

A _(policy) sketch_ is a set of sketch rules $C\mapsto E$ of the same form as
policy rules, but while policy rules filter 1-step transitions; namely, when
in a state $s$, a 1-step transition to any $s^{\prime}$ must be selected such
that $(s,s^{\prime})$ satisfies a policy rule, sketch rules define
_subproblems:_ when in a state $s$ of an instance $P$, a state $s^{\prime}$ is
to be reached, _not necessarily in one step_ , such that the multi-step
transition $(s,s^{\prime})$ satisfies a sketch rule (or $s^{\prime}$ satisfies
the goal of $P$).

Sketches _decompose_ problems into _subproblems_ without prescribing how the
subproblems should be solved (going from $s$ to $s^{\prime}$). One is
interested, however, in sketches that yield subproblems that can be solved
efficiently, in low polynomial time (in the number of problem variables), and
this is guaranteed when subproblems have _bounded width_ (Lipovetzky and
Geffner 2012). This observation led to the following formulation for learning
sketches, where the notation $P[R]$ is used to refer to the collection of
subproblems defined by the sketch $R$ over states $s$ that are reachable in
the instance $P$ (Drexler et al. 2022):

Learning general sketches. Given a known domain $D$, training instances
$P_{1},\ldots,P_{n}$ and a non-negative integer $k$, find the simplest sketch
$R$ over a pool of domain features $\cal F$ such that 1) the collection of
subproblems induced by $R$ on each instance $P_{i}$, $P_{i}[R]$, have _width
bounded_ by $k$, and 2) the sketch $R$ is acyclic in $P_{i}$, $i=1,\ldots,n$.

The complexity of a sketch is given by the complexity of the features
involved, and a sketch is acyclic in $P$ if the transitions $(s,s^{\prime})$
in $P$ that satisfy sketch rules do not form a cycle. The learning problem
becomes a combinatorial optimization problem modeled and solved using the
answer set programming system Clingo (Gebser et al. 2012).

The learned sketches are not aimed at representing the general causal
structure of the domain, but at exploiting it. Indeed, by learning to
decompose problems into subproblems of bounded width, the problems can be
solved in polynomial time using a general algorithm ($\text{SIW}_{R}$) that
takes the sketch into account (Bonet and Geffner 2021; Drexler et al. 2021).
Simple examples of learned sketches follow.

A width-2 sketch $R_{1}$ for the problem above, where packages need to be
delivered to a target cell, one by one, involves the feature $n$ which tracks
the number of packages not yet delivered, and is given by a single rule:

$\displaystyle
R_{1}:\\{\\{n{\,>\,}0\\}\mapsto\\{n\raisebox{0.6458pt}{$\downarrow$}\\}\\}\,.$

The sketch expresses a decomposition that for states $s$ where $n{\,>\,}0$,
states $s^{\prime}$ should be reached where the value of $n$ is lower than in
$s$. One can show that the resulting subproblems have width bounded by $2$ and
thus can be solved by running the IW(2) algorithm (Lipovetzky and Geffner
2012).

A width-1 sketch $R_{2}$ that involves the features $n$ and $H$ ($H$ is
“holding a package”) is given instead by two rules:

$\displaystyle R_{2}:\\{\\{\neg
H\\}\mapsto\\{H\\}\,,\,\\{n{\,>\,}0,H\\}\mapsto\\{n\raisebox{0.6458pt}{$\downarrow$},\neg
H\\}\\}\,.$

The first rule on the left says that if not holding a package, one such
package should be picked up, while the second on the right says that if
holding a package, it should be delivered. The rules do not express policies
but subgoals to be achieved. In this case, the subproblems have all width $1$
meaning that they can be solved in linear time by running the IW(1) algorithm.

## Related Work

Structured causal models. SCMs are the standard language for encoding and
studying causal models (Pearl 2009). Yet, planning and action languages also
encode causal models; i.e., they can accommodate observations, interventions,
and counterfactuals; all 3-levels of Pearl’s Causation Ladder (Pearl and
Mackenzie 2018)).111For doing this, uncertainty about the initial situation
must be represented, and action precondition and effects in STRIPS need to be
replaced by conditional effects, a standard feature of modern planning
languages (Haslum et al. 2019). Then, the atoms at time $0$ and the actions at
each time step are the exogenous variables, and the atoms at time $t+1$ for
$t>0$ are the endogenous variables. The truth value of the latter is a
function of the value of atoms at time $t$ and the action at $t$. Planning
languages just provide a way for defining the atoms (i.e., the Boolean
variables of interest), the functions, and in certain cases, the uncertainty
about the initial situation, in a compact and reusable form. SCMs enrich the
flat language of probabilities but are not rich enough to express
interventions that do not commute unless the variables are indexed with time
in the style of dynamic bayesian networks (Dean and Kanazawa 1989). Some
planning languages for modeling MDPs and POMDPs are variations of STRIPS and
PDDL (Younes et al. 2005); others, of dynamic bayesian networks (Sanner 2011).
More critically for representation learning, SCMs are propositional and not
first-order, which precludes learning compact representations in settings that
involve objects. The problem of learning SCMs when the variables are known has
been addressed as a combinatorial optimization problem (Hyttinen et al. 2014;
Forré and Mooij 2018), but it is more subtle and lacks a general formulation
when the variables are not known (Schölkopf et al. 2021; Schölkopf and von
Kügelgen 2022). We have shown that the use of first-order causal languages
along with a preference for compact representations uncovers objects,
relations, and causes from state graphs made up of black-box states.

Neuro-symbolic AI. The use of formal representation languages in a learning
setting is common of neuro-symbolic approaches where the languages are used to
encode background knowledge (Badreddine et al. 2020; Manhaeve et al. 2021;
Yang et al. 2020; Skryagin et al. 2021). In language-based representation
learning, on the other hand, no background knowledge is assumed, and the
language provides the general structure over which the representations are
learned (Geffner 2021).

Language-based representation learning.. Many works learn representations over
languages without using background knowledge (Cresswell et al. 2013; Konidaris
et al. 2018; Asai and Fukunaga 2018; Evans et al. 2021b, a; James et al.
2022). In some cases, these are programming or visual languages (Wong et al.
2021; Xie et al. 2021); in others, they provide the intuitions that underlie
the design of deep network architectures aimed at capturing production
systems, action schemas, and other classes of first-order formulas (Goyal et
al. 2020, 2021; Aniket Didolkar et al. 2021; Shanahan et al. 2020). Often
though, deep learning approaches are developed without providing a crisp
characterization of _what_ representations are to be learned that is
independent of _how_ they are learned. We have shown that action schemas and
predicates can be learned using combinatorial solvers but nothing prevents the
use of deep learning engines instead. General policies were learned using
combinatorial solvers (Francès et al. 2021), and then using deep learning
(Stählberg et al. 2022a, b).

General policies, subgoals, and intrinsic rewards. Some approaches for
learning general policies make use of languages for representing policies
(Khardon 1999; Martín and Geffner 2000; Fern et al. 2006); but most of those
based on deep learning, do not (Groshev et al. 2018; Garg et al. 2020; Toyer
et al. 2020). Subgoals in planning have been expressed in terms of
hierarchical task networks (Erol et al. 1994) but a recent language (Bonet and
Geffner 2021) supports more compact representations that facilitates learning
of both policies and sketches (Francès et al. 2021; Drexler et al. 2022). In
RL, subgoals are associated with states of intrinsic reward (stepping stones
to sparse states of extrinsic reward) (Zheng et al. 2020), but no language or
principles have been developed for expressing or learning them, and the focus
is on performance improvement that is less informative and crisp.

## Discussion

The language of structured causal models has been fundamental to model and to
understand causality, but the language itself is insufficient to model the
world. Objects and schemas are required to represent the dynamics of the world
in a compact way, and this ability is a prerequisite for learning it.222The
old AI saying that “you can’t learn what you can’t represent”, still contains
a grain of truth in the age of deep learning. We have advocated the use of a
broader class of domain-independent languages for learning causal
representations, including those required to model dynamics, policies, and
subgoals. Some of these languages can be taken off-the-shelf; others have to
be designed. It is the languages and the preference for compact
representations over them that structure the world and uncover objects,
relations, and causes. The languages considered for modeling and learning
system dynamics, leave many important aspects aside, including continuous,
exogenous, and non-deterministic change. For addressing such aspects, richer
languages and more powerful learning methods, possibly based on deep learning,
are needed. Learning reusable and meaningful language-based dynamic models of,
say, the Atari games from the screen pixels alone, is still an open challenge
that we think could be addressed in the near future.

### Acknowledgments

This research was partially supported by the European Research Council (ERC),
Grant No. 885107, and by project TAILOR, Grant No. 952215, both funded by the
EU Horizon research and innovation programme. This work was partially
supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP)
funded by the Knut and Alice Wallenberg Foundation.

## References

  * Aniket Didolkar et al. (2021) Anirudh Goyal Aniket Didolkar, Aniket Didolkar, Nan Rosemary Ke, Charles Blundell, Philippe Beaudoin, Nicolas Heess, Michael C Mozer, and Yoshua Bengio.  Neural production systems.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Asai and Fukunaga (2018) Masataro Asai and Alex Fukunaga.  Classical planning in deep latent space: Bridging the subsymbolic-symbolic boundary.  In _AAAI_ , 2018.
  * Baader et al. (2008) Frank Baader, Ian Horrocks, and Ulrike Sattler.  _Handbook of Knowledge Representation_ , chapter Description Logics.  Elsevier, 2008.
  * Badreddine et al. (2020) Samy Badreddine, Artur d’Avila Garcez, Luciano Serafini, and Michael Spranger.  Logic tensor networks.  _arXiv preprint arXiv:2012.13635_ , 2020.
  * Barceló et al. (2020) Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva.  The logical expressiveness of graph neural networks.  In _ICLR_ , 2020.
  * Bonet and Geffner (2018) Blai Bonet and Hector Geffner.  Features, projections, and representation change for generalized planning.  In _Proc. IJCAI_ , pages 4667–4673, 2018.
  * Bonet and Geffner (2020) Blai Bonet and Hector Geffner.  Learning first-order symbolic representations for planning from the structure of the state space.  In _Proc. ECAI_ , 2020.
  * Bonet and Geffner (2021) Blai Bonet and Hector Geffner.  General policies, representations, and planning width.  In _Proc. AAAI_ , pages 11764–11773, 2021.
  * Chentanez et al. (2004) Nuttapong Chentanez, Andrew Barto, and Satinder Singh.  Intrinsically motivated reinforcement learning.  _Advances in neural information processing systems_ , 2004.
  * Chevalier-Boisvert et al. (2019) Maxime Chevalier-Boisvert, Dzmitry Bahdanau, Salem Lahlou, Lucas Willems, Chitwan Saharia, Thien Huu Nguyen, and Yoshua Bengio.  Babyai: A platform to study the sample efficiency of grounded language learning.  In _ICLR_ , 2019.
  * Cresswell et al. (2013) S. N. Cresswell, T. L. McCluskey, and M. M. West.  Acquiring planning domain models using LOCM.  _The Knowledge Engineering Review_ , 28(2):195–213, 2013.
  * Dean and Kanazawa (1989) Thomas Dean and Keiji Kanazawa.  A model for reasoning about persistence and causation.  _Computational intelligence_ , 5(2):142–150, 1989\.
  * Drexler et al. (2021) Dominik Drexler, Jendrik Seipp, and Hector Geffner.  Expressing and exploiting the common subgoal structure of classical planning domains using sketches.  In _Proc. KR_ , pages 258–268, 2021.
  * Drexler et al. (2022) Dominik Drexler, Jendrik Seipp, and Hector Geffner.  Learning sketches for decomposing planning problems into subproblems of bounded width.  In _Proc. ICAPS_ , 2022.
  * Erol et al. (1994) Kutluhan Erol, James Hendler, and Dana S. Nau.  HTN planning: Complexity and expressivity.  In _Proc. AAAI-94_ , pages 1123–1123, 1994.
  * Evans et al. (2021a) Richard Evans, Matko Bošnjak, Lars Buesing, Kevin Ellis, David Pfau, Pushmeet Kohli, and Marek Sergot.  Making sense of raw input.  _Artificial Intelligence_ , 299, 2021a.
  * Evans et al. (2021b) Richard Evans, José Hernández-Orallo, Johannes Welbl, Pushmeet Kohli, and Marek Sergot.  Making sense of sensory input.  _Artificial Intelligence_ , 293, 2021b.
  * Fern et al. (2006) Alan Fern, Sungwook Yoon, and Robert Givan.  Approximate policy iteration with a policy language bias: Solving relational markov decision processes.  _JAIR_ , 25:75–118, 2006.
  * Forré and Mooij (2018) Patrick Forré and Joris M Mooij.  Constraint-based causal discovery for non-linear structural causal models with cycles and latent confounders.  In _Proc. UAI_ , 2018.
  * Francès et al. (2021) Guillem Francès, Blai Bonet, and Hector Geffner.  Learning general planning policies from small examples without supervision.  In _Proc. AAAI_ , pages 11801–11808, 2021.
  * Garg et al. (2020) Sankalp Garg, Aniket Bajpai, et al.  Symbolic network: generalized neural policies for relational mdps.  In _International Conference on Machine Learning_ , pages 3397–3407, 2020.
  * Gebser et al. (2012) Martin Gebser, Roland Kaminski, Benjamin Kaufmann, and Torsten Schaub.  _Answer set solving in practice_.  Morgan & Claypool Publishers, 2012.
  * Geffner (2021) Hector Geffner.  Target languages (vs. inductive biases) for learning to act and plan.  In _Proc. AAAI_ , 2021.
  * Geffner and Bonet (2013) Hector Geffner and Bonet Bonet.  _A Concise Introduction to Models and Methods for Automated Planning_.  Morgan & Claypool Publishers, 2013.
  * Goyal and Bengio (2020) Anirudh Goyal and Yoshua Bengio.  Inductive biases for deep learning of higher-level cognition.  _arXiv preprint arXiv:2011.15091_ , 2020.
  * Goyal et al. (2020) Anirudh Goyal, Alex Lamb, Jordan Hoffmann, Shagun Sodhani, Sergey Levine, Yoshua Bengio, and Bernhard Schölkopf.  Recurrent independent mechanisms.  In _International Conference on Learning Representations_ , 2020.
  * Goyal et al. (2021) Anirudh Goyal, Alex Lamb, Phanideep Gampa, Philippe Beaudoin, Sergey Levine, Charles Blundell, Yoshua Bengio, and Michael Mozer.  Object files and schemata: Factorizing declarative and procedural knowledge in dynamical systems.  In _Proc. ICLR_ , 2021.
  * Grohe (2020) Martin Grohe.  The logic of graph neural networks.  In _Proc. of the 35th ACM-IEEE Symp. on Logic in Computer Science_ , 2020.
  * Groshev et al. (2018) Edward Groshev, Maxwell Goldstein, Aviv Tamar, Siddharth Srivastava, and Pieter Abbeel.  Learning generalized reactive policies using deep neural networks.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 28, pages 408–416, 2018.
  * Gupta and Nau (1992) Naresh Gupta and Dana S Nau.  On the complexity of blocks-world planning.  _Artificial Intelligence_ , 56(2-3):223–254, 1992\.
  * Haslum et al. (2019) Patrik Haslum, Nir Lipovetzky, Daniele Magazzeni, and Christian Muise.  _An Introduction to the Planning Domain Definition Language_.  Morgan & Claypool, 2019.
  * Hyttinen et al. (2014) Antti Hyttinen, Frederick Eberhardt, and Matti Järvisalo.  Constraint-based causal discovery: Conflict resolution with answer set programming.  In _UAI_ , pages 340–349, 2014.
  * James et al. (2022) Steven James, Benjamin Rosman, and George Konidaris.  Autonomous learning of object-centric abstractions for high-level planning.  In _ICLR_ , 2022.
  * Kearns and Vazirani (1994) Michael J. Kearns and Umesh V. Vazirani.  _Computational Learning Theory_.  MIT Press, 1994.
  * Khardon (1999) Roni Khardon.  Learning action strategies for planning domains.  _Artificial Intelligence_ , 113:125–148, 1999.
  * Konidaris et al. (2018) George Konidaris, Leslie Pack Kaelbling, and Tomás Lozano-Perez.  From skills to symbols: Learning symbolic representations for abstract high-level planning.  _Journal of Artificial Intelligence Research_ , 61:215–289, 2018.
  * Liberman et al. (2022) Andrés Occhipinti Liberman, Hector Geffner, and Blai Bonet.  Learning first-order symbolic planning representations that are grounded.  In _ICAPS Workshop on Bridging the Gap Between AI Planning and Reinforcement Learning_ , 2022.
  * Lifschitz (1999) Vladimir Lifschitz.  Action languages, answer sets, and planning.  In _The Logic Programming Paradigm_ , pages 357–373. Springer, 1999\.
  * Lipovetzky and Geffner (2012) Nir Lipovetzky and Hector Geffner.  Width and serialization of classical planning problems.  In _Proc. ECAI_ , pages 540–545, 2012.
  * Manhaeve et al. (2021) Robin Manhaeve, Sebastijan Dumančić, Angelika Kimmig, Thomas Demeester, and Luc De Raedt.  Neural probabilistic logic programming in deepproblog.  _Artificial Intelligence_ , 298:103504, 2021.
  * Martín and Geffner (2000) Mario Martín and Hector Geffner.  Learning generalized policies from planning examples using concept languages.  In _Proc. KR_ , 2000.
  * McCarthy (1987) John McCarthy.  Generality in artificial intelligence.  _Communications of the ACM_ , 30(12):1030–1035, 1987.
  * Pearl (2009) Judea Pearl.  _Causality_.  Cambridge University press, 2009.
  * Pearl and Mackenzie (2018) Judea Pearl and Dana Mackenzie.  _The book of why: the new science of cause and effect_.  Basic books, 2018.
  * Rodriguez et al. (2021) Ivan D Rodriguez, Blai Bonet, Javier Romero, and Hector Geffner.  Learning first-order representations for planning from black-box states: New results.  In _KR_ , 2021.  arXiv preprint arXiv:2105.10830.
  * Sanner (2011) Scott Sanner.  Relational dynamic influence diagram language (RDDL), 2011.  https://users.cecs.anu.edu.au/ ssanner/IPPC_2011/RDDL.pdf.
  * Schölkopf and von Kügelgen (2022) Bernhard Schölkopf and Julius von Kügelgen.  From statistical to causal learning.  In _Proc. of the International Congress of Mathematicians_ , 2022\.
  * Schölkopf et al. (2021) Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio.  Toward causal representation learning.  _Proceedings of the IEEE_ , 109(5):612–634, 2021\.
  * Shanahan et al. (2020) Murray Shanahan, Kyriacos Nikiforou, Antonia Creswell, Christos Kaplanis, David Barrett, and Marta Garnelo.  An explicitly relational neural network architecture.  In _International Conference on Machine Learning_ , pages 8593–8603, 2020.
  * Skryagin et al. (2021) Arseny Skryagin, Wolfgang Stammer, Daniel Ochs, Devendra Singh Dhami, and Kristian Kersting.  Slash: Embracing probabilistic circuits into neural answer set programming.  _arXiv preprint arXiv:2110.03395_ , 2021.
  * Sonar et al. (2021) Anoopkumar Sonar, Vincent Pacelli, and Anirudha Majumdar.  Invariant policy optimization: Towards stronger generalization in reinforcement learning.  In _Learning for Dynamics and Control_ , pages 21–33, 2021.
  * Stählberg et al. (2022a) Simon Stählberg, Blai Bonet, and Hector Geffner.  Learning general optimal policies with graph neural networks: Expressive power, transparency, and limits.  In _Proc. ICAPS_ , 2022a.
  * Stählberg et al. (2022b) Simon Stählberg, Blai Bonet, and Hector Geffner.  Learning generalized policies without supervision using graph neural networks.  In _Proc. KR_ , 2022b.
  * Toyer et al. (2020) Sam Toyer, Sylvie Thiébaux, Felipe Trevizan, and Lexing Xie.  Asnets: Deep learning for generalised planning.  _Journal of Artificial Intelligence Research_ , 68:1–68, 2020.
  * Wong et al. (2021) Catherine Wong, Kevin M Ellis, Joshua Tenenbaum, and Jacob Andreas.  Leveraging language to learn program abstractions and search heuristics.  In _International Conference on Machine Learning_ , pages 11193–11204, 2021.
  * Xie et al. (2021) Yiheng Xie, Mingxuan Li, Shangqun Yu, and Michael Littman.  Learning generalizable behavior via visual rewrite rules.  _arXiv preprint arXiv:2112.05218_ , 2021.
  * Yang et al. (2020) Zhun Yang, Adam Ishay, and Joohyung Lee.  Neurasp: Embracing neural networks into answer set programming.  In _Proc. IJCAI_ , 2020.
  * Younes et al. (2005) Häkan LS Younes, Michael L Littman, David Weissman, and John Asmuth.  The first probabilistic track of the international planning competition.  _Journal of Artificial Intelligence Research_ , 24:851–887, 2005.
  * Zhang et al. (2020) Amy Zhang, Clare Lyle, Shagun Sodhani, Angelos Filos, Marta Kwiatkowska, Joelle Pineau, Yarin Gal, and Doina Precup.  Invariant causal prediction for block mdps.  In _International Conference on Machine Learning_ , pages 11214–11224, 2020.
  * Zheng et al. (2020) Zeyu Zheng, Junhyuk Oh, Matteo Hessel, Zhongwen Xu, Manuel Kroiss, Hado Van Hasselt, David Silver, and Satinder Singh.  What can learned intrinsic rewards capture?  In _International Conference on Machine Learning_ , pages 11436–11446, 2020.