1、序言：廣告排序機制的前世今生
1.1、簡介：廣告排序機制
線上廣告是國内外各大網際網路公司的重要收入來源之一，而線上廣告與傳統廣告最大的差別就在于其超大規模的實時競價環境：數以萬計的廣告主在一天内可以參與億級别的流量競拍。在這複雜的實時競價環境中，廣告系統的重排子產品（Rerank）擔負着确定 流量最終分發以及計費方式的重要職責。其中，流量分發會決定最終曝光的廣告物料，而流量計費則會對曝光廣告進行合理的收費，轉化為廣告收入。
不同于自然搜推系統側重使用者體驗的場域定位，廣告流量場考量的是在 使用者體驗限制下的流量變現問題。在這個背景下，傳統重排子產品（Rerank）在電商線上廣告中的業務定位發生了相應的變化，需在原有多業務目标（點選、GMV、時長等）基礎上進一步兼顧平台廣告收入，同時對勝出的廣告進行合理公平的計費。由于其特殊的業務屬性，廣告系統中的重排有時也被稱為 廣告排序機制，其目的旨在促進使用者、商家以及平台三方互利共赢。
結合業務背景和系統功能，我們将 廣告排序機制的目标 定義如下，
廣告排序機制目标：根據系統上遊提供的物料（召回 / 粗排）及 流量價值預估值（精排pctr、出價bid等），綜合考慮 使用者體驗（上下文、多樣性等）、平台收益（點選、收入、GMV等），設計激勵相容（鼓勵廣告主說真話）的拍賣機制（配置設定和計費規則）。
1.2、前世：經濟學視角下的傳統拍賣機制
在排序機制目标中我們提到了 激勵相容（鼓勵廣告主說真話），事實上，激勵相容是經濟學中機制設計的重要原則之一。下面，我們簡要回顧一下傳統拍賣機制的經濟學相關背景，
1.「機制設計」從經濟學的視角來看，廣告流量的配置設定及售賣可以被看作是 機制設計（Mechanism Design）【1】中的一類問題，拍賣機制設計及其相關工作在過去60年中，先後四次獲得諾貝爾經濟學獎。經典拍賣機制如GSP、VCG由于其良好的博弈性質以及易于實作的特點使其在2002年前後開始被網際網路廣告大規模的使用。
2.「廣告主類型」傳統拍賣機制往往假設廣告主是利益最大化（Utility Maximizer）的，即最大化GMV與成本的內插補點，然而，随着智能營銷手段在廣告投放端的普及，越來越多的廣告主通過向平台表達期望成本和目标，借助智能出價的算法能力進行廣告實時投放，廣告主的類型逐漸轉變為價值最大化（Value Maximizer）【2】，即在滿足成本限制的條件下最大化配置設定價值（例如GMV），而非單純追求內插補點的最大化。
3.「激勵相容限制」鼓勵廣告主在平台按照真實意願出價是拍賣機制設計中一項非常重要的經濟學限制，激勵相容的拍賣機制通過鼓勵廣告主說真話，大大簡化了出價政策設計，優化了博弈環境，同時也為平台設計收入最大化的機制提供了更便捷的抓手。
4.「個體理性限制」除了激勵相容的限制以外，一個良好的拍賣機制還需滿足個體理性的限制條件，簡單來說，個體理性的限制條件要求平台對廣告主的最終收費不高于廣告主的出價，保障廣告主的最低收益非負。
1.3、今生：電商場景下的推薦廣告排序機制
随着網際網路廣告的飛速發展，流量增長迅速，使用者規模及行為都更加龐大且豐富，廣告物料也從原來簡單的商品展示，拓展到了包含聚合頁、活動、店鋪、視訊以及直播等多種多樣的物料類型，此外，廣告主的目标和表達方式也從原先的手動出價，轉變為了由平台代理的，帶有預算和成本控制的智能出價。是以，廣告排序機制的設計也遇到了許多新的挑戰。結合京東業務場景，我們總結了以下三個問題與大家分享：
1.「多元物料價值可比」：更為豐富的物料類型（活動、店鋪、直播等内容類廣告）需要更為準确和全面的物料價值預估，使得多元的物料價值可比，進而提升流量分發效率；
2.「模糊使用者興趣捕捉」：相比于搜尋廣告與使用者搜尋query強相關的廣告展示結果，推薦廣告的使用者興趣更難精确捕捉，需在流量配置設定環節兼顧使用者興趣的探索和利用；
3.「資訊流多物品拍賣」：資訊流廣告序列級别的分發和售賣的場景是經濟學中典型的多品拍賣問題，與單品拍賣不同，多品拍賣面臨着指數級增長的機制搜尋空間，複雜的出價政策空間以及更難滿足的激勵相容限制條件等問題，是學術界和行業的公認難題。
為了更好地刻畫上述提到的三個挑戰，我們将排序機制的問題進行了以下數學模組化。 在上文中我們提到，機制要解決的問題是如何基于上遊提供的資訊（物料、價值預估），完成在使用者體驗限制下流量的高效分發以及變現。
流量的高效分發依賴于我們對流量價值的精準衡量以及高效的探索利用機制，将流量品質簡寫為 adq，我們有
其中，pctr 為上遊精排給出的點選率預估值，bid 為廣告主的出價，
為擾動項用以模組化探索力度，映射則決定流量價值的融合排序關系。可以看到，流量的高效分發依賴于對流量單點價值的準确衡量（函數内的重要因子如pctr、bid等），以及流量高效探索利用的分發機制（即
以及映射關系的設計）。
對于流量的變現問題，與單品拍賣設計一樣，需設計适配流量分發機制的計費方式，來保障機制的激勵相容，假設了一次請求曝光四個廣告，廣告收入可以拆解為
其中，pij為第i次請求對第j個廣告的扣費。是以，我們可以将問題進一步拆解為以下三項。
1.「流量價值精準衡量」：在物料形式豐富多樣的環境中，如何将流量分發依賴的重要排序因子（pctr、bid等）預估準确？
2.「流量高效探索利用」：在使用者興趣模糊難捕捉的情況下，如何設計一套高效的利用和探索（映射f以及探索擾動項）分發機制?
3.「流量高效公平變現」：在推薦資訊流廣告多品拍賣場景下，如何設計一個适配的計費方式，在保證機制激勵相容（DSIC）的同時，提升平台收入（rev）？
下面，我們結合京東推薦廣告排序機制演化發展的路線，給出我們對這三個問題的思考和解決方案，也希望抛磚引玉，與大家一起進行探讨。
2、正文：京東推薦廣告排序拍賣機制演化
2.1、價值先行：複雜業務場景下的流量價值準确衡量
随着電商業務的飛速發展，推薦物料展示形式從一屏單品、單一商品形式逐漸拓展到一屏多品、多樣物料形式（包括商品、店鋪、活動頁、聚合頁）的複雜業務場景，如何統一且準确衡量不同物料的價值，是困擾排序機制的一大難題，為此，我們從京東業務場景出發，重新審視排序階段的價值了解，通過對單點價值進行更準确地預估，全局資訊更深入地使用，實作了複雜業務場景下的流量價值準确衡量。
「使用者行為的MDP模組化」京東推薦廣告資訊流場景每次以一個組合形式曝光，如下圖所示，使用者通路京東app，浏覽推薦場景時是一個典型的馬爾科夫過程（MDP），對于某個曝光序列組合，使用者可能發生點選、下翻和退出等動作，針對某一個序列排序價值，我們拆分為目前價值、點選後價值、下拉後價值。很自然地，我們可以将不同的候選曝光序列作為不同的狀态（State），使用者的點選、下翻以及退出等常見操作作為動作（Action），點選率、下翻機率以及退出機率作為轉移機率（transition probability），收集使用者後驗回報作為獎勵（reward）。
由點到線：從單點到全局的價值預估
傳統排序機制通常使用以ctr以及ecpm作為重要排序因子，然而，根據上述MDP模組化，我們可以清楚的看到ctr / ecpm隻反映了當次請求的價值，并沒有準确反映這次請求在内頁 / 剩餘通路帶來的整體價值。事實上，一次請求不僅在曝光的當下産生價值，某個物料在被點選或者序列被下翻後也依然産生價值，這兩個動作分别通過點選機率和下翻機率與目前曝光發生關聯。
是以，針對某個曝光物料，我們定義點選進入内頁後産生的點選和消費為内頁價值，并搭建了一套與精排并行的預估系統；針對曝光序列，将優化的視野從單個請求擴充到會話，最大化考慮在更長時間範圍内的價值，為此，我們定義下翻進入下一頁産生的點選和消費為序列下翻價值，并在精排子產品之後搭建了長期價值預估模型，負責對下翻機率和下頁價值進行預估。
相比于點選率預估的二分類任務，内頁價值和長期價值是連續值，是典型的回歸任務，這種任務受離散點的影響比較大，而且有效樣本更稀疏（有效正樣本為外頁發生點選且内頁有行為樣本），樣本内分布差異大。此外，不同于時長預估任務【3，4】，價值預估任務還存在預估時看不到内頁資訊的 partially observable等問題，這些都是準确預估内頁價值和下頁價值面臨的特有挑戰。針對以上這些問題，我們通過将回歸問題分類化、多場景多任務聯合模組化、先驗資訊輔助、離線蒸餾等方式，顯著提高了模型的價值預估能力，為流量價值的高效分發打下了堅實的基礎。
點線成面：基于異步計算的價值校準
價值預估模型考慮的是單個物料的全局價值，然而資訊流廣告是多坑位曝光形式，單個物料的價值（點選率、内頁價值等）不僅受到目前物料影響，而且還受到周圍其他物料影響（例如，某物料内頁價值特别高，說明内頁具有極大吸引力，使用者進入内頁後再退出外頁的意願顯著降低，那麼周圍其他物料的點選率将受到明顯影響），僅基于單點資訊的前序子產品預估值存在嚴重偏差。
相比于精排階段，重排階段擁有更豐富準确的序列資訊、内外頁資訊和下翻機率等全局資訊。由于重排環節位于系統的出口處，可用的耗時空間有限，無法進行大規模複雜的特征提取和計算，是以，我們采用了異步前置計算的方式，利用前鍊路充足的耗時以及算力空間，提前計算價值校準需要的序列以及候選隊列資訊，同時我們在重排階段引入了價值糾偏子產品，對序列内各物料的點選率、内頁價值等名額同時做校準。對于點選率校準任務，采用曝光未點選做負樣本，曝光點選做正樣本，對于内頁價值校準任務，以點選消費資料為正樣本，點選無消費資料為負樣本，曝光未點選資料作為中間樣本，使用stop-grident阻斷中間樣本對内頁價值預估任務的影響。通過異步計算在耗時限制下引入全局資訊，同時模組化序列點選率和内頁價值資訊互相學習，在價值校準子產品實作離線auc以及rmse名額的雙提升，上線帶來了顯著的收益提升。
2.2、柳暗花明：模糊使用者興趣場景下的的流量高效探索利用
不同于搜尋場景下使用者有明确的意圖表達，推薦場景中無使用者 query ，無法擷取直接興趣，若過于關注相關性而推薦使用者曆史經常通路的類目，則無法滿足使用者的潛在興趣，帶來資訊繭房效應，導緻使用者厭煩，極端情況還會産生投訴和輿情；流量的高效探索利用同樣也存在很多難點。首先，流量的探索利用依賴召回、精排、重排等全鍊路的工作，難以單點優化；探索往往與平台短期目标（點選、收入）呈負相關，如何實作探索與利用的平衡是一個挑戰；不同使用者對探索的偏好是個性化的，探索偏好需做到千人千面，然而使用者對于曝光清單的探索偏好真實回報難以直接擷取，導緻探索的端到端學習目标難以量化。
針對模糊使用者興趣場景下的流量高效探索利用問題，我們從基于使用者興趣的商品預訓練【5，6】，以及系統化探索【7，8，9】兩個方面進行模組化。
磐石之固：基于使用者興趣的商品預訓練
對模糊使用者興趣的精細化模組化，依賴對商品物料了解的建設。電商場景下自有的商品标簽體系如類目、産品詞等，存在不準确、備援、粒度過粗、階層化不足的問題。對此，我們基于大規模的 NLP/CV 多模态預訓練模型，産出更準确的物料類目标簽和商品 embedding，為流量的高效探索利用奠定基礎。基于殘差量化變分編碼的思想，對embedding表征進行殘差量化，保留了item之間的階層化語義關聯，将預訓練語言模型的模式從“text ==> representation”改為“text ==> code ==> representation”的方式，緩解了預訓練embedding過度依賴文本描述資訊的問題，防止item之間的gap被過分誇大。
高山流水：系統化流量探索和利用
流量高效探索利用包括多樣性控制、探索與利用的配置設定機制等，核心是如何在滿足多樣性限制情況下，平衡流量探索和利用效率，提升使用者長期體驗和業務效果。是以，在模糊使用者興趣場景下進行流量的高效探索利用，對于推薦廣告的配置設定提效至關重要，可以輔助使用者開拓興趣邊界，提升使用者體驗和長期留存，有利于業務長期增長。
為此，我們提出了階層化、全鍊路、個性化的流量探索利用方案。通過多元度的密度打散政策高效解決了極端多樣性問題；在召回、候選集階段、序列生成評估階段等上下遊全鍊路引入多樣性和探索子產品；在重排子產品，基于序列生成-評估架構，實作了清單級探索利用方案，其中在序列生成階段，基于端到端生成模型實作了相關性和多樣性多目标協同優化；在序列評估階段，将使用者的長期體驗和探索偏好模組化為可量化的中短期回報，實作對使用者整體價值的端到端模組化。
2.3、百花齊放：多品拍賣場景下的流量高效公平變現
在單品拍賣場景中，經典的Myerson引理告訴我們：一個機制是激勵相容的，當且僅當其配置設定方式同出價是單調非減的，根據Envelop Theorem，其收費公式由配置設定規則唯一确定（至多相差一個常數)。然而，在多品拍賣場景下，由于指數級别的組合搜尋空間，激勵相容的嚴格要求，導緻收入最大化的多品拍賣機制設計十分困難。
是以，自2019年起，學術界興起了一個新的方向：Mechanism Design with Deep Learning，嘗試使用神經網絡來近似激勵相容的收入最大化多品拍賣機制，如RegretNet[10]、RDM[11]等，通過将機制設計問題模組化成為帶激勵相容限制的收入最大化問題，利用神經網絡強大的學習能力，來逼近收入最大化的激勵相容多品拍賣機制。然而，由于計算複雜度等原因，這些工作并不能很好的在業界大規模落地。此後，工業界也逐漸出現了利用海量資料驅動的深度拍賣機制，如阿裡媽媽的DeepGSP【12】，DNA【13】以及美團的NMA【14】等工作。
京東自2021年起開展了深度拍賣機制在推薦廣告場景的實踐和應用，由最初的TopK貪心排序 + GSP的拍賣機制，更新為基于GSP的分坑位模型化拍賣DeepAuction，最終演化為基于強化學習的多品拍賣ListVCG，實作了從行業跟随到行業領先機制的轉變和突破，下面我們分别介紹相關工作和機制的演化過程。
DeepAuction：從TopK貪心排序到分坑位模型化拍賣
在模型化拍賣逐漸成為行業主流之前，TopK貪心排序 + GSP計費的方式是行業通用方案。然而，傳統GSP不适用于多品組合拍賣，多品拍賣計費算法（VCG）由于其計算複雜度以及短期對平台收益的損失，落地困難。是以， 我們首先嘗試通過基于GSP計費的分坑位模型化拍賣實作傳統拍賣機制到模型化拍賣的切換。具體地，我們通過神經網絡在每個坑位對不同廣告物料計算品質分，根據該品質分進行排序以及二價扣費。
不同于傳統基于ecpm的排序方式，模型化打分支援多業務目标的端到端學習。我們引入了基于強化學習Actor-Critic架構來模組化流量長期價值，離線使用政策梯度回傳方式對政策打分參數進行學習更新，線上我們通過permutation invariant的候選集編碼器對候選物料進行模組化，傳入動态拍賣參數預估模型，進而實作分坑位的動态品質分計算。
ListVCG：基于課程強化學習的序列拍賣機制
前面有提到，資訊流廣告是典型的多品拍賣場景，業界通用方案GSP在理論、效率上均不是最優解，VCG多品拍賣機制是我們的理想方案。但是VCG僅僅是一個理論上的解決方案，他的前提是需要高效的找到最佳組合拍賣結果。與此同時，推薦業務複雜，是典型的多目标優化場景，但是标準VCG是追求社會福利最大化的機制，是以在由GSP切換到VCG時，平台收益在短期内會顯著下降，這也是業界公認的VCG機制切換難題。是以如何将VCG與多目标優化進行結合也是我們面臨的主要挑戰。結合京東的實際應用場景，我們提出了ListVCG拍賣機制，來解決上述問題。
首先面臨要解決的是700選4的排列組合問題，序列的搜尋空間上千億，我們将此定義成一個強化學習的問題，借鑒了經典的Actor-Critic架構，Actor輸出機率矩陣，通過采樣的手段去求解排列組合問題，同時我們利用使用者的真實回報去提升Critic的評估水準，挑選出的最優組合會利用政策梯度的方式指引Actor學習。通過這種互相疊代自提升的方式去高效逼近最優組合。
VCG下的多品拍賣同時是一個經濟學問題，需要滿足激勵相容的拍賣理論限制來保證長期的生态健康發展，然而常見的多目标問題的優化思路會使得無法使用vcg計費。是以我們在Listvcg中對于ECPM價值進行了參數化的變形，在保證可計費的同時通過可學習的參數來滿足平台收益、社會福利、使用者體驗以及物料整體價值多目标優化的訴求。
為了更好地對流量長期價值進行模組化，我們自然地引入了強化學習的方式，起初我們嘗試了傳統off-policy的Q-Learning算法如DDQN等，然而，由于後驗回報的獎勵稀疏，模型訓練效果不穩定，是以，我們嘗試引入reward shaping以及curriculum RL的思想，通過加入稠密先驗獎勵緩解資料側的獎勵稀疏，并讓模型在相對簡單的單步決策任務（如序列曝光、點選、單步價值預估等）收斂後，再學習長期決策任務，使得模型效果有了顯著提升，在優化長期競價環境的同時，實作了短期收入和廣告主roi的上升。
3、結語和展望
推薦廣告排序機制通過對流量價值的準确衡量，模糊使用者興趣場景下的流量高效探索利用以及多品拍賣場景下的流量高效公平變現，打造了符合京東推薦廣告場域特點的排序機制，實作了流量的高效分發和變現，助力推薦廣告業務增長。未來，排序機制團隊會持續沿着這三個方向，并在自然結果混合排序、智能出價環境下持續進行排序機制的疊代優化。
最後，我們也歡迎對排序拍賣機制、推薦系統或線上廣告感興趣的小夥伴加入京東推薦廣告組，共同成長，一齊助力京東廣告業務的發展！聯系郵箱：[email protected]。
4、參考文獻
【1】Tim Roughgarden, Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
【2】C.A. Wilkens, R. Cavallo, R. Niazadeh, S. Taggart, Mechanism Design for Value Maximizers, 2018.
【3】Paul Covington, Jay Adams, Emre Sargin, Deep Neural Networks for YouTube Recommendations, RecSys 2016.
【4】Ruohan Zhan et. al., Deconfounding Duration Bias in Watch-time Prediction for Video Recommendation, KDD 2022.
【5】S. Rahjput et. al., Recommender Systems with Generative Retrieval, NeurIPS 2023.
【6】Yupeng Hou et. al, Learning Vector-Quantized Item Representation for Transferable Sequential Recommenders, WWW 2023.
【7】Carbonell J, Goldstein J. The use of MMR, diversity-based reranking for reordering documents and producing summaries，ACM SIGIR, 1998: 335-336.
【8】Chen L, Zhang G, Zhou E. Fast greedy map inference for determinantal point process to improve recommendation diversity, NeurIPS, 2018, 31.
【9】Lin Z, Wang H, Mao J, et al. Feature-aware Diversified Re-ranking with Disentangled Representations for Relevant Recommendation, KDD 2022: 3327-3335.
【10】P. Dutting, F. Zhe et. al., Optimal Auctions through Deep Learning: Advances in Differentiable Economics, ICML 2019.
【11】J. Rahme, S. Jelassi, S. Matthew Weinberg, Auction learning as a two-player game, ICLR 2021.
【12】Xiangyu Liu et. al., Optimizing Multiple Performance Metrics with Deep GSP Auctions for E-commerce Advertising, WSDM 2021.
【13】Zhilin Zhang et. al., Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertising, KDD 2021.
【14】Guogan Liao et. al., NMA: Neural Multi-slot Auctions with Externalities for Online Advertising, 2022.