滴滴KDD 2019 論文詳解：基于深度價值網(wǎng)絡(luò)的多司機智能派單模型

世界數(shù)據(jù)挖掘領(lǐng)域頂級學術(shù)會議KDD2019繼續(xù)在美國阿拉斯加州安克雷奇市舉行。本次KDD大會首次采用雙盲評審制，共吸引了全球范圍內(nèi)約1879篇論文投遞。其中，Applied Data Science track收到約 700 篇論文投稿，最終45篇被接收為Oral論文，100篇被接收為Poster論文；而Research track 共收到了 1179 篇投稿，最終111篇被接收為Oral論文，63篇被接收為Poster論文。

今年，滴滴共有三篇Oral論文入選KDD2019，研究內(nèi)容涵蓋基于深度學習方法自動化地生成工單摘要、基于深度強化學習與半馬爾科夫決策過程進行智能派單及模仿學習和GAN在環(huán)境重構(gòu)的探索。

本文是對滴滴Oral論文《A Deep Value-networkBased Approach for Multi-Driver Order Dispatching》的詳細解讀。滴滴AI Labs技術(shù)團隊在KDD2018 Oral 論文《Large?Scale Order Dispatch in On?DemandRide?Hailing Platforms: A Learning and Planning Approach》的基礎(chǔ)上，新提出了一種新的基于深度強化學習與半馬爾科夫決策過程的智能派單應(yīng)用，在同時考慮時間與空間的長期優(yōu)化目標的基礎(chǔ)上利用深度神經(jīng)網(wǎng)絡(luò)進行更準確有效的價值估計。通過系統(tǒng)的離線模擬實驗以及在滴滴平臺的在線AB實驗證明，這種基于深度強化學習的派單算法相比現(xiàn)有最好的方法能進一步顯著提升平臺各項效率及用戶體驗。

研究背景

當下滴滴網(wǎng)約車采用的全局最優(yōu)的派單模式，是通過搜索1.5-2秒內(nèi)所有可能的司機乘客匹配，由算法綜合考慮接駕距離、道路擁堵情況等因素，自動將訂單匹配給最合適的司機接單，讓全局乘客接駕時間最短。本文所述的算法也是在這一派單模式基礎(chǔ)下的改進。

司機在不同時間地點會有不同的未來收益期望 (“熱區(qū)”vs”冷區(qū)”)。準確地估計這樣的收益 (或者價值) 期望對于提升派單效率有重要的意義。下面兩個簡單的例子可以更形象的說明這一點。

第一個例子是供給受限的情況，這里有一個司機，兩個乘客A跟B分別前往”熱區(qū)”和”冷區(qū)”，假設(shè)其他影響派單的因素完全一樣 (接駕距離、安全合規(guī)、合規(guī)司機收入傾斜、服務(wù)分等)。那么可以認為把乘客A派給司機是更優(yōu)的選擇 (實際情況更為復(fù)雜，比如在供需不平衡的情況下引入排隊機制)，因為司機在完成A訂單后可以更好的滿足”熱區(qū)”運力不足的需求，從而在整體上減少司機的空車時間，達到調(diào)節(jié)供需的作用；

第二個例子是需求受限的情況。假設(shè)這里有一個乘客，司機A跟B分別在”冷區(qū)”和”熱區(qū)”，而其他影響派單的因素完全一樣，那么在這個情況下，可以認為把訂單派給A會是更好的選擇，因為B在”熱區(qū)”期望上能比A更快地接到下一單，這樣長期來看總體上最小化了A跟B的空車時間。

深度價值網(wǎng)絡(luò)的強化學習和匹配規(guī)劃 (Learning andPlanning)

在上面兩個例子中說明，不管是供給端還是需求端受限，我們都可以通過在派單決策中系統(tǒng)的考慮冷”熱區(qū)”之間關(guān)系來提升系統(tǒng)效率。下面我們從數(shù)學上對派單問題進行建模并給出冷”熱區(qū)”在強化學習框架下的定義。

派單可以看成一個系列決策問題，我們將其建模為帶有時間延展性的馬爾科夫決策過程，也稱為Semi-MDP。與標準MDP類似，司機從一個狀態(tài) (時間、地點、情景式特征) 出發(fā)，通過接單或者空車游走的動作 (option)，轉(zhuǎn)移到下一個狀態(tài)，并獲得相應(yīng)獎勵 (對于接單的動作是訂單的金額，空車游走或者上下線則為0)。這里與標準MDP最大的不同在于動作帶有時間延展性，不同動作時間跨度不同，這一點很重要，會體現(xiàn)在訓(xùn)練使用的Bellman equation中。

在Semi-MDP的框架下我們可以寫出強化學習中價值函數(shù)的定義，表示司機從一個狀態(tài)出發(fā)，在給定的派單策略下，直到一天結(jié)束的期望收益

跟標準MDP類似，我們可以寫出基于價值函數(shù)的一步轉(zhuǎn)移Bellman方程

上面的公式表示了司機從狀態(tài)St經(jīng)過k個時間步長轉(zhuǎn)移到St+k，并收獲獎勵R。這里跟標準MDP最大的不同在于等式右邊第一項等效即時獎勵，不是直接用R，而是對R做了一個跟步長k相關(guān)的衰減。在Semi-MDP框架下兩個帶來同樣收益的動作，時間跨度小的動作的等效即時獎勵更大。另一角度來看，這可以理解為對廣泛應(yīng)用于實際的reward clipping做了一個平滑 (smoothing) 處理，用連續(xù)衰減代替了截斷處理 (clipping)。

我們用一個深度神經(jīng)網(wǎng)絡(luò)來表示價值函數(shù)，為了增加策略估計中遞歸迭代的穩(wěn)定性一般需要使用一個慢速更新的目標網(wǎng)絡(luò) (target network)，或者使用下面要介紹的在訓(xùn)練中加入Lipschitz正則化的方法。

一般的強化學習應(yīng)用，執(zhí)行策略只需要針對價值函數(shù)應(yīng)用貪心算法，但在線上派單的環(huán)境下我們需要調(diào)和多司機與多訂單之間的派單限制，所以我們通過解二分圖優(yōu)化問題來進行全局規(guī)劃。線上每2秒派單一次，每次派單會求解一個組合優(yōu)化匹配問題，目標函數(shù)是在滿足派單的限制下使得匹配結(jié)果總體邊權(quán)和最高

這里我們使用基于價值函數(shù)以及時序差分誤差 (TD Error) 的方法來計算每個訂單與司機的匹配分值

簡單來看，這里的匹配分數(shù)跟訂單終點價值成正比，跟司機當前狀態(tài)價值成反比，這使得在派單決策中同時考慮到長期收益 (時間維度上的優(yōu)化) 以及二分圖匹配得到的空間上最優(yōu)解，兩者的結(jié)合達到時空優(yōu)化 (spatiotemporal optimality) 的目標。最后，我們在邊權(quán)計算中加入了對用戶體驗的刻畫，最終的權(quán)值綜合考慮了長期價值司機收益以及用戶體驗多個目標。

如何學習針對派單的時空價值函數(shù)？

我們使用神經(jīng)網(wǎng)絡(luò)來表示上面定義的價值函數(shù)，訓(xùn)練通過Bellman方程的價值迭代，如何保證非線性迭代的穩(wěn)定性以及如何表達狀態(tài)空間是學習成功的關(guān)鍵。下面我們分為四個部分來介紹我們針對學習的難點提出的技術(shù)中的創(chuàng)新。

Cerebellar Embedding

機器學習應(yīng)用中很重要的一步是如何進行狀態(tài)表達。我們提出一種新的基于對狀態(tài)空間不同大小的重疊劃分的embedding網(wǎng)絡(luò)結(jié)構(gòu)。可以促進訓(xùn)練中的知識轉(zhuǎn)移，幫助網(wǎng)絡(luò)學習多層次的抽象特征，同時能解決訓(xùn)練數(shù)據(jù)分布稀疏不均的問題。例如人學習人工智能，我們會對人工智能領(lǐng)域進行不同的劃分比如強化學習、監(jiān)督學習，或者圖像識別，自然語言處理，推薦系統(tǒng)，或者優(yōu)化，統(tǒng)計，控制，具體的應(yīng)用相當于訓(xùn)練數(shù)據(jù)，會同時激活其中多個分類，比如派單應(yīng)用會激活 (activate) 強化學習，推薦系統(tǒng)，優(yōu)化控制等。通過解決不同應(yīng)用，我們學習掌握到不同類別的知識 (高層次的抽象概念)。當拿到一個新的應(yīng)用，我們可以很快將這個應(yīng)用映射到我們掌握的類別上，并利用我們對這些類別的知識來快速地求解這個新的應(yīng)用，這也就是我們常說的泛化 (generalization) 能力。同樣地，我們提出的這個新的網(wǎng)絡(luò)結(jié)構(gòu)能夠提升泛化，形成更豐富的狀態(tài)表達。

具體在派單中，比如對地理位置的表達，我們使用了大小不同的六邊形格子系統(tǒng)對地理空間進行劃分，這樣具體的地點的狀態(tài)相當于包含這個地點的多個大小不同的格子對應(yīng)embedding向量的加總表示。這樣學習可以達到兩個作用，一是幫助網(wǎng)絡(luò)學習比經(jīng)緯度更抽象的概念比如街道，小區(qū)，城市等；其次是針對不同區(qū)域比如市中心或者郊區(qū)網(wǎng)絡(luò)能自適應(yīng)學習結(jié)合不同分割精度來獲得更準確的狀態(tài)表達。

Lipschitz正則化 (regularization)

在訓(xùn)練中我們提出一種新的結(jié)合了Lipschitz正則化的策略估計方法，通過直接控制Lipschitz常量來學習得到一個更光滑的價值函數(shù)。價值函數(shù)光滑程度的重要性主要體現(xiàn)在增強狀態(tài)輸入之間關(guān)聯(lián)性以及提高非線性價值迭代的收斂性兩方面。如下圖所示，黃色跟藍色分別代表使用了和沒有使用Lipschitz正則化的神經(jīng)網(wǎng)絡(luò)。一開始兩個網(wǎng)絡(luò)的輸入分布幾乎重合，在對網(wǎng)絡(luò)參數(shù)加入了相等大小的噪聲后，藍色分布發(fā)生了劇烈變化，而黃色分布則體現(xiàn)了對噪聲的魯棒性。

情景隨機化  (contextrandomization)

我們學習的狀態(tài)價值函數(shù)帶有實時特征，為了使這部分特征有更好的泛化能力我們在訓(xùn)練中使用了類似于Domain Randomization的方法我們稱為情景隨機化。具體來講我們會在訓(xùn)練之前基于歷史數(shù)據(jù)建立一個所有實時特征的基于KD Tree的時空索引，在訓(xùn)練時針對每個訓(xùn)練數(shù)據(jù)的時空狀態(tài)我們會在索引中查找歷史上所有落在這個時空狀態(tài)附近的實時特征，并從中隨機采樣用于訓(xùn)練。通過這樣使得價值函數(shù)在訓(xùn)練中適應(yīng)不同情況下的實時性，增強對現(xiàn)實中的噪聲及variance的泛化能力。

多城市遷移學習 (multi-city transfer learning)

現(xiàn)實中派單具有很強的區(qū)域性，一般以城市為中心，不同的城市因為地理位置，氣候特征等不同而在供需動態(tài)等方面有不同的特性，這可以看作一個典型的多任務(wù)學習問題。我們針對派單中的價值估計提出了一種基于progressive network的新的多城市遷移學習框架，可以有效地利用數(shù)據(jù)量豐富的城市數(shù)據(jù)來促進對數(shù)據(jù)稀疏的城市的價值估計；另外，通過在遷移過程中針對不同輸入建立不同lateral connection網(wǎng)絡(luò)能夠在訓(xùn)練中更專注于有效的遷移 (比如實時特征的處理) 以及通過訓(xùn)練決定遷移的具體方式及強度 (調(diào)整lateral connection的權(quán)重)。

模擬及線上實驗結(jié)果

我們分別通過線下模擬以及線上AB測試來驗證方法的有效性。在基于現(xiàn)實數(shù)據(jù)的線下模擬實驗中，我們與其他四種不同方法進行了系統(tǒng)的多城市多天的對比。在為期多周線上AB測試中，在三個不同城市從不同維度上 (應(yīng)答率，完單率，司機總收入) 與線上默認方法進行了對比。結(jié)果均顯示，我們提出的基于神經(jīng)網(wǎng)絡(luò)長期價值估計的強化學習派單算法能進一步顯著提升平臺司機收入以及用戶體驗。

論文全文：https://www.kdd.org/kdd2019/accepted-papers/view/a-deep-value-network-based-approach-for-multi-driver-order-dispatching

在最新一期的雷鋒網(wǎng) AI 研習社 大講堂上，滴滴 AI Labs技術(shù)團隊也為我們帶來了相應(yīng)的詳細解讀分享。詳情可 掃碼 觀看回放視頻！

雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。