本论文于2023年发表于计算机顶级会议 KDD 。营销优化对于在线互联网平台的用户增长起着重要作用。现有的研究通常将这个问题表述为预算分配问题，并利用两个完全解耦的阶段，即机器学习（ML）和运筹优化（OR）来解决。然而，ML阶段的学习目标没有考虑下游OR阶段的优化任务，这导致ML阶段模型的预测精度可能与决策质量不呈正相关。因此，降低模型预估误差不一定提升优化任务的决策效果。
本论文提出了一种基于决策的因果学习方法（DFCL），将ML和OR两个阶段集成到一个端到端的因果学习框架中，使得机器学习模型能以下游OR阶段的优化目标作为损失函数，从而保证ML阶段与OR阶段优化方向的一致性。其次，DFCL克服了营销场景中的预算不确定性，反事实推断问题以及计算效率问题等多个技术挑战，使得DFCL可以实现针对大规模在线用户营销场景的直接反事实优化。离线实验和在线A/B测试都证明了DFCL相对于传统因果推断方法的有效性。
1. 问题背景
开展营销活动是在线互联网平台提高用户参与度和收入的一种流行且有效的方式。营销活动需要大量的成本，因此通常在有限的预算下进行。由于不同用户对不同营销方案的反应有所不同，为不同的人分配适当的营销方案对于营销活动的有效性至关重要。这也就是运筹学中经典的资源分配问题。
这一问题的主流解决方案是两阶段法。在第一阶段中，通过ML模型预测不同营销处理下的个体水平（增量）反映，确定每个个体在不同营销处理下会产生多少的成本和收入。第二阶段是OR，预测被输入到组合优化算法中，决策对每个个体的具体营销处理方案，在预算一定的前提下实现最优的整体收入。但是，这两个阶段的目标并不一致：前者侧重于ML模型的预测精度，而后者侧重于决策的质量。由于二者目标的偏差，两阶段法存在着一些缺陷：（1）ML模型的预测精度和最终决策的质量没有严格的正相关关系。这是因为标准损失函数没有考虑预测间的相互作用，这可能对决策质量造成较大的影响；（2）ML模型通常无法达到完美的精度，并且在OR中对预测进行处理等操作会放大或是累积这种预测误差。因此，两阶段方法还存在着很多改善的空间。
近来，决策学习（Decision-Focused Learning）作为两阶段法的替代方案，收到了越来越多的关注。该方法将预测和优化集成到一个端到端系统中，有效地协调了两个阶段的目标，并在许多具有挑战性的任务中实现了更好的性能。该方法的核心思想便是：对ML模型训练中的损失函数进行改造，从衡量预测精度误差转变为衡量从预测中获得的决策的质量。该方法的主体过程为：（1）根据历史数据进行预测；（2）根据预测解决优化问题；（3）计算决策损失，使用随机梯度下降更新ML模型参数。
然而由于以下挑战，在营销算法中部署DFL仍非易事：
（1）约束的不确定性。此前大多数研究工作均集中在目标函数中存在未知参数的优化问题。当未知参数只存在于目标函数中时，解空间仍是确定的，这种情况下的求解会较为简单；而当未知参数出现在约束中时，解空间出现不确定性，从预测中得到的最优解可能在真实参数中完全是不可行的。
（2）营销中的反事实推断。由于存在反事实，计算营销中的决策损失十分具有挑战性。具体来说，观察个人在不同营销处理下的不同价值和成本是不可能的，因为个人在单次决策下智能接受一种营销处理。例如在某时刻给一位用户发放5元优惠券后，观察用户反应可以得到这5元优惠券的ROI，但你无法穿越回去，重新给这位用户发放3元优惠券，观察他的新反应。这也是因果推断中的基本问题。由于反事实的存在，无法基于离线数据获得优化问题的最优解，这也使得DFL中常见的梯度估计方法失效。
（3）大规模数据集的计算成本。计算成本同样也是大规模优化中DFL的主要障碍之一。如上所述，DFL将预测和优化集成到一个端到端系统中，在训练期间频繁调用求解器来求解优化问题。因此，DFL将带来很高的计算成本，这可能也是以往研究集中在toy problem上的原因。
而在本文中，作者提出的决策因果学习（Decision-Focused Causal-Learning）成功解决了以上挑战。
2. 问题描述
假定营销处理共有$M$类，其中个体$i$在处理$j$下的营销收入和成本分别为$r_{ij}$和$c_{ij}$。给定有限预算$B$的条件下，问题目标是最大化平台收入。因此多处理下的预算分配问题（MTBAP）可以建模为：
\[\begin{align*} \max_z F(z, B) = & \sum_i \sum_j z_{ij} r_{ij}, \\ s.t. \quad & \sum_i \sum_j z_{ij}c_{ij} \leq B, \\ & \sum_j z_{ij} = 1, \forall i \\ & z_{ij} \in \{0, 1\}, \forall i, j \end{align*}\]当$r_{ij}$和$c_{ij}$的值已知时，MTBAP是经典的背包问题。它仍然是NP-hard的，现有研究中通常通过贪心算法或是拉格朗日对偶理论来解决这个问题。两种方法都能够提供和最优解间的近似比如下：
\[\rho = 1 - \frac{\max_{ij}r_{ij}}{OPT}\]然而，在实际应用中$r_{ij}$和$c_{ij}$是未知的，通常需要替换为预测值。这也是本文重点解决的问题。
3. DFCL学习框架
在DFCL中，损失函数由预测损失和决策损失两部分组成，即
\[\mathcal{L}_{DFCL} = \alpha\mathcal{L}_{PL} + \mathcal{L}_{DL}\]前者旨在降低预测误差，强化ML模型的泛化性能；后者意在衡量下游任务的决策质量，也就是优化问题的目标值大小。
3.1 预测损失
在传统两阶段法中，ML模型训练中的预测损失通常表示为
\[\mathcal{L}_{MSE}(r,c,\hat{r},\hat{c})=\frac{1}{NM}\sum_i\sum_j(r_{ij}-\hat{r}_{ij})^2 + (c_{ij}-\hat{c}_{ij})^2\]由于反事实的存在，观察个体在多个处理下的收入或成本是不可能的，在真实数据中体现为对于每个个体$i$，我们最多只有一组与之相对应的$j$的数据。为了解决这一问题，我们首先对训练数据集进行改造。假定在随机控制实验中共采集到了$N$组数据。其中，第$i$组数据标记为$(x_i,t_i,r_{it_i},c_{it_i})$。假定处理$j$下的样本数量为$N_j$。
- $x_i$：个体$i$的用户特征
- $t_i$：所采取的营销处理
- $r_{it_i}$：个体$i$在处理$t_i$下的收入
- $c_{it_i}$：个体$i$在处理$t_i$下的成本
给定上述数据集，定义预测损失为：
\[\mathcal{L}_{PL}(r,c,\hat{r},\hat{c})=\frac{1}{M}\sum_i\frac{1}{N_{t_i}}[(r_{it_i}-\hat{r}_{it_i})^2 + (c_{it_i}-\hat{c}_{it_i})^2]\]该预测损失和MSE损失是等价的。
3.2 决策损失
如上所述，$r$和$c$的真值往往无法提前知道，因此被替换为预测值$\hat{r}$和$\hat{c}$。。因此，原始优化问题$F(z,B)$也被替换为$F(z, B, \hat{r},\hat{c})$，对应的最优解为：
\[z^\star(B,\hat{r},\hat{c})=\arg\max_z F(z,B,\hat{r},\hat{c})\]当前解$z^\star(B,\hat{r},\hat{c})$在$r$和$c$的真值下的目标值为：
\[\sum_i \sum_j r_{ij}z_{ij}^\star(B,\hat{r},\hat{c})\]因此，定义预算$B$下的决策损失为目标函数真值的相反数：
\[\mathcal{L}_{DL}(B,r,c,\hat{r},\hat{c})= - \sum_i \sum_j r_{ij}z_{ij}^\star(B,\hat{r},\hat{c})\]在某些真实场景下，预算$B$同样也是随机变量，因此决策损失可以定义为：
\[\begin{align*} \mathcal{L}_{DL}(r,c,\hat{r},\hat{c}) &= \int_{0}^{\infty} \mathcal{L}_{DL}(B, r,c,\hat{r},\hat{c}) \ dB\\ &= \int_{0}^{\infty} - \sum_i \sum_j r_{ij}z_{ij}^\star(B,\hat{r},\hat{c}) \ dB \end{align*}\]3.3 学习框架
DFCL的学习框架如下所示。其中，最关键的步骤在于$\mathcal{L}_{DFCL}$中的梯度估计。
4. 梯度估计
DFCL的损失包括预测损失和决策损失。前者是一个连续可微函数，其梯度可以直接计算。因此，决策损失的梯度估计是本节的重点。首先，我们引入了等效的双重决策损失，以消除不确定的约束，降低组合优化算法的计算成本。其次，我们开发了两个代理损失函数，并改进了黑盒优化算法，以提供双重决策损失的梯度估计。
4.1 对偶决策损失
根据拉格朗日对偶理论，原始问题$F(z,B,r,c)$的上界可以通过求解下述问题得到
\[\begin{align*} & \min_{\lambda\geq 0} \left( \begin{matrix} \max_z \lambda B + \sum_i\sum_j(r_{ij} - \lambda c_{ij})z_{ij} \\ s.t. \sum_j z_{ij} = 1, \forall i\\ z_{ij} \in \{0,1\},\forall i,j \end{matrix} \right) \\ = & \min_{\lambda \geq 0} \max_zH(z,\lambda,B,r,c) \\ = & \min_{\lambda \geq 0} G(\lambda,B,r,c) \end{align*}\]最优的拉格朗日乘子$\lambda^\star$能够通过梯度下降法或是二分搜索法得到（终止条件为$B-\sum_i\sum_jc_{ij}z_{ij} \leq \epsilon$或$\lambda \leq \epsilon$）。此外，原始问题的近似最优解可以通过最大化$H(z,\lambda^\star,B,r,c)$得到。
假定$F_c(z,B,r,c)$为$F(z,B,r,c)$中变量$z$松弛为连续变量的形式，定义最优解为：
\[\begin{align*} & z_c^\star(B,r,c)=\arg\max_{z} F_c(z,B,r,c) \\ & z^\star(B,r,c)=\arg\max_{z} F_c(z,B,r,c) \\ & \lambda^\star(B,r,c)=\arg\min_{\lambda\geq 0} G(\lambda,B,r,c) \end{align*}\]给定最优拉格朗日乘子$\lambda^\star$，原始问题的近似解为：
\[z^d(\lambda^\star,B,r,c)=\arg\max_z H(z,\lambda^\star,B,r,c)\]基于上述定义，可以发现$\lambda^\star$随着$B$的增加单调递减，并且有
\[\begin{align*} F(z^d,B,r,c) & \leq F(z^\star,B,r,c) \\ & \leq F_c(z_c^\star,B,r,c) \\ & = G(\lambda^\star,B,r,c) \\ & \leq F(z^d,B,r,c) + \max_{ij}r_{ij} \end{align*}\]因此，通过对偶问题求解得到的近似比为：
\[\begin{align*} \rho=\frac{F(z^d,B,r,c)}{F(z^\star,B,r,c)} &\geq\frac{F(z^\star,B,r,c) - \max_{ij}r_{ij}}{F(z^\star,B,r,c)} \\ & = 1 - \frac{\max_{ij}r_{ij}}{F(z^\star,B,r,c)} \\ & \approx 1 \end{align*}\]因此，在此处将对偶问题$H(z,\lambda^\star,B,r,c)$替代原始问题，作为学习目标，称之为对偶决策损失。给定最优的$\lambda^\star$和预测值$\hat{r},\hat{c}$，最大化$H(z,\lambda^\star,B,\hat{r},\hat{c})$求解得到最优解$z^d(\lambda^\star,B,\hat{r},\hat{c})$。
\[z^d(\lambda^\star,B,\hat{r},\hat{c})=\arg\max_{z} H(z,\lambda^\star,B,\hat{r},\hat{c})\]注意到，$\lambda^\star B$是常量，因此$z^d$可以重写为
\[z^d(\lambda^\star,\hat{r},\hat{c})=\arg\max_{z} H(z,\lambda^\star,\hat{r},\hat{c})\]根据当前解$z^d$得到的对偶决策损失为
\[\mathcal{L}_{DDL}(\lambda^\star,B,r,c,\hat{r},\hat{c}) = - (\lambda^\star B + \sum_i\sum_j(r_{ij} - \lambda^\star c_{ij})z_{ij}^d(\lambda^\star,\hat{r},\hat{c}))\]同样地，由于$\lambda^\star$和$B$和预测值$\hat{r},\hat{c}$无关，因此可以从对偶决策损失中移除。由于$\lambda^\star$随着$B$的增加单调递减，每个$B$对应一个$\lambda^\star$，因此在随机预算$B$下，对偶决策损失可以转化为
\[\begin{align*} \mathcal{L}_{DDL}(r,c,\hat{r},\hat{c}) &= \int_{0}^{\infty}\mathcal{L}_{DDL}(\lambda^\star,r,c,\hat{r},\hat{c}) \ d\lambda^\star \\ &= \int_{0}^{\infty}\mathcal{L}_{DDL}(\lambda,r,c,\hat{r},\hat{c}) \ d\lambda \\ &= - \int_{0}^{\infty} \sum_i\sum_j(r_{ij} - \lambda c_{ij})z_{ij}^d(\lambda,\hat{r},\hat{c}) \ d\lambda\\ \end{align*}\]离散化拉格朗日乘子$\lambda$，有
\[\mathcal{L}_{DDL}(r,c,\hat{r},\hat{c})=\sum_{\lambda}\mathcal{L}_{DDL}(\lambda,r,c,\hat{r},\hat{c})\]4.2 策略学习损失
注意到对偶问题$H(z,\lambda,\hat{r},\hat{c})$可以由下式解决：
\[\begin{align*} \max_z H(z,\lambda,\hat{r},\hat{c}) &= \left( \begin{matrix} \max_z \sum_i\sum_j(\hat{r}_{ij} - \lambda \hat{c}_{ij})z_{ij} \\ s.t. \sum_j z_{ij} = 1, \forall i\\ z_{ij} \in \{0,1\},\forall i,j \end{matrix} \right) \\ &= \sum_i\max_j(\hat{r}_{ij}-\lambda\hat{c}_{ij}) \end{align*}\]因此，解$z^d(\lambda,\hat{r},\hat{c})=\arg\max_z H(z,\lambda,\hat{r},\hat{c})$可以表示为
\[z_{ij}^d(\lambda,\hat{r},\hat{c})=\mathbb{I}_{j=\arg\max_j \hat{r}_{ij}-\lambda\hat{c}_{ij}}\]对偶决策损失可以重新表示为：
\[\mathcal{L}_{DDL}(r,c,\hat{r},\hat{c})=-\sum_{\lambda}\sum_i\sum_j(r_{ij}-\lambda c_{ij})\mathbb{I}_{j=\arg\max_j \hat{r}_{ij}-\lambda\hat{c}_{ij}}\]然而，$\mathcal{L}_{DDL}(r,c,\hat{r},\hat{c})$仍然关于$\hat{r}$和$\hat{c}$是不可微的。因此，我们采用softmax函数来进行平滑化
\[\mathcal{L}'_{DDL}(r,c,\hat{r},\hat{c})=-\sum_{\lambda}\sum_i\sum_j(r_{ij}-\lambda c_{ij}) \frac{\exp(\hat{r}_{ij}-\lambda\hat{c}_{ij})}{\sum_k\exp(\hat{r}_{ik}-\lambda\hat{c}_{ik})}\]令$p_{ij}(\lambda,\hat{r},\hat{c})=\exp(\hat{r}{ij}-\hat{c}{ij}){/}\sum_k\exp(\hat{r}{ik}-\lambda\hat{c}{ik})$表示将处理$j$分配给个体$i$的概率，$r_{ij}-\lambda c_{ij}$表示将处理$j$分配给个体$i$的奖励。因此，最小化$\mathcal{L}’{DDL}(r,c,\hat{r},\hat{c})$等价于最大化策略$\pi=p{ij}(\lambda,\hat{r},\hat{c})$在不同拉格朗日乘子下的期望奖励。因此，$\mathcal{L}’_{DDL}$也被称为策略学习损失。
由于营销场景的反事实推断，$\mathcal{L}’_{DDL}(r,c,\hat{r},\hat{c})$无法直接计算，因此设计代理损失如下
\[\mathcal{L}_{PLL}(r,c,\hat{r},\hat{c}) = -\sum_\lambda\sum_i \frac{N}{N_{t_i}}(r_{it_i}-\lambda c_{it_i})\frac{\exp(\hat{r}_{it_i}-\lambda\hat{c}_{it_i})}{\sum_j\exp(\hat{r}_{ij}-\lambda\hat{c}_{ij})}\]4.3 最大熵正则化损失
为了得到$z^d(\lambda,\hat{r},\hat{c})$的可微闭式表达式，我们对约束$z\in{0,1}$进行松弛，并且在$H(z,\lambda,\hat{r},\hat{c})$的目标函数中加入最大熵正则化器。因此，$H(z,\lambda,\hat{r},\hat{c})$转化为非线性凸函数，即
\[\max_z\sum_i\sum_j(\hat{r}_{ij}-\lambda\hat{c}_{ij})z_{ij}-\tau\sum_i\sum_j z_{ij}\ln z_{ij} \\ s.t. \ \sum_j z_{ij} = 1, \forall i \\ z_{ij} \in [0, 1]\]拉格朗日松弛函数为：
\[L(z,\beta)=\sum_{i=1}^N\sum_{j=1}^M(r_{ij}-\lambda c_{ij})z_{ij} - \tau\sum_{i=1}^N\sum_{j=1}^Mz_{ij}\ln z_{ij} - \sum_i\beta_i(1 - \sum_j z_{ij})\]其中，$\beta$为等式约束的对偶变量。当$\frac{\partial L(z,\beta)}{\partial z} = 0$且$\frac{\partial L(z,\beta)}{\partial \beta} = 0$时，最优解为：
\[z_{ij}^d=\frac{\exp[(\hat{r}_{ij}-\lambda\hat{c}_{ij})/\tau]}{\sum_k\exp[(\hat{r}_{ik}-\lambda\hat{c}_{ik})/\tau]}\]该最优解对于$\hat{r}$和$\hat{c}$连续可微。因此，对偶决策损失可以重写为：
\[\mathcal{L}''_{DDL}(r,c,\hat{r},\hat{c})=-\sum_{\lambda}\sum_i\sum_j(r_{ij}-\lambda c_{ij}) \frac{\exp[(\hat{r}_{ij}-\lambda\hat{c}_{ij})/\tau]}{\sum_k\exp[(\hat{r}_{ik}-\lambda\hat{c}_{ik})/\tau]}\]类似地，由于反事实的存在，$\mathcal{L}’‘_{DDL}$不能直接计算，可以转化为：
\[\mathcal{L}_{MERL}(r,c,\hat{r},\hat{c}) = -\sum_\lambda\sum_i \frac{N}{N_{t_i}}(r_{it_i}-\lambda c_{it_i})\frac{\exp[(\hat{r}_{ij}-\lambda\hat{c}_{ij})/\tau]}{\sum_k\exp[(\hat{r}_{ik}-\lambda\hat{c}_{ik})/\tau]}\]Reference
Hao Zhou, Rongxiao Huang, Shaoming Li, Guibin Jiang, Jiaqi Zheng, Bing Cheng, and Wei Lin. 2024. Decision Focused Causal Learning for Direct Counterfactual Marketing Optimization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’24), August 25–29, 2024, Barcelona, Spain. ACM, New York, NY, USA, 12 pages. https://doi.org/10.1145/3637528.3672353