Google地圖更新反向強化學習演算法，路線建議結果改善可達24%

Google研究院、Google地圖和DeepMind各單位多年合作，透過重新檢視Google地圖路線規畫所使用的經典演算法反向強化學習（Inverse Reinforcement Learning，IRL），提出了一種新的IRL演算法稱為RHIP（Receding Horizon Inverse Planning），改善路線建議結果達16％到24％。

Google地圖的路線建議是用戶常用的功能，可考量各種因素，規畫從地點A到地點B的最佳路線，這些因素包含抵達時間、通行費、路況和用戶偏好等。Google運用反向強化學習來學習路線建議，透過給定用於表達道路網路的馬可夫決策過程（MDP）和一組展示軌跡，反向強化學習可計算出用戶的潛在獎勵函式。

簡單來說，反向強化學習可以從觀察到的連續決策行為學習偏好，當有一組用戶已經走過的路線，反向強化學習就能找出驅動用戶在選擇這些路線時心中的獎勵。

雖然Google在過去的研究，已經創建了許多通用的反向強化學習解決方案，但是這些應用很難擴展應用到世界規模。原因是擴展反向強化學習並不容易，每次更新的時候，都需要解決一個強化學習的子程序，因此每一次更新都要進行複雜的運算，如此便會增加更新的複雜性和所需時間。要計算全世界的道路網路，需要耗費極大的運算資源，因此在實際應用上並不切實際。

為了解決這個問題，Google進一步研究突破既有限制擴展反向強化學習，發展了一種稱為RHIP的方法，研究人員提到，他們實現了目前實際應用中最大的IRL實例。

研究人員從人們做計畫的方式獲得啟發，像是人們會問「接下來1小時要做什麼？」或是「5年後的生活會是什麼樣子」。人們在計畫和決策時，通常會考慮未來一段時間範圍，但隨著時間的推進，表示最遠時間範圍的線也會跟著移動，也就是說人們通常不會一次考慮非常遙遠的未來，而是把注意力集中在近期規畫，並在過程中透過觀察持續調整未來方向。

RHIP的核心概念便是在靠近當前的位置，或是已知路徑的地方，使用詳細的策略來確定路線，但在較遠的地方，則選擇更簡單且節省計算資源的策略，綜合遠近規畫策略，達到高效且準確的路網導航。

相較於精心調整的基準，RHIP策略使汽車與機踏車的全球路線相符比例，分別提高15.9％和24.1％。而所謂的全球路線相符比例，指得是用戶實際行駛的路線，符合Google地圖所建議路線的百分比。RHIP的執行速度更快，結果也更準確，相較傳統IRL存在難以擴展的問題，RHIP使Google能夠在有超大量狀態、示範軌跡和模型參數上訓練獎勵模型。