阿里巴巴WWW 2018錄用論文：主搜索與店鋪內搜索聯合優化的初步探索與嘗試

論文標題：Learning to Collaborate: Multi-Scenario Ranking via Multi-Agent Reinforcement Learning（Learning to Collaborate——主搜索與店鋪內搜索聯合優化的初步探索與嘗試）

作者：馮珺, 李恒, 黃民烈, 劉士琛, 歐文武, 王志榮，朱小燕

背景與簡介：Does your optimization really optimize your application?

在淘寶平臺上有非常多的子場景，例如搜索、推薦、廣告。每個子場景又有非常多細分，例如搜索包括默認排序、店鋪內搜索、店鋪搜索等；推薦內有猜你喜歡、今日推薦、每日好店等。基于數據驅動的機器學習和優化技術目前大量的應用于這些場景中，并已經取得了不錯的效果——在單場景內的A/B測試上，點擊率、轉化率、成交額、單價都能看到顯著提升。 然而，目前各個場景之間是完全獨立優化的，這樣會帶來幾點比較嚴重的問題：

a. 用戶在淘寶上購物會經常在多個場景之間切換，例如：從主搜索到猜你喜歡，從猜你喜歡到店鋪內。不同場景的商品排序僅考慮自身，會導致 用戶的購物體驗是不連貫或者雷同的 。例如：從冰箱的詳情頁進入店鋪，卻展示手機；各個場景都展現趨同，都包含太多的U2I（點擊或成交過的商品）。

b. 多場景之間是博弈（競爭）關系， 期望每個場景的提升帶來整體提升這一點是無法保證的 。很有可能一個場景的提升會導致其他場景的下降，更可怕的是某個場景帶來的提升甚至小于其他場景更大的下降。這并非是不可能的，那么這種情況下，單場景的A/B測試就顯得沒那么有意義，單場景的優化也會存在明顯的問題。因為這一點尤為重要，因此我們舉一個更簡單易懂的例子（如下圖）。一個1000米長的沙灘上有2個飲料攤A和B，沙灘上均分分布者很多游客，他們一般會找更近的飲料攤去買飲料。最開始A和B分別在沙灘250米和750米的位置，此時沙灘左邊的人會去A買，右邊的人去B買。然后A發現，自己往右邊移動的時候，會有更多的用戶（A/B測試的結論），因此A會右移，同樣B會左移。A和B各自‘優化’下去，最后會都在沙灘中間的位置，從博弈論的角度，到了一個均衡點。然而，最后‘優化’得到的位置是不如初始位置的，因為會有很多游客會因為太遠而放棄買飲料。這種情況下，2個飲料攤各自優化的結果反而是不如不優化的。

多場景問題實際并不止存在于淘寶上，目前比較大型的平臺或者無線APP都不止一個場景。即使不談Yahoo，Sina等綜合性網站，像Baidu、Google等功能比較單一、集中的應用，也會有若干場景（如網頁、咨詢、地圖等）。那么這些平臺或應用都會面臨類似的問題。 綜上，研究大型在線平臺上的多子場景聯合優化，無論從淘寶平臺的應用上，還是從科研的角度，都具有重要意義。

為了解決上述的問題，本文提出一個多場景聯合排序算法，旨在提升整體指標。我們將多場景的排序問題看成一個完全合作的、部分可觀測的多智能體序列決策問題，利用Multi-Agent Reinforcement Learning的方法來嘗試著對問題進行建模。該模型以各個場景為Agent，讓各個場景不同的排序策略共享同一個目標，同時在一個場景的排序結果會考慮該用戶在其他場景的行為和反饋。這樣使得各個場景的排序策略由獨立轉變為合作與共贏。由于我們想要使用用戶在所有場景的行為，而DRQN中的RNN網絡可以記住歷史信息，同時利用DPG對連續狀態與連續動作空間進行探索，因此我們算法取名MA-RDPG(Multi-Agent Recurrent Deterministic Policy Gradient)。

系統總覽

傳統的單場景優化

目前，單場景排序策略的大體結構如下，每個商品用一組特征來表示<人氣分，ctr分……>，排序策略通過給出一組特征權重來決定排序的結果，商品的分數即為各個特征的加權相加。主搜索和店鋪內搜索都有自己的排序策略，獨立優化，互不影響。

多場景聯合優化

多場景聯合排序的系統結構如下，場景之間不再是孤立的，而是由一個統一算法進行學習，然后將排序模型更新到各個排序場景（Agent）。所利用的用戶日志也不再是單場景內部的，而是基于多個場景的信息，其中不僅包含用戶的行為反饋，還包括當時所在場景的信息。

方法與應用

multi-agent reinforcement learning

問題描述

為了解決上述單場景優化的兩個缺陷，我們將多場景聯合優化轉化成一個Multi-Agent Reinforcement Learning的問題。對問題作如下具體定義：

Multi-Agent : 在多場景環境下，每一個場景的排序策略作為一個agent，agent學習自己的policy function，來將一個state映射為一個具體的action。

Sequential Decision ：用戶一次只與一個agent進行交互，當前agent的action會影響后面其他agent的策略。

Fully Cooperative ：所有的agent完全合作，來提升一個共同的指標。agent之間可以互相通信，并且所有agent的行為是由一個centralized critic進行評價。

Partially Observable ： 環境是部分可觀測的，每一個agent只能看到局部的信息，而觀察不到完整的信息。

模型

受DDPG的啟發，我們的模型也是基于actor-critic的方法，主要包含三個模塊：centralized critic，private actors和communication component。centralized critic近似一個狀態動作值函數，表示在當前狀態s下，執行動作a所能獲得的未來收益的期望。每一個agent的policy function由一個actor network來表示，輸入為當前的狀態s，輸出為一個確定的action。通信模塊將之前所有agent的local observation和action編碼成一個message向量，agent通過接收message來進行合作。通過這些message的傳遞，每個agent的決策不僅由自己決定，還會受到其他agent的影響。而且message還可以幫助agent得到更多關于環境信息的描述，幫助agent的決策。

我們用( \(o_1,r_1,a_1,?,a_{t-1},o_t,r_t\) ) 表示experience的序列，其中o/r/a 分別對應于observation/reward/action。如前所述，我們的環境是一個部分可觀測的，所以狀態st是前面所有觀測的函數，即st=f( \(o_1,r_1,a_1,?,a_{t-1},o_t,r_t\) )。N個agent { \(A_1,A_2,...,A_N\) }分別對應于N個不同的優化場景。每個agent  \(A_i\) 使用自己的policy function  \(μ^i\) (st) 產生action  \(a_t^i\) , 得到reward  \(r_t^i\) =r( \(s_t\) ,  \(a_t^i\) )，同時狀態從 \(s_t\) 跳轉到 \(s_{t+1}\) 。當給出一組action ( \(a_t^1,a_t^2,...,a_t^N\) )，我們使用一個centralized action-value function Q( \(s_t,a_t^1,a_t^2,...,a_t^N\) )來對其進行評價。

模型的具體結構見下圖所示：

Centralized Critic ： 和DDPG一樣，我們使用一個critic network來評估未來的總收益。由于我們的agent都共享一個目標，所以我們采用了一個centralized critic Q( \(s_t,a_t^1,a_t^2,...,a_t^N\) )。

Private Actor ：

每個agent有自己的private actor，來輸出自己所要采取的action。由于我們所要探索的是一個高維連續動作空間，因此我們使用神經網絡把actor設計成一個確定性的策略，即將state直接映射到一個具體的action。在時間t，agent 

\(A^{i_t}\)

的action為

\(a^{i_t}_t=μ^{i_t}(s_t; θ^{i_t})≈μ^{i_t }(h_{t-1}, o_t^{i_t};θ^{i_t})\)

，其中 \(μ^{i}(s_t; θ^{i})\) 是policy function, \(θ^{i }\) 是參數。actor network的輸入state有兩部分構成：1.當前的local observation；2.由所有agent的歷史observation和action通過LSTM編碼成的message。

Communication Component ： 將所有agent的歷史observation和action編碼成message向量，

\(h_{t?1}=LSTM(h_{t?2},[o_{t?1};a_{t?1}];ψ)\)

其中 \(o_t\) 和 \(a_t\) 表示t時刻，所有agent的observation和action。通過message的傳遞，使得任何一個agent都能夠得到更完整的信息，有助于agent之間更好的合作。

訓練

Critic ： critic network使用Bellman公式進行學習，最小化如下loss：

其中， \(y_t=r_t+yQ(h_t,o_{t+1},μ^{i_{t+1}} (h_t,o_{t+1});?)\)

Actor ： actor的更新是最大化performance function。以 \(A^{i_t}\) 在時間 t 為例，目標函數如下：

根據鏈式求導法則，actor的網絡參數更新為：

Communication Component ： 通信模塊實質上為Critic和Actor的共享部分，更新上面兩個模塊的時候就可以更新此模塊的參數。

算法描述如下：

主搜索與店鋪內搜索的應用

淘寶主搜索是淘寶流量的門戶，承載著每秒數以萬計的查詢，為用戶提供滿意的商品結果。店鋪內搜索（無query的情況下就是店鋪內推薦）也是用戶在店鋪內淘選商品的重要工具。長期以來兩者作為獨立的場景，各自優化，都取得了非常不錯的效果。由于主搜和店鋪內是統一分桶的，所以在日常優化中，我們很容易會發現兩者還是存在著一些互相影響。利用MARL的方法，將兩個場景的排序策略看作兩個agent，同時控制兩個場景的排序，優化整體去重的GMV指標，這個想法應運而生。下面介紹我們利用MA-RDPG算法在主搜和店鋪內搜索展開的應用。

首先，應用MA-RDPG算法，進行一個MARL的建模如下圖所示：

Environment： 以主搜和店鋪內搜索這兩個場景為環境。隨著兩個agent采取action，環境的狀態也發生著改變。并且該環境會跟據所采取的action和所處的state，給出一個reward。

Agents: 主搜索和店鋪內搜索分別是兩個agent。對同一個用戶而言，在同一時刻，只被一個agent所服務。

States： 我們的state包含兩個方面，一個是communication模塊所產生的上一個時刻的agent所發出的message，另一個是當前agent所觀測到的local observation。local observation包括：1. 用戶的靜態屬性信息（性別、年齡和購買力等）；2. 用戶點擊商品的屬性信息（價格、CVR和銷量等）；3. query的行業類型、以及當前用戶所在的頁碼編號；4. 當前所處場景的index。10維的message與52維的observation concat起來形成state向量。

Actions ： 如前所述，目前線上的排序是根據商品特征線性加權求和所得的分數，來進行排序的。如果控制了這些排序特征的權重，即控制了排序結果。主搜action為一個7維權重向量，店鋪內搜索action為一個3維權重向量。

Reward ： 如果用戶在此次pv上發生了點擊行為，則reward為1。若用戶發生了購買行為，則購買金額為reward，若既無點擊也無成交，則reward為-1。

實驗與分析

在線訓練過程如本文 系統總覽 中的圖所示。actor network是一個32/32/7(3)的全連層網絡，前兩層由ReLu激活，最后一次用softmax激活。critic network是一個三層的全連層網絡，用ReLu激活。γ設置為0.9。設置buffer size為 \(10^4\) ，minibatch size為100。我們進行了四組對比實驗：1. Empirical Weight（EW，經驗權重） + Learning To Rank（L2R，目前線上在使用的online LTR）；2. L2R + EW；3. L2R + L2R；4. MA-RDPG。A + B表示主搜部署A算法，店鋪內搜索部署B算法。每組實驗都與EW+EW作比較，A/B test結果如下圖所示：

結果分析

首先，MA-RDPG的效果顯然優于其他方法，甚至都不遜于目前線上最好的L2R+L2R。比起單場景獨立的優化，我們的聯合優化方法所取得的效果證明了場景之間確實有合作的空間，在多場景的協同配合之下，整體指標確實會得到提升。其次，我們可以看到MA-RDPG與L2R + L2R相比，在沒有損失主搜指標的情況下，提升了店鋪內搜索的GMV，場景之間的協助再一次得到了體現。最后，實驗L2R + EW也應證了主搜效果的提高，會一定程度上傷害店鋪內搜索的GMV這個結論。

訓練過程

我們監控每個訓練batch所輸出的平均action，觀察它們在訓練過程中的變化情況。如下圖所示：

可以看到，actor所輸出的action隨著訓練時間而逐步趨向穩定。上圖為主搜的action，下圖為店鋪內搜索的action。輸出權重的大小順序也基本與我們的業務常識相符合。

Case Study

我們選取幾種典型的case來進一步說明，MA-RDPG是如何促使兩個場景進行合作的。

case 1: 主搜是如何幫助店鋪內搜索。模擬這樣一個情景，一個高購買力的年輕女性，在尋找價格較高的商品，搜索“dress”，在主搜場景下，對比MA-RDPG和L2R給出的搜索結果。

左邊MA-RDPG給出的結果多數是大店和大品牌的商品，吸引用戶進店，從大局出發著眼于未來收益。而右邊L2R還是只考慮本場景內的收益，給出一些高轉化與高銷量的商品，希望引導用戶盡快成交。

case 2: 店鋪內搜索利用用戶在主搜場景的信息改善排序。一個男性用戶想購買一臺冰箱，起初在主搜搜索“冰箱”，并點擊瀏覽一些冰箱的商品，之后看到一款大型家電店鋪的商品，點擊并進入到店鋪內搜索頁面，比較MA-RDPG與L2R的店鋪內搜索頁結果如下：

顯然，左邊考慮了用戶在主搜場景內的信息，將更多的冰箱類目的商品排在前面，更加迎合用戶的需求。而右邊的結果并不能體現這一點。

實驗環境下的結果

主搜和店鋪內上線，測試效果如下：

單場景效果： 在綜合優化下，主搜與基準桶相比，算法相關指標提升+12.5%；店鋪內對比基準桶，算法相關指標有+9.4%的提升。

聯合效果： 在綜合優化下，聯合去重報表對比基準桶，有近+10%的提升。

總結與展望

隨著AI技術的發展，越來越多的新技術涌現，我們的排序也經歷了從規則到淺層監督學習，到深度學習、強化學習等智能排序算法的轉變。新的問題與挑戰，迫使我們不斷的開拓與進取。從一個場景的優化，到現在嘗試著聯合兩個場景一起優化，這只是聯合優化的一小步，現在的做法也比較簡單，甚至還存在著非常多的不足和缺陷，還有更多更復雜的問題需要我們去克服去解決。我們相信在面對未來越來越復雜的電商排序場景下，平臺需要的不是各場景之間的互搏與內耗，而是協同與合作，我們期待更多更高級的多場景聯合優化的方法涌現，為平臺創造更大的價值。

如果您也有論文被國際會議錄用或者對論文編譯整理工作感興趣，歡迎關注AI前線（ai-front），在后臺留下聯系方式，我們將與您聯系，并進行更多交流！

 

來自：http://www.infoq.com/cn/articles/alibaba-AAAI-2018-multi-scenario-ranking