3 马尔可夫决策过程

如果要用强化学习去解决一个实际问题，第一步要做的事情就是把这个实际问题抽象为一个马尔可夫决策过程，也就是明确马尔可夫决策过程的各个组成要素。

3.1 马尔可夫过程

3.2.1 随机过程

时刻\(t+1\)的状态\(S_{t+1}\)概率可以表示为\(P(S_{t+1}|S_1,S_2,...,S_t)\)，即未来的状态取决于过去的状态以及当前的状态。

3.2.2 马尔可夫性质

当且仅当未来状态的概率分布只依赖于当前状态时，这个随机过程具有马尔可夫性质。即：\(P(S_{t+1}|S_t)=P(S_{t+1}|S_1,S_2,...,S_t)\)

但是并不是说\(S_{t+1}\)和历史完全没有关系，因为\(S_{t+1}\)是由\(S_t\)决定的，而\(S_t\)又是由\(S_{t-1}\)决定的，以此类推，\(S_{t+1}\)和历史是有关系的，只是说\(S_{t+1}\)和历史的关系可以通过当前状态\(S_t\)来表示。

3.2.3 马尔可夫过程

马尔可夫过程(马尔科夫链)是指具有马尔可夫性质的随机过程。

通常用元组\(\langle S,P\rangle\)来表示马尔可夫过程，其中\(S\)是有限数量的状态集，\(P\)是状态转移矩阵。

假设状态集\(S\)有\(n\)个状态，状态转移矩阵\(P\)是一个\(n\times n\)的矩阵： \[ P=\begin{bmatrix} P(s_1|s_1) & P(s_2|s_1) & ... & P(s_n|s_1) \\ P(s_1|s_2) & P(s_2|s_2) & ... & P(s_n|s_2) \\ ... & ... & ... & ... \\ P(s_1|s_n) & P(s_2|s_n) & ... & P(s_n|s_n) \\ \end{bmatrix} \] \(P(s_i|s_j)\)表示从状态\(s_j\)转移到状态\(s_i\)的概率，被称为状态转移函数。从某个状态出发，到达其他状态的概率和必须为1，即状态转移矩阵的每一行之和为1。

举个例子如图所示： 可以写出如下的状态转移矩阵： \[ P=\begin{bmatrix} 0.9 & 0.1 & 0 & 0 & 0 & 0\\ 0.5 & 0 & 0.5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.6 & 0 & 0.4 \\ 0 & 0 & 0 & 0 & 0.3 & 0.7 \\ 0 & 0.2 & 0.3 & 0.5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \] 其中每一个节点都是一个状态(\(s_6\)通常被称为终止状态)。

给定一个马尔可夫过程，我们就可以从某个状态出发，根据它的状态转移矩阵生成一个状态序列（episode），这个步骤也被叫做采样（sampling）。例如，从状态\(s_1\)出发，根据状态转移矩阵\(P\)，可以生成一个状态序列\(s_1\rightarrow s_2\rightarrow s_3\rightarrow s_6\)，也可以是\(s_1\rightarrow s_1\rightarrow s_2\rightarrow s_3\rightarrow s_4 \rightarrow s_5\rightarrow s_3\rightarrow s_6\)。生成这些序列的概率和状态转移矩阵有关。

3.3 马尔可夫奖励过程