Q-学习，马克尔决策过程：强化学习
馬爾可夫決策過程
馬爾可夫決策過程是基于馬爾可夫過程理論的隨機動態系統的最優決策過程。馬爾可夫決策過程是序貫決策的主要研究領域。它是馬爾可夫過程與確定性的動態規劃相結合的產物，故又稱馬爾可夫型隨機動態規劃，屬于運籌學中數學規劃的一個分支。
馬爾可夫決策過程是指決策者周期地或連續地觀察具有馬爾可夫性的隨機動態系統，序貫地作出決策。即根據每個時刻觀察到的狀態，從可用的行動集合中選用一個行動作出決策，系統下一步（未來）的狀態是隨機的，并且其狀態轉移概率具有馬爾可夫性。決策者根據新觀察到的狀態，再作新的決策，依此反復地進行。馬爾可夫性是指一個隨機過程未來發展的概率規律與觀察之前的歷史無關的性質。馬爾可夫性又可簡單敘述為狀態轉移概率的無后效性。狀態轉移概率具有馬爾可夫性的隨機過程即為馬爾可夫過程。馬爾可夫決策過程又可看作隨機對策的特殊情形，在這種隨機對策中對策的一方是無意志的。馬爾可夫決策過程還可作為馬爾可夫型隨機最優控制，其決策變量就是控制變量。
原文地址：http://mnemstudio.org/path-finding-q-learning-tutorial.htm
這篇教程通過簡單且易于理解的實例介紹了Q-學習的概念知識，例子描述了一個智能體通過非監督學習的方法對未知的環境進行學習。
假設我們的樓層內共有5個房間，房間之間通過一道門相連，正如下圖所示。我們將房間編號為房間0到房間4，樓層的外部可以被看作是一間大房間，編號為5。注意到房間1和房間4可以直接通到房間5。
?
我們可以用圖來表示上述的房間，將每一個房間看作是一個節點，每一道門看作是一條邊（鏈路）。
?
在這個例子中，我們可能在任意一間房間中放置一個智能體（機器人），并期望該智能體能夠從該房間開始走出這棟樓（可以認為是我們的目標房間）。換句話說，智能體的目的地是房間5。為了設置這間房間作為目標，我們為每一道門（節點之間的邊）賦予一個獎勵值。能夠直接通到目標房間的門賦予一及時獎勵值100，而其他的未與目標房間直接相連的門賦予獎勵值0。因為每一道門都有兩個方向，因此，每一道門在圖中將描述為兩個箭頭。如下所示：
?
當然，從房間5到房間5的獎勵值也是100，其他所有直接通到目標房間5的獎勵值也是100。在Q-學習中，學習的目標是達到具有最高獎勵值的狀態，因此，如果智能體到底了目標位置，它將永遠的留在那兒。這種類型的目標被稱為“吸收目標”。
?
想象我們的智能體是一個不會說話的虛擬機器人，但是它可以從經驗中學習。智能體能夠從一個房間到底另外一個房間，但是它對周圍的環境一無所知，它不知道怎么走能夠通到樓層外面（房間5）。
?
假設我們想對智能體從某一個房間中撤退的過程進行建模，現在，我們假設智能體在房間2內，我們希望智能體通過學習到達房間5。
?
?
Q-學習中的術語包括狀態（state）和動作（action）。
?
我們將每一個房間稱為一個“狀態”，智能體從一個房間到另一個房間的移動過程稱為“動作”。在我們的示意圖中，狀態被描述為節點，動作被描述成箭頭。
?
?
假設智能體處于狀態2，那么，它從狀態2能夠直接到達狀態3，因為狀態2和狀態3相連。然而，智能體從狀態2不能直接到達狀態1，因為在房間2和房間1之間沒有直接相通的門，也即沒有箭頭存在。從狀態3，智能體要么到達狀態1，要么到達狀態4，抑或著返回到狀態2。如果智能體處于狀態4，那么它有3周可能的動作，即到達狀態0,、5或3。如果智能體在狀態1，它能夠到達狀態5或者狀態3。從狀態0，它只能到達狀態4。
?
我們可以將狀態圖和即時獎勵值填入到下面的獎勵表中，即矩陣R：
（表中的-1代表空值，表示節點之間無邊相連）
?
現在，我們再增加一個相似的矩陣Q，代表智能體從經驗中所學到的知識。矩陣Q的行代表智能體當前的狀態，列代表到達下一個狀態的可能的動作。
?
因為智能體在最初對環境一無所知，因此矩陣Q被初始化為0。在這個例子中，為了闡述方便，我們假設狀態的數量是已知的（設為6）。如果我們不知道有多少狀態時，矩陣Q在最初被設為只有一個元素。如果新的狀態一旦被發現，對矩陣Q增加新的行和新的列非常簡單。
Q-學習的轉換規則非常簡單，為下面的式子：
Q(state,?action)=R(state,?action)?+?Gamma?*?Max(Q[next?state,?all?actions])
依據這個公式，矩陣Q中的一個元素值就等于矩陣R中相應元素的值與學習變量Gamma乘以到達下一個狀態的所有可能動作的最大獎勵值的總和。
我們虛擬的智能體將從經驗中學習，不需要教師指導信號（這被稱為非監督學習）。智能體將從一個狀態到另一個狀態進行探索，直到它到達目標狀態。我們將每一次探索作為一次經歷，每一次經歷包括智能體從初始狀態到達目標狀態的過程。每次智能體到達了目標狀態，程序將會轉向下一次探索。
?
Q-學習算法的計算過程如下：
1、設置參數Gamma，以及矩陣R中的環境獎勵值；
2、初始化Q矩陣為0；
3、對每一次經歷：
?????????隨機選擇一個狀態；
????????Do?while?目標狀態未到達
?????????????對當前狀態的所有可能的動作中，選擇一個可能的動作；
?????????????使用這個可能的動作，到達下一個狀態；
?????????????對下一個狀態，基于其所有可能的動作，獲得最大的Q值；
?????????????計算：Q(state,?action)=R(state,?action)?+?Gamma?*?Max(Q[next?state,?all?actions])
?????????????設置下一個狀態作為當前狀態；
??End?For
?
智能體利用上述的算法從經驗中學習，每一次經歷等價于一次訓練。在每一次訓練中，智能體對環境進行探索（用矩陣R表示），并且其一旦到達目標狀態，就得到獎勵值。訓練的目的是增強智能體的大腦，用矩陣Q表示。越多的訓練結果將導致更優的矩陣Q。在這種情況下，如果矩陣Q已經被增強，那么智能體就不會四處盲目的探索，而是會找到最快的路線到達目標狀態。
參數Gamma的取值在0到1之間（0<=Gamma<=1），如果Gamma越接近于0，智能體更趨向于僅僅考慮即時獎勵；如果Gamma更接近于1，智能體將以更大的權重考慮未來的獎勵，更愿意將獎勵延遲。
為了使用矩陣Q，智能體僅僅簡單地跟蹤從起始狀態到目標狀態的狀態序列，這個算法在矩陣Q中，為當前狀態尋找到具有最高獎勵值的動作。
利用矩陣Q的算法如下：
1、設置當前狀態=初始狀態；
2、從當前狀態開始，尋找具有最高Q值的動作；
3、設置當前狀態=下一個狀態；
4、重復步驟2和3，直到當前狀態=目標狀態。
上述的算法將返回從初始狀態到目標狀態的狀態序列。
?
為了理解Q-學習算法是怎樣工作的，我們通過分析少量的例子進行分析。
我們設置學習率Gamma等于0.8，初始的狀態是房間1。
初始的矩陣Q作為一個零矩陣，如下：
觀察R矩陣的第二行（狀態1），對狀態1來說，存在兩個可能的動作：到達狀態3，或者到達狀態5。通過隨機選擇，我們選擇到達狀態5。
現在，讓我們想象如果我們的智能體到達了狀態5，將會發生什么？觀察R矩陣的第六行，有3個可能的動作，到達狀態1,4或者5。
Q(state,?action)?=?R(state,?action)?+?Gamma?*?Max[Q(next?state,?all?actions)]
Q(1,?5)?=?R(1,?5)?+?0.8?*?Max[Q(5,?1),?Q(5,?4),?Q(5,?5)]?=?100?+?0.8?*?0?=?100
由于矩陣Q此時依然被初始化為0，Q(5,?1),?Q(5,?4),?Q(5,?5)全部是0，因此，Q(1,?5)的結果是100，因為即時獎勵R(1,5)等于100。
下一個狀態5現在變成了當前狀態，因為狀態5是目標狀態，因此我們已經完成了一次嘗試。我們的智能體的大腦中現在包含了一個更新后的Q矩陣。
對于下一次訓練，我們隨機選擇一個初始狀態，這一次，我們選擇狀態3作為我們的初始狀態。
觀察R矩陣的第4行，有3個可能的動作，到達狀態1,2和4。我們隨機選擇到達狀態1作為當前狀態的動作。
現在，我們想象我們在狀態1，觀察矩陣R的第2行，具有2個可能的動作：到達狀態3或者狀態5。現在我們計算Q值：
Q(state,?action)?=?R(state,?action)?+?Gamma?*?Max[Q(next?state,?all?actions)]
Q(3,?1)?=?R(3,?1)?+?0.8?*?Max[Q(1,?2),?Q(1,?5)]?=?0?+?0.8?*?Max(0,?100)?=?80
我們使用上一次嘗試中更新的矩陣Q得到：Q(1,?3)?=?0?以及?Q(1,?5)?=?100。因此，計算的結果是Q(3,1)=80，因為獎勵值為0。現在，矩陣Q變為：
下一個狀態1變成了當前狀態，我們重復Q學習算法中的內部循環過程，因為狀態1不是目標狀態。
因此，我們從當前狀態1開始一次新的循環，此時有2個可能的動作：到達狀態3或者狀態5。我們幸運地選擇到達了狀態5。
現在，想象我們處于狀態5，有3個可能的動作：到達狀態1,4或5。我們計算Q值如下：
Q(state,?action)?=?R(state,?action)?+?Gamma?*?Max[Q(next?state,?all?actions)]
Q(1,?5)?=?R(1,?5)?+?0.8?*?Max[Q(5,?1),?Q(5,?4),?Q(5,?5)]?=?100?+?0.8?*?0?=?100
更新后的矩陣Q中，Q(5,?1),?Q(5,?4),?Q(5,?5)依然是0，故Q(1,?5)的值是100，因為即時獎勵R(5,1)是100，這并沒有改變矩陣Q。
因為狀態5是目標狀態，我們完成了這次嘗試。我們的智能體大腦中包含的矩陣Q更新為如下所示：
如果我們的智能體通過多次的經歷學到了更多的知識，Q矩陣中的值會達到一收斂狀態，如下：
?
通過對Q中所有的非零值縮小一定的百分比，可以對其進行標準化，結果如下：
一旦矩陣Q接近于收斂狀態，我們就知道智能體已經學習到了到達目標狀態的最佳路徑。
例如，從初始狀態2，智能體在矩陣Q的指導下進行移動：
在狀態2時，由矩陣Q中最大的值可知下一個動作應該是到達狀態3；
在狀態3時，矩陣Q給出的建議是到達狀態1或者4，我們任意選擇，假設選擇了到達狀態1；
在狀態1時，矩陣Q建議到達狀態5；
因此，智能體的移動序列是2-3-1-5。
?
?
總結
以上是生活随笔為你收集整理的Q-学习，马克尔决策过程：强化学习的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： html之字符数字引用
- 下一篇： 1295 爱翻译