合約廣告中基于風險限制的Pacing算法優化

摘要：本文提出一種适用于合約保量廣告的預算平滑Pacing算法，該算法通過對偶出價因子的百分位位置關聯調控Pacing，相容保量配置設定機制的同時，有效控制了預算釋放過快的風險，并且最大程度兼顧了投放效果的提升。基于該項工作整理的論文已發表在AAAI'24，歡迎閱讀交流。

論文：Percentile Risk-Constrained Budget Pacing for Guaranteed Display Advertising in Online Optimization

下載下傳（點選↓閱讀原文）：https://arxiv.org/abs/2312.06174

一、背景介紹

1.1 業務場景

合約廣告（Guaranteed Delivery，GD）是通過合同形式，為品牌或直播廣告主在指定時間内，在圈定的目标人群上觸達确定數量的曝光。和效果廣告的實時競價相比，GD 廣告采用曝光的合同固定價格計費，并且具有強保量的限制，也是廣告主在大促時期确定性擷取流量的重要廣告形式。合約廣告的線上配置設定機制中，通常基于「對偶理論」，采用"虛拟出價"（如 bid=CTR-對偶）的方式進行流量優選（0價過濾）和配置設定（最高價競得），在滿足保量限制的前提下，最大限度優化投放效果。除了合約廣告，有很多場景有采用類似的模組化方式，如：

• push次數有限的情況下，最大化使用者點選次數等；
• 消費券數量有限情況下，最大化轉化率/成交uplift。

1.2配置設定模組化

假設我們以優化 CTR 為目标，對于第次請求召回的廣告的預估價值為，原問題可以模組化成：

根據原始對偶可以推導出，虛拟出價公式為：

其中 是根據廣告消耗速度的快慢，基于回報算法（如PID等）進行調整得到的。虛拟出價後，再通過 0 底價過濾和出價排序，最終選取top1廣告傳回，過程表示為：

其中，表示召回率，表示Pacing子產品的随機通過率，表示參競率，表示競得率。是以，一段時間内廣告的曝光計費次數，可以串行漏鬥來表示：

1.3平滑問題

雖然理論上原始對偶方法可以實作最優的線上配置設定，但是在實際投放過程中，我們面對的是一個動态配置設定問題。如果隻使用“虛拟出價”，非常容易出現不平滑的情況。比如，對偶因子初始值不合理，廣告可能在幾分鐘之内釋放完一個小時的預算；另外，PID回報調整的步長設定不合理，也可能導緻廣告從完全沒展現到瞬間“爆量”。不平滑釋放會帶來兩方面問題：

1）業務方面：廣告主希望預算均勻消耗，尤其是主播希望均勻引流，長時間無量或者爆量會帶來客訴和資損；

2）效果方面：對廣告感興趣的使用者是随着大盤流量均勻到達的，不平滑投放會浪費後續投放到優質流量的機會，對效果有損。

二、技術挑戰與算法思路

2.1 現有算法

現有廣告裡平滑投放算法，主要有三類可以借鑒：

• Bid Modification（出價修改）：相當于沒有Pacing子產品，通過參競率來間接實作，回報速度慢且對于小訂單風險巨大（如初始值不合理預算瞬間花完），達不到較好的預算平滑效果
• Probabilistic Throttling（機率節流）：簡單高效，在RTB使用廣泛，但是在合約廣告裡，直接使用會帶來一個問題，同時用一個信号（預算消耗速度）回報調整兩個參數（出價&Pacing），會出現互相幹擾、控制混淆，引起保量風險和平滑問題。舉個例子，廣告釋放過快，應該調低出價，還是調低Pacing通過率？
• Regularization（配置設定正則項）：在之前合約配置設定模型模組化常采用正則項，以實作平滑或者均勻配置設定，但是這種方法的正則項超參數是固定的，無法在投放中自适應調整。

綜上，現存的方法并不能很好解決我們的問題。

2.2 合約業務挑戰

分析我們業務裡面平滑釋放的挑戰，主要包含以下因素：

1）靜态因素

• 預定量：不同廣告的保量目标從幾千到幾百萬PV不等
• 定向：不同廣告的定向人群、定向資源位不同
• 優化目标：不同廣告優化目标不同（轉化率/停留時長/進店率等），不同類型的目标分布差異極大，如轉化率~0.1%，點選率~10%，僅打分的平均值就相差百倍，導緻調控的初始化和步長配置非常複雜

2）動态因素

假設有兩個廣告 Ad1 和 Ad2，除了 Ad1 的流量供給大很多，其他靜态因子都相同的情況下，最終收斂後 Ad1 的對偶因子一定高于 Ad2 的對偶因子。這意味着：

• 由于 Ad1 的流量供給大于 Ad2，Ad1 更容易“爆量”；
• Ad1 的虛拟出價遠低于 Ad2， Ad1 的競得率更容易受其他訂單的影響；
• 從參競率的角度，如果對偶因子回報調整相同距離，或者打分分布發生變化，Ad1 的波動也比 Ad2 更大，可以用下圖來表示這個過程：

2.3 算法設計思路

平滑投放的主要挑戰來自于釋放過快，因為消耗是無法回撤的，而釋放過慢可以通過後期回報進行調整後加速。設計合約廣告中的Pacing算法，需要考慮以下幾點：一方面通過 Pacing 随機通過率，來控制廣告的流量供給，把對偶因子限制在安全的百分位範圍内，避免由于調控出現參競率太大的波動。另一方面，Pacing如果過濾流量太多，會讓對偶因子處于較低百分位，雖然沒有平滑風險，但是會随機丢棄大量優質流量，不利于效果提升。是以一個合格的合約Pacing算法，需滿足以下三點要求：

• 1）不能破壞合約保量配置設定機制，不幹擾到對偶因子的調控，否則有缺量風險；
• 2）能有效控制平滑風險（對偶百分位不能太高）；
• 3）盡量避免丢棄優質流量，減少效果損耗（流量充足情況下，對偶百分位不能太低）。

三、風險限制的Pacing算法細節

3.1雙向變換

為了解決不同打分類型分布不一緻，導緻“對偶初始化”以及”調控步長“難以統一設定的問題，一個很簡單的思路，是将所有打分通過之前落盤打分日志，統一變換到 [0,1] 的均勻分布。但是這帶來的問題是，我們的求解目标從變成了。盡管百分位變換是保序，但是其非線性變換的特性，将導緻百分位空間的最優解并不是原問題的最優解（不同類型分數，競得率的公平性不在讨論範圍内）。基于此，我們采用了雙向變換：

1）效果分前向變換：原空間() => 百分位()，将打分映射到百分位空間，在百分位空間調整對偶。通過對偶在百分位空間的位置，可以感覺爆量風險（比如目前對偶調整到 0.99，說明參競率為1%，爆量風險較高），并在pacing政策采取對應調整措施限制風險；

2）對偶後向變換：百分位() => 原空間()。在百分位空間調整對偶後，反向變換到原空間，是以bid 的計算還是在原來的空間，保證我們求解的是原問題的最優解。

原空間到百分位空間的變換，可以基于非參數方法（如累計直方圖統計），也可以采用參數化方法變換。這裡我們采用了參數化的 BoxCox 方法，将原空間變換到正态分布，再通過标準化轉換為标準正态分布，最後通過标準正态分布的累積分布函數(CDF)，變換成0到1的均勻分布，即百分位空間。變換過程如下圖所示：

後向變換與上述過程正好相反，互為逆函數。

3.2PTR粗估

上述我們分析了對偶的百分位越高，對應廣告的參競率越小，不平滑風險越高。是以我們希望 Pacing 子產品通過随機通過功能，将每個廣告的對偶的百分位 限制在一個安全門檻值内。例如 表示期望收斂後，此時廣告有top 5%的優質流量參競，餘下的 95% 流量bid為負被底價過濾。假設廣告定向的人群大小為，全局的競得率為 ， 通過之前的流量漏鬥公式，可以粗估出Pacing的通過率()為：

百分位對偶值初始化可以表示為：

3.3PTR微調

盡管我們在離線對 PTR 進行了粗估，但是在實際投放過程中，粗估值和實際線上投放情況可能有較大誤差，是以需要根據線上情況進行微調。微調函數我們分解為兩個函數：

1）對偶關聯

• 線上實際投放中如果，說明偏小，需要增加流量供給，減少缺量風險和優質流量損耗；反之則說明 偏高，需要快速降低以限制風險，我們用兩段指數函數來進行微調：

函數如下圖所示：

2）出價權重

• 受到 smart pacing 論文的啟發，效果越好的流量，PTR 應該更高。對應到我們的算法中，對于同一個廣告來說，即 bid 越高通過率越高。如果用原空間的bid權重，由于廣告的打分分布差異很大，bid也有很大的差異，不利于統一設定權重倍率。是以，我們在百分位空間進行權重，這裡我們采用簡單的線性權重，即：

如下圖所示：

相比于，是根據線上實時的“虛拟出價”進行權重的，是完全實時自适應的。舉個例子，比如我們歸一化參數更新不及時或者計算有偏差，導緻變換後的打分分布是的均勻分布，對于函數來說，會在離線粗估的 PTR的基礎上添加較大的倍數 ，存在爆量的風險，而對于函數來說則不存在這樣問題。

3.4梯度裁剪

在 PID 回報調控算法中，如果步長太大，調控容易出現大幅抖動，如果太小回報調整的反應速度又太慢。一種常見的做法是靜态梯度裁剪。假設限制相鄰兩次調整的對偶調整最大距離為， 通過 PID 算法計算出下一次百分位空間的對偶因子的值為 , 則下一次百分位對偶變量更新值為：

這種做法的一個缺點是，對偶因子在不同的百分位位置調整，帶來的波動其實是不一樣的。如百分位對偶從0.9 調整到 0.8，參競率（PR）可以從 0.1 增加到 0.2出現翻倍現象；百分位對偶從 0.2 調整到0.1，PR 則僅從 0.8 增加到0.9，幾乎沒有變化。上述隻分析了百分位對偶調整對于參競率的影響，此外，百分位對偶的調整還會影響到 PTR 和 WR。以下推導基于廣告出現缺量情況：根據回報算法 将往下調。假設該廣告的召回率、打分分布、線上競價環境在這期間沒有發生變化，會發生以下變化：

• 會增加。競價環境不變，下調對偶會提升 bid ，top1排序機率變大；
• 會增大。随着下調提高權重倍率；
• 也會增大。下0 底價過濾的比例也會降低。

假設我們廣告在第次周期中的真實消耗是，期望消耗是，則釋放速度可義為：

理想的調控結果是讓輪的消耗速度為1。上面分析了 WR、PTR 和 PR 都會增加，由于競價環境是未知的，增加倍率無法計算，但是如果 增加到了 倍，那麼廣告在輪的釋放速度肯定就超過 1 了，這就是我們調整範圍的下限。定義函數 ：

實際求解時，可以通過蒙特卡洛重要性采樣的方法進行積分計算。具體做法是：随機在有顔色區域的軸上打1000個點得到平均高度，乘以寬度就即為 。然後用二分查找法找到 的下限：下圖表示函數 ：

線上上實際使用時，我們采用的是靜态 + 動态梯度裁剪的方法雙管齊下來控制風險：

3.5可變步長

梯度裁剪隻是限制了更新的上限和下限，實際的更新的步長也有較大的優化空間。直覺上， 越靠近 1，PR 波動越大，此時步長應該越小；反之越靠近 0，PR 波動越小，不平滑的風險也更小，步長也應該設定更大。這個直覺上的判斷，可以通過數學推導得到一個可變更新步長，詳情可以查閱我們發表在 AAAI'24的論文：Percentile Risk-Constrained Budget Pacing for Guaranteed Display Advertising in Online Optimization (https://arxiv.org/abs/2312.06174，點選↓閱讀原文↓)。

3.6止血控制

以上所有的政策，都是基于梯度更新實作的。梯度更新有一個較大的問題是，當線上已經發生“爆量”情況，往往需要多次更新才能控制“險情”，這時候小時預算往往已經消耗完畢。針對這種情況，我們采用比例調控的方式，額外增加一個通用率進行及時止血，把廣告的釋放速度控制在2倍，既能防止損失進一步擴大，也能讓對偶因子朝着正确的梯度方向進行逐漸調整，止血調控的通過率計算公式為：

是以最終的的Pacing，由兩個機率通過子產品串行組成：

3.7冷啟問題

在廣告剛上線的幾分鐘，止血通過率可以設定成 10% 進行小流量試探，防止對偶初始化不準确導緻不平滑現象。

3.8流量傾斜

在合約業務裡，往往還有很多業務需求需要對部分流量進行權重投放，如通投廣告主中需要對廣告主圈選的人群進行流量傾斜、部分資源位流量傾斜等，可以從兩方面進行幹預：

• Pacing 對需要傾斜的流量進行通過倍率權重，以增加 PTR；
• Bid 環節對需要傾斜的流量進行出價權重，以增加 PR 和 WR。

如果流量傾斜需要達到某個目标，則權重因子需要通過回報調節鍊路進行調整。

3.9 整體流程

總結起來，Pacing 算法的流程如下：

1）設定超參數

• 全局參數：安全百分位門檻值，步長，靜态梯度裁剪；
• 廣告參數：預算，定向人群大小，止血冷啟動通過率。

2) 離線計算

• 對于每個廣告：根據供需比計算基礎通過率；
• 計算分位對偶初始值；
• 根據廣告優化目标的類型，通過曆史日志統計對應目标類型的歸一化參數（包括 boxcox參數、均值、标準差）。

3）線上決策

• 對于召回的廣告清單：用 RTP DNN模型預估分數；
• 将打分轉換到百分位空間；
• 将百分位對偶通過後向變換成原空間對偶；
• 計算原空間出價和百分位空間出價；
• 0 底價過濾；
• 通過、 和計算通過率；
• 計算最終Pacing通過率 ；
• 以的機率保留廣告；
• 按照原空間出價 排序；
• 選取 Top 1 傳回。

4）近線調控

• 每隔兩分鐘進行一次近線調控；
• 計算上次調控的釋放速度；
• 根據PID 算法（或動态步長算法），計算本次百分位空間的對偶值；
• 通過蒙特卡洛重要性采樣，計算動态梯度裁剪的上下界；
• 進行靜态 + 動态梯度裁剪，得到更新後的百分位對偶；
• 根據釋放速度，通過止血調控更新公式，得到止血通過率 ；
• 将 和推送到線上，進行下一輪線上決策。

4.業務效果

互動合約廣告對平滑投放要求較高，算法側經過一段時間的疊代和優化，逐漸形成了以上基于百分位風險限制的Pacing政策，并通過了日常投放、雙十一大促等各方面考驗。在日常互動商業上場景上，我們對出價權重進行了消融實驗，相比于無出價權重政策，收藏加購購買率 及 吸粉入會率均有所提升，平滑釋放和效果提升達到了較好的平衡。

5. 總結

本文提出一種适用于合約保量廣告的預算平滑Pacing算法，該算法通過對偶出價因子的百分位位置關聯調控Pacing，相容保量配置設定機制的同時，有效控制了預算釋放過快的風險，并且最大程度兼顧了投放效果的提升。實驗表明，該方案使平滑釋放和效果提升達到了較好的平衡。

▐參考文獻

[1] Budget pacing for targeted online advertisements at linkedin. KDD 2014

[2] Dual mirror descent for online allocation problems. PMLR 2020

[3] Clustering with Bregman divergences. JMLR 2005

[4] Shale: an efficient algorithm for allocation of guaranteed display advertising. KDD 2012

[5] The Box-Cox transformation technique: a review

[6] Smart pacing for effective online ad campaign optimization. KDD 2015

[7] An Adaptive Unified Allocation Framework for Guaranteed Display Advertising. WSDM 2022

作者:覺一、天穿

來源-微信公衆号:阿裡媽媽技術

出處:https://mp.weixin.qq.com/s/2QZsyHrMusYSEnt_E7WmUw