本文將帶你學習經典強化學習算法 Q-learning 的相關知識。在這篇文章中，你將學到：（1）Q-learning 的概念解釋和算法詳解；（2）通過 Numpy 實現 Q-learning。
故事案例：騎士和公主
假設你是一名騎士，並且你需要拯救上面的地圖裡被困在城堡中的公主。
你每次可以移動一個方塊的距離。敵人是不能移動的，但是如果你和敵人落在了同一個方塊中，你就會死。你的目標是以儘可能快的路線走到城堡去。這可以使用一個「按步積分」系統來評估。
你在每一步都會失去 1 分（每一步失去的分數幫助智能體訓練的更快）
如果碰到了一個敵人，你會失去 100 分，並且訓練 episode 結束。
如果進入到城堡中，你就獲勝了，獲得 100 分。
那麼問題來了：如何才能夠創建這樣的智能體呢？
下面我將介紹第一個策略。假設智能體試圖走遍每一個方塊，並且將其著色。綠色代表「安全」，紅色代表「不安全」。
同樣的地圖，但是被著色了，用於顯示哪些方塊是可以被安全訪問的。
接著，我們告訴智能體只能選擇綠色的方塊。
但問題是，這種策略並不是十分有用。當綠色的方塊彼此相鄰時，我們不知道選擇哪個方塊是最好的。所以，智能體可能會在尋找城堡的過程中陷入無限的循環。
Q-Table 簡介
下面我將介紹第二種策略：創建一個表格。通過它，我們可以為每一個狀態（state）上進行的每一個動作（action）計算出最大的未來獎勵（reward）的期望。
得益於這個表格，我們可以知道為每一個狀態採取的最佳動作。
每個狀態（方塊）允許四種可能的操作：左移、右移、上移、下移。
「0」代表不可能的移動（如果你在左上角，你不可能向左移動或者向上移動！）
在計算過程中，我們可以將這個網格轉換成一個表。
這種表格被稱為 Q-table（「Q」代表動作的「質量」）。每一列將代表四個操作（左、右、上、下），行代表狀態。每個單元格的值代表給定狀態和相應動作的最大未來獎勵期望。
每個 Q-table 的分數將代表在給定最佳策略的狀態下采取相應動作獲得的最大未來獎勵期望。
為什麼我們說「給定的策略」呢？這是因為我們並不實現這些策略。相反，我們只需要改進 Q-table 就可以一直選擇最佳的動作。
將這個 Q-table 想象成一個「備忘紙條」遊戲。得益於此，我們通過尋找每一行中最高的分數，可以知道對於每一個狀態（Q-table 中的每一行）來說，可採取的最佳動作是什麼。
太棒了！我解決了這個城堡問題！但是，請等一下... 我們如何計算 Q-table 中每個元素的值呢？
為了學習到 Q-table 中的每個值，我們將使用 Q-learning 算法。
Q-learning 算法：學習動作值函數（action value function）
動作值函數（或稱「Q 函數」）有兩個輸入：「狀態」和「動作」。它將返回在該狀態下執行該動作的未來獎勵期望。
我們可以把 Q 函數視為一個在 Q-table 上滾動的讀取器，用於尋找與當前狀態關聯的行以及與動作關聯的列。它會從相匹配的單元格中返回 Q 值。這就是未來獎勵的期望。
在我們探索環境（environment）之前，Q-table 會給出相同的任意的設定值（大多數情況下是 0）。隨著對環境的持續探索，這個 Q-table 會通過迭代地使用 Bellman 方程（動態規劃方程）更新 Q(s,a) 來給出越來越好的近似。
Q-learning 算法流程
Q-learning 算法的偽代碼
步驟 1：初始化 Q 值。我們構造了一個 m 列（m = 動作數 )，n 行（n = 狀態數）的 Q-table，並將其中的值初始化為 0。
步驟 2：在整個生命週期中（或者直到訓練被中止前），步驟 3 到步驟 5 會一直被重複，直到達到了最大的訓練次數（由用戶指定）或者手動中止訓練。
步驟 3：選取一個動作。在基於當前的 Q 值估計得出的狀態 s 下選擇一個動作 a。
但是……如果每個 Q 值都等於零，我們一開始該選擇什麼動作呢？在這裡，我們就可以看到探索/利用（exploration/exploitation）的權衡有多重要了。
思路就是，在一開始，我們將使用 epsilon 貪婪策略：
我們指定一個探索速率「epsilon」，一開始將它設定為 1。這個就是我們將隨機採用的步長。在一開始，這個速率應該處於最大值，因為我們不知道 Q-table 中任何的值。這意味著，我們需要通過隨機選擇動作進行大量的探索。
生成一個隨機數。如果這個數大於 epsilon，那麼我們將會進行「利用」（這意味著我們在每一步利用已經知道的信息選擇動作）。否則，我們將繼續進行探索。
在剛開始訓練 Q 函數時，我們必須有一個大的 epsilon。隨著智能體對估算出的 Q 值更有把握，我們將逐漸減小 epsilon。
步驟 4-5：評價！採用動作 a 並且觀察輸出的狀態 s' 和獎勵 r。現在我們更新函數 Q（s，a）。
我們採用在步驟 3 中選擇的動作 a，然後執行這個動作會返回一個新的狀態 s' 和獎勵 r。
接著我們使用 Bellman 方程去更新 Q（s，a）：
如下方代碼所示，更新 Q（state，action）：
New Q value = Current Q value + lr * [Reward + discount_rate * (highest Q value between possible actions from the new state s’ ) — Current Q value ]
讓我們舉個例子：
一塊奶酪 = +1
兩塊奶酪 = +2
一大堆奶酪 = +10（訓練結束）
吃到了鼠藥 = -10（訓練結束）
步驟 1：初始化 Q-table
初始化之後的 Q-table
步驟 2：選擇一個動作。從起始點，你可以在向右走和向下走其中選擇一個。由於有一個大的 epsilon 速率（因為我們至今對於環境一無所知），我們隨機地選擇一個。例如向右走。
我們隨機移動（例如向右走）
我們發現了一塊奶酪（+1），現在我們可以更新開始時的 Q 值並且向右走，通過 Bellman 方程實現。
步驟 4-5：更新 Q 函數
首先，我們計算 Q 值的改變量 ΔQ(start, right)。
接著我們將初始的 Q 值與 ΔQ(start, right) 和學習率的積相加。
可以將學習率看作是網絡有多快地拋棄舊值、生成新值的度量。如果學習率是 1，新的估計值會成為新的 Q 值，並完全拋棄舊值。
更新後的 Q-table
太好了！我們剛剛更新了第一個 Q 值。現在我們要做的就是一次又一次地做這個工作直到學習結束。
實現 Q-learning 算法
既然我們知道了它是如何工作的，我們將一步步地實現 Q-learning 算法。代碼的每一部分都在下面的 Jupyter notebook 中直接被解釋了。
你可以在我的深度強化學習課程 repo 中獲得代碼。
項目地址：https://github.com/simoninithomas/Deep_reinforcement_learning_Course/blob/master/Q%20learning/Q%20Learning%20with%20FrozenLake.ipynb
回顧
Q-learning 是一個基於值的強化學習算法，利用 Q 函數尋找最優的「動作—選擇」策略。
它根據動作值函數評估應該選擇哪個動作，這個函數決定了處於某一個特定狀態以及在該狀態下采取特定動作的獎勵期望值。
目的：最大化 Q 函數的值（給定一個狀態和動作時的未來獎勵期望）。
Q-table 幫助我們找到對於每個狀態來說的最佳動作。
通過選擇所有可能的動作中最佳的一個來最大化期望獎勵。
Q 作為某一特定狀態下采取某一特定動作的質量的度量。
函數 Q（state，action）→返回在當前狀態下采取該動作的未來獎勵期望。
這個函數可以通過 Q-learning 算法來估計，使用 Bellman 方程迭代地更新 Q（s，a）
在我們探索環境之前：Q-table 給出相同的任意的設定值→ 但是隨著對環境的持續探索→Q 給出越來越好的近似。
就是這些了！不要忘記自己去實現代碼的每一部分——試著修改已有的代碼是十分重要的。
試著增加迭代次數，改變學習率，並且使用一個更復雜的環境（例如：8*8 方格的 Frozen-lake）。祝你玩的開心！
原文鏈接：http://mp.weixin.qq.com/s/34E1tEQMZuaxvZA66_HRwA
閱讀更多 燈塔大數據 的文章
