Learning to Intervene Without a Known Causal Graph

18 concepts18 papers1 proposal

In standard multi-armed bandit problems, an agent interacts with the environment by pulling independent levers, treating each action as an isolated black box. However, in complex real-world systems—such as gene regulatory networks, financial markets, or large-scale recommendation engines—actions do not exist in a vacuum. Instead, they operate as interventions ($do$-operations) that ripple through a network of cause-and-effect relationships.

If an agent knows this network structure (represented as a Directed Acyclic Graph, or DAG), it gains a significant advantage. As demonstrated by Finnian Lattimore et al. in Causal Bandits: Learning Good Interventions via Causal Inference, observing un-intervened variables provides "side observations" that allow the agent to infer the consequences of alternative actions without having to execute them. Akihiro Yabe et al. in Causal Bandits with Propagating Inference proved that leveraging this propagating structure can reduce regret bounds to scale logarithmically with the number of actions, bypassing the exponential curse of dimensionality. By identifying a "possibly-optimal minimal intervention set" (POMIS), Sanghack Lee et al. in Structural Causal Bandits: Where to Intervene? showed that agents can prune redundant actions entirely, accelerating convergence by orders of magnitude.

Yet, these classical frameworks suffer from a severe bottleneck: they assume the causal graph is fully specified and accurate before learning begins. In practice, this structure is rarely known. The modern frontier of causal decision-making focuses on relaxing this assumption, forcing agents to navigate causal structure uncertainty by discovering the graph and optimizing policies simultaneously.

The Dual Exploration Problem

When the causal graph is unknown, the agent faces a nested exploration-exploitation dilemma. It must perform causal discovery (mapping out the graph topology) while concurrently executing policy optimization (finding the reward-maximizing intervention).

This tension spans multiple sequential decision-making paradigms. It appears in contextual settings, as explored by Chandrasekar Subramanian et al. in Causal Contextual Bandits with Targeted Interventions, and extends to complex state-space control models, such as the factored Markov decision processes analyzed by Ambuj Tewari et al. in Near-optimal Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms for the Non-episodic Setting. If an agent acts too early based on an unverified graph structure, its policy will be biased and suboptimal; if it spends its entire budget running experiments purely to map out the graph, it suffers catastrophic regret.

Interleaving Observation and Intervention

To resolve this tension efficiently, algorithms exploit the cost asymmetry between observing a system and intervening on it. Passive observations are typically cheap or free, whereas active interventions (like clinical trials or system overrides) are expensive or risky.

Vineet Nair et al. in Budgeted and Non-Budgeted Causal Bandits established frameworks for using passive observational data to narrow down the space of possible graphs before deploying costly interventions. By cleverly interleaving these passive observations with active, gap-dependent interventions, Nuoya Xiong et al. in Combinatorial Pure Exploration of Causal Bandits achieved polynomial sample complexity for linear causal models. The intuition here is straightforward: passive observations reveal conditional independencies that eliminate large classes of candidate graphs, allowing the agent to reserve its precious intervention budget for resolving the remaining structural ambiguities that directly impact the reward.

Bypassing Full Graph Reconstruction

A key insight driving this research direction is that an agent does not need to learn the entire causal graph to find the optimal intervention. Reconstructing a global network topology is an over-engineered solution when the objective is simply to maximize a localized reward variable.

Yangyi Lu et al. in Regret Analysis of Bandit Problems with Causal Background Knowledge demonstrated that the search space for optimal interventions is fundamentally governed by the direct parents of the reward variable, rather than the global network. By focusing structural learning locally around the reward node, algorithms can collapse an exponential action space into a manageable one.

Taking this a step further, some frameworks bypass explicit graph reconstruction entirely. Alan Malek et al. in Additive Causal Bandits with Unknown Graph proved that if the reward is an additive function of its direct causes, the causal bandit problem can be mathematically transformed into a linear bandit problem. Their algorithm, MODL, identifies optimal actions without ever explicitly reconstructing the graph topology.

When structural learning cannot be bypassed, it can be integrated directly into the policy loop. For example, Behzad Nourani-Koliji et al. in Linear Combinatorial Semi-Bandit with Causally Related Rewards utilized Structural Equation Models (SEMs) to simultaneously update the estimated network topology and optimize decisions based on real-time feedback, treating structure discovery and policy optimization as a single, unified learning problem.

Confronting Latent Confounders and Real-World Constraints

As these algorithms move from clean theoretical models to real-world environments, they must contend with hidden variables and physical limitations.

The most prominent hurdle is the presence of unobserved confounders—hidden variables that simultaneously influence multiple parts of the system, creating spurious correlations. To counter this, Lai Wei et al. in Approximate Allocation Matching for Structural Causal Bandits with Unobserved Confounders leveraged canonical Structural Causal Models to align data across disparate intervention distributions, allowing agents to efficiently account for hidden influences. In budgeted environments, Fateme Jamshidi et al. in Confounded Budgeted Causal Bandits showed that agents can still use cheap observations to "guess" interventional effects, even when hidden confounders threaten to bias the data.

Furthermore, real-world agents face physical constraints on what they can manipulate. As noted by Sanghack Lee et al. in Structural Causal Bandits with Non-Manipulable Variables, variables like age, weather, or socio-economic background cannot be forced or randomized by an agent. This changes the experimental design space entirely. Instead of searching for an unconstrained optimal intervention, the agent must identify a "minimum intervention cover"—a concept formalized by Arnab Bhattacharyya et al. in Minimum Intervention Cover of a Causal Graph—to find the smallest set of permissible experiments needed to resolve causal effects under structural uncertainty.

Ultimately, this integrated approach to structure and policy learning allows causal bandits to be applied to broader, more nuanced objectives. This includes maximizing rewards under general causal models (Zirui Yan et al. in Causal Bandits with General Causal Models and Interventions), optimizing mixed policies under partial observability (as characterized by the authors in Characterizing Optimal Mixed Policies: Where to Intervene and What to Observe), and ensuring counterfactual individual fairness in online recommendation systems (Lu Zhang et al. in Achieving Counterfactual Fairness for Causal Bandit).

Key Foundational Work

Causal Bandits: Learning Good Interventions via Causal Inference (2016) — contributed 1 concept elements to this direction.
Causal Bandits with Propagating Inference (2018) — contributed 1 concept elements to this direction.
Structural Causal Bandits: Where to Intervene? (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_causal_structure_uncertainty_4ad08a02,
  title = {causal structure uncertainty},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/causal-structure-uncertainty/rdr_4ad08a027a18436a8a2b7a43f078b94a},
  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_structure_uncertainty_4ad08a02_v1,
  title = {causal structure uncertainty},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/causal-structure-uncertainty/rdr_4ad08a027a18436a8a2b7a43f078b94a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake