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

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

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

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

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

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

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

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

1.4 目標(biāo)及計(jì)劃

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

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

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

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

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

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

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

3.1 問題建模

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下圖是對(duì) 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)鍵動(dòng)作：
1、利用訓(xùn)練數(shù)據(jù)及商用線性規(guī)劃優(yōu)化器gurobi對(duì)原問題和對(duì)偶問題求解，得到對(duì)偶問題最優(yōu)解p和q。
2、利用訓(xùn)練數(shù)據(jù)進(jìn)行最優(yōu)參數(shù)尋找，模擬實(shí)時(shí)競(jìng)價(jià)過程，p i d參數(shù)和擬合系數(shù)alpha、beta通過grid-search 進(jìn)行找尋。
線上參數(shù)部署：
3、用1中參數(shù)初始化線上q和p，2中參數(shù)固定為線上參數(shù)；4、按小時(shí)級(jí)收集競(jìng)價(jià)日志，計(jì)算預(yù)算和點(diǎn)擊/成交成本誤差，通過pid調(diào)控參數(shù)p和q；
整個(gè)流程基本就是這樣，具體細(xì)節(jié)不再這里展開。

四、總結(jié)

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

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