強化學(xué)習(xí)從基礎(chǔ)到進階-常見問題和面試必知必答[2]：馬爾科夫決策、貝爾曼方程、動態(tài)規(guī)劃、策略價值迭代

1.馬爾科夫決策核心詞匯

• 馬爾可夫性質(zhì)（Markov property，MP）：如果某一個過程未來的狀態(tài)與過去的狀態(tài)無關(guān)，只由現(xiàn)在的狀態(tài)決定，那么其具有馬爾可夫性質(zhì)。換句話說，一個狀態(tài)的下一個狀態(tài)只取決于它的當(dāng)前狀態(tài)，而與它當(dāng)前狀態(tài)之前的狀態(tài)都沒有關(guān)系。
• 馬爾可夫鏈（Markov chain）： 概率論和數(shù)理統(tǒng)計中具有馬爾可夫性質(zhì)且存在于離散的指數(shù)集（index set）和狀態(tài)空間（state space）內(nèi)的隨機過程（stochastic process）。
• 狀態(tài)轉(zhuǎn)移矩陣（state transition matrix）：狀態(tài)轉(zhuǎn)移矩陣類似于條件概率（conditional probability），其表示當(dāng)智能體到達(dá)某狀態(tài)后，到達(dá)其他所有狀態(tài)的概率。矩陣的每一行描述的是從某節(jié)點到達(dá)所有其他節(jié)點的概率。
• 馬爾可夫獎勵過程（Markov reward process，MRP）： 本質(zhì)是馬爾可夫鏈加上一個獎勵函數(shù)。在馬爾可夫獎勵過程中，狀態(tài)轉(zhuǎn)移矩陣和它的狀態(tài)都與馬爾可夫鏈的一樣，只多了一個獎勵函數(shù)。獎勵函數(shù)是一個期望，即在某一個狀態(tài)可以獲得多大的獎勵。
• 范圍（horizon）：定義了同一個回合（episode）或者一個完整軌跡的長度，它是由有限個步數(shù)決定的。
• 回報（return）：把獎勵進行折扣（discounted），然后獲得的對應(yīng)的獎勵。
• 貝爾曼方程（Bellman equation）：其定義了當(dāng)前狀態(tài)與未來狀態(tài)的迭代關(guān)系，表示當(dāng)前狀態(tài)的價值函數(shù)可以通過下個狀態(tài)的價值函數(shù)來計算。貝爾曼方程因其提出者、動態(tài)規(guī)劃創(chuàng)始人理查德 ?\cdot? 貝爾曼（Richard Bellman）而得名，同時也被叫作“動態(tài)規(guī)劃方程”。貝爾曼方程即 V(s)=R(s)+γ∑s′∈SP(s′∣s)V(s′)V(s)=R(s)+ \gamma \sum_{s’ \in S}P(s’|s)V(s’)V(s)=R(s)+γ∑s′∈SP(s′∣s)V(s′) ，特別地，其矩陣形式為 V=R+γPV\mathrm{V}=\mathrm{R}+\gamma \mathrm{PV}V=R+γPV。
• 蒙特卡洛算法（Monte Carlo algorithm，MC algorithm）： 可用來計算價值函數(shù)的值。使用本節(jié)中小船的例子，當(dāng)?shù)玫揭粋€馬爾可夫獎勵過程后，我們可以從某一個狀態(tài)開始，把小船放到水中，讓它隨波流動，這樣就會產(chǎn)生一個軌跡，從而得到一個折扣后的獎勵 ggg 。當(dāng)積累該獎勵到一定數(shù)量后，用它直接除以軌跡數(shù)量，就會得到其價值函數(shù)的值。
• 動態(tài)規(guī)劃算法（dynamic programming，DP）： 其可用來計算價值函數(shù)的值。通過一直迭代對應(yīng)的貝爾曼方程，最后使其收斂。當(dāng)最后更新的狀態(tài)與上一個狀態(tài)差距不大的時候，動態(tài)規(guī)劃算法的更新就可以停止。
• Q函數(shù)（Q-function）： 其定義的是某一個狀態(tài)和某一個動作所對應(yīng)的有可能得到的回報的期望。
• 馬爾可夫決策過程中的預(yù)測問題：即策略評估問題，給定一個馬爾可夫決策過程以及一個策略 π\(zhòng)piπ ，計算它的策略函數(shù)，即每個狀態(tài)的價值函數(shù)值是多少。其可以通過動態(tài)規(guī)劃算法解決。
• 馬爾可夫決策過程中的控制問題：即尋找一個最佳策略，其輸入是馬爾可夫決策過程，輸出是最佳價值函數(shù)（optimal value function）以及最佳策略（optimal policy）。其可以通過動態(tài)規(guī)劃算法解決。
• 最佳價值函數(shù)：搜索一種策略 π\(zhòng)piπ ，使每個狀態(tài)的價值最大，V?V^*V? 就是到達(dá)每一個狀態(tài)的極大值。在極大值中，我們得到的策略是最佳策略。最佳策略使得每個狀態(tài)的價值函數(shù)都取得最大值。所以當(dāng)我們說某一個馬爾可夫決策過程的環(huán)境可解時，其實就是我們可以得到一個最佳價值函數(shù)。

2.常見問題匯總

2.1為什么在馬爾可夫獎勵過程中需要有折扣因子？

（1）首先，是有些馬爾可夫過程是環(huán)狀的，它并沒有終點，所以我們想避免無窮的獎勵。

（2）另外，我們想把不確定性也表示出來，希望盡可能快地得到獎勵，而不是在未來的某個時刻得到獎勵。

（3）接上一點，如果這個獎勵是有實際價值的，我們可能更希望立刻就得到獎勵，而不是后面才可以得到獎勵。

（4）還有，在有些時候，折扣因子也可以設(shè)為0。當(dāng)它被設(shè)為0后，我們就只關(guān)注它當(dāng)前的獎勵。我們也可以把它設(shè)為1，設(shè)為1表示未來獲得的獎勵與當(dāng)前獲得的獎勵是一樣的。

所以，折扣因子可以作為強化學(xué)習(xí)智能體的一個超參數(shù)進行調(diào)整，然后就會得到不同行為的智能體。

2.2 為什么矩陣形式的貝爾曼方程的解析解比較難求得？

通過矩陣求逆的過程，我們就可以把 VVV 的解析解求出來。但是這個矩陣求逆的過程的復(fù)雜度是 O(N3)O(N^3)O(N3) ，所以當(dāng)狀態(tài)非常多的時候，比如從10個狀態(tài)到1000個狀態(tài)，到100萬個狀態(tài)，那么當(dāng)我們有100萬個狀態(tài)的時候，轉(zhuǎn)移矩陣就會是一個100萬乘100萬的矩陣。對于這樣一個大矩陣進行求逆是非常困難的，所以這種通過解析解去解的方法，只能應(yīng)用在很小量的馬爾可夫獎勵過程中。

2.3 計算貝爾曼方程的常見方法有哪些，它們有什么區(qū)別？

（1）蒙特卡洛方法：可用來計算價值函數(shù)的值。以本書中的小船示例為例，當(dāng)?shù)玫揭粋€馬爾可夫獎勵過程后，我們可以從某一個狀態(tài)開始，把小船放到水中，讓它“隨波逐流”，這樣就會產(chǎn)生一條軌跡，從而得到一個折扣后的獎勵 ggg 。當(dāng)積累該獎勵到一定數(shù)量后，直接除以軌跡數(shù)量，就會得到其價值函數(shù)的值。

（2）動態(tài)規(guī)劃方法：可用來計算價值函數(shù)的值。通過一直迭代對應(yīng)的貝爾曼方程，最后使其收斂。當(dāng)最后更新的狀態(tài)與上一個狀態(tài)區(qū)別不大的時候，通常是小于一個閾值 γ\gammaγ 時，更新就可以停止。

（3）以上兩者的結(jié)合方法：我們也可以使用時序差分學(xué)習(xí)方法，其為動態(tài)規(guī)劃方法和蒙特卡洛方法的結(jié)合。

2.4 馬爾可夫獎勵過程與馬爾可夫決策過程的區(qū)別是什么？

相對于馬爾可夫獎勵過程，馬爾可夫決策過程多了一個決策過程，其他的定義與馬爾可夫獎勵過程是類似的。由于多了一個決策，多了一個動作，因此狀態(tài)轉(zhuǎn)移也多了一個條件，即執(zhí)行一個動作，導(dǎo)致未來狀態(tài)的變化，其不僅依賴于當(dāng)前的狀態(tài)，也依賴于在當(dāng)前狀態(tài)下智能體采取的動作決定的狀態(tài)變化。對于價值函數(shù)，它也多了一個條件，多了一個當(dāng)前的動作，即當(dāng)前狀態(tài)以及采取的動作會決定當(dāng)前可能得到的獎勵的多少。

另外，兩者之間是有轉(zhuǎn)換關(guān)系的。具體來說，已知一個馬爾可夫決策過程以及一個策略 π\(zhòng)piπ 時，我們可以把馬爾可夫決策過程轉(zhuǎn)換成馬爾可夫獎勵過程。在馬爾可夫決策過程中，狀態(tài)的轉(zhuǎn)移函數(shù) P(s′∣s,a)P(s’|s,a)P(s′∣s,a) 是基于它的當(dāng)前狀態(tài)和當(dāng)前動作的，因為我們現(xiàn)在已知策略函數(shù)，即在每一個狀態(tài)，我們知道其采取每一個動作的概率，所以我們就可以直接把這個動作進行加和，就可以得到對于馬爾可夫獎勵過程的一個轉(zhuǎn)移概率。同樣地，對于獎勵，我們可以把動作去掉，這樣就會得到一個類似于馬爾可夫獎勵過程的獎勵。

2.5 馬爾可夫決策過程中的狀態(tài)轉(zhuǎn)移與馬爾可夫獎勵過程中的狀態(tài)轉(zhuǎn)移的結(jié)構(gòu)或者計算方面的差異有哪些？

對于馬爾可夫鏈，它的轉(zhuǎn)移概率是直接決定的，即從當(dāng)前時刻的狀態(tài)通過轉(zhuǎn)移概率得到下一時刻的狀態(tài)值。但是對于馬爾可夫決策過程，其中間多了一層動作的輸出，即在當(dāng)前這個狀態(tài)，首先要決定采取某一種動作，再通過狀態(tài)轉(zhuǎn)移函數(shù)變化到另外一個狀態(tài)。所以在當(dāng)前狀態(tài)與未來狀態(tài)轉(zhuǎn)移過程中多了一層決策性，這是馬爾可夫決策過程與之前的馬爾可夫過程的不同之處。在馬爾可夫決策過程中，動作是由智能體決定的，所以多了一個組成部分，智能體會采取動作來決定未來的狀態(tài)轉(zhuǎn)移。

2.6 我們?nèi)绾螌ふ易罴巡呗裕瑢ふ易罴巡呗苑椒ㄓ心男?/h3>

本質(zhì)來說，當(dāng)我們?nèi)〉米罴褍r值函數(shù)后，我們可以通過對Q函數(shù)進行最大化，從而得到最佳價值。然后，我們直接對Q函數(shù)取一個讓動作最大化的值，就可以直接得到其最佳策略。具體方法如下，

（1）窮舉法（一般不使用）：假設(shè)我們有有限個狀態(tài)、有限個動作可能性，那么每個狀態(tài)我們可以采取 AAA 種動作策略，那么總共就是 ∣A∣∣S∣|A|^{|S|}∣A∣∣S∣ 個可能的策略。我們可以把他們窮舉一遍，然后算出每種策略的價值函數(shù)，對比一下就可以得到最佳策略。但是這種方法的效率極低。

（2）策略迭代： 一種迭代方法，其由兩部分組成，以下兩個步驟一直在迭代進行，最終收斂，其過程有些類似于機器學(xué)習(xí)中的EM算法（期望-最大化算法）。第一個步驟是策略評估，即當(dāng)前我們在優(yōu)化這個策略 π\(zhòng)piπ ，在優(yōu)化過程中通過評估從而得到一個更新的策略；第二個步驟是策略提升，即取得價值函數(shù)后，進一步推算出它的Q函數(shù)，得到它的最大值。

（3）價值迭代： 我們一直迭代貝爾曼最優(yōu)方程，通過迭代，其能逐漸趨向于最佳策略，這是價值迭代方法的核心。我們?yōu)榱说玫阶罴训?V?V^*V? ，對于每個狀態(tài)的 V?V^*V? 值，直接使用貝爾曼最優(yōu)方程進行迭代，迭代多次之后它就會收斂到最佳策略及其對應(yīng)的狀態(tài)，這里是沒有策略函數(shù)的。

3.面試必知必答

3.1友善的面試官：請問馬爾可夫過程是什么？馬爾可夫決策過程又是什么？其中馬爾可夫最重要的性質(zhì)是什么呢？

馬爾可夫過程是一個二元組 <S,P><S,P><S,P> ， SSS 為狀態(tài)集合， PPP 為狀態(tài)轉(zhuǎn)移函數(shù)；

馬爾可夫決策過程是一個五元組 <S,P,A,R,γ><S,P,A,R,\gamma><S,P,A,R,γ>， 其中 RRR 表示從 SSS 到 S′S’S′ 能夠獲得的獎勵期望， γ\gammaγ 為折扣因子， AAA 為動作集合；

馬爾可夫最重要的性質(zhì)是下一個狀態(tài)只與當(dāng)前狀態(tài)有關(guān)，與之前的狀態(tài)無關(guān)，也就是 p(st+1∣st)=p(st+1∣s1,s2,…,st)p(s_{t+1} | s_t)= p(s_{t+1}|s_1,s_2,…,s_t)p(st+1∣st)=p(st+1∣s1,s2,…,st)。

3.2友善的面試官：請問我們一般怎么求解馬爾可夫決策過程？

我們求解馬爾可夫決策過程時，可以直接求解貝爾曼方程或動態(tài)規(guī)劃方程：

V(s)=R(S)+γ∑s′∈Sp(s′∣s)V(s′)V(s)=R(S)+ \gamma \sum_{s’ \in S}p(s’|s)V(s’)V(s)=R(S)+γ∑s′∈Sp(s′∣s)V(s′)

特別地，其矩陣形式為 V=R+γPV\mathrm{V}=\mathrm{R}+\gamma \mathrm{PV}V=R+γPV。但是貝爾曼方程很難求解且計算復(fù)雜度較高，所以可以使用動態(tài)規(guī)劃、蒙特卡洛以及時序差分等方法求解。

3.3友善的面試官：請問如果數(shù)據(jù)流不具備馬爾可夫性質(zhì)怎么辦？應(yīng)該如何處理？

如果不具備馬爾可夫性，即下一個狀態(tài)與之前的狀態(tài)也有關(guān)，若僅用當(dāng)前的狀態(tài)來求解決策過程，勢必導(dǎo)致決策的泛化能力變差。為了解決這個問題，可以利用循環(huán)神經(jīng)網(wǎng)絡(luò)對歷史信息建模，獲得包含歷史信息的狀態(tài)表征，表征過程也可以使用注意力機制等手段，最后在表征狀態(tài)空間求解馬爾可夫決策過程問題。

3.4友善的面試官：請分別寫出基于狀態(tài)價值函數(shù)的貝爾曼方程以及基于動作價值函數(shù)的貝爾曼方程。

（1）基于狀態(tài)價值函數(shù)的貝爾曼方程: Vπ(s)=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)[r(s,a)+γVπ(s′)]V_{\pi}(s) = \sum_{a}{\pi(a|s)}\sum_{s’,r}{p(s’,r|s,a)[r(s,a)+\gamma V_{\pi}(s’)]}Vπ(s)=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)[r(s,a)+γVπ(s′)]；

（2）基于動作價值函數(shù)的貝爾曼方程: Qπ(s,a)=∑s′,rp(s′,r∣s,a)[r(s′,a)+γVπ(s′)]Q_{\pi}(s,a)=\sum_{s’,r}p(s’,r|s,a)[r(s’,a)+\gamma V_{\pi}(s’)]Qπ(s,a)=∑s′,rp(s′,r∣s,a)[r(s′,a)+γVπ(s′)]。

3.5 友善的面試官：請問最佳價值函數(shù) V?V^*V? 和最佳策略 π?\pi^*π? 為什么等價呢？

最佳價值函數(shù)的定義為 V?(s)=max?πVπ(s)V^* (s)=\max_{\pi} V_{\pi}(s)V?(s)=maxπVπ(s) ，即我們搜索一種策略 π\(zhòng)piπ 來讓每個狀態(tài)的價值最大。V?V^V? 就是到達(dá)每一個狀態(tài)其的最大價值，同時我們得到的策略就可以說是最佳策略，即 π?(s)=arg?max?π Vπ(s)\pi^{}(s)=\underset{\pi}{\arg \max }~ V_{\pi}(s)π?(s)=πargmax Vπ(s) 。最佳策略使得每個狀態(tài)的價值函數(shù)都取得最大值。所以如果我們可以得到一個最佳價值函數(shù)，就可以說某一個馬爾可夫決策過程的環(huán)境被解。在這種情況下，其最佳價值函數(shù)是一致的，即其達(dá)到的上限的值是一致的，但這里可能有多個最佳策略對應(yīng)于相同的最佳價值。

3.6友善的面試官：能不能手寫一下第nnn步的價值函數(shù)更新公式呀？另外，當(dāng) nnn 越來越大時，價值函數(shù)的期望和方差是分別變大還是變小呢？

nnn 越大，方差越大，期望偏差越小。價值函數(shù)的更新公式如下：

Q(S,A)←Q(S,A)+α[∑i=1nγi?1rt+i+γnmax?aQ(S′,a)?Q(S,A)]Q\left(S, A\right) \leftarrow Q\left(S, A\right)+\alpha\left[\sum_{i=1}^{n} \gamma^{i-1} r_{t+i}+\gamma^{n} \max _{a} Q\left(S’,a\right)-Q\left(S, A\right)\right]Q(S,A)←Q(S,A)+α[i=1∑nγi?1rt+i+γnamaxQ(S′,a)?Q(S,A)]

更多優(yōu)質(zhì)內(nèi)容請關(guān)注公號：汀丶人工智能文章來源地址http://www.zghlxwxcb.cn/news/detail-843500.html

到了這里，關(guān)于強化學(xué)習(xí)從基礎(chǔ)到進階-常見問題和面試必知必答[2]：馬爾科夫決策、貝爾曼方程、動態(tài)規(guī)劃、策略價值迭代的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！