CS Paper Radar

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

Min Woo Park, Sanghack Lee

cs.LG ·submitted 2026-11-10 13:30 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Multi-Objective Causal Bandits: Minimal Intervention Space and Policy-Level Learning

cs.LG ·2026-11-14 ·Muhammad Qasim Elahi, Mahsa Ghasemi, Murat Kocaoglu
top venue similarity 0.81
Abstract · To appear in Proceedings of NeurIPS 26

Many decision-making problems involve multiple objectives, where actions affect several performance metrics, fairness criteria, or safety constraints. We study multi-objective causal bandits with multiple reward nodes, where actions correspond to interventions on subsets of variables in a causal graph and performance is evaluated through Pareto optimality. Existing approaches to multi-objective bandits often rely on pairwise Pareto dominance or optimize a fixed scalarization. However, pairwise comparisons alone can fail to identify actions dominated by randomized policies, whose expected reward vectors lie in the convex hull of action-level rewards. Thus, an intervention may be suboptimal even if no single intervention dominates it, because it can be dominated by a randomized policy over other interventions. We formalize this policy-level phenomenon and show that it has consequences for both causal action-space reduction and online learning. First, we provide a necessary-and-sufficient graphical characterization of possibly Pareto- optimal minimal intervention sets. Our characterization yields a minimal, sound, and complete candidate intervention family from the graph alone, correcting prior formulations that may include intervention sets that are never Pareto-optimal under any compatible structural causal model. Second, over this reduced intervention space, we design an online UCB-style algorithm that eliminates actions using dominance tests against convex combinations of other actions, and prove logarithmic gap-dependent Pareto regret. Finally, we study constrained multi-objective causal bandits, where feasibility and optimality may be realized only with randomized policies, and develop an online UCB-style constrained bandit algorithm with sublinear regret and constraint-violation guarantees.

0.26

Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

cs.LG ·2026-10-01 ·Junhyuk Huh, Seoungbin Bae, Dabeen Lee
similarity 0.77
Abstract

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)$ expected joint loss. Under a weaker full-rank condition on the factual covariance pooled across actions, we identify a target-specific information scale $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 $Ω\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_\star$ and an adaptive algorithm that does not require its value. Both algorithms achieve $\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 $R_T$ is regret relative to the best fair action and $V_T$ denotes the cumulative stage-wise positive violations. Thus the upper and lower bounds match in their leading dependence on $T$, $V_\star$, and $\min\{\log K,d\}$, up to logarithmic factors.

0.20

Action-Centered Causal Bandits for Budget-Constrained Promotion Targeting

cs.LG ·2026-11-06 ·Yifan Lin, Kaixu Yang, Di Mo
publishedbenchmarktheory similarity 0.72
Abstract · Accepted at the 20th ACM International Conference on Web Search and Data Mining (WSDM 2027)

Web platforms select among costly interventions for each user to maximize incremental outcomes under a global budget. We formulate this problem as a budget-constrained contextual bandit with heterogeneous treatment effects. Although an action-independent outcome baseline cancels from treatment comparisons, modeling a nonlinear baseline can increase statistical complexity. We propose DR-CATE-CBwK, an action-centered causal bandit that directly learns treatment contrasts. Its online update remains valid under baseline-model misspecification without inverse-propensity weighting. It combines an offline doubly robust learner to warm-start treatment-effect estimates, an online action-centered estimator for sequential contrast learning, and a primal-dual controller with an affordable-action rule to enforce the effective-cost budget pathwise. For linear conditional average treatment effects (CATEs) in a stationary i.i.d. setting, we prove a high-probability (\widetilde{O}(Kd\sqrt{T})) regret bound, where K is the number of priced actions, d the context dimension, and T the horizon. We benchmark against the fluid linear program (LP) under the coverage-guaranteed action rule. We further show that the action-centered estimating moment remains unbiased under any predictable baseline estimate, whereas a specified separate-arm reward regression can exhibit asymptotic contrast bias under action-dependent logging and shared-baseline misspecification. On a semi-synthetic job-marketplace benchmark with real logged features and simulated outcomes, our practical Thompson-restricted variant achieves the lowest regret among evaluated budget-feasible methods in the operating regime. It reduces regret by approximately 20% versus the strongest reward-based baseline, outperforming raw-reward contextual bandits, BwK baselines, and a static offline policy, while never exceeding the effective-cost budget.

0.27

Transportable Offline Reinforcement Learning in Presence of Unmeasured Confounding

cs.LG ·2026-10-28 ·Junyi Liao, Hangqi Ren, Zhuoran Yang
similarity 0.72
Abstract

Offline reinforcement learning seeks to learn decision policies from previously collected data, but deployment environments may differ from the domains in which the data were collected, and logged variables may omit confounders that affected both historical actions and outcomes. We study offline policy learning under the joint challenges of domain discrepancy and unmeasured confounding, where multiple heterogeneous source datasets provide complementary information about a target domain. We develop a causally adjusted transportability framework combining transportability theory with instrumental variables, negative controls, and proxies to identify target-domain causal quantities. For confounded contextual bandits, identification reduces to systems of bridge-function integral equations, enabling minimax estimation from finite samples. Confidence sets for the identified quantities are then used for pessimistic policy optimization, yielding CAT-CCB. We extend the framework to episodic confounded Markov decision processes, where complementary sources identify target reward and transition mechanisms under structural and completeness conditions. Under Gaussian dynamics and linear function approximation, this yields CAT-CMDP. We establish high-probability finite-sample suboptimality guarantees that quantify the effects of approximation, estimation, source-to-target shift, offline coverage, and sample size. For bounded finite-dimensional linear classes, the contextual-bandit guarantee recovers the standard $\widetilde{\mathcal O}(N^{-1/2})$ rate. Numerical experiments support the effectiveness of the framework for learning target-domain policies from heterogeneous confounded data. Together, the results provide a principled approach when no single source dataset suffices for causal identification and policy optimization.

0.18

Causal Bayesian Optimization: Foundations, Methods, and Applications

cs.LG stat.ML ·2026-09-21 ·Chenfeng Huang, Thuy T. Le, Zixuan Ma, Hien Tran
publishedsurveybenchmark similarity 0.71
Abstract · Accepted at Transactions on Machine Learning Research (TMLR), 2026

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.

0.44

Gated Decoupled Compositional Bandits: A Unified Theory of Contextual Bandits with Supervised-Calibrated Action Scaling and Pre-Execution Gating

cs.LG ·2026-08-22 ·Oleg Miroshnichenko
theory similarity 0.68
Abstract · 30 pages, 4 figures

We introduce Gated Decoupled Compositional Bandits (GDCB), a family of contextual bandit algorithms with three structural innovations that jointly fall outside the taxonomy of LinUCB, LinTS, HierTS, factored bandits, neural contextual bandits, and RLHF. In a GDCB system: (i) the action delivered to the environment is the composition of a nominal arm, drawn by a discrete or hierarchical bandit, with a context-dependent scaler; (ii) the scaler parameter is learned in a separate supervised loop, not jointly with arm selection; and (iii) every action passes through a pre-execution gate that may modify or veto the composed action before it reaches the environment. We formalise this class of algorithms, prove four structural theorems characterising its statistical behaviour, and show that six industrially significant systems -- short-term rental dynamic pricing, clinical drug dosing, credit origination, grid demand response, content moderation, and LLM tool-use agents -- are all instances of GDCB, differing only in the composition operator, scaler family, and gate. The central result is the Decoupling Variance Reduction theorem: a well-calibrated scaler removes context-induced variance from the arm-to-reward mapping, turning a non-stationary bandit problem into an approximately stationary one. The Gate-Induced Equivalence theorem shows that under a stationary gate, historical data collected under any prior policy is a valid warm-up initialiser without importance-sampling correction, generalising the companion P-HITL result (arXiv:2606.02595) from human approval to arbitrary gates. In regulated, high-stakes domains, constraints usually treated as deployment frictions -- approval gates, compliance rules, safety shields -- are the mechanism that makes fast deployment possible, not an obstacle to it. The companion paper validates instance 1 (STR dynamic pricing) on real production data.

0.30

The Surrogate Is Not the Reward: Post-Surrogate Primary-Outcome Acquisition in Contextual Bandits

cs.LG stat.ML ·2026-10-05 ·Kyungbok Lee, Michael R. Kosorok
benchmarkhot direction similarity 0.68
Abstract

We study contextual bandits in which a surrogate is observed after the action but before the learner decides whether to acquire the primary outcome that defines action value and regret. The value of acquiring the primary outcome depends on both decision relevance (how much the current outcome matters for comparing policies) and the residual uncertainty after observing the surrogate. The Audited Surrogate Bandit (ASB) learns a contextual policy while allocating a budget of $B$ primary-outcome acquisitions over $T$ rounds. ASB sets a pre-surrogate acquisition level from current decision relevance and, after observing the surrogate, redistributes that level using an estimate of that residual uncertainty. For a finite class of $N$ policies over $K$ actions, ASB incurs $\widetilde O[\sqrt{KT\log N}\{1+\sqrt{T/B}\}]$ regret relative to the best policy in the class. In a two-action family where the surrogate does not reveal the better action, a learner that observes the surrogate before deciding whether to acquire can achieve bounded regret, whereas any learner that must decide before seeing the surrogate incurs $Ω(T/B)$ worst-case regret under the same budget. Synthetic experiments show that both acquisition factors matter: ASB has lower regret than variants using only decision relevance or only residual uncertainty. On a KuaiRec benchmark of user-video interactions, the regret gap relative to relevance-only acquisition widens and then narrows as the budget grows.

0.47

Optimal Online Regret for Context-Lumpable Bandits

cs.LG ·2026-10-13 ·Chenyu Lu, Zihan Zhang
theory similarity 0.67
Abstract

We study stochastic contextual bandits with an unknown context-lumpable structure. The $S$ contexts are partitioned into $r$ blocks, and every arm has the same mean reward across contexts in the same block. Under arbitrary context distributions and without separation assumptions, we design an algorithm with expected regret $\widetilde{O}(\sqrt{r(S+K)T})$, matching the lower bound of Lee et al. (2023) up to logarithmic factors and improving their previous upper bound by a factor of $r$. The algorithm operates over dyadic accuracy levels, using a baseline policy and confidence-based early stopping to control exploration. It then performs cross-context elimination: since rewards are identical within a block, one selected arm eliminates all surviving records from that block, requiring at most $r$ selections at each level. Multi-scale exploration assigns finer accuracies to frequent blocks and coarser accuracies to rare blocks, yielding a near-optimal arm for every block while keeping the weighted policy error small.

0.16