馬爾可夫決策問題的關(guān)鍵狀態(tài)優(yōu)先學(xué)習(xí)算法

白塵

[摘 要] 針對傳統(tǒng)強化學(xué)習(xí)算法的維數(shù)災(zāi)難問題，首先提出了用于識別關(guān)鍵狀態(tài)的“決策收益率”概念及其估算方法，然后借鑒學(xué)習(xí)范圍擴展的思想，以經(jīng)典Q-Learning學(xué)習(xí)算法為基礎(chǔ)，提出了關(guān)鍵狀態(tài)優(yōu)先學(xué)習(xí)算法（Critical States Prioritized Learning，CSPL）。最后本文實現(xiàn)了機器人尋徑實驗，并比較了CSPL算法與Q-Learning算法的實驗結(jié)果。

[關(guān)鍵詞] 馬爾可夫決策；關(guān)鍵狀態(tài)；決策收益率；關(guān)鍵狀態(tài)優(yōu)先學(xué)習(xí)算法

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2016. 07. 092

[中圖分類號] TP311 [文獻標(biāo)識碼] A [文章編號] 1673 - 0194（2016）07- 0198- 05

1 引 言

馬爾可夫決策過程（Markov Decision Process，MDP）模型被廣泛用于描述通訊網(wǎng)絡(luò)、金融工程、制造系統(tǒng)和人工智能等領(lǐng)域的序貫決策問題[1]。強化學(xué)習(xí)算法（Reinforcement Learning，RL）是MDP問題的一類重要解決方法[2]。在解決復(fù)雜MDP問題時，傳統(tǒng)強化學(xué)習(xí)算法面臨著“維數(shù)災(zāi)難”問題，即隨著狀態(tài)空間和行為空間維數(shù)增大，算法的學(xué)習(xí)空間和學(xué)習(xí)時間呈指數(shù)增長[3]。

維數(shù)災(zāi)難問題的常用解決方法是分層強化學(xué)習(xí)（Hierarchical Reinforcement Learning）[4]和學(xué)習(xí)范圍擴展（Learning Scale Extension）[5]。分層強化學(xué)習(xí)將原有決策問題分解為由多個子任務(wù)構(gòu)成的層次結(jié)構(gòu)以提高整體效率，但是構(gòu)建層次結(jié)構(gòu)需要依賴大量先驗知識；學(xué)習(xí)范圍擴展是通過學(xué)習(xí)狀態(tài)空間結(jié)構(gòu)信息以擴大一次學(xué)習(xí)所影響的狀態(tài)范圍，若學(xué)習(xí)范圍設(shè)定不合理，需要耗費大量運算時間和空間記憶額外信息。兩種解決方法的實用性較低。

本文針對傳統(tǒng)強化學(xué)習(xí)算法的維數(shù)災(zāi)難問題，提出了一種新的思路：優(yōu)先學(xué)習(xí)對整體決策效果影響較大的“關(guān)鍵狀態(tài)”，從而提高復(fù)雜狀態(tài)空間下的整體決策效率。本文首先提出“決策收益率”的概念和估計方法，解決了“如何識別關(guān)鍵狀態(tài)”的問題；然后提出“逆向?qū)W習(xí)”的方法，解決了“如何優(yōu)先學(xué)習(xí)關(guān)鍵狀態(tài)”的問題；并借鑒學(xué)習(xí)范圍擴展的思想，以經(jīng)典Q-Learning學(xué)習(xí)算法[6]為基礎(chǔ)，提出了關(guān)鍵狀態(tài)優(yōu)先學(xué)習(xí)算法。