Q-learning 是一個經(jīng)典的強化學(xué)習算法。
為了便于描述，這里依然定義一個“世界”：
令空白格子的獎勵為1.
Q-Table
Q-table 是 Q-learning 的核心。它是一個表格，記錄了每個狀態(tài)下采取不同動作，所獲取的最大長期獎勵期望。通過此，就可以知道每一步的最佳動作是什么。
Q-table 的每一列代表一個動作，每一行表示一個狀態(tài)。則每個格子的值就是此狀態(tài)下采取此動作獲得的最大長期獎勵期望。例如：
| U↑ | D↓ | L← | R→ | |
|---|---|---|---|---|
| START | ? | 0 | 0 | ? |
| (2,1) | 0 | 0 | ? | ? |
| (1,2) | ? | ? | 0 | 0 |
| … | … | … | … | … |
上表表示，對于狀態(tài) STRAT 向下或左的獎勵期望是0（因為無法移動），其余兩個方向由于未探索，所以獎勵未知。狀態(tài)(2,1)和狀態(tài)(1,2)同理。
如果能求出整個表的所有值，那么這個問題就解決了。為了做到這一點，需要使用 Q-learning 算法。
Q-learning 算法
算法流程可以表述為：
- 初始化 Q-table.
- 選擇一個動作 A.
- 執(zhí)行動作 A.
- 獲得獎勵。
- 更新 Q. 并循環(huán)執(zhí)行步驟2.
在這個流程中有兩個地方需要注意。
如何選取動作
在一開始，表格中值都為0，自然地我們會想到隨機選取一個動作。但隨著迭代的進行，若一直隨機選擇，就相當于沒有利用已經(jīng)學(xué)習到的東西。為了解決這個問題，可能會想到除第一次外，均采取當前Q值最大的動作。但這樣又可能陷入局部最優(yōu)解，因為可能還有更好的動作沒有被發(fā)現(xiàn)。
這其實是如何平衡「探索」與「利用」的問題。
于是可以采用一種叫做 ε-greedy 的策略。
ε-greedy 策略的本質(zhì)就是：每次有ε概率進行探索，有(1-ε)的概率利用已學(xué)習的數(shù)據(jù)。探索意味著隨機選取一個動作，利用意味著采取當前Q值最高的動作。
除了 ε-greedy ，還有一些效果更好的方法，但是復(fù)雜很多。
一開始往往設(shè)定一個較高的 ε（比如1），因為我們對環(huán)境一無所知，只能隨機選擇。隨著迭代，可以逐步降低 ε，因為我們已經(jīng)越來越準確地了解了環(huán)境。如下圖所示：
如何更新 Q
這就是更新 Q 的函數(shù)，其中 α 為學(xué)習速率。顯然，α 越大，保留之前學(xué)習的結(jié)果越少。
