模型匯總19 強化學習（Reinforcement Learning）演算法基礎及分類

01-25

前一期介紹了強化學習基礎知識，今天，主要介紹強化學習各種演算法理論基礎。處於一個state空間下，Agent一系列動作決策問題，類似於一個馬爾科夫決策過程（Markov Decision Process， MDP），即當前的狀態只與前一個狀態有關，因此，Agent面臨的其實是在某個狀態State（環境下），一個最優動作（Action）序列的決策問題。動態規劃和強化學習都是基於馬爾科夫鏈，求解一個最優動作序列的方法。動態規劃的方法主要解決當MDP環境下，Agent的狀態轉移概率和回報函數模型已知的決策問題；強化學習主要處理二者未知情況下，最優動作序列的決策問題。

1、馬爾科夫決策過程（Markov Decision Process，MDP）概念

強化學習隨機過程定義：

假設存在一個由{S，A，D，P，r，J}六元組描述的，與Agent決策有關的，離散時間隨機決策過程，其中，S表示有限的環境狀態空間，A表示有限的動作空間，D表示S的初始狀態概率分布。P表示Agent的狀態轉移概率，屬於[0,1]，是P（s，a，s』）的簡寫，表示在狀態s下，執行動作s，轉移到狀態s』的概率函數。R表示回報函數，是r（s，a，s』）：S X A X S』的簡寫，表示Agent根據轉移概率P（s，a，s』）動作後，Agent得到的立即回報（獎賞）函數。J表示動作序列決策的目標函數，因此，R是一種「短視」評價信號，J是一種「遠視」評價信號。

馬爾科夫性質：未來狀態只與當前狀態有關，與歷史狀態無關，即P（St+1|St）= P（St+1|S1，S2....S

t）。馬爾科夫性質的意義：當前狀態S包含了歷史Step的所有相關信息，且當前狀態足夠用於預測未來的狀態，因此，只要當前狀態，歷史狀態就可以拋掉。

馬爾科夫過程或馬爾科夫鏈定義：具有馬爾科夫性質的隨機過程，可以採用一個二元組<S，P>表示，其中S是一個有限的狀態集合，P表示狀態的轉移概率（從一個狀態s，轉移到另一個狀態s』的概率），Pss』=P（St+1=S』|St=S）。

Markov Reward Process（MRP）與Markov Decision Process（MDP）的聯繫與區別：

MRP是MDP的基礎，MRP由<S,P,R,r>四元組構成，S、P、R與上面定義已知，分別表示隨機過程的狀態空間，轉移概率矩陣和之間獎勵函數，r表示折扣因子（後面會仔細講）。

MDP是一個與決策相關的MRP過程，隨機過程中所有狀態都具有馬爾科夫性質。MDP由<S,A,P,R,r>構成，比MRP多了一個A，表示隨機過程中，有限的動作集合。

在基於馬爾科夫過程的強化學習序列決策過程中，Agent從目前狀態s調到下一個狀態s』的轉移概率P和立即回報R，只與當前的狀態s有關，與歷史的狀態和動作無關，這樣可以簡化決策過程目標函數J的求解問題，也是Bellman方程的基礎。比如，在馬爾科夫決策過程環境下，狀態轉移概率求解可以大大簡化：

P（S=St，A=At，S』=S（t+1））=Pr{S（t+1）|（St，At，St-1，At-1，.....S0，A0）}=Pr{St+1|St，At}

馬爾科夫決策環境下，動作序列決策過程的目標函數J有三種表示形式，即有限序列總回報目標函數、無限序列折扣總回報目標函數和有限序列平均回報目標函數。

有限總回報目標函數為：

（1）

其中，rt表示t時刻的立即回報，N表示序列長度，即馬爾科夫鏈長度。

無限折扣總回報目標函數：

（2）

其中，tao屬於（0,1]表示折扣因子。

有限序列平均回報目標函數：

（3）

在MDP決策過程中，一般都採用無限折扣回報目標函數和有限平均回報目標函數求解J。為什麼？因為實際情況下，大多數的馬爾科夫Reward和決策過程都是包含折扣的，這樣做具有以下優點：

（1）、方便計算打折後的Reward，與實際情況相符。

（2）、避免出現無限循環的馬爾科夫決策過程。

（3）、把直接回報（immediate reward）R與未來回報（delayed reward）區分開來，直接回報影響更大，符合人或動物傾向於選擇直接回報實際情況。

（4）、描述了我來回報對於總回報影響的不確定性。

此外，可以發現，平均回報是折扣回報一個特例，當折扣回報目標函數中的折扣因子取值為1時，兩個目標函數等價。

2、策略、值函數和Bellman方程

策略（policy）pi：S -> A -> [0,1]，確定了Agent在狀態S下，選擇動作A的概率。在MDP環境下，當策略確定後，MDP對應的值函數（value function）可以分為：只與狀態有關的狀態值函數Vpi（s），與狀態->動作相關的動作值函數Qpi（s，a）。與直接回報R不同，值函數（狀態值函數V或動作值函數Q）是對未來回報函數的一種預測，目的是為了獲得更多的回報。因此，Agent進行動作選擇時，不是根據直接回報R進行選擇，而是根據值函數回報進行選擇。

狀態值函數Vpi（s）對應的是一個馬爾科夫獎直接獎勵過程（Markov Reward Process， MRP），描述值函數的值，僅有當前和未來的直接Reward相關，與動作無關。狀態值函數表達式如公式（4）所示：

（4）

狀態值函數表示Agent從狀態s開始，根據策略pi選擇動作所獲得的期望總回報。P（.）和R（.）分別表示對應的轉移概率和回報函數。

公式（4）也是著名的Bellman方程。值函數Vpi（St）的值可以被分成兩個部分：直接回報r（t+1）和折扣的未來回報rV（St+1），因此，可以按照狀態序列對值函數進行拆解，通過迭代求和方式得到值函數V（s）的值。

基於Bellman方程求解狀態值函數V（s）的值：

把值函數的表達式簡化，可以得到簡化的Bellman方程表達式：

圖中，V（s）對應公式（4）中Vpi（s），表示當前狀態的值函數，V（s』）對應公式V（St+1）。狀態值函數可以看做與轉移概率矩陣Pss』和直接回報Rs相關的線性防長，在狀態轉移矩陣和直接回報已知條件下，很容易求解狀態值函數的值。對於比較短的MRP過程的狀態值函數，可以直接計算V（s）的值。但對於比較長的MRP過程狀態值函數求解，一般還是通過迭代方法求解，如：動態規劃方法（Dynamic Programming）、蒙特卡洛方法（Monte-Carlo Evaluation）、時間差分學習（TD Learning）方法。

動作值函數Qpi（s，a）對應的是一個MDP過程。類似於狀態值函數，動作值函數Qpi（s，a）表示agent從狀態s、動作a出發，根據策略pi進行動作選擇，所獲得的期望回報，表達式如（5）所示：