強化學(xué)習(xí) --- 馬爾科夫決策過程（MDP）

一、馬爾科夫過程（Markov Process）

馬爾科夫性某一狀態(tài)信息包含了所有相關(guān)的歷史，只要當前狀態(tài)可知，所有的歷史信息都不再需要，當前狀態(tài)就可以決定未來，則認為該狀態(tài)具有馬爾科夫性

[P(S_{t+1}|S_t) = p(S_{t+1}|S_1, S_2, cdots , S_t)
]

馬爾科夫過程又叫做馬爾科夫鏈（Markov Chain）,它是一個無記憶的隨機過程，可以用一個元組<S, P>表示，其中

S是有限數(shù)量的狀態(tài)集 (S ={s_1, s_2, s_3, cdots, s_t})
P是狀態(tài)轉(zhuǎn)移概率矩陣 (p(S_{t+1} = s'|s_t=s) ， 其中 s' 表示下一時刻的狀態(tài)，s 表示當前狀態(tài))

二、馬爾科夫獎勵過程（Markov Reward Process）

馬爾科夫獎勵過程是在馬爾科夫過程基礎(chǔ)上增加了獎勵函數(shù) (R) 和衰減系數(shù) (gamma)， 用 (<S, R,P, gamma>)表示

(R) : 表示 (S) 狀態(tài)下某一時刻的狀態(tài)(S_t) 在下一個時刻 ((t + 1)) 能獲得的獎勵的期望

[R_s = E[R_{t+1}|S_t=s]
]

(G_t) : 收獲 (G_t)為在一個馬爾科夫獎勵鏈上從t時刻開始往后所有的獎勵的有衰減的收益總和

[G_t = R_{t+1} + gamma R_{t+2} + gamma^2 R_{t+3} + cdots + gamma^{T-t-1}R_T
]

(gamma) : 折扣因子(（Discount ; factor γ ∈ [0, 1]）)

1、為了避免出現(xiàn)狀態(tài)循環(huán)的情況
2、系統(tǒng)對于將來的預(yù)測并不一定都是準確的，所以要打折扣
很顯然越靠近1，考慮的利益越長遠。

(V(s)) : 狀態(tài)價值函數(shù)（state value function） 表示從從該狀態(tài)開始的馬爾科夫鏈收獲(G_t)的期望

[v(s) = E[G_t|S_t = s]
]

例子：

獎勵：(S_1) +5， (S_7) +10， 其余獎勵為 0，則 (R = [5,0,0,0,0,0,10])
(gamma = 0.5)

$S_4, S_5, S_6, S_7: $ 0 + 0.5*0 + 0.5*0 + 0.125 *10 = 1.25
(S_4,S_3,S_2,S_1) : 0 + 0.5 ×0 + 0.25×0 + 0.125×5 = 0.625

Bellman Equation 貝爾曼方程

(v(s) = E[G_t|S_t = s])

(= E[R_{t+1} + gamma R_{t+2} + gamma^2 R_{t+3} + cdots|S_t = s])

(= E[R_{t+1} + gamma(R_{t+2} + R_{t+3} + cdots)|S_t=s])

(=E[R_{t+1} + gamma v(S_{t+1})|S_t = s])

(=underbrace{E[R_{t+1}|S_t=s]}_{當前的獎勵} + underbrace{gamma E[v(S_{t+1})|S_t = s]}_{下一時刻狀態(tài)的價值期望})

使用貝爾曼方程狀態(tài)價值(V)可以表示為：

[V(s) = underbrace{R(s)}_{Immediate ; reward} + underbrace{gamma sum_{s' in S}P(s'|s)V(s')}_{Discounted ; sum ; of ; future ; reward}
]

S 表示下一時刻的所有狀態(tài)
s' 表示下一時刻可能的狀態(tài)

三、馬爾科夫決策過程（Markov Decision Process）

馬爾科夫決策過程是在馬爾科夫獎勵過程的基礎(chǔ)上加了 Decision 過程，相當于多了一個動作集合，可以用 (<S, A, P, R, gamma>)

(A) 表示有限的行為集合

(S)表示有限的狀態(tài)集合

(P^a) is dynamics / transition model for each action

(P(s_{t+1} = s'|s_t = s, a_t = a))

(R) 是獎勵函數(shù) (R(s_t=s, a_t = a) = E[R_t|s_t=s, a_t=a])

策略 （Policy）

用 (pi) 表示策略的集合，其元素 (pi(a|s)) 表示某一狀態(tài) s 采取可能的行為 a 的概率

[pi(a|s) = P(A_t=a|S_t=s)
]

在馬爾科夫獎勵過程中 策略 (pi) 滿足以下方程，可以參照下面圖來理解

[狀態(tài)轉(zhuǎn)移概率：quad P^pi(s'|s) = sum_{a in A}pi(a|s)P(s'|s, a) \
獎勵函數(shù)：quad R^pi(s) = sum_{ain A}pi(a|s)R(s,a)
]

狀態(tài)轉(zhuǎn)移概率可以描述為：在執(zhí)行策略 (pi) 時，狀態(tài)從 s 轉(zhuǎn)移至 s' 的概率等于執(zhí)行該狀態(tài)下所有行為的概率與對應(yīng)行為能使狀態(tài)從 s 轉(zhuǎn)移至 s’ 的概率的乘積的和。參考下圖

獎勵函數(shù)可以描述為：在執(zhí)行策略 (pi) 時獲得的獎勵等于執(zhí)行該狀態(tài)下所有行為的概率與對應(yīng)行為產(chǎn)生的即時獎勵的乘積的和。

我們引入策略，也可以理解為行動指南，更加規(guī)范的描述個體的行為，既然有了行動指南，我們要判斷行動指南的價值，我們需要再引入基于策略的價值函數(shù)。

基于策略的狀態(tài)價值函數(shù)（state value function）

(V(s)) 表示從狀態(tài) (s) 開始，遵循當前策略時所獲得的收獲的期望

[v_{pi}(s) = E_{pi}[G_t|S_t = s]
]

其中 (G_t) 可以參照馬科夫獎勵過程。我們有了價值衡量標準，如果狀態(tài) s 是一個好的狀態(tài)，如何選擇動作到達這個狀態(tài)，這時就需要判斷動作的好壞，衡量行為價值。

基于策略的行為價值函數(shù)（action value function）

(q_{pi}(s,a))當前狀態(tài)s執(zhí)行某一具體行為a所能的到的收獲的期望

[q_{pi}(s, a) = E_{pi}[G_t|S_t=s, A_t=a]
]

根據(jù) Bellman 公式推導(dǎo)可得（參照馬爾科夫獎勵過程中 V 的推導(dǎo)）

[q_{pi}(s,a) = R(s, a) + gamma sum_{s' in S} P_{(s'|s, a)} cdot V_{pi}(s')
]

在某一個狀態(tài)下采取某一個行為的價值，可以分為兩部分：其一是離開這個狀態(tài)的價值，其二是所有進入新的狀態(tài)的價值于其轉(zhuǎn)移概率乘積的和。參考下圖右理解

由狀態(tài)價值函數(shù)和行為價值函數(shù)的定義，可得兩者的關(guān)系

[v_{pi}(s) = sum_{a in A}pi(a|s) cdot q_{pi}(s,a)
]

我們知道策略就是用來描述各個不同狀態(tài)下執(zhí)行各個不同行為的概率，而狀態(tài)價值是遵循當前策略時所獲得的收獲的期望，即狀態(tài) s 的價值體現(xiàn)為在該狀態(tài)下遵循某一策略而采取所有可能行為的價值按行為發(fā)生概率的乘積求和。參照下圖左理解

上面兩個公式組合可得 Bellman Expectation Equation

[v_{pi}(s) = sum_{a in A}pi(a|s)left(R(s, a) + gamma sum_{s' in S} P_{(s'|s, a)} cdot V_{pi}(s')ight)
]

[q_{pi}(s,a) = R(s, a) + gamma sum_{s' in S} P_{(s'|s, a)} cdot sum_{a' in A}pi(a'|s') cdot q_{pi}(s',a')
]

實例

假設(shè)(gamma = 1)上圖數(shù)字值為對于狀態(tài)價值v(s)，根據(jù)公式價值函數(shù)需要下一個狀態(tài)的價值，終點的狀態(tài)價值為0，利用遞歸的方式即可得到

5.5=0.5*(10+0)+0.5*(0+1*1)

1.65=0.5*(-2+0.4*3.5+0.4*5.5+0.2*1)+0.5*(-2+1*3.5)

五、Decision Making in MDP

可以把 Decision Making 分為兩個過程

Prediction (評估給定的策略)

輸入: MDP(<S, A, P, R, gamma>) 和 策略 $pi $
輸出：value function (V_pi)

Control (尋找最優(yōu)策略)

輸入：MDP$<S, A, P, R, gamma> $
輸出：最優(yōu)的價值函數(shù) (V^*) 和最優(yōu)的策略 (pi^*)

1、Policy evaluation on MDP

Prediction 滿足動態(tài)規(guī)劃的條件：

貝爾曼等式可以遞歸分解
value function 可以被存儲和重用

Iteration on Bellman exception backup

我們可以用所有的狀態(tài) s 在 t 時刻的價值 (v_t(s')) 來更新 (v_{t+1}(s)) 時刻的價值，然后迭代下去

[V_{t+1}(s) = sum_{a in A}pi(a|s)(R(s, a) + gamma sum_{s' in S} P_{(s'|s, a)} cdot V_t(s')) \
V_{t+1}(s) = R_pi(s) + gamma sum_{s' in S} P_{pi}(s'|s) cdot V_t(s')
]

最優(yōu)狀態(tài)價值函數(shù)指的是在從所有策略產(chǎn)生的狀態(tài)價值函數(shù)中，選取使狀態(tài)s價值最大的函數(shù)：

[V_*(s) = max_pi V_pi(s)
]

最優(yōu)的策略

[pi^*(s) = argmax_pi V^*(s)
]

對于任何MDP，下面幾點成立：

1.存在一個最優(yōu)策略，比任何其他策略更好或至少相等；
2.所有的最優(yōu)策略有相同的最優(yōu)價值函數(shù)；
3.所有的最優(yōu)策略具有相同的行為價值函數(shù)。

根據(jù)以上幾點，我們可以最大化最優(yōu)行為價值函數(shù)找到最優(yōu)策略

[pi^*(a|s) =
egin{cases}
1, & ext{if $a = argmax ; q^*(s,a)$} \
0, & ext{otherwise}
end{cases}
]

策略的個數(shù)為 (|A|^{|S|}) 個，對于狀態(tài)比較多的環(huán)境，計算量太大
更加高效的方法是 policy iteration 和 value iteration

2、MDP Control

(1) Policy Iteration

分為兩個部分

Evaluate the policy $ pi $，（通過給定的 $ pi $ 計算 V）
Improve the policy $ pi $，（通過貪心策略）

[pi' = greedy(v^{pi})
]

如果我們有 一個 策略 (pi)，我們可以用策略 估計出它的狀態(tài)價值函數(shù) (v_pi(s)), 然后根據(jù)策略改進提取出更好的策略 (pi')，接著再計算 (v_{pi'}(s))， 然后再獲得更好的 策略 (pi'')，直到相關(guān)滿足相關(guān)終止條件。

評估價值 (Evaluate)

[v_i(s) = sum_{a in A}pi(a|s)(R(s, a) + gamma sum_{s' in S} P_{(s'|s, a)} cdot v_{i-1}(s'))
]

如何改進策略（Improve）

[q^{pi_i}(s,a) = R(s, a) + gamma sum_{s' in S} P_{(s'|s,a)} cdot v^{pi_i}(s') \
pi_{i+1}(s) = argmax_a ; q^{pi_i}(s,a)
]

可以把 (q^{pi_i}(s,a)) 想象成一個表格，其中橫軸代表不同的狀態(tài)，縱軸代表每種狀態(tài)下不同的動作產(chǎn)生的價值，然后選擇一個最大的行為價值作為當前的狀態(tài)價值

當 improve 過程停止時，已經(jīng)找到最佳策略

Bellman Optimality Equation

利用狀態(tài)價值函數(shù)和動作價值函數(shù)之間的關(guān)系，得到

[v_*(s) = max_a q_*(s,a)
]

[q_*(s,a) = R(s, a) + gamma sum_{s' in S} P_{s's}^a cdot V_*(s')
]

把上面兩個式子結(jié)合起來有Bellman Optimality Equation

[v_*(s) = max_a (R(s, a) + gamma sum_{s' in S} P_{s's}^a cdot V_*(s'))
]

[q_*(s,a) = R(s, a) + gamma sum_{s' in S} P_{s's}^a cdot max_{a'}q_*(s', a')
]

(2) Value Iteration

如果我們解決了子問題的 (V^*(s'))
那么我們就可以通過反復(fù)迭代Bellman Optimality Equation找到 $ V^*(s) $

[v_*(s) = max_a q_*(s,a) \
Downarrow \
v_{i+1}(s) leftarrow max_{a in A} ; left(R(s, a) + gamma sum_{s' in S} P_{(s'|s,a)} cdot V_i(s')ight)
]

然后直接提取最優(yōu)策略 $ pi $

[pi^*(s) = argmax_a ; q^{pi}(s,a) \
Downarrow \
pi^*(s) leftarrow argmax_a ; left(R(s, a) + gamma sum_{s' in S} P_{(s'|s,a)} cdot V_{end}(s')ight)
]

六 后記

關(guān)于直觀的理解 Policy Iteration 和 Value Iteration 可以訪問下面的網(wǎng)址

https://cs.stanford.edu/people/karpathy/reinforcejs/gridworld_dp.html

總結(jié)

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

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