20.7強(qiáng)化學(xué)習(xí)的一般化

第二十章強(qiáng)化學(xué)習(xí)20.1序論20.2已知環(huán)境中的被動(dòng)式學(xué)習(xí)20.3未知環(huán)境中的被動(dòng)式學(xué)習(xí)20.4未知環(huán)境中的主動(dòng)式學(xué)已20.5探索20.6學(xué)習(xí)一個(gè)行動(dòng)-數(shù)值函數(shù)20.7強(qiáng)化學(xué)習(xí)的一般化20.8基因演算法和演化程式設(shè)計(jì)20.1序論環(huán)境提供輸入和輸出序?qū)?，而要做的工作是學(xué)習(xí)一個(gè)可能產(chǎn)生這些序?qū)Φ暮瘮?shù)。當(dāng)有一位老師在旁提供正確的值、或是當(dāng)函數(shù)的輸出表現(xiàn)出對(duì)於未來(lái)的預(yù)測(cè)，而這些預(yù)測(cè)可經(jīng)由檢查下個(gè)時(shí)間步驟之認(rèn)知而確認(rèn)時(shí)，這些監(jiān)督式學(xué)習(xí)方法是合宜的?；仞?，代理人就沒(méi)有決定如何移動(dòng)的根據(jù)。例如，我們知道一個(gè)代理人可以用監(jiān)督式學(xué)習(xí)法學(xué)習(xí)下棋──藉由給予棋局狀況的範(fàn)例，並伴隨著該狀況下的最佳移動(dòng)。但若沒(méi)有好老師從旁提供範(fàn)例，代理人能怎麼做？雖然藉著隨機(jī)移動(dòng)棋子的嘗試，最終代理人還是能建立一個(gè)環(huán)境的預(yù)測(cè)模型：在代理人做一次移動(dòng)之後棋盤(pán)上的情勢(shì)會(huì)變得如何，甚至是對(duì)手在一個(gè)給定狀況下可能有怎樣的反應(yīng)。但若缺乏一些關(guān)於什麼是好什麼是壞的20.2已知環(huán)境中的被動(dòng)式學(xué)習(xí)

為了讓事情保持單純，我們從被動(dòng)式學(xué)習(xí)代理人的例子開(kāi)始，並在已知且可得知資訊的環(huán)境中使用狀態(tài)基礎(chǔ)的表示式。在被動(dòng)式學(xué)習(xí)之中，環(huán)境會(huì)產(chǎn)生狀態(tài)轉(zhuǎn)換，代理人則會(huì)察覺(jué)到這些變化。1想像有一個(gè)代理人嘗試學(xué)習(xí)如圖20.1(a)所示的狀態(tài)之功效。創(chuàng)始更新（Na?veUpdating）

一項(xiàng)簡(jiǎn)單的更新效能評(píng)估的方法是在1950年代後期，由Widrow和Hoff（1960）在適應(yīng)性控制理論的領(lǐng)域中所發(fā)明。稱(chēng)為L(zhǎng)MS（最小平均平方，leastmeansquares）方法?；旧?，假設(shè)訓(xùn)練序列中的每個(gè)狀態(tài)，序列上的可見(jiàn)外帶回報(bào)為實(shí)際的預(yù)期外帶回報(bào)提供直接證據(jù)。因此，在序個(gè)序列的結(jié)尾，該演算法為每個(gè)狀態(tài)計(jì)算可見(jiàn)的外帶回報(bào)，並藉以評(píng)估該狀態(tài)更新的效能。

當(dāng)功效函數(shù)以各個(gè)狀態(tài)的值呈現(xiàn)於一個(gè)表中，只需要藉由維護(hù)一個(gè)執(zhí)行平均即可達(dá)到更新的目的，如圖20.3所示。圖20.4顯示在圖20.1的4

3環(huán)境中一項(xiàng)典型的演變，同時(shí)描述功效評(píng)估的收斂性，以及對(duì)應(yīng)正確功效值、逐漸縮小的平均平方誤差。它讓代理人在經(jīng)歷上千次訓(xùn)練序列之後能夠很接近正確值。適應(yīng)性動(dòng)態(tài)規(guī)劃

使用到環(huán)境結(jié)構(gòu)知識(shí)的程式通常學(xué)習(xí)得較快。在圖20.5的範(fàn)例中（摘取自（Sutton,1988）），對(duì)於右方的三個(gè)狀態(tài)，代理人已經(jīng)有一個(gè)公正的經(jīng)驗(yàn)總計(jì)，並已經(jīng)學(xué)得指定的數(shù)值。時(shí)間差學(xué)習(xí)法

可能同時(shí)有兩個(gè)（幾乎）最好的環(huán)境──也就是說(shuō)，可以逼近之前提到的限制等式，並且不需對(duì)所有可能狀態(tài)解出這些等式。關(guān)鍵是使用可見(jiàn)的轉(zhuǎn)換以調(diào)整可見(jiàn)狀態(tài)的值，使其與限制等式一致。所有時(shí)間差方法的基本觀念都是先定義當(dāng)功效評(píng)估正確時(shí)，局部成立的條件﹔接著寫(xiě)一項(xiàng)更新等式，使所有評(píng)估能接近這個(gè)理想的均態(tài)（equilibrium）等式。如圖20.6的TD-UPDATE演算法。圖20.7表示一個(gè)典型的TD學(xué)習(xí)演算法在圖20.1的環(huán)境中執(zhí)行的狀況。

20.3未知環(huán)境中的被動(dòng)式學(xué)習(xí)

適應(yīng)性動(dòng)態(tài)規(guī)劃方法只在更新受評(píng)估之環(huán)境模型的PASSIVE-RL-AGENT中增加一個(gè)步驟。然後被評(píng)估過(guò)的模型就成為動(dòng)態(tài)規(guī)劃階段的基礎(chǔ)，並在每次觀察之後計(jì)算對(duì)應(yīng)的功效評(píng)估。當(dāng)環(huán)境模型接近正確的模型，功效評(píng)估必然會(huì)收斂到正確的功效。配合環(huán)境的表格狀表示法，可以藉由掌握每個(gè)狀態(tài)到相鄰狀態(tài)的轉(zhuǎn)換次數(shù)百分比而更新環(huán)境模型M。對(duì)圖20.1的4

3環(huán)境使用這項(xiàng)簡(jiǎn)單的技巧，可獲得如圖20.8所示的學(xué)習(xí)效能。注意ADP法遠(yuǎn)比LMS和TD學(xué)習(xí)法收斂的更快。20.4未知環(huán)境中的主動(dòng)式學(xué)習(xí)

被動(dòng)式學(xué)習(xí)代理人可被視為有固定策略，並且不需要擔(dān)心該採(cǎi)取哪一項(xiàng)行動(dòng)。主動(dòng)式代理人必須考量該採(cǎi)取何種行動(dòng)、結(jié)果會(huì)是什麼、以及這些行動(dòng)會(huì)對(duì)收到的回報(bào)造成什麼影響。圖20.2的PASSIVE-RL-AGENT模型只需要做些微修改就可配合代理人的行動(dòng)。完整的ACTIVE-ADP-AGENT之設(shè)計(jì)列於圖20.9。20.5探索

對(duì)主動(dòng)式強(qiáng)化學(xué)習(xí)唯一剩餘的考量是代理人該採(cǎi)取哪種行動(dòng)的問(wèn)題──也就是說(shuō)，PERFORMANCE-ELEMENT要傳回什麼。這發(fā)展為比想像中更困難的情況?；旧?，一個(gè)行動(dòng)有兩種結(jié)果：(1)由目前序列獲得回報(bào)。

(2)影響所接受到的認(rèn)知，並因此影響代理人學(xué)習(xí)的能力──並在未來(lái)的序列中收到回報(bào)。

由課本中的例子，在圖20.11可清楚地看到這項(xiàng)探索策略的影響，它減緩了朝向最佳效能的急劇收斂，與古怪或貪婪方法的收斂狀況不同。只要18次嘗試後就可找到一項(xiàng)很接近最佳化的策略。注意功效評(píng)估本身並不會(huì)這麼快度地收斂。這是因?yàn)榇砣撕芸斓赝Ｖ固剿鳡顟B(tài)空間中沒(méi)有回報(bào)的部分，之後會(huì)到達(dá)那些狀態(tài)純粹是偶然。探索與匪徒

在拉斯維加斯，一個(gè)武裝匪徒（one-armed-bandit）是一臺(tái)吃角子老虎。一個(gè)賭客可以投入一枚硬幣，拉下拉桿，並取出獎(jiǎng)金（如果有的話）。一個(gè)n-武裝匪徒有n個(gè)拉桿。賭客必須在每次連續(xù)投下硬幣時(shí)選擇玩哪一支拉桿──獲利最好的那一支，或是還沒(méi)有是過(guò)的那一支？n-武裝匪徒問(wèn)題是許多攸關(guān)生命的重要領(lǐng)域中真實(shí)問(wèn)題的一個(gè)正規(guī)模型，例如決定AI研究和發(fā)展的年度預(yù)算。每個(gè)拉桿對(duì)應(yīng)於一項(xiàng)行動(dòng)（例如編列兩千萬(wàn)美元發(fā)展新的AI教科書(shū)），拉下拉桿所獲得的收益則對(duì)應(yīng)於採(cǎi)取行動(dòng)所獲得的收益（無(wú)限的）。最佳探索策略所獲得的正規(guī)結(jié)果只能套用於代理人以明確表列式表現(xiàn)轉(zhuǎn)換模型的狀況，並不能對(duì)所有狀態(tài)和行為作一般化。對(duì)更實(shí)際的問(wèn)題，只能作到在無(wú)限次實(shí)驗(yàn)的條件限制下，收斂於正確模型和最佳行為。這可以由隨機(jī)執(zhí)行小部份步驟而獲得，其中執(zhí)行步驟的數(shù)量隨著時(shí)間而適當(dāng)?shù)剡f減。20.6學(xué)習(xí)一個(gè)行動(dòng)-數(shù)值函數(shù)

一個(gè)行動(dòng)-數(shù)值函數(shù)指定一個(gè)預(yù)期功效，藉以在一個(gè)給定狀態(tài)上採(cǎi)取一項(xiàng)給定的動(dòng)作﹔如同之前所述，這樣的值也稱(chēng)為Q-值（Q-values）。使用表示法Q(a,i)表示在狀態(tài)i執(zhí)行動(dòng)作a的值。Q-值以下列等式與功效值直接相關(guān)：U(i)= (20.5)一個(gè)使用TD的探索式Q-學(xué)習(xí)代理人的完整設(shè)計(jì)如圖20.12所列。注意其中用到與探索式ADP代理人完全相同的探索函數(shù)f，因此需要在採(cǎi)取行動(dòng)時(shí)保存統(tǒng)計(jì)值（表N）。若使用一個(gè)較簡(jiǎn)單的探索策略──也就是說(shuō)，在某些步驟隨機(jī)行動(dòng)，而這些步驟的數(shù)量會(huì)隨時(shí)間遞減──則可省卻統(tǒng)計(jì)值。圖20.13表示在4

3環(huán)境中Q-學(xué)習(xí)代理人的效能。注意功效評(píng)估（由使用等式(20.5)的Q-值所導(dǎo)出）需要比使用ADP代理人時(shí)花費(fèi)更長(zhǎng)的時(shí)間才能穩(wěn)定下來(lái)。這是因?yàn)門(mén)D並未藉由模型強(qiáng)制數(shù)值間的一致性。雖然只要26個(gè)嘗試就可得到一個(gè)很好的策略，但從最佳狀態(tài)的觀點(diǎn)，則仍差A(yù)DP代理人很遠(yuǎn)（圖20.11）。

20.7強(qiáng)化學(xué)習(xí)的一般化

到目前為止我們做的假設(shè)是所有代理人（U,M,R,Q）所學(xué)習(xí)的函數(shù)都以表格的形式呈現(xiàn)──亦即對(duì)每個(gè)輸入多元組（inputtuple）之一項(xiàng)輸出值的顯然表示法（explicitrepresentation）。這樣的方法對(duì)較小的狀態(tài)空間可以執(zhí)行的很不錯(cuò)，但隨著空間擴(kuò)大，收斂所需的時(shí)間和（對(duì)ADP）每次疊代的時(shí)間都快速增加。競(jìng)局的應(yīng)用

強(qiáng)化學(xué)習(xí)的第一項(xiàng)重要範(fàn)例，同時(shí)也是對(duì)任何學(xué)習(xí)形式最重要的學(xué)習(xí)程式──由ArthurSamuel（1959;1967）所寫(xiě)的西洋棋競(jìng)局程式。Samuel首先使用一個(gè)加權(quán)線性函數(shù)評(píng)估棋局，在每一次都使用高達(dá)16個(gè)數(shù)學(xué)項(xiàng)目。他用等式（20.8）的一個(gè)版本更新權(quán)重。然而，他的程式和現(xiàn)在的方法有一些重大的差異。首先，他使用目前狀態(tài)與搜尋樹(shù)中完整前瞻所產(chǎn)生之備份值的差。這有不錯(cuò)的效果，因?yàn)檫@相當(dāng)於從不同細(xì)緻化的程度看狀態(tài)空間。第二項(xiàng)差異是程式並未使用任何可見(jiàn)的回報(bào)！也就是說(shuō)，終止?fàn)顟B(tài)的值被忽略掉。機(jī)器人控制的應(yīng)用

有名的車(chē)桿（cart-pole）平衡問(wèn)題裝置，也稱(chēng)為倒鐘擺（invertedpendulum），如圖20.14所示。該問(wèn)題是控制車(chē)子的位置x以使得車(chē)桿保持大約直立的狀態(tài)（

/2），並保持在所示的車(chē)軌限制範(fàn)圍內(nèi)。更近期的類(lèi)神經(jīng)網(wǎng)路被用在從狀態(tài)空間到行動(dòng)的連續(xù)對(duì)應(yīng)，有稍微改善的結(jié)果。然而，最令人印象深刻的表現(xiàn)當(dāng)屬於對(duì)三個(gè)倒單擺使用古典控制理論所導(dǎo)出的控制演算法，其中三根長(zhǎng)桿一根疊一根地平衡，長(zhǎng)桿連接處有轉(zhuǎn)矩控制（Furutaetal.,1984）。20.8基因演算法和演化程式設(shè)計(jì)

大自然對(duì)於成功地演化出有機(jī)體有很強(qiáng)健的方法。對(duì)於環(huán)境適應(yīng)不良的有機(jī)體就死亡，而能適應(yīng)生活的就繁殖。子代與其親代相似，因此新世代具有與能適應(yīng)環(huán)境的上一代類(lèi)似的有機(jī)體。若環(huán)境緩慢改變，物種會(huì)隨著環(huán)境的改變而逐漸演化，但環(huán)境中的劇烈改變則有可能殲滅一個(gè)物種。發(fā)展出的結(jié)果是：對(duì)自然有益的也會(huì)對(duì)人造系統(tǒng)有益。圖20.15表示一個(gè)GENETIC-ALGORITHM，從一個(gè)有一或多個(gè)個(gè)體的集合開(kāi)始，並套用選擇和繁殖運(yùn)算元以演化出一個(gè)成功的個(gè)體，用適宜性函數(shù)（fitnessfunction）做評(píng)估。繁衍以交雜（cross-over）和突變而達(dá)成。首先，所有被選出來(lái)作煩眼的個(gè)體被隨機(jī)配對(duì)，接