基于帶懲罰的點概率距離策略優化算法 在展示廣告實時競標中的研究

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

關鍵詞： "展示廣告； 實時競價； 出價策略； 強化學習

中圖分類號： "TP181 """文獻標志碼： A

文章編號： "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 引言

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

a）當互聯網用戶打開某一個網頁時（假設該網頁存在要出售的廣告位），交易立即激活，網頁中的廣告腳本程序向SSP發送展示請求。

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

c）ADX通知各個DSP進行競標。

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

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

f）DSP對包括廣告位及用戶信息在內的所有相關信息進行綜合分析，進而作出出價決策，并把出價提交給ADX。

g）ADX根據所有DSP提交的出價金額，以價高者得的游戲規則確定仲裁結果。

h）ADX將贏標者的廣告素材發送給用戶瀏覽器。

i）用戶在網頁上看到贏標者的廣告。

更多關于RTB的詳細信息請參見文獻［1，3，4］。

值得注意的兩點是：a）為了不影響用戶瀏覽網站內容的體驗，整個交易完成時間通常在100 ms內［2］；b）獲勝者支付的金額通常是第二價格［5］。

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

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

1 相關工作

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

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

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

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

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

2 背景和問題定義

2.1 出價策略的目標

通常，在廣告投放周期內（例如一天），廣告展示機會按時間順序依次到達， 廣告商依次對每個到達的展示機會進行程序化自動出價，如果其出價高于其他廣告商，則意味著其贏得拍賣，獲勝者的廣告將顯示給用戶（如引言所述）并享有展示價值。相應地，其將支付購買該廣告展示的成本，出價策略的目標是在預算限制下最大化贏得展示的總價值（例如點擊次數）。

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

其中： N 代表廣告投放周期內廣告展示機會的總數量；索引 i 表示第 i 個展示機會； χ i 代表是否贏得拍賣的二元指標，即 χ i∈{0，1}，χ i=0 表示競標失敗， χ i=1 則表示贏得拍賣； value i 代表第 i 個展示機會的價值； cost i 表示其他廣告商對第 i 個展示機會的最高出價，同時也代表在第二價格的拍賣規則下，廣告商對贏得廣告展示應付的成本；最后， B 代表廣告商的總預算。在不失一般的情況下，本文將點擊視為價值，即廣告商的目標是最大化點擊總數。

2.2 強化學習投標

本文遵循文獻［6］中的建模方法，將RTB投標過程轉換為對 λ 調節過程，并用強化學習方法來學習以獲得最佳 λ 的調整策略。本文將RTB過程建模為情節式的馬爾可夫決策過程（Markov decision process，MDP），MDP可以由元組 （S，A，P，r） 表示，其中， S和A 分別代表狀態 s 和動作 a 的集合， P：S×A×S→[0，1] 為狀態轉換函數， "P（s，a，s′） 表示在狀態 s 執行動作 a 轉換到狀態 s′ 的概率。 r：S×A→"Euclid Math TwoRAp

為立即獎勵函數， r（s，a） 表示在狀態 s 是下執行動作 a 得到的立即獎勵。通常，每個情節包含有限的 T 個時間步長（ 1，2，…，T） ，在與拍賣環境交互中，競標代理在每個時間步都會依據自己的策略 π ，采取相應的動作 a t～π（s t） ，并將獲得環境的獎勵反饋 r（s t，a t） ，此過程將產生狀態、動作的軌跡： s 1，a 1，…，s T，a T ，整個情節的累積折現獎勵為

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

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

a） S 。狀態 s t 包含七個特征：（a）第 t 時間步；（b）剩余預算 B t ；（c） ROL t ：剩余的 λ 調節機會；（d）預算花費率 BCR t ： BCR t=（B t-1-B t）/B t-1 ；（e）贏得展示的成本 CPM t ；（f） WR t ：競拍中贏得展示次數的占比；（g） clicks t-1 ：上一時間步中贏得展示的總點擊次數。

b） A 。動作 a t是對λ參數的調整比例，a t∈A={-8%，-3%，-1%，0，1%，3%，8%}，λ的調節公式為λ t=λ t-1×（1+a t） 。

c） r。r（s t，a t）是在[t，t+1] 時間段內所有贏得展示的預估點擊率的總和。請注意，在廣告中，點擊是稀疏的，將點擊率而不是點擊視為獎勵能夠避免獎勵的稀疏問題。

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

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

3 方法

在強化學習投標中，需要訓練一個投標代理以使得它在不同狀態下能作出最佳決策。對于代理的訓練，采用POP3D算法［11］，這是策略梯度方法的最新改進，它促進了學習的穩定性，同時具有鼓勵更多探索的機制，這有利于代理在高度動態的RTB拍賣環境中搜索最佳策略。本章將介紹策略梯度方法及其演變過程，進而介紹POP3D算法，最后介紹基于POP3D算法的出價模型的訓練過程。策略梯度方法直接使用逼近器來近似表示和優化策略，以獲得最優策略［20］。在MDP中，給定一個由參數 θ表示的策略π θ（s，a），代理和環境交互中可觀察到狀態—動作軌跡τ（s 1，a 1，s 2，a 2，…，s T，a T） ，其中，軌跡 τ 發生的概率為

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） 為軌跡的初始狀態概率； p（s t+1|s t，a t） 表示從狀態 s t 執行動作 a t 轉移到 s t+1 的概率，兩者均由環境決定，代理的目標是獲得最優的 θ （最優的 θ 表示了最優的策略 π ），以最大化期望累積折扣獎勵。

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

為了獲得最優的 θ ，可以通過對式（7）中的目標函數 J（θ） 執行隨機梯度上升算法來優化 θ ：

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

其中： r（τ） 是 ∑ T t=1 γt-1r（s t，a t） 的標記，其含義是軌跡的累積折扣獎勵。通過計算目標函數 J（θ） 對 θ 求偏導來獲得目標函數梯度：

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

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

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

聯立式（5）和（9），進而得到：

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

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

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

另外，可以通過對累積折扣獎勵函數進行修改以進一步減小方差：

θ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）

然后，目標梯度為

θ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） 分別是狀態動作值函數和優勢函數。在策略 π θ（s，a） 下兩者的計算公式分別為

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）

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

θ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）中樣本數據來源于舊策略 π θ old ，舊策略與新策略的軌跡分布不同，因此，乘上重要采樣比率 π θ（a t|s t）/π θ old（a t|s t） 以修正分布差異，但是，重要性采樣方法會引起方差的變化，導致隨機變量 [π θ（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 差異很大，在采樣不充分的情況下（實踐中采樣數量通常不大）很可能會出現式（16）的梯度估計結果與式（13）的估計結果發生嚴重偏離（例如一正一負），最終導致學習變得糟糕。針對此問題，文獻［11］提出一種改進方法，稱之為帶懲罰的點概率距離策略優化（policy optimization with penalized point probability distance，POP3D），該方法在禁止策略更新過大的同時鼓勵更多的探索，這有利于代理在高度動態的RTB拍賣環境中搜索最佳策略。

首先，由式（16）可得到具有重要性采樣的目標函數：

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

而POP3D建議的替代目標函數為

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）） 表示點概率距離，在離散的動作空間中，代理采取動作 a t時，π θ old（ ·|s t）和π θ（ ·|s t） 之間的點概率距離被定義為

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

對于式（18）的目標函數的直觀解釋是：在最大化原目標（見式（17））的同時對新策略偏離舊策略進行懲罰，其中 β 是懲罰系數。

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

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

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

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

請注意，式（21）中，計算累積回報 G t 時，采用優勢估計值 ""t 來替代原始立即獎勵 r t ，這對加快收斂速度有所幫助。然后從經驗池 M 中進行mini-batch采樣 N 個轉換樣本（同時也獲取相應的 ""t 和 G t ），將該mini-batch中的所有狀態 s t 同時輸入到價值 V φ網絡和π θ 網絡以獲得新的狀態價值 V′ t和π θ（·|s t），然后利用V′ t和G t來計算V φ 網絡的損失函數并對該損失函數執行梯度下降法來更新 φ ，該損失函數的計算公式為

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

與此同時，根據mini-batch中的 a t和π θ網絡輸出的π θ（·|s t）計算出轉換樣本中的動作a t在π θ 網絡下的被采取概率的對數形式log π θ（a t|s t），然后利用 "t 和log π θ（a t|s t） 以及mini-batch中的log "π θ old（a t|s t） 計算 π θ 網絡的損失函數：

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）

另外，在實踐中通常可以通過增加 π θ（a t|s t） 的熵值 H（π θ（a t|s t）） 來進一步增強探索，加入熵值后， π θ 網絡最終的損失函數為

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 是熵系數。請注意，以上兩式中最后取負的意義是，對于 π θ 網絡，本文目標是最大化目標函數（也稱為損失函數），而對原目標函數取反則轉換為對目標函數執行梯度下降。以上通過mini-batch采樣訓練的過程可以重復執行多次（而原始的策略梯度方法只能執行一次）。 最后，當訓練過程完成時，把 π θ 網絡的網絡參數復制給 π θ old 以更新交互策略，此外，必須將當前的經驗池 M 清空，后續將重新收集數據。重復以上觀察和訓練兩個子過程直到訓練結束。基于POP3D的出價算法實現步驟如下：

a）初始化回放經驗池 M、π θ網絡參數θ、π θ old網絡參數θ old以及V φ網絡參數，其中θ=θ old

for "e "from 1 to "E ，進行迭代 //迭代次數

for "episode "from 1 to nbsp;K "http://軌跡長度為 K 個情節

b）按照式（1）用 λ 0 計算出價

for "t "1 from 1 to "T ，進行迭代

c）觀察當前狀態 s t ，并分別通過 V φ網絡和π θ old網絡計算輸出V t和π θ old（·|s t）

d）按照 π θ old（·|s t）分布隨機抽樣一個動作a t，并根據π θ old（·|s t）和a t 計算log "π θ old（a t|s t）

e）執行動作 a t，即將λ t-1調整為λ t，并按照式（1）用λ t計算出價，隨后將獲得獎勵r t 以及觀察到下一個狀態 s t+1 ，然后將轉換存儲轉換 〈s t，a t，s t+1，r t，V t， log "π θ old（a t|s t）〉存儲到經驗池M

f）初始化優勢函數存儲區 D A 和累積回報存儲區 D G

g）分別按式（20）和（21）計算經驗池 M 中所有狀態—動作對的優勢函數 ""t 和所有狀態的累積回報 G t ，并分別存儲于 D A 和 D G

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

h）從經驗池 M 中進行mini-batch采樣得到 N 個轉換 〈s t，a t，s t+1，r t，V t， log π θ old（a t|s t）〉 ，分別從 D A 和 D G 獲取與被采樣到的樣本對應的優勢函數 ""t 和累積回報 G t

i）分別通過 V φ網絡和π θ網絡計算輸出新的狀態價值V′ t和π θ（·|s t） ，然后根據 π θ（·|s t） 和計算log π θ（a t|s t）

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

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

l）清空經驗池 M

m）將 π θ 網絡權值復制給 π θ old，即θ old=θ

4 實驗

4.1 數據集

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

4.2 基準模型

本實驗將本文提出的出價策略與在實踐中應用廣泛的策略和最近提出的幾個基于強化學習策略進行了實驗對比，以驗證本文提出的新策略的有效性。基準策略包括如下：

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

b）Lin［12］。線性出價使用歷史平均CTR作為參考值，如果當前廣告機會的CTR估值大于該參考值則意味著出價應該大于基礎出價 b 0 ，反之，應該小于 b 0 ，其中 b 0 是一個可調整的參數，實驗中在訓練數據中運行具有不同該值的出價函數，然后通過觀察最優的結果以獲得最優的 b 0 。因此，第 i 個展示機會的出價 b i 的計算取決于訓練數據的平均點擊率 "CTR avg 、當前CTR預測值 "pCTR i 和參數 b 0 。

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

和Mcpc相似，Lin策略在在線運行中，出價函數僅與 pCTR i 相關，因此屬于靜態策略。

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

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

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

4.3 評價指標

在本實驗中，按照一般慣例，將在測試集上所獲得的點擊次數作為主要的評價指標，同時還會觀察贏標率。

4.4 預算設置

競價優化類似于背包問題，需要在關鍵資源的約束下最大化目標價值，在RTB中，預算是競價過程的關鍵資源，因此，測試過程中必須對預算進行限制，具體地，測試中分配的預算必須少于測試集中所有記錄的總成本。本文實驗中測試時的預算遵循文獻［14］中的設置，即

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

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

4.5 點擊率預測模型設置

本文出價策略中包含了點擊率的預測功能，采用邏輯回歸模型來預測每條廣告展示機會的點擊率，具體的模型設置，本文遵循文獻［13］。實驗中邏輯回歸模型的預測結果的AUC（area under curve）為98.82%。

4.6 參數設置

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

4.7 實驗結果及分析

4.7.1 性能比較

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

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

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

4.7.2 穩定性比較

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

5 結束語

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

參考文獻：

［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］ 劉夢娟，岳威，仇笠舟，等.實時競價在展示廣告中的應用研究及進展［J］.計算機學報，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］ 劉全，翟建偉，章宗長，等.深度強化學習綜述［J］.計算機學報，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.