📈 economics

Budget-Constrained Causal Bandits: Bridging Uplift Modeling and Sequential Decision-Making

This article introduces Budget-Constrained Causal Bandits (BCCB), an online framework that unifies learning advertising effectiveness, exploration, and budget pacing to outperform traditional offline methods in cold-start advertising scenarios by operating effectively from the first user while exhibiting significantly lower performance variance.

Original authors: Abhirami Pillai

Published 2026-04-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Abhirami Pillai

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 the manager of a massive digital billboard campaign. You have a limited amount of money (a budget) to show ads to millions of people. Your goal is simple: get as many people as possible to click on the ad and buy something.

But here's the catch: Not everyone is the same.

Some people would buy the product even if they never saw the ad.
Some people would never buy it, no matter how many times you show them the ad.
Some people are the "Sweet Spot": They buy only because they saw your ad.

The challenge is to figure out who falls into this "Sweet Spot" without wasting your money on the others while your cash register counts down.

The Old Way: The "Crystal Ball" Approach

Traditionally, companies tried to solve this in two steps, like a chef preparing a dish before guests arrive:

The Recipe Book: You would sift through a huge pile of past data (like a recipe book) to learn who usually buys what.
The Shopping List: You would use this book to create a strict list of exactly the people to whom the ad should be shown.

The Problem: This works brilliantly if you have a massive, perfect recipe book. But what if you are launching a brand-new product, entering a new country, or targeting a new type of customer? You don't have a recipe book yet. The old method fails because it has nothing to learn from. It is like trying to cook a gourmet meal with an empty pantry.

The New Solution: The "Smart Explorer" (BCCB)

The authors of this paper propose a new method called Budget-Constrained Causal Bandits (BCCB). Instead of waiting for a recipe book, this method learns while cooking.

Imagine BCCB as a smart explorer walking through a crowd, carrying a limited amount of money.

The "Causal" Part: The explorer doesn't just guess who looks interested. They try to figure out the cause-and-effect: "If I show this specific person an ad, will they buy because of the ad, or would they have bought anyway?"
The "Bandit" Part: This is a fancy term for "learning by trial and error." The explorer must balance two things:
- Exploitation: Showing ads to people who look like a safe bet (to generate immediate sales).
- Exploration: Showing ads to people who are a mystery (to find out if they are actually good targets).
The "Budget" Part: The explorer is smart with money. If they spend too quickly at the beginning, they might run out of money before meeting the perfect customer. If they are too stingy, they miss easy sales. BCCB constantly adjusts how fast it spends based on how much money is left and how much time remains.

The Big Discovery: The "Tipping Point"

The researchers tested this new explorer against the old "recipe book" method using a real dataset from a major advertising company. They found a fascinating "tipping point" in the amount of data you need:

The Cold Start (0 to 2,000 people): The old method crashes completely. It tries to build a recipe book with too few ingredients and produces garbage results. The new explorer (BCCB), however, works effectively from the very first person. It learns along the way.
The Middle Range (2,000 to 10,000 people): The old method begins to work but is very shaky. One day it might get lucky and find 100 buyers; the next day, with the same amount of data, it finds only 10. It is unpredictable. The new explorer is consistent and reliable.
The Sweet Spot (10,000+ people): Once the old method has a huge amount of historical data (about 10,000+ people), it eventually becomes better than the explorer. It can predict perfectly without needing to "waste" money on learning.

The Core Message: If you are starting a new campaign with little to no history, do not wait for data. Use the explorer (BCCB). It is 3 to 5 times more stable and reliable than old methods when data is scarce.

Why This Matters

In the real world of digital advertising, things change quickly. New products are launched, new markets open up, and user habits shift. Often, you don't have time to wait until data from 10,000 past customers has accumulated.

This paper shows that you don't have to wait. You can spend your budget wisely from day one while learning along the way who responds to your ads, without blowing your budget or guessing wildly. It transforms the chaotic process of "trying to find customers" into a steady, predictable journey.

1. Problem Formulation

The paper addresses the challenge of budget-constrained treatment allocation in digital advertising, particularly in Cold-Start scenarios, where historical data is scarce or non-existent (e.g., new campaigns, new markets).

Core Objective: Maximize the total number of conversions (treatment outcomes) by selecting a subset of users to show ads to, while adhering to a total budget constraint $B$ .
Key Constraints & Challenges:
1. Heterogeneous Treatment Effects (HTE): Users respond differently to ads. The goal is to target users with high positive causal effects ( $\tau(x)$ ) and avoid those who remain unaffected or are negatively influenced.
2. Budget Constraints: Each user has specific costs $c_t$ (e.g., auction price for ads). Cumulative costs must not exceed $B$ .
3. Cold-Start / Data Scarcity: Conventional offline methods require large historical datasets to train uplift models. In new scenarios, these data are unavailable, leading to the "Cold-Start" problem.
4. Sequential Decision-Making: Users arrive sequentially. The system must learn treatment effects online while simultaneously controlling budget pacing (avoiding premature exhaustion or wasteful underutilization).

Formal Definition:
The problem is modeled as a sequential process over $T$ rounds. In each round $t$ , the agent observes a user with features $x_t$ and costs $c_t$ and chooses an action $a_t \in \{0, 1\}$ (treat or not). The objective is:
$\max \sum_{t=1}^T a_t \cdot Y_t(1) \quad \text{subject to} \quad \sum_{t=1}^T a_t \cdot c_t \le B$
where $Y_t(1)$ is the potential outcome under treatment.

2. Methodology: Budget-Constrained Causal Bandits (BCCB)

The authors propose BCCB, a unified online framework that integrates three distinct components into a single sequential decision process. Unlike offline two-stage pipelines (train, then optimize) or standard bandits (which ignore HTE), BCCB learns, explores, and controls simultaneously.

A. Online HTE Estimation

Approach: Use of a Two-Model Approach to estimate individual treatment effects online.
- Model 1: Estimates $P(Y=1 | x, T=1)$ (conversion probability under treatment).
- Model 2: Estimates $P(Y=1 | x, T=0)$ (conversion probability under control).
Mechanism: Both models are updated incrementally after each observation via Stochastic Gradient Descent (SGD) with logistic loss.
Cold-Start Handling: Before sufficient data is collected (fewer than 50 treated/controlled observations), an optimistic prior ( $\hat{\tau} = 0.002$ ) is used to encourage initial exploration.

B. Thompson-Sampling Exploration

Goal: Balance between exploration (learning about uncertain users) and exploitation (targeting known high-value users).
Mechanism: Maintenance of Beta posterior distributions for the global success rates of treatment and control.
Exploration Bonus: At each step, the algorithm draws from the posteriors to calculate an exploration bonus:
$\text{exploration\_bonus}_t = (\theta_t^{(1)} - \theta_t^{(0)}) \cdot \eta$
This bonus is added to the estimated HTE and encourages the algorithm to treat users with uncertain effects, even if the current HTE estimate is ambiguous.

C. Adaptive Budget Pacing

Goal: Prevention of premature budget exhaustion or inefficient underutilization.
Mechanism: Calculation of a Budget Pressure Ratio ( $pace_t$ $p a c e_{t}$ ) in each round:
$pace_t = \frac{B_t / B_0}{(T - t) / T}$
- If $pace_t > 1$ : The budget is abundant relative to time; the algorithm spends more generously.
- If $pace_t < 1$ : The budget is depleting too quickly; the algorithm becomes more selective.
Threshold Modulation: The pacing ratio dynamically adjusts the decision threshold. When the budget is tight, the threshold for treatment increases, ensuring only users with high cost-efficiency are selected.

D. Combined Decision Rule

For each user $t$ , the algorithm calculates a score and a value-per-dollar metric:

Score: $s_t = \hat{\tau}(x_t) + \text{exploration\_bonus}_t$
Value: $v_t = s_t / c_t$
Decision: Treat ( $a_t=1$ ) if $v_t > \frac{\lambda}{\max(pace_t, \epsilon)}$ , where $\lambda$ is a base threshold.

3. Key Contributions

Unified Framework: Proposal of BCCB, the first framework that unifies HTE learning, Thompson-Sampling exploration, and adaptive budget pacing in a single online process, without requiring pre-collected historical data.
Data-Efficient Crossover: Empirical identification of a critical threshold (~10,000 historical observations). Below this, offline methods fail or are highly unstable; above this, offline methods can outperform online methods. BCCB functions effectively from the first user.
Performance Stability: Demonstration that BCCB exhibits 3–5 times lower performance variance compared to offline methods across repeated runs, making it more reliable for campaign planning.
Superior Online Performance: Among pure online methods, BCCB consistently outperforms standard Thompson Sampling, Budgeted Thompson Sampling, and Greedy HTE estimation across all budget levels.

4. Experimental Results

The study was evaluated on the Criteo Uplift Dataset (1.4 million users) with synthetic costs generated via a Log-Normal distribution.

Online-vs.-Online Comparison:
- At a high budget ($8,000), BCCB achieved 46 conversions and outperformed standard Thompson Sampling (37) and HTE-Greedy (29).
- At tight budgets ($1,000), BCCB and Budgeted TS performed best, underscoring the importance of budget awareness.
Data-Efficient Crossover (Offline vs. Online):
- < 2,000 observations: Offline methods failed completely (the model could not be fitted due to zero positive examples in the control group). BCCB worked successfully.
- 2,000 – 10,000 observations: Offline methods showed extreme variance (coefficient of variation > 100%). BCCB remained stable.
- > 50,000 observations: Offline methods eventually outperformed BCCB (104 vs. 25 conversions), confirming that offline methods are superior when ample representative data is available.
Stability: BCCB exhibited standard deviations of 7–13 conversions, while offline methods ranged from 35–65. This 3–5-fold reduction in variance is crucial for predictable ROI forecasting.
Scalability: BCCB maintained peak performance across various dataset sizes (100K, 500K, 1.4M users), while Greedy-HTE methods were highly inconsistent.

5. Significance and Limitations

Significance:

Solving the Cold-Start Problem: Provides a practical solution for new advertising campaigns where historical data is unavailable, a scenario where standard industry pipelines fail.
Risk Mitigation: The high stability of BCCB reduces the risk of campaign failure due to random seed variance, a common issue with offline models trained on small datasets.
Paradigm Shift: Moves the field from "train-then-deploy" to "simultaneous learning and allocation" for resource-constrained causal inference.

Limitations:

Data Abundance: If a company possesses over 50,000 historical observations from the same population, offline methods remain superior.
Synthetic Costs: The study used synthetic costs based on a Log-Normal distribution. Real-world auction dynamics could be more complex.
Model Complexity: The current implementation uses linear classifiers for HTE. More expressive online models (e.g., Online Neural Networks) could improve accuracy but were deferred for future work.

Conclusion:
BCCB bridges the gap between uplift modeling and sequential decision-making, offering a robust, data-efficient solution for budget-constrained treatment allocation in digital advertising, particularly in scenarios characterized by data scarcity and the need for immediate, stable performance.