在介绍马尔可夫决策过程之前，先介绍它的简化版本：马尔可夫链以及马尔可夫奖励过程，通过跟这两种过程的比较，我们可以更容易理解马尔可夫决策过程。

Markov Process(MP)
Markov Property
如果一个状态转移是符合马尔可夫的，那就是说下一个状态只取决于他当前状态，而跟他当前状态之前的状态都没有关系。

假定状态历史为h_t={s₁,s₂,…,s_t}(h_t包含了之前的所有状态)，如果一个状态转移是符合马尔科夫的，也就是满足如下条件：

从当前s_t转移到s_t+1这个状态，他就直接等于它之前所有的状态转移到s_t+1。如果某一个过程满足马尔可夫性质（Markov Property），就是说未来的转移跟过去是独立的，只取决于现在。马尔可夫性质是所有马尔可夫过程的基础

Markov Process/Markov Chain

首先看一看马尔可夫链（Markov Chain）。例如上图里面有四个状态，四个状态之间可以相互转移，比如说从s₁开始：
s₁有 0.1 的概率继续存活在 s₁状态，
有 0.2 的概率转移到 s₂，
有 0.7 的概率转移到 s₄。
如果 s₄ 是我们当前状态的话，
它有 0.3 的概率转移到 s₂，
有 0.2 的概率转移到 s₃ ，
有 0.5 的概率留在这里。
可以使用状态转移矩阵（State Transition Matrix）P来描述状态转移P（s_t+1=s‘ | s_t=s），如下图所示。

Example of MP

上图是一个马尔可夫链的例子，我们这里有七个状态。比如说从 s₁开始到 s₂ ，它有 0.4 的概率，然后它有 0.6 的概率继续存活在它当前的状态。s₂ 有 0.4 的概率到左边，有 0.4 的概率到 s₃，另外有 0.2 的概率存活在现在的状态，所以给定了这个状态转移的马尔可夫链后，我们可以对这个链进行采样，这样就会得到一串的轨迹。

下面我们有三个轨迹，都是从同一个起始点开始。假设还是从 s₃这个状态开始，

第一条链先到了 s₄， 又到了 s₅s ，又往右到了 s₆，然后继续存活在 s₆状态。
第二条链从 s₃开始，先往左走到了 s₂。然后它又往右走，又回到了s₃ ，然后它又往左走，然后再往左走到了 s₁。
通过对这个状态的采样，我们生成了很多这样的轨迹。

Markov Reward Process（MRP）

马尔可夫奖励过程（Markov Reward Process，MRP）是马尔科夫链再加上了一个奖励函数，在MRP中，转移矩阵跟它的这个状态都是跟马尔科夫链一样的，多了一个奖励函数（reward function）。奖励函数是一个期望，即就是说当你到达某一状态的时候，可以获得多大的奖励，然后另外定义了一个 discount factor $\gamma$

Example of MRP

这里是我们刚才看的马尔可夫链，如果把奖励也放上去的话，就是说到达每一个状态，我们都会获得一个奖励。这里我们可以设置对应的奖励，比如说到达 s₁状态的时候，可以获得 5 的奖励，到达 s₇的时候，可以得到 10 的奖励，其它状态没有任何奖励。因为这里状态是有限的，所以我们可以用向量 R=[5,0,0,0,0,0,10]来表示这个奖励函数，这个向量表示了每个点的奖励大小。

我们通过一个形象的例子来理解 MRP。我们把一个纸船放到河流之中，那么它就会随着这个河流而流动，它自身是没有动力的。所以你可以把 MRP 看成是一个随波逐流的例子，当我们从某一个点开始的时候，这个纸船就会随着事先定义好的状态转移进行流动，它到达每个状态过后，我们就有可能获得一些奖励。

Return and Value function
先进一步定义一些概念
Horizon是指一个回合的长度（每个回合最大的时间步数），由有限个步数决定。
Return（汇报)指的是把奖励进行折扣后所获得的收益。Return可以定义为奖励的逐步叠加，如下所示：

这里有一个叠加系数，越往后得到的奖励，折扣得越多，这说明我们其实更希望得到现有的奖励，未来的奖励就要把它打折扣。

当有了return过后，就可以定义一个状态的价值了，即state value function。对于MRP，state value function被定义成是return的期望，如下所示：
其中G_t是之前定义的discounted return，我们这里取了一个期望，期望就是说从这个状态开始，你有可能获得多大的价值。所以这个期望也可以看成是对未来可能获得奖励的当前价值的一个表现，就是当你进入某一个状态过后，你现在就有多大的价值。

Why Discount Factor
这里解释一下为什么需要 discount factor。

1>有些马尔可夫过程是带环的，它并没有终结，我们想避免这个无穷的奖励。
2>我们并没有建立一个完美的模拟环境的模型，也就是说，我们对未来的评估不一定是准确的，我们不一定完全信任我们的模型，因为这种不确定性，所以我们对未来的预估增加一个折扣。我们想把这个不确定性表示出来，希望尽可能快地得到奖励，而不是在未来某一个点得到奖励。
3>如果这个奖励是有实际价值的，我们可能是更希望立刻就得到奖励，而不是后面再得到奖励（现在的钱比以后的钱更有价值）。
4>在人的行为里面来说的话，大家也是想得到即时奖励。
5>有些时候可以把这个系数设为 0，$\gamma =0$：我们就只关注了它当前的奖励。当$\gamma =1$即就是对未来并没有折扣，未来获得的奖励跟当前获得的奖励是一样的。

Discount factor 可以作为强化学习 agent 的一个超参数来进行调整，然后就会得到不同行为的 agent.

Example of MRP

这里就引出了一个问题，当我们有了一些轨迹的实际 return，怎么计算它的价值函数。比如说我们想知道 s₄状态的价值，就是当你进入 s₄后，它的价值到底如何。一个可行的做法就是说我们可以产生很多轨迹，然后把这里的轨迹都叠加起来。比如我们可以从 s₄开始，采样生成很多轨迹，都把它的 return 计算出来，然后可以直接把它取一个平均作为你进入 s₄它的价值。这其实是一种计算价值函数的办法，通过这个蒙特卡罗采样的办法计算 s₄的状态。接下来会进一步介绍蒙特卡罗算法。

Bellman Equation

但是这里我们采取了另一种计算方法，从这个价值函数里面推导出Bellman Equation(贝尔曼等式)，如下所示

其中：
s^’可以当作未来的所有状态
转移P{s^’ | s}是指从当前状态转移到未来状态的概率。
V（s^’）代表的是未来某一个状态的价值。从当前位置开始，有一定的概率去到未来的所有状态，所以要把这个概率也写上去，这个转移矩阵也写上去，然后就得到了未来状态，然后再乘以一个$\gamma$,这样就可以把未来的奖励打折扣。

Law of Total Expectation
在推导Bellman-equation之前，先使用Low of Total Expectation（全期望公式）证明下面式子：

证明：
为了记号简介并且易读，就丢掉下标，令s=s_t，g^’=G_t+1,s^’=s_t+1.所以我们可以将回报的期望重写为：

令S_t=s，对上式求期望得：

Bellman Equation Derivation
Bellman equation的推导过程如下：

Bellman Equation 就是当前状态与未来状态的迭代关系，表示当前状态的值函数可以通过下个状态的值函数来计算。Bellman Equation 因其提出者、动态规划创始人 Richard Bellman 而得名 ，也叫作“动态规划方程”。

Bellman Equation 定义了状态之间的迭代关系，如下式所示：

假设有一个马尔可夫转移矩阵是右边这个样子，Bellman Equation 描述的就是当前状态到未来状态的一个转移。假设我们当前是在 s₁， 那么它只可能去到三个未来的状态：有 0.1 的概率留在它当前这个位置，有 0.2 的概率去到 s₂ 状态，有 0.7 的概率去到 s₄的状态，所以我们要把这个转移乘以它未来的状态的价值，再加上它的 immediate reward 就会得到它当前状态的价值。所以 Bellman Equation 定义的就是当前状态跟未来状态的一个迭代的关系。

我们可以把Bellman Equation写成一种矩阵的形式，如下所示：

首先有这个转移矩阵。我们当前这个状态是一个向量 [V(s₁),V(s₂),……,V(s_N)]^T。我们可以写成迭代的形式。我们每一行来看的话，VV 这个向量乘以了转移矩阵里面的某一行，再加上它当前可以得到的 reward，就会得到它当前的价值。

当我们把 Bellman Equation 写成矩阵形式后，可以直接求解：

这样就可以得到一个解析解（analytic solution）

我们可以通过矩阵求逆把这个 V 的这个价值直接求出来。但是一个问题是这个矩阵求逆的过程的复杂度是 O(N³)。所以当状态非常多的时候，比如说从十个状态到一千个状态，到一百万个状态。那么当我们有一百万个状态的时候，这个转移矩阵就会是个一百万乘以一百万的矩阵，这样一个大矩阵的话求逆是非常困难的，所以这种通过解析解去求解的方法只适用于很小量的 MRP。

Iterative Algorithm for Computing Value of a MRP
接下来我们来求解这个价值函数。我们可以通过迭代的方法来解这种状态非常多的 MRP(large MRPs)，比如说:

动态规划的方法，
蒙特卡罗的办法(通过采样的办法去计算它)，
时序差分学习(Temporal-Difference Learning)的办法。 Temporal-Difference Learning 叫 TD Leanring，它是动态规划和蒙特卡罗的一个结合。

首先我们用蒙特卡罗(Monte Carlo)的办法来计算它的价值函数。蒙特卡罗就是说当得到一个 MRP 过后，我们可以从某一个状态开始，把这个小船放进去，让它随波逐流，这样就会产生一个轨迹。产生了一个轨迹过后，就会得到一个奖励，那么就直接把它的折扣的奖励 gg 算出来。算出来过后就可以把它积累起来，得到 return G_t​ 。 当积累到一定的轨迹数量过后，直接用 G_t除以轨迹数量，就会得到它的价值。

比如说我们要算 s₄状态的价值。

我们就可以从 s₄状态开始，随机产生很多轨迹，就是说产生很多小船，把小船扔到这个转移矩阵里面去，然后它就会随波逐流，产生轨迹。
每个轨迹都会得到一个 return，我们得到大量的 return，比如说一百个、一千个 return ，然后直接取一个平均，那么就可以等价于现在 s₄这个价值，因为 s₄的价值 V(s₄)定义了你未来可能得到多少的奖励。这就是蒙特卡罗采样的方法。

也可以用这个动态规划的办法，一直去迭代他的Bellman equation，让他最后收敛，就可以得到他的一个状态。所以在这里算法二就是一个迭代的算法，通过 bootstrapping(拔靴自助) 的办法，然后去不停地迭代这个 Bellman Equation。当这个最后更新的状态跟你上一个状态变化并不大的时候，更新就可以停止，我们就可以输出最新的 V’(s) 作为它当前的状态。所以这里就是把 Bellman Equation 变成一个 Bellman Update，这样就可以得到它的一个价值。

动态规划的方法基于后继状态值的估计来更新状态值的估计（算法二中的第 3 行用 V’更新 V ）。也就是说，它们根据其他估算值来更新估算值。我们称这种基本思想为 bootstrapping。

Markov Decision Process(MDP)

相对于MRP，马尔可夫决策过程（Markov Decision Process）多了一个decision，其他定义跟MRP都是类似的。
这里多了一个决策，多了一个动作。
状态转移也多了一个条件，变成了P(s_t+1=s’|s_t=s，a_t=a）。你采取某一种动作，然后你未来的状态会不同。未来的状态不仅是依赖于你当前的状态，也依赖于在当前状态 agent 采取的这个动作。
对于这个价值函数，它也是多了一个条件，多了一个你当前的这个动作，变成了 R（s_t=s，a_t=a）=E[r_t | s_t=s,a_t=a]。你当前的状态以及你采取的动作会决定你在当前可能得到的奖励多少。

Policy in MDP
Policy 定义了在某一个状态应该采取什么样的动作。

知道当前状态过后，我们可以把当前状态带入 policy function，然后就会得到一个概率，即

概率就代表了在所有可能的动作里面怎样采取行动，比如可能有 0.7 的概率往左走，有 0.3 的概率往右走，这是一个概率的表示。

另外这个策略也可能是确定的，它有可能是直接输出一个值。或者就直接告诉你当前应该采取什么样的动作，而不是一个动作的概率。

假设这个概率函数应该是稳定的(stationary)，不同时间点，你采取的动作其实都是对这个 policy function 进行采样。

这里说明了 MDP 跟 MRP 的之间的一个转换。

** Comparison of MP/MRP and MDP**

这里可以看一下MDP里面的状态转移跟MRP以及MP的一个差异。

马尔可夫过程的转移是直接就决定的。如当前状态是s，那么就直接通过这个转移概率决定了下一个状态是什么
但对于MDP，它中间多了一层这个动作a，就是说在当前这个状态的时候，首先要决定的是采取某一种动作，那么就会到某一个黑色的节点。到了这个黑色的节点，由于具有不确定性，当你当前状态决定过后以及你当前采取的动作过后，你到未来的状态其实也是一个概率分布。**所以在这个当前状态跟未来状态转移过程中这里多了一层决策性，这是MDP跟之前的马尔可夫决策过程很不同的一个地方。**在马尔可夫决策过程中，动作由agent决定，所以多了一个component，agent会采取动作来决定未来的状态转移。

Value function for MDP
顺着 MDP 的定义，我们可以把 状态-价值函数(state-value function)，就是在 MDP 里面的价值函数也进行一个定义，它的定义是跟 MRP 是类似的，如下所示：

但是这里 expectation over policy，就是这个期望是基于你采取的这个 policy ，就当你的 policy 决定过后，我们通过对这个 policy 进行采样来得到一个期望，那么就可以计算出它的这个价值函数。
这里我们另外引入了一个 Q 函数(Q-function)。Q 函数也被称为 action-value function。**Q 函数定义的是在某一个状态采取某一个动作，它有可能得到的这个 return 的一个期望，**如式所示：

这里期望其实也是 over policy function。所以你需要对这个 policy function 进行一个加和，然后得到它的这个价值。 对 Q 函数中的动作函数进行加和，就可以得到价值函数，如式 所示

此章还有很多数学公式在此不多做解释，详情见
链接: https://datawhalechina.github.io/easy-rl/#/chapter2/chapter2?id=comparison-of-mpmrp-and-mdp.