Budgeted and Non-Budgeted Causal Bandits

Vineet Nair, Vishakha Patil, Gaurav Sinha

Abstract

This paper addresses the optimization of decision-making in causal systems where interventions are costly and observations are cheap. By leveraging causal Bayesian networks, the authors propose new algorithms for both budgeted and non-budgeted settings. Notably, they demonstrate that constant cumulative regret is achievable in general causal graphs when parent distributions are known, marking a significant advancement over previous sub-linear bounds.

Introduction: The Power of Causal Structure

In a standard Multi-Armed Bandit (MAB) problem, a decision-maker pulls "arms" to find the one with the highest reward, typically assuming no prior knowledge of how these arms relate to one another. Causal Bandits represent a sophisticated evolution of this framework, utilizing Causal Bayesian Networks (directed graphs) to model dependencies between variables. This allows an agent to predict the outcome of an intervention based on its understanding of the system's structure.

Example of a causal graph in an e-commerce setting, where various product features influence the final purchase decision.

However, traditional causal bandit models often overlook two critical real-world constraints:

  1. The Cost Gap: In domains like medicine or digital marketing, intervening (e.g., administering a drug or running a specific ad campaign) is significantly more expensive than simply observing the system in its natural state.
  2. Budget Constraints: Most decision-makers operate with a finite budget, making the efficiency of each action paramount.

This paper, presented at AISTATS 2021, tackles the challenge of minimizing "regret"—the difference between the earned reward and the reward from an optimal strategy—under these realistic constraints.

Algorithmic Frameworks

The authors categorize their contributions into two primary settings based on the complexity of the causal graph and the presence of budget constraints.

1. Budgeted Setting (No-Backdoor Graphs)

In "no-backdoor" graphs, observing a variable provides a direct, unbiased estimate of the effect of an intervention on that variable. The authors introduce two key algorithms for this space:

  • γ-NB-ALG: This algorithm identifies a "tipping point" (γ). It intelligently switches between cheap observations and strategic interventions based on whether the cost of intervention is justified by the potential information gain.
  • CRM-NB-ALG: A cumulative regret minimization algorithm that adapts the "Upper Confidence Bound" (UCB) approach. It introduces the concept of effective pulls, allowing observational data to contribute to the "experience" level of an intervention arm, thereby accelerating learning at a lower cost.

2. Non-Budgeted Setting (General Graphs)

For complex graphs where observations may be biased due to hidden "backdoor paths," the authors propose C-UCB-2. Previous state-of-the-art algorithms often suffered from high complexity by maintaining bounds for every possible combination of parent variables. C-UCB-2 simplifies this by maintaining a UCB for each intervention directly, significantly reducing both computational overhead and regret.

Key Insights and Results

The core innovation of this work lies in treating observations as "free" exploration. While an observational arm might yield lower immediate rewards, it provides data on all intervenable variables simultaneously. The authors mathematically define the threshold where the cost of an intervention outweighs its informational value.

The most striking theoretical and experimental result is the achievement of constant cumulative regret. In many bandit problems, regret is expected to grow logarithmically or sub-linearly with time. However, the authors show that if the distribution of the "parents" of the reward node is known, the expected cumulative regret can reach a ceiling and stop growing.

Comparison of cumulative regret over time (T). C-UCB-2 achieves constant regret, whereas the baseline C-UCB continues to accumulate regret.

As shown in the experimental results, C-UCB-2 quickly reaches this constant regret level, outperforming the previous benchmark, C-UCB, which continues to accumulate regret over time. Similarly, in budgeted scenarios, γ-NB-ALG and CRM-NB-ALG demonstrated superior efficiency by leveraging the causal graph to learn from observations, whereas traditional budgeted bandit algorithms (like F-KUBE) treat every arm as isolated, failing to exploit the underlying structure.

Limitations and Future Directions

While this work sets a new theoretical bar, it relies on a few key assumptions:

  • Known Graph Structure: The algorithms assume the "map" of causal relationships is already known. Future work must address "causal discovery"—learning the graph structure while simultaneously optimizing rewards.
  • Known Parent Distributions: The constant regret result for general graphs currently requires known distributions for the reward node's parents. Relaxing this to allow for online learning of these distributions is a necessary next step.
  • Hard Interventions: The current focus is on "hard" interventions (setting a variable to a fixed value). Extending these methods to "soft" interventions (shifting a distribution) would increase their applicability to more nuanced real-world scenarios.

Summary updated

BibTeX
@inproceedings{nair2021budgeted,
  author = {Vineet Nair and Vishakha Patil and Gaurav Sinha},
  title = {{Budgeted and Non-Budgeted Causal Bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=c_XsGXw9GNs},
}
Figure