关于机器学习:基于动态背包的多场景广告序列投放算法

简介： 电商广告是广告主接触其指标用户的重要伎俩。广泛的广告指标是在估算束缚下，在肯定工夫范畴内最大化广告主累计支出。理论利用中，广告的转化通常须要对同一用户进行屡次曝光，直到该用户最终购买为止。然而，现有的广告零碎次要关注单次广告曝光的间接收益，而疏忽了每次曝光对最终转化的奉献，因而通常属于次优解决方案。在本文中，咱们将广告序列投放策略优化转化为一个动静背包问题。为求解此背包问题，咱们提出了一个具备实践保障的双层优化框架，该框架在不影响求解精度同时，显着缩小了原始优化问题的求解空间。在上层框架的优化中，咱们引入强化学习并设计了一种无效的动作空间约减办法，进步了强化学习在理论广告利用中的摸索效率。

1. 背景

在电商平台中，在估算束缚下优化一段时间的 GMV 是广告主的外围诉求之一。作为电商平台，从广告主视角如何帮忙其实现该诉求是十分重要的问题。

1. 对广告主：一段时间估算束缚下的 GMV 优化帮忙广告主实现更多营收和更高的投资回报率（ROI），从而让广告主真正称心；
2. 对平台：消费者和广告主的满意度晋升为平台带来衰弱的生态和长期的贸易凋敝，并能吸引更多的广告主退出以及投入更多的广告估算，从而带来平台的支出晋升；
3. 对消费者：GMV 的优化满足了更多的消费者购买需要，从而优化了消费者体验；

总之，在估算束缚下优化一段时间的 GMV 可能带来三方共赢，其重要性显而易见。

为了解决该问题，绝大多数出价策略将一段时间的 GMV 优化问题拆解为：对每次用户申请进行独立优化，并简略地认为这些独立优化的汇总后果能够实现一段时间整体 GMV 的最优化。事实上，这类策略失去的是次优解，因为它们以孤立的视角把消费者和广告限定在了单次交互中，而疏忽了一段时间内的屡次交互可能产生的其它影响。

为什么孤立的单次交互视角优化会导致次优解？咱们从理论状况登程，首先，同一个消费者在一段时间内（例如 3 - 7 天）会屡次拜访淘宝，并且随机地在淘宝不同的场景呈现（例如首页猜你喜爱、领取胜利等），这为同一个广告和同一个消费者在不同场景屡次接触发明了机会；其次，大量的成交并非产生在消费者和广告的首次接触中，而是产生在第二次或之后的屡次接触中。通过 AB 试验，咱们发现广告和消费者的前序接触会影响消费者对该广告在后续接触中的点击率和转化率，阐明屡次的接触对消费者的心智有累积影响的效应。在这样的背景下，单次申请优化后果的累积很容易导致次优解。

举个常见的例子，假如消费者和广告存在两次接触，第一次接触时，其转化的冀望低于其它流量转化的均匀冀望，而如果在接触一次后再产生第二次接触，因为消费者心智累积效应，其第二次接触后转化的冀望显著升高，使得两次接触的整体转化冀望高于其它流量转化的均匀冀望。在这种的设定下，单次贪婪的优化策略在第一次接触时因为其转化冀望较低，所以不会抉择去竞得流量；而因为第一次的未接触导致了心智并没有产生积攒效应，因而第二次接触的转化冀望仍然较低，也不会去竞得流量。然而，如果在第一次接触时就能预估到两次接触的整体转化冀望较大，那么第一次接触就会做出竞得的决策，并牵强附会地竞得第二次高价值接触，咱们称这种策略为序列投放算法，不言而喻，其在整体上比单次申请优化策略（下文对立称为“单次投放算法”）实现了更好的成果。

这个例子中，序列投放算法和单次投放算法做出不同决策的外围起因在于：第一次接触前，单次投放算法只评估了单次申请的价值，即短期价值，而序列投放算法评估了将来屡次申请的整体价值，咱们称为长期价值。咱们定义同一个消费者和同一个广告的屡次接触形成了一个广告投放序列，并定义长期价值为从此刻起残余序列的总价值。能够看出，当序列长度为 1 时，短期价值是长期价值的一种非凡状况。因而，基于长期价值的序列投放策略可能兼容并优于基于短期价值的单次投放策略。基于这个理念，咱们提出了基于长期价值的多场景序列投放算法。

然而，基于长期价值的序列投放算法在解决估算束缚下 GMV 的优化问题时存在诸多挑战：

1. 优化指标是长期的累积价值，而决策的粒度是单次的；如何基于长期价值的预估取得最优的单次决策？
2. 长期价值预估模型的学习离不开策略摸索生成的序列数据。长期价值预估模型和决策模型的学习如何保障收敛性？如何保障决策的最优性？如何晋升策略摸索的效率？
3. 如何保障估算束缚的满足？

针对这些挑战，咱们逐个给出了相应的解决方案。首先，咱们将估算束缚问题建模为背包问题：背包中物品的价值为 < 用户,ad> 造成的序列价值（长期成交、珍藏加购等），物品的分量为此序列中产生的老本（耗费）；咱们依照性价比（序列价值 / 老本）由高到低一一抉择物品，直到选出的物品总耗费刚好不超过预算束缚。这里，因为物品分量远小于背包容量，按性价比排序的贪婪算法可能靠近最优解。然而，每个序列的价值和老本与经营该序列的广告策略无关，因而这是一个动静背包问题。为求解此动静背包，咱们采纳双层优化问题的解法来迭代求解：1）物品的贪婪筛选，2）物品价值 / 老本以及对应策略的优化。在此框架下，咱们提出了一种近似最优的经营策略，该策略满足强化学习中 Policy Iteration 算法的性质，可能保障其学习的收敛性。此外，为了使策略在理论场景中落地，咱们提出了一种将间断出价转换为离散动作的办法，可能在不失落出价精度的状况下，大幅度缩小动作的摸索空间，进步学习效率。综上，咱们将整个算法称之为 MSBCB(Multi-channel Sequential Budget Constrained Bidding)，大量的离线和在线试验验证了咱们算法的有效性。上面咱们具体介绍问题的定义、解决方案和试验后果。

该工作已被 ICML-2020 接管，论文原文《Dynamic Knapsack Optimization Towards Efficient Multi-Channel Sequential Advertising》地址：https://arxiv.org/abs/2006.16312

2. 建模计划

3.3 预估模型

下面次要介绍了如何依据长期价值来做相应的决策，在本大节，咱们介绍长期价值该如何预估。首先，模型的预估对象分成交和耗费两种，因而咱们这是一个多任务学习，须要同时学习回归和分类。为应答多任务学习，咱们将模型构造进行拆分，底层共享 embedding，顶层网络参数解耦，以升高多任务学习相互不利烦扰，而且通过 validation 的形式优化各个 loss 之间的权重。其次，对于回归工作，因为其存在大量的零样本，导致模型成为一个零收缩模型（Zero-inflated models），其输入基本上全为 0，无奈用 MSE loss 来失常学习网络参数。为解决此问题，咱们提出两种解决办法：

1. 通过正当的负采样来保障证样本的无效学习，并通过校准技术弥补由样本分布调整造成的预估偏差；
2. 引入 CTR 先验，结构 CTR loss 来辅助回归学习。咱们认为耗费的冀望能够拆分成耗费产生的概率与对应的耗费值的点乘，因而咱们将将来耗费产生的概率显示地独自用 CTR 的 label 来学习，并使其更新不受其余 loss 的影响；而后咱们基于较为精确的耗费概率，再来学习其概率对应下的耗费值，可能无效防止耗费值输入全为 0 的状况，使 MSE loss 能失常更新模型参数。

另外，对于偏长期预估的模型，因为历次大促流动会对样本分布有较大影响，造成模型重大高估问题。为了解决这些问题，咱们通过稳固的样本分布调整，保障训练样本与预测样本分布近似统一。此外，咱们还在样本特色上也有一些尝试，在用户历史行为根底上新增了一些实时行为特色，带了来一些成果晋升。

3.4 整体框架

咱们对整个流程进行梳理：

1. 首先，当用户申请达到广告平台之后，咱们结构用户和广告特色，而后对每个进行四个长期价值的预估，得出每个广告所采取的策略（投 / 不投）并算出对应的最优出价。
2. 接着，对于任意广告，咱们计算以后用户在两个不同决策下的最高性价比，若此性价比高于此广告的阈值 CPRthr，则将以后用户装入此广告的背包中。
3. 最初，咱们拿到用户的反馈，一方面，咱们在 PID 模块中基于估算和理论耗费来更新阈值 CPRthr，另一方面，咱们结构训练数据来更新强化学习模型参数，使预估的长期价值更精确。

步骤一形容了咱们基于长期价值对每个广告进行投放 / 不投放的动作决策，但无论哪个动作都会取得一个最终出价，即便是不投策略也会产生一个出价，因为此出价会保障此广告最终不会博得竞价；步骤二形容了咱们通过比照以后用户最高性价比与广告主设定的阈值，来判断此广告背包中是否还有多余的空间能装下以后用户；前两个步骤须要进行在线打分和决策，实时地与用户交互，而第三个步骤则是依据其反馈离线更新阈值 CPRthr 和模型参数，具体来说，阈值 CPRthr 的预设初始值个别较高，这样能够保障背包中都是优质的流量（性价比），但此时耗费较少，而后逐渐下调阈值导致耗费减少，直到耗费满足估算。

4. 离线试验

为了比照咱们算法最优性质，咱们在离线比照了咱们办法 MSBCB 与多种强化学习 baseline 以及其余实践最优办法，具体如下：

• Greedy + DDPG：动静背包下应用 DDPG 求解动作策略，没有应用动作约减。
• Greedy + DQN: 动静背包下应用 DQN 求解动作策略，出价被手动离散至 11 维。
• Greedy + PPO: 动静背包下应用 PPO 求解动作策略，出价被手动离散至 11 维。
• MSBCB: 这是咱们基于 RL 的办法，动静背包下应用 DQN 求解动作策略，并应用了动作约减。
• Myopic Greedy: 动态背包下应用短视预估值 (CVR) 来结构动作策略。
• Greedy with maximized CPR (enumeration)：动静背包下应用枚举办法求解动作策略，枚举抉择的是性价比 CPR 最大的策略。
• MSBCB (enumeration)：这是咱们实践最优解，动静背包下应用枚举办法求解动作策略，枚举抉择的是最大 reward 的策略（不通过 RL 求解）。
• Offline Optimal (dynamic programming): 这是离线的全局最优解，应用动静布局办法，此办法不能用于在线试验，只能利用于十分小规模的离线试验。

离线数据中蕴含了 10000 个用户和 500 个广告，每个广告有 4000 元的估算，咱们用实在的数据对线上的用户心智进行了剖析和拟合，并将下面算法与拟合后的模拟器进行交互，画出各个算法的学习曲线在 GMV 上的体现，其后果如下：

从下面的学习曲线，咱们能取得以下论断：MSBCB 优于 DDPG, DQN, PPO 阐明咱们提出的动作约减比间接应用 RL 更无效；MSBCB 优于 Myopic 阐明基于长期价值的决策优于基于短期价值的决策；MSBCB(枚举)约等于 Offline Optima 阐明咱们办法实践最优解与全局最优解完全一致；而 Greedy maxCPR(枚举)小于 MSBCB(枚举)阐明最大化 CPR 的实践最优解并不是全局最最优，对应章节 3.2 证实局部，同时也阐明咱们算法的实践天花板劣势；而 MSBCB 和 MSBCB(枚举)的比照阐明了咱们算法在理论学习过程中能疾速收敛并迫近实践天花板。

5. 在线试验

为了验证算法在理论落地中的成果，咱们在淘宝线上首猜、购后等 9 个场景部署了 MSBCB 算法以及 Myopic Greedy。咱们思考以下几个试验对象：

1. base 桶：大盘基准桶，其调价算法为 OCPC。
2. test1 桶：Myopic Greedy 试验桶（在业务上也称整合营销），它的目标是在多场景中优化短期 CVR，用于与优化长期价值的办法进行比照。
3. test2 桶：MSBCB 试验桶，它的预估决策与咱们的建模计划统一
4. test3 桶：这是一个 MSBCB 试验桶的简化版，它的试验目标是为了验证对耗费的预估是否精确，test2 和 test3 共用着同一个长期价值预估模型，只是在出价动作上 test3 不思考将来耗费状况。

咱们通过用户尾号进行分桶。

长期总体成果：首先，为了验证其长期的优化成果，咱们将当天展示广告的成交、耗费等指标窗口拉到 7 天，以察看广告展示后的 7 天长期成果；咱们统计了 2019.12.13-2019.12.19 这七天内展示的广告的长期成果如下，从表中能够看出，咱们的试验桶 test2 可能在 cost 根本持平的状况下(<1%)，晋升 +10% 的 GMV，使广告主的 ROI 晋升近 10%。

长期天级成果：为了更清晰展示咱们的办法在天级上的体现，下图给出 2019.12.13-2019.12.19 七天内每天 ROI 和耗费的状况；其中，左坐标轴示意 cost 的增减状况，由折线示意，右坐标轴示意 ROI 的增减，由条形柱示意。从图中咱们能够看出，咱们试验桶在 ROI 指标每天基本上都正向，最高能达到 +19.07%(test2,20191218)，最低在 +0.58%(test2,20191214)，稳定还是存在的；耗费大部分都管制在 5% 以内。

ROI 正负向店铺占比：咱们统计这段时间内各个店铺的 ROI 正负向占比方下图(a)，85.1% 的店铺有 ROI 的正向成果，其中，7.4% 的店铺 ROI 能优化至 +30% 以上，51.1% 的店铺 ROI 能晋升至 +10-30%，26.6% 的店铺能晋升 +0-10% 左右。这些后果阐明了咱们算法对于绝大多数店铺都有较好的正向成果。

序列长度变动：为了凸显咱们的办法在长期价值上的优化，咱们比照了用户在不同试验办法下对于一个广告接触的均匀次数（咱们称为序列长度），上图 (b) 给出了咱们的办法在用户序列长度占比上绝对于整合营销晋升的幅度。后果发现，咱们办法能晋升序列长度的占比，特地是当序列长度为 7 的 case 占比能进步 30%，这阐明了咱们办法可能促成更长的用户行为序列，而更长的用户行为序列意味着更多的机会去影响用户对某个广告的心智，从而优化用户对于广告的在长期上的成交。

分场景的优化状况：进一步，咱们还能够剖析试验算法在各个场景上的体现状况，下图画出了各个试验桶在 9 个场景的估算散布以及对应 ROI 的状况。左坐标轴为 ROI，对应条形图，给出了各个算法在这些场景上的 ROI 体现；右坐标轴为各试验桶绝对于 base 在各个场景上耗费的增减，对应折线图。从图中咱们能察看出一些景象：

1. MSBCB 试验桶和整合营销都把更多的估算花在 roi 较高的购后场景，特地是领取胜利
2. MSBCB 试验桶相比整合营销，把更多的流量从首猜调配到了其余场景，特地是收藏夹和购物车这两个购中场景

这些景象阐明了咱们算法可能在场景间对流量进行正当调配，把估算尽可能画在高 ROI 的场景，另外，长期价值模型绝对于短期 cvr 模型更加看好购中、购后等场景，阐明了它对用户的经营偏差应用较长的交互序列去优化长期价值，间接证实了咱们算法的有效性。

更多试验后果请参考论文原文：https://arxiv.org/abs/2006.16312

6. 总结瞻望

在机制策略层面，咱们首次采纳了基于长期价值的动静背包问题来建模和求解序列广告投放问题，整个建模不仅贴切问题实质，还具备十分丑陋和简洁的实践反对，而且建模计划易于实现和利用。在落地方面，咱们进行了大量的离线和在线试验，不仅证实了咱们算法的收敛性和最优性，而且在线上帮忙广告主在雷同的估算下晋升了 10% 的 ROI，表明了咱们算法对长期价值 / 短期价值的优化能力。咱们建设了一套基于长期价值的背包序列化投放实践和技术，并在机制策略层面获得了肯定的成绩和停顿，在将来，不只针对长期成交，咱们会将长期价值横向扩大到其余指标，如珍藏、加购、耗费、多指标交融等，最终满足广告主在长期价值上的各种诉求优化。