The Minimal Search Space for Conditional Causal Bandits

Causal bandits exploit structural relationships among variables to share information across interventions and accelerate the identification of high-reward decisions. In many applications, however, some variables cannot be directly manipulated, even though they influence the reward and provide useful information about the underlying causal system. We study contextual causal bandits with non-manipulable variables, where context variables are observed before action selection and additional variables are observed after each intervention. Assuming a known causal graph without latent confounding, we adopt a Bayesian formulation in which the conditional probability tables of the observational distribution constitute the unknown parameter. This representation allows observations collected under one intervention to update reward estimates for other interventions through their shared causal mechanisms. We develop causal variants of Thompson Sampling and Information-Directed Sampling (IDS) for this setting. For Thompson Sampling, we establish an entropy-dependent sublinear Bayesian regret bound. For IDS, we derive an entropy-dependent regret bound that explicitly quantifies the additional error introduced by Monte Carlo approximation of the expected regret and information gain; when these quantities are available exactly, the bound recovers the standard sublinear IDS rate. The dependence of these guarantees on the action-set size is worst-case: our model contains the standard multi-armed bandit as a special case. We further provide high-probability confidence bounds for the Monte Carlo estimates. Experiments on synthetic causal bandit tasks show that the proposed methods outperform causal and non-causal baselines by effectively exploiting information shared across interventions.

Causal Bayesian Optimization (CBO) combines causal inference with Bayesian optimization to enable sample-efficient intervention selection in systems with causal structure. This survey provides a systematic review of CBO through a unified BO-loop perspective, showing how causal assumptions shape intervention search spaces, surrogate models, acquisition functions, and decision policies. We organize existing methods by graph and system-knowledge assumptions, environment, intervention representation, surrogate architecture, and decision rule, and connect CBO to causal bandits, Bayesian experimental design, safe optimization, policy search, and causal abstraction. We also introduce a reproducibility-oriented benchmark spanning hard- and soft-intervention settings, with standardized GAP and a new trajectory-aware Path-Aware GAP (PA-GAP), evaluating seven CBO methods and a non-causal BO baseline across thirteen datasets, three budgets, and two metrics. Results show that no method dominates uniformly: rankings depend on dataset, budget, metric, and how causal information is used, while strong non-causal baselines remain competitive in several settings. Controlled graph-misspecification and omitted-variable stress tests further show that rankings can change substantially when learner-side causal information is perturbed. We conclude by identifying key open challenges, including robustness to causal-assumption violations, scalable unknown-graph optimization, mixed intervention types, realistic cost models, stronger theoretical guarantees, and integration with modern representation learning and causal abstractions.

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).