Abstract
This paper investigates the intersection of Causal Inference and Multi-Armed Bandits (MAB), focusing on two critical challenges: the high cost of interventions relative to observations and the achievement of constant cumulative regret in complex causal networks. We introduce novel algorithms, including $\gamma$-NB-ALG for budgeted scenarios and C-UCB-2 for general graphs. Our results demonstrate that leveraging causal side-information allows for significant reductions in regret, with C-UCB-2 achieving constant expected cumulative regret—a major theoretical advancement over previous sub-linear bounds.
1. Introduction
In a standard Multi-Armed Bandit problem, an agent pulls arms to identify the one with the highest reward. Causal Bandits extend this framework by treating arms as interventions within a Causal Bayesian Network (CBN). This paper addresses two primary gaps in existing research: the Cost Gap, where interventions (e.g., clinical trials) are far more expensive than observations (e.g., historical data), and the Regret Gap, where opportunity costs typically grow over time ($O(\sqrt{T})$) rather than reaching a steady state of zero new mistakes.
2. Causal Bandit Framework
In Causal Bandits, observations provide "free" exploration by revealing data about the conditional distributions of all variables in the network. This side-information can drastically reduce the need for costly interventions. For example, in a marketing scenario, variables such as product image size or promotional offers serve as intervenable nodes that influence a reward node like "Purchase" through intermediate steps.
3. Proposed Algorithms
The authors introduce three primary strategies to optimize decision-making:
- $\gamma$-NB-ALG: Designed for "no-backdoor" graphs, this algorithm uses a budget $B$ and a cost ratio $\gamma$ (intervention vs. observation cost). It intelligently switches between interventions and observations based on a calculated threshold to maximize information gain per unit of cost.
- CRM-NB-ALG: A cumulative regret minimization version for budgeted settings. It modifies the classic Upper Confidence Bound (UCB) approach to use "effective pulls," incorporating both direct interventions and relevant observations to sharpen reward estimates.
- C-UCB-2: A non-budgeted algorithm for general graphs. By maintaining UCB estimates for each intervention directly and utilizing knowledge of parent distributions, C-UCB-2 can eventually identify the optimal arm with certainty, leading to constant cumulative regret.
4. Key Results and Insights
The evaluation across synthetic simulations and conceptual models yielded several key findings:
- Budget Efficiency: In budgeted scenarios, $\gamma$-NB-ALG outperforms standard benchmarks by knowing when to cease expensive interventions. When the cost ratio $\gamma$ is high, relying on observations proves to be the optimal strategy.
- Constant Regret: C-UCB-2 maintains a flat regret curve after an initial learning period in general graphs with backdoors. This transition from a "learning" problem to a "verification" problem is a significant leap over previous algorithms like C-UCB, which continue to accumulate regret indefinitely.
- The No-Backdoor Advantage: In graphs without backdoor paths, observations are exceptionally powerful. If intervention costs are sufficiently high, the best strategy may involve zero interventions.
5. Conclusion and Future Work
This research demonstrates that accounting for intervention costs and causal structure can lead to more efficient and effective bandit algorithms. While the achievement of constant regret is a major milestone, it currently relies on known parent distributions. Future work will explore learning these distributions online and extending cost-aware strategies to graphs with unobserved confounders and soft interventions.
Summary updated