马尔可夫过程

马尔可夫性值

在随机过程中，马尔可夫性质（Markov property）是指一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。即
$$P(s_{t+1}|s_t)=P(s_{t+1}|s_1,\cdots ,s_t)$$

马尔科夫过程

马尔可夫过程是一组具有马尔可夫性质的随机变量序列$s_1,\cdots ,s_t$，其中下一个时刻的状态$s_{t+1}$只取决于当前状态$s_t$。我们设状态的历史为 h t = { s 1 , s 2 , . . . . . . , s t } h_t=\{s_1,s_2,......,s_t\} ht​={s1​,s2​,......,st​}（$h_t$包含了之前的所有状态），则马尔可夫过程满足条件：
$$p(s_{t+1}|s_t)=p(s_{t+1}|h_t)\text{\hspace{1em}(1)}$$
从当前$s_t$转移到$s_{t+1}$，它是直接就等于它之前所有的状态转移到$s_{t+1}$。

离散时间的马尔可夫过程也称为马尔可夫链（Markov chain）。马尔可夫链是最简单的马尔可夫过程，其状态是有限的。例如，下图里面有4个状态，这4个状态在$s_1,s_2,s_3,s_4$之间相互转移。比如从$s_1$开始，$s_1$有 0.1 的概率继续存留在$s_1$状态，有 0.2 的概率转移到$s_2$，有 0.7 的概率转移到$s_4$。

我们可以用状态转移矩阵（state transition matrix）$P$ 来描述状态转移 $p(s_{t+1}=s^{\prime }|s_t=s)$
$$P=\left(\begin{array}{cccc}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)\\ ⋮& ⋮& \ddots & ⋮\\ p(s_1|s_N)& p(s_2|s_N)& ...& p(s_N|s_N)\end{array}\right)$$
状态转移矩阵类似于条件概率（conditional probability），它表示当我们知道当前我们在状态$s_1$时，到达下面所有状态的概率。所以它的每一行描述的是从一个节点到达所有其他节点的概率。

马尔可夫奖励过程

马尔可夫奖励过程（Markov reward process, MRP）是马尔可夫链加上奖励函数。在马尔可夫奖励过程中，状态转移矩阵和状态都与马尔可夫链一样，只是多了奖励函数（reward function）。奖励函数$R$是一个 期望，表示当我们到达某一个状态的时候，可以获得多大的奖励。
$$R(s)=E[R_{t+1}|s_t=s]$$

回报与价值函数

回报（return）可以定义为奖励的逐步叠加，假设时刻$t$后的奖励序列为$r_{t+1},r_{t+2},r_{t+3},\cdots ,$则回报为
$$G_t=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+{\gamma }^3{r}_{t+4}+\cdots +{\gamma }^{T-t-1}{r}_T$$
其中，$T$是最终时刻，$\gamma$是折扣因子，越往后得到的奖励折扣越多。这说明我们更希望得到现有的奖励，对未来的奖励要打折扣。当我们有了回报之后，就可以定义状态的价值了，就是状态价值函数（state-value function）。对于马尔可夫奖励过程，状态价值函数被定义成回报的期望，即
$$\begin{array}{rl}{V}^t(s)& =E[G_t|s_t=s]\\ & =E[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+{\gamma }^3{r}_{t+4}+...+{\gamma }^{T-t-1}{r}_T|s_t=s]\end{array}$$
其中，$G_t$是之前定义的折扣回报（discounted return）。我们对$G_t$取了一个期望，期望就是从这个状态开始，我们可能获得多大的价值。

我们使用折扣因子的原因如下。第一，有些马尔可夫过程是带环的，它并不会终结，我们想避免无穷的奖励。第二，我们并不能建立完美的模拟环境的模型，我们对未来的评估不一定是准确的，我们不一定完全信任模型，因为这种不确定性，所以我们对未来的评估增加一个折扣。我们想把这个不确定性表示出来，希望尽可能快地得到奖励，而不是在未来某一个点得到奖励。第三，如果奖励是有实际价值的，我们可能更希望立刻就得到奖励，而不是后面再得到奖励（现在的钱比以后的钱更有价值）。最后，我们也更想得到即时奖励。有些时候可以把折扣因子设为 0，我们就只关注当前的奖励。我们也可以把折扣因子设为 1，对未来的奖励并没有打折扣，未来获得的奖励与当前获得的奖励是一样的。折扣因子可以作为强化学习智能体的一个超参数（hyperparameter）来进行调整，通过调整折扣因子，我们可以得到不同动作的智能体。

下面是一个计算回报的例子。如图所示，智能体进入第一个状态$s_1$的时候会得到 5 的奖励，进入第七个状态$s_7$的时候会得到 10 的奖励，进入其他状态都没有奖励。我们可以用向量来表示奖励函数，即
$$R=[5,0,0,0,0,0,10]$$

我们对 4 步的** 回合 **（episode）($\gamma =0.5$)来采样回报$G$。

$(1)s_4,s_5,s_6,s_7的回报:0+0.5\times 0+0.25\times 0+0.125\times 10=1.25$

$(2)s_4,s_3,s_2,s_1的回报:0+0.5\times 0+0.25\times 0+0.125\times 5=0.625$

$(3)s_4,s_5,s_6,s_6的回报:0+0.5\times 0+0.25\times 0+0.125\times 0=0$

我们现在可以计算每一个回合得到的奖励，比如我们对轨迹$s_4,s_5,s_6,s_7$的奖励进行计算，这里折扣因子是 0.5。在$s_4$的时候，奖励为0。下一个状态$s_5$的时候，因为我们已经到了下一步，所以要把$s_5$进行折扣，$s_5$的奖励也是0。然后是$s_6$，奖励也是0，折扣因子应该是0.25。到达$s_7$后，我们获得了一个奖励，但是因为状态$s_7$的奖励是未来才获得的奖励，所以我们要对之进行3次折扣。最终这个轨迹的回报就是 1.25。类似地，我们可以得到其他轨迹的回报。

当我们有了一些轨迹的实际回报时，怎么计算它的价值函数呢？比如我们想知道$s_4$的价值，即当我们进入$s_4$后，它的价值到底如何？一个可行的做法就是我们可以生成很多轨迹，然后把轨迹都叠加起来。比如我们可以从$s_4$开始，采样生成很多轨迹，把这些轨迹的回报都计算出来，然后将其取平均值作为我们进入$s_4$的价值。这其实是一种计算价值函数的办法，也就是通过蒙特卡洛（Monte Carlo，MC）采样的方法计算$s_4$的价值。

贝尔曼方程

此外，我们可以使用贝尔曼方程求解价值函数。贝尔曼方程就是当前状态与未来状态的迭代关系，表示当前状态的价值函数可以通过下个状态的价值函数来计算。贝尔曼方程（Bellman equation）如下：
$$V(s)=\underset{\text{及时奖励}}{\underbrace{R(s)}}+\underset{\text{未来奖励的折扣总和}}{\underbrace{\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s)V(s^{{}^{\prime }})}}$$
其中，

• $s^{{}^{\prime }}$可以看成未来的所有状态
• $p(s^{{}^{\prime }}|s)$是指从当前状态转移到未来状态的概率
• $V(s^{{}^{\prime }})$代表的是未来某一个状态的价值。我们从当前状态开始，有一定的概率去到未来的所有状态，所以我们要把$p(s^{{}^{\prime }}|s)$写上去。我们得到了未来状态后，乘一个$\gamma$，这样就可以把未来的奖励打折扣。
• $\gamma {\sum }_{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s)V(s^{{}^{\prime }})$可以看成未来奖励的折扣总和（discounted sum of future reward）。

贝尔曼方程的推导过程如下：

$$\begin{array}{rl}{V}^t(s)& =E[G_t|s_t=s]\\ & =E[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+...|s_t=s]\\ & =E[r_{t+1}|s_t=s]+\gamma E[r_{t+2}+\gamma r_{t+3}+{\gamma }^2{r}_{t+4}+...|s_t=s]\\ & =R(s)+\gamma E[G_{t+1}|s_t=s]\\ & =R(s)+\gamma E[V(s_{t+1}|s_t=s)]\\ & =R(s)+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s)V(s^{{}^{\prime }})\end{array}$$

例子：假设有一个马尔可夫链如下图所示，计算红色框的 价值 ？

我们可以把贝尔曼方程写成矩阵的形式：
$$\left(\begin{array}{c}V(s_1)\\ V(s_2)\\ ⋮\\ V(s_N)\end{array}\right)=\left(\begin{array}{c}R(s_1)\\ R(s_2)\\ ⋮\\ R(s_N)\end{array}\right)+\gamma \left(\begin{array}{cccc}p(s_1|s_1)& p(s_2|s_1)& \dots & p(s_N|s_1)\\ p(s_1|s_2)& p(s_2|s_2)& \dots & p(s_N|s_2)\\ ⋮& ⋮& \ddots & ⋮\\ p(s_1|s_N)& p(s_2|s_N)& \dots & p(s_N|s_N)\end{array}\right)\left(\begin{array}{c}V(s_1)\\ V(s_2)\\ ⋮\\ V(s_N)\end{array}\right)$$

我们当前的状态是向量$[V(s_1),V(s_2),\cdots ,V(s_N){]}^T$。每一行来看，向量$V$乘状态转移矩阵里面的某一行，再加上它当前可以得到的奖励，就会得到它当前的价值。

当我们把贝尔曼方程写成矩阵形式后，可以直接求解：
$$\begin{array}{rl}& V=R+\gamma PV\\ & IV=R+\gamma PV\\ & (I-\gamma P)V=R\\ & V=(I-\gamma P{)}^{-1}R\end{array}$$
我们可以通过矩阵求逆把$V$的价值直接求出来。但是一个问题是这个矩阵求逆的过程的复杂度是$O(N^3)$。所以当状态非常多的时候，比如从10个状态到1000个状态，或者到100万个状态，当我们有100万个状态的时候，状态转移矩阵就会是一个100万乘100万的矩阵，对这样一个大矩阵求逆是非常困难的。所以这种方法只适用于很小量的马尔可夫奖励过程。

马尔可夫决策过程

相对于马尔可夫奖励过程，马尔可夫决策过程（Markov decision process, MDP）多了决策（决策是指动作），其他的定义与马尔可夫奖励过程的是类似的。此外，状态转移也多了一个条件，变成了$p(s_{t+1}=s^{{}^{\prime }}|s_t=s,a_t=a)$，表示未来的状态不仅依赖于当前的状态，也依赖于在当前状态智能体采取的动作。马尔可夫决策过程满足条件：
$$p(s_{t+1}|s_t,a_t)=p(s_{t+1}|h_t,a_t)$$
对于奖励函数，它也多了一个当前的动作，变成了
$$R(s_t=s,a_t=a)=E[r_t|s_t=s,a_t=a]$$
当前的状态以及采取的动作会决定智能体在当前可能得到的奖励多少。

策略

策略$\pi$是一个函数，表示输入状态为$s$的情况下采取动作$a$的概率。
$$\pi (a|s)=p(a_t=a|s_t=s)$$
概率代表在所有可能的动作里面怎样采取行动，比如可能有 0.7 的概率往左走，有 0.3 的概率往右走，这是一个概率的表示。另外策略也可能是确定的，它有可能直接输出一个值，或者直接告诉我们当前应该采取什么样的动作，而不是一个动作的概率。

已知马尔可夫决策过程和策略 $\pi$，我们可以把马尔可夫决策过程转换成马尔可夫奖励过程。在马尔可夫决策过程里面，状态转移函数$P(s^{{}^{\prime }}|s,a)$基于它当前的状态以及它当前的动作。因为我们现在已知策略函数，也就是已知在每一个状态下，可能采取的动作的概率，所以我们就可以直接把动作进行加和，去掉 $a$，这样我们就可以得到对于马尔可夫奖励过程的转移，这里就没有动作，即
$$P_{\pi }(s^{{}^{\prime }}|s)=\sum _{a\in A}\pi (a|s)p(s^{{}^{\prime }}|s,a)$$
对于奖励函数，我们也可以把动作去掉，这样就会得到类似于马尔可夫奖励过程的奖励函数，即
$$R_{\pi }(s)=\sum _{a\in A}\pi (a|s)R(s,a)$$

马尔科夫决策过程中的价值函数

马尔可夫决策过程中的状态价值函数定义
$$V_{\pi }(s)=E_{\pi }[G_t|s_t=s]\text{\hspace{1em}(2)}$$
状态价值函数$V_{\pi }(s)$是从状态$s$出发，遵循策略$\pi$得到的期望回报。

马尔可夫决策过程中的动作价值函数定义
$$Q_{\pi }(s,a)=E_{\pi }[G_t|s_t=s,a_t=a]\text{\hspace{1em}(3)}$$
动作价值函数$Q_{\pi }(s,a)$是从状态$s$开始，遵循策略$\pi$，对当前状态$s$执行动作$a$得到的期望回报。

状态价值函数和动作价值函数的 关系

状态价值函数的期望是基于策略函数的，所以对策略函数进行一个加和，然后得到它的价值。对动作价值函数中的动作进行加和，就可以得到状态价值函数：
$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)Q_{\pi }(s,a)\text{\hspace{1em}(4)}$$
对动作价值函数而言：
$$\begin{array}{rl}Q(s,a)& =E[G_t|s_t=s,a_t=a]\\ & =E[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\cdots |s_t=s,a_t=a]\\ & =E[r_{t+1}|s_t=s,a_t=a]+\gamma E[r_{t+2}+\gamma r_{t+3}+{\gamma }^2{r}_{t+4}+\cdots |s_t=s,a_t=a]\\ & =R(s,a)+\gamma E[G_{t+1}|s_t=s,a_t=a]\\ & =R(s,a)+\gamma E[V(s_{t+1}|s_t=s,a_t=a)]\\ & =R(s,a)+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s,a)V(s^{{}^{\prime }})\end{array}$$

贝尔曼期望方程

我们可以把状态价值函数和动作价值函数拆解成两个部分：即时奖励和后续状态的折扣价值（discounted value of successor state）。通过对状态价值函数进行分解，我们就可以得到一个类似于之前马尔可夫奖励过程的贝尔曼方程————贝尔曼期望方程（Bellman expectation equation）：
$$V_{\pi }(s)=E_{\pi }[r_{t+1}+\gamma V_{\pi }(s_{t+1})|s_t=s]\text{\hspace{1em}(5)}$$
对于动作价值函数，我们也可以做类似的分解，得到动作价值函数的贝尔曼期望方程：
$$Q_{\pi }(s,a)=E_{\pi }[r_{t+1}+\gamma Q_{\pi }(s_{t+1},a_{t+1})|s_t=s,a_t=a]\text{\hspace{1em}(6)}$$
贝尔曼期望方程定义了当前状态与未来状态之间的关联。

我们进一步进行简单的分解，先给出式(7)：
$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)Q_{\pi }(s,a)\text{\hspace{1em}(7)}$$
接着，我们再给出式(8)：
$$Q_{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s,a)V_{\pi }(s^{{}^{\prime }})\text{\hspace{1em}(8)}$$
式(7)和式(8)代表状态价值函数与动作价值函数之间的关系。

我们把式(8)代入式(7)可得
$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)\left(R(s,a)+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s,a)V_{\pi }(s^{{}^{\prime }})\right)\text{\hspace{1em}(9)}$$
式(9)代表当前状态的价值与未来状态价值之间的关联。

我们把式(7)代入式(8)可得
$$Q_{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s,a)\sum _{a^{{}^{\prime }}\in A}\pi (a^{{}^{\prime }}|s^{{}^{\prime }})Q_{\pi }(s^{{}^{\prime }},a^{{}^{\prime }})\text{\hspace{1em}(10)}$$
式(10)代表当前时刻的动作价值函数与未来时刻的动作价值函数之间的关联。

式(9)和式(10)是贝尔曼期望方程的另一种形式。

例子，如下图所示，求红色框的 价值？

再比如，左边的-1.3这个状态是 怎么来的 ？

最优价值函数

在马尔可夫决策过程中，最优价值函数分为两种：最优状态值函数和最优动作值函数。

最优状态价值函数是所有策略产生的状态价值函数中，使状态$s$价值最大的函数：
$$V^{\ast }(s)=\underset{\pi }{\max }{V}_{\pi }(s)$$
最优动作价值函数是指所有策略产生的动作价值函数中，使状态-行动价值最大的函数：
$$Q^{\ast }(s,a)=\underset{\pi }{\max }{Q}_{\pi }(s,a)$$

最优价值函数明确了MDP的最优可能表现。一旦最优价值函数知晓，则认为MDP已完成求解。

最优策略

最优价值函数是指我们搜索一种策略$\pi$让每个状态的价值最大，在这种最大化情况中，我们得到的策略就是最优策略，即
$${\pi }^{\ast }(s)=\arg \underset{\pi }{\max }{V}_{\pi }(s)$$

寻找最优策略

最优策略使得每个状态的价值函数都取得最大值。所以如果我们可以得到一个最优价值函数，就可以认为某个马尔可夫决策过程的环境可解。在这种情况下，最优价值函数是一致的，环境中可达到的上限的值是一致的，但这里可能有多个最优策略，多个最优策略可以取得相同的最优价值。

当取得最优动作价值函数后，我们可以通过对动作价值函数进行最大化来得到最优策略：
$${\pi }^{\ast }(a|s)=\{\begin{array}{rl}1,& a=\arg \underset{a\in A}{\max }{Q}^{\ast }(s,a)\\ 0,& 其他\end{array}$$
当动作价值函数收敛后，因为动作价值函数是关于状态与动作的函数，所以如果在某个状态采取某个动作，可以使得动作价值函数最大化，那么这个动作就是最佳的动作。如果我们能优化出一个动作价值函数$Q^{\ast }(s,a)$，就可以直接在动作价值函数中取一个让动作价值函数值最大化的动作的值，就可以提取出最佳策略。

怎样进行策略搜索？最简单的策略搜索方法就是穷举。假设状态和动作都是有限的，那么每个状态我们可以采取$A$种动作的策略，总共就是 $|A{|}^{|S|}$个可能的策略。我们可以把策略穷举一遍，算出每种策略的价值函数，对比一下就可以得到最佳策略。

但是穷举非常没有效率，所以我们要采取其他方法。

贝尔曼最优方程

贝尔曼最优方程（Bellman optimality equation）如下
$$V_{\pi }(s)=\underset{a\in A}{\max }{Q}_{\pi }(s,a)$$
贝尔曼最优方程表明：最佳策略下的一个状态的价值必须等于在这个状态下采取最好动作得到的回报的期望。当马尔可夫决策过程满足贝尔曼最优方程的时候，整个马尔可夫决策过程已经达到最佳的状态。

只有当整个状态已经收敛后，我们得到最佳价值函数后，贝尔曼最优方程才会满足。满足贝尔曼最优方程后，我们可以采用最大化操作，即
$$V^{\ast }(s)=\underset{a}{\max }{Q}^{\ast }(s,a)\text{\hspace{1em}(12)}$$
当我们取让 Q 函数值最大化的动作对应的值就是当前状态的最佳的价值函数的值。另外，我们给出 Q 函数的贝尔曼方程
$$Q^{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s,a)V^{\ast }(s^{{}^{\prime }})\text{\hspace{1em}(13)}$$
我们把式(12)代入式(13)可得
$$\begin{array}{rl}{Q}^{\ast }(s,a)& =R(s,a)+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s,a)V^{\ast }(s^{{}^{\prime }})\\ & =R(s,a)+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s,a)\underset{a}{\max }{Q}^{\ast }(s^{{}^{\prime }},a^{{}^{\prime }})\end{array}$$
我们就可以得到 Q 函数之间的转移。Q学习是基于贝尔曼最优方程来进行的，当取Q函数值最大的状态（${\max }_{a^{{}^{\prime }}}{Q}^{\ast }(s^{{}^{\prime }},a^{{}^{\prime }})$）的时候可得
$$Q^{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s,a)\underset{a^{{}^{\prime }}}{\max }{Q}^{\ast }(s^{{}^{\prime }},a^{{}^{\prime }})$$
我们还可以把式(13)代入式(12)可得
$$\begin{array}{rl}{V}^{\ast }(s)& =\underset{a}{\max }{Q}^{\ast }(s,a)\\ & =\underset{a}{\max }E[G_t|s_t=s,a_t=a]\\ & =\underset{a}{\max }E[r_{t+1}+\gamma G_{t+1}|s_t=s,a_t=a]\\ & =\underset{a}{\max }E[r_{t+1}+\gamma V^{\ast }(s_{t+1})|s_t=s,a_t=a]\\ & =\underset{a}{\max }E[r_{t+1}]+\underset{a}{\max }E[\gamma V^{\ast }(s_{t+1})|s_t=s,a_t=a]\\ & =\underset{a}{\max }R(s,a)+\underset{a}{\max }\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s,a)V^{\ast }(s^{{}^{\prime }})\\ & =\underset{a}{\max }\left(R(s,a)+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s,a)V^{\ast }(s^{{}^{\prime }})\right)\end{array}$$

例子，使用贝尔曼最优方程求下面 ？的价值

贝尔曼最优方程是非线性的，不能使用与策略优化相同的直接矩阵解决方案，可以通过一些其他迭代方法来求解。

• 价值迭代
• 策略迭代
• Q-learning
• Sarsa