Google地圖更新反向強(qiáng)化學(xué)習(xí)算法，路線建議結(jié)果改善可達(dá)24%

Google研究院、Google地圖和DeepMind各單位多年合作，通過重新查看Google地圖路線規(guī)劃所使用的經(jīng)典算法反向強(qiáng)化學(xué)習(xí)（Inverse Reinforcement Learning，IRL），提出了一種新的IRL算法稱為RHIP（Receding Horizon Inverse Planning），改善路線建議結(jié)果達(dá)16%到24%。

Google地圖的路線建議是用戶常用的功能，可考量各種因素，規(guī)劃從地點(diǎn)A到地點(diǎn)B的最佳路線，這些因素包含抵達(dá)時(shí)間、通行費(fèi)、路況和用戶偏好等。Google運(yùn)用反向強(qiáng)化學(xué)習(xí)來學(xué)習(xí)路線建議，通過給定用于表達(dá)道路網(wǎng)絡(luò)的馬可夫決策過程（MDP）和一組展示軌跡，反向強(qiáng)化學(xué)習(xí)可計(jì)算出用戶的潛在獎(jiǎng)勵(lì)函數(shù)。

簡(jiǎn)單來說，反向強(qiáng)化學(xué)習(xí)可以從觀察到的連續(xù)決策行為學(xué)習(xí)偏好，當(dāng)有一組用戶已經(jīng)走過的路線，反向強(qiáng)化學(xué)習(xí)就能找出驅(qū)動(dòng)用戶在選擇這些路線時(shí)心中的獎(jiǎng)勵(lì)。

雖然Google在過去的研究，已經(jīng)創(chuàng)建了許多通用的反向強(qiáng)化學(xué)習(xí)解決方案，但是這些應(yīng)用很難擴(kuò)展應(yīng)用到世界規(guī)模。原因是擴(kuò)展反向強(qiáng)化學(xué)習(xí)并不容易，每次更新的時(shí)候，都需要解決一個(gè)強(qiáng)化學(xué)習(xí)的子程序，因此每一次更新都要進(jìn)行復(fù)雜的運(yùn)算，如此便會(huì)增加更新的復(fù)雜性和所需時(shí)間。要計(jì)算全世界的道路網(wǎng)絡(luò)，需要耗費(fèi)極大的計(jì)算資源，因此在實(shí)際應(yīng)用上并不切實(shí)際。

為了解決這個(gè)問題，Google進(jìn)一步研究突破既有限制擴(kuò)展反向強(qiáng)化學(xué)習(xí)，發(fā)展了一種稱為RHIP的方法，研究人員提到，他們實(shí)現(xiàn)了目前實(shí)際應(yīng)用中最大的IRL實(shí)例。

研究人員從人們做計(jì)劃的方式獲得啟發(fā)，像是人們會(huì)問“接下來1小時(shí)要做什么？”或是“5年后的生活會(huì)是什么樣子”。人們?cè)谟?jì)劃和決策時(shí)，通常會(huì)考慮未來一段時(shí)間范圍，但隨著時(shí)間的推進(jìn)，表示最遠(yuǎn)時(shí)間范圍的線也會(huì)跟著移動(dòng)，也就是說人們通常不會(huì)一次考慮非常遙遠(yuǎn)的未來，而是把注意力集中在近期規(guī)劃，并在過程中通過觀察持續(xù)調(diào)整未來方向。

RHIP的核心概念便是在靠近當(dāng)前的位置，或是已知路徑的地方，使用詳細(xì)的策略來確定路線，但在較遠(yuǎn)的地方，則選擇更簡(jiǎn)單且節(jié)省計(jì)算資源的策略，綜合遠(yuǎn)近規(guī)劃策略，達(dá)到高效且準(zhǔn)確的路網(wǎng)導(dǎo)航。

相較于精心調(diào)整的基準(zhǔn)，RHIP策略使汽車與機(jī)踏車的全球路線相符比例，分別提高15.9%和24.1%。而所謂的全球路線相符比例，指得是用戶實(shí)際行駛的路線，符合Google地圖所建議路線的百分比。RHIP的執(zhí)行速度更快，結(jié)果也更準(zhǔn)確，相較傳統(tǒng)IRL存在難以擴(kuò)展的問題，RHIP使Google能夠在有超大量狀態(tài)、示范軌跡和模型參數(shù)上訓(xùn)練獎(jiǎng)勵(lì)模型。