[2502.02020] Causal Bandit Over Unknown Graphs: Upper Confidence Bounds With Backdoor Adjustment

Computer Science > Machine Learning arXiv:2502.02020 (cs) [Submitted on 4 Feb 2025 (v1), last revised 3 Apr 2026 (this version, v3)] Title:Causal Bandit Over Unknown Graphs: Upper Confidence Bounds With Backdoor Adjustment Authors:Yijia Zhao, Qing Zhou View a PDF of the paper titled Causal Bandit Over Unknown Graphs: Upper Confidence Bounds With Backdoor Adjustment, by Yijia Zhao and 1 other authors View PDF HTML (experimental) Abstract:The causal bandit problem seeks to identify, through sequential experimentation, an intervention that maximizes the expected reward in a causal system modeled by a directed acyclic graph (DAG). Existing methods typically assume that the causal graph is known or impose restrictive structural assumptions. In this paper, we study causal bandit problems when the causal graph is unknown. We first consider Gaussian DAG models without latent confounders. By combining observational and experimental data collected sequentially during the bandit process, we identify candidate backdoor adjustment sets for each intervention arm. These sets enable estimation of causal effects and construction of upper confidence bounds that integrate information from both data sources. Based on these estimates, we propose a new algorithm, termed backdoor-adjustment upper confidence bound (BA-UCB), for sequential intervention selection. We establish finite-time upper bounds on the cumulative regret of BA-UCB, showing improved rates and substantially relaxed dependency on...