【论文笔记】004 Feedback Control of Real-Time Display Advertising

本文主要介绍了在实时广告投放中的流量控制问题，该技术广泛应用在程序化广告中，简单来说就是依据实时的投放反馈数据，对流量进行动态调整，以达到投放速度的均匀稳定。现在非常流行的 OCPA/OCPM 等方法背后，也都离不开这一算法。

注：我个人的一些理解补充，主要放在文中的括号内，并会带有 注：

更新历史

2020.02.06: 完成初稿
2020.02.07: 更新最后一节

摘要

实时竞价 RTB 在广告行业是一种颠覆性的展现方式，对于广告主来说，可以进行颗粒度为用户的广告采买（注：这与传统方式有很大不同，想象一下杂志上的广告，并不可能根据不同的人展现不同的广告）。这样一来，我们可以使用更加精细的数据（如 cookies）来进行用户定向，进而提升广告效果（注：在移动互联网时代，因为没有 cookies，所以更多的是使用当前的设备 id，以及对应的用户画像进行判断）。

然而 RTB 模式也有其固有的问题，就是不稳定。因为广告的竞价是基于每一次曝光的，并且不同广告主的 KPI 差异较大，所以对于广告主来说，如何控制不同广告投放的效果和花费是非常困难的事情。本文提出了一种在 RTB 场景下的反馈控制机制，能够帮助广告主动态控制关键 KPI 参数（如获胜率和点击成本等）。本文也证明了该机制能够优化广告投放效果：设定单次点击成本的参考值后，能够在预算的约束下，达成尽可能多的点击。该机制同时也在现实世界中进行过测试，可以有效且稳定地在不同条件下达成广告投放 KPI。

简介

出现于 2009 年的实时竞价 RTB 已经成为了广告投放的一种全新范式。与传统的基于约定或者设置固定的曝光价格不同，在 RTB 模式下，不同 DSP 可以根据算法为每次曝光进行竞价。是否参与竞价，参与竞价出多少钱等决策可以基于某次曝光的预估价值和花费进行权衡做出。更重要的是，我们可以使用实时信息（如用户的人口学统计信息，兴趣倾向等）来帮助算法进行评估。基于这样的机制，RTB 可以比其他的在线广告形式的 ROI 高很多。

虽然 RTB 引入了效果驱动的广告投放，但同时也带来了极高的不稳定性，相关的 KPI 指标有 CPM/AWR/eCPC/CTR 等。下图是两个不同的广告投放计划在不同时间段里这四个关键指标的表现，可以看到这些指标波动非常大。于是对于广告主来说，想要在固定花费的前提下优化广告效果非常困难（注：难点一在于如何控制好花费，难点二在于如何在不断变化的指标中找到最佳的配置）

本文中，我们使用了反馈控制理论来解决 RTB 的不稳定问题。反馈控制理论在许多场景（飞机方向控制、机器人 AI）都有应用，给定参考值后就可以自动动态调整相关变量。对于 RTB 场景来说，指定的 KPI 就是广告主设定的参考值，这里我们主要针对如下两个场景：1）对于效果广告来说，eCPC。2）对于品牌广告来说，AWR。更具体来说，我们将这两个指标作为控制输入信号，输出 bid price 的调整量。使用的控制控制器也有两个：PID(proportional-integral-derivative) 和 WL(aterlevel-based)。根据大量实践得到的经验，PID 和 WL 都能够控制 eCPC 和 AWR，并且 PID 算法在准确性和稳定性上更优。

更进一步的试验是将该控制机制应用到可控竞价优化中。通常来说，一次广告投放在不同渠道的表现会有差异（如不同的广告平台，用户位置，用户设备类型等），如果我们能够自动分配预算给效果更好的渠道，就可以提高总体广告投放效果。本文提出了一个多渠道竞价优化模型，可以针对不同的渠道计算最优参考 eCPC。经过试验验证，在预算不变的前提下，效果有显著提升。

预备知识

RTB 流程

用户访问带广告的站点，给 ADX 发送广告请求
ADX 给各个 DSP 发送竞价请求，带有用户和上下文信息
DSP 计算出价，并返回给 ADX（这个过程一般不超过 100ms）
ADX 收到所有出价后，出价最高的赢得此次广告曝光机会
ADX 通知出价最高的 DSP 竞价成功
用户看到出价最高的 DSP 投放的广告
用户之后的点击或转化会发送给获胜的广告主。

竞价策略

对于 DSP 来说一个基础问题就是一个竞价请求来了之后要出多少钱，一般来说取决于两个因素：1）效用（如 CTR，或期望收入）。2）花费（预估价格）。一个通用的竞价策略如下：

$b(t)=b_0\frac{\theta_t}{\theta_0}$

其中

$\theta_t$ 预估 CTR
$\theta_0$ 指定条件下（如某个用户兴趣标签）的平均 CTR
$b_0$ 是指定条件下（如某个用户兴趣标签）的调整后的底价

本文中采用的竞价策略如上，并且 CTR 预估基于 logistic 算法（注：也就是基于最通用的算法和策略）

反馈控制原理

在反馈控制系统中，控制装置对被控对象施加的控制作用，是取自被控量的反馈信息，用来不断修正被控量与输入量之间的偏差，从而实现对被控对象进行控制的任务，这就是反馈控制的原理。

注：更多相关信息可参考控制理论：寻找普适方法之路

RTB 反馈控制系统

一个 RTB 反馈控制系统如下图所示。传统的竞价策略在 DSP 的 Bid Calculator 中，控制器所做的工作是调整由 Bid Calculator 计算出的 Bid Price。具体来说，Monitor 从 ADX 接收竞价的获胜通知，从广告追踪系统接收点击通知，然后计算指定的 KPI 值（如 AWR 和 eCPC）。如果要控制 eCPC 的话，给定的参考 eCPC 和实际观测计算到的 eCPC 的误差会传递给控制函数(control function)，最终的输出结果会传递给 actuator 并计算得到最终的 adjusted bid price，继而发送给 ADX 参与竞价。

Actuator

对于 t 时刻收到的竞价请求，actuator 会使用当前的控制信号 $\phi(t)$ 将竞价 $b(t)$ 调整为 $b_a(t)$，公式如下：

$b_a(t)=b(t)exp\{\phi(t)\}$

模型需要满足当 $\phi(t)=0$ 时对出价不作调整，之所以采用指数模型是因为线性模型会出现负竞价（使得出价无意义）。注：在具体的工程实现中，这部分可以封装在一个函数中。

PID 控制器

我们先来看看传统的 PID 控制器。顾名思义，PID 控制器通过线性组合误差(error factor)的比例(proportional)、积分(integral)和微分(derivative)产生控制信号，公式如下

$e(t_k)=x_r-x(t_k)$ $\phi(t_{k+1}) \leftarrow \lambda_Pe(t_k)+\lambda_I\sum_{j=1}^ke(t_j)\Delta t_j+\lambda_D\frac{\Delta e(t_k)}{\Delta t_k}$

其中：

$e(t_k)$ 误差 error factor
$x_r$ 给定的参考值
$x(t_k)$ 当前的被控变量值
$\Delta t_j=t_j-t_{j-1}$ 更新的时间间隔
$\Delta e(t_k)=e(t_k)-e(t_{k-1})$ 误差变化
$\lambda_P, \lambda_I, \lambda_D$ 控制系数，分布对应 P, I, D

在每次更新之前，所有的控制系数 $(\phi(t),e(t_k),\lambda_P, \lambda_I, \lambda_D)$ 都不变，也就是说在时间 $t_k$ 到时间 $t_{k+1}$ 之间，$\phi(t)$ 不变。

根据上述公式可知，P 系数会将当前的值往参考值靠近，I 系数可以减少从开始到目前为止的积累误差，D 系数可以控制变量的波动避免起伏。（注：这部分的详细理解可以参考 PID控制算法原理）

Waterlevel-based 控制器

WL 控制器是另一种反馈控制模型，最初源于用水位控制的设备，公式如下：

$\phi(t_{k+1}) \leftarrow \phi(t_k)+\gamma(x_r-x(t_k))$

其中 $\gamma$ 是用来控制 $\phi(t_k)$ 的一个指数增长的参数。从公式中我们可以看到，WL 控制器只关注当前值和参考值，输出序列化的控制信号（即下一个控制信号基于当前控制信号）

为最大化点击设定参考值

反馈控制机制可以与任何竞价策略配合，成为一种无需模型的点击最大化架构。设置较好的参考值后，该机制能够自动在多个渠道间自动进行预算分配。本节主要介绍如何寻找这个最佳的参考值。

假设我们在某平台开启了一个针对点击的广告投放计划，对接了 n 个 ADX，假设 $\xi_i$ 是第 i 个 ADX 的 eCPC，$c_i(\xi_i)$ 是对应该广告投放计划整个周期中第 i 个 ADX 最终获得的点击数量（我们通过调整出价达到使其 eCPC 为 $\xi_i$），总预算为 $B$，用公式描述就是：

$max_{\xi_1,...,\xi_n} \sum_i c_i(\xi_i)\ \ \ s.t. \sum_i c_i(\xi_i)\xi_i=B$

具体解方程不赘述，感兴趣可以看论文原文。简单说来就是经过一波数学代换和近似操作，可以得到 $c_i(\xi_i)$ 的多项式表达以及 $\xi_i$ 的方程：

$c_i(\xi_i)=c_i^\ast a_i\left(\frac{\xi_i}{\xi_i^\ast}\right)^{b_i}$ $\xi_i=\frac{b_i}{\alpha (b_i+1)}$

这里有几个新参数，其中：

$\xi_i^\ast$ 是该广告投放计划在第 i 个 ADX 投放中的历史平均 eCPC，可以从历史数据直接计算得出
$c_i^\ast$ 是该广告投放计划在第 i 个 ADX 投放中的历史点击数量，可以从历史数据直接计算得出
$a_i,b_i$ 通过拟合历史数据得出
$\alpha$ 是拉格朗日求解法中的系数，后续需要求解

再经过一波操作得到下面两个公式：

$$\delta_i=\frac{c_i^\ast a_i}{{\xi_i^\ast }^{b_i}}\left(\frac{b_i}{b_i + 1}\right)^{b_i+1}$$ $\sum_i \delta_i\left(\frac{1}{\alpha}\right)^{b_i+1}=B$

对最后一个式子用梯度下降法可以找到数值解，就可以对应计算得出 $\alpha, \xi_i$ 了。在只有 1 个 ADX 的情况下，用这个方法可以直接确定最佳的 eCPC，将其设置为参考值，就可以自动进行点击最大化。

经验研究

本节是在公开是的数据集上进行的试验，试验代码在这里

评估设置

数据集：iPinYou DSP 数据集(35GB)，包含 9 个广告计划 10 天的数据，64.75M 竞价记录，19.50M 曝光，14.79K 点击，16K 元消耗
数据切分：每个广告计划最后 3 天数据为测试集，其他为训练集
特征维度：0.7M
CTR 模型：logistic

利用全部点击曝光和点击数据训练 CTR 模型，然后通过 CTR 模型给出的预测值，得到出价并与获胜价格比较，如果高于获胜价格，则可以曝光，并按照获胜价格计费。控制变量每 2 小时更新一次。

评测方法采用的是在反馈控制系统中比较常用的评估方法：

error band 为正负 10%，也就是如果被控制的变量在参考值的正负 10% 范围内，则认为是成功
rise time 来评价被控变量进入 error band 的时间
overshoot 记录被控变量超过参考值的百分比
RMSE-SS(root mean square error) 进入稳定状态(steady state)后，用来评估被控变量和参考值的差距
SD-SS(standard deviation) 进入稳定状态后，计算被控变量的标准差

首先训练好控制参数，以便能够最快达到稳定状态，然后在测试数据上评估效果。在 eCPC 和 AWR 上的评估结果为

具体的分析会在接下来的章节给出

控制能力

PID 和 WL 两种方法的控制能力如下图所示，其中水平的虚线是参考值。

结合上表和上图可以得出如下结论：

所有的 PID 控制器都可以将 eCPC 和 AWR 控制在 error band 的范围内（注：上表中 WL 方法无法在 40 轮以内 settling）
即使已经通过训练数据找到了比较好的参数，WL 控制器在测试数据上依然表现不佳（尤其是 eCPC 上），原因在于 WL 在 RTB 这种变化巨大的动态场景下能力较弱
WL 的 RMSE-SS 和 SD-SS 都比较高，但是 overshoot 较低（一般来说 rise 时间段，overshoot 就会高）
CTR 预估模型的 AUC 越高，一般来说达到稳定状态的时间就越短
PID 控制器表现不错，原因在于 Integral factor 帮助降低积累误差（如 RMSE-SS），而 Derivative factor 帮助降低了变量波动（如 SD-SS）
相对于 eCPC 来说，AWR 更容易进入稳定状态，因为 AWR 只取决于市场价格的分布，而 eCPC 还包括了用户反馈（如 CTR），使得预测更不确定

控制难度

这一节我们在前面的基础上扩展了试验，设定了不同档位的参考值，考察参考值的设定对控制难度的影响，这里重点关注不同参考值设定的效果对比。

下图是在 eCPC 和 AWR 上不同参考值在 setting time, RMSE-SS, SD-SS 的对比：

通过上图可以发现，参考值越高，setting time, RMSE-SS 和 SD-SS 越低。这个结果也非常符合直觉，因为参考值高，只需要提高出价更多赢得竞价即可。

下图给出了 PID 和 WL 在 eCPC 和 AWR 中设定个不同档位参考值的变化趋势图。可以看到参考值离初始值越远，控制的难度就越大。对于广告主来说，需要在目标值和实际的控制效果间寻找到一个最佳的平衡。

PID 方法中的静态与动态参考值

本小节主要想要探讨的是在 RTB 模式下，如果 PID 方法一开始没有快速接近参考值，是否需要手动调整参考值来达到预期目标。直接上实验结果：

对于 eCPC 来说，动态参考值效果并没有比静态参考值表现好
对于 AWR 来说，动态参考值可以减少到达稳定状态的花费和时间，但是准确度(RMSE-SS)和稳定性(SD-SS)会比静态参考值差很多

总结一下就是直接设定一个静态参考值，剩下的交给 PID

为最大化点击设定参考值

本小节主要想验证分别针对不同的 ADX 设定不同的参考值是否能够真正达到在预算不变的情况下提升点击数量。下面的结果表格中

multiple 针对不同 ADX 设定不同的最优参考值
uniform 针对不同 ADX 设定相同的参考值
none 不用 PID 控制器，直接采用线性的竞价策略

具体结果如下

通过上表我们可以得到如下结果：

使用了反馈控制机制的 uniform 和 multiple 效果比 none 好非常多。点击更多，eCPC 更低，CTR 更高，CPM 更低。也就是说设定好的参考值，是可以起到提升点击的作用的。
通过重新分配预算，multiple 在 8 个测试中的 7 个都比 uniform 有效果提升
在曝光相关的统计中，反馈控制机制通过降低 CPM 提升了曝光量（但同时降低了 AWR）。结果显示分配更多预算到没有那么贵的曝光中可以获得更多的点击（注：这个结果和 ORTB 的结果居然一致了）

下图是三个不同方法的达到稳定状态的趋势图，水平的虚线是三个不同 ADX 的不同参考值，我们可以看到在 multiple 设定下，这三个参考值都可以成功达到。另外我们还可以看到达到稳定状态的速度基本一致的前提下，multiple 可以达到比 uniform 更低的 eCPC，效果更好。

PID 参数调优

本小节主要关于如何对 PID 参数进行调优与线上更新的经验。

关于参数搜索，根据经验 $\lambda_D$ 对控制效果影响较小，一般来说设定一个较小值（如 $1\times 10^{-5}$ 即可降低 overshoot 并稍微减少达到稳定状态的时间，于是我们只要关注 $\lambda_P$ 和 $\lambda_I$。

因为 Grid Search 比较耗时耗算力，所以这里采取了 adaptive coordinate search。每次更新，先固定一个参数，然后调整另一个参数以最快达到稳定状态（每次搜索的 line searching 不常指数级缩小）。一般来说 3 到 4 个迭代就可以找到局部最优解，与 grid search 比较可以发现是非常接近的。

关于设置控制信号 $\phi(t)$ 的上下限，我们发现进行上下限的设定非常重要。在 RTB 场景下，用户的 CTR 可能在某一个时间段下降非常多（即 eCPC 非常高），那么可能就对应一个非常大的负向控制信号，使得出价非常低以至于无法获胜，继而不再有点击和花费。为此，我们设定 $\phi(t)$ 下限为 $-2$ 来降低极端情况的影响。与此同时我们设定 $\phi(t)$ 上限为 $5$ 避免超过参考值太多。

关于在线的参数更新，对于正在运行的 DSP 来说，收集到的新的反馈数据可以立刻进行 PID 控制器的训练和更新。我们在试验中每 10 轮重新训练一次 PID 控制器（一轮 2 小时，重新训练大约花费 10min），下图是两种方式的对比：

观察两种模式我们可以发现（从 10 轮之后开始比较），online 模式对 eCPC 的控制更高效的同时，能够以更小的波动更快到达稳定状态。另外在我们更新 PID 的参数时，不会引起额外的波动和不稳定，也就是说，我们可以基于最新几个小时的数据，不断训练和更新参数来提升控制效果。

在线部署和测试

本文提及的 RTB 反馈控制系统（Python 实现）部署在 BigTree DSP（注：网站已无法打开）上，机器是阿里云的 3 个节点的集群（Ubuntu 12.04, 8Core 8GB RAM）。

使用 2014 年最后 6 个星期的竞价日志作为训练数据来得到 PID 参数，采用 3-fold 验证来评估 PID 控制器的效果，控制信号每 90 分钟更新一次，测试结果如下：

可以看到 PID 控制器效果提升非常明显，在线上更加复杂的环境下依然能够取得比较好的结果。

结论

即使在 RTB 这样非常动态的条件下，使用反馈控制机制仍然可以很好的对 KPI 指标进行控制
不同的参考值对于你个不同的控制难度，最终反映到不同的控制速度、准确度和稳定度上
PID 控制器会自己找到最佳的变量设置值，无需人工干预
设置 eCPC 为最优参考值后，反馈控制器能够自动进行竞价优化

写在最后

悼念李文亮医生。2020.02.07

在这短短半个月里，我通过网络看到了太多太多，五味杂陈，百感交集。我现在能做的就是好好在家，照顾好家人，提高自己，积攒力量，贡献自己的一份力。