Abstract
Traditional multi-armed bandit (MAB) algorithms face a significant challenge in high-dimensional decision spaces where the number of possible actions grows exponentially with the number of variables. This paper presents causal bandit algorithms, specifically C-UCB and C-TS, which leverage known causal structures to optimize interventions. By focusing on the direct parents of a reward variable within a Directed Acyclic Graph (DAG), these algorithms achieve regret bounds that scale with the number of direct causes rather than the total number of possible interventions. Empirical evaluations demonstrate that this approach effectively resolves the curse of dimensionality, providing substantial performance gains in both synthetic and semi-synthetic marketing datasets.
Introduction
In a standard MAB problem, an agent seeks to maximize cumulative rewards by selecting the best action from a set of available arms. However, in complex real-world scenarios such as digital marketing or clinical trials, the number of possible interventions is often astronomical. For instance, if an agent can toggle $N$ different variables, the number of possible actions grows exponentially ($k^N$). Standard algorithms like Upper Confidence Bound (UCB) and Thompson Sampling (TS) treat each intervention as an independent arm, failing to exploit structural similarities between actions. This lack of knowledge leads to "regret" that explodes as the system complexity increases.
Causal Background Knowledge
The core innovation of this research is the integration of causal background knowledge, represented as a Directed Acyclic Graph (DAG). The authors demonstrate that to optimize a reward $Y$, an agent does not need to learn the entire causal mechanism of the environment. Instead, it is sufficient to understand the relationship between actions and the reward's direct parents ($Pa_Y$).
As shown in Figure 1, an intervention $do(X=x)$ affects the reward $Y$ primarily through its impact on the parent variables $W$. By observing these parent variables after each action, the agent can learn about multiple interventions simultaneously, drastically reducing the required exploration.
Proposed Algorithms
The paper introduces four primary algorithms designed to exploit this causal structure:
- C-UCB (Causal UCB): Maintains confidence bounds for the conditional distributions of the reward's direct parents rather than for every individual intervention.
- C-TS (Causal Thompson Sampling): A Bayesian variant that updates posterior distributions for the reward given its parents.
- CL-UCB & CL-TS (Causal Linear versions): These extend the framework to linear bandit settings, where the reward is a linear function of features derived from the parent variables, further improving efficiency in high-dimensional parent spaces.
Key Results and Scaling
The theoretical analysis resolves a long-standing open problem by providing cumulative regret bounds that achieve the optimal $\tilde{O}(\sqrt{T})$ scaling with respect to time. More importantly, the regret scales with the number of direct causes ($k^n$) rather than the total number of variables ($(k+1)^N$).
Empirical results in Figure 2 confirm these scaling laws. While standard UCB and TS regret grows sharply as the number of parents ($n$) increases, the causal algorithms (C-UCB, C-TS, and their linear counterparts) maintain significantly lower regret. In simulations, these causal methods achieved regret levels nearly 3x lower than standard MAB algorithms within just a few hundred iterations. Furthermore, experiments using semi-synthetic email campaign data showed that C-TS often handles exploration more gracefully than C-UCB, consistent with broader bandit literature.
Conclusion
By incorporating causal background knowledge, the proposed algorithms provide a scalable solution for high-dimensional decision-making problems. Future work aims to relax the assumption of a known causal graph by integrating causal discovery directly into the bandit loop and extending the framework to Causal Markov Decision Processes (MDPs) where actions have long-term effects on future states.
Summary updated