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

1 INTRODUCTION

• Marketing incentives must be allocated under budget constraints because users respond differently, and the objective is to maximize overall return.Examples include users who need coupons to buy and users who would buy without them.Source: §1 · p. 1
• The large-scale challenge is improving treatment selection efficiently; greedy policies choose maximal estimated effects but can be suboptimal under a budget.The introduction also notes that existing tree-based techniques fall into two categories.Source: §1 · pp. 1–2
• Tu et al.’s multi-model approach has large-scale optimization and comparability limitations: it favors cohort-level optimization, and treatment estimates may use different feature spaces.Maintaining and serving multiple binary causal forest models is also computationally demanding.Source: §1 · p. 2
• LBCF combines member-level treatment-effect estimation with budget-constrained optimization, using a unified model and parallelizable Dual Gradient Bisection for the optimization task.The method formulates optimization as a multi-choice knapsack problem and reports O(N) time complexity for DGB.Source: §1 · p. 2, Figure 1 · p. 3
• PMG is proposed for more holistic offline BTS evaluation, addressing limitations in existing metrics for multi-treatment policies and evaluation under a fixed budget.The paper also introduces simulation, real-world offline, and online A/B tests; the offline data records engagement duration across seven randomly enrolled incentive groups.Source: §1 · p. 2
• At least 0.9% improvement in campaign engagement duration over baseline methods under the same budget; simulations also show good performance across noise levels.The paper reports effectiveness and scalability across simulation, offline, and online experiments.Source: §1 · p. 2

2 PROBLEM FORMULATION

• The formulation uses features, treatment assignments, and outcomes from an RCT, with treatment effects expressed through potential outcomes and CATE.Treatments are mutually exclusive, and the control group is T = 0.Source: §2 · p. 3
• It assumes treatment assignment is as-if random after controlling for features, and that treatment costs are known while control has no cost.SUTVA is also assumed for treatment-effect estimation; the total budget is denoted B.Source: §2 · p. 3
• The objective is to maximize total return by selecting treatments for users under a manually set global budget.The policy assigns treatment j to user i through binary decision variables z_ij.Source: §2 · p. 3

3 POLICY EVALUATION

• AUUC-style evaluation ranks users by maximal predicted treatment effect, although a policy need not select that treatment.The maximal-effect treatment may not be optimal for the policy.Source: §3 · p. 3
• Expected Outcome uses only users whose RCT and policy treatments match, so policies with different consumed budgets are not comparable.It therefore does not estimate the mean outcome across all RCT users.Source: §3 · p. 3
• PMG is proposed for BTS evaluation in response to limitations in existing metrics.It estimates policy outcome gain relative to the control-group mean.Source: §3 · pp. 3–4
• RCT treatment is randomly assigned, policy treatment is selected by the policy, S(j) is their overlap, and A(j) contains samples assigned policy treatment j.The paper uses these subsets to distinguish observed outcomes from policy-assigned outcomes.Source: §3 · p. 3
• Only outcomes in the overlap S(j) are observed under policy treatment, and RCT randomization makes that overlap a random subset of A(j).The observed overlap mean is an unbiased estimate of the mean outcome for samples in A(j).Source: §3 · p. 4
• PMG aggregates estimated outcomes across policy subsets and expresses the policy's mean gain relative to the control-group mean.The paper describes PMG as a plug-in estimator of the relative difference between policy and control outcomes.Source: §3 · p. 4

4.1.1 Uplift Random Forest.

• With budget B = 6, the ROI-greedy policy yields total treatment effect 92, while an alternative allocation yields 98 under the same budget.The alternative changes treatment for user1 and assigns no treatment to user4, leaving other assignments unchanged.Source: §4.1.1 · p. 4

4.1.2 Optimal Treatment Selection Algorithm.

• Prior approaches either use cohort-level optimization at large scale or train separate binary forests, which are computationally cumbersome and can place users in incompatible feature spaces.Tu et al. suggested cohort-level rather than member-level optimization because large-scale linear-programming solvers were unavailable.Source: §4.1.2 · p. 5

4.2 Proposed LBCF Algorithm

• LBCF separates BTS into member-level CATE estimation with one model and optimal treatment selection through a constrained optimization problem.The approach is proposed to address limitations of existing methods for large-scale BTS.Source: §4.2 · p. 5, §4.2.1 · p. 5

4.2.1 Unified Discriminative Causal Forest.

• UDCF builds one forest with shared split rules across treatments and distinguishes both inter-node and intra-node treatment-effect heterogeneity.Its two-step criterion first selects top m candidates using the Inter split, then chooses among them using the Intra split.Source: §4.2.1 · p. 5
• After constructing UDCF, the method estimates treatment effects by fitting treatment and outcome in a weighted least-squares regression, weighted by sample similarity.The termination rule is the same as in binary causal forests.Source: §4.2.1 · p. 5

4.2.2 Budget-constrained Optimization.

• For budget-constrained optimization, LBCF decomposes the problem using linear relaxation and duality, then applies dual gradient bisection to solve the convex Lagrange dual.The proposed bisection method avoids selecting an initial learning rate for dual gradient descent.Source: §4.2.2 · p. 6

4.2.3 Large-Scale System and Parallelization.

• The forest and the optimization gradient can be parallelized across treatment groups and users, respectively, on distributed systems.The paper describes UDCF as one model trained on K treatment groups and the gradient calculation as N independent subproblems.Source: §4.2.3 · p. 6

4.2.4 Overall Algorithm.

• The overall LBCF workflow takes RCT samples, estimates member-level effects with UDCF, and solves the member-level budget-constrained optimization with DGB.Source: §4.2.4 · p. 7

5 EVALUATION

• The evaluation comprises simulation analysis, a real-world offline test, and an online A/B test.Simulation uses 80,000 samples with three treatments; the offline video-app RCT contains over 100,000 app-visit instances.Source: §5 · p. 7, §5.1 · p. 7, §5.2 · p. 7

5.1 Simulation Analysis

• LBCF outperforms every listed baseline at every uncertainty weight on the synthetic RCT datasets.The comparison uses mean ITE normalized by the control group's average outcome.Source: Figure 4 · p. 7, §5.1 · p. 7

5.2 Offline Test

• LBCF achieves the largest PMG for campaign engagement duration under every tested budget configuration.This matches the simulation-analysis result.Source: Figure 5 · p. 7, §5.2 · p. 7

5.3 Online AB Test

• At the last day, LBCF reaches 7.79% gain, above CT.ST at 6.87% and CF.DT (MBCF.DGB) at 5.31%.After the first few days, LBCF consistently provides high percentage gain.Source: Figure 6 · p. 8, §5.3 · p. 8

6 RELATED WORK

• Tree-based baselines either use potentially suboptimal greedy selection under a budget or lack a shared feature space for uplift estimation and may require multiple models.The cited methods include ED, Chi, CTS, CT.ST, and CF.DT.Source: §6 · p. 8
• Traditional exact and heuristic MCKP algorithms were not designed for distributed computing and cannot handle very large datasets with billions of decision variables.MCKP is described as NP-hard.Source: §6 · p. 8
• AUUC, Qini-curve, and AUCC require similarly scored groups to exhibit similar features, while expected outcome evaluation excludes some RCT users, making budgets differ across policies.The paper notes that policies evaluated under different consumed budgets are not comparable.Source: §6 · p. 8

7 DISCUSSION

• SUTVA's independence condition does not strictly hold because app users may share incentive information, but its single-level condition holds for discrete treatments of equal incentive amounts.The authors identify adding constraints such as user experience, and solving the task efficiently at large scale, as future work.Source: §7 · p. 8
• The authors propose adding constraints such as user experience and developing an efficient solution for the resulting large-scale optimization task.Source: §7 · p. 8

A SUPPLEMENTARY MATERIALS

• Python, C++, and R code are provided for running the offline experiments, alongside a proof of the convexity of L(λ).The proof is in Section 4.2.2; the code supports simulation and offline evaluation reproduction.Source: A SUPPLEMENTARY MATERIALS · p. 9
• The supplementary attachment directory organizes the uploaded data, code files, and images.Source: A SUPPLEMENTARY MATERIALS · p. 9, Figure 7 · p. 9

• L(λ) is a convex function of λ.Source: §A.1 · p. 9
• L(λ) is obtained by combining linear functions, including constants, through max and addition operations.Source: §A.1 · p. 9
• Convexity follows recursively because max and addition preserve convexity.Source: §A.1 · p. 9

• Synthetic data are generated from a causal DAG with heterogeneous, unobserved, treatment, outcome, and cost variables.The DAG is self-defined and follows the method of Tu et al..Source: §A.2 · pp. 9–10, Figure 8 · p. 10
• The model folder contains LBCF and five baseline methods for simulation and offline testing.Source: §A.2 · p. 10
• Evaluation code uses ITE measurement for synthetic data and the PMG method for offline testing on real-world RCT data.Source: §A.2 · p. 10

A.3 Data

• Synthetic training and testing data span four uncertainty levels, with the unobserved variable removed from training data.Source: §A.3 · p. 10
• The real-world RCT dataset contains over 100 K app-visit instances from seven randomly enrolled incentive groups with different bonus levels.The outcome is users’ campaign engagement duration.Source: §A.3 · p. 10
• The full real-world dataset used in offline testing is not disclosed pending authorization; the provided encrypted 2,000-sample subset is not for reproducing the results.Source: §A.3 · p. 10

A.4 Utilities

• Utilities include DGB implementation, synthetic and real-world evaluation scripts, and notebooks detailing both evaluations.Source: §A.4 · p. 10