20.7强化学习的一般化

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

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

一項簡單的更新效能評估的方法是在1950年代後期，由Widrow和Hoff（1960）在適應性控制理論的領域中所發明。稱為LMS（最小平均平方，leastmeansquares）方法。基本上，假設訓練序列中的每個狀態，序列上的可見外帶回報為實際的預期外帶回報提供直接證據。因此，在序個序列的結尾，該演算法為每個狀態計算可見的外帶回報，並藉以評估該狀態更新的效能。

當功效函數以各個狀態的值呈現於一個表中，只需要藉由維護一個執行平均即可達到更新的目的，如圖20.3所示。圖20.4顯示在圖20.1的4

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

使用到環境結構知識的程式通常學習得較快。在圖20.5的範例中（摘取自（Sutton,1988）），對於右方的三個狀態，代理人已經有一個公正的經驗總計，並已經學得指定的數值。時間差學習法

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

20.3未知環境中的被動式學習

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

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

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

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

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

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

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

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

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

20.7強化學習的一般化

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

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

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

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

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