WSDM 2022 | 一种用于在线广告自动竞价的协作竞争多智能体框架
丨目錄：
· 摘要
· 背景
· 基礎(chǔ)概念
·??IL的行為分析
· 我們的方法
· 實(shí)驗(yàn)
· 總結(jié)
· 參考文獻(xiàn)
??摘要
在在線廣告中，自動(dòng)競(jìng)價(jià)已經(jīng)成為廣告主優(yōu)化自身廣告性能的必需工具，自動(dòng)競(jìng)價(jià)允許廣告主通過簡單地設(shè)置計(jì)劃目標(biāo)以及相應(yīng)約束來優(yōu)化其關(guān)心的廣告性能指標(biāo)。之前的工作大多從單智能體的角度考慮自動(dòng)競(jìng)價(jià)問題，少有考慮建模智能體之間的相互影響。本文從分布式多智能體系統(tǒng)的角度研究自動(dòng)競(jìng)價(jià)智能體的設(shè)計(jì)問題，并提出了一個(gè)通用的多智能體自動(dòng)競(jìng)價(jià)框架，稱為MAAB（Multi-Agent Auto-bidding)，用以學(xué)習(xí)自動(dòng)競(jìng)價(jià)策略。首先，我們研究自動(dòng)競(jìng)價(jià)智能體之間的競(jìng)爭與合作關(guān)系，并提出了一種基于溫度調(diào)控的獎(jiǎng)勵(lì)分配機(jī)制來建立自動(dòng)競(jìng)價(jià)智能體之間的混合協(xié)作競(jìng)爭關(guān)系。通過調(diào)節(jié)競(jìng)價(jià)智能體之間的協(xié)作與競(jìng)爭，從而達(dá)到了一種能夠同時(shí)保證廣告主自身效用和社會(huì)福利最大化的均衡狀態(tài)。其次，我們觀察到協(xié)作關(guān)系會(huì)引導(dǎo)智能體走向共謀出低價(jià)的行為模式，從而破壞平臺(tái)生態(tài)。為了解決這個(gè)問題，我們引入了門檻智能體來為每一個(gè)自動(dòng)競(jìng)價(jià)智能體設(shè)置一個(gè)個(gè)性化的競(jìng)價(jià)門檻。第三，為了將MAAB部署到擁有數(shù)百萬廣告主的大型廣告系統(tǒng)中，我們提出了一種基于平均場(chǎng)方法，通過將目標(biāo)相同的廣告主分組為一個(gè)均值自動(dòng)競(jìng)價(jià)智能體，廣告主之間的復(fù)雜交互得以簡化，從而使MAAB得以高效訓(xùn)練。在工業(yè)離線數(shù)據(jù)集以及阿里巴巴廣告平臺(tái)的實(shí)驗(yàn)表明，本文的方法在社會(huì)福利以及平臺(tái)收入上能夠超越基準(zhǔn)算法。
論文下載：https://arxiv.org/pdf/2106.06224.pdf
??背景
在線廣告已經(jīng)成為廣告主提高其產(chǎn)品曝光機(jī)會(huì)的一種不可或缺的工具。在傳統(tǒng)的廣告拍賣中，廣告主需要對(duì)每一次廣告拍賣進(jìn)行手動(dòng)出價(jià)，然而這種細(xì)粒度的出價(jià)過程需要廣告主對(duì)參竟環(huán)境有全面的了解。為減輕廣告主的競(jìng)價(jià)優(yōu)化負(fù)擔(dān)，在線平臺(tái)部署了各種類型的自動(dòng)出價(jià)服務(wù)，例如谷歌的 AdWords 廣告活動(dòng)管理工具、百度的鳳巢以及淘寶的超級(jí)推薦產(chǎn)品。這些服務(wù)使得廣告主可以通過簡單地表達(dá)其目標(biāo)和約束，然后由自動(dòng)出價(jià)智能體優(yōu)化其廣告效果。在線廣告的自動(dòng)出價(jià)的過程如下圖所示：
其中自動(dòng)出價(jià)智能體由廣告平臺(tái)負(fù)責(zé)設(shè)計(jì)，該智能體目標(biāo)是在廣告主設(shè)置的約束下，根據(jù)廣告主設(shè)置的目標(biāo)來優(yōu)化其出價(jià)策略。在阿里媽媽超級(jí)推薦&引力魔方上存在多種訴求，大體可以分為三類：優(yōu)化點(diǎn)擊、優(yōu)化成交和優(yōu)化收藏加購。這些自動(dòng)出價(jià)智能體之間存在相互競(jìng)爭關(guān)系。為了學(xué)習(xí)自動(dòng)競(jìng)價(jià)智能體的競(jìng)價(jià)策略，最自然的方式就是去為每一個(gè)自動(dòng)競(jìng)價(jià)智能體求解一個(gè)獨(dú)立的優(yōu)化問題，而將其他智能體出價(jià)的影響隱式地建模為環(huán)境的一部分。然而這種方式忽略了拍賣機(jī)制本質(zhì)上是一個(gè)多智能體系統(tǒng)，即最終的拍賣結(jié)果取決于所有智能體的出價(jià)，且任一智能體的策略的改變會(huì)影響到其他所有智能體的策略。因此若不做任何的協(xié)調(diào)，則所有智能體會(huì)處于一個(gè)無約束狀態(tài)，進(jìn)而降低系統(tǒng)的整體效果。因此我們希望構(gòu)建一個(gè)多智能體框架，通過精心設(shè)計(jì)協(xié)作機(jī)制來引導(dǎo)智能體走向一個(gè)具有較好系統(tǒng)性能的均衡狀態(tài)。然而這面臨以下幾個(gè)挑戰(zhàn)：
智能體間復(fù)雜的競(jìng)爭與合作關(guān)系使得聯(lián)合優(yōu)化個(gè)體效果和系統(tǒng)整體性能變得困難。一方面，在完全競(jìng)爭的環(huán)境下，每個(gè)廣告主的效用可以被極度優(yōu)化，但預(yù)算充足或可接受成本更高的廣告主將會(huì)以更加激進(jìn)的出價(jià)方式以獲得更多的曝光，導(dǎo)致流量的按需分配無法實(shí)現(xiàn)，進(jìn)而導(dǎo)致對(duì)社會(huì)福利的負(fù)面影響。另一方面，在完全協(xié)作的優(yōu)化范式中，盡管能夠讓所有廣告主以最優(yōu)化整體社會(huì)福利為目標(biāo)進(jìn)行出價(jià)，但這可能會(huì)犧牲單個(gè)廣告主的效果，同時(shí)廣告主可能學(xué)得“共謀”出低價(jià)的行為，導(dǎo)致平臺(tái)受損。因此，為了平衡個(gè)體效果和整體社會(huì)福利，一個(gè)可能的方案是構(gòu)建一個(gè)混合合作-競(jìng)爭框架(MCC, mixed cooperative-competitive)，來使平臺(tái)能夠在社會(huì)福利和平臺(tái)收入之間進(jìn)行一個(gè)靈活的取舍。為實(shí)現(xiàn)混合合作-競(jìng)爭，現(xiàn)有方案一般通過手動(dòng)修改獎(jiǎng)賞函數(shù)或改變與環(huán)境有關(guān)的參數(shù)來達(dá)到該目標(biāo)，然而前者在拍賣場(chǎng)景下并沒有一個(gè)確定的獎(jiǎng)賞函數(shù)形式，而后者僅在模擬器中可行。
MCC中的合作關(guān)系可能會(huì)損害平臺(tái)的收入，例如合作的出價(jià)智能體可能會(huì)共謀出低價(jià)。盡管保留價(jià)是一種保證平臺(tái)收入的有效方法，但如何在MCC框架中優(yōu)化保留價(jià)來減少對(duì)社會(huì)福利的影響仍是一個(gè)開放性問題。
MCC框架在工業(yè)界的實(shí)現(xiàn)也是一個(gè)巨大的挑戰(zhàn)。理想情況下每個(gè)廣告主對(duì)應(yīng)一個(gè)智能體，但這個(gè)數(shù)量級(jí)過于巨大，且每個(gè)智能體得到的獎(jiǎng)賞過于稀疏，導(dǎo)致難以學(xué)得一個(gè)較好的出價(jià)策略。
基于以上挑戰(zhàn)，我們提出了合作-競(jìng)爭多智能體自動(dòng)出價(jià)框架(MAAB, Multi-Agent Auto-bidding)，其主要思想如下：
為了平衡出價(jià)智能體間的競(jìng)爭和合作關(guān)系，我們提出了一種基于溫度調(diào)控的獎(jiǎng)勵(lì)分配機(jī)制。即將一次拍賣中的獎(jiǎng)賞根據(jù)softmax函數(shù)產(chǎn)出的權(quán)重分配給各方智能體。此外，softmax函數(shù)中引入的溫度參數(shù)可以有效調(diào)控智能體之間的競(jìng)爭與合作關(guān)系。
為了減少智能體合作共謀出價(jià)導(dǎo)致平臺(tái)收入受損的問題，我們引入了門檻智能體來為每一個(gè)自動(dòng)出價(jià)智能體設(shè)置一個(gè)個(gè)性化的競(jìng)價(jià)門檻。直覺上，門檻智能體的目標(biāo)是通過提高競(jìng)價(jià)門檻來獲取較高的平臺(tái)收入，然而自動(dòng)競(jìng)價(jià)智能體則具有一個(gè)相反的目標(biāo)，即降低出價(jià)門檻使得可以以較低的成本獲取流量。門檻智能體和出價(jià)智能體是通過一種對(duì)抗的方式進(jìn)行聯(lián)合訓(xùn)練，直到彼此策略達(dá)到某種均衡點(diǎn)。
我們提出一種類似平均場(chǎng)的方法來解決來自工業(yè)場(chǎng)景大規(guī)模多智能體系統(tǒng)的挑戰(zhàn)。通過將同目標(biāo)的智能體聚合為一個(gè)平均自動(dòng)出價(jià)智能體，百萬級(jí)別廣告主之間復(fù)雜的交互可以被簡化，使得在大規(guī)模多智能體系統(tǒng)中部署自動(dòng)競(jìng)價(jià)服務(wù)變?yōu)榭赡堋?/p>
??基礎(chǔ)概念
1. 自動(dòng)出價(jià)模型
廣告主訴求和約束多種多樣，預(yù)算約束是最常見的一種約束形式。為了簡化說明，我們以BCB計(jì)劃為例介紹我們的機(jī)制設(shè)計(jì)。
對(duì)BCB計(jì)劃來說，假設(shè)一段時(shí)間內(nèi)(如一天)有T個(gè)參竟機(jī)會(huì)，日預(yù)算為的計(jì)劃i對(duì)機(jī)會(huì)t出價(jià)。如果他出價(jià)最高則競(jìng)得該流量，并按照GSP進(jìn)行扣費(fèi)，消耗記為，并獲得價(jià)值。BCB計(jì)劃目標(biāo)則是在總消耗小于預(yù)算的約束下，最大化其獲得的價(jià)值，即：
其中表示是否競(jìng)得流量。
2. 馬爾科夫過程
一個(gè)部分觀測(cè)的馬爾科夫過程可以表示為
402 Payment Required
。其中s是環(huán)境的真實(shí)狀態(tài)，o是能夠觀測(cè)到的狀態(tài)，觀測(cè)函數(shù)為：。在任一時(shí)刻，任一智能體根據(jù)觀測(cè)做出的動(dòng)作為：。當(dāng)所有智能體動(dòng)作執(zhí)行后，每個(gè)智能體可以得到一個(gè)獎(jiǎng)賞 ，且環(huán)境狀態(tài)變?yōu)閟'，轉(zhuǎn)移函數(shù)記為：。為折扣系數(shù)，每個(gè)智能體需要通過優(yōu)化其策略最大化累計(jì)獎(jiǎng)賞：我們采用馬爾科夫過程建模自動(dòng)出價(jià)中的多智能體系統(tǒng)。每個(gè)自動(dòng)出價(jià)智能體i的動(dòng)作為出價(jià)，其觀測(cè)狀態(tài)由三部分構(gòu)成：，分別為剩余預(yù)算、流量價(jià)值和剩余競(jìng)價(jià)機(jī)會(huì)。出價(jià)受業(yè)務(wù)限制，一般存在上下界。獎(jiǎng)賞為，競(jìng)得后通過二價(jià)算得扣費(fèi)，則下一時(shí)刻的觀測(cè)變量為402 Payment Required
。每個(gè)智能體目標(biāo)為優(yōu)化競(jìng)得流量的價(jià)值總和：3. 獨(dú)立學(xué)習(xí) (IL, Independent Learner)
在多智能體強(qiáng)化學(xué)習(xí)領(lǐng)域，最常用的訓(xùn)練方式是同時(shí)學(xué)習(xí)非中心化的價(jià)值函數(shù)和策略，比如Independent 𝑄 -learning ，每個(gè)agent共享環(huán)境，并同時(shí)分別用DQN或者Q-learning訓(xùn)練獨(dú)立Q函數(shù)。在后面我們將這種agent記為IL。
IL中每個(gè)agent的Q函數(shù)表示為：，其參數(shù)表示為。函數(shù)的訓(xùn)練細(xì)節(jié)DQN一致。replay buffer中的存儲(chǔ)了。loss為：
其中是target network的參數(shù)，是每個(gè)智能體用于訓(xùn)練的獎(jiǎng)賞，有兩種：
環(huán)境獎(jiǎng)賞，即每個(gè)智能體從環(huán)境中獲得的自己的獎(jiǎng)賞。當(dāng)時(shí)，各智能體之間是完全競(jìng)爭的，稱為CM-IL。
總獎(jiǎng)賞，是所有智能體獎(jiǎng)賞之和，也為此次分配結(jié)果的社會(huì)總福利(Social welfare)。當(dāng)時(shí)，各智能體是合作關(guān)系，即為了總社會(huì)福利共同努力，此時(shí)他們?yōu)楹献麝P(guān)系，稱為CO-IL。
我們也定義了合作和競(jìng)爭關(guān)系如下：假設(shè)一次拍賣中有兩個(gè)智能體，這次展現(xiàn)對(duì)兩個(gè)智能體的價(jià)值分別為：、，假設(shè)，當(dāng)他們的出價(jià)滿足時(shí)，這兩個(gè)智能體間的關(guān)系是合作的，否則是競(jìng)爭的。這種定義是基于直覺的，合作的目標(biāo)是為了更大的社會(huì)總福利。
??IL的行為分析
在本節(jié)中，我們分析了CM-IL和CO-IL兩種模式下的自動(dòng)出價(jià)智能體的表現(xiàn)，并發(fā)現(xiàn)CM-IL會(huì)導(dǎo)致寡頭現(xiàn)象的產(chǎn)生并不利于社會(huì)總福利，而CO-IL雖然具有較高的社會(huì)福利，但會(huì)損害平臺(tái)收入。為了直觀闡明以上結(jié)論，我們構(gòu)建了一個(gè)由兩個(gè)自動(dòng)出價(jià)智能體構(gòu)成的環(huán)境，這兩個(gè)自動(dòng)出價(jià)智能體的目標(biāo)都是在固定預(yù)算內(nèi)最大化他們的總價(jià)值。我們分別以CM-IL和CO-IL模式訓(xùn)練50k輪，并從以下三種指標(biāo)觀察其最終效果：
智能體1獲得的總價(jià)值：智能體2獲得的價(jià)值由社會(huì)福利以及智能體1獲取的總價(jià)值反推出來，因此沒有繪出。
社會(huì)福利：社會(huì)福利為所有智能體價(jià)值的總和。
平臺(tái)收入：扣費(fèi)使用GSP機(jī)制。
假設(shè)兩個(gè)智能體預(yù)算總和為，預(yù)算分配比例參數(shù)為，則兩個(gè)智能體的預(yù)算分別為：和，我們嘗試了不同和的參數(shù)組合，在此環(huán)境下得到的實(shí)驗(yàn)結(jié)果如下圖所示：
其中每張圖中的每一個(gè)單元中的數(shù)值代表在不同參數(shù)組合下的實(shí)驗(yàn)結(jié)果。我們首先觀察CM-IL下的智能體1獲取的價(jià)值，如圖(a)所示，當(dāng) ，即智能體1預(yù)算顯著多于2時(shí)，智能體1獲得的總價(jià)值為(39, 38, 41, 36)，其顯著多于智能體2所獲得的價(jià)值(19, 19, 16, 21)。此時(shí)智能體1通過出更高的出價(jià)獲取了大部分展現(xiàn)機(jī)會(huì)，形成了寡頭現(xiàn)象。同時(shí)這種寡頭現(xiàn)象也導(dǎo)致了較低社會(huì)福利，如圖(c)和(d)所示，CM-IL達(dá)到了比CO-IL更低的社會(huì)福利，特別是在具有充足預(yù)算的設(shè)置下（例如當(dāng)時(shí)，CO-IL的社會(huì)福利為（64，64，64），顯著低于CM-IL的社會(huì)福利（57，56，58）。
適當(dāng)?shù)暮献骺梢酝ㄟ^防止寡頭現(xiàn)象的產(chǎn)生從而提高社會(huì)福利。這可以通過比較圖(a)和圖(b)得出：有較多預(yù)算時(shí)（），智能體1的價(jià)值從（39，38，41，36）降低為（35，38，33，33），而具有較少預(yù)算時(shí)（），智能體1的價(jià)值從（20，16，17，22）提高為（20，25，28，30）。這表明CO-IL更多是通過展現(xiàn)價(jià)值而非預(yù)算來進(jìn)行展現(xiàn)機(jī)會(huì)的分配，并且就社會(huì)福利而言，CO-IL的這種方式顯然達(dá)到了一種更好的均衡。
然而CO-IL也會(huì)導(dǎo)致部分廣告主利益受損，尤其當(dāng)存在其他廣告主的value顯著大于它時(shí)。同時(shí)，合作也會(huì)使各智能體“合謀”降低出價(jià)，導(dǎo)致平臺(tái)收入受損（對(duì)比(f)和(d)）。
總的來說，競(jìng)爭和合作狀態(tài)會(huì)導(dǎo)致兩種極端情況：競(jìng)爭會(huì)導(dǎo)致在預(yù)算差異過大時(shí)出現(xiàn)寡頭現(xiàn)象，進(jìn)而損害社會(huì)總福利；合作能達(dá)到更高的社會(huì)總福利，但會(huì)導(dǎo)致平臺(tái)收入和部分廣告主利益受損。
??我們的方法
為了在大規(guī)模多智能體環(huán)境中兼顧社會(huì)總福利和平臺(tái)收入，我們提出了MAAB框架。該框架示意圖如下圖所示：
框架主要包含三部分：
為平衡競(jìng)爭與合作關(guān)系，提出基于溫度調(diào)控的獎(jiǎng)勵(lì)分配機(jī)制（Temperature Regularized Credit Assignment, TRCA）；
為了降低因合作導(dǎo)致的平臺(tái)收入損失，引入門檻智能體；
用于大規(guī)模多智能體系統(tǒng)的平均場(chǎng)方法。
下面我們進(jìn)行詳細(xì)的介紹。
基于溫度調(diào)控的獎(jiǎng)勵(lì)分配機(jī)制TRCA
受上文實(shí)驗(yàn)中IL在競(jìng)爭和合作下分別產(chǎn)生的極端行為啟發(fā)，我們提出了TRCA這種獎(jiǎng)勵(lì)分配機(jī)制，來建立多智能間的一種混合合作競(jìng)爭關(guān)系。
TRCA的主要思路是給每個(gè)智能體的獎(jiǎng)賞賦以一個(gè)權(quán)重參數(shù)。這個(gè)權(quán)重衡量了每個(gè)智能體對(duì)總獎(jiǎng)賞的貢獻(xiàn)，因此各智能體的獎(jiǎng)賞為：。其中我們將定義為
402 Payment Required
。它是一個(gè)softmax式的權(quán)重，滿足和。超參()決定了競(jìng)爭和合作的程度，為了分析是如何影響智能體行為的，我們以一輪拍賣中的兩個(gè)智能體的情況進(jìn)行簡要分析，并給出下面的定理證明在此處省略，有興趣的同學(xué)可以查看原文。：證明在此處省略，感興趣的同學(xué)可以查看原文。
由上可知，當(dāng)大于一定閾值時(shí)，智能體將會(huì)傾向于合作狀態(tài)，反之則處于競(jìng)爭狀態(tài)。因此我們可以使用來很方便的調(diào)節(jié)混合競(jìng)爭合作狀態(tài)中競(jìng)爭和合作的相對(duì)程度，進(jìn)而達(dá)到平臺(tái)收入與社會(huì)福利之間的適當(dāng)取舍。
門檻智能體
在線廣告的一個(gè)目標(biāo)是實(shí)現(xiàn)平臺(tái)和廣告主的雙贏。如上節(jié)仿真實(shí)驗(yàn)可知，盡管合作有助于提升社會(huì)總福利，但各智能體會(huì)傾向于共謀出低價(jià)，導(dǎo)致平臺(tái)收入下降。在本節(jié)中，我們提出了幾種提升平臺(tái)收入的方法。
最簡單的方法是設(shè)置一個(gè)固定的出價(jià)門檻。當(dāng)自動(dòng)出價(jià)智能體出價(jià)時(shí)，使用TRCA獎(jiǎng)賞，反之獎(jiǎng)賞為0：。但固定的門檻很難設(shè)置，過高會(huì)損失廣告主收益，過低則對(duì)提升平臺(tái)收入無益。
一種進(jìn)階方法，是對(duì)每次參竟設(shè)置自適應(yīng)出價(jià)門檻。我們可以新增一個(gè)面向平臺(tái)收入的智能體，并使用RL方法優(yōu)化其設(shè)置出價(jià)門檻的策略。但該智能體的獎(jiǎng)賞很難定義。如果簡單地將其獎(jiǎng)賞定義為平臺(tái)收入，那么這個(gè)智能體會(huì)傾向于設(shè)置一個(gè)過高出價(jià)門檻。另一方面，同一拍賣中的不同自動(dòng)出價(jià)智能體具有差異化的個(gè)體信息，因此共用一個(gè)出價(jià)門檻可能并非一個(gè)好選擇。
基于以上分析，我們?cè)贛AAB中提出使用多門檻智能體，每一個(gè)門檻智能體為對(duì)應(yīng)的自動(dòng)出價(jià)智能體提供一個(gè)出價(jià)門檻。每次拍賣中，門檻智能體和出價(jià)智能體分別給出出價(jià)門檻和出價(jià)。參竟后我們得到客戶收益并計(jì)算得到TRCA獎(jiǎng)賞，同時(shí)門檻智能體獲得平臺(tái)收入，其定義為單次拍賣中的扣費(fèi)。同時(shí)，為了防止門檻智能體出過高的競(jìng)價(jià)門檻，我們提出了一種稱為門檻門控（bar gate）機(jī)制的方法。門檻門控機(jī)制為每對(duì)出價(jià)智能體和門檻智能體輸出：
然后我們采用和分別作為兩個(gè)智能體的獎(jiǎng)賞。注意門檻智能體僅用作訓(xùn)練，在線執(zhí)行階段不發(fā)揮作用。
門檻智能體和出價(jià)智能體采用同時(shí)訓(xùn)練的方式。門檻智能體致力于提升平臺(tái)收入，出價(jià)智能體致力于提升客戶收益。門檻門控機(jī)制將這兩種不同的獎(jiǎng)賞建立了一種關(guān)系。一方面，當(dāng)門檻過高，雙方都獲得0獎(jiǎng)賞，此時(shí)門檻智能體會(huì)降低門檻，出價(jià)智能體則增加出價(jià)，直到兩方達(dá)成一致，即，此時(shí)雙方才能同時(shí)獲得獎(jiǎng)賞。另一方面，當(dāng)門檻過低時(shí)，雙方均會(huì)獲得一定的收益，但下一輪門檻智能體會(huì)嘗試提升出價(jià)，同時(shí)受TRCA中合作關(guān)系鼓勵(lì)出價(jià)智能體會(huì)嘗試降低出價(jià)，直到穩(wěn)態(tài)形成。
總的來說，我們提出的這個(gè)多門檻智能體和對(duì)應(yīng)的獎(jiǎng)賞設(shè)計(jì)，能夠通過將出價(jià)提升至合適水平來提升平臺(tái)收入。值得一提的是，這個(gè)方案看起來和保留價(jià)很相似，但我們提出的門檻智能體僅在訓(xùn)練階段生效，在執(zhí)行階段被移除，因此在線的GSP機(jī)制仍然得到保留。
用于大規(guī)模多智能體系統(tǒng)的平均場(chǎng)方法
在實(shí)踐中，我們面臨上百億的參竟機(jī)會(huì)和數(shù)百萬的參竟計(jì)劃，理想情況下每個(gè)計(jì)劃應(yīng)當(dāng)對(duì)應(yīng)一個(gè)出價(jià)智能體，這些智能體同時(shí)進(jìn)行訓(xùn)練，但這會(huì)導(dǎo)致計(jì)算資源緊張以及獎(jiǎng)賞稀疏等問題。一個(gè)可行方案是把智能體按照更高視角、按照某種劃分標(biāo)準(zhǔn)做聚類。聚類后的智能體會(huì)有更稠密的獎(jiǎng)賞，同時(shí)訓(xùn)練的智能體個(gè)數(shù)也大大減少。我們的方法中提出使用計(jì)劃間最本質(zhì)的不同來做計(jì)劃分組，即計(jì)劃的訴求。當(dāng)然也可以使用其他原則進(jìn)行分組。按照待優(yōu)化目標(biāo)分組后，我們得到，其中每組包含了對(duì)應(yīng)目標(biāo)下的所有計(jì)劃。但是，在對(duì)每組訓(xùn)練可以應(yīng)用于組內(nèi)所有計(jì)劃的出價(jià)策略時(shí)，還面臨以下困難：
Q-learning算法中需要下時(shí)刻狀態(tài)下的最大Q值用于訓(xùn)練，但聚類后的下時(shí)刻狀態(tài)未知
計(jì)劃間通常有不同的預(yù)算約束，每條流量對(duì)應(yīng)的流量價(jià)值也不同，共用策略存在困難
為了解決上述問題，我們的平均場(chǎng)方法如下：
其主要思想是平均策略先基于平均預(yù)算等觀測(cè)變量計(jì)算平均出價(jià)，組內(nèi)各計(jì)劃則在平均價(jià)值的基礎(chǔ)上，考慮自身流量價(jià)值與平均價(jià)值的相對(duì)大小關(guān)系調(diào)整其出價(jià)。在詳細(xì)介紹我們的方案前，我們首先介紹下我們使用的符號(hào)的含義。我們將一段時(shí)間（如15分鐘）看做是一個(gè)時(shí)間戳，每段時(shí)間內(nèi)會(huì)陸續(xù)出現(xiàn)展現(xiàn)機(jī)會(huì)。將時(shí)間戳t內(nèi)的所有參竟機(jī)會(huì)集合記作，為其中一次展現(xiàn)機(jī)會(huì)。代表展現(xiàn)機(jī)會(huì)e對(duì)計(jì)劃的價(jià)值。表示計(jì)劃k是否贏得了展現(xiàn)機(jī)會(huì)e，即它的ecpm排序分=是否最高。上述方案的馬爾科夫過程的具體定義如下：
觀測(cè)狀態(tài)：平均智能體i在時(shí)刻t的觀測(cè)值被定義為：。其中是在時(shí)刻t的剩余預(yù)算，其初始值為。為流量的平均價(jià)值。是剩余出價(jià)機(jī)會(huì)。
動(dòng)作空間：平均智能體的動(dòng)作為平均出價(jià)。計(jì)劃在展現(xiàn)機(jī)會(huì)e上的出價(jià)為，其中。clip(.)用于保證最終出價(jià)不會(huì)出現(xiàn)極端值。
獎(jiǎng)賞函數(shù)：獎(jiǎng)賞也定義在一個(gè)聚合粒度：
402 Payment Required
轉(zhuǎn)移函數(shù)：展現(xiàn)機(jī)會(huì)e上獲勝計(jì)劃的期望扣費(fèi)為，其中j為ecpm排序中下一位廣告的下標(biāo)。因此平均智能體的消耗為：，則下一時(shí)刻觀測(cè)狀態(tài)為，當(dāng)剩余預(yù)算為0是，智能體的出價(jià)只能為0.
在線階段，組內(nèi)計(jì)劃共享一個(gè)出價(jià)策略。如對(duì)于計(jì)劃，出價(jià)策略的輸入為計(jì)劃k自身觀測(cè)狀態(tài)（而非組內(nèi)平均狀態(tài)），策略輸出即為其出價(jià)。
配合以上平均智能體模型，我們的門檻智能體和TRCA獎(jiǎng)賞也需要進(jìn)行一些適配：TRCA中的替換為平均出價(jià)；門檻智能體也采用平均場(chǎng)方法，每個(gè)平均出價(jià)智能體對(duì)應(yīng)一個(gè)門檻智能體。如此我們的方法就可在大規(guī)模廣告系統(tǒng)中進(jìn)行訓(xùn)練了。
? 實(shí)驗(yàn)
離線數(shù)據(jù)集仿真
離線數(shù)據(jù)集
離線數(shù)據(jù)集來自阿里巴巴廣告系統(tǒng)在2020年某天中某6小時(shí)的參竟日志。包含了約70w次展現(xiàn)機(jī)會(huì)，每次參竟約有400個(gè)廣告參竟。日志中包含了廣告主id、時(shí)間、廣告主目標(biāo)、流量價(jià)值預(yù)估值、原始手動(dòng)出價(jià)等信息。日志中的計(jì)劃按照其目標(biāo)大體可以分為三類：優(yōu)化點(diǎn)擊的、優(yōu)化購買的、優(yōu)化收藏加購的，后文我們將這三組計(jì)劃分別記為CLICK, CONV, CART 。
評(píng)估指標(biāo)
我們主要關(guān)注兩個(gè)指標(biāo)：(1) 社會(huì)總福利(Social welfare)；（2）平臺(tái)收入，拍賣機(jī)制使用GSP機(jī)制。
預(yù)算約束
對(duì)于離線實(shí)驗(yàn)，我們首先令所有平均智能體出最高價(jià)，然后計(jì)算按最高進(jìn)行出價(jià)的總扣費(fèi)，記為 。然后計(jì)劃 的預(yù)算設(shè)置為 。
我們考慮兩種設(shè)置：1），，這種設(shè)置下所有自動(dòng)競(jìng)價(jià)智能體的預(yù)算一致（記為setting 1）；2），，這種為預(yù)算不均衡的設(shè)定（記為setting 2）。
對(duì)比方法
（1）MSB(Manually set bids)：人工設(shè)定的出價(jià)，即廣告主的原始出價(jià)。
（2）DQN-S：單智能體版本的IL，每一類需求對(duì)應(yīng)一個(gè)智能體，假設(shè)其他廣告使用原始出價(jià)進(jìn)行訓(xùn)練。
（3）CM-IL
（4）CO-IL
（5）MAAB，即我們的方法。
實(shí)驗(yàn)結(jié)果
離線實(shí)驗(yàn)結(jié)果如下圖：
我們發(fā)現(xiàn)，傳統(tǒng)的手動(dòng)競(jìng)價(jià)(MSB)方式并沒有取得很好的效果，其社會(huì)福利為64.5，平臺(tái)的收入為16.9，且是所有方法中最差的。相比之下，DQN-S在三個(gè)組的價(jià)值(29.3, 35.8, 36.0)，社會(huì)福利(101.0)和平臺(tái)收入(68.3)上均更優(yōu)，這是得益于RL可以較好地控制預(yù)算的使用。
然而，DQN-S的性能仍然受到其他智能體出價(jià)固定這一不切實(shí)際的假設(shè)的限制。采用多智能體學(xué)習(xí)范式可以進(jìn)一步消除這種假設(shè)，例如CM-IL無論從社會(huì)福利(例如,setting 1中104.1 > 101.0)還是平臺(tái)的收入上(例如,setting 1中86.8 > 68.3)均優(yōu)于DQN-S。
然而，這種競(jìng)爭關(guān)系可能并不能幫助實(shí)現(xiàn)更好的社會(huì)福利，這一點(diǎn)可以從CM-IL與CO-IL的比較中看出。CO-IL建模智能體之間的合作關(guān)系，因此其在社會(huì)福利上略優(yōu)于CM-IL(Setting 1中104.3 > 104.1，Setting 2中103.0 > 99.6)，然而，這種提升是以犧牲平臺(tái)收入為代價(jià)的(Setting 1 中 66.9 < 86.8，Setting 2中52.9 < 85.0)。
在這兩個(gè)極端之間，MAAB采用了TRCA并以混合合作競(jìng)爭的方式建立智能體之間的關(guān)系，從而實(shí)現(xiàn)了社會(huì)福利與收入之間更好的均衡。如表所示，MAAB的社會(huì)福利優(yōu)于CM-IL(在Setting 1中為105.3 > 104.1，在Setting 2中103.4 > 99.6)，同時(shí)在收入方面顯著優(yōu)于CO-IL(在Setting 1中為80.6 > 66.9，在Setting 2中為69.0 > 52.9)。
在線實(shí)驗(yàn)
我們也進(jìn)行了線上AB實(shí)驗(yàn)，效果如下表（各指標(biāo)數(shù)值均進(jìn)行了歸一化），能夠看出我們的方法能夠在有限的平臺(tái)收入損失下，有效的提升社會(huì)總福利。
消融實(shí)驗(yàn)
TRCA有效性
為了評(píng)估TRCA在建模合作和競(jìng)爭關(guān)系上的有效性，我們?nèi)コ齅AAB中門檻智能體，并將該方法成為MIX-IL，然后通過調(diào)整MIX-IL中的參數(shù)進(jìn)行離線實(shí)驗(yàn)分析。越大關(guān)系越傾向于合作，越小關(guān)系越傾向于競(jìng)爭。當(dāng)時(shí)，MIX-IL等價(jià)于CM-IL；當(dāng)時(shí)，MIX-IL等價(jià)于CO-IL。
我們使用和進(jìn)行實(shí)驗(yàn)，我們嘗試了= 0, 2, 4, ，結(jié)果如下：
可以看到合作和競(jìng)爭程度可以很方便的通過調(diào)節(jié)來平衡。
門檻智能體的影響
為了驗(yàn)證門檻智能體在提升平臺(tái)收入上的必要性以及自適應(yīng)門檻智能體的效果，我們用這兩種方法和MAAB進(jìn)行了比較：（1）MIX-IL：無門檻智能體；（2）MAAB-fix：使用固定的門檻智能體動(dòng)作：。預(yù)算設(shè)定為：和。離線實(shí)驗(yàn)結(jié)果如下：
對(duì)比MIX-IL和MAAB-fix，可以看到出價(jià)門檻對(duì)平臺(tái)收入的明顯提升，門檻越高提升越大(99.6->114.3->164.9)。但同時(shí)過高的門檻也會(huì)降低社會(huì)福利(104->99.3)，過低的門檻平臺(tái)收入提升有限。采用自適應(yīng)門檻的MAAB則能兼顧兩者，在社會(huì)福利損失有限情況(104->103.9)下大幅度提升平臺(tái)收入。
??總結(jié)
自動(dòng)出價(jià)已經(jīng)成為在線廣告中優(yōu)化廣告主投放效果的基礎(chǔ)工具。我們提出的MAAB是一個(gè)能用于大規(guī)模廣告系統(tǒng)自動(dòng)出價(jià)的多智能體強(qiáng)化學(xué)習(xí)框架，它主要有三個(gè)貢獻(xiàn)：
（1）提出了TRCA，建立了自動(dòng)出價(jià)智能體間的混合競(jìng)爭-合作關(guān)系。
（2）提出了在訓(xùn)練時(shí)使用門檻智能體提升平臺(tái)收入。
（3）使用了平均場(chǎng)方法，將MAAB用于大規(guī)模廣告平臺(tái)。
未來我們將會(huì)持續(xù)探索TRCA中的溫度參數(shù)實(shí)時(shí)動(dòng)態(tài)調(diào)整，和升級(jí)門檻智能體的獎(jiǎng)賞方案設(shè)計(jì)以加快其收斂。
參考文獻(xiàn)
[1] Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. 2019. Autobidding with constraints. In WINE. Springer, 17–30.
[2] Han Cai, Kan Ren, Weinan Zhang, Kleanthis Malialis, Jun Wang, Yong Yu, and Defeng Guo. 2017. Real-time bidding by reinforcement learning in display advertising. In WSDM. 661–670.
[3] Google Ads Help Center. 2021. About automated bidding. https://support.google. com/google-ads/answer/2979071. Accessed: January 24, 2021.
[4] Carl Davidson and Raymond Deneckere. 1986. Long-run competition in capacity, short-run competition in price, and the Cournot model. The Rand Journal of Economics (1986), 404–415.
[5] Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath. 2019. Optimal auctions through deep learning. In ICML. PMLR, 1706–1715.
[6] Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. 2007. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American economic review 97, 1 (2007), 242–259.
[7] eMarketer. 2015. Worldwide retail ecommerce sales: eMarketer’s updated estimates and forecast through 2019. (2015).
[8] Facebook. 2021. Facebook. https://www.facebook.com/business/m/one-sheeters/ facebook-bid-strategy-guide. Accessed: January 24, 2021.
[9] Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. 2018. Counterfactual multi-agent policy gradients. In AAAI, Vol. 32.
[10] Google. 2021. Google AdWords API. https://developers.google.com/adwords/ api/docs/guides/start. Accessed: January 24, 2021.
[11] Ziyu Guan, Hongchang Wu, Qingyu Cao, Hao Liu, Wei Zhao, Sheng Li, Cai Xu, Guang Qiu, Jian Xu, and Bo Zheng. 2021. Multi-Agent Cooperative Bidding Games for Multi-Objective Optimization in e-Commercial Sponsored Search. arXiv preprint arXiv:2106.04075 (2021).
[12] Garrett Hardin. 2009. The tragedy of the commons. Journal of Natural Resources Policy Research 1, 3 (2009), 243–253.
[13] Pablo Hernandez-Leal, Bilal Kartal, and Matthew E Taylor. 2019. A survey and critique of multiagent deep reinforcement learning. AAMAS 33, 6 (2019), 750–797.
[14] Junqi Jin, Chengru Song, Han Li, Kun Gai, Jun Wang, and Weinan Zhang. 2018. Real-time bidding with multi-agent reinforcement learning in display advertising. In CIKM. 2193–2201.
[15] Jean-Michel Lasry and Pierre-Louis Lions. 2007. Mean field games. Japanese journal of mathematics 2, 1 (2007), 229–260.
[16] Joel Z Leibo and Marc Lanctot. 2017. Multi-agent Reinforcement Learning in Sequential Social Dilemmas. (2017). arXiv:arXiv:1702.03037v1
[17] Michael L Littman. 1994. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994. Elsevier, 157–163.
[18] Xiangyu Liu, Chuan Yu, Zhilin Zhang, Zhenzhe Zheng, Yu Rong, Hongtao Lv, Da Huo, Yiqing Wang, Dagui Chen, Jian Xu, Fan Wu, Guihai Chen, and Xiaoqiang Zhu. 2021. Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertising. In SIGKDD. 3354–3364.
[19] Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. 2017. Multi-agent actor-critic for mixed cooperative-competitive environments. In NIPS. 6379–6390.
[20] Robert C Marshall and Leslie M Marx. 2007. Bidder collusion. Journal of Economic Theory 133, 1 (2007), 374–402.
[21] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. 2015. Human-level control through deep reinforcement learning. nature 518, 7540 (2015), 529–533.
[22] Mehryar Mohri and Andres Munoz Medina. 2014. Learning theory and algorithms for revenue optimization in second price auctions with reserve. In ICML. PMLR, 262–270.
[23] Roger B Myerson. 1981. Optimal auction design. Mathematics of operations research 6, 1 (1981), 58–73.
[24] Michael Ostrovsky and Michael Schwarz. 2011. Reserve prices in internet advertising auctions: A field experiment. In EC. 59–60.
[25] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. 2018. QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning. In ICML. 4295–4304.
[26] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinícius Flores Zambaldi, Max Jaderberg, Marc Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. 2018. Value-Decomposition Networks For Cooperative Multi-Agent Learning Based On Team Reward.. In AAMAS. 2085–2087.
[27] Ardi Tampuu, Tambet Matiisen, Dorian Kodelja, Ilya Kuzovkin, Kristjan Korjus, Juhan Aru, Jaan Aru, and Raul Vicente. 2017. Multiagent cooperation and competition with deep reinforcement learning. PloS one 12, 4 (2017), e0172395.
[28] Ming Tan. 1993. Multi-agent reinforcement learning: Independent vs. cooperative agents. In ICML. 330–337.
[29] David RM Thompson and Kevin Leyton-Brown. 2013. Revenue optimization in the generalized second-price auction. In EC. 837–852.
[30] Chao Wen, Xinghu Yao, Yuhui Wang, and Xiaoyang Tan. 2020. SMIX (𝜆): Enhancing Centralized Value Functions for Cooperative Multi-Agent Reinforcement Learning.. In AAAI. 7301–7308.
[31] 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 CIKM. 1443–1451.
[32] Xiao Yang, Daren Sun, Ruiwei Zhu, Tao Deng, Zhi Guo, Zongyao Ding, Shouke Qin, and Yanfeng Zhu. 2019. Aiads: Automated and intelligent advertising system for sponsored search. In SIGKDD. 1881–1890.
[33] Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. 2018. Mean field multi-agent reinforcement learning. In ICML. PMLR, 5571–5580.
[34] Shuai Yuan, Jun Wang, Bowei Chen, Peter Mason, and Sam Seljan. 2014. An empirical study of reserve price optimisation in real-time bidding. In SIGKDD. 1897–1906.
END
也許你還想看
丨阿里媽媽技術(shù)團(tuán)隊(duì)4篇論文入選WSDM 2022
丨WSDM 2022 | 合約廣告自適應(yīng)統(tǒng)一分配框架
丨WSDM 2022 | 基于元學(xué)習(xí)的多場(chǎng)景多任務(wù)商家建模
丨WSDM 2022 | 點(diǎn)擊率模型特征交叉方向的發(fā)展及CAN模型介紹
歡迎關(guān)注「阿里媽媽技術(shù)」，了解更多~
瘋狂暗示↓↓↓↓↓↓↓
總結(jié)
以上是生活随笔為你收集整理的WSDM 2022 | 一种用于在线广告自动竞价的协作竞争多智能体框架的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： WSDM 2022 | 点击率模型特征交
- 下一篇： Deep GSP ： 面向多目标优化的工