世界數據挖掘領域頂級學術會議KDD2019繼續在美國阿拉斯加州安克雷奇市舉行。本次KDD大會首次採用雙盲評審制，共吸引了全球範圍內約1879篇論文投遞。其中，Applied Data Science track收到約 700 篇論文投稿，最終45篇被接收為Oral論文，100篇被接收為Poster論文；而Research track 共收到了 1179 篇投稿，最終111篇被接收為Oral論文，63篇被接收為Poster論文。
今年，滴滴共有三篇Oral論文入選KDD2019，研究內容涵蓋基於深度學習方法自動化地生成工單摘要、基於深度強化學習與半馬爾科夫決策過程進行智能派單及模仿學習和GAN在環境重構的探索。
本文是對滴滴Oral論文《A Deep Value-networkBased Approach for Multi-Driver Order Dispatching》的詳細解讀。滴滴AI Labs技術團隊在KDD2018 Oral 論文《Large‑Scale Order Dispatch in On‑DemandRide‑Hailing Platforms: A Learning and Planning Approach》的基礎上，新提出了一種新的基於深度強化學習與半馬爾科夫決策過程的智能派單應用，在同時考慮時間與空間的長期優化目標的基礎上利用深度神經網絡進行更準確有效的價值估計。通過系統的離線模擬實驗以及在滴滴平臺的在線AB實驗證明，這種基於深度強化學習的派單算法相比現有最好的方法能進一步顯著提昇平臺各項效率及用戶體驗。
研究背景當下滴滴網約車採用的全局最優的派單模式，是通過搜索1.5-2秒內所有可能的司機乘客匹配，由算法綜合考慮接駕距離、道路擁堵情況等因素，自動將訂單匹配給最合適的司機接單，讓全局乘客接駕時間最短。本文所述的算法也是在這一派單模式基礎下的改進。
司機在不同時間地點會有不同的未來收益期望 (「熱區」vs」冷區」)。準確地估計這樣的收益 (或者價值) 期望對於提升派單效率有重要的意義。下面兩個簡單的例子可以更形象的說明這一點。
第一個例子是供給受限的情況，這裡有一個司機，兩個乘客A跟B分別前往」熱區」和」冷區」，假設其他影響派單的因素完全一樣 (接駕距離、安全合規、合規司機收入傾斜、服務分等)。那麼可以認為把乘客A派給司機是更優的選擇 (實際情況更為複雜，比如在供需不平衡的情況下引入排隊機制)，因為司機在完成A訂單後可以更好的滿足」熱區」運力不足的需求，從而在整體上減少司機的空車時間，達到調節供需的作用；
第二個例子是需求受限的情況。假設這裡有一個乘客，司機A跟B分別在」冷區」和」熱區」，而其他影響派單的因素完全一樣，那麼在這個情況下，可以認為把訂單派給A會是更好的選擇，因為B在」熱區」期望上能比A更快地接到下一單，這樣長期來看總體上最小化了A跟B的空車時間。
深度價值網絡的強化學習和匹配規劃 (Learning andPlanning)在上面兩個例子中說明，不管是供給端還是需求端受限，我們都可以通過在派單決策中系統的考慮冷」熱區」之間關係來提升系統效率。下面我們從數學上對派單問題進行建模並給出冷」熱區」在強化學習框架下的定義。
派單可以看成一個系列決策問題，我們將其建模為帶有時間延展性的馬爾科夫決策過程，也稱為Semi-MDP。與標準MDP類似，司機從一個狀態 (時間、地點、情景式特徵) 出發，通過接單或者空車遊走的動作 (option)，轉移到下一個狀態，並獲得相應獎勵 (對於接單的動作是訂單的金額，空車遊走或者上下線則為0)。這裡與標準MDP最大的不同在於動作帶有時間延展性，不同動作時間跨度不同，這一點很重要，會體現在訓練使用的Bellman equation中。
在Semi-MDP的框架下我們可以寫出強化學習中價值函數的定義，表示司機從一個狀態出發，在給定的派單策略下，直到一天結束的期望收益
跟標準MDP類似，我們可以寫出基於價值函數的一步轉移Bellman方程
上面的公式表示了司機從狀態St經過k個時間步長轉移到St+k，並收穫獎勵R。這裡跟標準MDP最大的不同在於等式右邊第一項等效即時獎勵，不是直接用R，而是對R做了一個跟步長k相關的衰減。在Semi-MDP框架下兩個帶來同樣收益的動作，時間跨度小的動作的等效即時獎勵更大。另一角度來看，這可以理解為對廣泛應用於實際的reward clipping做了一個平滑 (smoothing) 處理，用連續衰減代替了截斷處理 (clipping)。
我們用一個深度神經網絡來表示價值函數，為了增加策略估計中遞歸迭代的穩定性一般需要使用一個慢速更新的目標網絡 (target network)，或者使用下面要介紹的在訓練中加入Lipschitz正則化的方法。
一般的強化學習應用，執行策略只需要針對價值函數應用貪心算法，但在線上派單的環境下我們需要調和多司機與多訂單之間的派單限制，所以我們通過解二分圖優化問題來進行全局規劃。線上每2秒派單一次，每次派單會求解一個組合優化匹配問題，目標函數是在滿足派單的限制下使得匹配結果總體邊權和最高
這裡我們使用基於價值函數以及時序差分誤差 (TD Error) 的方法來計算每個訂單與司機的匹配分值
簡單來看，這裡的匹配分數跟訂單終點價值成正比，跟司機當前狀態價值成反比，這使得在派單決策中同時考慮到長期收益 (時間維度上的優化) 以及二分圖匹配得到的空間上最優解，兩者的結合達到時空優化 (spatiotemporal optimality) 的目標。最後，我們在邊權計算中加入了對用戶體驗的刻畫，最終的權值綜合考慮了長期價值司機收益以及用戶體驗多個目標。
如何學習針對派單的時空價值函數？我們使用神經網絡來表示上面定義的價值函數，訓練通過Bellman方程的價值迭代，如何保證非線性迭代的穩定性以及如何表達狀態空間是學習成功的關鍵。下面我們分為四個部分來介紹我們針對學習的難點提出的技術中的創新。
Cerebellar Embedding
機器學習應用中很重要的一步是如何進行狀態表達。我們提出一種新的基於對狀態空間不同大小的重疊劃分的embedding網絡結構。可以促進訓練中的知識轉移，幫助網絡學習多層次的抽象特徵，同時能解決訓練數據分布稀疏不均的問題。例如人學習人工智慧，我們會對人工智慧領域進行不同的劃分比如強化學習、監督學習，或者圖像識別，自然語言處理，推薦系統，或者優化，統計，控制，具體的應用相當於訓練數據，會同時激活其中多個分類，比如派單應用會激活 (activate) 強化學習，推薦系統，優化控制等。通過解決不同應用，我們學習掌握到不同類別的知識 (高層次的抽象概念)。當拿到一個新的應用，我們可以很快將這個應用映射到我們掌握的類別上，並利用我們對這些類別的知識來快速地求解這個新的應用，這也就是我們常說的泛化 (generalization) 能力。同樣地，我們提出的這個新的網絡結構能夠提升泛化，形成更豐富的狀態表達。
具體在派單中，比如對地理位置的表達，我們使用了大小不同的六邊形格子系統對地理空間進行劃分，這樣具體的地點的狀態相當於包含這個地點的多個大小不同的格子對應embedding向量的加總表示。這樣學習可以達到兩個作用，一是幫助網絡學習比經緯度更抽象的概念比如街道，小區，城市等；其次是針對不同區域比如市中心或者郊區網絡能自適應學習結合不同分割精度來獲得更準確的狀態表達。
Lipschitz正則化 (regularization)
在訓練中我們提出一種新的結合了Lipschitz正則化的策略估計方法，通過直接控制Lipschitz常量來學習得到一個更光滑的價值函數。價值函數光滑程度的重要性主要體現在增強狀態輸入之間關聯性以及提高非線性價值迭代的收斂性兩方面。如下圖所示，黃色跟藍色分別代表使用了和沒有使用Lipschitz正則化的神經網絡。一開始兩個網絡的輸入分布幾乎重合，在對網絡參數加入了相等大小的噪聲後，藍色分布發生了劇烈變化，而黃色分布則體現了對噪聲的魯棒性。
情景隨機化 (contextrandomization)
我們學習的狀態價值函數帶有實時特徵，為了使這部分特徵有更好的泛化能力我們在訓練中使用了類似於Domain Randomization的方法我們稱為情景隨機化。具體來講我們會在訓練之前基於歷史數據建立一個所有實時特徵的基於KD Tree的時空索引，在訓練時針對每個訓練數據的時空狀態我們會在索引中查找歷史上所有落在這個時空狀態附近的實時特徵，並從中隨機採樣用於訓練。通過這樣使得價值函數在訓練中適應不同情況下的實時性，增強對現實中的噪聲及variance的泛化能力。
多城市遷移學習 (multi-city transfer learning)
現實中派單具有很強的區域性，一般以城市為中心，不同的城市因為地理位置，氣候特徵等不同而在供需動態等方面有不同的特性，這可以看作一個典型的多任務學習問題。我們針對派單中的價值估計提出了一種基於progressive network的新的多城市遷移學習框架，可以有效地利用數據量豐富的城市數據來促進對數據稀疏的城市的價值估計；另外，通過在遷移過程中針對不同輸入建立不同lateral connection網絡能夠在訓練中更專注於有效的遷移 (比如實時特徵的處理) 以及通過訓練決定遷移的具體方式及強度 (調整lateral connection的權重)。
我們分別通過線下模擬以及線上AB測試來驗證方法的有效性。在基於現實數據的線下模擬實驗中，我們與其他四種不同方法進行了系統的多城市多天的對比。在為期多周線上AB測試中，在三個不同城市從不同維度上 (應答率，完單率，司機總收入) 與線上默認方法進行了對比。結果均顯示，我們提出的基於神經網絡長期價值估計的強化學習派單算法能進一步顯著提昇平臺司機收入以及用戶體驗。
論文全文：https://www.kdd.org/kdd2019/accepted-papers/view/a-deep-value-network-based-approach-for-multi-driver-order-dispatching
在最新一期的雷鋒網(公眾號：雷鋒網) AI 研習社 大講堂上，滴滴 AI Labs技術團隊也為我們帶來了相應的詳細解讀分享。詳情可 掃碼 觀看回放視頻！
雷鋒網特約稿件，未經授權禁止轉載。詳情見轉載須知。