強(qiáng)化學(xué)習(xí)方法的對(duì)比分析

欒詠紅 章鵬

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

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

中圖分類(lèi)號(hào)：TP18 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

強(qiáng)化學(xué)習(xí)（reinforcement learning：RL）又稱(chēng)為增強(qiáng)學(xué)習(xí)或再勵(lì)學(xué)習(xí)，是一種從環(huán)境空間狀態(tài)到動(dòng)作空間映射的學(xué)習(xí)，通過(guò)試錯(cuò)法不斷與環(huán)境交互，期望動(dòng)作從中獲得的累積獎(jiǎng)賞值最大[1，7，8]，它是以環(huán)境反饋?zhàn)鳛檩斎氲臋C(jī)器學(xué)習(xí)方法，也是近年來(lái)自動(dòng)控制和人工智能領(lǐng)域的研究熱點(diǎn)之一。

1 強(qiáng)化學(xué)習(xí)理論

1.1 強(qiáng)化學(xué)習(xí)基本原理

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

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

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

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

圖1 強(qiáng)化學(xué)習(xí)模型

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

⑴

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

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

⑵

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

⑶

1.2 馬爾科夫決策過(guò)程

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

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

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

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

2 強(qiáng)化學(xué)習(xí)的基本方法

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

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

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

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

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

⑷

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

⑸

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

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

2.2 蒙特卡羅方法

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

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

⑹

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

2.3 時(shí)間差分學(xué)習(xí)方法

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

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

⑺

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

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

3 基于柵格問(wèn)題仿真實(shí)驗(yàn)

3.1 柵格模型

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

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

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

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

圖2 柵格問(wèn)題示意圖

3.2 實(shí)驗(yàn)結(jié)果與算法收斂分析

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

參考文獻(xiàn)（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] 高陽(yáng)，陳世福，陸鑫.強(qiáng)化學(xué)習(xí)研究綜述[J].自動(dòng)化學(xué)報(bào)，

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] 陳學(xué)松，楊宜民.強(qiáng)化學(xué)習(xí)研究綜述[J].計(jì)算機(jī)應(yīng)用研究，

2010.27（8）：2834-2838