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
- Markov Blanket Estimation: Using observational data, the algorithm identifies the local neighborhood of each variable to restrict the search space for causal influencers.
- 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.
- 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.
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.
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