📊 statistics

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

This paper proposes the Backdoor-Adjustment Upper Confidence Bound (BA-UCB) algorithm for causal bandit problems with unknown graphs, which leverages sequential observational and experimental data to identify valid backdoor adjustment sets, thereby achieving improved regret bounds and reduced dependency on the number of arms compared to existing methods.

Original authors: Yijia Zhao, Qing Zhou

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yijia Zhao, Qing Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a farmer trying to figure out which single change will make your crops grow the biggest. You have a garden with many variables: temperature, soil moisture, fertilizer type, and sunlight. You know these things affect your harvest, but you don't know exactly how they interact.

This is the Causal Bandit Problem. You have to make a series of decisions (interventions) to find the best outcome, but every time you change something (like turning up the heat), it costs time and money. You want to learn the best strategy as quickly as possible without wasting resources on bad ideas.

The Old Way: Guessing in the Dark

Traditionally, farmers (or computer algorithms) would just try things one by one.

"Let's try more water." (Wait for results.)
"Let's try more sun." (Wait for results.)
"Let's try less fertilizer." (Wait for results.)

This is like playing a slot machine with 100 levers, pulling each one randomly to see which pays out the most. It works, but it's slow and expensive because you have to pull every lever many times to be sure.

The New Idea: The "Backdoor" Shortcut

The authors of this paper, Zhao and Zhou, propose a smarter way called BA-UCB (Backdoor-Adjustment Upper Confidence Bound).

Here is the secret sauce: You already have a massive library of old, free data.
Imagine you have 10 years of historical weather and crop records (Observational Data) where you didn't change anything, just watched what happened naturally. You also have a small budget to run new experiments (Experimental Data).

The problem is: You don't know the "Rulebook" (the Causal Graph). You don't know if "Heat" causes "Dry Soil" or if "Dry Soil" causes "Heat." Without the rulebook, you can't easily use the old data to predict what will happen if you change something.

The Magic Trick: Finding the "Backdoor"

In statistics, there's a concept called a Backdoor Adjustment. Think of it like this:
If you want to know if Fertilizer causes Big Crops, but Rain affects both (making the soil wet and helping crops grow), Rain is a "confounder." If you just look at the data, you might think Fertilizer is great, but it's actually just the Rain doing the work.

To fix this, you need to "block the backdoor" by holding "Rain" constant in your analysis. But how do you know which variables to hold constant if you don't know the rulebook?

BA-UCB solves this by doing two things at once:

The Detective: It looks at the old data and the new experimental data together to guess which variables are the "backdoors" (the confounders) that need to be blocked.
The Optimist: It builds a "confidence score" for each idea. If the old data and the new data agree that "Fertilizer + Blocking Rain = Big Crops," the score goes up. If they disagree, the score stays low, and the algorithm keeps investigating.

The Analogy: The Detective and the Lab

Imagine you are a detective trying to solve a crime (find the best crop strategy).

Standard Method (UCB): You only trust your own new experiments. You interview one suspect, then another, then another. It takes forever.
BA-UCB Method: You have a giant stack of old police reports (Observational Data). You don't know who the culprit is yet, so you can't just read the reports.
- Instead, you run a small experiment (e.g., "What happens if we lock the front door?").
- You then look at the old reports and ask: "If we lock the front door, does the data from 10 years ago match what I see now?"
- If the old data and new data line up, you gain confidence that you've found the right clue.
- If they clash, you know you missed a variable (a "backdoor") and you keep looking.

Why is this a Big Deal?

It's Cheaper: It uses the free, old data to do 90% of the heavy lifting, saving your expensive experimental budget.
It's Faster: Because it learns from all the data at once (not just one variable at a time), it finds the best solution much faster, especially when you have many variables to choose from.
It Doesn't Need a Map: Most previous methods required you to have the "map" (the causal graph) drawn out beforehand. This method figures out the map while it's driving.
It Handles Hidden Enemies: Even if there are "hidden confounders" (variables you can't see, like a secret underground water source), the algorithm is smart enough to realize when it can't use the old data and switches to relying purely on new experiments, so it never gets tricked.

The Result

In their computer simulations, this new BA-UCB algorithm made far fewer mistakes (lower "regret") than the standard methods. It found the best farming strategy faster, used less money, and didn't need to know the secret rules of the garden in advance.

In short: It's a smart, adaptive learning system that knows how to mix free historical data with expensive new experiments to make the best decisions, even when it doesn't know the full story yet.

1. Problem Formulation

The paper addresses the Causal Bandit (CB) problem, a sequential decision-making task where an agent selects interventions (arms) to maximize expected reward in a causal system.

Challenge: Unlike standard Multi-Armed Bandits (MAB) where arms are independent black boxes, causal bandits operate within a Directed Acyclic Graph (DAG) where variables are causally linked. Intervening on one variable affects others.
The Gap: Existing CB methods typically assume the causal graph structure is known or impose restrictive structural assumptions. In reality, the underlying DAG is often unknown.
Specific Setting: The authors focus on Gaussian DAG models (Linear Structural Equation Models) where the reward is a linear function of the variables. The goal is to identify the atomic intervention $do(X_i = x_i)$ that maximizes the expected reward $E[Y | do(X_i = x_i)]$ without prior knowledge of the graph.
Data Sources: The setting leverages two data sources:
1. Experimental Data: Collected sequentially during the bandit process (expensive, limited).
2. Observational Data: Historical data collected without interventions (abundant, cheap).

2. Methodology: The BA-UCB Algorithm

The authors propose the Backdoor-Adjustment Upper Confidence Bound (BA-UCB) algorithm. The core innovation is integrating observational data to estimate causal effects via backdoor adjustment, even when the graph is unknown.

Key Components:

Backdoor Adjustment Identification:
- Instead of recovering the full DAG (which is computationally hard and often impossible due to Markov equivalence), the algorithm identifies candidate backdoor adjustment sets ( $S$ ) for each intervention arm $X_i$ .
- Mechanism: For a candidate set $S$ , the algorithm compares the causal effect estimate derived from observational data (using regression $Y \sim X_i + X_S$ ) against the estimate from experimental data (direct intervention on $X_i$ ).
- Selection Criterion: A set $S$ is considered a valid candidate if the confidence interval of the difference between the observational estimate and the experimental estimate contains zero. This data-driven approach filters out invalid adjustment sets without needing the true graph.
Weighted Estimation:
- Once a candidate set $S$ is identified, the algorithm constructs a weighted average estimator for the expected reward $\mu_i$ .
- It combines the observational estimate ( $\hat{\mu}_{i,obs}$ ) and the experimental estimate ( $\hat{\mu}_{i,int}$ ) based on their respective sample sizes and variances.
- Robustness: The paper argues against a "single regression" approach (pooling all data into one regression) because it can be biased if the selected adjustment set is invalid. The weighted average approach is more robust to mis-specification.
Decision Rule (UCB):
- The algorithm selects the arm $A_{t+1}$ that maximizes the Upper Confidence Bound:
  $\hat{\mu}_i(t, S) + \hat{\sigma}_i(t, S) \cdot c \sqrt{\log t}$
- Here, $\hat{\mu}_i$ and $\hat{\sigma}_i$ are derived from the weighted combination of observational and experimental data.
Handling Latent Confounders:
- The framework is extended to Acyclic Directed Mixed Graphs (ADMGs) where latent confounders exist (represented by bidirected edges).
- If no valid adjustment set exists for a specific arm (due to latent confounding), the algorithm automatically defaults to using only experimental data for that arm, ensuring theoretical validity.

3. Key Contributions

Unknown Graph Assumption: The first method to solve causal bandits with unknown causal graphs without assuming the graph is provided or restricting the action space to parents of the reward.
Data Integration: A novel framework to seamlessly integrate abundant, low-cost observational data with expensive experimental data to reduce regret.
Theoretical Guarantees:
- Regret Bounds: Established finite-time upper bounds on cumulative regret.
- Dependence on $K$ : In the absence of latent confounders, the regret bound is $O(\sqrt{T \log T / (m+n)})$ , which does not depend on the number of arms $K$ (assuming sufficient observational data). This is a significant improvement over standard MAB bounds of $O(\sqrt{KT \log T})$ .
- Latent Confounders: Extended bounds show that regret depends on $K_1$ (the number of arms with no valid adjustment set) rather than the total $K$ .
Computational Efficiency: Unlike Bayesian approaches that require updating posteriors over all possible graph structures (exponential complexity), BA-UCB uses regression-based neighborhood estimation, making it scalable to larger graphs.

4. Results

The authors conducted extensive simulations comparing BA-UCB against:

Standard UCB: Uses only experimental data.
CN-UCB (Central Node): Attempts to identify parents of the reward first (fails if optimal arm is not a parent).
BBB-UCB (Bayesian Backdoor): A Bayesian method that is computationally prohibitive for larger graphs.

Key Findings:

Performance: BA-UCB achieves significantly lower cumulative regret than Standard UCB and CN-UCB.
Scalability: BA-UCB is computationally efficient and scales well with the number of nodes ( $p$ ), whereas BBB-UCB becomes intractable for $p \ge 20$ .
Robustness: When the optimal intervention is not a parent of the reward (a common failure case for CN-UCB), BA-UCB maintains high performance.
Convergence: Simulations show that the algorithm successfully identifies valid adjustment sets over time, and the combined estimator converges to the true causal effect.

5. Significance

This work bridges the gap between causal inference and sequential decision-making in realistic settings where:

Graphs are unknown: It removes the unrealistic assumption of known causal structures.
Data is heterogeneous: It effectively leverages the "free" observational data to accelerate learning, reducing the need for costly experimentation.
Scalability is critical: It provides a computationally feasible alternative to Bayesian methods for high-dimensional causal bandit problems.

The proposed BA-UCB algorithm represents a state-of-the-art approach for causal bandits, offering strong theoretical guarantees and practical efficiency, particularly in scenarios with large action spaces and available historical observational data.