cs.LGNov 10, 2026

Generalizing Causal Decision-Making: Markov Equivalence, Transportability and Counterfactuals

Authors: Min Woo Park, Sanghack Lee

Organizations: Seoul National University Seoul, Republic of Korea

Abstract

Structural causal bandits use causal knowledge to guide exploration when reward mechanisms are unknown. This paper extends the approach to partially known causal structure, information from other environments, and realizable counterfactual actions. First, we develop graphical criteria for minimal intervention sets under Markov equivalence and characterize possibly-optimal minimal intervention sets for maximal ancestral graphs. A search algorithm finds sets that are possibly optimal in at least one graph represented by a partial ancestral graph. Second, we derive target reward bounds from source distributions through partial transportability, accounting for non-manipulable variables. Dominance relations provide further bounds for action pruning and restricted exploration, with a regret guarantee under valid prior bounds. Third, we formulate counterfactual structural causal bandits over actions supported by specified experimental capabilities. Graphical characterizations of minimality and possible optimality yield algorithms that remove equivalent or dominated choices while preserving an optimal action. Experiments with specified structural causal models examine how these reductions and transferred bounds affect learning. Together, these results clarify how causal knowledge and experimental capabilities determine which actions merit exploration and guide learning within the retained action space.

Figures & tables

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Feb 10, 2025

The Minimal Search Space for Conditional Causal Bandits

Causal knowledge can be used to support decision-making problems. This has been recognized in the causal bandits literature, where a causal (multi-armed) bandit is characterized by a causal graphical model and a target variable. The arms are then interventions on the causal model, and rewards are samples of the target variable. Causal bandits were originally studied with a focus on hard interventions. We focus instead on cases where the arms are conditional interventions, which more accurately model many real-world decision-making problems by allowing the value of the intervened variable to be chosen based on the observed values of other variables. This paper presents a graphical characterization of the minimal set of nodes guaranteed to contain the optimal conditional intervention, which maximizes the expected reward. We then propose an efficient algorithm with a time complexity of O(∣V∣+∣E∣)O(|V| + |E|) to identify this minimal set of nodes. We prove that the graphical characterization and the proposed algorithm are correct. Finally, we empirically demonstrate that our algorithm significantly prunes the search space and substantially accelerates convergence rates when integrated into standard multi-armed bandit algorithms.
Oct 1, 2026

Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

We study causal logistic bandits with counterfactual fairness constraints. The causal structure is given through known factual and counterfactual feature maps that share an unknown logistic reward parameter, but the learner observes only factual rewards. Consequently, the directions determining counterfactual feasibility need not be identifiable from the available feedback. The closest prior analyses either omit a coverage condition or impose a comparatively strong one, and do not establish matching lower bounds. We first show that some coverage condition is necessary: without a coverage-type restriction, factually indistinguishable environments with different optimal fair actions force Ω(T)Ω(T) expected joint loss. Under a weaker full-rank condition on the factual covariance pooled across actions, we identify a target-specific information scale V⋆V_\star that measures the difficulty of estimating rewards and counterfactual effects from factual feedback. We construct worst-case families satisfying this condition on which every policy incurs expected joint loss Ω([V⋆min⁡{log⁡K,d}]1/3T2/3)Ω\left(\left[V_\star\min\{\log K,d\}\right]^{1/3}T^{2/3}\right). We also give an explore--then--exploit procedure tuned using V⋆V_\star and an adaptive algorithm that does not require its value. Both algorithms achieve max⁡{RT,VT}=O~([V⋆min⁡{log⁡K,d}]1/3T2/3+κd/σ02)\max\{R_T,V_T\}=\widetilde{O}\left(\left[V_\star\min\{\log K,d\}\right]^{1/3}T^{2/3}+κd/σ_0^2\right), where RTR_T is regret relative to the best fair action and VTV_T denotes the cumulative stage-wise positive violations. Thus the upper and lower bounds match in their leading dependence on TT, V⋆V_\star, and min⁡{log⁡K,d}\min\{\log K,d\}, up to logarithmic factors.
Jul 17, 2026

Information-Directed Sampling for 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.