ifaamas [AAMAS ’24]Proc. of the 23rd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2024)May 6 – 10, 2024 Auckland, New
ZealandN. Alechina, V. Dignum, M. Dastani, J.S. Sichman (eds.) 2024 2024 588
Vrije Universiteit Amsterdam Amsterdam The Netherlands University of Twente
Enschede The Netherlands IvI and ILLC, University of Amsterdam Amsterdam The
Netherlands LIACS, Leiden University Leiden The Netherlands

# CORE: Towards Scalable and Efficient Causal Discovery with Reinforcement
Learning

Andreas Sauter<EMAIL_ADDRESS>,  Nicolò Botteghi<EMAIL_ADDRESS>,
Erman Acar<EMAIL_ADDRESS>and  Aske Plaat<EMAIL_ADDRESS>
###### Abstract.

Causal discovery is the challenging task of inferring causal structure from
data. Motivated by Pearl’s Causal Hierarchy (PCH), which tells us that passive
observations alone are not enough to distinguish correlation from causation,
there has been a recent push to incorporate interventions into machine
learning research. Reinforcement learning provides a convenient framework for
such an active approach to learning. This paper presents CORE, a deep
reinforcement learning-based approach for causal discovery and intervention
planning. CORE learns to sequentially reconstruct causal graphs from data
while learning to perform informative interventions. Our results demonstrate
that CORE generalizes to unseen graphs and efficiently uncovers causal
structures. Furthermore, CORE scales to larger graphs with up to 10 variables
and outperforms existing approaches in structure estimation accuracy and
sample efficiency. All relevant code and supplementary material can be found
at https://github.com/sa-and/CORE.

###### Key words and phrases:

Causal Discovery, Reinforcement Learning

###### Key words and phrases:

Causal Discovery Reinforcement Learning

##  1\. Introduction and Related Work

Causal discovery (CD) is the challenging task of inferring causal structure
from data Glymour et al. (2019); Vowels et al. (2023). Traditional approaches
to causal discovery consider data from purely observational distributions.
These are approaches such as constraint-based ones Spirtes et al. (2000);
Hyttinen et al. (2014), score-based ones Chickering (2003), and more recently
continuous optimization-based ones Zheng et al. (2018); Yu et al. (2019).

Pearl’s Causal Hierarchy (PCH) asserts that distinguishing between mere
correlations and genuine causal relationships requires the integration of
interventions in general Bareinboim et al. (2022). As a response to this
requirement, there has been a recent push to incorporate interventions into
causal discovery research Mooij et al. (2020); Hauser and Ch (2012) including
machine learning Brouillard et al. (2020); Lippe et al. (2021); Sauter et al.
(2023), among others.

Reinforcement learning (RL) learns an optimal policy for sequential decision
problems through interactions Sutton and Barto (2018). Therefore, RL is a
promising framework for using interventions to investigate causal
relationships. In particular, RL plays a dual role in the realm of causal
discovery - it can be used not only to recover the causal structure of an
environment Zhu et al. (2019), but also to learn causal discovery algorithms
Sauter et al. (2023), thus representing a versatile tool for CD.

In particular, RL has also been used to search the space of causal structures
more efficiently based on a fixed dataset Zhu et al. (2019); Wang et al.
(2021) with the possibility of incorporating prior knowledge (Hasan and Gani,
2022). Similarly, work on RL-related GFlow Nets (Bengio et al., 2023) has been
deployed to generate good estimates of the true causal structure (Deleu et
al., 2022; Li et al., 2022). Furthermore, many integrations of RL with causal
concepts have been investigated that restrict their CD process to supervised
learning (Nair et al., 2019; Ton et al., 2021; Méndez-Molina et al., 2022; Lei
et al., 2022; Feng et al., 2022). In addition to that, RL has also been used
to learn policies that choose the best interventions to do for CD (Amirinezhad
et al., 2022; Scherrer et al., 2022; Tigas et al., 2022).

Although causal discovery has seen substantial progress with these works over
the years, leading to a multitude of methodologies, challenges persist in
areas such as scalability, generalization, and planning of interventions. In
this context, this paper introduces CORE (Causal DiscOvery with REinforcement
Learning), a deep-RL-based algorithm designed for the task of learning a CD
policy. CORE can learn a policy that sequentially reconstructs causal graphs
from both observational and interventional data, while simultaneously
performing informative interventions. This dual learning paradigm allows CORE
not only to uncover causal structures efficiently, but also to identify
interventions that enhance its causal models. The following lists our main
contributions:

  * •

We formalize the task of learning a CD algorithm as a partially observable
Markov decision process (POMDP).

  * •

We propose a dual Q-learning setup to learn intervention design and structure
estimation simultaneously.

  * •

We demonstrate that CORE can be successfully applied for causal discovery to
previously unseen graphs of sizes of up to 10 variables.

In addition to those, we show the importance of jointly learning which
interventions to perform and graph generation, and investigate the limitations
of our approach regarding the applicability to the real world.

The most distinctive feature of CORE is that it does not impose a specific
algorithm for identifying causal models, but rather attempts to learn it.
Among others, this can have positive effects on efficiency and transferability
to new problem instances. While MCD Sauter et al. (2023) and AVICI Lorch et
al. (2022) solve the same task, they run into pitfalls that hinder their
application to realistic graph sizes or rely on offline data, respectively. We
set steps to overcome these pitfalls by imposing additional structure on our
policy, more efficient rewards, and learning to actively perform relevant
interventions.

Our results show robust generalization to unseen graphs and the capability to
scale to scenarios with up to ten variables, a step forward over the state of
the art, and a crucial advancement towards addressing real-world complexities.
The subsequent sections delve into the intricacies of CORE’s architecture, its
training methodologies, and empirical validations.

##  2\. Preliminaries and Notation

In this section, we establish the necessary notation and provide an overview
of key concepts and techniques used in the field of causal discovery with
interventions and reinforcement learning.

###  2.1. Causal Models

Causal relations are often formalized through a _structural causal model_
(SCM) which is a tuple $M=(\mathcal{X},\mathcal{F},\mathcal{U},\mathcal{P})$
with a set of endogenous (random) variables (i.e., relevant variables for the
problem) $\mathcal{X}=\\{X_{1},\ldots,X_{n}\\}$,
$\mathcal{U}=\\{U_{1},\ldots,U_{n}\\}$ a set of exogenous (random) variables
(often also called unobservable or noise variables),
$\mathcal{F}=\\{f_{1},\ldots,f_{n}\\}$ the set of functions (also called
_structural equations_) whose elements are in the form of $X_{i}\leftarrow
f_{i}(Pa(X_{i}),U_{i})$ where
$Pa(X_{i})\subseteq\mathcal{X}\backslash\\{X_{i}\\}$ stands for endogenous
parent variables of $X_{i}$, and $\mathcal{P}=\\{P_{1},...,P_{n}\\}$ the set
of pairwise independent probability distributions defined over $\mathcal{U}$
with $U_{i}\sim P_{i}$.

Interpreting variables as nodes and the functional dependency between
variables as directed edges, every SCM $M$ induces a directed graph structure
$G$, which we will call the corresponding causal graph. Directed edges
represent direct causation from parent nodes to child nodes, hence absence of
edges is as important as present edges. For the sake of simplicity, we shall
follow the common assumption that no variable is its own cause i.e., there is
no circular functional dependency, hence the induced causal graph is always a
directed acyclic graph (DAG). Furthermore, each SCM $M$ induces a joint
distribution $P_{M}(\mathcal{X})$ over its endogenous variables, whose
structural properties inherited from the corresponding induced graph $G$
satisfy the Markov condition. That is, each $X_{i}$ is independent of its non-
descendants, given its parents $Pa(X_{i}$). Along with the independence of the
noise variables, this condition implies the following factorization Pearl
(2009):

$P_{M}(\mathcal{X})=\prod_{X_{i}\in\mathcal{X}}P(X_{i}|Pa(X_{i}))$ (1)

We shall refer to this distribution as _observational distribution_.

Note that SCMs are generative models, i.e., we can sample values for
$\mathcal{X}$ from them. We can sample the exogenous variables from
$\mathcal{P}$ and determine the values of endogenous variables according to
their functions in $\mathcal{F}$. This procedure effectively corresponds to
sampling from the joint distribution over endogenous variables Pearl (2009).

###  2.2. Interventions

Interventions play a crucial role in causal discovery, allowing us to
investigate causal relationships by actively manipulating variables in a
system. In general, imposed by Pearl’s causal hierarchy Bareinboim et al.
(2022), interventions are necessary to distinguish causation from correlation,
and eventually to reason about causal effects.

Formally, an _intervention_ on a variable $X$ changes the variable’s value to
$x$ (an arbitrary but fixed value), independently of $X$’s actual causes. Then
$X$ is called the _intervention target_. Effectively, at the graph level,
intervening on a variable $X$, removes all the edges incoming to $X$,
resulting in $Pa(X)=\emptyset$. This operation is the so-called _do-operation_
(denoted as $do(X=x)$), and allows us to distinguish the causal effect of
variable $X$ on variable(s) $Y$ from the confounding influence of common
parents of $X$ and $Y$ (Figure 1).

Figure 1. A simple graphical illustration of a (hard) intervention. Given the
causal graph $G$ with endogenous variables $\mathcal{X}=\\{X,Y,Z\\}$ and the
corresponding noise variables $\mathcal{U}=\\{U_{X},U_{Y},U_{Z}\\}$,
intervening on variable $X$ (i.e., $do(X=x)$) results in modifying $G$ into
$G^{\prime}$ by pruning the incoming edges to node $X$ and assigning the value
$x$.

In an SCM, intervening on a variable $X$ implies that the corresponding
structural equation $f_{X}\in\mathcal{F}$ is replaced by $X\leftarrow x$,
resulting in a modified SCM $M^{\prime}$. Therefore, an intervention affects
the distribution of the intervention target, since:

$P_{M^{\prime}}(X|Pa(X))=P_{M^{\prime}}(X|\emptyset)=P_{M^{\prime}}(X)=\delta_{x}$
(2)

where $\delta_{x}$ is the probability density function that has all mass on
$x$. Put differently, an intervention replaces the factor associated with the
intervened variable. We refer to the resulting joint distribution

$P_{M}(\mathcal{X}|do(X=x))=\prod_{X_{i}\in\mathcal{X}\setminus\\{X\\}}P_{M}(X_{i}|Pa(X_{i}))\cdot
P_{M^{\prime}}(X=x)$ (3)

as _post-interventional_ distribution. To simplify the notation, we will
sometimes use $P_{M_{do(X=x)}}(\mathcal{X})$ or $P_{M_{do(X)}}(\mathcal{X})$
to refer to the expression $P_{M}(\mathcal{X}|do(X=x))$ when the target
variable or $x$ is clear from the context.

###  2.3. Reinforcement Learning

Reinforcement learning (RL) is a general approach to learning through
interaction with the world Sutton and Barto (2018), especially in sequential
decision problems. An RL agent aims to find the sequence of actions that
maximize the expected return, i.e., the cumulative (discounted) _reward_. How
the RL agent selects its actions only relies on (possibly indirect) measures
of how the world changes after each action is taken.

##### POMDP

In reinforcement learning problems, the relationship between an agent and the
environment in which the states are not fully observable is often modeled as a
Partially Observable Markov Decision Process (POMDP). Formally, a POMDP is a
tuple $(\mathcal{S,A,T,R},\Omega,\mathcal{O},\gamma)$ where $\mathcal{S}$ is a
set of states, $\mathcal{A}$ is a set of actions,
$\mathcal{T}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\longrightarrow[0,1]$
is a set of transition probabilities between states,
$\mathcal{R}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is the reward
function, $\Omega$ is a set of observations,
$\mathcal{O}:\mathcal{S}\times\mathcal{A}\times\Omega\rightarrow[0,1]$ is the
set of conditional observation probabilities, and $\gamma\in[0,1)$ is the
discount factor.

##### RL:

The strategy of actions of an RL agent is called _policy_. A policy can be
either deterministic or stochastic. A deterministic policy
$\pi:\mathcal{S}\longrightarrow\mathcal{A}$ maps states to an action, whereas
a stochastic policy $\pi:\mathcal{S}\times\mathcal{A}\longrightarrow[0,1]$ is
characterized by a conditional distribution of actions given states. To
maximize the return in the long run, RL agents often estimate the so-called
_value_ function $V:\mathcal{S}\longrightarrow\mathbb{R}$ or _action value_
function $Q:\mathcal{S}\times\mathcal{A}\longrightarrow\mathbb{R}$. These
functions determine the desirability of a state or a state-action pair,
respectively. The optimal Q-function $Q^{*}$ allows us to derive an optimal
policy $\pi^{*}$ that maximizes the return by greedily choosing the action
that maximizes the value of each state, that is,
$\pi^{*}(s)=\mathrm{argmax}_{a}Q^{*}(s,a)$ Sutton and Barto (2018).

##### Deep Q-Learning:

The Q-learning algorithm Watkins and Dayan (1992) estimates the state-action
value function $Q$ using the  temporal difference (TD). In particular, TD
learning decomposes the problem of estimating the expected return of a given
policy as the sum of the instantaneous reward and the value accumulated by
following the optimal policy in the next step:

$Q(s,a)=r(s,a)+\gamma\mathrm{max}_{a^{\prime}}Q(s^{\prime},a^{\prime})$ (4)

where $r(s,a)$ is the instantaneous reward of the state-action pair. To
estimate the future reward, we assume that the agent follows the optimal
policy $\pi^{*}(s)$, i.e., $\mathrm{argmax}_{a}Q^{*}(s,a)$. Especially in the
first iterations of the algorithm, the estimate of $Q$ does not correspond to
the optimal value function $Q^{*}$. However, tabular Q-learning can still
converge to the optimal solution Watkins and Dayan (1992). The _deep Q-network
(DQN)_ algorithm Mnih et al. (2015) adapts the Q-learning algorithm to non-
tabular settings, e.g., continuous state spaces, where the Q-function needs to
be approximated via a neural network. DQN utilizes the TD-learning rule to
generate a target for the training of the neural network that approximates the
Q-value by means of the loss function:

$\mathcal{L}(\theta)=\mathbb{E}_{s,a,r,s^{\prime}}[(r(s,a)+\gamma\mathrm{max}_{a^{\prime}}Q(s^{\prime},a^{\prime};\theta^{-})-Q(s,a;\theta))^{2}]$
(5)

where $Q(s,a;\theta)$ is the Q-function approximated by the neural network of
parameters $\theta$, while $Q(s,a;\theta^{-})$ is the so-called target
network, used to generate a fixed target and stabilize the training dynamics,
and $\gamma$ is the discount factor.

##  3\. Learning a Causal Discovery Policy with Informative Interventions

Figure 2. Overview of COREs training setup (right) and a minimal example of
the transition dynamics for an SCM with two endogenous variables (left). At
each step, the agent picks the intervention/structural actions according to an
$\epsilon$-greedy policy on $Q_{in}$ and $Q_{st}$ respectively. The
intervention is applied to the SCM $M^{i}$ leading to a post-interventional
distribution $P_{M_{do(.)}}$ from which an observation is sampled. The agent
receives a reward based on the structure action and the induced graph of
$M_{do(\emptyset)}^{i}$. The observation is added to the history of
observations and serves as input to the agent. At the beginning of each
episode a new $M^{j}$ is drawn from the training set and the observation
history is cleared.

In this section, we present our algorithmic setup for learning causal
discovery policies. We consider the classic agent-environment interaction
scheme commonly used in RL. The goal is to learn a policy that represents a CD
algorithm that uses observational and interventional data to sequentially
estimate the true causal structures by performing informative interventions.
Such modules can be applied to previously unseen causal structures through a
few forward passes of a neural network without retraining, making them a
highly efficient tool for causality Lorch et al. (2022); Sauter et al. (2023).

Following this line of research, we learn a policy that collects a stream of
data by intervening on the environment to infer a causal structure estimate.
This setup acknowledges the strong influence that informative interventions
have, especially when there is a limited budget for interventions. We learn to
perform these interventions by rewarding interventions that lead to the
generation of a better structural update and limiting the budget for
interventions by means of possible steps in an episode.

One key aspect of learned CD modules is that they need information about the
ground truth causal structure only during training. This promises the
possibility of (i) training the CD policy on synthetic data where the ground
truth can easily be generated, and then (ii) applying it to estimate the
causal structure of environments where the ground truth structure is
potentially unknown, such as in the real world.

###  3.1. POMDP Formulation of Causal Discovery Through Interventions

To conveniently model the causal discovery process where there is partial
observability, we will use a POMDP. However, since such a formalization is not
entirely obvious, it constitutes our first contribution, which we will present
in this section.

##### State Space:

Our environment is determined by SCMs.111Our approach can be applied to any
data-generating process that allows for sampling from and intervening on its
variables. Therefore, each state will correspond to an SCM. We shall describe
each SCM as the set of functions that determine the endogenous variables.
Therefore, having $n$ endogenous variables, a state is a set
$s=\\{f_{0},...,f_{n-1}\\}$ of functions that define the current SCM.
Furthermore, each state contains the ground truth observational graph
$G^{*}_{s}$ induced by the observational SCM $M_{do(\emptyset)}$.

##### Action Space:

We model our action space as a multi-discrete space $A=\leavevmode\nobreak\
[n+1]\leavevmode\nobreak\ \times\leavevmode\nobreak\ [2n(n-1)+1]$ where the
notation $[n]=\\{1,2,\ldots,n\\}$ with $n$ being the number of nodes in the
graph. The first dimension of the action space represents the endogenous
variables of the current SCM and determines the _intervention targets_. For
each variable $X_{i}\in\mathcal{X}$, there is an action $do(X_{i}=c)$, where
$c$ is a predefined constant. In addition, the agent can do _nothing_ and just
collect observational data. In total, this dimension of the action space has
$n+1$ elements. The second dimension represents the _structural actions_. Each
action in this space indexes the removal and addition of edges on the
currently estimated graph. Additionally, the agent can perform a _void_
structural update which leads to a total size of $2n(n-1)+1$ actions in this
dimension since we disallow reflective edges. The action space scales
quadratically with the number of nodes. To address this problem, we mask the
possible actions at every step such that the agent cannot add an already
existing edge or remove a non-existing edge. This effectively halves the size
of this action space dimension.

##### Transition Dynamics:

Each episode starts in the observational SCM $M_{do(\emptyset)}$ where no
intervention is performed. An intervention $do(X_{i})$ on this SCM
deterministically leads to a new SCM $M_{do(X_{i})}$ where $f_{i}$ is replaced
by some constant $c$. This effectively replaces $f_{i}$ in the state. With an
intervention $do(X_{j})$, we transition from $M_{do(X_{i})}$ to
$M_{do(X_{j})}$, that is, $T(M_{do(X_{i})},do(X_{j}),M_{do(X_{j})})=1$ or,
equivalently, $T(M_{do(X_{i})},do(X_{j}))=M_{do(X_{j})}$. A minimal example of
the transition dynamics of our approach can be seen in Figure 2.

##### Observations:

At each step $t$, the agent collects the value of the endogenous variables
$\\{x_{0},\ldots,x_{n-1}\\}$ from the joint distribution
$P_{M_{do(X)}}(\mathcal{X})$ induced by the current SCM $M_{do(X)}$.
Therefore, the observation is $o_{t}\sim P_{M_{do(X)}}(\mathcal{X})$.

##### State Representation:

The use of a single observation $o_{t}$ is not sufficient to determine the
best action in POMDPs. Thus, the agent has to build its own state
representation $h_{t}$ using the history of observations and actions Sutton
and Barto (2018). We denote the history of observations and actions by
$h_{t}=[x_{0},a_{0},...,x_{t},a_{t}]$.

##### Reward:

The structural Hamming distance (SHD) measures the distance between two DAGs
by counting the number of different edges. Since our goal is to minimize the
distance between the generated and the ground truth observational graphs at
every step, we consider the SHD as a natural candidate for our reward
function. For a ground truth observational graph $G^{*}_{s}$, a graph estimate
$\hat{G}_{t}$, and a graph estimate $\hat{G}_{t^{\prime}}$ in the consecutive
step $t^{\prime}$, we define the potential-based reward Jenner et al. (2022)
as $r(s,a)=SHD(G^{*}_{s},\hat{G}_{t})-SHD(G^{*}_{s},\hat{G}_{t^{\prime}})$.

To simplify, we rewrite our reward function in the following way: Let $E(a)$
be the directed edge that is manipulated in action $a$. Then, when adding an
edge $E(a)$, our reward becomes:

$r(s,a)=\begin{cases}1&\text{if }E(a)\in G_{s}^{*}\\\ -1&\text{if }E(a)\not\in
G_{s}^{*}\\\ \end{cases}$ (6)

When removing an edge $E(a)$ our reward becomes $-r(s,a)$. In all other cases
($E(a)=\emptyset$) the reward is $0$.

This formulation has the computational advantage that only $E(a)$ must be
compared to the edges of $G_{s}^{*}$ instead of comparing the entire graph
$\hat{G}_{s^{\prime}}$. Furthermore, it makes the reward denser and depends
only on $s$ and $a$ instead of relying on the entire history of structural
actions that make up the current graph estimate. In Appendix A we demonstrate
that this formulation is equivalent to
$SHD(G^{*}_{s},\hat{G}_{s})-SHD(G^{*}_{s},\hat{G}_{s^{\prime}})$.

###  3.2. Data-Generation

We train our CORE agents using a training set of DAGs. In addition, we have an
evaluation set of DAGs that the agent has not seen during training. To ensure
that the evaluation set does not include any graphs from the training set, we
first create a set of unique DAGs, shuffle it to ensure equal sparsity
throughout the list, and then divide it into training and evaluation sets. As
per common assumption in machine learning, we assume that having more graphs
in the training set will help us to generalize better to the evaluation set.

Since the space of DAGs grows superexponentially in the number of its nodes,
it quickly becomes infeasible to generate all possible graph structures with
$n$ nodes. For this reason, we generate all possible graphs only for graphs
with 3 nodes (for a total of 25 graphs) and graphs with 4 nodes (for a total
of 543 graphs). For graphs with more than 4 nodes, we generate subsets of the
possible graphs. Similarly to many works in the literature, each graph is
generated as an Erdös-Rényi Erdós and Rényi (1959) graph with an edge
probability of 0.2. We diversify the training data by generating SCMs based on
these graphs by sampling a function $f_{i}(Pa_{G}(X_{i}))$ from a class of
possible functions for every node $X_{i}$ in the graph $G$ at the beginning of
each episode.

| 3 variables | 4 variables | 5 variables | 8 variables | 10 variables
---|---|---|---|---|---
random | $3.29\pm 0.97$ | $5.92\pm 1.41$ | $8.33\pm 1.22$ | $11.08\pm 2.80$ | $14.85\pm 4.01$
empty | $1.80\pm 0.90$ | $3.80\pm 1.10$ | $6.20\pm 0.42$ | $5.10\pm 1.60$ | $7.0\pm 2.50$
MCD | $1.85\pm 1.10$ | $4.97\pm 1.61$ | $6.18\pm 0.44$ | - | -
CORE | $0.50\pm 0.50$ | $0.54\pm 0.65$ | $1.26\pm 1.06$ | $2.04\pm 1.64$ | $5.16\pm 2.69$
Table 1. Average SHDs on the test set of SCMs with unseen causal structures.

###  3.3. Learning Approach

The CORE agent is based on the DQN algorithm Mnih et al. (2015), but it
maintains two multilayer perceptron Q networks simultaneously. One network,
$Q_{st}(h,a_{st};\Theta_{st})$, estimates the Q-values specific to the
structural updates, the other $Q_{in}(h,a_{in};\Theta_{in})$ maintains the
values for the interventions. Each of the two networks comes with its own
target network, and the loss is computed separately. Note that Q values are
determined on the basis of the history of observations, as is often done when
applying DQN to POMDP problems Mnih et al. (2015). The networks are identical
except for the output layers due to different dimensionalities of the action
space. The overall output of the Q-function is the concatenation of the
individual Q-values, and our greedy policy picks $a_{in}$ and $a_{st}$ in such
a way that the corresponding Q-values are maximized.

At the procedural level, our algorithm generates a new SCM based on a random
sample of the graph data at the beginning of each episode. Furthermore, we
start every episode with an empty graph estimate. The inference time for a
given SCM is fully determined by the fixed number of steps per episode. This
puts a hard upper bound on the number of samples and makes inference highly
efficient. Figure 2 gives an overview of our agent.

##  4\. Generalization to Unseen Structures

In this section, we empirically validate whether our learned policy
constitutes a good causal discovery algorithm. To this end, we train our model
on a training set of SCMs with known causal structures and evaluate it on SCMs
with causal structures that were not seen during training.

###  4.1. Training Data

For this experiment, we generate graphs with 3, 4, 5, 8, and 10 variables as
described in Section 3.2. We split the generated graphs into training and test
sets as follows: We first generate the graphs (25, 543, 16000, 91000, 101000),
and then split the final list into train and test sets with splits 19/6,
401/142, 15000/1000, 90000/1000, 100000/1000 for 3, 4, 5, 8 and 10 variables,
respectively. We limit the number of test graphs to 1000 since the evaluation
would otherwise slow down the training prohibitively.

At the beginning of each episode, a graph is sampled from the data set. To
generate the SCMs in accordance with Section 3.2, we define a class of linear
additive functions. For each node $X_{i}$ in the graph $G$, we sample $\mid
Pa_{G}(X_{i})\mid$ weights from $Uniform(0.5,2.0)$. The generated function for
this node is then $X_{i}\leftarrow\Sigma_{X_{j}\in Pa(X_{i})}w_{j}\cdot x_{j}$
for the current values $x_{j}$ of the parents of $X_{i}$. If $X_{i}$ is a root
node, we assign a default value of 0. We use an intervention value of 20 to
provide a strong signal about the causal structure w.r.t. to the true causal
effect sizes. This value can be considered as a hyperparameter and we discuss
its impact further in Section 6.

###  4.2. Experimental Setup

We evaluate the generalization capability of CORE w.r.t. the available
baselines. While AVICI Lorch et al. (2022) learns a graph generator that
estimates the causal structure of an offline dataset, CORE operates in a few-
shot online data sample regime. Therefore, a meaningful comparison with AVICI
is out of reach. Consequently, MCD Sauter et al. (2023) is, to the best of our
knowledge, the only SOTA method that learns a CD algorithm that actively
intervenes. Furthermore, we compare with the _random_ baseline that generates
random DAGs, and the _empty_ baseline which represents the empty graph.

We train both MCD and our approach for the same amount of steps and align all
relevant hyperparameters including the neural network sizes. MCD runs into
difficulties when scaling up to graphs with more than 4 nodes. Due to such
computational infeasibility, we cannot run experiments for MCD on SCMs with 8
or 10 variables. A detailed description of the hyperparameters and the
architectures used can be found in Appendix B. We set a maximum compute budget
via a timeout of 25 training hours. The precise hardware configuration can be
found in Appendix C. We paid special attention to setting comparable episode
lengths for both approaches. For the sake of fair comparison, we set the
episode length of our approach to half the episode length used in MCD, since
our approach can perform interventions and structure updates synchronously,
while MCD can only perform them sequentially.

###  4.3. Results

Figure 3. Two examples of how the learned CORE policy estimates the causal
structure of two unseen SCMs described in Equations (7) and (8). Green
elements indicate intervention (do (c = 20)) and structural update (adding an
edge) in the current step, respectively. The red arrow indicates the deletion
of an edge.

The results in Table 1 are from applying the learned models to three SCMs
randomly generated for each graph in the held-out test set. The model that
achieved the best performance during training was chosen for each evaluation.

We can see the favorable performance of CORE compared to MCD and the trivial
baselines. For all sizes of graphs tested, we observe that our approach
estimates graphs that are closer to the ground-truth structures than the other
approaches in less than 34 milliseconds per graph. We generate an average of
0.5, 0.5, 1.3, 2.0, and 5.2 wrong edges in graphs with 3, 4, 5, 8, and 10
nodes, respectively. Even in a set of graphs with 10 variables, our approach
adds approximately 2 correct edges out of 90 potential edges while only
observing 15 data points. For smaller graphs, the ratio of correctly
identified edges is even higher.

We attribute the improvement over MCD to a variety of aspects. First,
addressing the structural actions and the intervention actions with separate
networks makes learning the corresponding Q-functions more efficient. This is
because two separate networks have a greater degree of freedom to represent
structural and intervention actions that are inherently different. Second,
representing the reward densely instead of a summary at the end of each
episode often improves performance Ng et al. (1999). Third, instead of
learning to integrate observations from the environment via a long short-term
memory (LSTM) Hochreiter and Schmidhuber (1997), we directly input the history
of samples into our policy. And, lastly, by not generating graphs at runtime,
but rather having a pre-defined training set, we avoid a significant
computational overhead.

Furthermore, we observe the rather unfavorable performance of MCD compared to
the baselines. We partly attribute this to a lack of extensive hyperparameter
tuning, since this would likely have been needed to achieve the results in
Sauter et al. (2023). For the 4 and 5 variable cases, MCD reached the timeout
of 25 hours.

Given these results, we conclude that CORE is capable of successfully learning
a CD algorithm that can be applied to previously unseen causal structures.
Even for these cases, our approach estimates the ground truth graph accurately
without having to retrain on the new structure. Furthermore, we show that with
CORE’s novelties, we are able to scale towards graph sizes of more relevance
for real-world applications, while simultaneously increasing training
efficiency.

###  4.4. Examples

We present qualitative results on how our learned policy performs on the
following two randomly selected example SCMs with unseen causal structures:

$M_{do(\emptyset)}^{0}=\begin{cases}X_{0}\leftarrow 0.54\cdot X_{1}+0.91\cdot
X_{3}+0.83\cdot X_{4},\\\ X_{1}\leftarrow 1.52\cdot X_{2}+1.84\cdot X_{3},\\\
X_{2}\leftarrow 1.38\cdot X_{3},\\\ X_{3}\leftarrow 0,\quad X_{4}\leftarrow
0\\\ \end{cases}$ (7) $M_{do(\emptyset)}^{1}=\begin{cases}X_{0}\leftarrow
0,\\\ X_{1}\leftarrow 1.61\cdot X_{3},\\\ X_{2}\leftarrow 0.83\cdot
X_{1}+1.60\cdot X_{3}+1.5\cdot X_{4},\\\ X_{3}\leftarrow 1.39\cdot X_{0},\\\
X_{4}\leftarrow 0.54\cdot X_{0},\\\ \end{cases}$ (8)

In Figure 3, we can see that in both cases the agent identifies the underlying
causal structure almost correctly, with the exception of the missing edge
$X_{3}\rightarrow X_{0}$ in the first instance. In the second instance, it
even recognizes an error and corrects it in Step 7.

##  5\. On the Importance of Jointly Learning an Intervention Policy

As described in Section 3, our method is designed to jointly learn a causal
graph generator and an intervention policy. In this section, we show that
learning an intervention policy, aimed at performing the interventions that
are most informative for CD, helps in learning a CD policy.

It is worth noting that our agent does not receive any specific reward that
represents the quality of the intervention performed in the environment.
Instead, the reward function depends only on the structural update of the
currently estimated causal structure (see Equation (6)). Since, for the full
identification of the causal structure, interventions are generally needed
Bareinboim et al. (2022), our agent has to learn to perform interventions to
update the estimate of the causal structure. Therefore, our agent receives
good rewards only if it performs interventions that are relevant to discover
the current causal structure.

Although it is clear that interventions, in general, are helpful for CD, we
argue that learning an intervention policy by measuring the usefulness for
structure identification helps the overall learning process. Especially when
the budget for performing interventions is very restrictive, as is the case in
many real-world applications, it is crucial to perform the interventions that
are most informative about the underlying causal structure Shanmugam et al.
(2015); Tigas et al. (2022). Which interventions are the most informative ones
depends on the causal structure that is currently being discovered. This
further motivates learning the intervention policy jointly with the structure
generation policy. In this section, we empirically show that there is in fact
a benefit in learning an intervention policy jointly with the CD policy.

###  5.1. Experimental Setup

To show the hypothesized performance gain, we compare the performance of the
agent that learns the intervention policy and the structure generation policy
jointly, to an agent that learns only the structure generation policy and
randomly picks an intervention target at each step. We train the two agents 3
times each on environments with 4 endogenous variables. The graphs, function
classes, and hyperparameters remain the same as described in Section 4.1.

###  5.2. Results

Figure 4 shows the aggregated results for the two types of agents.

Figure 4. Plot of the average SHD on the test set (lower is better). We
present the means over three training runs of CORE with random interventions
(blue) and when jointly learning an intervention policy (red) over graphs with
4 variables.

We can see that learning the intervention policy jointly with the CD policy
results in a significantly better estimation of the ground truth causal
structure. Additionally, it decreases the number of learning steps needed to
reach a certain level of performance. Lastly, Figure 4 suggests that even with
random interventions, our approach performs reasonably well (average SHD of
$\sim 2.3$). This indicates the robustness of the CORE agent to less
informative interventions.

Overall, we observe that the ability to learn the intervention policy is an
integral part of learning a CD policy and that rewarding interventions leading
to better structure estimates is sensible.

##  6\. Applicability to the Real-World

| 3 Variables | 4 Variables | 5 Variables
---|---|---|---
| lin | lin + noise | interaction | lin | lin + noise | interaction | lin | lin + noise | interaction
empty | $1.8\pm 0.9$ | $3.8\pm 1.1$ | $6.2\pm 0.4$
lin 5 | $0.2\pm 0.4$ | $1.2\pm 0.4$ | $2.2\pm 0.7$ | $0.6\pm 0.7$ | $0.8\pm 0.8$ | $3.4\pm 1.9$ | $1.4\pm 1.1$ | $1.8\pm 1.2$ | $6.1\pm 2.4$
lin 20 | $0.5\pm 0.5$ | $0.8\pm 0.4$ | $2.3\pm 0.5$ | $0.5\pm 0.7$ | $0.6\pm 0.6$ | $3.8\pm 1.8$ | $1.3\pm 1.1$ | $1.2\pm 1.0$ | $6.5\pm 2.2$
lin+noise 5 | $0.7\pm 0.7$ | $0.6\pm 0.7$ | $1.3\pm 0.7$ | $0.6\pm 0.7$ | $0.8\pm 0.8$ | $3.6\pm 2.0$ | $2.0\pm 1.3$ | $2.3\pm 1.3$ | $5.9\pm 2.1$
lin+noise 20 | $0.2\pm 0.4$ | $0.8\pm 0.4$ | $2.0\pm 0.8$ | $0.6\pm 0.6$ | $0.7\pm 0.7$ | $4.3\pm 1.7$ | $1.2\pm 1.0$ | $1.2\pm 1.0$ | $6.8\pm 2.2$
interaction 5 | $0.8\pm 0.7$ | $1.3\pm 0.7$ | $1.0\pm 0.5$ | $4.1\pm 1.3$ | $4.1\pm 1.3$ | $4.0\pm 1.3$ | $7.9\pm 1.7$ | $7.8\pm 1.7$ | $7.9\pm 1.7$
Table 2. We show the performance of trained CORE policies on unseen graphs
with various function classes for their corresponding SCMs. Each row describes
which function class the model was trained on and what intervention value it
uses. Each column describes the function class it was tested on. Empty
describes the baseline that generates the empty graph.

Throughout this work, we acknowledge the capability of learning CD algorithms
that can be applied to environments with previously unseen causal structures
with up to 10 variables. This constitutes a substantial improvement over the
SOTA when it comes to the application of learned CD algorithms in the real
world, as many problems can be modeled with 10 variables Zwitter and Soklic
(1988); Sachs et al. (2005). Therefore CORE, reaches graph sizes that are
relevant in CD. However, we acknowledge that many applications with up to 5000
variables Maathuis et al. (2010) are currently out of reach. In this section,
we shed light on some of the limitations that this approach currently has with
regard to applying it in a real-world scenario.

Here, we specifically investigate two design aspects that limit real-world
applicability, and they are interconnected. First, during training, the
functions of the SCMs are sampled from a specific function class, and for some
function classes (e.g., non-linear functions), discovering the true causal
structure can be harder than for others Glymour et al. (2019). Consequently,
as we will show in this section, learning a CD algorithm for these classes of
functions is more difficult.

Second, our approach is tailored to generate graph estimates for the function
class on which it was trained. This means that when used for different causal
structures, the same function class is expected during inference.
Consequently, this can lead to a decrease in performance if the function class
is altered. We expect an exception for this for function classes that are
either very similar to the training functions or that subsume them. Therefore,
when CORE is trained with the intention of being used in a real-world setting,
the real-world function class has to be anticipated during training.

###  6.1. Transferability across Noise and Non-Linearity

Motivated by these aspects, we show the difficulty in training CD policies on
some function classes and test CORE on function classes that it was not
trained on.

####  6.1.1. Experimental Setup

For the data-generating processes in this section, we test how noise and non-
linearities influence the performance and transferability of CORE. Therefore,
we use three function classes that define each function class
$f_{i}(Pa(X_{i}),U_{i})$ in an SCM as follows:

  * •

_linear:_ $f_{i}=\Sigma_{X_{j}\in Pa(X_{i})}w_{j}\cdot x_{j}$ (same as Section
4.1)

  * •

_linear + noise:_ $f_{i}=\Sigma_{X_{j}\in Pa(X_{i})}w_{j}\cdot x_{j}+u_{i}$,
where $u_{i}\sim\mathcal{N}(0,0.5)$

  * •

_interaction:_ $f_{i}=\Sigma_{X_{j}\in Pa(X_{i})}w_{j}\cdot x_{j}+x_{k}\cdot
x_{l}$, where $X_{j},X_{k}\in Pa(X_{i})$

where the lowercase $x_{i}$ represents the current value of the variable
$X_{i}$. Whenever a node is a root node, we set a default value of 0.

We train two CORE models for various graph sizes for each of the two linear
functions, one with an intervention value of 5 and the other with an
intervention value of 20. This setup gives us further insight into how the
signal-to-noise ratio affects our performance. For the interaction function,
we train one model with an intervention value of 5. We then tested all the
trained models in all three function classes.

####  6.1.2. Results

In Table 2, we show how models that were trained with one function class
perform when applied to various function classes with previously unseen causal
structures.

Our first observation is that, as hypothesized, the application of our learned
CD algorithm on previously unseen function classes is problematic if the
testing function class is very different from the training function class.
While applying the linear models to their noisy/non-noisy counterparts still
leads to good estimates, applying them to the interaction data mostly fails.
This supports our claim that the function class chosen for training must be
informative about the function class encountered during testing.

Looking at the model that was trained on interaction data, we observe two
interesting aspects. First, for graphs with 4 and 5 variables, CORE fails to
learn a CD policy that generalizes to unseen graphs. We believe that, given
the right hyperparameters and a sufficient training budget, we can solve the
task for larger graphs, based on the results obtained from smaller graphs.
However, these results demonstrate that the performance of a learned CD
algorithm depends on the complexity of the SCM function that generates the
data. Second, we observe that, for the interaction case, the learned policy
can be successfully applied to the linear function. We argue that this is
because the interaction data encompasses the linear data as well. This
suggests that if the function classes used during training are broad enough,
the CD algorithm that is learned will be relatively more applicable to real-
world scenarios.

When comparing linear models with a higher intervention value with those with
a lower intervention value, we observe that they tend to perform better on
function classes that they successfully learned. We attribute this to a higher
signal-to-noise ratio w.r.t. the data-generating process.

Overall, we can say that learning CD algorithms is limited by the function
class that is observed during training. This currently obstructs their
application to real-world scenarios, but finding more general functions on
which CORE can be trained is a promising research direction.

###  6.2. Further Limitations

Apart from aspects related to the function classes on which CORE is trained,
we point out the additional limitations of learning a model that is applicable
to the real world.

One of them is the assumption of being able to intervene on any variable with
any target value. In real-world scenarios, it might be that some variables
cannot be manipulated (imagine changing the outside temperature) or a good
target value is unknown during training. Furthermore, CORE-like algorithms
might suffer from the presence of unobserved confounders. For both the unknown
target value and unobserved confounders, there is hope that augmenting the
learning procedure in the future will overcome these limitations.

##  7\. Summary and Conclusion

In this paper, we introduce CORE, a deep RL-based approach to tackle the task
of causal discovery. CORE learns a policy to sequentially perform informative
interventions and generate candidate causal graphs from scratch. Moreover, the
learned policy generalizes to previously unseen graphs of up to 10 variables
in size. CORE outperforms the current SOTA baseline (i.e., MCD Sauter et al.
(2023)) both in the number of variables it can deal with and in the accuracy
of the estimated structure. Furthermore, it demonstrates that by learning to
perform the most informative interventions, highly sample-efficient CD
algorithms can be learned ($\sim 15$ data samples for 10 variables).

Such improvement can be attributed to several key design features. One such
feature is the imposed additional structure in the policy that separates the
networks for interventions and structural updates. However, such separation is
not completely isolated. As shown in our ablation study, CORE learns to
perform relevant interventions outperforming random interventions. Learning
which interventions are relevant is guided solely through a dense reward that
assesses the accuracy of the generated graph.

Moreover, we outlined the real-world applicability of our approach in terms of
the number of variables and generalizability across more complex function
classes. For the former, while the number of variables that CORE can deal with
matches some domains, for some other domains, usual practice is still out of
reach. For the latter, it turns out that CORE delivers good estimates when it
comes to linear functions, training on noisy functions, and testing on non-
noisy counterparts, and vice versa. However, generalizing to more complex
classes such as non-linear functions necessitates improvements. Furthermore,
we empirically confirmed that training on more complex function classes and
testing on simpler classes yields promising estimates. Such an observation can
serve as a key idea along the road of applying these methods to real-world
problems.

Future work includes investigating the limitations of our approach in the
presence of confounders, soft interventions, and determining the right target
value for interventions. In particular, it would be interesting to understand
how robust our approach is when it comes to different topologies regarding
such non-intervenable variables and unobservable confounders. Another avenue
that we plan to address is an extensive study of the transferability of our
approach across different function classes, such that learned CD algorithms
that autonomously plan interventions can be applied to real-world data.

We thank Frank van Harmelen for his valuable input throughout this project and
the anonymous reviews for helping to improve the final version of this work.
This research was partially funded by the Hybrid Intelligence Center, a
10-year programme funded by the Dutch Ministry of Education, Culture and
Science through the Netherlands Organisation for Scientific Research,
https://hybrid-intelligence-centre.nl, grant number 024.004.022

## References

  * (1)
  * Amirinezhad et al. (2022) Amir Amirinezhad, Saber Salehkaleybar, and Matin Hashemi. 2022.  Active learning of causal structures with deep reinforcement learning.  _Neural Networks_ 154 (10 2022), 22–30.  https://doi.org/10.1016/J.NEUNET.2022.06.028
  * Bal et al. (2016) Henri Bal, Dick Epema, Cees de Laat, Rob van Nieuwpoort, John Romein, Frank Seinstra, Cees Snoek, and Harry Wijshoff. 2016.  A Medium-Scale Distributed System for Computer Science Research: Infrastructure for the Long Term.  _Computer_ 49, 5 (5 2016), 54–63.  https://doi.org/10.1109/MC.2016.127
  * Bareinboim et al. (2022) Elias Bareinboim, Juan D. Correa, Duligur Ibeling, and Thomas Icard. 2022.  On Pearl’s Hierarchy and the Foundations of Causal Inference.  In _Probabilistic and Causal Inference_. ACM, New York, NY, USA, 507–556.  https://doi.org/10.1145/3501714.3501743
  * Bengio et al. (2023) Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward J Hu, Mo Tiwari, and Emmanuel Bengio. 2023.  GFlowNet Foundations.  _Journal of Machine Learning Research_ 24, 210 (2023), 1–55.  http://jmlr.org/papers/v24/22-0364.html
  * Brouillard et al. (2020) Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. 2020.  Differentiable Causal Discovery from Interventional Data. In _Advances in Neural Information Processing Systems_ , H Larochelle, M Ranzato, R Hadsell, M F Balcan, and H Lin (Eds.), Vol. 33. Curran Associates, Inc., 21865–21877.  https://proceedings.neurips.cc/paper_files/paper/2020/file/f8b7aa3a0d349d9562b424160ad18612-Paper.pdf
  * Chickering (2003) David Maxwell Chickering. 2003.  Optimal Structure Identification with Greedy Search.  _J. Mach. Learn. Res._ 3, null (3 2003), 507–554.  https://doi.org/10.1162/153244303321897717
  * Deleu et al. (2022) Tristan Deleu, António Góis, Chris Emezue, Mansi Rankawat, Simon Lacoste-Julien, Stefan Bauer, and Yoshua Bengio. 2022.  Bayesian structure learning with generative flow networks. In _Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence_ _(Proceedings of Machine Learning Research, Vol. 180)_ , James Cussens and Kun Zhang (Eds.). PMLR, 518–528.  https://proceedings.mlr.press/v180/deleu22a.html
  * Erdós and Rényi (1959) P. Erdós and A. Rényi. 1959.  On random graphs.  _Publicationes Mathematicae_ (1959), 290–297.
  * Feng et al. (2022) Fan Feng, Biwei Huang, Kun Zhang, and Sara Magliacane. 2022.  Factored Adaptation for Non-Stationary Reinforcement Learning. In _Advances in Neural Information Processing Systems_ , S Koyejo, S Mohamed, A Agarwal, D Belgrave, K Cho, and A Oh (Eds.), Vol. 35. Curran Associates, Inc., 31957–31971.  https://proceedings.neurips.cc/paper_files/paper/2022/file/cf4356f994917177213c55ff438ddf71-Paper-Conference.pdf
  * Glymour et al. (2019) Clark Glymour, Kun Zhang, and Peter Spirtes. 2019.  Review of Causal Discovery Methods Based on Graphical Models.  _Frontiers in Genetics_ 10 (6 2019).  https://doi.org/10.3389/fgene.2019.00524
  * Hasan and Gani (2022) Uzma Hasan and Md Osman Gani. 2022.  Kcrl: A prior knowledge based causal discovery framework with reinforcement learning. In _Machine Learning for Healthcare Conference_. 691–714.
  * Hauser and Ch (2012) Alain Hauser and Buhlmann@stat Math Ethz Ch. 2012.  Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs Peter B ¨ uhlmann.  _Journal of Machine Learning Research_ 13 (2012), 2409–2464.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long Short-Term Memory.  _Neural Computation_ 9, 8 (11 1997), 1735–1780.  https://doi.org/10.1162/neco.1997.9.8.1735
  * Hyttinen et al. (2014) Antti Hyttinen, Frederick Eberhardt, and Matti Järvisalo. 2014.  Constraint-based Causal Discovery: Conflict Resolution with Answer Set Programming. In _Conference on Uncertainty in Artificial Intelligence_. 340–349.
  * Jenner et al. (2022) Erik Jenner, Herke van Hoof, and Adam Gleave. 2022.  Calculus on MDPs: Potential Shaping as a Gradient.  (8 2022).  https://arxiv.org/abs/2208.09570v2
  * Lei et al. (2022) Anson Lei, Bernhard Schölkopf, and Ingmar Posner. 2022.  Causal Discovery for Modular World Models. In _NeurIPS 2022 Workshop on Neuro Causal and Symbolic AI (nCSI)_.  https://openreview.net/forum?id=VfkjQzdGCH
  * Li et al. (2022) Wenqian Li, Yinchuan Li, Shengyu Zhu, Yunfeng Shao, Jianye Hao, and Yan Pang. 2022.  GFlowCausal: Generative Flow Networks for Causal Discovery.  (2022).  http://arxiv.org/abs/2210.08185
  * Lippe et al. (2021) Phillip Lippe, Taco Cohen, and Efstratios Gavves. 2021.  Efficient Neural Causal Discovery without Acyclicity Constraints. In _International Conference on Learning Representations_.
  * Lorch et al. (2022) Lars Lorch, Scott Sussex, Jonas Rothfuss, Andreas Krause, and Bernhard Schölkopf. 2022.  Amortized Inference for Causal Structure Learning. In _Advances in Neural Information Processing Systems_ , S Koyejo, S Mohamed, A Agarwal, D Belgrave, K Cho, and A Oh (Eds.), Vol. 35. Curran Associates, Inc., 13104–13118.  https://proceedings.neurips.cc/paper_files/paper/2022/file/54f7125dee9b8b3dc798bb9a082b09e2-Paper-Conference.pdf
  * Maathuis et al. (2010) Marloes H. Maathuis, Diego Colombo, Markus Kalisch, and Peter Bühlmann. 2010.  Predicting causal effects in large-scale systems from observational data.  _Nature Methods 2010 7:4_ 7, 4 (4 2010), 247–248.  https://doi.org/10.1038/nmeth0410-247
  * Méndez-Molina et al. (2022) Arquímides Méndez-Molina, Eduardo F.Morales, and L Enrique Sucar. 2022.  Causal Discovery and Reinforcement Learning: A Synergistic Integration. In _Proceedings of The 11th International Conference on Probabilistic Graphical Models_ _(Proceedings of Machine Learning Research, Vol. 186)_ , Antonio Salmerón and Rafael Rumi (Eds.). PMLR, 421–432.  https://proceedings.mlr.press/v186/mendez-molina22a.html
  * Mnih et al. (2015) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. 2015.  Human-level control through deep reinforcement learning.  _Nature_ 518 (2015).  https://doi.org/10.1038/nature14236
  * Mooij et al. (2020) Joris M Mooij, Sara Magliacane, and Tom Claassen. 2020.  Joint Causal Inference from Multiple Contexts.  _Journal of Machine Learning Research_ 21 (2020), 1–108.  http://jmlr.org/papers/v21/17-123.html.
  * Nair et al. (2019) Suraj Nair, Yuke Zhu, Silvio Savarese, and Li Fei-Fei. 2019.  Causal Induction from Visual Observations for Goal Directed Tasks.  (2019).
  * Ng et al. (1999) Andrew Y. Ng, Daishi Harada, and Stuart Russell. 1999.  Policy invariance under reward transformations: Theory and application to reward shaping.  _ICML_ (1999), 278–287.
  * Pearl (2009) Judea Pearl. 2009.  Introduction to Probabilities, Graphs, and Causal Models.  In _Causality_. Cambridge University Press, 1–40.  https://doi.org/10.1017/CBO9780511803161.003
  * Sachs et al. (2005) Karen Sachs, Omar Perez, Dana Pe’er, Douglas A. Lauffenburger, and Garry P. Nolan. 2005.  Causal Protein-Signaling Networks Derived from Multiparameter Single-Cell Data.  _Science_ 308, 5721 (4 2005), 523–529.  https://doi.org/10.1126/science.1105809
  * Sauter et al. (2023) Andreas W M Sauter, Erman Acar, and Vincent Francois-Lavet. 2023.  A Meta-Reinforcement Learning Algorithm for Causal Discovery. In _Proceedings of the Second Conference on Causal Learning and Reasoning_ _(Proceedings of Machine Learning Research, Vol. 213)_ , Mihaela van der Schaar, Cheng Zhang, and Dominik Janzing (Eds.). PMLR, 602–619.  https://proceedings.mlr.press/v213/sauter23a.html
  * Scherrer et al. (2022) Nino Scherrer, Olexa Bilaniuk, Yashas Annadani, Anirudh Goyal, Patrick Schwab, Bernhard Schölkopf, Michael C Mozer, Yoshua Bengio, Stefan Bauer, and Nan Rosemary Ke. 2022.  Learning Neural Causal Models with Active Interventions.  (2022).
  * Shanmugam et al. (2015) Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. 2015.  Learning Causal Graphs with Small Interventions. In _Advances in Neural Information Processing Systems_ , C Cortes, N Lawrence, D Lee, M Sugiyama, and R Garnett (Eds.), Vol. 28. Curran Associates, Inc.  https://proceedings.neurips.cc/paper_files/paper/2015/file/b865367fc4c0845c0682bd466e6ebf4c-Paper.pdf
  * Spirtes et al. (2000) Peter Spirtes, Clark N Glymour, and Richard Scheines. 2000.  _Causation, prediction, and search_.  MIT press.
  * Sutton and Barto (2018) R.S. Sutton and A.G. Barto. 2018.  _Reinforcement learning: An introduction_.  MIT press.
  * Tigas et al. (2022) Panagiotis Tigas, Yashas Annadani, Andrew Jesson, Bernhard Schölkopf, Yarin Gal, and Stefan Bauer. 2022.  Interventions, Where and How? Experimental Design for Causal Models at Scale.  _Advances in Neural Information Processing Systems_ 35 (12 2022), 24130–24143.  https://github.com/yannadani/cbed
  * Ton et al. (2021) Jean-François Ton, Dino Sejdinovic, and Kenji Fukumizu. 2021.  Meta learning for causal direction. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 35. 9897–9905.
  * Vowels et al. (2023) Matthew J. Vowels, Necati Cihan Camgoz, and Richard Bowden. 2023.  D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery.  _Comput. Surveys_ 55, 4 (4 2023), 1–36.  https://doi.org/10.1145/3527154
  * Wang et al. (2021) Xiaoqiang Wang, Yali Du, Shengyu Zhu, Liangjun Ke, Zhitang Chen, Jianye Hao, and Jun Wang. 2021.  Ordering-Based Causal Discovery with Reinforcement Learning.  (2021).  https://arxiv.org/abs/2105.
  * Watkins and Dayan (1992) Christopher J C H Watkins and Peter Dayan. 1992.  Q-Learning.  8 (1992), 279–292.
  * Yu et al. (2019) Yue Yu, Jie Chen, Tian Gao, and Mo Yu. 2019.  DAG-GNN: DAG Structure Learning with Graph Neural Networks. In _Proceedings of the 36th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 97)_ , Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR, 7154–7163.  https://proceedings.mlr.press/v97/yu19a.html
  * Zheng et al. (2018) Xun Zheng, Bryon Aragam, Pradeep Ravikumar, and Eric P Xing. 2018.  DAGs with NO TEARS: Continuous Optimization for Structure Learning.  (2018).  https://github.com/xunzheng/notears.
  * Zhu et al. (2019) Shengyu Zhu, Ignavier Ng, and Zhitang Chen. 2019.  Causal Discovery with Reinforcement Learning.  (2019).  http://arxiv.org/abs/1906.04477
  * Zwitter and Soklic (1988) Matjaz Zwitter and Milan Soklic. 1988.  Breast Cancer.  UCI Machine Learning Repository.

##  Appendix A Equivalence of our Reward and the Difference in SHDs

Let $G^{*}_{s}$ be the observational ground-truth graph of the current SCM
$M^{i}_{do(\emptyset)}$. Furthermore, let $\hat{G}_{s}$ be the estimated graph
at state $s$, $\hat{G}_{s^{\prime}}$ the estimated graph in the consecutive
state and $E(a)$ the edge that is manipulated by action $a$. We show that

$SHD(G^{*}_{s},\hat{G}_{s})-SHD(G^{*}_{s},\hat{G}_{s^{\prime}})=\begin{cases}1&ifE(a)\in
G^{*}_{s}\\\ -1&ifE(a)\not\in G^{*}_{s}\\\ 0&ifE(a)=\emptyset\end{cases}$ (9)

if $a$ adds an edge and

$SHD(G^{*}_{s},\hat{G}_{s})-SHD(G^{*}_{s},\hat{G}_{s^{\prime}})=\begin{cases}-1&ifE(a)\in
G^{*}_{s}\\\ 1&ifE(a)\not\in G^{*}_{s}\\\ 0&ifE(a)=\emptyset\end{cases}$ (10)

if $a$ deletes an edge. In the following, we derive this equality. For a
simplified notation, we write $E_{G}$ for the set of edges in $G$. We start by
decomposing the difference in its set-theoretic components.

$\displaystyle SHD(G^{*}_{s},\hat{G}_{s})-SHD(G^{*}_{s},\hat{G}_{s^{\prime}})$
$\displaystyle=\mid E_{G^{*}_{s}}\setminus E_{\hat{G}_{s}}\mid+\mid
E_{\hat{G}_{s}}\setminus E_{G^{*}_{s}}\mid$ $\displaystyle-\mid
E_{G^{*}_{s}}\setminus E_{\hat{G}_{s^{\prime}}}\mid-\mid
E_{\hat{G}_{s^{\prime}}}\setminus E_{G^{*}_{s}}\mid$

We now distinguish the two cases of adding and deleting, and edge. In these
cases, the terms become:

##### Case 1; an edge is _added_ to $\hat{G}_{s}$:

Then

$\mid E_{G^{*}_{s}}\setminus E_{\hat{G}_{s}}\mid-\mid E_{G^{*}_{s}}\setminus
E_{\hat{G}_{s^{\prime}}}\mid=\begin{cases}1&ife\in E_{G^{*}_{s}}\\\
0&ife\not\in E_{G^{*}_{s}}\end{cases}$ (11)

and

$\mid E_{\hat{G}_{s}}\setminus E_{G^{*}_{s}}\mid-\mid
E_{\hat{G}_{s^{\prime}}}\setminus E_{G^{*}_{s}}\mid=\begin{cases}0&ife\in
E_{G^{*}_{s}}\\\ -1&ife\not\in E_{G^{*}_{s}}\end{cases}$ (12)

Finally, considering the case where the edge was not manipulated
($E(a)=\emptyset$), we add Equations (11) and (12) and arrive at Equation (9).

##### Case 2; an edge is _removed_ from $\hat{G}_{s}$:

In this case, the results in Equation (11) and (12) are multiplied by $-1$.
After again adding the inverted parts, we arrive at Equation (10).

##  Appendix B Hyperparameters

|  | shared layers | shared layers size | policy layers | policy layers size | episode length | total training steps
---|---|---|---|---|---|---|---
3 variables | MCD | 1 LSTM | 64 | 2 | 128 | 10 | 2000000
| CORE | 0 | - | 3 | 128 | 5 | 2000000
4 variables | MCD | 1 LSTM | 64 | 2 | 128 | 16 | 3500000
| CORE | 0 | - | 3 | 128 | 8 | 3500000
5 variables | MCD | 1 LSTM | 128 | 2 | 256 | 20 | 4500000
| CORE | 0 | - | 3 | 256 | 10 | 4500000
8 variables | MCD | - | - | - | - | - | -
| CORE | 0 | - | 2 | 1024 | 12 | 45000000
10 variables | MCD | - | - | - | - | - | -
| CORE | 0 | - | 3 | 1024 | 15 | 90000000

Table 3. The hyperparameters that we used to obtain our results. These
parameters are the same for all experiments we performed in this paper.

Table 3 describes the main hyperparameters that we used throughout this paper.
For MCD Sauter et al. (2023), we additionally used the default hyperparameters
that were used in the original paper.

##  Appendix C Hardware Requirements

We ran training and evaluation on the DAS-6 compute cluster (Bal et al.,
2016). At inference time, CORE generates a graph estimate in about 18-34
milliseconds, depending on the size of the policy network and the episode
length.

For training, CORE took approximately 51min, 1h40min, 2h5min, 23h, 30h to
train for 3, 4, 5, 8, 10 variables, respectively. For the 3, 4, and 5 variable
case these are the results on a 24 core machine with an RTX4000 GPU, for 8 and
10 variables the results are on a 48 core A100 machine.