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

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

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

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

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

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

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

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

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

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

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

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

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

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

由課本中的例子，在圖20.11可清楚地看到這項探索策略的影響，它減緩了朝向最佳效能的急劇收斂，與古怪或貪婪方法的收斂狀況不同。只要18次嘗試後就可找到一項很接近最佳化的策略。注意功效評估本身並不會這麼快度地收斂。這是因為代理人很快地停止探索狀態(tài)空間中沒有回報的部分，之後會到達那些狀態(tài)純粹是偶然。探索與匪徒

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

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

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

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

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

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

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

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

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