An End-to-End Framework for Marketing Effectiveness Optimization under Budget Constraint

Starting from a common objective, many budget allocation methods have been proposed. Early methods (Guelman et al., 2015; Zhao et al., 2017; Zhao and Harinen, 2019) often select the amount of incentives for users heuristically after obtaining the heterogeneous treatment effects estimation. However, lacking an explicit optimization problem formulation could make these methods less effective in maximizing the marketing goal.

A popular way of allocating budget is to follow a two-stage paradigm (Zhao et al., 2019; Makhijani et al., 2019; Goldenberg et al., 2020; Tu et al., 2021; Ai et al., 2022; Albert and Goldenberg, 2022): in the first stage uplift models are used to predict the treatment effects, and in the second stage integer programming is invoked to find the optimal allocation. For instance, Zhao et al. (2019) propose to use a logit response model (Phillips, 2021) to predict treatment effects and then obtain the optimal allocation via root-finding for KKT conditions. Later, Tu et al. (2021) introduce various advanced estimators (including Causal Tree (Athey and Imbens, 2016), Causal Forest (Wager and Athey, 2018) and Meta-Learners (Sołtys et al., 2015; Künzel et al., 2019)) to estimate the heterogeneous effects. The second stage has also received much research attention. Makhijani et al. (2019) formulate the marketing goal as a Min-Cost Flow network optimization problem for better expressivity. More recently, Ai et al. (2022); Albert and Goldenberg (2022) use MCKP to represent the budget allocation problem in the discrete case and develop efficient solvers based on Lagrangian duality. Though effective, owing to the misalignment between the objectives of these two stages, solutions from these two-stage methods could be suboptimal.

Several methods have also been proposed to directly learn the optimal budget assignment policy (Xiao et al., 2019; Du et al., 2019; Goldenberg et al., 2020; Zou et al., 2020; Zhang et al., 2021; Zhou et al., 2023). Xiao et al. (2019); Zhang et al. (2021) develop reinforcement learning solutions based on constrained Markov decision process to directly learn an optimal policy. However, learning such complicated policies in a pure model-free black-box approach without exploiting the causal structures could suffer from sample inefficiency. Du et al. (2019); Zou et al. (2020); Goldenberg et al. (2020) propose to directly learn the ratios between values and costs in the binary treatment setting, and treatments could be first applied to users with higher scores. Later, a contemporary work (Zhou et al., 2023) proves the proposed loss in (Du et al., 2019; Zou et al., 2020) cannot achieve the correct rank when the loss converges. Furthermore, the method proposed in (Goldenberg et al., 2020) is applicable only if the budget constraint is that monetary ROI$\geq 0$, which is not flexible enough for many marketing campaigns in online Internet platforms. Zhou et al. (2023) extend the decision-focused learning idea to the multiple-treatments setting and develop a loss function to learn decision factors for MCKP solutions. However, the proposed method relies on the assumption of diminishing marginal utility, which is often not strictly hold in practice.

Estimating the gradients of a black-box function has been extensively studied for decades and widely used in the field of reinforcement learning (Sutton et al., 1999) and adversarial attack (Ilyas et al., 2018; Guo et al., 2019). The simplest approach is the finite-difference strategy, i.e., calculating the gradients by definition. The finite-difference strategy could give accurate gradients but might be computationally expensive if the independent variables of the black-box function have high dimensionalities. An alternative way of gradient estimation is natural evolution strategies (NES) (Wierstra et al., 2014), which generate several search directions to probe local geometrics of the black-box function and estimate the gradients based on sampled search directions. NES is generally more computationally efficient than the finite-difference strategy, but the estimated gradients are noisy. Antithetic sampling (Salimans et al., 2017) could be employed to reduce the variance of NES gradient estimation. In this paper, we present both finite-difference- and NES-based algorithms for gradient estimation.

In most online Internet platforms, randomized controlled trials (RCT) could be easily deployed and thus a decent amount of RCT data could usually be collected at an acceptable cost in practice. As such, in this paper, we focus on training models using RCT data for simplicity and leave the exploration on exploiting observational data to future works. We use $u_{i}\in\mathbb{R}^{d}$ to denote the features for $i$-th user in a certain user group. The term “user group” might refer to a group of RCT training users or a group of non-RCT users whose budgets are allocated by our model. The exact meaning of the term “user group” should be easily inferred from the context in this paper. We set $K$ mutually exclusive treatments, and each treatment represents a certain amount of incentives (e.g., cash bonus, or discount levels) assigned to the user. The treatment assigned to user $u_{i}$ in RCT is denoted by $t_{i}\in\{1,\ldots K\}$, and the user would have a binary response $y_{i}\in\{0,1\}$ after receiving the treatment $t_{i}$. The response shall be the business goal we want to maximize. Meanwhile, applying treatment $t_{i}$ to user $u_{i}$ would induce a non-negative cost $z_{i}\geq 0$. Each sample from an RCT dataset consists of a quadruple $(u_{i},t_{i},y_{i},z_{i})$.

As discussed, a lot of efforts have been devoted to two-stage budget allocation methods (Zhao et al., 2019; Makhijani et al., 2019; Goldenberg et al., 2020; Tu et al., 2021; Ai et al., 2022; Albert and Goldenberg, 2022). In this section, we briefly introduce common components in two-stage budget allocation methods. In the first stage, two-stage methods seek to build an uplift model to predict the uplifts of responses under all possible treatments. In principle, any uplift models could be applied in this stage, such as S-Learners (Künzel et al., 2019), R-Learners (Nie and Wager, 2021), Uplift Trees (Rzepakowski and Jaroszewicz, 2012), Causal Forests (Athey and Imbens, 2016), GRFs (Athey et al., 2019), ORFs (Oprescu et al., 2019) and LBCFs (Ai et al., 2022). Although some tree-based uplift models like GRFs (Athey et al., 2019) and ORFs (Oprescu et al., 2019) are unbiased uplift estimators with theoretical convergence guarantees, the splitting criteria in their tree-growing process are not flexible enough to be easily extended and integrated with our proposed regularizers. Thus in this paper, we restrict our attention to using S-Leaners with DNNs (Krizhevsky et al., 2012) as base models, just like (Zhou et al., 2023). A typical DNN S-Learner model $f$ would take the user feature $u_{i}$ as input and feed $u_{i}$ into a multi-layer perceptron (MLP) with several fully-connected layers to obtain the base hidden representation $h_{i}$ of the user $u_{i}$, and then the model $f$ would branch $2K$ headers (i.e., shadow MLPs) on the top of the base hidden representation $h_{i}$ to predict responses and costs for every possible treatment, where each treatment corresponds two headers (one header for response and the other header for cost). In general, any DNN architecture could be used in this stage provided the DNN model takes $u_{i}$ as input and outputs two $K$-dimensional vectors for predicted responses/costs under all possible treatments, and in this paper, we use the simple architecture described above and leave the exploration on DNN architectures to future works. Let $\theta$ exhaustively collects learnable parameters of the above DNN S-Leaner $f$, and let $f_{v}\left(u_{i};\theta\right)\in\mathbb{R}^{K}$ and $f_{c}\left(u_{i};\theta\right)\in\mathbb{R}^{K}$ denote the predicted responses/costs of $f$. The predicted response and cost of applying treatment $j$ to user $u_{i}$ are denoted by $f_{v}\left(u_{i};\theta\right)_{j}$ and $f_{c}\left(u_{i};\theta\right)_{j}$, respectively. Given a training set with $N$ RCT users, the DNN S-Learner is trained in the first stage by minimizing the following objective:

where $L_{\textrm{CE}}(\cdot,\cdot)$ is the cross entropy loss for the binary response, and $L_{\textrm{C}}(\cdot,\cdot)$ is a suitable loss for the cost target. The formulation of $L_{\textrm{C}}(\cdot,\cdot)$ could vary from one dataset to another. For example, on a dataset where the cost label $z_{i}$ is categorical, it could be reasonable to use a cross entropy-loss for $L_{\textrm{C}}(\cdot,\cdot)$, while on another dataset where the cost label $z_{i}$ is continuous, a regression loss would be more appropriate for $L_{\textrm{C}}(\cdot,\cdot)$. After minimizing the objective $L_{\textrm{SL}}\left(\theta\right)$ in Equation (1), given a feature vector of a user, the well-trained DNN S-Leaner model should predict unbiased estimations of expected responses/costs of this user under all possible treatments.

In the second stage, two-stage methods usually keep the uplift model $f$ fixed and use a multiple choice knapsack problem (MCKP) (Kellerer et al., 2004) formulation to maximize the marketing goal under the budget constraint. Suppose the total budget for a group of $M$ users is set to $T$. The expected response of $u_{i}$ under treatment $j$ is denoted by $v_{ij}\in[0,1]$, and $v_{ij}$ could be predicted by the well-trained DNN S-Learner from the first stage: $v_{ij}=f_{v}\left(u_{i};\theta\right)_{j}$. Let $c_{ij}\geq 0$ denotes the expected cost of $u_{i}$ under treatment $j$, and $c_{ij}$ could also be similarily predicted by $c_{ij}=f_{c}\left(u_{i};\theta\right)_{j}$. Using the above coefficients and constants, two-stage methods typically construct the following MCKP to find the optimal personalized treatment assignment solution $x\in\{0,1\}^{M\times K}$ which could maximize the expected marketing goal under a given budget constraint:

where the $M\times K$ matrix $x$ represents the budget allocation solution for $M$ users. All entries in $x$ are either 0 or 1. Each row of $x$ has exactly one entry with value 1, and $x_{ij}=1$ means user $u_{i}$ should be assigned with treatment $j$. Although MCKP is proven to be NP-Hard (Kellerer et al., 2004), in practice we can approximately solve it by first making linear relaxation to get rid of the integer constraints and then converting it to the dual problem (Ai et al., 2022; Zhou et al., 2023). Specifically, the dual problem of MCKP has only one scalar variable $\alpha$ under a constraint that $\alpha\geq 0$ (Kellerer et al., 2004), and the objective of dual problem is given by

The dual problem (3) could be efficiently solved via bisection methods such as Dyer-Zemel algorithm (Zemel, 1984) or dual gradient descent (Ai et al., 2022; Zhou et al., 2023). Once the optimal dual solution $\alpha^{*}$ is obtained, the optimal solution $x^{*}$ of the primal MCKP (2) could be given by KKT conditions:

Interested readers can read the insightful paper (Kellerer et al., 2004) for more details about solving MCKPs.

As discussed in Section 1, our core idea for end-to-end training is to construct a regularizer to represent the marketing goal (i.e., the expected response under a certain budget constraint) and optimize it efficiently using gradient estimation techniques. Suppose we have a batch of $B$ RCT users from the training set (we set the batch size to $B=10,000$ in all experiments), the S-Learner model could predict responses for each user and we shall stack their predicted responses into a $B\times K$ matrix $v$ to simplify the notations, and the costs of applying arbitrary treatments to these users could also be stacked into a $B\times K$ matrix $c$ in a similar way. In this section, we present our solution to design a function $Q(v,c)$ to map the predicted response matrix $v$ and cost matrix $c$ to the marketing goal and integrate $Q(v,c)$ into the training objective of the S-Leaner model as a regularizer.

We use Expected Outcome Metric (EOM) method (Zhao et al., 2017; Ai et al., 2022; Zhou et al., 2023) to construct $Q(v,c)$. Concretely, starting from any dual feasible solution $\alpha\geq 0$, we can obtain the corresponding budget allocation solution $x$ via KKT conditions in Equation (4). Since $\alpha$ is the Lagrangian multiplier associated with the budget constraint in the primal MCKP (2), we know from complementary slackness conditions that $x$ must be the primal optimal solution for another MCKP in which the total budget $T$ is set to be $T=\sum_{i=1}^{M}\sum_{j=1}^{K}c_{ij}x_{ij}$ while other coefficients $c$ and $v$ remain unchanged. In other words, given any $\alpha\geq 0$, the corresponding $x$ is the optimal budget allocation solution under a certain total budget constraint. Using the budget allocation solution $x$, we can find the set of user indices (denoted by $\mathcal{S}_{\alpha}$) in the $B$ RCT users whose treatment on the RCT data is equal to the assigned treatment in $x$:

where $t_{i}$ is the treatment applied to user $u_{i}$ in the RCT data. Based on the set $\mathcal{S}_{\alpha}$, the per-capita response $V\left(v,c,\alpha\right)\in\mathbb{R}_{+}$ and per-capita cost $C\left(v,c,\alpha\right)\in\mathbb{R}_{+}$ could be empirically estimated by:

where $y_{i}\in\{0,1\}$ and $z_{i}\in\mathbb{R}_{+}$ denote the response and cost of user $u_{i}$ in the RCT data respectively, and $\left\lvert\mathcal{S}_{\alpha}\right\rvert$ represents the cardinality of set $\mathcal{S}_{\alpha}$.

As discussed, the obtained $x$ is the optimal budget allocation solution for these $B$ users under a certain budget constraint, and thus we could tune the total budget by adjusting the value of dual feasible solution $\alpha$ (Kellerer et al., 2004). As such, we could start from $\alpha=0$ and gradually increase its value, and the total budget in MCKP would be accordingly decreased. In this process, we could plot empirical per-capita cost $C\left(v,c,\cdot\right)$ and empirical per-capita response $V\left(v,c,\cdot\right)$ in the same figure ¹¹1Note this curve might not be strictly monotonically increasing since the empirical estimation process is noisy. to illustrate the users’ expected responses under different costs, and an example figure is shown in Figure 1. Based on this curve, intuitively we can use bisection search to find a suitable $\alpha^{\prime}$ such that the empirical per-capita cost $C\left(v,c,\alpha^{\prime}\right)\in\mathbb{R}_{+}$ equals the given per-capita budget $\frac{T}{\left\lvert\mathcal{S}_{\alpha}\right\rvert}$ in the original MCKP, and define $Q(v,c)$ as the empirical per-capita response at that $\alpha^{\prime}$: $Q(v,c)=V\left(v,c,\alpha^{\prime}\right)$. All details of evaluating $Q(v,c)$ given $v$ and $c$ are summarized in Algorithm 1.

The bisection process in Algorithm 1 could also be extended to $n$-ary search by adding more middle points in the search interval in each iteration. Although the bisection method and the $n$-ary search method share the same asymptotic time complexity, in modern GPU devices the $n$-ary search method could usually run faster if the implementation is properly vectorized.

Given a batch of training data with $B$ RCT users, instead of optimizing the original objective $L_{\textrm{SL}}\left(\theta\right)$ in Equation (1) for S-Learner, we could directly optimize the marketing effectiveness by minimizing the following regularized objective $L_{R}(\theta)$ in this batch:

where $L_{\textrm{SL}}(\theta)$ is the original loss in Equation (1) on this batch, and $\lambda>0$ is a scaling factor that balances the importance of the original objective $L_{\textrm{SL}}\left(\theta\right)$ and the regularizer $Q(v,c)$.

If the gradient $\frac{\partial Q(v,c)}{\partial v}$ and $\frac{\partial Q(v,c)}{\partial c}$ could be obtained (see Section 3.4), we can integrate the gradient into the back-propagation process (see Section 3.5). As such, the regularizer $Q(v,c)$ could be jointly optimized with the original learning objective $L_{\textrm{SL}}(\theta)$ and the whole objective $L_{R}(\theta)$ in Equation (7) could be efficiently solved in an end-to-end flavor. This endows the trained model with an ability to directly learn from the marketing goal and further maximize it, in a principled way.

As shown in Algorithm 1, the construction of regularizer $Q(v,c)$ involves many non-differentiable operations. Thus if we naïvely implement Algorithm 1 as a computational graph in modern machine learning libraries such as TensorFlow (Abadi et al., 2015) and PyTorch (Paszke et al., 2019), the automatic differentiation mechanism would not generate correct gradients. In this section, we present our solution to overcome this challenge and calculate the (estimation of) gradient $\frac{\partial Q(v,c)}{\partial v}$ and $\frac{\partial Q(v,c)}{\partial c}$. We treat $Q(v,c)$ as a black-box function, and use two strategies to estimate the gradients: 1) finite-difference strategy in Section 3.4.1, and 2) natural evolution strategies (NES) (Wierstra et al., 2014) in Section 3.4.2. For clarity of presentation, in this section, we would present the detailed solution for estimating $\frac{\partial Q(v,c)}{\partial v}$ only, and estimating for $\frac{\partial Q(v,c)}{\partial c}$ could be similarly performed.

In this section, we present our solution to train the DNN model to maximize the marketing goal, by optimizing the regularized objective $L_{R}(\theta)$ in Equation (7). Common gradient descent based optimizers such as SGD or Adam (Kingma and Ba, 2015) would require the gradients w.r.t. DNN model parameter (i.e., $\frac{\partial Q(v,c)}{\partial\theta}$) to update $\theta$, while in Section 3.4 we only have $\frac{\partial Q(v,c)}{\partial v}$ and $\frac{\partial Q(v,c)}{\partial c}$. Thus, a back-propagation step which converts $\frac{\partial Q(v,c)}{\partial v}$ and $\frac{\partial Q(v,c)}{\partial c}$ to $\frac{\partial Q(v,c)}{\partial\theta}$ is required. To this end, we design the following surrogate loss $L_{S}(\theta)$:

where $\lambda>0$ is a scaling factor that balances the importance of the original objective and the regularizer, $\operatorname{Tr}[\cdot]$ is the matrix trace operator, $v^{\mathrm{T}}$ and $c^{\mathrm{T}}$ is the transpose of matrix $v$ and $c$ respectively, and $\texttt{stop\_gradient}(\cdot)$ is the operator to treat a certain variable as a constant and avoid back-propagation through it.³³3In TensorFlow this could be achieved via tf.stop_gradient(), and in PyTorch this could be achieved by tensor.detach(). Unlike the regularizer part of $L_{R}(\theta)$ which is cumbersome to handle, the regularizer part of $L_{S}(\theta)$ is a simple linear combination of elements in matrix $v$ and $c$, which are output values from the last layer of the DNN model. As such, the gradient of $L_{S}(\theta)$ w.r.t. $\theta$ could be easily obtained by running a standard back-propagation over the DNN model. Furthermore, it could be verified that $L_{S}(\theta)$ and $L_{R}(\theta)$ shares the same first order gradient: $\frac{\partial L_{S}(\theta)}{\partial\theta}=\frac{\partial L_{R}(\theta)}{\partial\theta}$. Thus, with the help of the surrogate loss $L_{S}(\theta)$, we could effectively optimize the original regularized objective $L_{R}(\theta)$, and the well-trained DNN model shall learn to maximize the marketing goal in an end-to-end manner. Algorithm 2 summarizes all details for training.

We evaluate the efficacy of our method in three different datasets:

• •

  Synthetic dataset. To elaborate on key components of our idea (i.e., EOM and gradient estimation), we generate a synthetic dataset consisting of 10,000 RCT users. We set four different treatments (i.e., $K=4$), and the treatment $t_{i}$ applied to the $i$-th user in RCT is randomly sampled from these four treatments with equal probabilities. We assume the $i$-th user has a four-dimensional ground truth vector $v^{\textrm{gt}}_{i}\in[0,1]^{4}$, where the $j$-th element in $v^{\textrm{gt}}_{i}$ (denoted by $v^{\textrm{gt}}_{ij}$) represents the probability of $y_{i}=1$ when treatment $j$ is applied to that user. We use the following three steps to generate $v^{\textrm{gt}}_{i}$: 1) the first element of $v^{\textrm{gt}}_{i}$ (i.e., $v^{\textrm{gt}}_{i1}$) is sampled from the uniform distribution in $[0,0.1]$, 2) to determine the remaining elements of $v^{\textrm{gt}}_{i}$, we sample three i.i.d. numbers from the uniform distribution in $[0,0.2]$ and sort these three numbers in descending order (denoted by $0.2\geq k_{1}\geq k_{2}\geq k_{3}\geq 0$), and 2) these three numbers are used as incremental values of $v^{\textrm{gt}}$: let $v^{\textrm{gt}}_{ij}=v^{\textrm{gt}}_{i(j-1)}+k_{j-1}$, where $j=2,3,4$. Once the four-dimensional ground truth vector $v^{\textrm{gt}}_{i}$ is generated, we get the $t_{i}$-th element of the $v^{\textrm{gt}}_{i}$ (denoted by $v^{\textrm{gt}}_{i(t_{i})}$) and sample the binary response $y_{i}$ of the $i$-th user from the Bernoulli distribution with probability $v^{\textrm{gt}}_{i(t_{i})}$. We assume the cost of applying the $j$-th treatment to any user is $j$. In other words, we set the $\left(i,j\right)$-th element in ground-truth cost matrix $c^{\textrm{gt}}$ to be $c^{\textrm{gt}}_{ij}=j$, where $j=1,2,3,4$. The synthetic dataset is designed for illustrating the effectiveness of EOM and gradient estimation, thus the features of users are omitted in this dataset.

• •

  CRITEO-UPLIFT v2 (Diemert et al., 2018). This publicly available dataset is designed for evaluating models for uplift modeling. This dataset contains 13.9 million samples which are collected from an RCT. Each sample has 12 dense features, one binary treatment indicator, and two binary labels: visit and conversion. In this dataset, treatment is defined as whether the user is targeted by advertising or not, and labels are defined as positive if the user visited/converted on the advertiser’s website during a test period of two weeks. To evaluate different budget allocation methods, we follow (Zhou et al., 2023) and use the visit/conversion label as the cost/value respectively. We compare the performance of our proposed method with state-of-the-arts in CRITEO-UPLIFT v2 to demonstrate the effectiveness of our method.

• •

  KUAISHOU-PRODUCE-COIN. Produce Coin is a common marketing campaign to incentivize short video creators to upload more short videos in Kuaishou. In this campaign, we provide a prized task to each short video creator on the Kuaishou platform. Concretely, in each task, if a creator uploads a video within 24 hours, he/she will receive a certain amount of coins as a reward. Each creator could see the number of coins he/she could possibly obtain, and if the number seems attractive enough the creator might finish the task to collect these coins. We manually select 30 distinct levels of coins (e.g., 1 coin, 2 coins, $\ldots$), and each creator will be assigned one of these 30 levels. The amount of coins could be personalized to maximize the total amount of video uploads under the constraint that the total amount of coins does not exceed a certain limit. In this dataset, we define treatment as the level of coins, thus we have $K=30$ treatments. For the user (i.e., creator) $u_{i}$, the response $y_{i}$ would be $y_{i}=1$ if the user has successfully completed the task, and otherwise, we set $y_{i}=0$. The cost of applying a treatment to $u_{i}$ would be defined as the real number of coins sent to $u_{i}$: if $y_{i}=1$ we set the cost to the number of coins corresponding to the assigned treatment, and if $y_{i}=0$ we set the cost to zero. To collect this dataset we conduct an RCT for one week. In this RCT, we randomly sample one reward level from predefined 30 levels with equal probabilities for each user as the treatment and collect the response/cost label from the logs. This dataset contains 82.4 million samples, and we deploy several models trained on this dataset in the Kuaishou platform to evaluate the online performance of different methods. To protect data privacy, we normalize the per-capita response/cost and report the normalized values on all tables and figures.

We use the following evaluation metrics to evaluate and compare the performance of different methods:

• •

  AUCC (Area Under the Cost Curve) in (Du et al., 2019). AUCC is commonly used in existing literatures (Du et al., 2019; Ai et al., 2022; Zhou et al., 2023) to evaluate the ranking performance of uplift models in the two-treatment setting. Interested readers can check the original paper (Du et al., 2019) for more details about the evaluation process of AUCC. In this paper, we use AUCC to compare the performance of different methods in CRITEO-UPLIFT v2.

• •

  EOM (Expected Outcome Metric). EOM or similar metric is also commonly used in existing literatures (Ai et al., 2022; Zhou et al., 2023) to empirically estimate the expected outcome (e.g., per-capita response or per-capita cost) for arbitrary budget allocation policy. EOM can make an unbiased estimation of any outcome, provided that outcome is calculable given a budget allocation solution on RCT data. Thus, EOM is more flexible than AUCC in practice. In this paper, we use EOM in the synthetic dataset and the KUAISHOU-PRODUCE-COIN dataset to evaluate different budget allocation methods, and technical details of EOM have been introduced in Equation (5) and Equation (6) in Section 3.3.

Implementation details on different datasets are shown as follows:

• •

  The synthetic dataset. To illustrate the basic idea of EOM and gradient estimation in our proposed method, we first generate a cost matrix $c\in\mathbb{R}_{+}^{10,000\times 5}$ and a value matrix $v\in[0,1]^{10,000\times 5}$ as the starting point, and then use the Adam optimizer with a learning rate 0.005 to optimize $v$ by maximizing $Q(v,c)$ for 100 gradient ascent steps. For the starting point of cost matrix $c$, we directly use the ground-truth cost matrix $c=c^{\textrm{gt}}$ and keep it fixed during gradient ascent. For the starting point of value matrix $v$, we use the same procedure as described in Section 4.1 to re-generate a random matrix $v$ which satisfies the following conditions for all $i$: 1) $0\leq v_{i1}\leq v_{i2}\leq v_{i3}\leq v_{i4}$, and 2) $v_{i2}-v_{i1}\geq v_{i3}-v_{i2}\geq v_{i4}-v_{i3}\geq 0$. We set the per-capita budget to 2.0 for evaluating the $Q$ function. Since features of users are omitted in the synthetic dataset, we could not expect any generalization. Thus, we treat all 10,000 samples as training samples and report per-capita response and per-capita cost estimated by EOM on all training samples.

• •

  CRITEO-UPLIFT v2. We compare our proposed method with the following baseline methods in terms of AUCC:

  • –

    TSM-SL. The baseline two-stage method in many existing literatures (Ai et al., 2022; Zhao et al., 2019; Zhou et al., 2023). In the first stage, a DNN-based S-Learner model is exploited to predict the conversion uplifts and visit uplifts for individuals. In the second stage, an MCKP formulation could be used to find the optimal budget allocation solution. However for AUCC, the explicit budget allocation solution is not required, and we simply rank different individuals by the ratio between the conversion uplifts and visit uplifts and use the rank to compute AUCC.

  • –

    Direct Rank (Du et al., 2019). Du et al. (2019) propose a direct rank method to directly learn the ratios between values and costs and use the ratios to rank individuals.

  • –

    DRP (Zhou et al., 2023). Zhou et al. (2023) design several decision factors for MCKP solutions, and propose a surrogate loss function to directly learn these decision factors.

  Following (Zhou et al., 2023), we randomly sample 70% samples from the dataset as the training set, and the remaining samples are used as the test set. We report the performance of different methods in the test set, and for baseline methods, we directly cite results from (Zhou et al., 2023). For our proposed method, we use a DNN architecture described in Section 3.2: the base DNN is a 4-layer MLP (hidden sizes 512-256-128-64), and each header DNN is a 2-layer MLP (hidden sizes 32-1). We insert a ReLU activation layer after each fully connected layer in both base DNN and header DNN, except the final output layer in header DNN. We also insert a Batch Normalization layer (Ioffe and Szegedy, 2015) after the activation layer for faster convergence. The value of $\lambda$ in the surrogate loss $L_{S}(\theta)$ in Equation (11) is set to 200. For the finite-difference strategy, we set $F^{\prime}=4,000$ and $h=0.0003$. For NES, we set $N^{\prime}=2,000$ and $\sigma=0.001$. The MSRA initialization (He et al., 2015) is invoked to initialize all weight matrices in our model. The randomly initialized DNN S-Learner model is trained using the Adam optimizer with a learning rate of 0.0001 for 10 epochs. In each training step, the per-capita budget for evaluating the $Q$ function is randomly sampled from a uniform distribution in $[0.039,0.047]$. Following (Zhou et al., 2023), we run our proposed method 20 times and report the mean and variance of results.

• •

  KUAISHOU-PRODUCE-COIN. To demonstrate the effectiveness of our proposed training framework in real-world scenarios, we conduct both offline evaluation and online evaluation to compare our proposed method and TSM-SL. The offline experiment and online experiment share the following settings:

  • –

    The architecture for base DNN header DNN is kept the same as in the CRITEO-UPLIFT v2 dataset.

  • –

    We train the DNN S-Learner model using the Adam optimizer with a learning rate of 0.0003 for 20 epochs. To make a fair comparison, we use identical feature engineering/DNN architecture/training policies for our proposed method and TSM-SL.

  • –

    In each training step, the per-capita budget for evaluating the $Q$ function is randomly sampled from a uniform distribution in $[1.0,1.5]$.

  Furthermore, in the offline experiment:

  • –

    We randomly sample 80% of users from the KUAISHOU-PRODUCE-COIN dataset as the training set and the remaining 20% is used as the test set.

  • –

    We employ EOM and bisection to find the value of per-capita response when per-capita cost equals 1.2, and this metric is used to measure the performance of different methods.

  In the online experiment:

  • –

    All samples in the KUAISHOU-PRODUCE-COIN dataset are used for training and the obtained well-trained models are deployed in an online A/B test in the Kuaishou platform to compare the efficacy of their budget allocation policies in the real world.

  • –

    The online A/B test is conducted for one week. There are 14.2 million users in the online A/B test, and these users are disjoint for users in the KUAISHOU-PRODUCE-COIN dataset. We randomly partition 14.2 million users into two equally sized groups, one group for our proposed method and the other group for TSM-SL. For each group, the reported per-capita response/cost is directly computed over the entire 7.1 million users, and EOM is not employed.

Results on the synthetic dataset are summarized in Figure 2. The black line in Figure 2(a) shows the statistics about per-capita cost and per-capita value in RCT. As discussed in Section 3.3, starting from any cost and value matrix we could obtain a series of budget allocation solutions corresponding to different budgets, and further invoke EOM to empirically estimate the per-capita value $V\left(v,c,\alpha\right)$ and per-capita cost $C\left(v,c,\alpha\right)$ for each budget allocation solution. We perform the above EOM procedure using ground-truth $v^{\textrm{gt}}$ and $c^{\textrm{gt}}$, and plot the trajectory of $V\left(v^{\textrm{gt}},c^{\textrm{gt}},\cdot\right)$ and $C\left(v^{\textrm{gt}},c^{\textrm{gt}},\cdot\right)$ as the red dotted line in Figure 2(a). The value of $Q$ function for ground-truth $v^{\textrm{gt}}$ and $c^{\textrm{gt}}$ is $Q\left(v^{\textrm{gt}},c^{\textrm{gt}}\right)=0.2123$.

To verify the effectiveness of the gradient estimation process, we first generate initial $v$ and $c$ as described in Section 4.3 and study the cosine similarity between our estimated gradient and the precise gradient. To this end, we first set $F^{\prime}=40,000$ and use the finite-difference strategy to calculate the precise gradient $\frac{\partial Q(v,c)}{\partial v}$. Then, we use NES to estimate $\frac{\partial Q(v,c)}{\partial v}$ (Equation (10)) and gradually increase $N^{\prime}$. Finally, we check the cosine similarity between the NES estimated gradient and the precise gradient. Figure 2(b) shows the relations between cosine similarity and $N^{\prime}$, and we can see that as more sampling directions are involved in NES, the estimated gradients are more accurate.

We further plug the estimated gradient by NES into an Adam optimizer to maximize $Q(v,c)$, which represents the per-capita value when the per-capita cost equals 2.0. Figure 2(c) shows the per-capita value and per-capita cost of initial $v$ and $c$. The value of $Q$ function for initial $v$ and $c$ is $Q(v,c)=0.1996$. After 100 gradient ascent steps, we can increase the value of $Q$ function from 0.1996 to 0.2141. Figure 2(d) shows the per-capita value and per-capita cost of optimized $v$ and $c$. By comparing Figure 2(c) and Figure 2(d), we see that our proposed method could effectively increase the value of $Q$ function. From the properties of EOM, we know that $Q$ would be an unbiased estimator of the marketing goal. As such, the marketing goal could be effectively maximized. Since we only have 10,000 data samples, the Adam optimizer could severely overfit the training data and thus in Figure 2(d) there might be a peak around the region where the per-capita budget equals 2.0.

Results on CRITEO-UPLIFT v2 are summarized in Table 1. Ours-FD and Ours-NES refer to our proposed method with finite-difference strategy / NES as the gradient estimator, respectively. We see both Ours-FD and Ours-NES significantly outperform all competitive methods in the sense of AUCC. Ours-FD has the highest variance in AUCC for 20 runs, and this phenomenon could be partially explained by the fact that NES gradients are noisy. Although the performance of Ours-FD surpasses that of Ours-NES, Ours-FD costs 4x more running times on an NVIDIA Tesla T4 GPU (Ours-FD 17.6 hours v.s. Ours-NES 4.3 hours) since we need to evaluate the $Q$ function for more times.

We adopt Ours-FD for the KUAISHOU-PRODUCE-COIN dataset and compare it with TSM-SL.