🤖 AI

Optimal Experiments for Partial Causal Effect Identification

This paper addresses the NP-hard problem of selecting cost-constrained experiments to maximally tighten causal effect bounds by formalizing the "max-potency" objective, developing efficient graphical pruning criteria to drastically reduce the search space, and demonstrating the approach's effectiveness on both synthetic benchmarks and real-world NHANES data.

Original authors: Tobias Maringgele, Jalal Etesami

Published 2026-05-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Tobias Maringgele, Jalal Etesami

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery: Does eating more vegetables actually prevent heart disease?

You have a pile of old records (observational data) showing who ate vegetables and who got sick. But there's a problem: these records are messy. Maybe the people who eat vegetables also exercise more, or have better healthcare, or just have healthier genes. Because of these hidden "confounders," you can't say for sure if the vegetables are the hero. All you can say is, "The effect is somewhere between a tiny benefit and a huge benefit." Your answer is a wide, fuzzy range.

To get a precise answer, you need to run an experiment (like a controlled trial). But experiments are expensive, time-consuming, and sometimes impossible to do on everything at once. You have a limited budget.

The Big Question: If you can only afford to run one or a few specific experiments right now, which ones should you pick to shrink that fuzzy range the most?

This paper introduces a new method to answer that question before you even spend a dime.

The Core Idea: "Epistemic Potency"

The authors call the value of an experiment its "Epistemic Potency." Think of this as the experiment's "shrink-ray power."

Low Potency: An experiment that, no matter what the result is, leaves your fuzzy range almost as wide as it was. It's like trying to fix a leaky roof with a band-aid.
High Potency: An experiment that guarantees to shrink your range significantly, no matter the outcome. It's like finding the exact source of the leak.

The goal of the paper is to find the "Max-Potency" set of experiments you can afford.

The Problem: Too Many Choices

If you have 20 variables in your mystery (diet, sleep, stress, genes, etc.), the number of possible experiments you could run is astronomical. It's not just "do we test diet?" It's "do we test diet and sleep together?" or "do we test diet on Mondays but sleep on Tuesdays?"

The number of combinations grows so fast it's called "super-exponential." Trying to check every single combination to see which one is best is like trying to read every book in a library to find the one with the best plot, but the library doubles in size every time you turn a page. It's mathematically impossible to check them all.

Furthermore, the paper proves that finding the perfect combination is a NP-hard problem. In plain English: it's a puzzle so complex that even the fastest computers would take longer than the age of the universe to solve it perfectly for large cases.

The Solution: The "Useless" Filter

Since we can't check every option, the authors built a smart filter. They realized that many experiments are "combinatorially inert" or "useless." These are experiments that, based purely on the structure of the relationships (the causal graph), cannot possibly give you new information, no matter what the result is.

They created two "rules of thumb" (pruning criteria) to spot these useless experiments instantly, without doing any heavy math:

The "Path-Interception" Rule: Imagine the information about your mystery flows like water through pipes. If you plan to test a variable, but the "pipes" carrying the information to your final answer are blocked by another variable you aren't testing, your experiment is useless. It's like trying to measure the water pressure at the end of a hose when the main valve is already closed. The authors can spot this blockage in a split second by looking at the map of connections.
The "Already Known" Rule: Sometimes, the math says an experiment's result is already determined by the data you already have. Running it would be like asking a question that the answer key already holds. The paper uses a known algorithm (the ID algorithm) to spot these "already solved" cases.

The Results: Cutting the Search Space

By using these two rules, the authors showed they could throw away 50% to 88% of all possible experiments before doing any complex calculations.

Analogy: Imagine you have a haystack of a million needles. You need to find the sharpest one. Instead of testing every needle, you use a magnet that instantly pulls out 80% of the non-needles (the useless experiments). Now you only have to test the remaining 20%.
The Impact: This doesn't just save time; it makes the impossible possible. By removing the "useless" options, the number of combinations left to check drops so dramatically that a computer can actually find the best set of experiments in a reasonable amount of time.

Real-World Test: Exercise and Diabetes

To prove it works, the authors applied their method to real data from the NHANES survey (a large US health study).

The Mystery: Does physical activity prevent diabetes?
The Setup: They had data on balance, falls, insurance, activity, and diabetes.
The Outcome: Their algorithm looked at thousands of potential experiments (like "force people to exercise" or "measure specific health markers") and instantly identified which ones were useless. It then calculated the "potency" of the remaining ones.
The Verdict: It told them exactly which experiment (or combination of experiments) would give them the tightest, most useful answer for their budget. For example, it showed that testing a specific type of physical activity was better than testing a general one, and that combining two specific tests was better than doing either alone.

Summary

This paper doesn't give you a magic wand to solve every mystery instantly. Instead, it gives you a super-efficient map.

It defines how to measure the "value" of an experiment (Potency).
It admits that finding the perfect set is incredibly hard.
It provides a clever way to instantly discard the experiments that are guaranteed to be a waste of money.
It shows that by discarding the waste, you can actually find the best experiments to run, saving time and money while getting clearer answers about cause and effect.

In short: Don't waste your budget on experiments that can't possibly help. This paper tells you exactly which ones those are, so you can spend your money on the ones that will actually solve the mystery.

Title: Optimal Experiments for Partial Causal Effect Identification

Problem Statement
In causal inference, many queries of interest—such as the probability of necessity and sufficiency (PNS) or specific counterfactual quantities—are only partially identifiable from observational data. While sharp bounds can be derived, they are often too wide to support decision-making. Tightening these bounds typically requires experimental data, yet experiments are costly and subject to budget constraints. The central challenge addressed in this paper is the ex-ante selection of a cost-constrained subset of experiments that maximally tightens the bounds on a target causal query. Unlike sequential designs that adapt to realized outcomes, this work focuses on selecting the optimal batch of experiments before any experimental data is observed, navigating a search space that grows super-exponentially with the number of variables.

Methodology
The authors formalize this challenge as the max-potency problem. They define epistemic potency as the worst-case reduction in the width of the causal bounds guaranteed by an experiment (or set of experiments), regardless of the specific outcome observed.

Formal Framework: The problem is modeled using Structural Causal Models (SCMs) represented by Acyclic Directed Mixed Graphs (ADMGs). The authors leverage the polynomial-programming framework of Duarte et al. [2023], which expresses causal bounds as optimization problems over response-type variables (discrete functions mapping latent disturbances to outcomes).
Complexity: The paper proves that the max-potency problem is NP-hard via a reduction from the 0-1 knapsack problem. This is achieved by constructing disjoint "TP-cells" (confounded treatment-outcome pairs) where the potency of each cell can be tuned independently, making the total potency additive.
Evaluation Procedure: To evaluate the potency of a candidate experiment, the authors construct a coupled polynomial program. This program optimizes the difference between the upper and lower bounds of the target query subject to observational constraints and the constraints imposed by the hypothetical experimental outcomes.
Graphical Pruning: To manage the super-exponential search space, the authors introduce two graphical criteria to certify experiments as having zero potency (i.e., "useless") without solving any polynomial programs:
- Path-Interception Rule: Based on the district structure of the ADMG, this rule identifies experiments where all directed paths from the query-relevant response-types to the experimental outcomes pass through the intervened variables. This check runs in linear time.
- Identifiability Check: Based on the ID algorithm [Shpitser and Pearl, 2006], this rule certifies that any experiment whose outcome is already identifiable from observational data has zero potency.
Combinatorial Inertness: A key theoretical result (Corollary 6.15) establishes that experiments pruned by the ID check are "combinatorially inert." This means they can be entirely removed from the subset search space without affecting the optimal solution, effectively reducing the exponent of the search space.

Key Contributions

Problem Formalization: The definition of the max-potency problem and the proof of its NP-hardness.
Evaluation Algorithm: A general procedure for computing epistemic potency in discrete settings using polynomial programming.
Pruning Criteria: The introduction of two sound (though not complete) graphical criteria (path-interception and ID-check) that eliminate a significant portion of candidate experiments prior to optimization.
Search Space Reduction: The demonstration that ID-pruned experiments can be removed entirely from the subset enumeration, drastically reducing the computational burden for general subset searches.
Empirical Validation: Extensive testing on synthetic Erdős–Rényi graphs and 11 real-world benchmark networks from the bnlearn repository, as well as an end-to-end application on NHANES observational data.

Results

Pruning Efficiency: On Erdős–Rényi random graphs and bnlearn benchmarks, the two pruning criteria combined prune between 50% and 88% of candidate experiments on average when selecting a single optimal experiment.
Subset Search Reduction: For the general subset search, the ID-inertness property reduces the search space exponent by approximately 60% on average. For a candidate set of size 200, this reduces the effective search space from $2^{200}$ to roughly $2^{80}$ .
NHANES Application: In a case study estimating the effect of physical activity on diabetes using NHANES 2017–2018 data, the pipeline successfully identified useless experiments and selected optimal subsets under different budget constraints (e.g., selecting a single experiment for budget $B=1$ vs. a combination for $B=3$ ).

Significance and Claims
The paper claims to bridge the gap between causal identification (determining if a query is identifiable) and partial identification (determining how tightly it can be bounded). Its primary significance lies in providing a rigorous, pre-experimental framework for resource allocation in causal studies where point identification is impossible.

The authors emphasize that their approach guarantees a reduction in bound width regardless of the experimental outcome (worst-case guarantee), distinguishing it from expected-width or best-case criteria. They acknowledge limitations, including the reliance on discrete variables with finite support, the requirement for a known ADMG, and the fact that their pruning criteria are sound but not complete (some experiments not certified as useless may still have zero potency). The work is presented as a foundational step toward efficient experimental design in the regime of partial identification, offering a scalable alternative to brute-force search in complex causal settings.