強化學習簡介(4)--蒙地卡羅法(Monte Carlo)

進入主題之前，也要先引入一個概念：基於模型/無模型學習。基於模型的學習，表示知道環境的狀況，包括是否為確定性環境，以及狀態轉移的情形、機率等。相對的，無模型學習的情況對於環境了解未知。動態規劃的作法屬於基於模型學習，因為我們計算期望值，需要機率；如果不知道環境，無法計算。

蒙地卡羅就是一種無模型學習的方法，可以用於對環境機率未知時。先回到期望值的定義：，是值和機率的乘積加總。蒙地卡羅使用大量的抽樣，抽到的值的總和，除以抽樣次數，以近似期望值。抽樣次數越多，和期望值越接近。

同樣的作法可以用在函數上。如果想要近似函數的期望值，也可以用抽樣後代入函數求得的值加總，除以抽樣次數。即

在強化學習，蒙地卡羅可以做預測和控制兩項任務。預測，就是用給定的策略預測價值或Q。控制，就是從隨機初始化策略，迭代到最佳策略。下面分別介紹兩種任務。

預測

價值函數

價值函數的定義是依狀態-動作，機率和回饋的乘積加總計算期望值，。在無模型學習，機率未知，使用蒙地卡羅近似。

例如在隨機性策略於狀態E，有兩種行動方式：一種()是0.3機率轉移到狀態D，然後依序到狀態A、B，獲得獎勵1、1、-1；另一種()是0.7機率轉移到狀態H，然後到狀態I，獲得獎勵1、1。則價值計算

如果不知道機率，只能以抽樣方式計算回饋，抽樣就是實際行動。例如第一次，，獎勵為1、1、-1，回饋是1；第二次行動是，獎勵為1、1，回饋是2；第三次行動：和第一次一樣，回饋為1。則利用蒙地卡羅計算期望值近似為。

舉例

要預測各狀態的價值，就要把狀態被接觸到的次數，以及每次被接觸時當下的回饋都記錄下來。這又分成兩種方式：every-visit，在單一回合中，每次狀態轉移接觸到的狀態都要記錄，包括重複的；和first-visit，只記錄每回合第一次接觸到的。

every-visit

例如在某策略的某一回合有狀態轉移：，得到獎勵1、1、1、1、-1

1. 在第一個狀態E得到的回饋是G(E)=1+1+1+1-1=3，記成表格如下，N表示接觸次數

1. 在第二個狀態H得到的回饋是G(H)=1+1+1-1=2

1. 在第三個狀態E得到的回饋是G(E)=1+1-1=1，但表格中已有記錄此狀態，所以直接疊加上去

1. 依序把D、A的回饋加上去(B沒有獎勵不用算)，回合結束

第二回合的狀態轉移為，獎勵為1、1、1、1

1. 第一個狀態E的獎勵為G(E)=1+1+1+1=4，繼續覆寫表格

1. 依序計算D、E、H的獎勵，並寫入表格。回合結束

1. 採樣結束，要計算各狀態的價值，只需把回饋除以接觸次數即可

first-visit

重複上面的例子，在第一回合，雖然E接觸了兩次，但因為只計第一次，所以多的那次，接觸次數和回饋都不加入。

第二回合則為

計算價值方法一樣

Q函數

類似價值函數估算的方式，主要差異在於還要記錄動作。所以狀態和動作都吻合才能疊加，否則要分開紀錄。計算式為。

舉例

一樣分成every-visit和first-visit。

every-visit

某策略第一回合的狀態變化如下：，得到獎勵1、1、1、1、-1

1. 對於第一個狀態E的回饋為，紀錄於表格如下

1. 對於第二個狀態H的回饋是，一樣寫於表格

1. 第三個狀態又是從E開始，但這次是到D而非H，因此紀錄必須和第一筆分開

1. 依序完成D和A的紀錄，結束第一回合。B沒有辦法紀錄，因為沒有動作。

1. 第二回合狀態轉移變成，獎勵為1、1、1、1。第一個狀態E的回饋是，這時表格中有狀態和動作都一樣的，可以覆寫

1. 第二、第三個狀態也有重複，都可以覆寫。本回合結束後表格變成如下

1. Q值一樣是把G/N

first-visit

概念和價值函數的時候一樣，同回合內第二次接觸不算。沿用first-visit的例子，第一回合，得到獎勵1、1、1、1、-1。由於剛好回合內都沒有重複，所以結果跟every-visit完全一樣。

第二回合是，獎勵為1、1、1、1。這裡回合內有重複，只能算一次，所以最後的結果不一樣。Q值也不同。

漸進式平均更新(incremental mean updates)

對於特定時間點，某個狀態的價值為，該狀態上一個時間點的價值，加上「本次獲得的回饋與上次價值之差」。寫成式子為。

• 初始價值為0(第0時間點)
• 為學習速率，即為更新價值的幅度。若，代入上式變成，就是MC預測價值的式子。
• Q值式子為，當，也就是MC預測Q值的式子。

控制

蒙地卡羅控制，和策略迭代一樣，目的是要找到最佳策略。初始策略也是隨機設定，不過這邊要引入一個觀念：貪婪策略/貪婪策略(greedy policy/greedy policy)。

貪婪策略，就是使Q最大的行動方式()。貪婪策略，則是先設定一個值，其值介於0和1之間，然後再隨機抽一個介於0和1之間的值，若則選使Q最大的策略；若則隨機選一個行動，即

其中，在的情境，叫做利用(exploitation)，利用Q值最大的策略。則為探索(exploration)，隨機挑選行動。這適用於有未知的行動選擇的情境，即已知策略中可能無法囊括所有的行動，所以保留一定機率探索，開發出新行動，有機會取代目前最佳策略。

蒙地卡羅控制流程

1. 隨機初始策略：
2. 迭代：
   1. ​策略評估：，使用進行回合，利用MC預測Q函數，回合數可指定。通常使用貪婪策略，有機會找到新行動。
   2. 策略改善：，使用Q函數提取新策略，並更新策略。使用貪婪策略，從現有行動中找出最佳組合。
   3. 收斂檢查：若，則迭代結束，為最佳策略。否則，重複(1)。