Q-Learning這一篇對應(yīng)Sutton書的第六章部分和UCL強化學習課程的第五講部分。

1. Q-Learning算法的引入

Q-Learning算法是一種使用時序差分求解強化學習控制問題的方法，回顧下此時我們的控制問題可以表示為：給定強化學習的5個要素：狀態(tài)集SS， 動作集AA， 即時獎勵RR，衰減因子γγ， 探索率??， 求解最優(yōu)的動作價值函數(shù)q?q?和最優(yōu)策略π?π?。

這一類強化學習的問題求解不需要環(huán)境的狀態(tài)轉(zhuǎn)化模型，是不基于模型的強化學習問題求解方法。對于它的控制問題求解，和蒙特卡羅法類似，都是價值迭代，即通過價值函數(shù)的更新，來更新策略，通過策略來產(chǎn)生新的狀態(tài)和即時獎勵，進而更新價值函數(shù)。一直進行下去，直到價值函數(shù)和策略都收斂。

再回顧下時序差分法的控制問題，可以分為兩類，一類是在線控制，即一直使用一個策略來更新價值函數(shù)和選擇新的動作，比如我們上一篇講到的SARSA， 而另一類是離線控制，會使用兩個控制策略，一個策略用于選擇新的動作，另一個策略用于更新價值函數(shù)。這一類的經(jīng)典算法就是Q-Learning。

對于Q-Learning，我們會使用????貪婪法來選擇新的動作，這部分和SARSA完全相同。但是對于價值函數(shù)的更新，Q-Learning使用的是貪婪法，而不是SARSA的????貪婪法。這一點就是SARSA和Q-Learning本質(zhì)的區(qū)別。

2. Q-Learning算法概述

Q-Learning算法的拓補圖入下圖所示：

首先我們基于狀態(tài)SS，用????貪婪法選擇到動作AA， 然后執(zhí)行動作AA，得到獎勵RR，并進入狀態(tài)S′S′，此時，如果是SARSA，會繼續(xù)基于狀態(tài)S′S′，用????貪婪法選擇A′A′，然后來更新價值函數(shù)。但是Q-Learning則不同。

對于Q-Learning，它基于狀態(tài)S′S′，沒有使用????貪婪法選擇A′A′，而是使用貪婪法選擇A′A′，也就是說，選擇使Q（S′，a）Q（S′，a）最大的aa作為A′A′來更新價值函數(shù)。用數(shù)學公式表示就是：

對應(yīng)到上圖中就是在圖下方的三個黑圓圈動作中選擇一個使Q（S′，a）Q（S′，a）最大的動作作為A′A′。

此時選擇的動作只會參與價值函數(shù)的更新，不會真正的執(zhí)行。價值函數(shù)更新后，新的執(zhí)行動作需要基于狀態(tài)S′S′，用????貪婪法重新選擇得到。這一點也和SARSA稍有不同。對于SARSA，價值函數(shù)更新使用的A′A′會作為下一階段開始時候的執(zhí)行動作。

下面我們對Q-Learning算法做一個總結(jié)。

3. Q-Learning算法流程

下面我們總結(jié)下Q-Learning算法的流程。

算法輸入：迭代輪數(shù)TT，狀態(tài)集SS， 動作集AA， 步長αα，衰減因子γγ， 探索率??，

輸出：所有的狀態(tài)和動作對應(yīng)的價值QQ1. 隨機初始化所有的狀態(tài)和動作對應(yīng)的價值QQ. 對于終止狀態(tài)其QQ值初始化為0.

2. for i from 1 to T，進行迭代。

a） 初始化S為當前狀態(tài)序列的第一個狀態(tài)。

b） 用????貪婪法在當前狀態(tài)SS選擇出動作AA
c） 在狀態(tài)SS執(zhí)行當前動作AA，得到新狀態(tài)S′S′和獎勵RR
d） 更新價值函數(shù)Q（S，A）Q（S，A）：

e） S=S′S=S′
f） 如果S′S′是終止狀態(tài)，當前輪迭代完畢，否則轉(zhuǎn)到步驟b）

4. Q-Learning算法實例：Windy GridWorld

我們還是使用和SARSA一樣的例子來研究Q-Learning。如果對windy gridworld的問題還不熟悉，可以復(fù)習強化學習（六）時序差分在線控制算法SARSA第4節(jié)的第二段。

完整的代碼參見我的github： https://github.com/ljpzzz/machinelearning/blob/master/reinforcement-learning/q_learning_windy_world.py

絕大部分代碼和SARSA是類似的。這里我們可以重點比較和SARSA不同的部分。區(qū)別都在episode這個函數(shù)里面。

首先是初始化的時候，我們只初始化狀態(tài)SS，把AA的產(chǎn)生放到了while循環(huán)里面， 而回憶下SARSA會同時初始化狀態(tài)SS和動作AA，再去執(zhí)行循環(huán)。下面這段Q-Learning的代碼對應(yīng)我們算法的第二步步驟a和b：

# play for an episode

def episode（q_value）：

# track the total time steps in this episode

time = 0

# initialize state

state = START

while state ！= GOAL：

# choose an action based on epsilon-greedy algorithm

if np.random.binomial（1， EPSILON） == 1：

action = np.random.choice（ACTIONS）

else：

values_ = q_value［state［0］， state［1］， ：］

action = np.random.choice（［action_ for action_， value_ in enumerate（values_） if value_ == np.max（values_）］）

接著我們會去執(zhí)行動作AA，得到S′S′， 由于獎勵不是終止就是-1，不需要單獨計算。，這部分和SARSA的代碼相同。對應(yīng)我們Q-Learning算法的第二步步驟c：

next_state = step（state， action）

def step（state， action）：

i， j = state

if action == ACTION_UP：

return ［max（i - 1 - WIND［j］， 0）， j］

elif action == ACTION_DOWN：

return ［max（min（i + 1 - WIND［j］， WORLD_HEIGHT - 1）， 0）， j］

elif action == ACTION_LEFT：

return ［max（i - WIND［j］， 0）， max（j - 1， 0）］

elif action == ACTION_RIGHT：

return ［max（i - WIND［j］， 0）， min（j + 1， WORLD_WIDTH - 1）］

else：

assert False

后面我們用貪婪法選擇出最大的Q（S′，a）Q（S′，a），并更新價值函數(shù)，最后更新當前狀態(tài)SS。對應(yīng)我們Q-Learning算法的第二步步驟d，e。注意SARSA這里是使用????貪婪法，而不是貪婪法。同時SARSA會同時更新狀態(tài)SS和動作AA，而Q-Learning只會更新當前狀態(tài)SS。

values_ = q_value［next_state［0］， next_state［1］， ：］

next_action = np.random.choice（［action_ for action_， value_ in enumerate（values_） if value_ == np.max（values_）］）

# Sarsa update

q_value［state［0］， state［1］， action］ += \

ALPHA * （REWARD + q_value［next_state［0］， next_state［1］， next_action］ -

q_value［state［0］， state［1］， action］）

state = next_state

跑完完整的代碼，大家可以很容易得到這個問題的最優(yōu)解，進而得到在每個格子里的最優(yōu)貪婪策略。

5. SARSA vs Q-Learning

現(xiàn)在SARSA和Q-Learning算法我們都講完了，那么作為時序差分控制算法的兩種經(jīng)典方法嗎，他們都有說明特點，各自適用于什么樣的場景呢？

Q-Learning直接學習的是最優(yōu)策略，而SARSA在學習最優(yōu)策略的同時還在做探索。這導(dǎo)致我們在學習最優(yōu)策略的時候，如果用SARSA，為了保證收斂，需要制定一個策略，使????貪婪法的超參數(shù)??在迭代的過程中逐漸變小。Q-Learning沒有這個煩惱。

另外一個就是Q-Learning直接學習最優(yōu)策略，但是最優(yōu)策略會依賴于訓(xùn)練中產(chǎn)生的一系列數(shù)據(jù)，所以受樣本數(shù)據(jù)的影響較大，因此受到訓(xùn)練數(shù)據(jù)方差的影響很大，甚至會影響Q函數(shù)的收斂。Q-Learning的深度強化學習版Deep Q-Learning也有這個問題。

在學習過程中，SARSA在收斂的過程中鼓勵探索，這樣學習過程會比較平滑，不至于過于激進，導(dǎo)致出現(xiàn)像Q-Learning可能遇到一些特殊的最優(yōu)“陷阱”。比如經(jīng)典的強化學習問題“Cliff Walk”。

在實際應(yīng)用中，如果我們是在模擬環(huán)境中訓(xùn)練強化學習模型，推薦使用Q-Learning，如果是在線生產(chǎn)環(huán)境中訓(xùn)練模型，則推薦使用SARSA。

6. Q-Learning結(jié)語

對于Q-Learning和SARSA這樣的時序差分算法，對于小型的強化學習問題是非常靈活有效的，但是在大數(shù)據(jù)時代，異常復(fù)雜的狀態(tài)和可選動作，使Q-Learning和SARSA要維護的Q表異常的大，甚至遠遠超出內(nèi)存，這限制了時序差分算法的應(yīng)用場景。在深度學習興起后，基于深度學習的強化學習開始占主導(dǎo)地位，因此從下一篇開始我們開始討論深度強化學習的建模思路。
編輯：hfy