引言

在概率論及統(tǒng)計(jì)學(xué)中，馬爾可夫過程（英語：Markov process）是一個(gè)具備了馬爾可夫性質(zhì)的隨機(jī)過程，因?yàn)槎韲鴶?shù)學(xué)家安德雷·馬爾可夫得名。馬爾可夫過程是不具備記憶特質(zhì)的（memorylessness）。換言之，馬爾可夫過程的條件概率僅僅與系統(tǒng)的當(dāng)前狀態(tài)相關(guān)，而與它的過去歷史或未來狀態(tài)，都是獨(dú)立、不相關(guān)的。

概論

馬爾可夫模型分成四種：馬爾可夫鏈、隱馬爾可夫模型（HMM）、馬爾可夫決策過程（MDP）和部分可觀測(cè)馬爾可夫決策過程（POMDP）

最簡(jiǎn)單的馬爾可夫模型是馬爾可夫鏈。它用一個(gè)隨時(shí)間變化的隨機(jī)變量來模擬系統(tǒng)的狀態(tài)。在這種情況下，馬爾可夫性質(zhì)表明，這個(gè)變量的分布只取決于之前狀態(tài)的分布。當(dāng)馬爾可夫鏈的狀態(tài)只能部分觀察到，這就是隱馬爾可夫模型。隱馬爾可夫模型常用的用途是語音識(shí)別，它是大多數(shù)現(xiàn)代自動(dòng)語音識(shí)別系統(tǒng)的基礎(chǔ)。

馬爾可夫決策過程也是馬爾可夫鏈，但其狀態(tài)轉(zhuǎn)換取決于當(dāng)前狀態(tài)和應(yīng)用于系統(tǒng)的動(dòng)作向量。通常，使用馬爾可夫決策過程來計(jì)算行動(dòng)策略，該行為策略將最大限度地提高與預(yù)期獎(jiǎng)勵(lì)相關(guān)的某種效用。它與強(qiáng)化學(xué)習(xí)密切相關(guān)，可以用價(jià)值迭代法和相關(guān)方法解決。

部分可觀測(cè)馬爾可夫決策過程是一個(gè)系統(tǒng)的狀態(tài)只被部分觀察到的馬爾可夫決策過程，其中系統(tǒng)的狀態(tài)只被部分觀察到。部分可觀測(cè)馬爾可夫決策過程可以用于控制簡(jiǎn)單代理或機(jī)器人。

馬爾可夫模型還包括馬爾可夫隨機(jī)場(chǎng)（MRF）和馬爾可夫鏈蒙特卡洛（MCMC）——這兩個(gè)模型也常常被用于近似和預(yù)測(cè)—— Tolerant Markov model (TMM)、層級(jí)馬爾科夫模型（Hierarchical Markov models）、層級(jí)隱馬爾可夫模型(hierarchicalhiddenMarkov model)等。

一、馬爾科夫決策過程

機(jī)器學(xué)習(xí)算法（有監(jiān)督，無監(jiān)督，弱監(jiān)督）中，馬爾科夫決策過程是弱監(jiān)督中的一類叫增強(qiáng)學(xué)習(xí)。增加學(xué)習(xí)與傳統(tǒng)的有監(jiān)督和無監(jiān)督不同的地方是，這些方法都是一次性決定最終結(jié)果的，而無法刻畫一個(gè)決策過程，無法直接定義每一次決策的優(yōu)劣，也就是說每一次的決策信息都是弱信息，所以某種程度上講，強(qiáng)化學(xué)習(xí)也屬于弱監(jiān)督學(xué)習(xí)。從模型角度來看，也屬于馬爾科夫模型，其與隱馬爾科夫模型有非常強(qiáng)的可比性。

下面是一個(gè)常用的馬爾科夫模型的劃分關(guān)系

1.1 馬爾科夫決策過程定義

馬爾可夫決策過程并不要求 $S$ 或者 $A$ 是有限的，但基礎(chǔ)的算法中假設(shè)它們由有限的

狀態(tài)(state): 智能體在每個(gè)步驟中所處于的狀態(tài)集合
行為(action): 智能體在每個(gè)步驟中所能執(zhí)行的動(dòng)作集合
轉(zhuǎn)移概率(transition): 智能體處于狀態(tài)s下，執(zhí)行動(dòng)作a后，會(huì)轉(zhuǎn)移到狀態(tài)s’的概率
獎(jiǎng)勵(lì)(reward): 智能體處于狀態(tài)s下，執(zhí)行動(dòng)作a后，轉(zhuǎn)移到狀態(tài)s’后獲得的立即獎(jiǎng)勵(lì)值
策略(policy): 智能體處于狀態(tài)s下，應(yīng)該執(zhí)行動(dòng)作a的概率

MDP考慮了動(dòng)作，即系統(tǒng)下個(gè)狀態(tài)不僅和當(dāng)前的狀態(tài)有關(guān)，也和當(dāng)前采取的動(dòng)作有關(guān)。舉下棋的例子，當(dāng)我們?cè)谀硞€(gè)局面（狀態(tài)s）走了一步(動(dòng)作a)，這時(shí)對(duì)手的選擇（導(dǎo)致下個(gè)狀態(tài)s’）我們是不能確定的，但是他的選擇只和s和a有關(guān)，而不用考慮更早之前的狀態(tài)和動(dòng)作，即s’是根據(jù)s和a隨機(jī)生成的。

值得注意的是，在馬爾科夫決策過程中，狀態(tài)集合是離散的，動(dòng)作集合是離散的，轉(zhuǎn)移概率是已知的，獎(jiǎng)勵(lì)是已知的。在這個(gè)條件下的學(xué)習(xí)稱之為有模型學(xué)習(xí)。

1.1.1 MDP的動(dòng)態(tài)過程

1.1.2 策略 $\pi$

a policy $\pi$ is a distribution over actionsgiven states
$\pi (a|s)=P[A_t=a|S_t=s]$
A policy fully defines the behaviour of an agent

1.1.3 值函數(shù)

1.1.4 馬爾科夫過程的描述

我們分三種情況來討論：

• T=1, greedy case. 這時(shí)算法是退化的，拿我們的例子而言，機(jī)器人只會(huì)考慮下一步動(dòng)作帶來的影響，而不會(huì)考慮之后一系列動(dòng)作帶來的影響。但是這個(gè)算法卻在實(shí)際應(yīng)用中起著重要作用，是很多機(jī)器人問題的最優(yōu)解。因?yàn)樗?jì)算起來非常簡(jiǎn)單。它的缺點(diǎn)也很明顯，容易陷入局部最優(yōu)。很明顯，此時(shí) γ 的取值不影響結(jié)果，只要滿足 γ>1 即可。
• 1<T<∞, finite?horizon case. 此時(shí)，一般會(huì)取 γ=1. 意思是說每個(gè)狀態(tài)轉(zhuǎn)換的收益權(quán)重是一樣的。有人會(huì)說這種 finite-horizon 的處理方式是最符合實(shí)際情況的。但事實(shí)上，這種 finite-horizon的情況處理起來比下邊提到的infinite-horizon更加復(fù)雜。因?yàn)槲覀円蟮膭?dòng)作序列是時(shí)間的函數(shù)。也就是說，即便是從相同的狀態(tài)開始計(jì)算，由于時(shí)間參數(shù) T 不同，最后得到的最優(yōu)動(dòng)作序列會(huì)不同。課本里的原話是， Near the far end of the time horizon, for example, the optimal policy might differ substantially from the optimal choice earlier in time, even under otherwise identical conditions (e.g., same state, same belief). As a result, planning algorithms with finite horizon are forced to maintain different plans for different horizons, which can add undesired complexity.
• T=∞, infinite?horizon case. 這種情況不會(huì)有上邊所提到的計(jì)算復(fù)雜度增加的問題，因?yàn)?T 是無窮大的。在這種情況下， γ 的取值很重要，因?yàn)樗枰ＷC計(jì)算結(jié)果是收斂的。假設(shè) $R_{at}$ 是有界的， |Rat|≤$r_{max}$. 那么我們可以得到
  

1.2 問題求解

兩種求解有限狀態(tài)MDP具體策略的有效算法。這里，我們只針對(duì)MDP是有限狀態(tài)、有限動(dòng)作的情況。

1.2.1 策略迭代算法

1.2.2 值迭代算法

1.3 實(shí)例

1.3.1 策略迭代實(shí)例

使用馬爾科夫決策過程策略迭代算法進(jìn)行計(jì)算，具體過程詳見，

https://github.com/persistforever/ReinforcementLearning/tree/master/carrental

1.3.2 值迭代實(shí)例

賭徒問題 ：一個(gè)賭徒拋硬幣下賭注，如果硬幣正面朝上，他本局將贏得和下注數(shù)量相同的錢，如果硬幣背面朝上，他本局將輸?shù)粝伦⒌腻X，當(dāng)他輸光所有的賭資或者贏得$100則停止賭博，硬幣正面朝上的概率為p。賭博過程是一個(gè)無折扣的有限的馬爾科夫決策問題。

使用馬爾科夫決策過程值迭代算法進(jìn)行計(jì)算，具體過程詳見，
https://github.com/persistforever/ReinforcementLearning/tree/master/gambler

1.4 MDP中的參數(shù)估計(jì)

1.4.1 Policies策略

1.4.2 Policy based Value Function基于策略的價(jià)值函數(shù)

1.4.3 Bellman Expectation Equation貝爾曼期望方程

1.4.4 Optimal Value Function最優(yōu)價(jià)值函數(shù)

1.4.5 Theorem of MDP定理

1.4.6 Finding an Optimal Policy尋找最優(yōu)策略

1.4.7 Bellman Optimality Equation貝爾曼最優(yōu)方程

1.4.7.1 Solving the Bellman Optimality Equation求解貝爾曼最優(yōu)方程

貝爾曼最優(yōu)方程是非線性的，通常而言沒有固定的解法，有很多著名的迭代解法：

• Value Iteration 價(jià)值迭代
• Policy Iteration 策略迭代
• Q-learning
• Sarsa

這個(gè)可以大家之后去多了解了解。

1.5 最優(yōu)決策

也許上面的目標(biāo)函數(shù)還不清晰，如何求解最有決策，如何最大化累積回報(bào)

下面結(jié)合例子來介紹如何求解上面的目標(biāo)函數(shù)。且說明累積回報(bào)函數(shù)本身就是一個(gè)過程的累積回報(bào)，回報(bào)函數(shù)才是每一步的回報(bào)。

下面再來看求解上述最優(yōu)問題，其中 就是以s為初始狀態(tài)沿著決策函數(shù)走到結(jié)束狀態(tài)的累積回報(bào)。

1.6 值迭代

1.7 策略迭代

值迭代是使累積回報(bào)值最優(yōu)為目標(biāo)進(jìn)行迭代，而策略迭代是借助累積回報(bào)最優(yōu)即策略最優(yōu)的等價(jià)性，進(jìn)行策略迭代。

1.8 MDP中的參數(shù)估計(jì)

回過頭來再來看前面的馬爾科夫決策過程的定義是一個(gè)五元組，一般情況下，五元組應(yīng)該是我們更加特定的問題建立馬爾科夫決策模型時(shí)該確定的，并在此基礎(chǔ)上來求解最優(yōu)決策。所以在求解最優(yōu)決策之前，我們還需更加實(shí)際問題建立馬爾科夫模型，建模過程就是確定五元組的過程，其中我們僅考慮狀態(tài)轉(zhuǎn)移概率，那么也就是一個(gè)參數(shù)估計(jì)過程。（其他參數(shù)一般都好確定，或設(shè)定）。

假設(shè)，在時(shí)間過程中，我們有下面的狀態(tài)轉(zhuǎn)移路徑：

二、連續(xù)時(shí)間馬爾科夫過程

2.1 連續(xù)時(shí)間馬爾科夫鏈的一般定義

和起始時(shí)間t無關(guān)的話，我們稱這是時(shí)間齊次的馬爾科夫鏈。這個(gè)轉(zhuǎn)移矩陣和離散時(shí)間不同的是，離散時(shí)間給出的是一步轉(zhuǎn)移概率，但是連續(xù)馬爾科夫鏈的轉(zhuǎn)移概率給出的是和時(shí)間相關(guān)的。

2.2 連續(xù)時(shí)間馬爾科夫鏈的另一類定義

我們考慮連續(xù)時(shí)間馬爾科夫鏈從一個(gè)狀態(tài) i開始，到狀態(tài)發(fā)生變化，比如變成j所經(jīng)過的時(shí)間，由于馬爾科夫鏈的馬爾科夫性，這個(gè)時(shí)間是具有無記憶性的，所以這個(gè)時(shí)間是服從指數(shù)分布的。這和離散時(shí)間馬爾科夫鏈?zhǔn)敲芮邢嚓P(guān)的，離散時(shí)間馬爾科夫鏈中的時(shí)間是離散時(shí)間，因?yàn)橛蔁o記憶性，所以是服從幾何分布的。
這樣我們就可以這樣定義連續(xù)時(shí)間馬爾科夫鏈。馬爾科夫鏈?zhǔn)沁@樣的一個(gè)過程。

• (i)在轉(zhuǎn)移到不同的狀態(tài) $i$前，它處于這個(gè)狀態(tài)的時(shí)間是速率為$v_i$的指數(shù)分布。
• (ii)當(dāng)離開狀態(tài) $i$時(shí)，以某種概率$P_{ij}$進(jìn)入下一個(gè)狀態(tài)$j$,當(dāng)然$P_{ij}$滿足
  

對(duì)比于半馬爾科夫鏈，我們可以發(fā)現(xiàn)，連續(xù)時(shí)間馬爾科夫鏈?zhǔn)且环N特殊的半馬爾科夫鏈，在一個(gè)狀態(tài)所待的時(shí)間是只不過是一個(gè)具體的分布–指數(shù)分布，而半馬爾科夫鏈只是說所待的時(shí)間是任意的一個(gè)隨機(jī)時(shí)間。

2.3 生滅過程

2.4 連續(xù)時(shí)間馬爾科夫鏈的兩個(gè)定義(2.1和2.2)之間的關(guān)系

接下來，我們舉個(gè)例子來說明馬爾科夫鏈的極限分布的應(yīng)用

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

2.5 最優(yōu)決策

也許上面的目標(biāo)函數(shù)還不清晰，如何求解最優(yōu)決策，如何最大化累積回報(bào)

下面結(jié)合例子來介紹如何求解上面的目標(biāo)函數(shù)。且說明累積回報(bào)函數(shù)本身就是一個(gè)過程的累積回報(bào)，回報(bào)函數(shù)才是每一步的回報(bào)。

下面再來看求解上述最優(yōu)問題，其中 就是以s為初始狀態(tài)沿著決策函數(shù)走到結(jié)束狀態(tài)的累積回報(bào)。

2.5.1 值迭代

2.5.2 策略迭代

值迭代是使累積回報(bào)值最優(yōu)為目標(biāo)進(jìn)行迭代，而策略迭代是借助累積回報(bào)最優(yōu)即策略最優(yōu)的等價(jià)性，進(jìn)行策略迭代。

2.6 MDP中的參數(shù)估計(jì)

回過頭來再來看前面的馬爾科夫決策過程的定義是一個(gè)五元組，一般情況下，五元組應(yīng)該是我們更加特定的問題建立馬爾科夫決策模型時(shí)該確定的，并在此基礎(chǔ)上來求解最優(yōu)決策。所以在求解最優(yōu)決策之前，我們還需更加實(shí)際問題建立馬爾科夫模型，建模過程就是確定五元組的過程，其中我們僅考慮狀態(tài)轉(zhuǎn)移概率，那么也就是一個(gè)參數(shù)估計(jì)過程。（其他參數(shù)一般都好確定，或設(shè)定）。

假設(shè)，在時(shí)間過程中，我們有下面的狀態(tài)轉(zhuǎn)移路徑：

2.7 轉(zhuǎn)移速率

連續(xù)時(shí)間馬爾科夫鏈的假設(shè)

• 當(dāng)前狀態(tài)i到下一個(gè)轉(zhuǎn)移的時(shí)間服從參數(shù)$v_i$的指數(shù)分布，且獨(dú)立于之前的歷史過程和下一個(gè)狀態(tài)
• 當(dāng)前狀態(tài)i以概率$p_{ij}$到達(dá)下一個(gè)狀態(tài)j，而且獨(dú)立于之前的歷史過程和下一個(gè)狀態(tài)

三、馬爾可夫鏈

3.1 一些定義

3.2 C-K方程

查普曼-柯爾莫格洛夫方程(Chapman-Kolmogorov equation,C-K equation)給出了計(jì)算 [公式] 步轉(zhuǎn)移概率的一個(gè)方法：

3.3 狀態(tài)的分類

命題得證。

很顯然，暫態(tài)也是一個(gè)類性質(zhì)。而利用上述性質(zhì)可以得到：有限馬爾可夫鏈的所有狀態(tài)不可能都是暫態(tài)，有限不可約馬爾可夫鏈的所有狀態(tài)都是常返態(tài)。

3.4 長(zhǎng)程性質(zhì)和極限概率

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

馬爾可夫決策過程為決策者在隨機(jī)環(huán)境下做出決策提供了數(shù)學(xué)架構(gòu)模型，為動(dòng)態(tài)規(guī)劃與強(qiáng)化學(xué)習(xí)的最優(yōu)化問題提供了有效的數(shù)學(xué)工具，廣泛用于機(jī)器人學(xué)、自動(dòng)化控制、經(jīng)濟(jì)學(xué)、以及工業(yè)界等領(lǐng)域。當(dāng)我們提及馬爾可夫決策過程時(shí)，我們一般特指其在離散時(shí)間中的隨機(jī)控制過程：即對(duì)于每個(gè)時(shí)間節(jié)點(diǎn)，當(dāng)該過程處于某狀態(tài)(s)時(shí)，決策者可采取在該狀態(tài)下被允許的任意決策(a)，此后下一步系統(tǒng)狀態(tài)將隨機(jī)產(chǎn)生，同時(shí)回饋給決策者相應(yīng)的期望值

，該狀態(tài)轉(zhuǎn)移具有馬爾可夫性質(zhì)。

https://zhuanlan.zhihu.com/p/35354956

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

四、馬爾可夫過程

https://zhuanlan.zhihu.com/p/30317123

五、Markov Reward Process馬爾可夫獎(jiǎng)勵(lì)過程

5.1 MRP

簡(jiǎn)單來說，馬爾可夫獎(jiǎng)勵(lì)過程就是含有獎(jiǎng)勵(lì)的馬爾可夫鏈，要想理解MRP方程的含義，我們就得弄清楚獎(jiǎng)勵(lì)函數(shù)的由來，我們可以把獎(jiǎng)勵(lì)表述為進(jìn)入某一狀態(tài)后收獲的獎(jiǎng)勵(lì)。獎(jiǎng)勵(lì)函數(shù)如下所示：

5.2 Return回報(bào)

5.3 Value Function價(jià)值函數(shù)

5.4 Bellman Equation貝爾曼方程

六、廣義馬爾科夫模型

廣義馬爾科夫模型 (generalized Markov model) 指的是連續(xù)時(shí)間上的隨機(jī)過程，在一系列時(shí)間點(diǎn)$0\le S_1\le S_2\le \le ...$上滿足Markov特性。

6.1 Markov renewal process

In probability and statistics, a Markov renewal process (MRP) is a random process that generalizes the notion of Markov jump processes. Other random processes like Markov chains, Poisson processes and renewal processes can be derived as special cases of MRP’s.

Consider a state space $\mathrm{S}$. Consider a set of random variables $(X_n,T_n)$, where $T_n$ are the jump times and $X_{n} $are the associated states in the Markov chain (see Figure above). Let the inter-arrival time, ${\tau }_n=T_n?T_{n?1}$. Then the sequence $(X_n,T_n)$ is called a Markov renewal process if

What is Markov Modulated Poisson Process (MMPP)
1.A process, belonging to the class of markov renewal processes, where arrivals occur according to a statedependent poisson process with different rates governed by a continuous-time markov chain.

https://mp.weixin.qq.com/s?__biz=Mzg3OTAyMjcyMw==&mid=2247485738&idx=1&sn=f31a646d6cee548fd99525d2c798fdf4&chksm=cf0b8ec6f87c07d05960be03b64eddbce47426bc6ccaef7a97c49c2ff5f23c07a940e2b557cf&token=1326040548&lang=zh_CN#rd
https://zhuanlan.zhihu.com/p/149765762
http://xtf615.com/2017/07/15/RL/
https://zhuanlan.zhihu.com/p/271221558
https://zhuanlan.zhihu.com/p/148932940

總結(jié)

以上是生活随笔為你收集整理的马尔可夫决策过程 Markov decision process MDP, 连续时间Markov chain, CMDP（全）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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