2015年yahoo在《Smart Pacing for Effective Online Ad Campaign Optimization》提出了一种smart pacing的策略。

0.摘要

在定向广告中，广告主会在预算范围内在分发约束的情况下最大化竞价效果。大多数广告主通常喜欢引入分发约束（delivery constraint）来随时间平滑地花费预算，以便触达更广范围的受众，并具有持续性的影响。对于在线广告，由于许多曝光会通过公开竞拍(public auctions)来进行交易，流动性（liquidity）使得价格更具弹性，在需求方和供给方间的投标景观（bid landscape）会动态变化。因此，对于同时执行平滑步调控制（smooth pacing control）并且最大化竞价效果很具挑战。本文中提出了一种smart pacing方法，它会同时从离线和在线数据中学习每个campaign的分发步调（delivery pace），来达到平滑分发和最优化效果目标。我们也在真实DSP系统中实现了该方法。实验表明，在线广告活动（online ad campaign）和离线模拟都表明我们的方法可以有效提升campaign效果，并能达到分布目标。

1.介绍

在线广告是一个数十亿美金的产业，并且在最近几年持续两位数增长。市场见证了搜索广告（search advertising）、上下文广告（ contextual advertising）、保证展示广告(guaranteed display advertising)、以及最近的基于竞价的广告的出现。我们主要关注基于竞价的广告（auction-based），它具有最高的流动性，例如：每次ad曝光可以通过一个公开竞价使用一个不同的价格来交易。在市场中，DSPs（Demand-Side Platforms ）是个关键角色，它扮演着大量广告主的代理，并通过许多direct ad-network 或者RTB（实时竞价）广告交换来获得不同的广告曝光，来管理ad campaigns的整个welfare。一个广告主在一个DSP上的目标可以归为：

• 达到分发和效果目标：对于品牌活动（branding campaigns），目标通常是花费预算来达到一个广泛受众、同时使得活动效果尽可能好；对于效果活动（performance campaigns），目标通常是达到一个performance目标（比如：eCPC <= 2美元），并同时尽可能花费越多预算。其它campaigns的目标通常在这两个极端之内。

• 执行预算花费计划(budget spending plan)：广告主通常期望它们的广告会在购买周期内平滑展示，以便达到一个更广的受众，可以有持续性影响，并在其它媒介上（TV和杂志）增加活动。因此，广告主可以定制自己的预算花费计划（budget spending plans）。图1给出了budget spending plan的两个示例：平均步调（even pacing）和基于流量的步调（traffic based pacing）。

图1 不同的预算花费计划

• 减少创意服务开销（creative serving cost）：除了通过由DSPs负责的开销外，也存在由第3方创意服务提供商负责的creative serving cost。现在，越来越多的广告活动会以视频或富媒体的形式出现。这种类型的曝光的creative serving cost可以与优质存货开销（premium inventory cost）一样多，因此，广告主总是愿意减少这样的开销，并且来高效和有效地分发曝光给合适的用户。

3.问题公式化

我们关注两个campaign类型： 1) 品牌广告（branding campaigns） 2) 效果广告（performance campaigns）。其它campaign类型位于两个之间。这些类型的campaign可以具有它自己唯一的budget spending plan。我们首先将该问题公式化来解决，接着给出我们的解法。

3.1 前提

假设Ad是一个ad campaign，B是Ad的预算，G是Ad的效果目标。spending plan是一个随着由K个time slots构成的预算序列，表示在每个time slot上待花费的期望预算数目。我们将AD的spending plan表示为：

\[B = (B^{(1)}, \cdots, B^{(K)})\]

其中，\(B^{(t)} >= 0\)并且 \(\sum_{t=1,\cdots,K} B^{(k)} = B\)。假设\(Req_i\)是由一个DSP接受到的第i个ad request。如第2节所述，我们使用概率节流（probabilistic throttling）来进行budget pacing control。我们表示为：

• \(s_i \sim Bern(r_i)\)：该变量表示：在\(Req_i\)上Ad是否参与竞价。其中：\(r_i\)是在\(Req_i\)上的point pacing rate。\(r_i \in [0, 1]\)表示Ad参与\(Req_i\)上竞价的概率。

• \(w_i\)：该变量表示在\(Req_i\)上参与该次竞价时是否赢得该Ad。它会依赖于通过竞价最优化模块（bid optimization module）给出的竞价\(bid_i\)

• \(c_i\)：当Ad服务于\(Req_i\)时的广告主开销。注意：开销包括inventory cost和creative serving cost。

• \(q_i \sim Bern(p_i)\)：该变量表示当Ad服务于\(Req_i\)时，用户是否会执行一些期望的响应（例如：click）。其中\(p_i = Pr(respond \mid Req_i, Ad)\)是这些响应的概率。

• \(C = \sum_i s_i \times w_i \times c_i\)是ad campaign Ad的总开销。

• \(P=C/\sum_i s_i \times w_i \times q_i\)：ad campaign Ad的效果（performance）（例如：当期望响应是点击时的eCPC）

• \(C = (C^{(1)}, \cdots, C^{(k)})\)：在K个time slots上的spending pattern，其中\(C^{(t)}\)是第t个time slot的开销，\(C^{(t)} >= 0\)并且\(\sum_{t=1,\cdots,K} C^{(k)} = C\)

给定一个广告活动Ad，我们定义：\(\Omega\)是penalty(error) function，它会捕获spending pattern C是如何偏离spending plan B。值越小表示对齐（alignment）越好。作为示例，我们会将penalty定义如下：

\[\Omega (C, B) = \sqrt \frac{1}{K} \sum\limits_{t=1}^K (C^{(t)} - B^{(t)})^2\]

…(1)

3.2 在线广告campaign最优化的Smart Pacing问题

广告主会花费预算，执行spending plan，并同时最优化campaign效果。然而，这样的一个抽象的多目标最优化问题，会有多个帕累托最优解（Pareto optimal solutions）。在真实场景中，广告主通常会为不同campaigns对这些目标定制优化级。对于品牌广告（branding campaigns），广告主通常会将花费预算放在最高优化级，接着是spending plan，而对效果并不很关注。在serving time时（例如：ad request time），由于我们使用概率节流（probabilistic throttling），我们完全可以控制的唯一东西是\(r_i\)。因而，对于没有指定效果目标的ad campaigns的smart pacing问题(smart pacing for ad campaigns without specific performance goals)定义为：决定\(r_i\)的值，以便以下的测算是最优的：

\[\underset{r_i}{min} P \\ s.t. C = B, \Omega (C,B) \leq \epsilon\]

…(2)

其中，\(\epsilon\)定义了违背spending plan的容忍度。相反的，对于效果广告（performance campaigns）具有指定的效果目标，达成效果目标是top优先级。此时坚持spending plan通常是低优先的。我们将smart pacing for ad campaigns with specific performance goals的问题定义为：决定\(r_i\)的值，以便以下测算是最优的：

\[\underset{r_i}{min} \Omega(C, B) \\ s.t. P <= G, B - C \leq \epsilon\]

…(3)

其中，\(\epsilon\)定义了没有花光所有预算的容忍度。由于市场的动态性，对于两个单目标最优化问题很难解决。在工业界已存在被广泛使用的方法，只会捕获效果目标，或者只会捕获预算花完目标。达到效果目标的一个示例是：对retargeting beacon触发ad requests，总是竞价。不幸的是，避免过度消费（overspending）或者欠消费（underspending）是无保障的。对于平滑步调控制（smooth pacing control）的另一个示例是，引入一个全局pacing rate，以便ad requests具有相同的概率被一个campaign竞价。然而，这些已经存在的方法没有一个可以解决我们公式化的smart pacing问题。为了解决该问题，我们研究了流行的campaign setups，并做出一些关键观察（可以启发我们的解法）：

• CPM campaigns：广告主对于每个曝光会会付定固定数目的钱。对于品牌广告主（branding advertisers），campaign最优化的定义如公式2所示。只要预算可以被花费，并且spending pattern会随plan安排，高响应广告请求会比低响应的具有一个更高的point pacing rate，以便效果可以被最优化。对于效果广告主（performance advertisers，例如：eCPC、eCPA为目标），campaign最优化的定义如公式3所示。很明显，高响应的ad requerest应具有更高的point pacing rate来达到performance目标。

• CPC/CPA campaigns：广告主会基于clicks/actions的绝对数目进行付费。显式效果目标是，保证当代表广告主进行竞价时，DSP不会损失钱。因此，这种optimzation的定义为等式(3)。授于高responding ad request以高point pacing rates，从广告主和DSP的视角来说会更有效：广告主会在creative serving cost上花费更少，而DSP可以节省更多ad机会来服务其它campaigns。

• 动态CPM campaigns：DSP会为每个曝光花费一个动态数目的钱，而非固定。这些campaigns通常具有指定效目的目标，以便最优化问题会落在等式(3) 中。与CPC/CPA campaigns相似，高responding ad requests会更受偏爱，以便减少creative serving cost以及节约ad机会。

3.4 解法汇总

受这些观察的启发，我们开发了新的heuristics来求解smart pacing问题。该heuristics尝试找到一个可行解，它会满足如等式2或3定义的所有constraints，接着进一步通过feedback control来最优化目标。

• 首先从离线服务日志中构建一个response prediction模型来估计\(p_i = Pr(respond \mid Req_i, Ad)\)，它会帮助我们区分高响应广告请求 和 低响应广告请求。
• 第二，我们会通过将相似的响应请求group在一起来减小solution space，并且在相同group中的请求会共享相同的group pacing rate。使用高responding rates的groups会具有高的pacing rates（比如图2(a)中的蓝色箭头）。
• 第三，我们会开发一个新的control-based的方法来从在线feedback data中学习，并能动态调整group pacing rates来逼近最优解。

不失一般性，我们假设campaign setup是具有/没有一个eCPC目标的CPM计费。我们的方法可以应用到其它计费（billing）方法上 ，效果广告或者其它grouping策略，比如：基于\(p_i/c_i\)的grouping。（期望的response per cost）

图2 概率节流（Probabilistic Throttling） vs. 竞价修改（Bid Modification）的因子依赖图。灰色的因子涉及到budget pacing control。在pacing rate和response rate间添加依赖是其中一个关键点.

4.response预测

我们的解法依赖于一个准确的response prediction模型来预估\(p_i\)。如第2节，有许多文献解决该问题。这里我们简单描述了如何执行该预估。我们会使用在(2,11)中的方法，并基于它做出一些改进。在这种方法中，我们首先利用在数据中的层次结构来收集具有不同间隔的response feedback features。例如，在ad侧，从root开始，接着一层接一层是：advertiser category，advertiser，campaign，最后是ad。在层次结构的不同levels上的历史响应率（historical response rates）可以当作features来使用机器学习模型（LR、gbdt等）来给出一个\(p_i\)的原始预估（raw estimation），称为\(\hat{p}_i\)。接着我们使用属性（比如：用户的age、gender）来构建一个shallow tree。树的每个叶子节点标识一个关于ad requests的不相交集合，它可以进一步划分成具有不同平均响应率的子集。最后，我们会在叶子节点\(Req_i\)内对\(\hat{p}_i\)进行微调，使用一个piecewise linear regression来估计最终的\(p_i\)。该scheme会生成一个公平的accurate response prediction。

5.control-based的解法

在一个在线环境中，很难达到完全最优解来解决等式（2）和等式（3）的问题。我们采用启发法来减小原始问题的解空间。更特别的，使用第4节中描述的response prediction模型，相似的，responding ad requests会分组到一起，他们会共享相同的group pacing rate。不同分组会具有不同的group pacing rates来影响在高responding ad request groups上的偏好。原始问题（求解每个\(r_i\)的point pacing rate）会简化成求解一个group pacing rates的集合。我们会采用control-based的方法来调节group pacing rates以便online feedback data可以立即用于campaign最优化。换句话说，group pacing rates会通过campaign的生命周期动态调节。出于简洁性，在本文其它地方，pacing rate和group pacing rate会相通，我们会在第l个group的group pacing rate表示为\(r_l\)。

5.1 层级表示（Layered Presentation）

对于每个ad campaign，我们会维护一个层级数据结构，其中每层对应于一个ad request group。我们会以层级数据结构来保存每个ad request group的以下信息：

• 平均响应率（通常是：CTR、AR等，它来自response prediction模型）
• ad request group的优先级
• pacing rate（例如：在ad request group中对一个ad request的竞价概率）
• campaign在该ad request group中在最新time slot上的花费

这里的原则是：

• 1) 对应于高响应ad request groups的layers应具有高优先级
• 2) 高优先级layer的pacing rate应会比一个低优先级layer要更小

对于每个campaign，当DSP接收到一个合格的ad request时，它会首先决定：该ad request 会落在哪个ad request group上，指的是相应的layer来获得该pacing rate。DSP接着会代表campaign来竞价，它的概率会等于由一个preceding bid 最优化模块给出的retrieved pacing rate。

5.2 Online Pacing Rate调节

我们基于实时反馈，来采用一个control-based方法来调节每层的pacing rate。假设我们具有L个layers。对于每个layer，由response prediction model给出的response rate预估是：

\[p=(p_1, \cdots, p_L)\]

这里，如果期望的response是click，那么预估的每层的eCPC是:

\[e(e_1, \cdots, e_L)\]

其中：\(e_i = \frac{CPM}{ 1000 \times p_i}\)。假设每层的pacing rate在第t-1个time slot上是：

\[r^{(t-1)} = (r_1^{(t-1)}, \cdots, r_L^{(t-1)})\]

那么，每个layer的spending为：

\[c^{(t-1)} = (c_1^{(t-1)}, \cdots, c_L^{(t-1)})\]

对于将要到来的第t个 time slot会基于campaign目标，control-based的方法会预估：

\[r^{(t)} = (r_1^{(t)}, , \cdots, r_L^{(t)})\]

图3 加速budget spending的一个示例

5.2.1 没有performance目标的Campaigns

我们首先描述对于没有指定效果目标的ad campaigns的微调算法。对于这种campaign类型，首要目标是花费预算，并根据budget spending plan进行安排。因而，在每个time slot的end，算法需要决定在下一个time slot中的预算量，并调整layered pacing rates来花费该量。

在下一time slot中的待花费预算，由当前预算花费状态来决定。给定一个ad campaign，假设它的总预算是B，budget spending plan是\(B = (B^{(1)}, \cdots, B^{(K)})\)，在运行m个time slots后，剩余预算变为\(B_m\)。我们需要决定在每个剩余time slots中的花费，表示为\(\hat{C}^{m+1}, \cdots, \hat{C}^{(K)}\)，以便总预算可以花完，penalty最小。

\[\underset{\hat{C}^{(m+1)}, \cdots, \hat{C}^{(K)}}{arg min \Omega} \\ s.t. \sum\limits_{t=m+1}^k \hat{C}^{(t)} = B_m\]

…(4)

其中，如果我们采用等式（1）的\(\Omega\)定义，我们具有以下的最优化公式：

\[\hat{C}^{(t)} = B^{(t)} + \frac{B_m - \sum_{t=m+1}^K B^{(t)}}{K - m}\]

…(5)

其中，\(t=m+1, \cdots, K\)。我们会触发该细节：由于页面限制，如何估计\(\hat{C}^{(t)}\)。在在线环境中，假设在最新的time slot中的实际花费是\(C^{(t-1)}\)，我们定义\(R=\hat{C}^{(t)} - C^{(t-1)}\)是residual，它可以帮助我们来做出调整决策。

算法1

算法1给出了adujstment是如何完成的。假设：index L表示最高优先级，index 1表示最低优先级，假设\(l'\)是具有非零pacing rate的最后一层。

• 如果R=0, 则不需要做adjustment。
• 如果R>0，这意味着需要加速分发，pacing rates会以一种自上而下的方式进行调整。

从第L层开始，每一层的pacing rate会随层数一层层增加，直到第\(l'\)层。第5行会计算当前层的期望pacing rate，为了offset R。当第\(l' \neq 1\)时并且它的updated pacing rate \(r_{l'}^{(t)} > trial \ rate\)时，我们给第\(l' - 1\)层一个trial rate来准备进一步加速，如果R< 0，这意味着分发会变慢，每一层的pacing rate会以自底向上的方式减小，直接R是offset。第11行会生成当前layer到offset R的期望的pacing rate。假设l是最后要调的layer，\(l \neq 1\)和它的新的pacing rate \(r_l^{(t)} > trial \ rate\)，我们会给出第\(l-1\)层的trail rate来准备进一步加速。图4是一个分发如何变慢 的示例。

图4 一个减少budget spending的示例

我们注意到，在在线环境中，该greedy策略会尝试达到等式（2）的最优解。在每个time slot内，它会努力投资inventories，并在总预算和speding plan约束下具有最好的效果。

5.2.2 具有效果目标的Campaigns

对于指定效果目标的campaigns（例如：eCPC <=2美元），pacing rate adjustment是有点复杂。很难预见在所有未来time slots内的ad request traffic，并且response rate分布可以随时间变化。因此，给定预算花费目标，利用在当前time slot中的所有ad requests，它们满足效果目标，不是等式（3）的最优解。算法2描述了对于这种类型的campaigns如何来完成adjustment。我们采用heuristic来进一步基于效果目标进行adjustment，它会添加到算法1中。

算法2

如果在算法1后的期望效果不满足效果目标，pacing rates会从低优先级layers one-by-one的减少，直到期望效果满足目标。第7行会生成current layer的期望pacing rate，并使整体期望eCPC满足目标。在第2行，第4行的函数\(ExpPerf(c^{(t-1), r^{(t-1)}, r^{(t)}, e, i}\)会估计layers \(i, cdots, L\)的期望联合eCPC，如果pacing rates会从\(r^{(t-1)}\)调整到\(r^{(t)}\)，其中，\(e_j\)是layer j的eCPC。

\[ExpPerf(c^{(t-1)}, r^{(t-1)}, r^{(t)}, e, i) = \frac{\sum\limits_{j=i}^L \frac{c_j^{(t-1) \times r_j^{(t)}}{r_j^{(t-1)}}}}{\sum\limits_{j=i}^L} \frac{c_j^{(t-1)} \times r_j^{(t)}}{ r_j^{(t-1)} \times e_j }}\]

…(6)

5.3 Layers的数目，初始化和Trial Rates

设置layers的数目，intial和trial pacing rates很重要。对于一个新的ad campaign，它没有任何分发数据，我们在DSP中标识出最相似的最已存在ad campaigns，并估计一个合适的全局pacing rate \(r_G\)，我们期望新的campaign可以花完它的预算。接着layers的数目设置为\(L = [\frac{1}{r_G}]\)。我们表示：一个合适数目的layers要比过多数目的layer更重要：

• 1) 如果有许多层，每个layer的分发统计并不重要
• 2) 从系统角度看，过多数目的layers会使用更多宽带和内存

一旦layers的数目决定后，我们会在第一个time slot上运行全局pacing rate \(r_G\)。我们将该step称为一个intialization phase，这里分发数据可以被收集。我们将相同数目的曝光，基于它们的预测response rate来来标识layer分界，将它们分组（group）到期望数目的layers上。在下一time slot上，每一layer的pacing rate会基于在下一time slot的计划预算来重新分配，高响应layers会具有1.0的rates，而低响应layers将会具有0.0的rates。

在adjustment算法中，具有非零pacing rate相互挨着的直接连续的layer，会分配一个trial pacing rate。目标是在该layer收集分发数据，并准备将来加速。该trial rate假设相当低。我们通过保留预算的一个特定比例\(\lambda, e.g. \lambda=1%\)，生成这样一个rate，来在下一time slot中花费。假设trial layer是第l层，下一time slot上的预算是\(\hat{C}^{(t)}\)，我们会在至少一个time slot（初始阶段）上具有该layer的历史花费和pacing rate，trial pacing rate会生成：\(trial \ rate = r_l^{(*)} \times \frac{\lambda \times \hat{C}^{(t)}}{c_l^{(*)}}\)，其中：\(c_l^{(*)}\)和\(r_l^{(*)}\)是第l层的历史花费，以及pacing rate。

快速总结下，我们采用一个基于predicted response rate生成的关于所有ad requests的分层表示，并在每个layer level上执行budget pacing control来达到分发和效果目标。在当前time slot上的预算，以及剩余预算会被考虑来计算在下一time slot上的layered pacing rates。我们也尝试另一种方法来控制一个threshold，以便超过该threshold的predicted response rate的ad requests可以竞价。这种方法的缺点是不能令人满意。主要 原因是，ad requests通常不随response rate平滑分布，因此，在单个threshold上很难实现平滑控制。

6.实验评估

参考

• 1.https://arxiv.org/pdf/1506.05851.pdf