Fixed-Confidence Best-Arm Identification for Causal Mediation Analysis

Harsh Shrivastava; Yuta Kawakami; Junpei Komiyama; Jin Tian

stat.MLJul 5, 2026

Fixed-Confidence Best-Arm Identification for Causal Mediation Analysis

Authors: Harsh Shrivastava, Yuta Kawakami, Junpei Komiyama, Jin Tian

Organizations: Mohamed bin Zayed University of Artificial Intelligence (MBZUAI), Abu Dhabi, UAE · RIKEN AIP, Tokyo, Japan

Abstract

This paper studies the problem of identifying the treatment that maximizes the expected natural direct potential outcome (NDPO), which captures the potential outcome of an intervention while excluding the pathway transmitted through a mediator that researchers may wish to remove from evaluation. We first establish population-level identification of the expected NDPO in a causal bandit setting using observable interventional distributions. We then develop a fixed-confidence best-arm identification (BAI) algorithm based on the Track-and-Stop (TaS) framework, employing a cutting-set method to solve the resulting semi-infinite optimization problem. The proposed algorithm achieves sample-efficient identification with a high-probability correctness guarantee. We prove that it satisfies $δ$ -correctness and asymptotic optimality. Finally, we validate the approach through empirical evaluations on a large-scale real-world advertising dataset (IPinYou).

Explore similar work

Optimal Experiments for Partial Causal Effect Identification
May 7, 2026Tobias Maringgele, Jalal EtesamiCausal Graph Identifiability
Fundamental Limitations of Fixed-Budget Best-Arm Identification
Jul 13, 2026Motti Goldberger
The Minimal Search Space for Conditional Causal Bandits
Feb 10, 2025Francisco N. F. Q. Simoes, Itai Feigenbaum, Mehdi Dastani +1Causal Graph Linear Contextual Bandits

May 7, 2026 · cs.AIJ/K move · Enter open · S save

Optimal Experiments for Partial Causal Effect Identification

Tobias Maringgele, Jalal Etesami

Technical University of Munich · UC Berkeley

Causal queries are often only partially identifiable from observational data, and experiments that could tighten the resulting bounds are typically costly. We study the problem of selecting, prior to observing experimental outcomes, a cost-constrained subset of experiments that maximally tightens bounds on a target query. We formalize this as the max-potency problem, where epistemic potency measures the worst-case reduction in bound width guaranteed by an experiment, and show that this problem is NP-hard via a reduction from 0-1 knapsack. Building on the polynomial-programming framework of Duarte et al. (2023), we give a general procedure for evaluating epistemic potency in discrete settings. To control the super-exponential search space, we introduce two graphical pruning criteria that depend only on the causal graph and the query: a novel path-interception rule that exploits district structure to certify zero potency in linear time, and an identifiability check based on the ID algorithm. On Erdos-Renyi random graphs and 11 bnlearn benchmark networks, the two criteria together prune 50-88% of candidate experiments on average without solving a single polynomial program. For the general subset search, we show that ID-pruned experiments are combinatorially inert, yielding a super-exponential reduction in the number of subsets evaluated. We close with an end-to-end demonstration on observational NHANES data, selecting optimal experiments for estimating the effect of physical activity on diabetes.

Causal Graph Identifiability Epistemic Actions

Open paper Ask about it PDF

Abstract

Explore similar work

Optimal Experiments for Partial Causal Effect Identification

Fundamental Limitations of Fixed-Budget Best-Arm Identification

The Minimal Search Space for Conditional Causal Bandits