Q-Learning這一篇對(duì)應(yīng)Sutton書(shū)的第六章部分和UCL強(qiáng)化學(xué)習(xí)課程的第五講部分。

1. Q-Learning算法的引入

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

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

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

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

2. Q-Learning算法概述

Q-Learning算法的拓補(bǔ)圖入下圖所示：

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

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

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

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

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

3. Q-Learning算法流程

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

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

輸出：所有的狀態(tài)和動(dòng)作對(duì)應(yīng)的價(jià)值QQ1. 隨機(jī)初始化所有的狀態(tài)和動(dòng)作對(duì)應(yīng)的價(jià)值QQ. 對(duì)于終止?fàn)顟B(tài)其QQ值初始化為0.

2. for i from 1 to T，進(jìn)行迭代。

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

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

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

4. Q-Learning算法實(shí)例：Windy GridWorld

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

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

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

首先是初始化的時(shí)候，我們只初始化狀態(tài)SS，把AA的產(chǎn)生放到了while循環(huán)里面， 而回憶下SARSA會(huì)同時(shí)初始化狀態(tài)SS和動(dòng)作AA，再去執(zhí)行循環(huán)。下面這段Q-Learning的代碼對(duì)應(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_）］）

接著我們會(huì)去執(zhí)行動(dòng)作AA，得到S′S′， 由于獎(jiǎng)勵(lì)不是終止就是-1，不需要單獨(dú)計(jì)算。，這部分和SARSA的代碼相同。對(duì)應(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），并更新價(jià)值函數(shù)，最后更新當(dāng)前狀態(tài)SS。對(duì)應(yīng)我們Q-Learning算法的第二步步驟d，e。注意SARSA這里是使用????貪婪法，而不是貪婪法。同時(shí)SARSA會(huì)同時(shí)更新?tīng)顟B(tài)SS和動(dòng)作AA，而Q-Learning只會(huì)更新當(dāng)前狀態(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

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

5. SARSA vs Q-Learning

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

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

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

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

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

6. Q-Learning結(jié)語(yǔ)

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