強化學習入門基礎-馬爾可夫決策過程（MDP）

2021 年 1 月 3 日
筆記

作者：YJLAugus 部落格： //www.cnblogs.com/yjlaugus 項目地址：//github.com/YJLAugus/Reinforcement-Learning-Notes，如果感覺對您有所幫助，煩請點個⭐Star。

MDP背景介紹

Random Variable

隨機變數（Random Variable），通常用大寫字母來表示一個隨機事件。比如看下面的例子：

$X$: 河水是鹹的

$Y$: 井水是甜的

很顯然，$X$, $Y$兩個隨機事件是沒有關係的。也就是說$X$和$Y$之間是相互獨立的。記作：

\[\large
X \bot Y
\]

Stochastic Process

對於一類隨機變數來說，它們之間存在著某種關係。比如：

$S_{t}$：表示在 $t$ 時刻某支股票的價格，那麼 $S_{t+1}$ 和 $S_t$ 之間一定是有關係的，至於具體什麼樣的關係，這裡原先不做深究，但有一點可以確定，兩者之間一定存在的一種關係。隨著時間 $t$ 的變化，可以寫出下面的形式：

\[\large
…S_t, S_{t+1},S_{t+2}…
\]

這樣就生成了一組隨機變數，它們之間存在著一種相當複雜的關係，也就是說，各個隨機變數之間存在著關係，即不相互獨立。由此，我們會把按照某個時間或者次序上的一組不相互獨立的隨機變數的這樣一個整體作為研究對象。這樣的話，也就引出了另外的一個概念：隨機過程（Stochastic Process）。也就是說隨機過程的研究對象不在是單個的隨機變數，而是一組隨機變數，並且這一組隨機變數之間存在著一種非常緊密的關係（不相互獨立）。記作：

\[\large
\lbrace S_t \rbrace ^\infty_{t=1}
\]

Markov Chain/Process

馬爾科夫鏈（Markov Chain）即馬爾可夫過程，是一種特殊的隨機過程——具備馬爾可夫性的隨機過程。

馬爾可夫性：（Markov Property）: 還是上面股票的例子，如果滿足 $P(S_{t+1} \mid S_t,S_{t-1}…S_1) = P(S_{t+1}\mid S_t)$，即具備了馬爾可夫性。簡單來說，$S_{t+1}$ 和$S_t$之間存在關係，和以前的時刻的沒有關係，即只和「最近的狀態」有關係。
現實例子：下一個時刻僅依賴於當前時刻，跟過去無關。比如：一個老師講課，明天的講課狀態一定和今天的狀態最有關係，和過去十年的狀態基本就沒關係了。
最主要考量：為了簡化計算。$P(S_{t+1} \mid S_t,S_{t-1}…S_1) = P(S_{t+1}\mid S_t)$ 如果 $S_{t+1}$ 和 $S_t,S_{t-1}…S_1$ 都有關係的話，計算的話就會爆炸了。

馬爾可夫鏈/過程即滿足馬爾可夫性質的隨機過程，記作：

\[\large P(S_{t+1}) \mid S_t,S_{t-1}…S_1) = P(S_{t+1}\mid S_t)
\]

State Space Model

狀態空間模型（State Space Model），常應用於 HMM,Kalman Filterm Particle Filter，關於這幾種這裡不做討論。在這裡就是指馬爾可夫鏈 + 觀測變數，即Markov Chain + Obervation

如上圖所示，s1-s2-s3為馬爾可夫鏈，a1, a2, a3為觀測變數，以a2為例，a2隻和s2有關和s1, s3無關。狀態空間模型可以說是由馬爾可夫鏈演化而來的模型。記作：

Markov Chain + Obervation

Markov Reward Process

馬爾可夫獎勵過程（Markov Reward Process），即馬爾可夫鏈+獎勵，即：Markov Chain + Reward。如下圖：

舉個例子，比如說你買了一支股票，然後你每天就會有「收益」，當然了這裡的收益是泛化的概念，收益有可能是正的，也有可能是負的，有可能多，有可能少，總之從今天的狀態$S_t$ 到明天的狀態 $S_{s+1}$ ，會有一個reward。記作：

Markov Chain + Reward

Markov Decision Process

馬爾可夫決策過程（Markov Decision Process），即馬爾可夫獎勵過程的基礎上加上action，即：Markov Chain + Reward + action。如果還用剛才的股票為例子的話，我們只能每天看到股票價格的上漲或者下降，然後看到自己的收益，但是無法操作股票的價格的，只有看到份，只是一個「小散戶」。這裡的馬爾可夫決策過程相當於政策的制定者，相當於一個操盤手，可以根據不同的狀態而指定一些政策，也就相當於 action。

在馬爾可夫決策過程中，所有的狀態是我們看成離散的，有限的集合。所有的行為也是離散有限的集合。記作：

\[\large
\enclose{box}{
\it S: \quad state \quad set \quad \quad \quad\quad\quad\quad\quad\quad\quad\quad S_t \\
\it A: \quad action \quad set ,\quad \quad \forall s \in S,A_{(s)} \quad\quad A_t\\
\it R: \quad reward \quad set \quad\quad\quad\quad\quad\quad\quad\quad\quad R_t, R_{(t+1)} \\
}
\]

對於上述公式簡單說明，$S_t$ 用來表示某一個時刻的狀態。$A_{(s)}$ 表示在某一個狀態時候的行為，這個行為一定是基於某個狀態而言的，假設在$t$ 時刻的狀態為$S$ 此時的action記作 $A_t$ 。$R_t 和 R_{(t+1)}$ 只是記法不同，比如下面的例子：從$S_t$狀態經過 $A_t$ 到$S_{t+1}$狀態，獲得的獎勵一般記作$R_{(t+1)}$。也就是說$S_t$， $A_t$ ，$R_{(t+1)}$ 是配對使用的。

Summary

MDP動態特性

Markov Chain

馬爾可夫鏈只有一個量——狀態。比如 $S\in(s_1,s_2,s_3,s_4,s_5,s_6,s_7,s_8,s_9,s_{10})$ ，在狀態集合中一共有十個狀態，每個狀態之間可以互相轉化，即可以從一個狀態轉移到另外一個狀態，當然，「另外的狀態」也有可能是當前狀態本身。如下圖所示，s1狀態到可以轉移到s2狀態，s1狀態也可以轉移到自己當前的狀態，當然s1也有可能轉移到s3，s4，s5，狀態，下圖中沒有給出。

根據上面的例子，我們可以把所有的狀態寫成矩陣的形式，就成了狀態轉移矩陣。用狀態轉移矩陣來描述馬爾可夫鏈的動態特性。以上面的狀態集合$S\in(s_1,s_2,s_3,s_4,s_5,s_6,s_7,s_8,s_9,s_{10})$ 為例，可得一個 $10\times10$ 的矩陣。如下圖所示：

\[\large
\begin{bmatrix}
s_1s_1 &… & s_1s_{10} \\
\vdots & \vdots & \vdots \\

s_{10}s_1 & … & s_{10}s_{10}\\
\end{bmatrix}
\]

由上面的例子可知，在狀態轉移的過程中，對於下一個狀態轉移是有概率的，比如說s1轉移到到s1狀態的概率可能是0.5，s1有0.3的概率轉移到s2狀態。⻢爾科夫過程是⼀個⼆元組（S， P），且滿⾜： S是有限狀態集合， P是狀態轉移概率。 可得：

\[\large
P=
\begin{bmatrix}
P_{11} &… & P_{1n} \\
\vdots & \vdots & \vdots \\

P_{n1} & … & P_{nn}\\
\end{bmatrix}
\]

一個簡單的例子：如圖2.2所⽰為⼀個學⽣的7種狀態{娛樂，課程1，課程2，課程3，考過，睡覺，論⽂}，每種狀態之間的轉換概率如圖所⽰。則該⽣從課程 1 開始⼀天可能的狀態序列為：

MRP

在 MPR 中，打個比喻，更像是隨波逐流的小船，沒有人為的干預，小船可以在大海中隨波逐流。

MDP

在MDP中，打個比喻，更像是有人劃的小船，這裡相比較MRP中的小船來說，多了「人划船槳」的概念，可以認為控制船的走向。這裡我們看下面的圖：

s1狀態到s2狀態的過程，agent從s1發出action A1，使得s1狀態轉移到s2狀態，並從s2狀態得到一個R2的獎勵。其實就是下圖所示的一個過程。這是一個動態的過程，由此，引出動態函數。

動態函數： The function $p$ defines the dynamics of the MDP. 這是書上的原話，也就說，這個動態函數定義了MDP的動態特性，動態函數如下：

\[\large
p(s’,r\mid s,a) \dot{=} Pr\lbrace S_{t+1}=s’,R_{t+1} = r \mid S_{t} =s,A_{t}=a \rbrace
\]
狀態轉移函數： 我們去掉 $r$ ，也就是reward，動態函數也就成了狀態轉移函數。

\[\large{
p(s’\mid s,a) \dot{=} Pr\lbrace S_{t+1}=s’,\mid S_{t} =s,A_{t}=a \rbrace \\
p(s’\mid s,a) = \sum_{r\in R} p(s’\mid s,a)
}
\]

reward的動態性： 在 s 和 a 選定後，r 也有可能是不同的，即 r 也是隨機變數。但是，大多數情況在 s 和 a 選定後 r 是相同的，這裡只做簡單的介紹。

Summary

MDP價值函數

策略的定義

在MDP中，即馬爾可夫決策過程，最重要的當然是策略（Policy），用 $\pi$ 來表示。在策略中其主要作用的就是action，也即 $A_t$，需要指出的一定是，action 一定是基於某一狀態 S 時。看下面的例子：

即，當 $S_t = S$ 狀態時，無論 $t$ 取何值，只要遇到 $S$ 狀態就選定 $a_1$ 這個 action ，這就是一種策略，並且是確定性策略。

策略的分類

確定性策略：也就是說和時間 $t$ 已經沒有關係了，只和這個狀態有關，只要遇到這個狀態，就做出這樣的選擇。
隨機性策略：與確定性策略相對，當遇到 $S$ 狀態時，可能選擇 $a_1$ ，可能選擇 $a_2$，也可能選擇 $a_3$。只是選擇action的概率不同。如下圖，就是兩種不同的策略:

從上面兩天圖中，因為一個策略是基於一個狀態而言的，在 $S$ 狀態，可能選擇 $a_1$ ，可能選擇 $a_2$，也可能選擇 $a_3$，故三個 action 之間是或的關係，所以說以上是兩個策略，而不要誤以為是6個策略。

故策略可分為確定性策略和隨機性策略兩種。

\[\large
Policy= \begin{cases} 確定性策略, & \text {a $\dot{=}\pi(s)$} \\ 隨機性策略, & \text { $\pi(a\mid s) \dot{=} P \lbrace A_t=a \mid S_t = s \rbrace$} \end{cases}
\]

對於隨機性策略而言，給定一個 $s$ ，選擇一個 $a$ ，也就是條件概率了。

確定性策略可以看作是一種特殊的隨機性策略，以上表-Policy1為例，選擇a1的概率為1，選擇a2，a3的概率都為0。

最優策略

在所有的策略中一定存在至少一個最優策略，而且在強化學習中，reward的獲得有延遲性（delay），舉雅達利遊戲中，很多遊戲只有到結束的時候才會知道是否贏了或者輸了，才會得到回饋，也就是reward，所以這就是獎勵獲得延遲。當選定一個狀態 $S_t$ 時，選定action $A_t$ ，因為獎勵延遲的原因可能對後續的 $S_{t+1}$ 等狀態都會產生影響。這樣，就不能用當前的reward來衡量策略的好壞、優劣。這裡引入了回報和價值函數的概念。

回報（$G_t$）

而是後續多個reward的加和，也就是回報，用 $G_t$ 表示 $t$ 時刻的回報。

如上圖所示，此時的「回報」可以表示為：$G_t = R_{t+1} + R_{t+2}+ \ …\ +R_T$

值得注意的是，$T$ 可能是有限的，也有可能是無限的。

舉例：張三對李四做了行為，對李四造成了傷害，李四在當天就能感受到傷害，而且，這個傷害明天，後頭都還是有的，但是，時間是最好的良藥，隨著時間的推移，李四對於張三對自己造成的傷害感覺沒有那麼大了，會有一個wei折扣，用 $\gamma$ 來表示。故真正的回報表示為：

\[\large
G_t = R_{t+1} + \gamma R_{t+2}+\gamma^2 R_{t+3} \ …\ +\gamma^{T-t-1}R_T = \sum_{i=0}^{\infty}\gamma^i R_{t+i+1} \quad \quad \gamma\in[0,1],\quad (T\rightarrow\infty)
\]

用 $G_t$ 來衡量一個策略的好壞，$G_t$ 大的策略就好，反之。

但是使用 $G_t$ 也不能很好的衡量策略的好壞，比如一個最大的問題是，在給定一個狀態後，選擇一個確定的action後（這裡還是在隨機策略的角度），進入的下一個狀態也是隨機的。如下圖所示：把左側的過程放大，只給出a3下的隨機狀態，a1，a2也是有同樣的情況，這裡勝率。

舉個例子，就像我們給一盆花澆水，水是多了還是少了，對於這盆花來說我們是不得知的，可能會少，也可能會多。這個花的狀態變化也就是隨機的了。從上面的例子得知，如果還是用 $G_t$ 來對一個策略來進行評估的話，至少有9中情況（隨機策略，3個action選一種）。

$G_t$ 只能評估的是一個「分叉」而已（圖中綠色分支）。而不能更好的進行評估。如下圖所示：

因為回報不能很好的對策略進行一個評估，由此引入了另外一個概念——價值函數。

價值函數（Value Function ）

在指定一個狀態 $s$ ，採取一個隨機策略 $\pi$ ，然後加權平均，以上圖為例，把9 個分叉($G_t$)加權平均。也就是期望 $E$。故得出價值函數：

\[\large
V_\pi(s) = E_\pi[G_t\mid S_t = s]
\]

Summary

MDP貝爾曼期望方程

價值函數分類

上面提到的的價值函數其實是其中的一種，確切的可以稱為 狀態價值函數，用$v_\pi(s)$ 來表示只和狀態有關係。初次之外還有另外一種價值函數，那就是狀態動作價值函數，用$q_\pi(s,a)$這裡引入的action。故價值函數可以分為下面的兩種:

\[Value \quad Function = \begin{cases} v_\pi(s) = E_\pi[G_t\mid S_t = s], & \text {only $s$ is independent variable} \\ q_\pi(s,a) = E_\pi[G_t\mid S_t = s,A_t = a], & \text{Both $s$ and a are independent variable} \end{cases}
\]

從上面的公式中，我們可以得知，在 $v_\pi(s)$ 中，只有 $s$ 是自變數，一個 $\pi$ 其實就是一個狀態$s$ 和一個action的一個映射。故，只要$\pi$ 確定了，那麼$s,a$ 也就確定了，即此時的 $\pi$ 對狀態 $s$ 是有限制作用的。但是，在 $q_\pi(s,a)$ 中，子變數為$s,a$ 兩個，這兩個自變數之間是沒有特定的關係的。也就是說，$s$和$a$ 都在變，無法確定一個映射(策略) $\pi$ ,那麼也就是說在 $q_\pi$ 中的$\pi$ 對於$s$ 是沒有約束的。

兩種價值函數之間的關係

$v_\pi(s)$ 和 $q_\pi(s,a)$ 之間的關係

還是以上圖為例，對於 s 狀態，在隨機策略中有三種 action 選擇，分別是 $\pi(a_1 \mid s)$，$\pi(a_1 \mid s)$，$\pi(a_1 \mid s)$，三種action(行為)對應的價值函數（此時為動作價值函數）為 $q_\pi(s,a_1)$， $q_\pi(s,a_2)$， $q_\pi(s,a_3)$。那麼此時的 $v_\pi(s)$ 就等於各個action的動作狀態價值函數的加和，即：

\[v_\pi(s) = \pi(a_1 \mid s)·q_\pi(s,a_1) + \pi(a_2 \mid s)·q_\pi(s,a_2) + \pi(a_3 \mid s)·q_\pi(s,a_3)
\]

這樣一來我們就得出了 $v_\pi(s)$ 和 $q_\pi(s,a)$ 之間的關係，若條件已知，就可以直接計算出 $v_\pi$。

\[\large
v_\pi(s) = \sum_{a\in A} \pi(a\mid s) ·q_\pi(s,a)
\]

對於某個狀態 $s$ 來說，$v_\pi \leq \underset{a}{max}\ q_\pi(s,a)$ ，$v_\pi(s)$ 是一個加權平均，實際上就是一個平均值，當然要小於等於$\ q_\pi(s,a)$的最大值。$v_\pi(s)$只有全部是最大值的時候，兩者才有可能相等。比如 5，5，5，平均值是5，最大值也是5；3，4，5而言，平均值為4，但是最大值為5。注意的是，4是乘上權值後的值，換句話說也就是乘了一個概率（$\pi(a\mid s)$）。

$q_\pi(s,a)$ 和 $v_\pi(s’)$ 之間的關係

從下面圖中可得，在 $q_\pi(s,a)$ 位置，（一個action）狀態轉移只能向「箭頭」方向轉移，而不能向上。如果想從下面的狀態轉移到上面的狀態，那必須還要另外一個action。情況是一樣的，就按下圖來說明，經過a3後到達狀態s’，此時的狀態函數就是 $v_\pi(s』）$。

上面的圖可知：在確定了s 後，由隨機策略action，引起「分叉」，同理，以a3為例，因為系統狀態轉移的隨機性，也會引起分叉，也就是 s’ 的狀態也是不確定的。還有一點 r 也又不確定性，如下圖藍色虛線部分。

由我們前面提到的公式也可得知：s’ 和 r 都是隨機的。比如說s，a ，s’ 都是給定的，r也是不確定的。

\[\large p(s’,r\mid s,a) \dot{=} Pr\lbrace S_{t+1}=s’,R_{t+1} = r \mid S_{t} =s,A_{t}=a \rbrace
\]

這樣一來，可得一條藍色通路的回報：

\[\large
q_\pi(s,a) = r + \gamma v_\pi(s’) \quad\quad\quad (1)
\]

(1)式是怎麼來的呢？以上圖為例，在 $q_\pi(s,a)$ 處往下走，選定一個 r ，再往下到達一個狀態s’，此時在往下還是同樣的狀態，就是俄羅斯套娃，以此類推。關於其中的 $\gamma v_\pi(s’) $ ，來自於 $G_t$。看下面的式子：

\[\large{
G_t = R_{t+1} + \gamma R_{t+2}+\gamma^2 R_{t+3} \ …\ +\gamma^{T-t-1}R_T \quad\quad \gamma\in[0,1],\quad (T\rightarrow\infty) \\
G_t = R_{t+1} + \gamma(R_{t+2}+\gamma R_{t+3}+\gamma^2 R_{t+4}+ …)
}
\]

因為 $v_\pi(s)$ 來自 $G_t$ ，故類比得（1）式。

因為走每條藍色的通路也都是由概率的，故我們需要乘上概率，同時累加求和，一個是多條藍色通路另一個是多個s’。故得：$q_\pi(s,a)$ 和 $v_\pi(s’)$ 之間的關係 如下：

\[\large
q_\pi(s,a) =\sum_{s’,r}P(s’,r \mid s,a)[r+ \gamma v_\pi(s’)] \quad\quad\quad (2)
\]

貝爾曼期望等式（方程）

這樣我們得到兩個式子：

\[\large{
v_\pi(s) = \sum_{a\in A} \pi(a\mid s) ·q_\pi(s,a) \quad\quad\quad\quad\quad\quad\quad\quad\ (3) \\

q_\pi(s,a) =\sum_{s’,r}P(s’,r \mid s,a)[r+ \gamma v_\pi(s’)] \quad\quad\quad (4)
}
\]

（4）式帶入（3）得：

\[\large
v_\pi(s) = \sum_{a\in A} \pi(a\mid s) \sum_{s’,r}P(s’,r \mid s,a)[r+ \gamma v_\pi(s’)] \quad\quad\quad\quad\quad\quad (5)
\]

（3）式帶入（4）得：

\[\large
q_\pi(s,a) =\sum_{s’,r}P(s’,r \mid s,a)[r+ \gamma \sum_{a’\in A} \pi(a’\mid s’) ·q_\pi(s’,a’) ] \quad\quad (6)
\]

關於（6）式可以看下圖，更容易理解：

（5）式和（6）式被稱為貝爾曼期望方程。

一個實例：

例子是一個學生學習考試的MDP。裡面實心圓位置是起點，方框那個位置是終點。上面的動作有study, Pub, Facebook, Quit, Sleep，每個狀態動作對應的即時獎勵R已經標出來了。我們的目標是找到最優的狀態動作價值函數或者狀態價值函數，進而找出最優的策略。

為了方便，我們假設衰減因子 $\gamma =1, \pi(a|s) = 0.5$ 。對於終點方框位置，由於其沒有下一個狀態，也沒有當前狀態的動作，因此其狀態價值函數為0，對於其他的狀態（圓圈）按照從上到下，從左到右的順序定義其狀態價值函數分別是 $v_1,v_2,v_3,v_4$ ，根據（5）式 :

\[v_\pi(s) = \sum_{a\in A} \pi(a\mid s) \sum_{s’,r}P(s’,r \mid s,a)[r+ \gamma v_\pi(s’)] \quad\quad\quad\quad\quad\quad (5)
\]

對於$v_1$位置，我們有：$v_1 = 0.5*(-1+v_1) +0.5*(0+v_2)$

對於$v_2$位置，我們有：$v_2 = 0.5*(-1+v_1) +0.5*(-2+v_3)$

對於$v_3$位置，我們有：$v_3 = 0.5*(0+0) +0.5*(-2+v_4)$

對於$v_4$位置，我們有：$v_4 = 0.5*(10+0) +0.5*(1+0.2*v_2+0.4*v_3+0.4*v_4)$

解出這個方程組可以得到 $v_1=-2.3, v_2=-1.3, v_3=2.7, v_4=7.4$, 即每個狀態的價值函數如下圖：

從上面可以看出，針對一個特定狀體，狀態價值函數計算都是基於下一個狀態而言的，通俗的講，按照「出箭頭」的方向計算當前狀態的價值函數。

Summary

MDP貝爾曼最優方程

最優價值函數

能夠使得 $v$ 達到最大值的那個 $\pi$ ，這個 $\pi$ 被成為最優策略，進而得到最優狀態價值函數。同理得到最優狀態動作價值函數。

\[\large
\begin{cases} v_*(s)\ \dot{=}\ \ \underset{\pi}{max} \ v_\pi(s) & \text{} \\
q_*(s,a)\ \dot{=}\ \ \underset{\pi}{max} \ q_\pi(s,a) & \text{} & \text {} \end{cases}
\]

記 $\pi_* = \underset{\pi}{argmax} \ v_\pi(s) = \underset{\pi}{argmax} \ q_\pi(s,a)$，含義是 $\pi_*$ 可以使得 $ v_*(s)$達到最大值，同樣的，也可以使得

$q_\pi(s,a)$ 達到最大值。

由以上公式得：

\[\large
\begin{cases}v_*(s)=\underset{\pi}{max}\ v_\pi(s)= v_{\pi_*}(s) & \text{(7)} \\
q_*(s,a)=\underset{\pi}{max}\ q_\pi(s,a)= q_{\pi_*}(s,a) & \text{} & \text {(8)} \end{cases}
\]

值得注意的一點是$ v_*(s)$ 強調的是，不管你採用的是什麼策略，只要狀態價值函數達到最大值，而 $v_{\pi_*}(s)$ 則更為強調的是 $\pi$ ，達到最大的狀態價值函數所採取的最優的那個 $\pi$

此時，我們再探討一下$v_{\pi_*}(s)$ 和 $q_{\pi_*}(s,a)$ 的關係。在貝爾曼期望方程中，我們提到過 $v_\pi(s) \leq \underset{a}{max}\ q_\pi(s,a)$ ，那麼在這裡是不是也由類似的關係$v_{\pi_*}(s)\leq \underset{a}{max}\ q_\pi(s,a)$ 成立？我們知道 $v_{\pi_*}(s)$ 是一種策略，並且是最優的策略，$q_{\pi_*}(s,a)$ 是代表一個「分支」，因為 $v_{\pi_*}(s)$ 是一個加權平均值，但同樣的，和$v_\pi(s)$ 不同的是，$v_{\pi_*}(s)$ 是最優策略的加權平均，那麼是不是可以把小於號去掉，寫成下面的形式：

\[\large
v_{\pi_*}(s)= \underset{a}{max}\ q_\pi(s,a)
\]

假定 $v_{\pi_*}(s)\leq \underset{a}{max}\ q_\pi(s,a)$ 中的 $\pi_*$ 還是一個普通的策略，那麼一定滿足 $v_{\pi_*}(s)\leq \underset{a}{max}\ q_\pi(s,a)$ ，這一點我們已經提到過，如果說 $v_{\pi_*}(s)< \underset{a}{max}\ q_\pi(s,a)$ ，說明$v_{\pi_*}(s)$ 還有提高的空間，並不是最優策略，這和條件矛盾了。所以這個小於不成立，得證：$v_{\pi_*}(s)= \underset{a}{max}\ q_\pi(s,a)$

詳細證明過程如下：

其實，上面的式子是由 (3)式

\[v_\pi(s) = \sum_{a\in A} \pi(a\mid s) ·q_\pi(s,a) \quad\quad (3)
\]

演變而來的。$v_{\pi_*}(s)$ 直接取最大值時候和 $\underset{a}{max}\ q_\pi(s,a)$ 的最大值是相等的。也就是此時不用加權平均了，直接是 $v_\pi(a) = q_\pi(s,a)$ 。那麼從原先的(4)式能不能也得出相似

\[q_\pi(s,a) =\sum_{s’,r}P(s’,r \mid s,a)[r+ \gamma v_\pi(s’)] \quad\quad (4)
\]

的結論，把求和符號去掉，直接等於最大值呢？答案是否定的，因為$v_{\pi_*}(s)= \underset{a}{max}\ q_\pi(s,a)$ 是作用在action上的，在公式中也可以看出，換句話說，我們對於下圖的a1，a2，a3這裡是可以控制的。但是對於下圖中的藍色虛線部分，系統狀態轉移是無法控制的。

所以，原先的兩組公式（3）、（4）並結合（7）、（8）

\[\large{
v_\pi(s) = \sum_{a\in A} \pi(a\mid s) ·q_\pi(s,a) \quad\quad\quad\quad\quad\quad\quad\quad\ (3) \\

q_\pi(s,a) =\sum_{s’,r}P(s’,r \mid s,a)[r+ \gamma v_\pi(s’)] \quad\quad\quad (4)
}
\]

並進行一個推導，得出另外的兩組公式（9）、（10）如下：

\[\large{
v_*(s)=\underset{a}{max}\ q_*(s,a) \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad (9) \\
q_*(s,a)= \sum_{s’,r}P(s’,r \mid s,a)[r+\gamma v_*(s’)] \quad\quad\quad (10)
}
\]

貝爾曼最優方程

（10）式帶入（9）式得：

\[\large{
v_*(s)=\underset{a}{max}\sum_{s’,r}P(s’,r \mid s,a)[r+\gamma v_\pi(s’)] \quad\quad(11) \\

}
\]

（9）式帶入（10）式得：

\[\large
q_*(s,a)= \sum_{s’,r}P(s’,r \mid s,a)[r+\gamma \underset{a’}{max}\ q_*(s’,a’) ] \quad\quad (12)
\]

（11）、（12）被稱為貝爾曼最優方程。

一個實例：還是以上面的例子講解，我們這次以動作價值函數 $q_*(s,a)$ 為例來求解 $v_(s),q_(s,a) $

根據（12）式

\[\large
q_*(s,a)= \sum_{s’,r}P(s’,r \mid s,a)[r+\gamma \underset{a’}{max}\ q_*(s’,a’) ] \quad\quad (12)
\]

可得方程組如下：

\[\large{\begin{align}
q_*(s_4, study) & = 10 \\
q_*(s_4, pub) & = 1 + 0.2 * \underset{a’}{max}q_*(s_2, a’) + 0.4 * max_{a’}q_*(s_3, a’) + 0.4 * \underset{a’}{max}q_*(s_4, a’) \\
q_*(s_3, sleep) & = 0 \\
q_*(s_3, study) & = -2 + \underset{a’}{max}q_*(s_4, a’) \\
q_*(s_2, study) & = -2 + \underset{a’}{max}q_*(s_3, a’) \\
q_*(s_2, facebook) & = -1 + \underset{a’}{max}q_*(s_1, a’) \\
q_*(s_1, facebook) & = -1 + \underset{a’}{max}q_*(s_1, a’) \\
q_*(s_1, quit) & = 0 + \underset{a’}{max}q_*(s_2, a’)
\end{align}}
\]

然後求出所有的 $q_*(s,a)$，然後再利用 $v_*(s) = \underset{a’}{max}q_*(s,a)$，就可以求出所有的 $v_*(s)$，最終結果如下圖所示：

詳細的計算過程可以看下影片的簡單分析。//www.bilibili.com/video/BV1Fi4y157vR/

Summary

參考文獻

//www.bilibili.com/video/BV1RA411q7wt

//www.cnblogs.com/pinard/p/9426283.html

//www.davidsilver.uk/wp-content/uploads/2020/03/MDP.pdf

//www.cnblogs.com/jsfantasy/p/jsfantasy.html