強化學習入門——說到底研究的是如何學習

強化學習究竟研究的是一個什麼樣的問題，讓其具有實現通用人工智能的潛力？

引入統計學的思維，也就引入了不確定性，雖然如此，但是卻帶來了更合理的描述系統的方式和系統層面的確定性。

以上描述的這一模型，在強化學習的世界裏，我們稱作 Markov 決策過程，簡稱 MDP（Markov Decision Process）。這裏面的不確定性也就是 Markov 特性。

有了這個模型之後，我們就可以從數學上來研究這個問題了。強化學習研究的正是如何在這樣的一個數學模型的基礎上去實現一個有效的算法，進而實現智能決策。

一個小例子

綠色格子代表機器人可以移動到的位置
灰色格子表示有障礙物，機器人不能移動到那個位置
紅色格子表示一個陷阱，如果機器人移動到此，遊戲失敗
黃色格子代表一個出口，如果機器人移動到此，遊戲成功

這個遊戲中的 MDP，可以描述爲如下：

系統狀態：格子位置，機器人位置
機器人可執行的動作：向上下左右四個方向移動
狀態轉換概率：如果機器人向某個方向移動，它移動到對應方向的格子的概率假設爲 0.7（如果無法移動到對應方向的位置，則留在原格子的概率爲 0.7），移動到其他位置的概率爲 0.3/n，n 爲其他可轉換到的狀態的數量。

狀態轉換概率舉例如下（假設我們對格子進行編碼，編碼方式與 excel 表格的編碼方式一致，從 A1 到 E3）：

假設機器人在位置 A2，如果其向上移動，有 70% 的概率會移動到 A1，分別有 15% 的概率會移動到 A2（留在原位）和 A3
假設機器人在位置 A2，如果其向左或向右移動，有 70% 的的概率會留在原位 A2，分別有 15% 的概率會移動到 A1 和 A3

我們的算法要解決的問題是，在任意綠色格子裏面放置一個機器人，算法可以指導機器人一步一步到達位置 E1（成功完成遊戲）。

方案與算法

爲了實現一個智能算法解決上述機器人走格子問題，我們可以考慮給每個格子定義一個價值。這個價值表示到達這個格子後有多大可能性能成功完成遊戲。

觀察這個遊戲可以發現，D1 的價值應該高於 C1，C1 的價值應該高於 B1。

如果可以計算出每個格子的價值，我們是不是就解決了這個問題了呢？因爲，無論機器人處於哪個位置，它只需要往價值比當前格子更高的格子方向走即可。

現在問題轉化爲如何定義和計算這個價值。

我們先將目標數值化。由於到達出口格子即成功，如果機器人能到達此處，我們就給智能體反饋獎勵 1。同理，如果到達陷進格子，反饋獎勵 - 1，到達綠色格子則獎勵 0。

這個時候我們來看格子 D1。如果機器人在此處，它可以往四個方向移動。如果右移，有 70% 的概率可以到達出口，獲得獎勵 1。如果往其他三個方向走，則分別有 10% 的概率會到達出口，獲得獎勵 1。

經過以上的分析可以發現，我們其實可以將概率與獎勵相乘來代表某個移動方向的價值。得到如下的價值數值：

向右移動：0.7 * 1 = 0.7
向上 / 下 / 左移動：0.1 * 1 = 0.1

這裏的數值我們可以定義爲動作價值。有了這個動作價值，要計算某個格子的價值，我們其實可以直接用最大的動作價值來表示，即：max([0.7, 0.1, 0.1, 0.1]) = 0.7。

如果要計算格子 C1 的價值呢？這時，雖然達到格子 D1 的獎勵爲 0，但是我們可以利用剛計算好的 D1 的價值。還是按照前面的方式進行計算：

向右移動：0.7 * (0 + 0.7) = 0.49
向上 / 下 / 左移動：0.1 * (0 + 0.7) = 0.07
格子價值：max([0.49, 0.07, 0.07, 0.07]) = 0.49

到這裏，一個簡單的算法呼之欲出。我們只需要找到所有有獎勵的位置，然後從那裏開始去計算其他所有位置的獎勵，好像這個問題就解決了。

實際情況會稍微複雜一些。因爲我們可能有很多個位置都存在獎勵，而且這些獎勵的多少可能由於任務定義而不一樣。這裏更實際一些的算法是利用多次迭代來實現。

爲了不失一般性，我們可以定義公式：

（表示每個格子的價值，其中：s 表示當前狀態，a 表示動作）

一般而言，我們會引入一個額外的γ參數，對下一個狀態的價值打一定的折扣，這是因爲當前獲得的獎勵一般會優於下一個狀態的價值的，畢竟下一個狀態的價值只是一個估計值。這時，上述第一個公式變爲：

於是，我們的算法就可以描述爲：* 對每一個狀態，初始化 V := 0 * 循環，直到 V 收斂：* 對每一個狀態，

這裏爲判斷 V 是否收斂，我們可以檢查當前這次迭代是否會更新 V 的值。用 javascript 代碼實現，主要代碼如下：

上述算法就是強化學習裏面的經典算法價值迭代算法了。而我們上面定義 V 的迭代形式的公式就是著名的 Bellman 公式了，其最初由 Richard Bellman 提出。

另一個思路

上述算法存在一個問題，我們最後得到的是一系列狀態價值（每個格子的價值），爲了得到我們想要的行動，我們還需要根據根據狀態價值，計算行動價值，即上述 Q(s, a)。使用上有所不便。

那麼有沒有辦法改進呢？再來思考一下這個問題的目標，實際上我們想要找到一種指導機器人行動的策略。這裏的策略可以表示爲：在任意一個位置，算法可以給出一個恰當的行動。

我們能不能直接去衡量某一個策略的價值呢？因爲一旦有了這個策略的價值，我們就可以考慮直接去優化這個策略，而不是去對所有的狀態計算價值。

對於某一策略，由於其可以基於當前狀態指導我們作出行動，我們可以定義它爲一個 輸入爲狀態輸出爲行動 的函數，即π: a = π(s)

既然這樣，參考價值迭代算法中的狀態價值（格子價值）定義，我們可以定義策略價值函數爲：

（策略π的價值，其中：s 表示當前狀態；a = π(s) 表示動作；s'表示下一個狀態；T(s, π(s), s') 表示在狀態 s，執行動作 a=π(s) 轉換到狀態 s'的概率；R(s, π(s), s') 表示在狀態 s，執行動作 a=π(s) 轉換到狀態 s'得到的獎勵）

上面的公式是一個迭代形式的定義，既然如此，我們可以參考之前的狀態價值迭代算法，迭代計算這個策略的價值，最後這個價值可能會收斂到某個具體的值。

然而就算可以計算策略的價值，我們如何得到一個有效的策略呢？如果沒有策略，其實也無從計算其價值。

能不能隨機初始化一個策略？在這基礎上計算其價值，進而得到更好的策略。

對於以上解決問題的思路，我第一次看到的時候，也不禁暗暗讚歎。事實上，這就是我這裏想要給大家介紹的另一個強化學習經典算法：策略迭代 算法。

如何根據一個策略尋找更優策略？可以這樣做：

計算在當前策略下，哪一個行動能得到最大價值
選擇價值最大的行動作爲新策略的行動

用公式表述如下：

（下一個（第 i+1 個）更優策略π(i+1)，其中：s 表示當前狀態；a = π(s) 表示動作；s'表示下一個狀態；T(s, a, s') 表示在狀態 s，執行動作 a 轉換到狀態 s'的概率；R(s, a, s') 表示在狀態 s，執行動作 a 轉換到狀態 s'得到的獎勵）

到這裏，這個 策略迭代 算法就差不多完成了。用 JavaScript 代碼實現，主要代碼如下：

 1MDPPISolver.solve = function () {
 2  var policy = this.randomPolicy();
 3  var policyNew = policy;
 4  do {
 5    policy = policyNew;
 6    values = this.solveForPolicy(policy);
 7    policyNew = this.improvePolicy(values, policy);
 8  } while (!this.converged(policy, policyNew));
 9  ...
10}
11

完整代碼見這裏（https://github.com/gmlove/gmlove.github.io/blob/source/source/examples/mdp/grid-world.js）932 行到 1024 行。

擴展

狀態空間降維

雖然我們可以用上述兩個經典算法解決這個問題，但是它們的效率是很低的，算法複雜度用大 O 計算法可以表示爲 O(a_s_s)。對於這個非常簡單的問題，計算速度尚能接受，但是如果我們考慮一些更復雜的問題，就會發現這裏的狀態 s 的取值空間可能會非常大。

比如對於下面這個喫豆子的遊戲，這裏的狀態數量爲：

狀態數量 = 格子數量 * N (N 爲每個格子的可能狀態：比如是否有喫豆人、是否有豆子、是否有敵人及敵人的類型等等)

過大的狀態空間就導致上述經典算法實際無法執行，也就無法滿足實際需求。

一個可能的優化手段是人爲的設計一些特徵來表示某個狀態 s，這樣就實現了對 s 進行降維的操作。比如對於上面喫豆子的遊戲，我們可以建模這樣幾個特徵：

離最近的豆子的方向和距離
離每個敵人的方向和距離
敵人的移動速度和方向

有了這樣的很小的狀態空間，上述算法就可以執行了。

深度強化學習 DQN

有了上述狀態空間降維的辦法，我們可以考慮是不是可以用一個深度神經網絡來替代人工特徵的過程呢？當然是可以的，這就是前幾年 Deep Mind 轟動學界和產業界的關於 深度強化學習 的論文中的內容了。

DQN 的全稱是 Deep Q-Network，它的核心是一個 Q 值迭代的算法。Q 值迭代公式就是我們 價值迭代 公式中的關於行動價值的公式的一個迭代形式。算法也是不斷迭代直到收斂。

我在另一篇文章中有關於 DQN 的更多內容。詳情見這裏（http://brightliao.com/2016/12/05/let-machine-play-games/）。

狀態空間降維

深度強化學習 DQN

更多的問題

猜你喜歡