基于帶懲罰的點(diǎn)概率距離策略優(yōu)化算法 在展示廣告實(shí)時(shí)競標(biāo)中的研究

摘 要： "實(shí)時(shí)競價(jià)（RTB）是在線展示廣告中被廣泛采用的廣告投放模式，針對(duì)由于RTB拍賣環(huán)境的高度動(dòng)態(tài)性導(dǎo)致最佳出價(jià)策略難以獲得的問題，提出了一種基于強(qiáng)化學(xué)習(xí)（RL）的出價(jià)策略優(yōu)化方法，即采用帶懲罰的點(diǎn)概率距離策略優(yōu)化（POP3D）算法來學(xué)習(xí)最佳出價(jià)策略。在基于POP3D的出價(jià)框架中，廣告投標(biāo)過程被建模為情節(jié)式的馬爾可夫決策過程，每個(gè)情節(jié)被劃分為固定數(shù)量的時(shí)間步，每個(gè)廣告展示的出價(jià)由它的預(yù)估點(diǎn)擊率大小和競標(biāo)因子共同決定。每個(gè)時(shí)間步，競標(biāo)代理都會(huì)根據(jù)上一時(shí)間步的拍賣情況對(duì)競標(biāo)因子進(jìn)行調(diào)整，以使得出價(jià)策略能夠適應(yīng)高度動(dòng)態(tài)的拍賣環(huán)境，競標(biāo)代理的目標(biāo)是學(xué)習(xí)最佳的競標(biāo)因子調(diào)整策略。在iPinYou數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，與DRLB算法相比，所提出價(jià)算法在預(yù)算比例為1/16和1/32時(shí)，在點(diǎn)擊次數(shù)方面均提升了0.2%；當(dāng)預(yù)算比例為1/8、1/16和1/32時(shí)，在贏標(biāo)率方面分別提升了1.8%、1.0%和1.7%；另外，在穩(wěn)定性方面，所提方法也具有優(yōu)勢。表明了該方法的優(yōu)越性。

關(guān)鍵詞： "展示廣告； 實(shí)時(shí)競價(jià)； 出價(jià)策略； 強(qiáng)化學(xué)習(xí)

中圖分類號(hào)： "TP181 """文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： "1001-3695（2022）02-023-0461-07

doi：10.19734/j.issn.1001-3695.2021.07.0264

Research on policy optimization algorithm based on probability distance with

penalized point in real-time bidding of display advertising

Li Wenquan1， Qi Qi1， Li Ni2， Liu Yongna3

（1.College of Computer Science amp; Technology， Hainan University， Haikou 570228， China； 2.College of Mathematics amp; Statistics， Hainan Normal University， Haikou 571158，China； 3.College of Applied Science amp; Technology， Hainan University， Danzhou Hainan 571737， China）

Abstract： "Real-time bidding（RTB） is a widely used advertising mode in online display advertising.In response to the problem that the best bidding strategy is difficult to obtain due to the high dynamics of the RTB auction environment，this paper proposed a method of optimizing bid strategy based on reinforcement learning（RL），which used the policy optimization with pena-lized point probability distance（POP3D） algorithm to learn the best bidding strategy.In the POP3D-based bidding framework，the advertising bidding process was modeled as an episodic Markov decision process.Each epiosode contained a fixed number of time steps，and the bid for each ad display was determined by its estimated click-through rate and bidding factors were jointly determined.At each time step，the bidding agent would adjust the bidding factors according to the auction situation at the previous time step，so that the bidding strategy could adapt to the highly dynamic auction environment.The goal of the bidding agent was to learn the best bidding factor adjustment strategy.The experimental results on the iPinYou data set demonstrate that compared with the DRLB algorithm，the proposed bidding algorithm increases the number of clicks by 0.2% when the budget ratio is 1/16 and 1/32，as well as increased the win rate by 1.8%，1.0% and 1.7% when the budget ratio is were 1/8，1/16 and 1/32.In addition，the proposed method also has advantages in terms of stability.It shows the superiority of this method.

Key words： "display advertising； real-time bidding； bidding strategy； reinforcement learning

0 引言

近年來，實(shí)時(shí)競價(jià)（real time biding，RTB） ［1，2］已成為在線展示廣告最重要的交易模式之一，它提高了廣告投放效率同時(shí)促進(jìn)廣告資源的合理分配。在RTB中，廣告的拍賣以一次的展示機(jī)會(huì)為粒度，對(duì)每一個(gè)展示機(jī)會(huì)進(jìn)行實(shí)時(shí)拍賣。如圖1所示，在實(shí)時(shí)競價(jià)系統(tǒng)中交易參與方一般包括互聯(lián)網(wǎng)用戶、幫助媒體發(fā)布方出售廣告資源的提供方平臺(tái)（supply side platform，SSP）、代理廣告客戶進(jìn)行程序化競拍的需求方平臺(tái)（demand side platform，DSP）、充當(dāng)仲裁角色的廣告交易中心（ad exchange，ADX）以及為DSP提供互聯(lián)網(wǎng)用戶相關(guān)信息的數(shù)據(jù)管理平臺(tái)（data management platform，DMP）。以下對(duì)拍賣過程進(jìn)行簡要的描述：

a）當(dāng)互聯(lián)網(wǎng)用戶打開某一個(gè)網(wǎng)頁時(shí)（假設(shè)該網(wǎng)頁存在要出售的廣告位），交易立即激活，網(wǎng)頁中的廣告腳本程序向SSP發(fā)送展示請求。

b）SSP向ADX提交該廣告展示機(jī)會(huì)的競標(biāo)請求，請求中包含用戶cookie和廣告位信息（例如廣告位的尺寸）。

c）ADX通知各個(gè)DSP進(jìn)行競標(biāo)。

d）DSP接到競標(biāo)通知后，通過對(duì)用戶cookie進(jìn)行解析和咨詢DMP以獲取關(guān)于用戶的信息（例如用戶收入情況、興趣愛好等）。

e）DMP將用戶信息提供給DSP。

f）DSP對(duì)包括廣告位及用戶信息在內(nèi)的所有相關(guān)信息進(jìn)行綜合分析，進(jìn)而作出出價(jià)決策，并把出價(jià)提交給ADX。

g）ADX根據(jù)所有DSP提交的出價(jià)金額，以價(jià)高者得的游戲規(guī)則確定仲裁結(jié)果。

h）ADX將贏標(biāo)者的廣告素材發(fā)送給用戶瀏覽器。

i）用戶在網(wǎng)頁上看到贏標(biāo)者的廣告。

更多關(guān)于RTB的詳細(xì)信息請參見文獻(xiàn)［1，3，4］。

值得注意的兩點(diǎn)是：a）為了不影響用戶瀏覽網(wǎng)站內(nèi)容的體驗(yàn)，整個(gè)交易完成時(shí)間通常在100 ms內(nèi)［2］；b）獲勝者支付的金額通常是第二價(jià)格［5］。

如上所述，在RTB交易系統(tǒng)中，DSP是廣告商參與競拍的代理，它代表廣告商的利益，具體地，當(dāng)廣告商在DSP上設(shè)置好相關(guān)規(guī)則（例如預(yù)算、目標(biāo)定向）之后，在不違背廣告商的設(shè)置規(guī)則下，DSP會(huì)程序化自動(dòng)作出是否競拍某一展示機(jī)會(huì)以及為其出價(jià)多少的決策，這依賴于DSP平臺(tái)內(nèi)部嵌入的出價(jià)策略。大多數(shù)之前的出價(jià)策略被稱為靜態(tài)策略，它們無法在線感知拍賣市場的變化（例如競爭形情的變化），進(jìn)而根據(jù)不同的市場環(huán)境來調(diào)整出價(jià)策略，以使得自身在不同的環(huán)境中都能保持良好地工作。而最近提出基于強(qiáng)化學(xué)習(xí)（reinforcement lear-ning，RL）的動(dòng)態(tài)出價(jià)策略能夠很好地感知拍賣市場環(huán)境的變化并作出相應(yīng)的調(diào)整，它能夠適應(yīng)動(dòng)態(tài)的市場環(huán)境，進(jìn)一步來說，它是以即時(shí)和未來獎(jiǎng)勵(lì)為驅(qū)動(dòng)，隨著拍賣市場的變化而動(dòng)態(tài)調(diào)整為不同廣告展示分配預(yù)算的戰(zhàn)略。

本文的工作基于文獻(xiàn)［6］，其提出了第一個(gè)深度強(qiáng)化學(xué)習(xí)的出價(jià)模型，稱之為DRLB。在DRLB中，廣告投標(biāo)過程被轉(zhuǎn)換為式（1）中 λ 的調(diào)節(jié)，代理的任務(wù)是學(xué)習(xí)對(duì) λ 的最佳控制策略，DRLB采用深度Q網(wǎng)絡(luò)（deep Q-network，DQN）［7］來學(xué)習(xí)最佳的控制策略，DQN是基于值函數(shù)的RL方法。本文嘗試使用基于策略梯度的RL方法來替代它，這樣做的好處是，策略梯度的方法能夠避免因值函數(shù)估計(jì)錯(cuò)誤而導(dǎo)致策略降級(jí)［8］，另外，基于值函數(shù)的方法可能存在收斂性問題，而基于策略梯度的方法從理論上具有更好的收斂性［9，10］。具體地，本文采用帶懲罰的點(diǎn)概率距離策略優(yōu)化（policy optimization with penalized point probability distance，POP3D）［11］來代替DQN學(xué)習(xí)最佳的 λ 控制策略，進(jìn)而提出了一種新穎的出價(jià)算法。在真實(shí)數(shù)據(jù)集上驗(yàn)證其有效性，實(shí)驗(yàn)證明，與幾種典型和具有代表性的基線策略相比，在點(diǎn)擊次數(shù)、贏標(biāo)率方面，性能更好。另外，在穩(wěn)定性方面，與DRLB相比更加穩(wěn)定。

1 相關(guān)工作

出價(jià)策略會(huì)影響甚至決定廣告商的營銷收益，因此，對(duì)出價(jià)策略的研究是RTB領(lǐng)域的重要課題。文獻(xiàn)［12］提出一種線性出價(jià)策略，即出價(jià)與點(diǎn)擊率是線性關(guān)系，該出價(jià)策略在實(shí)踐中被廣泛應(yīng)用。文獻(xiàn)［13］從現(xiàn)實(shí)數(shù)據(jù)分析中發(fā)現(xiàn)最優(yōu)的出價(jià)與點(diǎn)擊或轉(zhuǎn)換率應(yīng)是非線性關(guān)系，然而，以上策略都屬于靜態(tài)策略，它們無法在線感知拍賣市場的變化（例如競爭形情的變化），進(jìn)而根據(jù)不同的市場環(huán)境來調(diào)整出價(jià)策略以使得自身在不同的環(huán)境中都能保持良好地工作。為了解決拍賣RTB市場環(huán)境的動(dòng)態(tài)問題，文獻(xiàn)［14］將競標(biāo)過程公式化為馬爾可夫決策過程，其中，狀態(tài)模型是已知的，因此，它屬于有模型的強(qiáng)化學(xué)習(xí)框架，最后通過動(dòng)態(tài)編程算法來求解這種基于模型的強(qiáng)化學(xué)習(xí)問題。然而，基于模型的強(qiáng)化學(xué)習(xí)方法由于計(jì)算資源的限制無法用于像RTB這類大規(guī)模問題，所以研究者們開始探索基于無模型強(qiáng)化學(xué)習(xí)的解決方法，文獻(xiàn)［6］基于最優(yōu)投標(biāo)理論［15］將投標(biāo)過程轉(zhuǎn)換為對(duì)式（1）中的 λ 的調(diào)節(jié)。

b i= pCTR i λ """（1）

其中： i 表示第 i 個(gè)廣告展示機(jī)會(huì)； b 表示出價(jià)； pCTR 表示預(yù)測的點(diǎn)擊率； λ 表示競價(jià)因子。在文獻(xiàn)［6］中，一天的投標(biāo)過程被視為一個(gè)情節(jié)，每個(gè)情節(jié)具有 T 個(gè)時(shí)間步，通過在每個(gè)時(shí)間步 t∈{1，2，…，T} 根據(jù)當(dāng)前狀態(tài) s t （狀態(tài)由拍賣信息表示，例如當(dāng)前剩余預(yù)算等）采取適當(dāng)?shù)膭?dòng)作 a t 來對(duì) λ 進(jìn)行調(diào)整，進(jìn)而動(dòng)態(tài)地調(diào)整出價(jià)公式以適應(yīng)動(dòng)態(tài)的拍賣環(huán)境。動(dòng)作 a t 是精心設(shè)計(jì)的離散空間 A={-8%，-3%，-1%，0，1%，3%，8%} 的任意元素， λ 的調(diào)節(jié)公式為

λ t=λ t-1×（1+a t） ""（2）

然后利用DQN算法來解決 λ 最優(yōu)問題，如引言中所述，該方法稱之為DRLB。但是，DQN作為典型的基于價(jià)值的強(qiáng)化學(xué)習(xí)方法，可能存在收斂性的問題，而基于策略梯度的方法從理論上具有更好的收斂性［9，10］。文獻(xiàn)［16］提出基于策略梯度的異步優(yōu)勢演員批評(píng)（asynchronous advantage actor-critic，A3C）［17］方法來解決投標(biāo)環(huán)境下的強(qiáng)化學(xué)習(xí)問題，為了捕獲順序信息以及考慮到狀態(tài)空間的稀疏性，將最近時(shí)間間隔的關(guān)鍵績效指標(biāo)（KPI）提取為KPI曲線，然后利用高斯混合模型（GMM）對(duì)KPI曲線進(jìn)行軟聚類，并將結(jié)果作為A3C模型的輸入，從而提出稱之為ClusterA3C的出價(jià)模型。與單代理建模方式不同，文獻(xiàn)［18］將投標(biāo)問題視為多代理強(qiáng)化學(xué)習(xí)問題，然后利用深度確定性策略梯度（deep deterministic policy gradient，DDPG） ［19］的方法來解決，但這通常僅適用于獨(dú)立擁有完整RTB生態(tài)系統(tǒng)的廣告平臺(tái)（例如阿里巴巴旗下的淘寶廣告平臺(tái)）。

2 背景和問題定義

2.1 出價(jià)策略的目標(biāo)

通常，在廣告投放周期內(nèi)（例如一天），廣告展示機(jī)會(huì)按時(shí)間順序依次到達(dá)， 廣告商依次對(duì)每個(gè)到達(dá)的展示機(jī)會(huì)進(jìn)行程序化自動(dòng)出價(jià)，如果其出價(jià)高于其他廣告商，則意味著其贏得拍賣，獲勝者的廣告將顯示給用戶（如引言所述）并享有展示價(jià)值。相應(yīng)地，其將支付購買該廣告展示的成本，出價(jià)策略的目標(biāo)是在預(yù)算限制下最大化贏得展示的總價(jià)值（例如點(diǎn)擊次數(shù)）。

max ∑ N i=1 χ i·value i "s.t. "∑ N i=1 χ i·cost i≤B ""（3）

其中： N 代表廣告投放周期內(nèi)廣告展示機(jī)會(huì)的總數(shù)量；索引 i 表示第 i 個(gè)展示機(jī)會(huì)； χ i 代表是否贏得拍賣的二元指標(biāo)，即 χ i∈{0，1}，χ i=0 表示競標(biāo)失敗， χ i=1 則表示贏得拍賣； value i 代表第 i 個(gè)展示機(jī)會(huì)的價(jià)值； cost i 表示其他廣告商對(duì)第 i 個(gè)展示機(jī)會(huì)的最高出價(jià)，同時(shí)也代表在第二價(jià)格的拍賣規(guī)則下，廣告商對(duì)贏得廣告展示應(yīng)付的成本；最后， B 代表廣告商的總預(yù)算。在不失一般的情況下，本文將點(diǎn)擊視為價(jià)值，即廣告商的目標(biāo)是最大化點(diǎn)擊總數(shù)。

2.2 強(qiáng)化學(xué)習(xí)投標(biāo)

本文遵循文獻(xiàn)［6］中的建模方法，將RTB投標(biāo)過程轉(zhuǎn)換為對(duì) λ 調(diào)節(jié)過程，并用強(qiáng)化學(xué)習(xí)方法來學(xué)習(xí)以獲得最佳 λ 的調(diào)整策略。本文將RTB過程建模為情節(jié)式的馬爾可夫決策過程（Markov decision process，MDP），MDP可以由元組 （S，A，P，r） 表示，其中， S和A 分別代表狀態(tài) s 和動(dòng)作 a 的集合， P：S×A×S→[0，1] 為狀態(tài)轉(zhuǎn)換函數(shù)， "P（s，a，s′） 表示在狀態(tài) s 執(zhí)行動(dòng)作 a 轉(zhuǎn)換到狀態(tài) s′ 的概率。 r：S×A→"Euclid Math TwoRAp

為立即獎(jiǎng)勵(lì)函數(shù)， r（s，a） 表示在狀態(tài) s 是下執(zhí)行動(dòng)作 a 得到的立即獎(jiǎng)勵(lì)。通常，每個(gè)情節(jié)包含有限的 T 個(gè)時(shí)間步長（ 1，2，…，T） ，在與拍賣環(huán)境交互中，競標(biāo)代理在每個(gè)時(shí)間步都會(huì)依據(jù)自己的策略 π ，采取相應(yīng)的動(dòng)作 a t～π（s t） ，并將獲得環(huán)境的獎(jiǎng)勵(lì)反饋 r（s t，a t） ，此過程將產(chǎn)生狀態(tài)、動(dòng)作的軌跡： s 1，a 1，…，s T，a T ，整個(gè)情節(jié)的累積折現(xiàn)獎(jiǎng)勵(lì)為

R=∑ T t=1 γt-1r（s t，a t） ""（4）

其中： γ∈[0，1] 為折扣因子，代理的目標(biāo)是最大化累積獎(jiǎng)勵(lì) R 。接下來本文將進(jìn)一步描述 λ 的調(diào)節(jié)過程，對(duì)于每個(gè)情節(jié)（通常為一天），每個(gè)情節(jié)都有 T 個(gè)時(shí)間步，時(shí)間步 t∈{1，2，…，T} 到 t+1 為一個(gè)時(shí)段，時(shí)段長度為15 min。首先初始化一天的預(yù)算 B 和 λ 0 ，從第一個(gè)時(shí)段開始，對(duì)于該時(shí)段內(nèi)的所有廣告機(jī)會(huì)，代理以 b i=pCTR i/λ 0 （由式（1）得到）進(jìn)行出價(jià)；該時(shí)段結(jié)束后，代理會(huì)觀察到狀態(tài) s 1 ，然后在狀態(tài) s 1 下根據(jù)策略 π 執(zhí)行相應(yīng)的動(dòng)作 a t來調(diào)整當(dāng)前的λ參數(shù)，即將λ 0 調(diào)整為 λ 1，λ 1 將應(yīng)用于下一時(shí)段的出價(jià)公式中，如此循環(huán)下去直到情節(jié)結(jié)束。代理的立即獎(jiǎng)勵(lì) r（s t，a t） 是時(shí)間步 t到t+1 之間贏得展示的點(diǎn)擊率的總和。代理的目標(biāo)是學(xué)習(xí)一個(gè)最優(yōu)的 λ 調(diào)整策略 π 以使得情節(jié)結(jié)束時(shí)累積的折扣獎(jiǎng)勵(lì) R 最大化，MDP中相關(guān)元素的定義如下。

a） S 。狀態(tài) s t 包含七個(gè)特征：（a）第 t 時(shí)間步；（b）剩余預(yù)算 B t ；（c） ROL t ：剩余的 λ 調(diào)節(jié)機(jī)會(huì)；（d）預(yù)算花費(fèi)率 BCR t ： BCR t=（B t-1-B t）/B t-1 ；（e）贏得展示的成本 CPM t ；（f） WR t ：競拍中贏得展示次數(shù)的占比；（g） clicks t-1 ：上一時(shí)間步中贏得展示的總點(diǎn)擊次數(shù)。

b） A 。動(dòng)作 a t是對(duì)λ參數(shù)的調(diào)整比例，a t∈A={-8%，-3%，-1%，0，1%，3%，8%}，λ的調(diào)節(jié)公式為λ t=λ t-1×（1+a t） 。

c） r。r（s t，a t）是在[t，t+1] 時(shí)間段內(nèi)所有贏得展示的預(yù)估點(diǎn)擊率的總和。請注意，在廣告中，點(diǎn)擊是稀疏的，將點(diǎn)擊率而不是點(diǎn)擊視為獎(jiǎng)勵(lì)能夠避免獎(jiǎng)勵(lì)的稀疏問題。

d） γ。折扣因子γ=1 。

e） P 。本文基于無模型的RL，不需要考慮具體的轉(zhuǎn)換模型。

3 方法

在強(qiáng)化學(xué)習(xí)投標(biāo)中，需要訓(xùn)練一個(gè)投標(biāo)代理以使得它在不同狀態(tài)下能作出最佳決策。對(duì)于代理的訓(xùn)練，采用POP3D算法［11］，這是策略梯度方法的最新改進(jìn)，它促進(jìn)了學(xué)習(xí)的穩(wěn)定性，同時(shí)具有鼓勵(lì)更多探索的機(jī)制，這有利于代理在高度動(dòng)態(tài)的RTB拍賣環(huán)境中搜索最佳策略。本章將介紹策略梯度方法及其演變過程，進(jìn)而介紹POP3D算法，最后介紹基于POP3D算法的出價(jià)模型的訓(xùn)練過程。策略梯度方法直接使用逼近器來近似表示和優(yōu)化策略，以獲得最優(yōu)策略［20］。在MDP中，給定一個(gè)由參數(shù) θ表示的策略π θ（s，a），代理和環(huán)境交互中可觀察到狀態(tài)—?jiǎng)幼鬈壽Eτ（s 1，a 1，s 2，a 2，…，s T，a T） ，其中，軌跡 τ 發(fā)生的概率為

p θ（τ）=p θ（s 1，a 1，…，s T，a T）=p（s 1）∏ T t=1 π θ（a t|s t）p（s t+1|s t，a t） "（5）

其中： p（s 1） 為軌跡的初始狀態(tài)概率； p（s t+1|s t，a t） 表示從狀態(tài) s t 執(zhí)行動(dòng)作 a t 轉(zhuǎn)移到 s t+1 的概率，兩者均由環(huán)境決定，代理的目標(biāo)是獲得最優(yōu)的 θ （最優(yōu)的 θ 表示了最優(yōu)的策略 π ），以最大化期望累積折扣獎(jiǎng)勵(lì)。

θ= argmax "θ ""E τ～p θ（τ）[∑ T t=1 γt-1r（s t，a t）] ""（6）

為了獲得最優(yōu)的 θ ，可以通過對(duì)式（7）中的目標(biāo)函數(shù) J（θ） 執(zhí)行隨機(jī)梯度上升算法來優(yōu)化 θ ：

J（θ）=E τ～p θ（τ）[r（τ）]=∑ τ r（τ）p θ（τ） ""（7）

其中： r（τ） 是 ∑ T t=1 γt-1r（s t，a t） 的標(biāo)記，其含義是軌跡的累積折扣獎(jiǎng)勵(lì)。通過計(jì)算目標(biāo)函數(shù) J（θ） 對(duì) θ 求偏導(dǎo)來獲得目標(biāo)函數(shù)梯度：

θJ（θ）=E τ～p θ（τ）[r（τ） ""θ "log "p θ（τ）] ""（8）

現(xiàn)實(shí)中無法搜索整個(gè)軌跡集合來計(jì)算式（8）中的梯度，實(shí)際的做法是通過采樣 N 條軌跡，然后計(jì)算平均梯度以獲得式（8）中梯度的無偏估計(jì)，即：

θJ（θ）≈ 1 N ∑ N n=1 r（τn） ""θ log "p θ（τn） ""（9）

聯(lián)立式（5）和（9），進(jìn)而得到：

θJ（θ）≈ 1 N ∑ N n=1 ∑ T t=1 r（τn） ""θ "log "π θ（an t|sn t） ""（10）

在實(shí)踐中，通常加入一個(gè)與策略無關(guān)的基線 b（s t） 以減小因采樣而引入的方差，通常 b（s t）=V（s t） ，給定一個(gè)策略 π θ（s，a） ， Vπ θ（s t）=E τ～π θ[∑ T t′=t γt′-tr（s t′，a t′）|s t] 表示狀態(tài)價(jià)值函數(shù)，請注意，引入基線后梯度的估計(jì)不會(huì)發(fā)生改變［21］，因此式（10）重寫為

θJ（θ）≈ 1 N ∑ N n=1 ∑ T t=1 """θ log π θ（an t|sn t）·（r（τn）-V（sn t）） ""（11）

另外，可以通過對(duì)累積折扣獎(jiǎng)勵(lì)函數(shù)進(jìn)行修改以進(jìn)一步減小方差：

θJ（θ）≈ 1 N ∑ N n=1 ∑ T t=1 """θ log π θ（an t|sn t）·（∑ T t′=t γt′-tr（sn t′，an t′）-V（sn t）） "（12）

然后，目標(biāo)梯度為

θJ（θ）=E （s t，a t）～π θ[ ""θ log π θ（a t|s t）·（Q（s t，a t）-V（s t））]= E （s t，a t）～π θ[ ""θ log π θ（a t|s t）A（s t，a t）] ""（13）

其中： Q（s t，a t） "和 A（s t，a t） 分別是狀態(tài)動(dòng)作值函數(shù)和優(yōu)勢函數(shù)。在策略 π θ（s，a） 下兩者的計(jì)算公式分別為

Qπ θ（s t，a t）=E （s t，a t）～π θ[∑ T t′=t γt′-tr（s t′，a t′）] ""（14）

Aπ θ（s t，a t）=Qπ θ（s t，a t）-Vπ θ（s t） "nbsp;（15）

另外，為了提高數(shù)據(jù)效率，可以通過引入重要性抽樣技術(shù)獲得基于重要性抽樣的策略梯度：

θJ IS（θ）=E （s t，a t）～π θ old[ π θ（a t|s t） π θ old（a t|s t） · ""θ log π θ（a t|s t）A（s t，a t）] ""（16）

其中： π θ old和π θ 分別表示舊策略（更新前）和新策略（更新后）。式（16）與（13）的不同之處在于，式（16）中樣本數(shù)據(jù)來源于舊策略 π θ old ，舊策略與新策略的軌跡分布不同，因此，乘上重要采樣比率 π θ（a t|s t）/π θ old（a t|s t） 以修正分布差異，但是，重要性采樣方法會(huì)引起方差的變化，導(dǎo)致隨機(jī)變量 [π θ（a t|s t）/π θ old（a t|s t）] ""θ log "π θ（a t|s t）A（s t，a t） 和

θ log "π θ（a t|s t）A（s t，a t）

的方差不同，并且兩者的方差的差異隨著策略 π θ 與 π θ old 的差異變大而變大，而如果策略 π θ與π θ old 差異很大，在采樣不充分的情況下（實(shí)踐中采樣數(shù)量通常不大）很可能會(huì)出現(xiàn)式（16）的梯度估計(jì)結(jié)果與式（13）的估計(jì)結(jié)果發(fā)生嚴(yán)重偏離（例如一正一負(fù)），最終導(dǎo)致學(xué)習(xí)變得糟糕。針對(duì)此問題，文獻(xiàn)［11］提出一種改進(jìn)方法，稱之為帶懲罰的點(diǎn)概率距離策略優(yōu)化（policy optimization with penalized point probability distance，POP3D），該方法在禁止策略更新過大的同時(shí)鼓勵(lì)更多的探索，這有利于代理在高度動(dòng)態(tài)的RTB拍賣環(huán)境中搜索最佳策略。

首先，由式（16）可得到具有重要性采樣的目標(biāo)函數(shù)：

J IS（θ）=E （s t，a t）～π θ old[ π θ（a t|s t） π θ old（a t|s t） A（s t，a t）] ""（17）

而POP3D建議的替代目標(biāo)函數(shù)為

J POP3D（θ）=E （s t，a t）～π θ old[ π θ（a t|s t） π θ old（a t|s t） A（s t，a t）- βDa t pp（π θ old（ ·|s t），π θ（ ·|s t））] ""（18）

其中： Da t pp（π θ old（ ·|s t），π θ（ ·|s t）） 表示點(diǎn)概率距離，在離散的動(dòng)作空間中，代理采取動(dòng)作 a t時(shí)，π θ old（ ·|s t）和π θ（ ·|s t） 之間的點(diǎn)概率距離被定義為

Da t pp（π θ old（ ·|s t），π θ（ ·|s t））=（π θ old（a t|s t）-π θ（a t|s t））2 ""（19）

對(duì)于式（18）的目標(biāo)函數(shù)的直觀解釋是：在最大化原目標(biāo)（見式（17））的同時(shí)對(duì)新策略偏離舊策略進(jìn)行懲罰，其中 β 是懲罰系數(shù)。

接下來對(duì)基于POP3D算法的出價(jià)模型的訓(xùn)練過程進(jìn)行介紹，POP3D包含兩個(gè)策略網(wǎng)絡(luò)和一個(gè)價(jià)值網(wǎng)絡(luò)，三者均由神經(jīng)網(wǎng)絡(luò)近似表示，分別記為 π θ、π θ old、V φ。其中，π θ old 負(fù)責(zé)輸出動(dòng)作選擇策略以和環(huán)境交互，在交互中將得到一系列的轉(zhuǎn)換樣本數(shù)據(jù)（即經(jīng)驗(yàn)樣本），目的是要用這些轉(zhuǎn)換樣本數(shù)據(jù)對(duì) π θ 網(wǎng)絡(luò)進(jìn)行訓(xùn)練，以使得它在未來的測試環(huán)境中能夠作出較優(yōu)的出價(jià)決策。 V φ 網(wǎng)絡(luò)在訓(xùn)練過程中扮演批評(píng)者的角色，即通過輸出每個(gè)狀態(tài)的狀態(tài)價(jià)值來評(píng)估代理在每個(gè)狀態(tài)下所采取的動(dòng)作的好壞。訓(xùn)練過程如圖2所示，訓(xùn)練流程包含觀察過程（左方框）和訓(xùn)練過程（右方框）兩個(gè)子過程，從觀察過程開始，收集到一定的經(jīng)驗(yàn)數(shù)據(jù)后并進(jìn)入訓(xùn)練過程，兩個(gè)過程交替進(jìn)行直到結(jié)束訓(xùn)練。在觀察過程中， π θ old 網(wǎng)絡(luò)負(fù)責(zé)和環(huán)境互動(dòng)，具體的，對(duì)于每個(gè)情節(jié)，從初始 λ 0 開始，根據(jù)式（1）計(jì)算出價(jià)，每一個(gè)時(shí)段 t∈{1，2，…，T}（T 個(gè)時(shí)間步對(duì)應(yīng) T 個(gè)時(shí)段）結(jié)束后，都會(huì)依據(jù)該時(shí)段內(nèi)的競拍情況更新狀態(tài)的各個(gè)特征，隨后將得到時(shí)間步 t 的狀態(tài) s t=（t，B t，ROL t，BCR t，CPM t，WR t，clicks t-1） ，狀態(tài) s t 將被輸入到 π θ old和V φ 網(wǎng)絡(luò)中，其中 π θ old 網(wǎng)絡(luò)輸出被輸入的狀態(tài)下所有可能的動(dòng)作被執(zhí)行的概率分布 π θ old（·|s t） 。隨后會(huì)根據(jù)該概率分布來隨機(jī)采樣一個(gè)動(dòng)作 a t 并執(zhí)行該動(dòng)作，即根據(jù)公式 λ t=λ t-1×（1+a t）調(diào)整把λ t-1 調(diào)整為 λ t ，進(jìn)而將該 λ t 應(yīng)用于式（1）中以更新出價(jià)公式，與此同時(shí)，狀態(tài)價(jià)值網(wǎng)絡(luò) V φ 會(huì)輸出狀態(tài)價(jià)值 V t （后續(xù)用來計(jì)算優(yōu)勢函數(shù)，進(jìn)而對(duì)當(dāng)前采取動(dòng)作進(jìn)行評(píng)估）。然后當(dāng) t+1 時(shí)段內(nèi)的所有廣告拍賣完后，狀態(tài)的相關(guān)特征將被更新，環(huán)境將返回更新后的狀態(tài)（即下一個(gè)狀態(tài)） s t+1 ，同時(shí)反饋一個(gè)獎(jiǎng)勵(lì) r t（即t 時(shí)段內(nèi)贏標(biāo)廣告的點(diǎn)擊率的總和）。另外，根據(jù) π θ old（·|s t） 以及被采取的動(dòng)作 a t 可以得到 a t 被采取前它會(huì)被采取的概率的對(duì)數(shù)形式log "π θ old（a t|s t） ，如此將得到轉(zhuǎn)換 〈s t，a t，s t+1，r t，V t， log "π θ old（a t|s t）〉 ，該轉(zhuǎn)換被依次存儲(chǔ)到經(jīng)驗(yàn)池 M 中，經(jīng)過 K 個(gè)情節(jié)后（由于投標(biāo)過程被建模為情節(jié)式的MDP。因此，每一次迭代在收集經(jīng)驗(yàn)數(shù)據(jù)時(shí)通常會(huì)收集 K 個(gè)完整的情節(jié)軌跡）便進(jìn)入訓(xùn)練過程。首先，根據(jù) T 步截?cái)嘈问降膹V義優(yōu)勢估計(jì)［22］計(jì)算經(jīng)驗(yàn)池 M 中的所有狀態(tài)—?jiǎng)幼鲗?duì) （s t，a t） 的優(yōu)勢：

t=∑ T l=0 （ηγ）lδ t+l δ t+l=r t+l+γV（s t+l+1）-V（s t+l） ""（20）

其中： T 為情節(jié)長度； γ 是折扣因子； V（s t） 是狀態(tài)價(jià)值函數(shù)； r t 是立即獎(jiǎng)勵(lì)； δ t 被稱為TD誤差； η 是控制偏差和方差之間的折中的參數(shù)。同時(shí)根據(jù)式（21）計(jì)算所有狀態(tài) s t 的累積回報(bào) G t ：

G t=∑ T t′=t γt′-t "t′ ""（21）

請注意，式（21）中，計(jì)算累積回報(bào) G t 時(shí)，采用優(yōu)勢估計(jì)值 ""t 來替代原始立即獎(jiǎng)勵(lì) r t ，這對(duì)加快收斂速度有所幫助。然后從經(jīng)驗(yàn)池 M 中進(jìn)行mini-batch采樣 N 個(gè)轉(zhuǎn)換樣本（同時(shí)也獲取相應(yīng)的 ""t 和 G t ），將該mini-batch中的所有狀態(tài) s t 同時(shí)輸入到價(jià)值 V φ網(wǎng)絡(luò)和π θ 網(wǎng)絡(luò)以獲得新的狀態(tài)價(jià)值 V′ t和π θ（·|s t），然后利用V′ t和G t來計(jì)算V φ 網(wǎng)絡(luò)的損失函數(shù)并對(duì)該損失函數(shù)執(zhí)行梯度下降法來更新 φ ，該損失函數(shù)的計(jì)算公式為

loss V φ= 1 N ∑ N i=1 （V′ i-G i）2 ""（22）

與此同時(shí)，根據(jù)mini-batch中的 a t和π θ網(wǎng)絡(luò)輸出的π θ（·|s t）計(jì)算出轉(zhuǎn)換樣本中的動(dòng)作a t在π θ 網(wǎng)絡(luò)下的被采取概率的對(duì)數(shù)形式log π θ（a t|s t），然后利用 "t 和log π θ（a t|s t） 以及mini-batch中的log "π θ old（a t|s t） 計(jì)算 π θ 網(wǎng)絡(luò)的損失函數(shù)：

loss π θ=-[ 1 N ∑ N i=1 （ π θ（a i|s i） π θ old（a i|s i） "（s i，a i）- βDa i pp（π θ old（·|s i），π θ（·|s i）））] ""（23）

另外，在實(shí)踐中通常可以通過增加 π θ（a t|s t） 的熵值 H（π θ（a t|s t）） 來進(jìn)一步增強(qiáng)探索，加入熵值后， π θ 網(wǎng)絡(luò)最終的損失函數(shù)為

loss π θ=-[ 1 N ∑ N i=1 （ π θ（a i|s i） π θ old（a i|s i） ） （s i，a i）-

βDa i pp（π θ old（·|s i），π θ（·|s i））+cH（π θ（a i|s i））] ""（24）

其中： H（π θ（a i|s i））=-π θ（a i|s i） "log "π θ（a i|s i）；c 是熵系數(shù)。請注意，以上兩式中最后取負(fù)的意義是，對(duì)于 π θ 網(wǎng)絡(luò)，本文目標(biāo)是最大化目標(biāo)函數(shù)（也稱為損失函數(shù)），而對(duì)原目標(biāo)函數(shù)取反則轉(zhuǎn)換為對(duì)目標(biāo)函數(shù)執(zhí)行梯度下降。以上通過mini-batch采樣訓(xùn)練的過程可以重復(fù)執(zhí)行多次（而原始的策略梯度方法只能執(zhí)行一次）。 最后，當(dāng)訓(xùn)練過程完成時(shí)，把 π θ 網(wǎng)絡(luò)的網(wǎng)絡(luò)參數(shù)復(fù)制給 π θ old 以更新交互策略，此外，必須將當(dāng)前的經(jīng)驗(yàn)池 M 清空，后續(xù)將重新收集數(shù)據(jù)。重復(fù)以上觀察和訓(xùn)練兩個(gè)子過程直到訓(xùn)練結(jié)束。基于POP3D的出價(jià)算法實(shí)現(xiàn)步驟如下：

a）初始化回放經(jīng)驗(yàn)池 M、π θ網(wǎng)絡(luò)參數(shù)θ、π θ old網(wǎng)絡(luò)參數(shù)θ old以及V φ網(wǎng)絡(luò)參數(shù)，其中θ=θ old

for "e "from 1 to "E ，進(jìn)行迭代 //迭代次數(shù)

for "episode "from 1 to nbsp;K "http://軌跡長度為 K 個(gè)情節(jié)

b）按照式（1）用 λ 0 計(jì)算出價(jià)

for "t "1 from 1 to "T ，進(jìn)行迭代

c）觀察當(dāng)前狀態(tài) s t ，并分別通過 V φ網(wǎng)絡(luò)和π θ old網(wǎng)絡(luò)計(jì)算輸出V t和π θ old（·|s t）

d）按照 π θ old（·|s t）分布隨機(jī)抽樣一個(gè)動(dòng)作a t，并根據(jù)π θ old（·|s t）和a t 計(jì)算log "π θ old（a t|s t）

e）執(zhí)行動(dòng)作 a t，即將λ t-1調(diào)整為λ t，并按照式（1）用λ t計(jì)算出價(jià)，隨后將獲得獎(jiǎng)勵(lì)r t 以及觀察到下一個(gè)狀態(tài) s t+1 ，然后將轉(zhuǎn)換存儲(chǔ)轉(zhuǎn)換 〈s t，a t，s t+1，r t，V t， log "π θ old（a t|s t）〉存儲(chǔ)到經(jīng)驗(yàn)池M

f）初始化優(yōu)勢函數(shù)存儲(chǔ)區(qū) D A 和累積回報(bào)存儲(chǔ)區(qū) D G

g）分別按式（20）和（21）計(jì)算經(jīng)驗(yàn)池 M 中所有狀態(tài)—?jiǎng)幼鲗?duì)的優(yōu)勢函數(shù) ""t 和所有狀態(tài)的累積回報(bào) G t ，并分別存儲(chǔ)于 D A 和 D G

for "j "from 1 to "epochs ，進(jìn)行迭代 //樣本利用 epochs 次

h）從經(jīng)驗(yàn)池 M 中進(jìn)行mini-batch采樣得到 N 個(gè)轉(zhuǎn)換 〈s t，a t，s t+1，r t，V t， log π θ old（a t|s t）〉 ，分別從 D A 和 D G 獲取與被采樣到的樣本對(duì)應(yīng)的優(yōu)勢函數(shù) ""t 和累積回報(bào) G t

i）分別通過 V φ網(wǎng)絡(luò)和π θ網(wǎng)絡(luò)計(jì)算輸出新的狀態(tài)價(jià)值V′ t和π θ（·|s t） ，然后根據(jù) π θ（·|s t） 和計(jì)算log π θ（a t|s t）

j）通過最小化式（22）的損失函數(shù)來更新

k）通過最小化式（24）的損失函數(shù)來更新 θ

l）清空經(jīng)驗(yàn)池 M

m）將 π θ 網(wǎng)絡(luò)權(quán)值復(fù)制給 π θ old，即θ old=θ

4 實(shí)驗(yàn)

4.1 數(shù)據(jù)集

本文實(shí)驗(yàn)中使用的數(shù)據(jù)來自中國知名的DSP公司品友公開發(fā)布的iPinYou數(shù)據(jù)集［3］，該數(shù)據(jù)集包含了9個(gè)不同領(lǐng)域的廣告商在廣告拍賣實(shí)踐中產(chǎn)生的真實(shí)數(shù)據(jù)，總過約1 500萬條廣告拍賣記錄，需要注意的是，不同的廣告商在實(shí)際活動(dòng)中產(chǎn)生的數(shù)據(jù)通常存在很大的差異，因此無法將所有數(shù)據(jù)混合在一起使用。實(shí)踐中將不同廣告商的數(shù)據(jù)分開使用，特定廣告商的數(shù)據(jù)只用來訓(xùn)練該廣告商在廣告活動(dòng)中的模型（例如競價(jià)策略模型）。本文使用ID為1458的廣告商的數(shù)據(jù)集，該數(shù)據(jù)集包含2013年6月6日至6月15日連續(xù)十天的現(xiàn)實(shí)數(shù)據(jù)，前七天為訓(xùn)練集，最后三天為測試集。表1、2分別給出了訓(xùn)練和測試數(shù)據(jù)的相關(guān)統(tǒng)計(jì)，表中關(guān)于花費(fèi)的單位是人民幣分。另外，表中關(guān)于點(diǎn)擊次數(shù)這一項(xiàng)的數(shù)據(jù)和原始數(shù)據(jù)稍微有點(diǎn)不同，對(duì)于同一次廣告展示可能會(huì)產(chǎn)生多個(gè)點(diǎn)擊，原始數(shù)據(jù)直接記錄了多個(gè)點(diǎn)擊結(jié)果，本文遵循文獻(xiàn)［13］的做法，同一次展示無論存在多個(gè)點(diǎn)擊都只被記錄一次。

4.2 基準(zhǔn)模型

本實(shí)驗(yàn)將本文提出的出價(jià)策略與在實(shí)踐中應(yīng)用廣泛的策略和最近提出的幾個(gè)基于強(qiáng)化學(xué)習(xí)策略進(jìn)行了實(shí)驗(yàn)對(duì)比，以驗(yàn)證本文提出的新策略的有效性。基準(zhǔn)策略包括如下：

a）Mcpc。該策略的出價(jià)公式為 b i=CPC×pCTR i。其中，b i是第i個(gè)展示機(jī)會(huì)的出價(jià)，CPC 是單次點(diǎn)擊成本（cost per click，CPC）， pCTR i 表示第 i 個(gè)展會(huì)機(jī)會(huì)的預(yù)測點(diǎn)擊率。實(shí)踐中， CPC 由訓(xùn)練集的總花費(fèi)和總點(diǎn)擊次數(shù)的比值確定，在線運(yùn)行時(shí)該出價(jià)函數(shù)僅與單個(gè)展示的 pCTR i 相關(guān)，它無法根據(jù)不同的市場競爭情形動(dòng)態(tài)地調(diào)整出價(jià)策略以使得整個(gè)投放周期的總體效益最大化，因此它被視為靜態(tài)策略。

b）Lin［12］。線性出價(jià)使用歷史平均CTR作為參考值，如果當(dāng)前廣告機(jī)會(huì)的CTR估值大于該參考值則意味著出價(jià)應(yīng)該大于基礎(chǔ)出價(jià) b 0 ，反之，應(yīng)該小于 b 0 ，其中 b 0 是一個(gè)可調(diào)整的參數(shù)，實(shí)驗(yàn)中在訓(xùn)練數(shù)據(jù)中運(yùn)行具有不同該值的出價(jià)函數(shù)，然后通過觀察最優(yōu)的結(jié)果以獲得最優(yōu)的 b 0 。因此，第 i 個(gè)展示機(jī)會(huì)的出價(jià) b i 的計(jì)算取決于訓(xùn)練數(shù)據(jù)的平均點(diǎn)擊率 "CTR avg 、當(dāng)前CTR預(yù)測值 "pCTR i 和參數(shù) b 0 。

b i=b 0× pCTR i CTR avg """（25）

和Mcpc相似，Lin策略在在線運(yùn)行中，出價(jià)函數(shù)僅與 pCTR i 相關(guān)，因此屬于靜態(tài)策略。

c）RLB［14］。如以上所述，該模型利用基于模型的RL方法來獲得最佳策略。

d）DRLB。該模型是基于深度強(qiáng)化學(xué)習(xí)的競價(jià)模型，它解決了RLB在大規(guī)模問題中因計(jì)算資源受限而無法應(yīng)用的難題，它使用DQN來學(xué)習(xí)最優(yōu)競價(jià)策略。如引言所述，它根據(jù)式（1）計(jì)算出價(jià)，其中， λ 0 根據(jù)給定預(yù)算以及式（1）通過在訓(xùn)練集上運(yùn)行貪婪算法得到。

e）本文方法。即本文提出的競價(jià)模型， λ 0 的設(shè)置與DRLB相同。

4.3 評(píng)價(jià)指標(biāo)

在本實(shí)驗(yàn)中，按照一般慣例，將在測試集上所獲得的點(diǎn)擊次數(shù)作為主要的評(píng)價(jià)指標(biāo)，同時(shí)還會(huì)觀察贏標(biāo)率。

4.4 預(yù)算設(shè)置

競價(jià)優(yōu)化類似于背包問題，需要在關(guān)鍵資源的約束下最大化目標(biāo)價(jià)值，在RTB中，預(yù)算是競價(jià)過程的關(guān)鍵資源，因此，測試過程中必須對(duì)預(yù)算進(jìn)行限制，具體地，測試中分配的預(yù)算必須少于測試集中所有記錄的總成本。本文實(shí)驗(yàn)中測試時(shí)的預(yù)算遵循文獻(xiàn)［14］中的設(shè)置，即

B test=B train× N test N train ×c 0 ""（26）

其中： B train 是訓(xùn)練集中的總成本； N train 代表訓(xùn)練集的記錄總數(shù)； N test 代表測試集的記錄總數(shù)； c 0 則是控制測試預(yù)算的比例因子。在實(shí)驗(yàn)中，為了更充分地評(píng)估不同競價(jià)策略的性能，本文設(shè)置了三種比例因子： c 0=1/8，1/16，1/32 ，并分別在三種不同的預(yù)算下進(jìn)行實(shí)驗(yàn)。

4.5 點(diǎn)擊率預(yù)測模型設(shè)置

本文出價(jià)策略中包含了點(diǎn)擊率的預(yù)測功能，采用邏輯回歸模型來預(yù)測每條廣告展示機(jī)會(huì)的點(diǎn)擊率，具體的模型設(shè)置，本文遵循文獻(xiàn)［13］。實(shí)驗(yàn)中邏輯回歸模型的預(yù)測結(jié)果的AUC（area under curve）為98.82%。

4.6 參數(shù)設(shè)置

和DRLB 模型一樣，所提模型將一天的視為一個(gè)情節(jié)，每個(gè)情節(jié)按時(shí)間順序依次分為96個(gè)時(shí)間步，每個(gè)時(shí)間步為15 min的記錄。在所提模型中，采用完全連接的神經(jīng)網(wǎng)絡(luò)（multi-layer perceptron，MLP）來構(gòu)造策略網(wǎng)絡(luò)和狀態(tài)價(jià)值網(wǎng)絡(luò)，策略和狀態(tài)價(jià)值網(wǎng)絡(luò)都有兩個(gè)具有128和128個(gè)節(jié)點(diǎn)的隱藏層，所有隱藏層節(jié)點(diǎn)都使用tanh作為其激活功能。策略網(wǎng)絡(luò)的最終輸出節(jié)點(diǎn)使用softmax作為其激活函數(shù)來輸出所有可能動(dòng)作被采取的概率。本文使用Adam來學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)的參數(shù)，其學(xué)習(xí)率為0.000 1，訓(xùn)練中，學(xué)習(xí)率隨著迭代次數(shù)的增加而線性減小至訓(xùn)練結(jié)束時(shí)為0。算法實(shí)現(xiàn)步驟中的參數(shù) K 設(shè)置為1，參數(shù) epochs 設(shè)置為3，即表示每收集一個(gè)情節(jié)的轉(zhuǎn)換樣本后便對(duì)該批樣本進(jìn)行3次的mini-batch抽樣并訓(xùn)練，其中，mini-batch大小設(shè)置為32，另外，熵系數(shù) c 設(shè)置為0.01，懲罰系數(shù) β 設(shè)置為5.0， η和γ 分別設(shè)置為0.96和1.0。在實(shí)驗(yàn)中，狀態(tài)特征作為策略和狀態(tài)價(jià)值網(wǎng)絡(luò)的輸入，在輸入之前做了標(biāo)準(zhǔn)化處理，請注意，在強(qiáng)化學(xué)習(xí)中，狀態(tài)是在交互過程中產(chǎn)生的，在訓(xùn)練之前無法預(yù)知其平均值和方差，實(shí)際采用運(yùn)行時(shí)的均值和方差作為近似代替。

4.7 實(shí)驗(yàn)結(jié)果及分析

4.7.1 性能比較

表3～5分別展示了各個(gè)出價(jià)策略的屬性特點(diǎn)以及出價(jià)策略在1/8、1/16、1/32的預(yù)算下在測試中獲得的點(diǎn)擊次數(shù)。圖3展示了各個(gè)出價(jià)策略在不同預(yù)算比例下的點(diǎn)擊次數(shù)柱狀分布圖。

從表中可以看出Mcpc和Lin策略屬于靜態(tài)策略，基于強(qiáng)化學(xué)習(xí)的RLB 和DRLB以及本文策略屬于動(dòng)態(tài)策略。如上所述，靜態(tài)策略的特點(diǎn)是，它在出價(jià)時(shí)僅考慮了每個(gè)展示點(diǎn)擊率的估算大小而不考慮出價(jià)對(duì)未來或整個(gè)投放期的影響［9］。與靜態(tài)策略不同，動(dòng)態(tài)策略在制定策略時(shí)能夠考慮未來及總體的效益，直覺上，動(dòng)態(tài)策略具有先進(jìn)性，從表3～5中可以驗(yàn)證這一點(diǎn)，無論在何種預(yù)算的情況下，屬于靜態(tài)策略的Mcpc和Lin在點(diǎn)擊量上都少于基于強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)策略。與此同時(shí)，本文方法在三種預(yù)算場景下獲得的點(diǎn)擊次數(shù)都是最高的。從表5中可以看出，預(yù)算為1/32時(shí)，Mcpc性能最差，此時(shí)，同樣是靜態(tài)策略的Lin點(diǎn)擊量比Mcpc高很多，主要原因是Mcpc無論在任何預(yù)算下，它始終以最初的最高eCPC為基礎(chǔ)來計(jì)算出價(jià)，這種過激的出價(jià)行為將使得它在預(yù)算極其有限時(shí)由于預(yù)算過早消耗殆盡而無法捕獲后續(xù)潛在的高質(zhì)量展示機(jī)會(huì)，從而導(dǎo)致其表現(xiàn)不佳，而Lin相對(duì)而言預(yù)算消耗速度較為平緩，這使得它能參與競拍更多的展示機(jī)會(huì)，進(jìn)而有機(jī)會(huì)捕獲更多能帶來點(diǎn)擊的印象。從圖3中可以看出，預(yù)算從1/8下降到1/16時(shí)，所有競價(jià)策略點(diǎn)擊次數(shù)下降的幅度都很小，下降幅度均不超過1.4%。然而，預(yù)算從1/16下降到1/32時(shí)，屬于靜態(tài)策略的Mcpc和Lin點(diǎn)擊次數(shù)下降的幅度分別為6.3%和2.3%，而基于強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)策略下降幅度均不超過1%。因此，可以看出兩種靜態(tài)策略在預(yù)算較低時(shí)，適應(yīng)性較差，而基于強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)策略能夠很好地適應(yīng)。從表3～5中可以看出，RLB的性能始終比DRLB和本文方法差，主要原因是RLB出價(jià)模型依賴于對(duì)歷史數(shù)據(jù)的市場價(jià)格分布的擬合模型，當(dāng)市場環(huán)境發(fā)生改變時(shí)實(shí)際的市場價(jià)格分布和擬合的市場價(jià)格分布容易發(fā)生偏離，容易導(dǎo)致模型的精度下降，從而影響出價(jià)模型的性能。而本文方法和DRLB可以根據(jù)實(shí)際中不同時(shí)段的拍賣信息來實(shí)現(xiàn)較為精確的 λ 調(diào)整。從表3～5中可以看出，本文方法在三個(gè)預(yù)算場景下勝率約為67%（贏得兩個(gè)場景的勝利），平率約為33%，驗(yàn)證了所提方法的有效性。

圖4展示了不同預(yù)算比例下各個(gè)出價(jià)策略的贏標(biāo)率，從圖4中可以看出，不同的預(yù)算比例下Mcpc的贏標(biāo)率沒有明顯的差異，如上所述，主要原因是Mcpc出價(jià)時(shí)不考慮預(yù)算的變化。結(jié)合表5和圖4來看，預(yù)算比例為1/32時(shí)，Mcpc和Lin的贏標(biāo)率都比RLB高，但是點(diǎn)擊次數(shù)卻都比RLB少很多，這說明了RLB比Mcpc和Lin更能捕獲高價(jià)值的展示（例如能帶來點(diǎn)擊的展示）。從圖中可以看出，本文方法在不同的預(yù)算比例下贏標(biāo)率都是最高的，意味著本文方法能夠獲得更多的展示機(jī)會(huì)，這對(duì)廣告商來說是有利的，因?yàn)檫@能夠增加其商品的曝光量，進(jìn)而吸引更多的用戶來購買其商品，這也是本文方法能夠得到更多點(diǎn)擊量的原因之一。請注意，正如前文所述，預(yù)算比例為1/32時(shí)，Mcpc和Lin的贏標(biāo)率都高于RLB，但點(diǎn)擊次數(shù)卻都少于RLB，因此，更高的贏標(biāo)率并不意味著一定能獲得更多的點(diǎn)擊，有可能獲勝的展示中大多是不能帶來點(diǎn)擊的低價(jià)值展示，而本文方法不僅贏標(biāo)率高，而且點(diǎn)擊次數(shù)也是最高的，這說明了本文方法不僅能帶來更多的展示機(jī)會(huì)，同時(shí)也能夠捕獲高價(jià)值的展示。

4.7.2 穩(wěn)定性比較

DRLB和本文方法都是基于無模型RL的出價(jià)模型，除了點(diǎn)擊次數(shù)和贏標(biāo)率方面，穩(wěn)定性也是值得關(guān)注的評(píng)價(jià)指標(biāo)，本節(jié)對(duì)兩者的穩(wěn)定性進(jìn)行了比較。在兩個(gè)模型的訓(xùn)練過程中，每10個(gè)episode存儲(chǔ)一次模型，并在測試集上運(yùn)行來獲得兩者各自的平均獎(jiǎng)勵(lì)曲線。如圖5所示，縱軸 R/R* 表示當(dāng)前策略下獲得的總獎(jiǎng)勵(lì) R 和貪婪算法得到的理論最優(yōu)總獎(jiǎng)勵(lì) R* 的比值，該比值體現(xiàn)了當(dāng)前策略的優(yōu)劣程度， R* 是在拍賣結(jié)束后，根據(jù)式（1）并運(yùn)行貪婪算法得到。從圖5中可以看出，雖然DRLB收斂速度較快，但穩(wěn)定性較差，表現(xiàn)在方差較大，相反，雖然本文方法收斂速度相對(duì)較慢，但穩(wěn)定性更好。曲線更接近1.0，而且方差很小。

5 結(jié)束語

本文將RTB中的廣告投標(biāo)問題制定為RL問題，競標(biāo)代理通過學(xué)習(xí)最佳的競標(biāo)因子調(diào)整策略以獲得能夠適應(yīng)動(dòng)態(tài)的拍賣環(huán)境的最佳出價(jià)策略，利用POP3D算法來學(xué)習(xí)最佳的競標(biāo)因子調(diào)整策略，從而提出了一種新穎的出價(jià)算法。在基于POP3D的出價(jià)框架中，每個(gè)周期（一天）的投標(biāo)過程被視為一個(gè)情節(jié)，每個(gè)情節(jié)具有固定數(shù)量的時(shí)間步，狀態(tài)由前一個(gè)時(shí)間步的拍賣結(jié)果的數(shù)據(jù)統(tǒng)計(jì)信息決定，動(dòng)作是對(duì)競標(biāo)因子的調(diào)節(jié)比例，獎(jiǎng)勵(lì)是相連的兩個(gè)時(shí)間步之間（即一個(gè)時(shí)段）競標(biāo)中贏得展示的點(diǎn)擊率的總和，競標(biāo)代理的任務(wù)是學(xué)習(xí)競標(biāo)因子的最佳調(diào)節(jié)策略以最大化整個(gè)廣告投放周期獲得的總點(diǎn)擊率。本文將基于POP3D的出價(jià)模型和幾種具有代表性的方法進(jìn)行實(shí)驗(yàn)對(duì)比，這些對(duì)比方法包含了兩種靜態(tài)策略以及三種基于強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)策略。實(shí)驗(yàn)結(jié)果表明，靜態(tài)策略在不同的預(yù)算場景下獲得的點(diǎn)擊次數(shù)都低于基于強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)策略，尤其是當(dāng)預(yù)算較低時(shí)（ c 0=1/32 ）。在三種基于強(qiáng)化學(xué)習(xí)的策略中，基于模型的RLB在三種預(yù)算場景下點(diǎn)擊次數(shù)和贏標(biāo)率兩種指標(biāo)都低于DRLB及本文方法。在三種預(yù)算場景下，本文方法在點(diǎn)擊次數(shù)和贏標(biāo)率兩種指標(biāo)上都是表現(xiàn)最好的。另外，在穩(wěn)定性方面，本文方法與DRLB相比，更加穩(wěn)定。在未來的工作中，本文將致力于進(jìn)一步提升本文出價(jià)策略的性能，并且計(jì)劃對(duì)獎(jiǎng)勵(lì)函數(shù)進(jìn)行重新設(shè)計(jì)。比如，將廣告展示成本納入到獎(jiǎng)勵(lì)函數(shù)的設(shè)計(jì)中，而不是只考慮點(diǎn)擊率估值。因?yàn)橹庇X上，對(duì)于某一個(gè)展示機(jī)會(huì)，即使它的點(diǎn)擊率估值很高，但有可能購買它的成本也較高，這會(huì)降低購買它的價(jià)值，所以代理在拍賣中因贏得該廣告展示機(jī)會(huì)而得到的獎(jiǎng)勵(lì)值應(yīng)該小于點(diǎn)擊率估算值。

參考文獻(xiàn)：

［1］ "Wang Jun，Yuan Shuai.Real-time bidding：a new frontier of computational advertising research［C］//Proc of the 8th ACM International Conference on WSDM.New York：ACM Press，2015：415-416.

［2］ Yuan Shuai，Wang Jun，Zhao Xiaoxue.Real-time bidding for online advertising：measurement and analysis［C］//Proc of the 7th International Workshop on Data Mining for Online Advertising.New York：ACM Press，2013：3.

［3］ Liao Hairen，Peng Lingxiao，Liu Zhenchuan， et al. iPinYou global RTB bidding algorithm competition dataset［C］//Proc of the 8th International Workshop on Data Mining for Online Advertising.New York：ACM Press，2014：1-6.

［4］ 劉夢娟，岳威，仇笠舟，等.實(shí)時(shí)競價(jià)在展示廣告中的應(yīng)用研究及進(jìn)展［J］.計(jì)算機(jī)學(xué)報(bào)，2020， 43 （10）：1810-1841. （Liu Mengjuan，Yue Wei，Qiu Lizhou， et al. Application research and progress of real-time bidding in display advertising［J］. Chinese Journal of Computers ，2020， 43 （10）：1810-1841.）

［5］ Edelman B，Ostrovsky M，Schwarz M.Internet advertising and the generalized second-price auction：selling billions of dollars worth of keywords［J］. National Bureau of Economic Research ，2007， 97 （1）：242-259.

［6］ Wu Di，Chen Xiujun，Yang Xun， et al. "Budget constrained bidding by model-free reinforcement learning in display advertising［C］//Proc of the 27th ACM International Conference on Information and Knowledge Management.New York：ACM Press，2018：1443-1451.

［7］ "Mnih V，Kavukcuoglu K，Silver D， et al. Human-level control through deep reinforcement learning［J］. Nature ，2015， 518 （7540）：529-533.

［8］ Wang Haonan，Liu Ning，Zhang Yiyun， et al. "Deep reinforcement learning：a survey［J］. Frontiers of Information Technology amp; Electronic Engineering ，2020， 21 （12）：1-19.

［9］ Liu Mengjuan，Li Jiaxing，Hu Zhengning， et al. A dynamic bidding strategy based on model-free reinforcement learning in display advertising［J］. IEEE Access ，2020， 8 ：213587-213601.

［10］ Sutton R S，Mcallester D，Singh S， et al. Policy gradient methods for reinforcement learning with function approximation［C］//Proc of the 12th International Conference on Neural Information Processing Systems.Massachusetts：MIT Press，1999：1057-1063.

［11］ Chu Xiangxiang.Policy optimization with penalized point probability distance：an alternative to proximal policy optimization［EB/OL］.（2019）［2021-03-01］.https：//arxiv.org/pdf/1807.00442v4.pdf.

［12］ Perlich C，Dalessandro B，Hook R， et al. Bid optimizing and inventory scoring in targeted online advertising［C］//Proc of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2012：804-812.

［13］ Zhang Weinan，Yuan Shuai，Wang Jun.Optimal real-time bidding for display advertising［C］//Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2014：1077-1086.

［14］ Cai Han，Ren Kan，Zhang Weinan， et al. Real-time bidding by reinforcement learning in display advertising［C］//Proc of the 10th ACM International Conference on Web Search and Data Mining.New York：ACM Press，2017：661-670.

［15］ Zhang Weinan，Ren Kan，Wang Jun.Optimal real-time bidding frameworks discussion［EB/OL］.（2016）［2021-03-01］.https：//arxiv.org/pdf/1602.01007.pdf.

［16］ Lu Junwei，Yang Chaoqi，Gao Xiaofeng， et al. "Reinforcement learning with sequential information clustering in real-time bidding［C］//Proc of the 28th ACM International Conference on Information and Know-ledge Management.New York：ACM Press，2019：1633-1641.

［17］ Mnih V，Badia A P，Mirza M， et al. "Asynchronous methods for deep reinforcement learning［C］//Proc of International Conference on Machine Learning.New York：ACM Press，2016：1928-1937.

［18］ Jin Junqi，Song Chengru，Li Han， et al. Real-time bidding with multi-agent reinforcement learning in display advertising［C］//Proc of the 27th ACM International Conference on Information and Knowledge Management.New York：ACM Press，2018：2193-2201.

［19］ Lillicrap T P，Hunt J J，Pritzel A， et al. Continuous control with deep reinforcement learning［EB/OL］.（2015）［2021-03-01］.https：//arxiv.org/pdf/1509.02971v6.pdf.

［20］ 劉全，翟建偉，章宗長，等.深度強(qiáng)化學(xué)習(xí)綜述［J］.計(jì)算機(jī)學(xué)報(bào)，2018， 41 （1）：1-27. （Liu Quan，Zhai Jianwei，Zhang Zongchang， et al. "A review of deep reinforcement learning［J］. Chinese Journal of Computers ，2018， 41 （1）：1-27.）

［21］ Ronald J W.Simple statistical gradient-following algorithms for connectionist reinforcement learning［J］. Machine Learning ，1992， 8 （3-4）：229-256.

［22］ Schulman J，Moritz P，Levine S， et al. High-dimensional continuous control using generalized advantage estimation［EB/OL］.（2015）［2021-03-01］.https：//arxiv.org/pdf/1506.02438.pdf.