欒詠紅 章鵬

摘 要： 強化學習是指從環(huán)境狀態(tài)到行為映射的學習，使智能體從環(huán)境交互中獲得的累積獎賞最大化。文章在介紹強化學習原理和方法的基礎(chǔ)上，對動態(tài)規(guī)劃、蒙特卡羅算法和時間差分算法進行了分析，并以柵格問題為仿真實驗平臺進行算法驗證，分析比較了蒙特卡羅算法與時間差分算法學習速率的收斂性，以及學習率對時間差分算法的影響。實驗結(jié)果表明，時間差分算法收斂速度比蒙特卡羅算法快一些；學習率選取較大時，時間差分算法收斂速度會快一些。

關(guān)鍵詞： 強化學習； 動態(tài)規(guī)劃； 蒙特卡羅方法； 時間差分方法； 值函數(shù)

中圖分類號：TP18 文獻標志碼：A 文章編號：1006-8228（2015）12-93-05

Comparative analysis of reinforcement learning method

Luan Yonghong1，2， Zhang Peng2

（1. Suzhou Institute of Industrial Technology， Suzhou， Jiangsu 215104， China； 2. Institute of Computer Science and Technology， Soochow University）

Abstract： Reinforcement learning is the learning from environment state mapping to action， to maximize the accumulated reward from the interaction with the environment. On the basis of the introduction of principles and methods of reinforcement learning， the dynamic programming， Monte Carlo algorithm and temporal-difference algorithm are analyzed， and the gridworld problem is used as the experiment platform to verify these algorithms. The convergence comparison between Monte Carlo algorithm and temporal-difference algorithm and the effect of the learning rate on the temporal-difference algorithm is analyzed. The analysis of the experiment result shows that temporal-difference algorithm is found to converge faster than Monte Carlo algorithm. The increase of learning rate improves the convergence rate of temporal-difference algorithm.

Key words： reinforcement learning； dynamic programming； Monte Carlo methods； temporal-difference method； value function

0 引言

強化學習（reinforcement learning：RL）又稱為增強學習或再勵學習，是一種從環(huán)境空間狀態(tài)到動作空間映射的學習，通過試錯法不斷與環(huán)境交互，期望動作從中獲得的累積獎賞值最大[1，7，8]，它是以環(huán)境反饋作為輸入的機器學習方法，也是近年來自動控制和人工智能領(lǐng)域的研究熱點之一。

1 強化學習理論

1.1 強化學習基本原理

強化學習是基于動物學習心理學的“試錯法”原理，智能體在與環(huán)境交互的過程中根據(jù)評價性反饋信號實現(xiàn)從環(huán)境狀態(tài)到動作狀態(tài)的學習，使得行為策略能夠從環(huán)境中得到最大的累積獎賞值，最終收斂到最優(yōu)策略，實現(xiàn)馬爾科夫決策過程的優(yōu)化，解決了優(yōu)化控制問題[2，6，7，8]。

在強化學習過程中，智能體的任務就是學習獲得一個最優(yōu)控制策略π*：S→A（其中S狀態(tài)集，A為動作集）。也就是找到一個從狀態(tài)到動作的映射，以得到最大化期望獎賞值的總和。強化學習框架模型如圖1所示。

在策略π*：S→A指導下，智能體與外界環(huán)境不斷進行試探交互，根據(jù)策略智能體選擇動作a作用于環(huán)境，該環(huán)境接受動作后產(chǎn)生一個強化信號r反饋給智能體，然后智能體再根據(jù)強化信號正負和當前狀態(tài)的策略選擇下一個動作。如果智能體與外界環(huán)境交互接受的強化信號為正，則為獎賞信號。這個獎賞信號通常是一個標量，它反映了某一時刻動作所作出的即時評價，也就是立即獎賞。由于選擇的動作不僅影響立即獎賞值，而且還影響智能體遷移到的下一狀態(tài)以及最終獎賞回報。因此，智能體選取動作時，其原則是要能夠獲得環(huán)境最大的獎賞。

[Agent][環(huán)境] [獎賞r][狀態(tài)s] [動作a]

圖1 強化學習模型

定義1 在t時刻，從任意初始狀態(tài)st起按照任一策略π選擇動作，從環(huán)境中獲得的累積值稱為累積回報，用Vπ（st）表示。則狀態(tài)值函數(shù)Vπ（st）定義形式[7]如式⑴。

⑴

式⑴為無限水平折扣模型，智能體僅僅考慮未來獲得的期望回報，并以某種形式的折扣累積在值函數(shù)中，其中rt是智能體從st到st+1所獲得的立即回報，γ稱為折扣因子，是用來確定長期回報和立即回報的相對比例，反映了學習系統(tǒng)對未來回報的重視度。γ取值越小，表示越重視短期回報，當γ取值為0時，表示只看重下一時刻的回報；當γ取值越大，表示重視長期回報，當γ取值為1時，表示對未來的所有回報是同等對待的。

策略的優(yōu)劣是通過狀態(tài)值函數(shù)進行判斷的，故最優(yōu)狀態(tài)值函數(shù)對應的就是最優(yōu)策略。由方程最優(yōu)性原理知最優(yōu)狀態(tài)值函數(shù)為

⑵

所求得的最優(yōu)策略可以表示為

⑶

1.2 馬爾科夫決策過程

通常假定環(huán)境是馬爾科夫型的，將滿足馬爾可夫性質(zhì)的強化學習任務稱為馬爾可夫決策過程[1，3，4，7]（Markov Decision Process，MDP）。強化學習的研究主要集中于馬爾科夫問題的處理。

定義2 （馬爾可夫決策過程MDP）設(shè)存在一個四元組，其中S表示離散狀態(tài)集，A表示動作集，狀態(tài)轉(zhuǎn)移函數(shù)T：S×A→Pr（s），獎賞函數(shù)R：S×A→R。記R（s，a，s'）為智能體在狀態(tài)s采用a動作使環(huán)境狀態(tài)轉(zhuǎn)移到s'獲得的立即獎賞值；記T（s，a，s'）為智能體在狀態(tài)s采用a動作使環(huán)境狀態(tài)轉(zhuǎn)移到s'的概率。

MDP本質(zhì)[1，5，7，8]是：當前狀態(tài)向下一狀態(tài)遷移的概率和所獲得的獎賞值僅僅取決于當前狀態(tài)和選擇的動作，而與歷史狀態(tài)和歷史動作無關(guān)。因此在已知狀態(tài)轉(zhuǎn)移概率函數(shù)T和獎賞函數(shù)R的環(huán)境模型下，一般采用動態(tài)規(guī)劃技術(shù)求解最優(yōu)策略。而強化學習著重研究在T函數(shù)和R函數(shù)未知的情況下，智能體如何獲得最優(yōu)動作策略。這就需要智能體通過試探，從環(huán)境中獲得立即回報從而學習狀態(tài)值函數(shù)。在試探過程中，智能體為了獲得環(huán)境的立即回報，必須采取一定的動作來改變當前的環(huán)境狀態(tài)。

強化學習系統(tǒng)中常用動作選擇機制有ε-greedy貪婪機制和Boltzmann分布機制。ε-greedy動作選擇機制是優(yōu)先按概率1-ε（0?ε<1）選擇使動作值最大的動作，當該動作未被選中時，則以概率ε選擇動作集A中其他動作執(zhí)行。Boltzmann分布動作選擇機制，是按照每個動作值的大小來給該動作賦予一個選擇概率。

2 強化學習的基本方法

解決強化學習問題的基本方法有動態(tài)規(guī)劃方法、蒙特卡羅方法和時間差分學習方法。這些方法都能很好的解決強化學習中存在的一系列問題。但是近年來對強化學習算法的研究已由算法本身逐漸轉(zhuǎn)向研究經(jīng)典算法在各種復雜環(huán)境中的應用，如Q學習算法，Sarsa算法，Dyan算法等。

2.1 動態(tài)規(guī)劃

動態(tài)規(guī)劃（Dynamic Programming，DP）是由Bellman于1957年提出，并證明了動態(tài)規(guī)劃方法可以用來解決很廣泛的問題。動態(tài)規(guī)劃其主要思想是利用狀態(tài)值函數(shù)搜索好的策略，在文獻[1]中都證明了動態(tài)規(guī)劃方法就是利用值函數(shù)來搜索好的策略。

動態(tài)規(guī)劃方法是由Bellman方程轉(zhuǎn)化而來，通過修正Bellman方程的規(guī)則，提高所期望值函數(shù)的近似值。常用算法有兩種：值迭代（Value Iteration）和策略迭代（Policy Iteration）。

假設(shè)環(huán)境是一個有限馬爾可夫集，對任意策略π，如果環(huán)境的動態(tài)信息已知，即策略π、T函數(shù)和R函數(shù)已知，可以用值迭代法來近似求解。則狀態(tài)值函數(shù)更新規(guī)則如式⑷。

⑷

在任意策略π下的任意狀態(tài)值函數(shù)V滿足Bellman方程的式⑴與式⑷兩種形式。值迭代算法就是將Bellman方程轉(zhuǎn)換成更新規(guī)則，利用Bellman方程求解MDP中所有狀態(tài)值函數(shù)。則狀態(tài)值函數(shù)V'（s）滿足Bellman最優(yōu)方程，表示為：

⑸

由于值迭代算法直接用可能轉(zhuǎn)到的下一步s'的V（s'）來更新當前的V（s），所以算法不需要存儲策略π。值迭代是在保證算法收斂的情況下，縮短策略估計的過程，每次迭代只掃描（sweep）了每個狀態(tài)一次。而策略迭代算法包含了一個策略估計的過程，而策略估計則需要掃描（sweep）所有的狀態(tài)若干次，其中巨大的計算量直接影響了策略迭代算法的效率。所以說，不管采用動態(tài)規(guī)劃中的哪種算法方法都要用到兩個步驟：策略估計和策略改進。

動態(tài)規(guī)劃方法通過反復掃描整個狀態(tài)空間，對每個狀態(tài)產(chǎn)生可能遷移的分布，然后利用每個狀態(tài)的遷移分布，計算出更新值，并更新該狀態(tài)的估計值，所以計算量需求會隨狀態(tài)變量數(shù)目增加而呈指數(shù)級增長，從而造成“維數(shù)災”問題[4，7.8]。

2.2 蒙特卡羅方法

蒙特卡羅方法（Monte Carlo methods：MC）是一種模型無關(guān)（model free）的，解決基于平均樣本回報的強化學習問題的學習方法[7-8]。它用于情節(jié)式任務（episode task），不需要知道環(huán)境狀態(tài)轉(zhuǎn)移概率函數(shù)T和獎賞函數(shù)R，只需要智能體與環(huán)境從模擬交互過程中獲得的狀態(tài)、動作、獎賞的樣本數(shù)據(jù)序列，由此找出最優(yōu)策略。MC方法具有一個很重要的優(yōu)點就是該方法對環(huán)境是否符合馬爾可夫?qū)傩砸蟛桓摺?/p>

假定存在終止狀態(tài)，任何策略都以概率1到達終止狀態(tài)，而且是在有限時間步內(nèi)到達目標。MC方法通過與環(huán)境交互過程中來評估值函數(shù)的，從而發(fā)現(xiàn)最優(yōu)（較優(yōu)）策略的。MC方法總是通過平均化采樣回報來解決強化學習問題。正是由于MC方法的這個特點，要求要解決的問題必須是可以分解成情節(jié)（episode）。而MC算法的狀態(tài)值函數(shù)更新規(guī)則為：

⑹

其中Rt為t時刻的獎賞值，α為步長參數(shù)（0<α<1）。MC算法只有在每個學習情節(jié)到達終止狀態(tài)并獲得回報值時才能更新當前狀態(tài)的值函數(shù)。所以相對那些學習情節(jié)中包含較多步數(shù)的任務，對比TD算法，MC算法的學習速度就非常慢。這也是MC算法的一個主要缺點。

2.3 時間差分學習方法

時間差分（Temporal-Difference，TD）學習方法是一種模型無關(guān)的算法，它是蒙特卡羅思想和動態(tài)規(guī)劃思想的結(jié)合，一方面可以直接從智能體的經(jīng)驗中學習，建立環(huán)境的動態(tài)信息模型，不必等到最終輸出結(jié)果產(chǎn)生之后，再修改歷史經(jīng)驗，而是在學習過程中不斷逐步修改。正因為這個特點使得TD方法處理離散序列有很大的優(yōu)勢[1，4，6，7]。另一方面TD方法和動態(tài)規(guī)劃一樣，可以用估計的值函數(shù)進行迭代。

最簡單的TD方法為TD（0）算法，這是一種自適應的策略迭代算法。文獻[1]指出TD（0）算法是由Sutton在1988年提出的，并且證明了當系統(tǒng)滿足馬爾科夫?qū)傩?，α絕對遞減條件下，TD算法必然收斂。TD（0）算法是指智能體獲得立即回報值僅向后退一步，也就是說迭代僅僅修改了相鄰狀態(tài)的估計值，則TD（0）算法的值函數(shù)更新規(guī)則為：

⑺

其中α稱為學習因子或?qū)W習率（也稱為步長參數(shù)，0<α<1），γ稱為折扣因子（0?γ?1）。由于TD（0）算法利用智能體獲得即時回報值，修改相鄰狀態(tài)值函數(shù)估計值，因此會出現(xiàn)收斂速度慢的情況。Singh等人對TD（0）算法進行改進，將智能體獲得的立即獎賞值由僅回退一步擴展到可以回退任意步，形成了TD（λ）算法。

TD（λ）算法比TD（0）算法具有更好的泛化性能，0?λ?1是資格跡的衰減系數(shù)。TD（λ）算法是一個經(jīng)典的函數(shù)估計方法，每一個時間步的計算復雜度為Q（n），其中n為狀態(tài)特征的個數(shù)。當學習因子α或者資格跟蹤參數(shù)λ選得不合適時，TD（λ）甚至會發(fā)散的。

3 基于柵格問題仿真實驗

3.1 柵格模型

柵格問題是一類經(jīng)典的人工智能問題，常被用來驗證強化學習算法的有效性。一般用二維網(wǎng)格世界來描述，每個網(wǎng)格代表智能體的一種狀態(tài)。S表示開始狀態(tài)，G表示終止狀態(tài)。智能體的任務是從起始點出發(fā)，尋找一條最優(yōu)的路徑，到達終點處。智能體在任意狀態(tài)下能執(zhí)行的動作有向上、向下，向左和向右。如果移動后的狀態(tài)是邊界，智能體狀態(tài)保持不變，否則執(zhí)行動作后智能體將遷移到相應的鄰近狀態(tài)。智能體到達目標狀態(tài)前的每一步狀態(tài)遷移的立即獎賞均為r=0，遷移到目標狀態(tài)G的立即獎賞r=1。

實驗主要關(guān)注狀態(tài)空間維度分別為5×5和20×20兩種情況，含三個方面的內(nèi)容：①智能體通過學習獲得的最短路徑軌跡；②在相同的學習因子，智能體在MC算法與TD算法下學習過程的收斂情況；③若學習率α的取值不同，TD算法值函數(shù)估計誤差的比較以及算法的收斂情況。

本文實驗選用ε-greedy貪婪機制選取動作，設(shè)置ε=0.1，選取動作時選擇最大動作值對應的動作概率為1-ε=0.9，選擇其他動作概率為ε=0.1。折扣因子γ（0?γ?1）反映了學習系統(tǒng)對未來回報的重視度。實驗中學習算法的參數(shù)設(shè)置為：探索因子ε=0.1，折扣因子γ=0.9，學習率α=0.1。

[＼&＼&＼&＼&＼&＼&＼&＼&G＼&＼&＼&＼&＼&＼&＼&＼&＼&＼&＼&＼&S＼&＼&＼&＼&＼&]

圖2 柵格問題示意圖

3.2 實驗結(jié)果與算法收斂分析

在MDP環(huán)境模型已知的情況下，使用動態(tài)規(guī)劃的值迭代算法更新求解最優(yōu)策略。根據(jù)已知模型先驗知識進行初始化，實驗時采用貪心策略的狀態(tài)值函數(shù)估計，根據(jù)式⑺動態(tài)規(guī)劃值迭代更新規(guī)則計算值函數(shù)，每一次迭代過程中更新所有狀態(tài)的值，在值迭代過程中不斷逼近最優(yōu)值，當所有狀態(tài)的值函數(shù)的更新誤差Δ小于設(shè)定的閾值ε=0.005時，值迭代算法收斂。

在MDP環(huán)境模型不確定的情況下，智能體成功地從起點尋找到終點的過程，稱之為一個情節(jié)（episode），當智能體到達終點后，重新回到起始點進行下一個情節(jié)的學習。圖3與圖4分別表示了MC算法與TD算法在不同狀態(tài)空間維度的上迷宮的實驗結(jié)果比較。橫坐標表示情節(jié)數(shù)，縱坐標為每個情節(jié)對應的步數(shù)。

圖3與圖4分別給出了MC算法與TD算法應用于不同狀態(tài)空間維度的柵格上取得的實驗數(shù)據(jù)。實驗結(jié)果顯示，TD學習算法得到最終策略結(jié)果比MC學習算法要好。

如圖3所示，設(shè)狀態(tài)空間維度為5×5的模型，從實驗結(jié)果可以看出MC算法大約在學習完40個情節(jié)后，時間步數(shù)基本趨于穩(wěn)定，逐漸收斂至次優(yōu)解。而TD算法在10個情節(jié)內(nèi)學習曲線是逐漸平滑遞減，當學習完10個情節(jié)后就收斂至最優(yōu)解。MC算法中一些狀態(tài)集的值函數(shù)的計算不依賴于其他狀態(tài)集的值函數(shù)，只需要將那些能夠精確描述環(huán)境信息的狀態(tài)子集中計算所獲得的平均回報獎賞值，作為將這個回報值作為V（st）的目標。而TD算法只迭代修改相鄰狀態(tài)的估計值，將觀察得到的獎賞rt+1和估計值V（st+1）為逼近目標進行迭代，在當前固定策略下給出策略的最優(yōu)狀態(tài)值估計。

在狀態(tài)空間維度較小的情況下，MC算法相對于TD算法的學習速度與學習結(jié)果較差些，收斂速度較慢些。但是，隨著離散空間維度的增大（即狀態(tài)空間維度設(shè)為20×20），從算法學習過程的收斂情況可以看出，TD算法大約在學習完90個情節(jié)后收斂至最優(yōu)解，如圖4所示。但是MC算法學習完500個情節(jié)，性能逐漸減退，且始終存在著劇烈的震蕩，最終結(jié)果也無法收斂到較好的值。這是因為MC算法是基于平均化取樣回報來更新當前狀態(tài)的值函數(shù)，只有在每個學習情節(jié)到達終止狀態(tài)并獲得返回值時，才能更新當前狀態(tài)的值函數(shù)。在大空間狀態(tài)下批量更新，MC算法由于采樣一次學習所獲得的立即獎賞值，然后多次學習逼近真實的狀態(tài)值函數(shù)，而每次學習必須要等到當前情節(jié)（episode）終止時才能夠進行。MC算法得到的是訓練樣本集上具有最小均方差的估計值。而TD算法不必等到最終輸出結(jié)果產(chǎn)生之后再修改以往學到的經(jīng)驗，而是在學習過程中逐步修改。TD算法得到的估計值是馬爾科夫過程最大似然模型得到的精確值。因此，TD算法比MC算法收斂更快。

Sutton在1988年提出并證明了TD（0）算法的收斂性，即TD（0）算法在最小化均方差（Mean Square Error：MSE）意義下的收斂性。雖然存在收斂速度慢的問題。但是當系統(tǒng)滿足馬爾科夫?qū)傩裕瑢W習因子α絕對遞減條件下，TD（0）算法必然收斂。圖5和圖6分別給出了學習因子α取值不同時，TD學習速度收斂的情況。實驗中TD算法根據(jù)ε-greedy貪心策略確定動作，探索因子ε=0.1， 折扣因子γ=0.9，學習因子分別設(shè)為α=0.1，α=0.2，α=0.5。在狀態(tài)空間維度20×20的迷宮模型驗證。從實驗結(jié)果可以看出，選取較大的α值時，TD算法能夠較快收斂，但是不夠平穩(wěn)，需要較長時間才能平穩(wěn)；選取較小的α值時，TD算法收斂速度較慢，但是在情節(jié)數(shù)多的情況比較平穩(wěn)。

4 結(jié)束語

基于查詢值表（Lookup-table）的TD方法是強化學習中一個經(jīng)典的值函數(shù)預測方法，即只評估某個穩(wěn)定策略下的值函數(shù)，解決了強化學習中根據(jù)時間序列進行預測的問題。

離散的馬爾可夫決策過程是強化學習研究的重要理論基礎(chǔ)，已知狀態(tài)轉(zhuǎn)移概率T和獎賞函數(shù)R的前提下，可以采用動態(tài)規(guī)劃的值迭代過程得到最優(yōu)策略。

動態(tài)規(guī)劃中的值迭代算法是通過在各種策略下計算狀態(tài)值函數(shù)，找出最優(yōu)狀態(tài)值對應的最優(yōu)策略。但是，這種方法每次迭代計算相對簡單、計算量小，但是所需的迭代次數(shù)可能較大。

MC方法是從樣本情節(jié)形式的經(jīng)驗中學習值函數(shù)和逼近最優(yōu)策略，解決基于平均樣本回報的強化學習問題的方法。

本文主要是針對小規(guī)模的、離散狀態(tài)空間問題，分析比較了MC算法與TD算法的收斂性。近年來，基于值函數(shù)逼近的強化學習方法越來越多地被用于模式識別、工業(yè)制造等領(lǐng)域，具有大規(guī)模連續(xù)動作空間的強化學習問題成為研究的熱點。這也是下一階段學習和研究的任務。

參考文獻（References）：

[1] Sutton R S， Barto A G. Reinforcement learning： An

introduction[M]. Cambridge： MIT Press，1998.

[2] Busoniu L， Babuska R， De Schutter B， et al. Reinforcement

learning and dynamic programming using function approximators[M]. USA： CRC Press，2010.

[3] 高陽，陳世福，陸鑫.強化學習研究綜述[J].自動化學報，

2004.33（1）：86-99

[4] Kaelbing L p， Littman M l， Moore A W. Reinforcement

learning： a survery[J]. Journal of Artificial Intelligence Rearch，1996.4：237-285

[5] Ratitch B. On characteristics of Markov decision processes

and reinforcement learning in large domains[D]. PhD thesis， The School of Computer Science McGill University，Montreal，2005.

[6] Konidaris G. A framework for transfer in reinforcement

learning[C]. In：ICML-2006 Workshop on Structural Knowledge Transfer for Machine Learning，2006.

[7] Wiering M， Van Otterlo M. Reinforcement Learning：

state-of-the-Art[M].Heidelberg Berlin： Springer，2012.

[8] 陳學松，楊宜民.強化學習研究綜述[J].計算機應用研究，

2010.27（8）：2834-2838