Causal Discovery as Reinforcement Learning

This direction is merged into another direction: combinatorial explosion in causal discovery. Its last version stays readable and citable here.

Version 1 of 112 papers17 conceptsfrozen 2026-10-04

The challenge of causal discovery—identifying the directed acyclic graph (DAG) that represents the underlying relationships between variables—is fundamentally a search problem. Because the number of possible graphs grows super-exponentially with the number of variables, traditional methods often get stuck in local optima or rely on restrictive assumptions. A growing body of research frames this search as a Reinforcement Learning (RL) task, where an agent learns to navigate the space of graph configurations to maximize a reward based on data fit and structural validity.

Traditional causal discovery algorithms, such as greedy search or continuous optimization, often struggle with the non-convex landscape of graph structures. Shengyu Zhu and Zhitang Chen demonstrated that RL can serve as a powerful global search mechanism. In Causal Discovery with Reinforcement Learning, they treat graph generation as a sequential decision process. Unlike greedy heuristics that modify one edge at a time, an RL agent uses reward signals to explore diverse configurations, allowing it to bypass local minima and identify optimal structures in massive combinatorial spaces.

This approach is particularly effective because it allows for the use of non-differentiable scoring functions. While gradient-based methods require smooth landscapes, RL agents can optimize for discrete metrics like the Bayesian Information Criterion (BIC). Mateusz Sypniewski and Piotr Miłoś leverage this in their work on Amortized Causal Discovery, using Proximal Policy Optimization (PPO) to propose graphs that maximize rewards derived from data likelihood.

Enforcing Acyclicity and Structural Constraints

A primary difficulty in causal discovery is ensuring the resulting graph is a DAG (i.e., it contains no cycles). Early RL approaches, such as those by Yanghe Feng and Jincai Huang, integrated acyclicity penalties directly into the reward function. By penalizing the agent for creating cycles, the constrained optimization problem is effectively converted into an unconstrained search task.

However, recent work has moved toward "acyclicity by design." Bao Duong, Biwei Huang, and Hung Le introduced the ALIAS framework, which utilizes a "Vec2DAG" parametrization. This mathematical mapping transforms unconstrained continuous vectors directly into the space of valid DAGs. By ensuring acyclicity through the architecture itself, the agent can generate valid causal structures in a single step, significantly improving speed and accuracy in dense networks.

Beyond Static Discovery: Causal RL

While many researchers use RL as a tool to find a static graph, others integrate causal discovery into the RL agent's primary goal of maximizing environmental rewards. Mirco Mutti and Giorgia Ramponi developed C-PSRL, an algorithm where the agent learns the environment's causal structure as a byproduct of interaction. By maintaining a belief distribution over possible factorizations, the agent naturally converges on sparse causal representations that are necessary for optimal decision-making, bridging the gap between structure learning and active control.

Handling Real-World Data Imperfections

The flexibility of the RL framework also extends to handling imperfect data. Xiaoshui Huang and Fujin Zhu addressed the problem of incomplete datasets by using a specialized encoder within the RL loop. Their framework simultaneously imputes missing values and extracts features, allowing the agent to uncover causal structures from "holey" data more accurately than traditional two-step imputation and discovery methods.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_causal_discovery_as_reinforcement_learni_b540804e,
  title = {Causal Discovery as Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/causal-discovery-as-reinforcement-learning/rdr_b540804e89e14bb59a6959c748216ae7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_causal_discovery_as_reinforcement_learni_b540804e_v1,
  title = {Causal Discovery as Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/causal-discovery-as-reinforcement-learning/rdr_b540804e89e14bb59a6959c748216ae7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}