DeepMind Teaching by David Silver

視頻課程鏈接（Youtube資源，需梯子）：https://youtu.be/lfHX2hHRMVQ

文章目錄

• • DeepMind Teaching by David Silver
  • • 1. 馬爾可夫過程（Markov Processes）
    • 2. 馬爾可夫回報過程（Markov Reward Processes）
    • 3. 馬爾可夫決策過程（Markov Decision Processes）
    • 4. 動態(tài)規(guī)劃（Planning by Dynamic Programming）
    • • 4.1 利用動態(tài)規(guī)劃求解MDP問題
      • 4.2 策略評估（Policy Evaluation）和策略迭代（Policy Iteration）
      • 4.3 值迭代（Value Iteration）
      • 4.4 小結(jié)

1. 馬爾可夫過程（Markov Processes）

馬爾可夫過程是一種形式化描述強化學(xué)習(xí)過程中的環(huán)境的數(shù)學(xué)模型，與字面理解的意思可能有所不同，馬爾可夫過程并沒有涉及到跟“過程”相關(guān)的問題，僅僅只是對“環(huán)境”進行了定義。一個問題要想被定義為馬爾可夫問題，必須具備以下幾個特征：

• 整個環(huán)境需要完全可觀測（fully observable），這意味著整個環(huán)境中不可以出現(xiàn)部分可觀測。
• 環(huán)境中下一時刻的狀態(tài)（$S_{t+1}$）只與當(dāng)前的狀態(tài)（$S_t$）有關(guān)，不能依賴于之前的歷史狀態(tài)，即：

$$P(S_{t+1}|S_t)=P(S_{t+1}|S_1,...,S_{t?1},S_t)$$

幾乎所有的RL相關(guān)的問題都可以轉(zhuǎn)化為MDP問題，部分可觀測的問題（POMDP）問題同樣也可以轉(zhuǎn)換為MDP問題，因此MDP問題是所有問題的核心基礎(chǔ)問題。

狀態(tài)轉(zhuǎn)移矩陣（State Transition Matrix

在馬爾可夫過程中，一個狀態(tài)$s$在被執(zhí)行了一個行為$a$后會轉(zhuǎn)變?yōu)橄乱粋€狀態(tài)$s^{\prime }$，但從 $s\to s^{\prime }$ 的轉(zhuǎn)移并不一定是百分之百成功的，因此定義一個狀態(tài)轉(zhuǎn)移概率來描述狀態(tài)是否能夠成功轉(zhuǎn)移的概率：
$$P_{s{s}^{\prime }}=P[S_{t+1}=s^{\prime }|S_t=s]$$
由于在馬爾可夫過程中，環(huán)境是完全可觀測的，因此所有可能的出現(xiàn)狀態(tài)都能被觀測到，我們把每一個可能的狀態(tài)列舉出來，并統(tǒng)計他們的狀態(tài)轉(zhuǎn)移概率，最終可以得到整個環(huán)境下狀態(tài)轉(zhuǎn)移矩陣為：
$$M=?\begin{array}{cccc}{P}_{11}& P_{12}& ...& P_{1n}\\ .& & & \\ .& & & \\ .& & & \\ P_{n1}& P_{n1}& ...& P_{nn}\end{array}?$$
note: 矩陣中每一行加起來的和為1。

馬爾可夫過程的定義

馬爾可夫過程（馬爾科夫鏈）是一個隨機過程，是一個由若干個隨機的、具有馬爾可夫性質(zhì)的狀態(tài)（$S$）組成的序列。一條 Markov Chain 是一個元組<$S,P$>，由2個部分組成：

• $S\to$ 一個狀態(tài)（state）的集合
• $P\to$ 一個狀態(tài)轉(zhuǎn)移概率矩陣

2. 馬爾可夫回報過程（Markov Reward Processes）

在第1章中我們講了 Markov 決策過程，是一個的狀態(tài)的集合和一個狀態(tài)轉(zhuǎn)移概率矩陣，但我們?nèi)绾稳ピu判在一個狀態(tài)下我們應(yīng)該往哪一個狀態(tài)去轉(zhuǎn)移是最優(yōu)的呢？這里我們將引入回報（Reward）來對狀態(tài)轉(zhuǎn)移效用進行一個量化表示。

馬爾可夫回報過程的定義

馬爾可夫回報過程是在馬爾可夫決策過程上添加了匯報函數(shù) $R$ 和折扣因子 $\gamma$，是一個4元組 <$S,P,R,\gamma$> ：

• $S\to$ 一個狀態(tài)（state）的集合
• $P\to$ 一個狀態(tài)轉(zhuǎn)移概率矩陣
• $R\to$ 一個用于計算回報的函數(shù)，計算的是在 $t$ 時刻下的即時回報
• $\gamma \to$ 一個折扣因子，用于做未來回報計算時的衰減系數(shù)，$\gamma \in (0,1)$

上面所提到的回報函數(shù) $R$ 只是用于計算在某一時刻下某一狀態(tài)的即時回報，但為了能更有遠見的評估當(dāng)前這個狀態(tài)的效用，我們通常會計算包含從該時刻起一直到最后一個時刻，這個狀態(tài)之后所有可能的轉(zhuǎn)移到的后續(xù)狀態(tài)所引起的回報總值 $G_t$：
$$G_t=R_{t+1}+\gamma R_{t+2}+...=\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$$

值函數(shù)（Value Function

上面說到在MRP問題中，我們通常會引入總回報 $G$ 來表示一個狀態(tài)的長遠回報，但由于 $G$ 只是計算的一個 具體sample 中的具體得分，而真實的 $G$ 是一個隨機變量，我們是無法通過一次采樣就確定其取值，因此我們引入值函數(shù) $v(s)$ 來描述狀態(tài) $S_t$ 的效用，使用期望值來代替一次采樣中的具體得分：
$$v(s)=E[G_t|S_t=s]$$
值函數(shù)可以通過貝爾曼方程（Bellman Equation）拆分為2個部分：

• 當(dāng)前狀態(tài) $S_t$ 的即時回報 $R_{t+1}$

• 衰減后的下一個狀態(tài) $S_{t+1}$ 的值函數(shù)回報 $\gamma v(S_{t+1})$

因此，當(dāng)前狀態(tài)值函數(shù)又可以表示為當(dāng)前狀態(tài)的既時回報加上下一個狀態(tài)的值函數(shù)：$v(S_t)=R_{t+1}+\gamma v(S_{t+1})$。

考慮到狀態(tài)轉(zhuǎn)移是有概率的，即有可能出現(xiàn) $S1\to S2$，也有可能出現(xiàn) $S1\to S3$，下一時刻的狀態(tài)是有概率進行隨機轉(zhuǎn)移的，這個我們之前使用狀態(tài)轉(zhuǎn)移概率矩陣 $P$ 來描述，我們現(xiàn)在將其引入進來：
$$v(s)=R_{t+1}+\gamma Pv(s^{\prime })$$
用 $v(1)$ 代表狀態(tài)1的值函數(shù)，$R1$ 代表狀態(tài)1的即時回報值，可以得到值函數(shù)的計算公式：
$$?\begin{array}{c}v(1)\\ v(2)\\ .\\ .\\ .\\ v(n)\end{array}?=?\begin{array}{c}R1\\ R2\\ .\\ .\\ .\\ Rn\end{array}?+\gamma ?\begin{array}{c}P(11)...P(1n)\\ .\\ .\\ .\\ P(n1)...P(nn)\end{array}??\begin{array}{c}v(1)\\ v(2)\\ .\\ .\\ .\\ v(n)\end{array}?$$

3. 馬爾可夫決策過程（Markov Decision Processes）

馬爾可夫決策過程（MDP）是在馬爾可夫回報過程（MRP）上加上“決策”這一個元素，決策我們使用 $A$ 來表示，代表 agent 的決策行為，因此MDP是一個5元組問題：<$S,P,A,R,\gamma$>：

• $S\to$ 一個狀態(tài)（state）的集合
• $P\to$ 一個受行為影響的狀態(tài)轉(zhuǎn)移概率矩陣，$P_{s{s}^{\prime }}^a=P[S_{t+1}=s^{\prime }|S_t=s,A_t=a]$
• $A\to$ 一個有限動作集
• $R\to$ 一個用于計算回報的函數(shù)，$R_s^a=E[R_{t+1}|S_t=s,A_t=a]$
• $\gamma \to$ 一個折扣因子，用于做未來回報計算時的衰減系數(shù)，$\gamma \in (0,1)$

策略（Policy）

策略 $\pi$ 是指在給定狀態(tài)下，采取各種行為的一種概率分布：
$$\pi (a|s)=P[A_t=a|S_t=s]$$
note：策略 $\pi$ 直接決定了 agent 的行為選擇，在 MDP 問題中，策略 $\pi$ 只能與當(dāng)前的狀態(tài)相關(guān)，歷史狀態(tài)無法對策略起到任何影響。這是因為我們在定義 MP 問題的時候就已經(jīng)定義了，下一個時刻的狀態(tài)與歷史狀態(tài)是完全獨立的（參考第一章-馬爾可夫過程特性）。

給定一個MDP問題$M=<S,P,A,R,\gamma >$，再給定一個策略 $\pi$，產(chǎn)生的狀態(tài)序列 $S1,S2,S3,...$ 就是一個馬爾可夫過程 （MP）<$S,P^{\pi }$>。產(chǎn)生的狀態(tài)-回報序列 $S1,R2,S_2,...$ 就是一個馬爾可夫回報過程（MRP）<$S,P^{\pi },R,\gamma$>。

MDP問題中的值函數(shù)

在MRP問題中，我們引入過值函數(shù)來描述一個狀態(tài)的好壞，但在MRP問題中是沒有涉及到策略 $\pi$ 的，因此在MDP問題中，同一個狀態(tài)在不同策略下所得到的評分也有可能不同，因此我們在評價一個狀態(tài)的好壞時，還需要考慮目前所使用的策略 $\pi$，即：
$$V_{\pi }(s)=E_{\pi }[G_t|S_t=s]$$
由于在MDP問題中，引入了最為關(guān)鍵的元素 $A$，即 agent 的行為，那么在有些時候，我們不僅需要想要評價一個策略的好壞，同時還想要知道 agent 做出的行為的具體效用好壞，因此我們還需要一種能夠描述行為 $a$ 效用好壞的值函數(shù)：
$$q_{\pi }(s,a)=E[G_t|S_t=s,A_t=a]$$
通常，$q_{\pi }$ 稱為行為值函數(shù)， $V_{\pi }$ 稱為狀態(tài)值函數(shù)。在行為值函數(shù)中，一般不會單獨評價一個動作的效用，而是會評價動作-狀態(tài)的效用，動作的效用與狀態(tài)是緊密相關(guān)的，同樣的動作在不同狀態(tài)下產(chǎn)生的效用不同，同樣的狀態(tài)采取不同的行為效用也會不同。

狀態(tài)值函數(shù)和行為值函數(shù)之間的轉(zhuǎn)換

通過貝爾曼方程（Bellman Equation），我們可以將行為值函數(shù)拆解為：當(dāng)前狀態(tài)下得到的即時回報 + 下一個狀態(tài)的狀態(tài)值函數(shù)，這樣我們就建立起了 t 時刻的行為值函數(shù)和 t+1 時刻的狀態(tài)值函數(shù)的關(guān)系，表達式為：
$$q_{\pi }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^{a}V(s^{\prime })$$
在同一時刻，一個狀態(tài)的值函數(shù)應(yīng)該等于所有可能的行為產(chǎn)生的行為值函數(shù)之和，即：
$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)q(s,a)$$

狀態(tài)值函數(shù)的求解形式

通過貝爾曼方程，我們可以把狀態(tài)值函數(shù)表示為：
$$V_{\pi }=R^{\pi }+\gamma P^{\pi }{V}_{\pi }$$
進而可以轉(zhuǎn)化為：
$$\begin{gathered} (I?\gamma P^{\pi })V_{\pi }=R^{\pi } \\ \downarrow \\ {V}_{\pi }=(I?\gamma P^{\pi }{)}^{?1}{R}^{\pi } \end{gathered}$$

（具體怎么應(yīng)用這個矩陣求解的示例參見這個鏈接：https://www.cnblogs.com/initial-h/p/9321961.html）

最優(yōu)策略的求解

在一個環(huán)境中可能存在多種策略 $\pi$，當(dāng)一個策略的值函數(shù)能夠大于其他所有策略時（$V_{\pi }(s)>V_{?}(s)$，則說明策略 $\pi$ 為最優(yōu)策略。最優(yōu)策略可以通過最優(yōu)行為值函數(shù)（$q_{?}(s,a)$）來確定，最高效用行為的概率為1，其余行為取0：
KaTeX parse error: Got function '\newline' with no arguments as argument to '\begin{array}' at position 1: \?n?e?w?l?i?n?e?
因此一旦我們有了最優(yōu)的行為值函數(shù) $q_{?}(s,a)$ 我們就能找到一個最優(yōu)策略 $\pi$，我們使用最優(yōu)貝爾曼方程進行求解，我們知道，一個狀態(tài)的值函數(shù)的最大取值應(yīng)當(dāng)是該策略下最優(yōu)行為的行為值函數(shù)取值：
$$v_{?}(s)=ma{x}_a{q}_{?}(s,a)$$
而行為值函數(shù) $q_{?}(s,a)$ 的取值可以轉(zhuǎn)換為當(dāng)前的即時回報加上下一時刻各個狀態(tài)的狀態(tài)值函數(shù)之和：
$$q_{?}(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in s}{P}_{s{s}^{\prime }}^a{v}_{?}(s^{\prime })$$
將 $v(s^{\prime })$ 換算成 $q(s,a)$ 的形式，可以得到最終結(jié)果：
$$q_{?}(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in s}{P}_{s{s}^{\prime }}^{a}ma{x}_{a^{\prime }}{q}_{?}(s^{\prime },a^{\prime })$$
以上我們就得到了一個遞歸的式子，想要計算此刻最優(yōu)的行為值函數(shù)取值只需要在之后的狀態(tài) $s^{\prime }$ 中選取具有最大效用的行為 $a^{\prime }$ 即可。遺憾的是，貝爾曼最優(yōu)方程并不是一個線性方程，我們需要使用迭代的方法進行求解，包括：值迭代、策略迭代、Q-Learning等方法，在之后的章節(jié)會著重討論。

4. 動態(tài)規(guī)劃（Planning by Dynamic Programming）

如何理解動態(tài)規(guī)劃？“動態(tài)” 是指我們每次只能看到整個任務(wù)的 “一部分” ，整個任務(wù)是由若干個連續(xù)的部分組成起來的一個任務(wù)串，動態(tài)規(guī)劃的核心思想就是將一個問題分解成若干個子問題再進行求解。

舉個例子來說：公司里面都有一定的組織架構(gòu)，可能有高級經(jīng)理、經(jīng)理、總監(jiān)、組長然后才是小開發(fā)。到了一年一度的考核季的時候，公司要挑選出三個最優(yōu)秀的員工。一般高級經(jīng)理會跟手下的經(jīng)理說，你去把你們那邊最優(yōu)秀的3個人報給我，經(jīng)理又跟總監(jiān)說你把你們那邊最優(yōu)秀的人報給我，經(jīng)理又跟組長說，你把你們組最優(yōu)秀的三個人報給我，這個其實就動態(tài)規(guī)劃的思想。將整個公司 “最優(yōu)秀人員” 的問題（原問題）分解為各個部門“最優(yōu)秀的人員”（子問題），最終再根據(jù)所有部門“最優(yōu)秀的人員”（子問題）來進行比較推導(dǎo)出整個公司“最優(yōu)秀的人員”（父問題）。一般來講，動態(tài)規(guī)劃問題可分為以下4個步驟來解決：

劃分狀態(tài)：即劃分子問題，例如上面的例子，我們可以認為每個組下面、每個部門、每個中心下面最優(yōu)秀的3個人，都是全公司最優(yōu)秀的3個人的子問題

狀態(tài)表示：即如何讓計算機理解子問題。上述例子，我們可以實用f[i][3]表示第i個人，他手下最優(yōu)秀的3個人是誰。

狀態(tài)轉(zhuǎn)移：即父問題是如何由子問題推導(dǎo)出來的。上述例子，每個人大Leader下面最優(yōu)秀的人等于他下面的小Leader中最優(yōu)秀的人中最優(yōu)秀的幾個。

確定邊界：確定初始狀態(tài)是什么？最小的子問題？最終狀態(tài)又是什么。例如上述問題，最小的子問題就是每個小組長下面最優(yōu)秀的人，最終狀態(tài)是整個企業(yè)，初始狀態(tài)為每個領(lǐng)導(dǎo)下面都沒有最優(yōu)名單，但是小組長下面擁有每個人的評分。

以上內(nèi)容引自：沙茶敏碎碎念的動態(tài)規(guī)劃入門博客

4.1 利用動態(tài)規(guī)劃求解MDP問題

動態(tài)規(guī)劃在MDP問題中通常用于以下兩個方面：

• 評判一個策略 $\pi$ 的好壞：在給定一個MDP <$S,P,A,R,\gamma$> 和一個策略 $\pi$ 的情況下， 計算該策略 $\pi$ 的評價函數(shù) $v_{\pi }$。
• 訓(xùn)練出一個好的策略 ${\pi }_{?}$：在一個給定的MDP <$S,P,A,R,\gamma$> 中，求解一個最優(yōu)策略 ${\pi }_{?}$。

4.2 策略評估（Policy Evaluation）和策略迭代（Policy Iteration）

策略評估是指給定一個固定的策略 $\pi$，我們?nèi)绾卧u判這個策略的好壞？通常我們使用貝爾曼方程的迭代法來得到求解：

首先我們隨機化一個狀態(tài)值函數(shù) $v_1$，$v_1$ 是一個表，其存放了當(dāng)前所有狀態(tài)的效用值，$v_1(s_1),v_1(s_2),...，v_1(s_n)$。

由于一開始的 $v_1$ 是一個隨機出來的表，不能正確的評價場景中狀態(tài)的正確效用，我們需要讓這個表中的效用值變成在采取策略 $\pi$ 下的真實狀態(tài)效用值，因此我們會不斷更新這個表，從 $v_1\to v_2\to ...\to v_{\pi }$，最終$v_{\pi }$ 就是一個在策略 $\pi$ 下，所有狀態(tài)的效用值表。

上面說到我們會不斷更新 $v$ 表，最終更新為一個 $v_{\pi }$ 表，但我們?nèi)绾芜M行更新這個表中各個狀態(tài)的效用值呢？我們先來看第一種方法 —— 同步backup法：

• 在第 k+1次迭代中：
  • 對于每一個狀態(tài) $s\in S$
  • 根據(jù) $v_k(s^{\prime })$ 的值來更新 $v_{k+1}(s)$ ，意思就是利用上一次迭代中的下個狀態(tài) $s^{\prime }$ 來更新這次迭代的當(dāng)前狀態(tài) $s$ 的效用值。

用數(shù)學(xué)公式來表示：
$$v_{k+1}(s)=\sum _{a\in A}\pi (a|s)(R_s^a+\gamma \sum _{s\in S}{P}_{s{s}^{\prime }}^a{v}_k(s^{\prime }))$$
上述式子表達的意思是，在計算第 $k+1$ 次迭代的狀態(tài) $s$ 的效用值時，用當(dāng)前得到的即時回報值 $R_s^a$ 再加上上一輪迭代表中的 $s^{\prime }$ 的效用值 $v_k(s^{\prime })$，可以簡化表示為：
$$v^{k+1}=R^{\pi }+\gamma P^{\pi }{v}^k$$

同步backup法應(yīng)用舉例

一個 4x4 的方格，一共有 4 種 action（上下左右），每走一步（除了走到灰色格子內(nèi)）得到的 reward 都是 -1，目標是使得 agent 學(xué)會走到左上或右下的兩個灰色格子中去。我們給定一個策略 $\pi$，該策略在任意一個狀態(tài)下都隨機進行行為選擇（即上下左右行為的概率都是0.25），一個格子代表一個state，我們?nèi)绾稳ビ嬎阍诓呗?$\pi$ 下每一個 state 的 $v$ 值？

下圖左邊是我們的 $v$ 表迭代的過程，我們先隨機初始化 $v$ 表中所有狀態(tài)的取值為0，在下一次迭代中（k=1），我們通過 backup 法一次計算每一個格子的狀態(tài)值，這里用格子1（第一排第二個）進行舉例：由于上下左右四個行為的采取概率均等（隨機選取動作），即 $\pi (up|?)=\pi (down|?)=\pi (left|?)=\pi (right|?)=0.25$，因此根據(jù)公式 $v^{k+1}=R^{\pi }+\gamma P^{\pi }{v}^k$ （$\gamma =1$）可得 $v_1(s_1)=?1+0.25?0+0.25?0+0.25?0+0.25?0=?1$。在k=2 的迭代中時，由于向上走后會停留在原地，因此向上走后轉(zhuǎn)移到的狀態(tài)還是自身，同樣帶公式計算可得到計算結(jié)果：$v_2(s_1)=?1+0.25?(?1)+0.25?(?1)+0.25?(?1)+0.25?0=?1.75\approx ?1.7$。

上圖展示了前 3 輪迭代結(jié)果，一直迭代下去，$v$ 表一定會收斂（有數(shù)學(xué)公式證明，這里不做講解），收斂后的 $v$ 表代表了在我們給定的策略 $\pi$ 下每一個狀態(tài)的真實取值。此時我們不僅得到了策略 $\pi$ 下的狀態(tài)值表，同時我們還可以根據(jù)這個 $v$ 表通過貪婪算法得到一個新的更優(yōu)策略 ${\pi }^{\prime }$（下圖右），即在一個狀態(tài)下每次都選擇具有最大狀態(tài)值的狀態(tài)作為下一個轉(zhuǎn)移狀態(tài)，這個新策略 ${\pi }^{\prime }$ 明顯優(yōu)于我們一開始給定的隨機選擇行為的策略 $\pi$（在k=3的時候最優(yōu)策略就已經(jīng)出現(xiàn)了，之后再沒有變化過）。

上面的整個示例展示了 backup 法的兩個功能：

• 給定一個策略 $\pi$，評價在這個策略下各狀態(tài)的好壞（$v_{\pi }$ 表）
• improve 策略 $\pi$，得到一個更好的策略 ${\pi }^{\prime }$

在大多數(shù)情況下，我們需要重復(fù)這兩個步驟：評價一個給定策略 $\to$ 改善這個策略得到新策略 $\to$ 評價新策略 $\to$ 改善新策略得到另一個新策略 $\to$ ……，因此這是一個 **Evaluation - Improve **的迭代循環(huán)過程，這個過程我們就稱之為 Policy Iteration（策略迭代）。在若干個策略迭代過程后，策略 ${\pi }^{\prime }$ 會收斂到最優(yōu)策略 ${\pi }_{?}$ ，最優(yōu)策略就是我們最終的求解策略了。

note：改善策略（Improvement）的方法有許多種，上面的實例我們使用的是貪婪策略（greedy）進行的策略提升，但大多數(shù)時候貪婪策略能夠取得很好的結(jié)果。

4.3 值迭代（Value Iteration）

在策略迭代的部分我們提到，我們在最開始需要給定一個策略，并對該策略進行不斷的 improve，通常我們選擇等概率的行為選擇策略作為初始策略，那我們能不能有一種方法完全不需要一開始給定初始策略呢？其實我們可以發(fā)現(xiàn)，在策略迭代的方法中我們給定初始策略就是為了得到一張 $v$ 表，我們是根據(jù)這個 $v$ 表來找出最優(yōu)策略的，如果我們能不依賴一個初始策略就能計算出 $v$ 表，那我們就能解決這個問題了，這就是值迭代法的由來。

首先我們思考，什么算是最優(yōu)策略？最優(yōu)策略是指不僅能在當(dāng)前獲取最大的行為效用值，在下一個狀態(tài)應(yīng)該也能取得最大的行為效用值，在之后的每一個狀態(tài)都應(yīng)該取得最大的行為效用值。按照這個定義，假定我們已知了一個最優(yōu)策略 $v_{?}$，那么狀態(tài) $s$ 在該策略下的狀態(tài)值函數(shù) $v_{?}(s)$ 可以分解為：
$$v_{?}(s)=argma{x}_a{R}_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{?}(s^{\prime })$$
上述式子表達了當(dāng)前狀態(tài) $s$ 的狀態(tài)值等于采取當(dāng)前所有行為里有著最高效用值的行為得到的回報 + 下一個狀態(tài)在最優(yōu)策略下的狀態(tài)值。因此，我們可以從后往前開始迭代計算了，由于終止狀態(tài) $v(s_t)$ 的得分我們可知，終止狀態(tài)的前一個狀態(tài) $v(s_{t?1})$ 的值 = 采取最大效用行為得到的回報值 $R_{s_{t?1}}$+ 終止狀態(tài)的狀態(tài)值 $v(s_t)$，再前一個狀態(tài) $v(s_{t?2})$ 的狀態(tài)值 = 采取最大效用行為得到的回報值 $R_{s_{t?2}}$ + 后一個狀態(tài)的狀態(tài)值 $v(s_{t?1})$，…，依次迭代就可以求出每個狀態(tài)的狀態(tài)值了，$v$ 表也就求解完成了。

Value Iteration 求解法舉例

以下是一個 4x4 的方格，左上角是目標點，我們需要求出在任意一個格子到目標點的最短路徑。我們把每一個格子看成是一個狀態(tài)，每走一步得到的 reward 是 -1。下圖表示了整個問題的求解流程：初始化所有狀態(tài)值都為0，緊接著每一個格子都選擇上下左右臨近格子中狀態(tài)值最大的那個格子，并用即時回報 -1 加上最大值鄰居格子的狀態(tài)值（參照上面的公式）。一直這么迭代下去，直到第 7 次的時候該表格收斂了，求到了最終的結(jié)果。有了 $v$ 表我們的策略就相應(yīng)的出現(xiàn)了，對于任意一個狀態(tài)選擇最大狀態(tài)值的鄰居格子就能夠最快的到達終點格子了。

值迭代的方法要求人們需要枚舉出該狀態(tài) $s$ 之后所有可能到達的狀態(tài) $s^{\prime }$，并選擇出具有最高效用值的狀態(tài)作為自己的后續(xù)狀態(tài)；并且整個問題必須存在終點（end point），畢竟是從后向前推的思路，如果環(huán)境無法全部可知或者終點狀態(tài)不存在就無法使用該方法進行問題求解了。

4.4 小結(jié)

對整個利用動態(tài)規(guī)劃解決 MDP 問題的方法進行一個歸納總結(jié)：

功能貝爾曼方程算法

狀態(tài)值估計（$v$ 表求解）	貝爾曼期望方程	迭代策略評估法（Iterative Policy Evaluation）
策略學(xué)習(xí)	貝爾曼期望方程 + 貪婪策略	策略迭代法（Policy Iteration）
策略學(xué)習(xí)	貝爾曼最優(yōu)方程	值函數(shù)迭代法（Value Iteration）

總結(jié)

以上是生活随笔為你收集整理的DeepMind 的马尔可夫决策过程（MDP）课堂笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。