強化學習筆記3—有限馬爾科夫決策過程

本章介紹有限馬爾科夫決策過程(Finite Markov Decision Processes)或有限MDPs中的形式(formal)問題，它既設計評估性回饋，但也包含結合性內容—在不同的情況下選擇不同的行動。MDPs是經典的序列決策形式，其中行動不僅影響即時激勵，也通過未來激勵影響隨後的情形或狀態。因此MDPs包含延遲激勵，以及即時與延遲激勵之間的權衡。MDPs會評估每個行動在每個狀態的價值，或給定最優行動選擇每個狀態的價值。這些狀態無關的數量是為長期結果將信任精確分配到單個行動選擇的關鍵。MDPs是強化學習問題理想的數學形式，可以為其做出精確的理論陳述。

3.1 代理-環境介面

學習者和決策者稱為代理(agent)， 與它互動的、代理以外的所有的事物統稱為環境(enviroment)。這些互動持續不斷，代理選擇行動、環境對行動做出反應並向代理展示新的狀態。環境也會產生激勵，一種特殊的代理尋求通過自己的行動選擇來最大化俄特殊數值。見圖3.1。

更具體地說，代理和環境在離散的時間步序列 上互動。在每個時間步，代理獲得一個環境狀態(state) 的表示，（是所有可能的狀態）；然後以狀態為基礎選擇一個行動(action)，（表示在狀態獲得的行為集）。一個時間步後，代理收到一個數值激勵，並進入新狀態中。因此MDP和代理一起就產生了想這樣開始的一個序列或軌跡：

在有限MDP中，狀態、行動和激勵的集合（、和）都只有有限數目的元素。在這種情況下，隨機變數和有定義良好的僅依賴於先前狀態和行動的離散概率分布。也就是，對這些隨機變數的特定值和，給定特定的先前狀態和行動，存在一個那些值在時間的概率：

上式對所有的和都成立。等號上面的點表示這個等式是一個定義。函數是一個四個參數的常確定函數(ordinary deterministic function)，中間的「|」是來自條件概率的符號，但這裡恰(just)提醒我們為每個和的選擇確定一個概率分布，也就是：

由這個4-參數函數給出的概率完全描繪出了一個有限MDP的動態(dynamics)，從它可以計算出任何其他關於關於環境的信息，比如狀態轉移概率(state-transimition probilities) ，（可能有點濫用記號）記為 :

也可以作為2-參數函數計算狀態-行動對的期望激勵：

或者作為3-參數函數的狀態-行動-狀態三元組的期望激勵：

本書中通常使用(3.2)中的4-參數函數。

這個框架非常抽象和靈活，可以以不同的方式應用到不同的問題。比如，時間步不必是真實時間的固定間隔，可以是任意決策或行為的連續狀態；行為和狀態都可以採用非常多的形式；特別是，代理和環境的邊界並非如機器人或動物身體那樣的物理邊界，設定它們之間邊界的通用原則是任何無法被代理隨意改變的事物都認為是環境的一部分。也可以因為不同的原因設置在不同位置。

示例3.3：回收機器人 一個在辦公環境回收金屬罐的移動機器人，有檢測感測器、拾取臂爪和存放箱子，由充電電池驅動，搜尋金屬罐的決策則由基於當前電池電量水平的RL代理制定。代理需決定機器人是否要：(1)在特定時間段積極搜尋金屬罐，(2)保持靜止等待別人帶來，(3)回到基座充電。這些決策必須周期性或者特定事件發生（比如找到空罐）時做出，代理因此有三種行為，狀態由電池狀態決定。激勵大多時候為0，在弄到空罐時為正，或電量一直下降為大負數。這裡的RL代理並非整個機器人，其監測的狀態描述機器人內部情形，因此代理的環境包含機器人的其餘部分，以及機器人的外部環境。

示例3.4：回收機器人MDP 通過簡化和提供更多細節，回收機器人可轉變為簡單MDP例子。假定環境以如下方式運行：尋找金屬罐最好方法是積極搜尋，但會消耗電量，而等待則不會。每當機器人搜尋時，電量都有耗盡的可能。這種情況下機器人必須關機等待重用（產生低的激勵）。

代理將決策完全作為電池能量水平的函數，它能辨別兩種層面：和，將可能決策記為：、和。代理的行動集就是：

若能量水平為高，則一段搜尋總能在不耗盡電量情況下完成；高能開始的搜尋後，電量以的概率為高，以的概率減為低。另一方面，低能開始的搜尋後，電量以的概率為低，以的概率耗盡。耗盡後，機器人被重用，電量充回高。每個收集的金屬罐激勵計為+1，每次重用的激勵計為-3，記和()分別為搜尋和等待時金屬罐的期望數，且假設回去充電途中不會收集金屬罐。這樣這個系統就是一個有限MDP，其轉移矩陣和期望激勵為：

轉移圖便於總結有限MDP動態，圖3.3為回收機器人的轉移圖，有狀態和行動兩種節點。每個狀態有一個狀態節點（大圓圈），每個狀態-行動對有一個行動節點（小圓點）。從開始採取行動，到達行動節點，每個箭頭對應一個三元組，標記箭頭轉移概率，轉移激勵期望。

3.2 目標和激勵

代理的目標是最大化獲得的總激勵的數目，這表明不是即時激勵，而是長期累積的激勵。形式化的思想可以用激勵假設(reward hypothesis)來清楚地闡述：

所有關於目標(goals)或目的(purposes)含義都可以認為是激勵信號累積值期望的最大值。

使用激勵信號來形式化目標的思想，是強化學習最獨特的特徵之一，並已經證明足夠地靈活和有效。需要注意雖然大多數動物最終目標感知的計算都發生在機體內，但仍然認為目標和激勵在代理之外，屬於環境。因為將學習代理的邊界置於其控制的極限而非物理身體的極限非常方便，而這並不會妨礙代理為自己定義內部激勵。

3.3 回報和節

那如何正式地定義代理的目標呢？假設時間步後的激勵序列為，通常會尋求最大化期望的回報(expected return)，其中的回報(return)定義為激勵序列的特定函數。最簡單的方式就是定義為激勵之和：

其中是結束的時間步。這種方法對時間會自動結束的應用有效，即代理-環境的互動可以明顯地分為被稱為節(episodes)的子序列，比如比賽、迷宮旅行以及任何其它重複的互動形式，每一節以特殊的終止狀態(terminal state)結束，然後重置為標準的開始狀態或開始狀態分布的採樣，即便以不同的方式結束，下一節的開始依然與前一節的結束方式無關，因此所有的節都可以認為是以相同的終結狀態結束，只是不同的結果有不同的激勵。有節的任務都被認為是分節任務(episodic tasks)，有時這種任務需要從所有狀態中區分出所有非終結狀態。

但也有很多無限運行的持續任務(continuing task)就無法使用(3.1)的回報公式，因，要最大化的回報也很容易是無限大。這裡引入折扣(discounting)的概念，即代理嘗試選擇使得以後折扣激勵之和最大的行動。特別地，它選擇來最大化期望的折扣回報：

其中參數稱為折扣速率，它決定了未來激勵的當前值：即未來步獲得的激勵僅是其即時獲得的倍。若，則只要激勵序列是有界的，這個無限的和就有有界的值。若，則代理就是短視的，僅關心最大的眼前（即時)激勵；若代理的所有行為僅影響即時利益，則短視代理就能通過分別最大化每個激勵來最大化(3.2)；但在一般情況下，這樣會減少獲得未來激勵的機會，因此事實上的回報會減小；隨著接近1，目標就越來越重視未來的激勵，代理就變得越來越有遠見。

示例3.5 平衡桿：圖3.2的目標是對沿車轍移動的小車施力，阻止鉸在車上的桿掉落。若桿偏離沿垂直線超過一定角度或者小車駛離車轍，則任務失敗，在每次失敗後桿重設為直立。此任務可視為分段任務，每一節就是使桿平衡的重複嘗試。這時每一個未失敗時間步的激勵就是+1，因此每次的回報就是失敗前的步數。或者，也可以使用折扣將其視為連續任務。這時每個失敗的激勵就是-1，其餘為0。每次的回報會就與有關，是失敗前的步數。在兩種情況下，回報都儘可能長地保持桿平衡來最大化。

連續時間步的回報將強化學習理論和演算法以十分重要的方式關聯起來：

若定義，這就適用於所有的時間步，即便在步發生終結。這樣就能很方便地用激勵序列計算回報。注意，儘管(3.2)的回報是無窮項之和，但若激勵非0且不變，其值依然有界。如激勵恆為+1，則回報為：

3.4 統一記號

前面說到強化學習任務有分節和連續兩種任務，但在討論分節任務時並不會區分不同的節。因此可以將每一節的結束視為進入特殊的只會轉移到自身且激勵為0的終止狀態，比如：

這樣就能將兩者統一起來，即使引入折扣的也成立，回報因而可以寫為：

包括了和的情況（但兩者不同時成立）。本書剩餘部分使用這些約定來簡化記號並表示分節和持續任務之間的緊密相似。

3.5 策略和價值函數

幾乎所有的RL演算法都會涉及評估代理處於給定狀態（或在給定狀態下執行給定行動）好壞的價值函數——狀態（或狀態-行動）的函數。這裡的「好壞」依據期望的回報定義，未來可期的激勵取決於其採取的行動，因此價值函數由相應特定策略定義。

策略是從每個狀態和行為到在狀態採取行動概率的定義。在策略下狀態的價值，記為是從開始一直遵循的期望回報。對於MDP，定義為：

其中表示代理遵循策略隨機變數的期望，是任意時間步。注意任意終止狀態的價值總是0。稱函數為策略的狀態-價值函數。同樣定義策略下在狀態採取行動的價值為從狀態開始一直遵循策略採取行動的期望回報：

稱為策略的行動-價值函數。

價值函數和可以從經驗中估計。如果一個代理遵循策略且對遇到的每個狀態，都維護一個此狀態後實際回報的均值，則當狀態遇到的次數趨於無窮時，其均值就會收斂於其價值。如果對一個狀態的每個行為保持單獨的均值，則這些均值同樣會收斂到行為價值函數。這種估計方法被稱為蒙特卡洛方法，因其涉及了在實際回報的許多樣本上平均。但若狀態很多，則對每個狀態維持獨立的均值就很不實際，這樣代理就不得不將和維護為參數化函數（參數個數少於狀態數），並調整參數以更好地匹配觀察到的回報。這也能產生精確的估計，但依賴於參數化函數估運算元的性質。

貫穿價值函數在RL和DP使用的基礎特性是其滿足特定的遞歸關係。對任意策略和狀態，下面的價值和可能後繼狀態的價值之間始終滿足下面的相容條件(consistency condition)：

注意最後等式將兩個和，一個對所有的價值，另一個對所有值，歸併為一個對兩者所有可能值的和，本書會經常會用到這種歸併和的方式來簡化公式。這樣最後的表達式很容易讀為期望值。實際上是三個變數，和所有值的求和，對每個三元組，計算其概率來權衡中括弧內的量，最後將所有概率求和來獲得期望值。

公式(3.14)稱為的貝爾曼方程(Bellman Equation)，它表述了狀態的價值與其後繼狀態價值的關係。如圖3.4左邊所示，從狀態出發，根結點在頂端，代理可以採取任意某個集合里的任意行為——圖中為3個；之後環境會回應幾個可能後續狀態中的一個，以及一個激勵。貝爾曼方程將所有這些概率求均值，它表明開始狀態的價值必須等價於下一狀態（折扣）價值的期望加上期望的激勵。

價值函數是貝爾曼方程的唯一解。圖3.4這樣的圖表稱為後備圖(Backup Diagram)，因其用圖表示了形成RL方法核心的更新(update)或備份(backup)操作基礎的關係。這些操作將價值信息從後繼狀態（或狀態-行為）傳輸回一個狀態（或狀態-行為）。本書使用備份圖來提供討論演算法的圖形總結（與轉移圖不同，備份圖的狀態節點可以重複，而且時間總是向下流逝）。

示例3.6 網格世界：圖3.5左邊展示了一個簡單MDP的四邊網格世界，網格的每格對應環境的狀態；每格都有東南西北四種可能行為；確定了代理後面進入的格；可能致使代理離開網格的行為不會改變位置，但激勵為-1；其餘行為激勵為0，除了使代理離開特殊狀態的A和B。從狀態A，四種行為都使代理到達A併產生+10的激勵，從狀態B任意行為使代理到B併產生+5的激勵。

假定代理在所有位置都以等概率選擇四種行為（即隨機策略），圖3.5右邊展示了這種策略折扣的價值函數，由解(3.14)的線性方程計算而得。注意底部邊緣的負值，由隨機策略下高概率撞擊邊緣導致；這種策略下狀態A是最佳狀態，但其期待回報小於即時激勵10，因從A代理到達A，在這裡很容易撞到網格邊緣；而狀態B的價值則大於即時激勵5，因後繼狀態B的價值為正。

示例3.7 高爾夫：為將高爾夫進洞表示為強化學習任務，每次擊打記懲罰（負激勵）為-1，直到擊球進洞。狀態為球的位置，狀態價值是負的從此位置進洞需要擊打次數，行為是以所選擇球棍瞄準和擊打球的方式。假定後兩者已經給定，僅考慮球棍的選擇，並假設為一個putter或一個driver。圖3.6上部展示了一種總使用putter策略的可能狀態-價值函數；終止狀態進洞的價值為0。假定從綠色區域的任意位置可以做一次putt（通過putter擊球進洞），這些狀態的價值為-1；如果在一個狀態可以通過一次putt到達綠色區域，則其價值為-2；簡化起見假定可以putt地非常精準單範圍有限，這樣在圖上就可以有一個標為-2的尖利等高線；任意線和綠色區域間的位置恰好需兩次擊打來完成進洞。同樣可以有標記為-3、-4 ··· 的等高線。Putt無法使球逃離沙子陷阱(sand trap)，因此它們的值為。綜上所言，通過putting從球座到進洞需6次擊打。

3.6 最優策略和最優價值函數

籠統地說，解決強化學習問題意味著找到一個能獲得很多長期激勵的策略。對有限MDP，可以精確地定義最優策略：價值函數定義了一種關於策略的偏序關係。當策略在所有狀態的期望回報都大於或等於策略時，策略被定義為優於或等於策略。也就是說，。總是至少存在一個策略優於其他所有策略，這就是最優策略，記為；它們有共同的狀態價值函數，稱為最優狀態-價值函數，記為，並定義為：

最優策略同樣有共同的最優行為-價值函數，記為，定義為：

對行為-狀態對，這個函數給出在狀態採取行為後遵循最優策略的期望回報。因此，可以將寫為關於的形式：

示例3.10 高爾夫最優價值函數：圖3.6的下部展示了一種可能的最優行為-價值函數的等高線。這些是假設先用driver擊打再擇優選取行為的每個狀態的價值。Driver可以擊得更遠，但不精準，僅當距離很近時才能進洞，因此的-1等高線僅占綠色很小一部分；但若擊打多次，則對應等高線( )則更遠。-3等高線已經超過了球座。從這個球座開始，最優行為就是兩次driver一次putt。

因為是一個策略的價值函數，則必定滿足貝爾曼方程給定的狀態價值的自容條件(3.14)。因為是最優價值函數，的相容條件就能寫為與特定策略無關的特殊形式，也稱貝爾曼最優性方程。直觀上，貝爾曼最優性方程表述了最優策略下一個狀態的價值必然等價於此狀態最優行為的期望回報：

最後兩個等式是貝爾曼最優性方程的兩種形式。的貝爾曼最優性方程是：

備份圖3.5展示了和貝爾曼最優性方程中所考慮的未來狀態和行為的範圍。同和備份表相同，但在代理選擇點添加了圓弧以表示在某種策略下選擇最大值而非期望值：

對有限MDP，貝爾曼最優性方程(3.19)有與策略無關的唯一解。貝爾曼最優性方程實際是一個方程組，每個狀態一個方程，所以若有個狀態，則有個未知數的個未知方程。若環境的動態()已知，則原則上可以使用任一解非線性方程組的方法來求解這個的方程組；的方程組同樣如此。

一旦有了，確定最優策略就相對簡單了。對每個狀態，都存在一個或多個獲得貝爾曼最優方程最大值的行動，任意僅給這些行動賦予非零值的策略就是一個最優策略，可以將這個看作是一步搜索。若有了最優價值函數，則一步搜索後表現最好的行動就是最優行動。換句話說就是：任何關於最優評估函數貪婪的策略就是一個最優策略。在計算機科學中貪婪用於表述任何僅基於局部或即時做出選擇的搜索或決策過程。因此，它描述了僅基於短期結果選擇行為的策略。的優美之處在於若使用它評估行為的短期結果—尤其是一步結果—則貪婪策略事實上就是長期最優的，因已經考慮了所有可能未來行為的激勵結果（就是通過么？）。通過的方法，最優的期望長期回報就轉變為在每個狀態都能獲得的局部和即時數量。

擁有後選擇最優行為則更簡單，代理甚至不用做向前一步搜索：對任意狀態，很簡單就能找到任意最大化的行為。行為-價值函數有效地抓住了所有向前一步搜索的結果。它為每個行為-狀態對將最優期望長期回報作為局部和即時可得值提供。因此，以表達狀態-行為而非僅僅狀態的函數為代價，最優行為價值函數使得無需知道任何可能後繼狀態及其價值就能選出最優行為，也即無需了解任何環境的動態。

示例3.11 回收機器人的貝爾曼最優性方程：使用(3.19)，可以給出回收機器人的最優性方程；為緊湊表示，將狀態和行為分別表示為。因為僅有兩種狀態，因此貝爾曼最優性方程由兩個方程組成。的最優性方程可以寫為：

同樣的過程得到方程：

對任何滿足的，恰好存在一對和，同時滿足這兩個線性方程組。

示例3.12 解決網格世界問題：解決示例3.8簡單網格任務（圖3.8左邊）的的貝爾曼方程；圖3.8中間展示了最優狀態價值函數，圖3.8右邊展示了相應的最優策略。一個單元中的多個箭頭表示任一均為最優行為。

顯式地求解貝爾曼最優性方程提供了尋找最優策略從而解決強化學習問題的一種途徑。但這種方法很少能直接應用，它類似於窮盡搜索，向前看所有的可能性，計算它們發生的可能性和期待期望的合意性。這種方法依賴於至少三個實際很少同時滿足的假設：(1)精確知道環境動態；(2)有足夠的計算資源；(3)馬爾科夫特性。許多不同的方法可以視為貝爾曼最優性方程的近似解。比如啟發式搜索(heuristic search)方法可以視為展開幾次(3.19)的右側到某種深度，形成一棵概率「樹」，然後在「葉」節點使用啟發式評估函數近似（啟發式搜索方法如幾乎總是基於分節任務）。動態規劃方法則與貝爾曼最優性方程更相似。許多強化學習方法都能清晰地理解為使用實際經驗的轉移代替期望轉移的知識來近似求解貝爾曼最優性方程。

3.7 最優性與近似

雖然定義了最優價值函數和最優策略，學習最優策略的代理也工作地很好，但並不實用。除了上面說到的計算代價、環境未知的問題，所需內存也是主要的限制。建立價值函數、策略和模型的近似需要大量存儲容量。微小、有限狀態集的任務是有可能使用一個條目的數組或表格為每個狀態（或狀態-行為）建立這些近似，這些稱為表格(tabular)情形，對應的方法稱為表格方法。但在實際問題中，狀態遠超一個條目的存儲能力，這種情況下就必須使用某種更緊湊的參數化函數表示來近似這些函數。

強化學習的框架驅向近似方法，但也展示了一些獲得有效近似的獨特機會。比如，在近似最優行為時，代理面臨的很多狀態概率極低，即便為它們選擇次優行為對代理收到的激勵也無影響。強化學習的在線本質使得它能以犧牲罕見狀態為代價，更多投入到學習在常見狀態做出優良決策的方法近似最優策略。這是RL區別於其他近似解決MDP方法的關鍵特性。