LBCF: A Large-Scale Budget-Constrained Causal Forest Algorithm

Meng Ai, Biao Li, Heyang Gong, Qingwei Yu, Shengjie Xue, Yuan Zhang, Yunzhou Zhang, Peng Jiang

TL;DR

This paper introduces LBCF, a novel algorithm for optimizing marketing incentive allocation under budget constraints. By combining a unified causal forest for estimating treatment effects and an efficient dual gradient bisection method for budget optimization, LBCF significantly improves campaign engagement on a large-scale video platform, outperforming existing methods.

What Problem Does This Paper Address?

Online platforms frequently use incentives like discounts or bonuses to boost user engagement and revenue. However, these incentives come at a cost, and their effectiveness can vary greatly among users (heterogeneous treatment effects). Simply offering the largest incentive to everyone or using a greedy approach can lead to wasted budget and suboptimal returns. The core challenge is to determine the optimal amount and type of incentive to offer to each individual user, given a fixed overall budget, to maximize the platform's return on investment. This is framed as the "budget-constrained treatment selection" (BTS) problem. Existing methods struggle with the scale of modern platforms and often fail to accurately compare treatment effects across different incentive levels.

Methods

The paper proposes a two-pronged approach:

  1. Large-Scale Budget-Constrained Causal Forest (LBCF):
    • Unified Discriminative Causal Forest (UDCF): Unlike previous methods that train separate models for each incentive level (leading to incomparable treatment effect estimates), UDCF builds a single causal forest. This unified model allows for direct comparison of treatment effects across multiple incentive levels within the same feature space. It uses novel splitting criteria (Inter and Intra splits) to encourage both inter-node and intra-node heterogeneity, crucial for effective treatment selection.
  2. Dual Gradient Bisection (DGB): To address the computational challenges of optimizing incentive allocation across millions of users and potentially many incentive options, the authors propose DGB. This is an efficient, parallelizable algorithm that leverages the convexity of the problem's dual formulation to find the optimal budget allocation. It's designed to work well with distributed computing frameworks.
  3. Percentage Mean Gain (PMG) Policy Evaluation: A novel offline evaluation metric is introduced to better assess the performance of BTS algorithms using data from Randomized Control Trials (RCTs). PMG aims to provide a more holistic measure of a policy's effectiveness compared to existing metrics that may not accurately reflect the true outcome or budget usage.

Datasets

  • Synthetic Dataset: Used for simulation analysis, generated using methods from prior work ([26]) with varying noise levels.
  • Real-world RCT Dataset: Collected from a large-scale video streaming platform. This dataset contains user engagement data (campaign engagement duration) across seven different incentive groups (multi-treatment) and a control group. The paper notes that while the full dataset is not publicly released due to privacy concerns, a subset is available for code testing.

Key Insights and Ideas

  • Unified Causal Forests are Crucial for Multi-Treatment Comparison: The paper highlights a critical flaw in prior multi-treatment approaches: training separate models leads to incomparable treatment effect estimates. LBCF's unified model directly addresses this, enabling more accurate comparisons and better decision-making.
  • Greedy Treatment Selection is Sub-optimal: The authors demonstrate with an example (Table 1) that simply picking the treatment with the highest individual ROI or uplift for each user is not optimal when a global budget constraint is in place. This underscores the need for a more sophisticated optimization strategy.
  • Efficient Optimization for Large-Scale Systems: Traditional optimization methods for knapsack-like problems are not designed for modern distributed systems. DGB offers a scalable and efficient solution, making budget-constrained optimization feasible for platforms with millions of users.
  • A Better Way to Evaluate BTS Policies: The PMG metric is a significant contribution, offering a more robust way to compare different incentive allocation strategies offline, which is a persistent challenge in this domain.

Key Results

  • Simulation Analysis: LBCF consistently outperformed baseline methods (CTS, ED, Chi, CT.ST, CF.DT) across various noise levels, demonstrating its robustness.
  • Offline Test: LBCF achieved the largest Percentage Mean Gain (PMG) for user campaign engagement duration across different budget configurations on the real-world dataset.
  • Online AB Test: In a real-world deployment on a large-scale video platform, LBCF achieved a significant percentage gain in campaign engagement duration, consistently outperforming baseline methods like CT.ST and CF.DT. At the end of a 15-day test, LBCF showed a 7.79% gain, compared to 6.87% for CT.ST and 5.31% for CF.DT.
  • Scalability: The LBCF algorithm is currently serving hundreds of millions of users on the platform, demonstrating its practical scalability.

Limitations and Future Work

  • SUTVA Assumption: The authors acknowledge that the SUTVA (Stable Unit Treatment Value Assumption) assumption of independence between users might not strictly hold, as users might share incentive information. They mention that recent work exists to address such dependencies.
  • Adding More Constraints: The authors suggest future work could involve incorporating additional constraints into the optimization task, such as user experience, and developing efficient solutions for these more complex scenarios.

Summary updated

Abstract

Offering incentives (e.g., coupons at Amazon, discounts at Uber and video bonuses at Tiktok) to user is a common strategy used by online platforms to increase user engagement and platform revenue. Despite its proven effectiveness, these marketing incentives incur an inevitable cost and might result in a low ROI (Return on Investment) if not used properly. On the other hand, different users respond differently to these incentives, for instance, some users never buy certain products without coupons, while others do anyway. Thus, how to select the right amount of incentives (i.e. treatment) to each user under budget constraints is an important research problem with great practical implications. In this paper, we call such problem as a budget-constrained treatment selection (BTS) problem.The challenge is how to efficiently solve BTS problem on a Large-Scale dataset and achieve improved results over the existing techniques. We propose a novel tree-based treatment selection technique under budget constraints, called Large-Scale Budget-Constrained Causal Forest (LBCF) algorithm, which is also an efficient treatment selection algorithm suitable for modern distributed computing systems. A novel offline evaluation method is also proposed to overcome an intrinsic challenge in assessing solutions’ performance for BTS problem in randomized control trials (RCT) data. We deploy our approach in a real-world scenario on a large-scale video platform, where the platform gives away bonuses in order to increase users’ campaign engagement duration. The simulation analysis, offline and online experiments all show that our method outperforms various tree-based state-of-the-art baselines 1. The proposed approach is currently serving over hundreds of millions of users on the platform and achieves one of the most tremendous improvements over these months.
BibTeX
@inproceedings{ai2022lbcf,
  author = {Meng Ai and Biao Li and Heyang Gong and Qingwei Yu and Shengjie Xue and Yuan Zhang and Yunzhou Zhang and Peng Jiang},
  title = {{LBCF: A Large-Scale Budget-Constrained Causal Forest Algorithm}},
  booktitle = {The Web Conference},
  year = {2022},
  url = {https://openreview.net/forum?id=RcITUhIEzR},
}
Figure