• 马尔可夫过程（MP）
• 马尔可夫奖励过程（MRP）
• 马尔可夫决策过程（MDP）

马尔可夫过程（MP）

“ The future is independent of the past given the present ”，也就是说对当前而言，未来与过去是毫无关系的。

马尔可夫状态定义如下：

$P(s_{t+1}|s_t) = P(s_{t+1}|s_1,\cdots,s_t)$

即当前状态的前提下，下个状态发生的概率 = 当前状态及其之前所有状态的前提下，下一个状态发生的概率。可以理解为，当前状态已经包含了历史所有信息。未来只与当前状态有关，现在是过去的充分统计。

该性质称为马尔可夫性质。

状态转移概率定义如下：

$P_{ss'}=P(s_{t+1}=s'|s_{t}=s)$

将所有状态转移概率写成矩阵形式，得到状态转移矩阵：

$\begin{aligned} &\qquad\quad\text{(to)}\\ P=\text{(from)}&\begin{bmatrix} P_{11}&\cdots&P_{1,n}\\ \vdots\\ P_{n1}&\cdots&P_{nn} \end{bmatrix} \end{aligned}$

马尔可夫过程（Markov Process）定义如下：

马尔可夫过程（马尔科夫链）是一个元组$<S,P>$，$S$是有限状态集，$P$是状态转移矩阵。

马尔可夫奖励过程（MRP）

首先我们设想一下，现在我们处于“ 大学生 ”状态，之后可能的状态有“ 读研 ”和“ 找工作 ”，选择不同的“ 状态 ”将会有不同的“ 未来 ”，未来的“ 收入 ”当然也就有所区别了。现在我们假设选择了“ 读研 ”，以经济学中“ 折现 ”的概念来理解未来的“ 收入 ”，我们现在的选择其实已经一定程度上转换成了“ 一定折扣的未来收入 ”。

这就是所谓的累计奖励（Return），即在一条马尔科夫奖励链上从$t$时刻开始往后所有的奖励（Reward）的有衰减总和，定义如下：

$G_t=R_{t+1}+\gamma R_{t+2}+\cdots=\sum_{k=0}^\infty \gamma^{k}R_{t+k+1}$

其中$\gamma$​是折扣因子。就像未来的钱会贬值一样，$\gamma$​通常取[0,1]。$G_t$、$R_{t+1}$其实也可以理解为所有马尔科夫链收益值的集合。

值函数（Value）给出了当前状态​的期望，定义如下：

$v(s)=E(G_t|S_t=s)$

马尔可夫奖励过程（Markov Reward Process）定义如下：

马尔可夫奖励过程是一个四元组$<S,P_{ss'},R_s,\gamma>$，$S$是有限状态集，$P_{ss'}$​是状态转移概率，

• $R_s=E(R_{t+1}|S_t=s)$​​是奖励函数，
• $\gamma\in[0,1]$是折扣因子。

可以看出，每一个状态的马尔可夫链有无数个，给定一个马尔可夫链求回报$G_t$​容易，但是要求值函数$v(s)$​几乎不可能。

这里借助于贝尔曼等式（Bellman） 能够很好的解决这个问题。

贝尔曼等式定义如下：

$v(s)=R_s+\gamma \sum_{s'\in S}P_{ss'}v(s')$

推导过程为：

$\begin{aligned} v(s)&=E(G_t|S_t=s)\\ &=E(R_{t+1}+\gamma R_{t+2}+...|S_t=s)\\ &=E(R_{t+1}+\gamma G_{t+1}|S_t=s)\\ &=E(R_{t+1}+\gamma v(S_{t+1})|S_t=s)\quad (S_{t+1}\text{是多条马尔可夫链集合})\\ &=R_s+\gamma \sum_{s'\in S}P_{ss'}v(s') \end{aligned}$

贝尔曼等式的矩阵形式：

$V=R+\gamma PV$

可得

$V =(I-\gamma P)^{-1}R$

马尔可夫决策过程（MDP）

马尔可夫决策过程（Markov Decision Process）是伴有决策的的马尔可夫奖励过程，给出定义如下：

马尔可夫决策过程是一个五元组$<S,A,P_{ss'}^a,R_s^a,\gamma>$​​，$S$​​是有限状态集，$A$是有限动作集，

• $P_{ss'}^a=P(S_{t+1}=s'|S_{t}=s,A_t = a)$​是执行动作 的状态转移概率，
• $R_s^a=E(R_{t+1}|S_t=s,A_t=a)$是执行动作 的奖励函数，
• $\gamma\in[0,1]$是折扣因子。

为了表示不同状态采取不同动作的概率，我们引入策略（Policy）的概念，定义如下：

$\pi(a|s)=P(A_t=a|S_t=s)$

采取策略 的状态转移概率和奖励函数定义为：

$\begin{aligned} P_{ss'}^\pi&=\sum_{a\in A}\pi(a|s)P_{ss'}^a\\ R_{s}^\pi&=\sum_{a\in A}\pi(a|s)R_{s}^a \end{aligned}$

现在就出现了两种值函数：状态值函数$v_\pi$和动作值函数$q_\pi$，定义如下：

$\begin{aligned} v_\pi(s)&=E_\pi(G_t|S_t=s)\\ q_\pi(s,a)&=E_\pi(G_t|S_t=s,A_t=a) \end{aligned}$

可以看出

$v_\pi(s)=\sum_{a\in A}\pi(a|s)q_\pi(s,a)$

同样的，贝尔曼等式表示为

$v_\pi(s)=R_s^\pi+\gamma \sum_{s'\in S}P_{ss'}^\pi v_\pi(s')=\sum_{a\in A}\pi(a|s)\left(R_s^a+\gamma\sum_{s'\in S}P_{ss'}^av_\pi(s')\right)$