1 引言

馬爾可夫性：無(wú)后效性，指系統(tǒng)的下個(gè)狀態(tài)只與當(dāng)前狀態(tài)信息有關(guān)，而與更早之前的狀態(tài)無(wú)關(guān)；
馬爾可夫鏈(Markov Chain, MC)：系統(tǒng)的下一個(gè)狀態(tài)只與當(dāng)前狀態(tài)相關(guān)；
馬爾可夫決策過(guò)程(Markov Decision Process, MDP)：具有馬爾可夫性，與MC不同的是MDP還考慮了動(dòng)作，即系統(tǒng)下個(gè)狀態(tài)不僅和當(dāng)前的狀態(tài)有關(guān)，也和當(dāng)前采取的動(dòng)作有關(guān)。
以下棋為例：我們?cè)谀硞€(gè)局面（狀態(tài)$s_i$）走了一步(動(dòng)作$a_i$)，這時(shí)對(duì)手的選擇（導(dǎo)致下個(gè)狀態(tài)$s_{i+1}$）我們是不能確定的，但是他的選擇只和$s_i$和$a_i$有關(guān)，而不用考慮更早之前的狀態(tài)和動(dòng)作。

2 馬爾可夫決策過(guò)程

一個(gè)馬爾可夫決策過(guò)程可以由一個(gè)四元組表示：
$$M=(S,A,P_{sa},R)\text{\hspace{1em}(1)}$$

• $S=\{s_1,s_2,\dots ,s_k\}$：狀態(tài)集(states)，$s_i$表示第$i$步的狀態(tài);
• $A=\{a_1,a_2,\dots ,a_k\}$：一組動(dòng)作(actions)，$a_i$表示第$i$步的動(dòng)作;
• $P_{sa}$：狀態(tài)轉(zhuǎn)移概率，當(dāng)前$s_i\in S$狀態(tài)下，經(jīng)過(guò)$a_i\in A$作用后，會(huì)轉(zhuǎn)移到的其它狀態(tài)的概率分布情況，例如比如，在狀態(tài)$s_i\in S$下執(zhí)行動(dòng)作$a_i\in A$，轉(zhuǎn)移到$s_{i+1}\in S$的概率可以表示為$p(s_{i+1}|s_i,a_i)$;
• $R:S\times A?\mathbb{R}$：回報(bào)函數(shù)(reward function)，如果回報(bào)只與狀態(tài)有關(guān)，可以簡(jiǎn)化為$R:S?\mathbb{R}$。如果一組$(s_i,a_i)$轉(zhuǎn)移到了下個(gè)狀態(tài)$s_{i+1}$，那么回報(bào)函數(shù)可記為$r(s_{i+1}|s_i,a_i)$。如果$(s_i,a_i)$對(duì)應(yīng)的下個(gè)狀態(tài)$s_{i+1}$是唯一的，那么回報(bào)函數(shù)也可以記為$r(s_i,a_i)$。

MDP 的動(dòng)態(tài)過(guò)程如下：

• 智能體(agent)的初始狀態(tài)為$s_0$;
• 從 $A$ 中挑選一個(gè)動(dòng)作$a_0$執(zhí)行，執(zhí)行后，agent 按$P_{sa}$概率隨機(jī)轉(zhuǎn)移到了下一個(gè)$s_1$狀態(tài)，$s_1\in P_{s_0{a}_0}$。
• 然后再執(zhí)行一個(gè)動(dòng)作$a_1$，就轉(zhuǎn)移到了$s_2$，接下來(lái)再執(zhí)行$a_2$，…；
• 可以用下面的圖表示狀態(tài)轉(zhuǎn)移的過(guò)程：

如果回報(bào)$r_i$是根據(jù)狀態(tài)$s_i$和動(dòng)作$a_i$得到的，則MDP可以如圖表示：

3 值函數(shù)(value function)

增強(qiáng)學(xué)習(xí)學(xué)到的是一個(gè)從環(huán)境狀態(tài)到動(dòng)作的映射（即行為策略），記為策略$\pi :S\to A$。而增強(qiáng)學(xué)習(xí)往往又具有延遲回報(bào)的特點(diǎn): 如果在第$n$步輸?shù)袅似?#xff0c;那么只有狀態(tài)$s_n$和動(dòng)作$a_n$獲得了立即回報(bào)$r(s_n,a_n)=?1$，前面的所有狀態(tài)立即回報(bào)均為0。所以對(duì)于之前的任意狀態(tài)$s$和動(dòng)作$a$，立即回報(bào)函數(shù)$r(s,a)$無(wú)法說(shuō)明策略的好壞。因而需要定義值函數(shù)(value function，又叫效用函數(shù))來(lái)表明當(dāng)前狀態(tài)下策略$\pi$的長(zhǎng)期影響。

• $V^{\pi }(s)$：策略$\pi$下，狀態(tài)$s$的值函數(shù)；
• $r_i$：未來(lái)第$i$步的立即回報(bào)。

常見(jiàn)的值函數(shù)有以下三種：
$$V^{\pi }(s)=E_{\pi }\left[\sum _{i=0}^h{r}_i|s_0=s\right]\text{\hspace{1em}(2)}$$

$$V^{\pi }(s)=\underset{h\to \infty }{\lim }{E}_{\pi }\left[\frac{1}{h}\sum _{i=0}^h{r}_i|s_0=s\right]\text{\hspace{1em}(3)}$$

$$V^{\pi }(s)=E_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_i|s_0=s\right]\text{\hspace{1em}(4)}$$
其中：
a) 是采用策略π的情況下未來(lái)有限h步的期望立即回報(bào)總和；
b) 是采用策略π的情況下期望的平均回報(bào)；
c) 是值函數(shù)最常見(jiàn)的形式，式中$\gamma \in [0,1]$稱為折合因子，表明了未來(lái)的回報(bào)相對(duì)于當(dāng)前回報(bào)的重要程度。特別的，$\gamma =0$時(shí)，相當(dāng)于只考慮立即不考慮長(zhǎng)期回報(bào)，$\gamma =1$時(shí)，將長(zhǎng)期回報(bào)和立即回報(bào)看得同等重要。

4 策略

5 對(duì)2048游戲的建模

$s_1$： 初始化狀態(tài)，隨機(jī)產(chǎn)生的棋盤；
$a_1$：用戶連接相同的數(shù)字后，系統(tǒng)為棋盤分配新數(shù)字的動(dòng)作；
$s_2$：用戶選擇如何連線后導(dǎo)致的下一個(gè)棋盤，該棋盤依然有空缺，需要填充新數(shù)字；
$p(s_2|s_1,a_1)$：經(jīng)過(guò)$a_1$操作后狀態(tài)從$s_1$到$s_2$的概率，這個(gè)我覺(jué)得可以通過(guò)統(tǒng)計(jì)得到；
獎(jiǎng)勵(lì)函數(shù)：是設(shè)計(jì)的難點(diǎn)
如何進(jìn)行訓(xùn)練：也是一個(gè)難點(diǎn)

總結(jié)

以上是生活随笔為你收集整理的如何理解马尔可夫决策过程？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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