1.4　強化學習的理論基礎

本節將介紹前面討論的概念（獎勵、智能體、動作、觀察和環境）以及它們的數據表示和符號。然后，將這些作為知識基礎，探索RL更高階的概念，包括狀態、片段、歷史、價值和收益，這些概念會在本書后面反復提到，用于描述不同的方法。

1.4.1　馬爾可夫決策過程

在此之前，我們將介紹馬爾可夫決策過程（Markov Decision Process，MDP），用俄羅斯套娃的方式來描述它：從最簡單的馬爾可夫過程（Markov Process，MP）開始，然后將其擴展成馬爾可夫獎勵過程（Markov reward process），最后加入動作的概念，得到MDP。

MP和MDP被廣泛地應用于計算機科學和其他工程領域。因此，閱讀本章除了讓你對RL的上下文更熟悉外，對理解其他領域也有用。如果你已經很熟悉MDP了，那么可以快速瀏覽本章，只關注術語的定義即可。

馬爾可夫過程

我們從馬爾可夫家族最簡單的MP（也稱為馬爾可夫鏈）開始。想象一下你面前有一個只能被觀察的系統。能觀察到的被稱為狀態，系統可以根據動力學定律在狀態間進行切換。再強調一次，你不能影響系統，只能觀察到狀態的變化。

系統中所有可能的狀態形成了一個集合，稱為狀態空間。對MP而言，狀態集應該是有限的（雖然有限制，但是它可以非常大）。觀察結果形成了一個狀態序列或狀態鏈（這就是MP也稱為馬爾可夫鏈的原因）。例如，看一下最簡單的模型——城市的天氣模型，我們可以觀察到今天是晴天還是雨天，這就是狀態空間。隨著時間的推移，一系列觀察結果形成了一條狀態鏈，例如[晴天，晴天，雨天，晴天，……]，這稱為歷史。

要將這樣的系統稱為MP，它需要滿足馬爾可夫性質，這意味著系統未來的任何狀態變化都僅依賴于當前狀態。馬爾可夫性質的重點就是讓每一個可觀察的狀態是自包含的，都能描述系統的未來狀態。換句話說，馬爾可夫性質要求系統的狀態彼此可區分且唯一。在這種情況下，只需要一個狀態就可以對系統的未來動態進行建模，而不需要整個歷史或最后N個狀態。

在天氣的例子中，馬爾可夫性質將模型限制在這樣的情況下：不管之前看到了多少個晴天，晴天之后是雨天的概率都是相同的。這個模型不太現實，因為根據常識，我們知道明天會下雨的概率不僅取決于當前的狀況，還取決于許多其他因素，例如季節、緯度以及附近是否有山和海。最近有研究表明，甚至連太陽的活動都會對天氣造成重大影響。所以，這個例子的假設有點太天真了，但是有助于理解限制條件并做出清醒的決定。

當然，如果想讓模型變得更復雜，只需要擴展狀態空間就可以了，以更大的狀態空間為代價，我們可以捕獲模型更多的依賴項。例如，如果要分別捕獲夏天和冬天雨天的概率，將季節包含在狀態中即可。

在這種情況下，狀態空間將是[晴天+夏天，晴天+冬天，雨天+夏天，雨天+冬天]。

只要系統模型符合馬爾可夫性質，就可以用轉移矩陣來描述狀態轉移的概率，它是一個大小為N×N的方陣，N是模型中狀態的數量。矩陣中的單元（第i行，第j列）表示系統從狀態i轉移到狀態j的概率。

例如，在晴天/雨天的例子中，轉移矩陣如下所示：

在這種情況下，如果某天是晴天，那么第二天是晴天的概率為80%，是雨天的概率為20%。如果觀察到某天是雨天，那么第二天是晴天的概率是10%，第二天還是雨天的概率是90%。

MP的正式定義如下：

• 一組狀態（S），系統可以處于任一狀態。
• 一個轉移矩陣（T），通過轉移概率定義了系統的動態。

圖1.4是可視化MP的有效工具，其中節點代表系統的狀態，邊上的標記表示狀態轉移的概率。如果轉移的概率為0，那么我們不會畫出這條邊（即無法從一個狀態轉移到另一個狀態）。這種表示法通常也用來表示有限狀態機，這是自動機理論的研究范圍。

再強調一次，我們僅在討論觀察。我們無法影響天氣，只做觀察和記錄。

為了展示一個更復雜的例子，我們來考慮另外一個模型，上班族模型（迪爾伯特就是一個很好的例子，他是斯科特·亞當斯的著名漫畫中的主角）。上班族的狀態空間如下：

• 家：他不在辦公室。
• 計算機：他在辦公室用計算機工作。
• 咖啡：他在辦公室喝咖啡。
• 聊天：他在辦公室和同事聊天。

狀態轉移圖如圖1.5所示。

假設上班族的工作日通常從家的狀態開始，并且每天到了辦公室后，都毫無例外地從喝咖啡開始（沒有家→計算機的邊，也沒有家→聊天的邊）。圖1.5也展示了工作日都結束（即轉移到家的狀態）自計算機狀態。

其轉移矩陣如下所示：

轉移概率可以直接插入狀態轉移圖中，如圖1.6所示。

實際上，我們很少能知道確切的轉移矩陣。真實世界中，一般只能得到系統狀態的觀察，這被稱為片段：

• 家→咖啡→咖啡→聊天→聊天→咖啡→計算機→計算機→家
• 計算機→計算機→聊天→聊天→咖啡→計算機→計算機→計算機
• 家→家→咖啡→聊天→計算機→咖啡→咖啡

從觀察中估算轉移矩陣并不困難——將所有的狀態轉移計數，再將其歸一化，這樣總和就是1了。觀察的數據越多，估算就越接近真正的模型。

還需要注意，馬爾可夫性質暗示了穩定性（即所有狀態的底層轉移概率分布不會隨著時間變化）。非穩定性意味著有一些隱藏的因素在影響系統的動態，而這些因素沒有被包含在觀察中。但是，這與馬爾可夫性質相矛盾，后者要求同一狀態的底層概率分布必須相同，和狀態的轉移歷史無關。

注意，在片段中觀察到的實際狀態轉移與轉移矩陣中的底層概率分布是有區別的。觀察的具體片段是從模型的分布中隨機抽樣得到的，因此片段不同，估算得到的轉移分布也可能不同。而真正的狀態轉移概率是不變的。如果不能保證這個前提，那么馬爾可夫鏈將不再適用。

現在我們來繼續擴展MP模型，使其更接近RL問題。將獎勵加入其中吧！

馬爾可夫獎勵過程

為了引入獎勵，先對MP模型做一些擴展。首先，在狀態轉移之間引入價值的概念。概率已經有了，但是概率是用來捕獲系統的動態的，所以現在在沒有額外負擔的情況下，添加一個額外的標量。

獎勵能用各種形式來表示。最常用的方法是增加一個方陣，和轉移矩陣相似，用i行j列來表示從狀態i轉移到狀態j的獎勵。

如前所述，獎勵可正可負、可大可小。在某些情況下，這種表示方法是多余的，可以被簡化。例如，如果不管起始狀態是什么，獎勵都是由到達狀態給出的，那么可以只保留狀態→獎勵對，這樣的表示更緊湊。但情況并不總是這樣，它要求獎勵必須只依賴于目標狀態。

我們在模型中加入的第二個東西是折扣因子γ，它是從0到1（包含0和1）的某個數字。我們會在對馬爾可夫獎勵過程的其他特征都進行定義后解釋它表示的意義。

你應該記得，我們會觀察一個MP的狀態轉移鏈。在馬爾可夫獎勵過程中也是這樣，但是每次轉移，都加入一個新的量——獎勵。現在，每次系統狀態轉移時，我們的觀察都會加入一個獎勵值。

對于每一個片段，t時刻的回報定義如下：

試著理解一下這個公式。對每個時間點來說，回報都是這個時間點后續得到的獎勵總和，但是越遠的獎勵會乘越多的折扣因子，和t差的步數就是折扣因子的冪。折扣因子代表了智能體的遠見性。如果γ是1，則回報Gt就是所有后續獎勵的總和，對應的智能體會依賴后續所有的獎勵來做出判斷。如果γ等于0，則回報Gt就是立即獎勵，不考慮后續任何狀態，對應完全短視的智能體。

這些極端值只在極端情況下有用，而大多數時候，γ會設置為介于兩者之間的某個值，例如0.9或0.99。這種情況下，我們會關注未來不久的獎勵，但是不會考慮太遙遠。在片段比較短并有限的情況下，γ=1可能會適用。

γ參數在RL中非常重要，在后續章節中會頻繁出現。現在，把它想成在估算未來的回報時，要考慮多遠的未來。越接近1，會考慮越多的未來。

在實踐中，回報值不是非常有用，因為它是針對從馬爾可夫獎勵過程中觀察到的一個特定狀態鏈而定義的，所以即使是在同一個狀態，這個值的變動范圍也很大。但是，如果極端一點，計算出每一個狀態的數學期望（對大量的狀態鏈取平均值），就能得到一個更有用的值了，這個值被稱為狀態的價值：

解釋起來很簡單，對于每一個狀態s，V(s)就是遵循馬爾可夫獎勵過程獲得的平均（或稱為期望）回報。

為了在實踐中展示這些理論知識，在上班族（迪爾伯特）過程中加入獎勵，將其變成迪爾伯特獎勵過程（Dilbert Reward Process，DRP），獎勵值如下：

• 家→家：1（回家是件好事）
• 家→咖啡：1
• 計算機→計算機：5（努力工作是件好事）
• 計算機→聊天：–3（分心不是件好事）
• 聊天→計算機：2
• 計算機→咖啡：1
• 咖啡→計算機：3
• 咖啡→咖啡：1
• 咖啡→聊天：2
• 聊天→咖啡：2
• 聊天→聊天：–1（長時間的對話變得無聊）

其狀態轉移圖如圖1.7所示。

讓我們再把注意力放在γ參數上，考慮在γ不同的情況下，狀態的價值會是多少。先從簡單的情況開始：γ=0。要怎么計算狀態的價值呢？要回答這個問題，需要先把聊天的狀態固定住。隨后的狀態轉移會是什么樣的呢？答案是取決于概率。根據迪爾伯特獎過程的轉移矩陣，下一個狀態還是聊天的概率為50%，是咖啡的概率為20%，是計算機的概率為30%。當γ=0時，回報值就只等于下一個狀態的獎勵。所以，如果想計算聊天狀態的價值，就只需要將所有的轉移獎勵乘上相應概率，并匯總起來。

V(chat) = –1×0.5 + 2×0.3 + 1×0.2 = 0.3

V(coffee) = 2×0.7 + 1×0.1 + 3×0.2 = 2.1

V(home) = 1×0.6 + 1×0.4 = 1.0

V(computer) = 5×0.5 + (–3)×0.1 + 1×0.2 + 2×0.2 = 2.8

所以，計算機是最有價值的狀態（如果只考慮立即獎勵的話），這并不奇怪，因為計算機→計算機的轉移很頻繁，而且有巨大的獎勵，被打斷的概率也不是很高。

還有個更棘手的問題，γ=1時價值怎么計算？仔細思考一下。答案是所有的狀態的價值都是無窮大。圖1.7并沒有包含一個沉寂狀態（不向其他狀態轉移的狀態），而且折扣因子等于1時，未來無限次數的轉移都將被考慮在內。你已經見過γ=0的情況了，所有的價值從短期來看都是正的，所以不管一開始狀態的價值是多少，加上無限個正數就是一個無窮大值。

這個無窮大的結果告訴了我們為什么需要在馬爾可夫獎勵過程中引入γ，而不是直接將所有未來的獎勵都加起來。很多情況下，轉移的次數都是無限次的（或者很大的）。由于處理無窮大的值不切實際，因此需要限制計算的范圍。小于1的γ就提供了這樣的限制，本書后面的內容還會討論它。如果你的環境范圍有限（例如，井字棋，最多就只有9步），使用γ=1也能得到有限的價值。另外一個例子是多臂賭博機（Multi-Armed Bandit，MDP），這類環境很重要，它們只能進行一步操作。這意味著，你選擇一個動作執行了一步，環境給你返回一些獎勵，片段就結束了。

正如之前所提，馬爾可夫獎勵過程的γ通常被設置在0到1之間。但是，使用這樣的值會讓手工計算變得很困難，即使是迪爾伯特這樣簡單的馬爾可夫獎勵過程，因為這其中涉及成百上千個值。但計算機總是很擅長這類煩瑣的任務，而且，給定轉移矩陣和獎勵矩陣后，有幾個簡單的方法能加速計算馬爾可夫獎勵過程的狀態價值。在第5章研究Q-learning方法時，我們就能看到甚至實現一個這樣的方法。

現在，我們為馬爾可夫獎勵過程再添加一點復雜性，是時候介紹最后一項內容了：動作。

加入動作

你可能對如何將動作加入馬爾可夫獎勵過程已經有些想法了。首先，必須加入一組有限的動作（A）。這是智能體的動作空間。其次，用動作來約束轉移矩陣，也就是轉移矩陣需要增加一個動作的維度，這樣轉移矩陣就變成了轉移立方體。

MP和馬爾可夫獎勵過程的轉移矩陣是方陣，用行表示源狀態，列表示目標狀態。所以，每一行（i）都包含了轉移到每個狀態的概率（見圖1.8）。

現在智能體不只是消極地觀察狀態轉移了，它可以主動選擇動作來決定狀態的轉移。所以，針對每個源狀態，現在用一個矩陣來代替之前的一組數字，深度維度包含了智能體能采取的動作，另外一個維度就是智能體執行一個動作后能轉移的目標狀態。圖1.9展示了新的狀態轉移表，它是一個立方體，源狀態在高度維度（用i作索引），目標狀態在寬度維度（j），智能體執行的動作在深度維度（k）。

所以，通過選擇動作，智能體就能影響轉移到目標狀態的概率，這是非常有用的。

為了解釋為什么我們需要這么多復雜的東西，我們來想象一下機器人生活在3×3的網格中，可以執行左轉、右轉和前進的動作。狀態就是指機器人的位置和朝向（上、下、左、右），共包含3×3×4=36個狀態（機器人可以處在任何位置，任何朝向）。

再想象一下發動機不太好的機器人（在現實生活中很常見），當它執行左轉或右轉時，有90%的概率成功轉到指定的朝向，但有10%的概率輪子打滑了，機器人的朝向沒變。對于前進也是一樣的——90%可能成功，10%機器人會停留在原地。

圖1.10展示了狀態轉移的一部分，顯示了機器人處在網格的中心并朝向上，也就是從（1，1，朝上）狀態開始的所有可能轉移。如果機器人試著前進，則有90%的概率落到（0，1，朝上）狀態，但是也有10%的概率輪子打滑，目標位置還是（1，1，朝上）。

為了完整地捕獲所有細節，包括環境以及智能體動作可能產生的反應，MDP通常會是一個三維矩陣（3個維度分別為源狀態、動作和目標狀態）。

最后，為了將馬爾可夫獎勵過程轉成MDP，需要像處理狀態轉移矩陣一樣，將動作加入獎勵矩陣中去。獎勵矩陣將不止依賴于狀態，還將依賴于動作。換句話說，智能體獲得的獎勵將不止依賴于最終轉移到的狀態，還將依賴于促使其轉移到這個狀態的動作。

這和你把精力投入到某件事中很像——即使努力的結果不是很好，但你仍將習得技能并獲得知識。所以即使最終的結果是一樣的，做一些事總比什么都不做獲得的獎勵要更多一些。

有了正式定義的MDP后，終于可以來介紹MDP和RL中最重要的概念：策略。

1.4.2　策略

策略最簡單的定義是一組控制智能體行為的規則。即使是特別簡單的環境，也能有多種多樣的策略。在前面那個機器人網格世界的例子中，智能體就可能有多種策略，能導致被訪問的狀態不同。例如，機器人能執行下列動作：

• 不顧一切，盲目前進。
• 通過檢查前一個前進的動作是否失敗來試圖繞過障礙。
• 通過有意思的旋轉來逗樂其創造者。
• 通過隨機地選擇動作來模擬在網格世界中喝醉了的機器人。

你應該還記得RL中智能體的主要目的是獲得盡可能多的回報。不同的策略能給予不同的回報，所以找到一個好的策略是很重要的。因此策略的概念很重要。

策略的正式定義就是每個可能狀態下的動作概率分布：

π(a|s) = P[At = a|St = s]

定義中給出的是概率而不是具體的動作，是為了給智能體的行為引入隨機性。我們將在本書的后面討論為什么這是重要、有用的。確定性策略是概率性的一個特例，只需要將指定動作的概率設置成1就可以了。

另一個有用的概念是，如果策略是固定不變的，則MDP會變成馬爾可夫獎勵過程，因為我們可以用策略的概率來簡化狀態轉移矩陣和獎勵矩陣，以擺脫動作的維度。

恭喜你完成了這一階段的學習！本章很具挑戰性，但是對理解后續的實踐內容很重要。在完成后續兩章對OpenAI Gym和深度學習的介紹后，我們將開始解決這個問題——如何教智能體解決實際任務？