一、廣告業(yè)務(wù)介紹

1.1 廣告的業(yè)務(wù)邏輯

廣告系統(tǒng)中的業(yè)務(wù)邏輯用一句話來表示：廣告主通過付費在媒體對目標(biāo)用戶進(jìn)行營銷信息傳達(dá)，達(dá)成營銷目的的過程。抽取出三個主體，廣告主、媒體和用戶，他們的關(guān)系如下：

其中，廣告主和媒體之間是買賣付費關(guān)系。媒體有很多流量，可以按點擊售賣也可以按曝光售賣，媒體根據(jù)自有流量制定了售賣機(jī)制。廣告主則通過售賣機(jī)制提供的投放方式，建立廣告投放計劃，并付費給媒體。媒體和用戶之間是有訪問展示關(guān)系的，媒體在什么時間什么場景以什么樣的方式的讓用戶看到什么樣的廣告，這是投放策略決定的。本次主要介紹的是轉(zhuǎn)轉(zhuǎn)商業(yè)廣告OCPC產(chǎn)品實現(xiàn)的一種投放策略。

1.2 廣告的系統(tǒng)架構(gòu)

轉(zhuǎn)轉(zhuǎn)搜索廣告系統(tǒng)架構(gòu)圖如下，平臺的投放策略由ZZADECPM模塊（紅框圈定）來承載。本文介紹的投放策略也在這個模塊實現(xiàn)。

1.3 業(yè)務(wù)背景

隨著轉(zhuǎn)轉(zhuǎn)廣告業(yè)務(wù)的發(fā)展，商家的營銷需求也不斷豐富起來。既要有托管的流量包產(chǎn)品去平衡平臺收益和實現(xiàn)小微商家利益最大化[1]，也要有滿足中大型廣告主對成本、收益、流量的有更多把控的優(yōu)店通產(chǎn)品。為了不影響大盤推廣的效果，團(tuán)隊業(yè)務(wù)同學(xué)聚焦二手平臺藍(lán)海品類，圍繞流量充足，物料不夠的現(xiàn)象，綜合產(chǎn)研、運營和銷售的能力和經(jīng)驗，積極探索和制定了OCPC的拉新投放策略，為業(yè)務(wù)發(fā)展打開新局面，給予商家表達(dá)需求的機(jī)會，助力商家進(jìn)行合理的成本控制，讓商家參與進(jìn)來，盤活更多新商家。

1.4 目標(biāo)及計劃

OCPC產(chǎn)品策略的目標(biāo)有兩個，通過AB實驗的方式驗證目標(biāo)是否達(dá)成。

• 1、大盤收入不降的情況下提升ROI；
• 2、提升有效填充（100%相關(guān)性）的ASN、收入和ROI；

各團(tuán)隊合作完成該項目，具體動作：
1、產(chǎn)品同學(xué)負(fù)責(zé)設(shè)計產(chǎn)品方案、運營模式及后期迭代維護(hù)邏輯；
2、銷售和運營同學(xué)針對新產(chǎn)品進(jìn)行售賣及運營話術(shù)設(shè)計和人員培訓(xùn)；
3、技術(shù)同學(xué)負(fù)責(zé)調(diào)研合適的算法模型，設(shè)計合理可實現(xiàn)的優(yōu)化目標(biāo)，選擇匹配的策略方案：多重約束下的pid線性擬合控制方案[2]，也是本文要介紹的重點。

二、OCPC產(chǎn)品項目面臨的挑戰(zhàn)

下圖是廣告業(yè)務(wù)迭代的歷史脈絡(luò)。從2018年開始，在售賣機(jī)制/投放方式上，從最樸素的CPM/CPC類的廣告到衍生出來的基于流量預(yù)估價值去調(diào)整廣告的競價策略，即OCPM/OCPC這樣的平臺能力。為了滿足廣告主進(jìn)一步對成本和預(yù)算控制的需求，本次是BCB（Budget Constrained Bidding）的又一次升級，MCB（Multi-Constrained Bidding）多約束下的競價策略。

本次項目環(huán)環(huán)相扣，需要打通產(chǎn)品、研發(fā)、運行和銷售各個環(huán)節(jié)，各方合力才能保障項目的正常運行。在具體實時過程中面臨的挑戰(zhàn)主要有以下幾個方面：
1）滿足廣告主成本需求及預(yù)算需求的同時需要考慮冷啟動期間要給予廣告主的優(yōu)惠扶持策略；
2）配合產(chǎn)品同學(xué)，設(shè)計合理的算法邏輯，助力產(chǎn)品實現(xiàn)；
3）理解銷售和運營同學(xué)的話術(shù)，能夠用算法策略去進(jìn)行保障；
4）算法策略要優(yōu)先考慮大盤商家ROI，同時能嚴(yán)格把控平臺讓利規(guī)模；
5）優(yōu)化目標(biāo)中指標(biāo)多約束多，算法策略設(shè)計及參數(shù)調(diào)整都有挑戰(zhàn)。

三、OCPC產(chǎn)品策略的實現(xiàn)方案

3.1 問題建模

OCPC項目目標(biāo)抽象出來就是一個帶約束的線性規(guī)劃求最優(yōu)解的問題。廣告主訴求：預(yù)算不超過B，cpc的成本不超過C的情況下，最大化GMV。原始問題 LP1建模如下：

寫出對偶問題 LP2（大同小異，互顛倒）如下：

根據(jù)互補(bǔ)松弛定理，得到兩個等式

然后，論文作者精心設(shè)計了出價公式，帶入公式 8 轉(zhuǎn)化公式 10：根據(jù)等式(10)，如果競價贏得了展示機(jī)會，則并且推導(dǎo)得到如果競價輸?shù)袅诉@次展示機(jī)會，結(jié)合公式 9 和公式 7，推導(dǎo)得到說明最優(yōu)解的公式設(shè)計巧妙且合理。至此，線性規(guī)劃問題 LP1 最優(yōu)解的形式就求解出來了。

3.2 如何求解后驗數(shù)據(jù)的最優(yōu)解及最優(yōu)參數(shù)

這里會用到GNU Linear Programming Kit (GLPK)工具包，專門用來解線性規(guī)劃問題的。一開始使用的是開源工具包 pyomo+python[3]，對于小規(guī)模的問題，可以做到分鐘級別解出。簡單驗算完成后確認(rèn)求解最優(yōu)。但是當(dāng)問題規(guī)模變大時，解答時間接近指數(shù)級增長。如下圖所示：

小規(guī)模問題編碼較為簡單，求解時間也可以接受。下圖是具體實現(xiàn)的偽代碼，索引集合、決策變量、參數(shù)、目標(biāo)及約束條件，最后只需要調(diào)用 Objective 函數(shù)，輸入目標(biāo)即可。

但是當(dāng)問題規(guī)模變大時，耗時問題會嚴(yán)重影響進(jìn)度，因此嘗試使用商業(yè)級軟件 GUROBI[4]。無論是原問題還是對偶問題，即使問題規(guī)模在10w以上，依然能夠在分鐘級解決問題。不由得感嘆，GUROBI 背后的算法優(yōu)化的真是強(qiáng)大。具體安裝過程：

配置好環(huán)境后，就可以使用了。注意！！！這里我使用的是商業(yè)版的，只有2個月的試用期。如果有持續(xù)性需求建議購買正版商業(yè)化產(chǎn)品。

下面是部分具體實現(xiàn)，求解對偶問題的代碼。跟PYOMO的編程語言風(fēng)格較為類似。廣告主不同訴求對應(yīng)的約束不同：

其中alpha和beta分別對應(yīng) p* 和 q*。通過后驗數(shù)據(jù)獲得的最優(yōu)參數(shù)，后面會作為我們最優(yōu)解公式的初始化參數(shù)。

3.3 最優(yōu)出價參數(shù)分析

接下來，我們繼續(xù)講最優(yōu)解的使用。式中p和q對應(yīng)的最優(yōu)參數(shù)，可以根據(jù)后驗數(shù)據(jù)計算得到（3.2.3 節(jié)介紹），但是此時是對過去歷史數(shù)據(jù)的一個最優(yōu)參數(shù)組合。對于未來的最優(yōu)參數(shù)，需要我們自己去探索如何獲得；下面我們來分析最優(yōu)出價公式中的 p 和 q 兩個參數(shù)對預(yù)算和點擊成本的影響。

當(dāng)固定 q 時，從圖中可以看到，減小 p 時，cpc 出價整體提升，反之出價下降；p=0 時，表示沒有了 budget 這個約束。

當(dāng)固定 p 時，從圖中可以看到，減小 q 時，cpc 出價隨之變化，cvr>C * p 時，高價值流量出價進(jìn)一步提升，反之出價下降；增加 q 時，則正好相反，用高出價獲得了更多低 cvr 的流量，丟失了高 cvr 的流量。p=0 時，表示沒有了點擊成本這個約束。

分析以后，發(fā)現(xiàn)p 和 q 參數(shù)本身之間無法做到完全獨立。例如：當(dāng)出價升高時，預(yù)算也會相應(yīng)提高；如何調(diào)控 p 和 q 去優(yōu)化我們的算法，目前主要有兩種解法：

• 強(qiáng)化學(xué)習(xí)的思路，通過設(shè)計狀態(tài)、動作及合理 reward 函數(shù)，進(jìn)行參數(shù)控制，例如[5]；
• 反饋控制方法，也就是本文所采用多pid線性擬合控制方法。更有效的控制耦合效應(yīng)的方法是MPC[6]方法，由于系統(tǒng)耗時等因素，未選該方案，本次介紹不涉及。

3.4 參數(shù)控制-pid 反饋控制系統(tǒng)

下圖介紹了兩種 pid 控制系統(tǒng)，對于獨立控制變量可以選用圖 6，本次主要介紹圖 7 的實現(xiàn)。

下面公式是標(biāo)準(zhǔn) pid 的控制邏輯，公式 13、14、15 依次表示誤差，控制變量及系統(tǒng)輸入；

下圖是對 p 和 q 進(jìn)行線性擬合的公式：

3.5 離線流程及線上部署

總結(jié)一下，3.1介紹了問題建模，3.2介紹了如何用工具求解最優(yōu)解，3.3分析最優(yōu)參數(shù)的意義，選擇合適的參數(shù)控制方法-pid反饋控制，3.4 pid控制系統(tǒng)介紹及使用
離線關(guān)鍵動作：
1、利用訓(xùn)練數(shù)據(jù)及商用線性規(guī)劃優(yōu)化器gurobi對原問題和對偶問題求解，得到對偶問題最優(yōu)解p和q。
2、利用訓(xùn)練數(shù)據(jù)進(jìn)行最優(yōu)參數(shù)尋找，模擬實時競價過程，p i d參數(shù)和擬合系數(shù)alpha、beta通過grid-search 進(jìn)行找尋。
線上參數(shù)部署：
3、用1中參數(shù)初始化線上q和p，2中參數(shù)固定為線上參數(shù)；4、按小時級收集競價日志，計算預(yù)算和點擊/成交成本誤差，通過pid調(diào)控參數(shù)p和q；
整個流程基本就是這樣，具體細(xì)節(jié)不再這里展開。

四、總結(jié)

期間調(diào)研了拼多多 ocpc 的業(yè)務(wù)模式，優(yōu)秀案例，總結(jié)理解他們的目標(biāo)設(shè)計思路。為了保障項目成功，還與相關(guān)領(lǐng)域的專家技術(shù)進(jìn)行了深入探討和交流，系統(tǒng)地整理了業(yè)界發(fā)展進(jìn)程和最新研究，深入地了解了其他家 ocpc 項目的思路方法。為團(tuán)隊技術(shù)賦能打下堅實的基礎(chǔ)。
OCPC 模式在二手商業(yè)廣告領(lǐng)域不斷擴(kuò)展著自己的應(yīng)用領(lǐng)域。本此項目是產(chǎn)品、研發(fā)、運營和銷售團(tuán)隊通力配合的一個項目，算法策略肩負(fù)了核心邏輯實現(xiàn)的重任，是整個項目中順暢運行的潤滑劑。

最終結(jié)果，產(chǎn)品順利上線全量，并拿到預(yù)期的收益：針對有效填充部分的收益，收入、ASN 和 ROI 都有符合預(yù)期的提升: COST +4.61% CASH +4.58% ASN +8.64% TRUE_SHOW +12.16% GMV +23.73% ROI +17.86%；針對大盤的收益，收入持平，GMV 和 ROI 增長：收入持平，TRUE_SHOW +2.41% GMV +10.79% ROI +10.24%；

五、參考資料

[1] Zhu H. et al. 2017. Optimized Cost per Click in Taobao Display Advertising Proceedings of the 23rd International Conference on Knowledge Discovery and Data Mining. ACM, 2191--2200.
[2] Xun Yang, Yasong Li, Hao Wang, Di Wu, Qing Tan, Jian Xu, and Kun Gai. 2019. Bid optimization by multivariable control in display advertising. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1966–1974.
[3] Hart W E, Laird C D, Watson J P, et al. Pyomo-optimization modeling in python[M]. Berlin: Springer, 2017.
[4] https://www.gurobi.com/documentation/9.5/refman/py_python_api_details.html
[5] Di Wu, Xiujun Chen, Xun Yang, Hao Wang, Qing Tan, Xiaoxun Zhang, Jian Xu, and Kun Gai. 2018. Budget constrained bidding by model-free reinforcement learning in display advertising. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management. 1443–1451.
[6] James B Rawlings and David Q Mayne. 2009. Model predictive control: Theory and design. (2009).