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

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

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

研究背景

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

司機(jī)在不同時(shí)間地點(diǎn)會(huì)有不同的未來(lái)收益期望 (“熱區(qū)”vs”冷區(qū)”)。準(zhǔn)確地估計(jì)這樣的收益 (或者價(jià)值) 期望對(duì)于提升派單效率有重要的意義。下面兩個(gè)簡(jiǎn)單的例子可以更形象的說(shuō)明這一點(diǎn)。

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

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

深度價(jià)值網(wǎng)絡(luò)的強(qiáng)化學(xué)習(xí)和匹配規(guī)劃 (Learning andPlanning)

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

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

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

跟標(biāo)準(zhǔn)MDP類(lèi)似，我們可以寫(xiě)出基于價(jià)值函數(shù)的一步轉(zhuǎn)移Bellman方程

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

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

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

這里我們使用基于價(jià)值函數(shù)以及時(shí)序差分誤差 (TD Error) 的方法來(lái)計(jì)算每個(gè)訂單與司機(jī)的匹配分值

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

如何學(xué)習(xí)針對(duì)派單的時(shí)空價(jià)值函數(shù)？

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

Cerebellar Embedding

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

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

Lipschitz正則化 (regularization)

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

情景隨機(jī)化  (contextrandomization)

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

多城市遷移學(xué)習(xí) (multi-city transfer learning)

現(xiàn)實(shí)中派單具有很強(qiáng)的區(qū)域性，一般以城市為中心，不同的城市因?yàn)榈乩砦恢茫瑲夂蛱卣鞯炔煌诠┬鑴?dòng)態(tài)等方面有不同的特性，這可以看作一個(gè)典型的多任務(wù)學(xué)習(xí)問(wèn)題。我們針對(duì)派單中的價(jià)值估計(jì)提出了一種基于progressive network的新的多城市遷移學(xué)習(xí)框架，可以有效地利用數(shù)據(jù)量豐富的城市數(shù)據(jù)來(lái)促進(jìn)對(duì)數(shù)據(jù)稀疏的城市的價(jià)值估計(jì)；另外，通過(guò)在遷移過(guò)程中針對(duì)不同輸入建立不同lateral connection網(wǎng)絡(luò)能夠在訓(xùn)練中更專(zhuān)注于有效的遷移 (比如實(shí)時(shí)特征的處理) 以及通過(guò)訓(xùn)練決定遷移的具體方式及強(qiáng)度 (調(diào)整lateral connection的權(quán)重)。

模擬及線上實(shí)驗(yàn)結(jié)果

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

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

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

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