Causal bandits with backdoor adjustment on unknown Gaussian DAGs

Yijia Zhao, Qing ZhouarXiv 2025 · DOI · arXiv

Introduction

In the standard Multi-Armed Bandit (MAB) framework, an agent selects actions ("arms") to maximize cumulative rewards. However, real-world systems often exhibit complex causal structures where actions influence rewards through intermediate variables. This is the domain of Causal Bandits. While most existing literature assumes the underlying Causal Directed Acyclic Graph (DAG) is known, this paper addresses the more realistic scenario where the graph structure is unknown.

The BA-UCB Algorithm

The authors propose BA-UCB (Backdoor Adjustment - Upper Confidence Bound), which leverages both experimental and observational data. The core innovation lies in using "cheap" observational data to refine the estimates obtained from "expensive" experimental interventions.

The BA-UCB Workflow

  1. Markov Blanket Estimation: Using observational data, the algorithm identifies the local neighborhood of each variable to restrict the search space for causal influencers.
  2. Backdoor Set Identification: The algorithm identifies sets of variables that satisfy the backdoor criterion. It validates these sets by comparing observational estimates (adjusted for the backdoor set) with experimental results.
  3. Weighted UCB Calculation: BA-UCB computes a weighted average of experimental and adjusted observational estimates. This integration results in tighter confidence bounds, enabling faster convergence to the optimal action.

Experimental Evaluation

The performance of BA-UCB was evaluated using synthetic Gaussian Linear Structural Equation Models (SEMs). The study utilized random Gaussian DAGs with varying node counts ($p \in \{10, 20, 30, 50\}$). BA-UCB was benchmarked against several methods:

  • Standard UCB: A baseline that ignores causal structure entirely.
  • CN-UCB (Central Node UCB): A causal bandit algorithm that assumes the optimal arm is a direct parent of the reward.
  • BBB-UCB (Bayesian Backdoor Bandit): A theoretically robust Bayesian approach that is computationally intensive.

Results and Discussion

BA-UCB demonstrates significant improvements in cumulative regret compared to non-causal and restricted causal methods.

Cumulative regret comparison for BA-UCB, CN-UCB, and UCB across different graph sizes and parent-reward conditions.

As shown in Figure 1, BA-UCB consistently outperforms UCB and CN-UCB across various graph sizes. A critical finding is the algorithm's robustness when the optimal intervention is not a direct parent of the reward (the "FALSE" condition in the figure). In these scenarios, CN-UCB fails to identify the optimal arm, leading to linear regret, whereas BA-UCB successfully converges.

Comparison of BA-UCB against the Bayesian BBB-UCB method and other benchmarks.

While Bayesian methods like BBB-UCB can achieve lower regret in specific settings (Figure 2), they suffer from super-exponential computational complexity. BA-UCB provides a scalable alternative that remains efficient even as the number of nodes increases to $p=50$, where Bayesian methods become computationally prohibitive. Furthermore, the authors prove that with sufficient observational data, the regret of BA-UCB becomes independent of the number of arms ($K$), effectively using observational data as a force multiplier for exploration.

Conclusion and Future Work

BA-UCB represents a significant step forward in causal bandits by effectively utilizing observational data without requiring prior knowledge of the DAG. By focusing on local backdoor sets rather than global structure discovery, the algorithm achieves a favorable balance between exploration and exploitation.

Future research directions include extending the framework to non-linear systems, handling hidden confounders (relaxing the causal sufficiency assumption), and adapting to dynamic environments where the causal structure may evolve over time.

Summary updated

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 the number of intervention arms compared to standard multi-armed bandit methods. We further extend the methodology and theoretical guarantees to settings with latent confounders, where the observed variables are modeled by an acyclic directed mixed graph. Simulation studies demonstrate that BA-UCB achieves substantially lower cumulative regret and favorable computational efficiency relative to existing approaches.
BibTeX
@misc{zhao2025causal,
  author = {Yijia Zhao and Qing Zhou},
  title = {{Causal bandits with backdoor adjustment on unknown Gaussian DAGs}},
  year = {2025},
  eprint = {2502.02020},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.02020},
}
Figure