参考来源：

关于马尔可夫

什么是马氏过程

直观地来讲，对于一个马氏过程，指的是在 $X_{t+1}$ 之前的所有信息全部已知的情况下， $X_{t+1}$ 的分布只和 $X_t$ 的取值有关，与 $X_t$ 前面发生过的事情无关，即未来只由现在决定，而不由过去决定。这是因为 $X_{t-1}$ 对于 $X_{t+1}$ 的影响，全部体现在了 $X_{t}$ 中。对于一个初始值是 $X_1$ 的随机变量，服从某个初始分布，而 $X_{1}$ 的取值又决定了 $X_{2}$ 的分布， $X_{2}$ 的取值又决定了 $X_{3}$ 的分布 $\cdots$ 以此类推，就形成了一个马尔科夫链。

马氏链具有一个核心性质：如果我们已知某些条件，要去求解某些表达式关于这些条件的期望，则我们只需要距离所求事件最接近的条件就足够了，举个例子即 $$E(X_{16}^2|X_2 = x_2, X_5 = x_5, X_9 = x_9) = E(X_{16}^2|X_9 = x_9)$$

马尔可夫决策过程 MDP

马氏过程只有状态之间的内在关系 $P(S_{t+1} = s_{t+1} | S_t = s_t)$ ，而在 MDP 中，转移方程变为了 $P(S_{t+1}|S_t = s_t, A_t = a_t)$ ，同时增加了与我们最终目的有关的变量 $R_t$ , 由 $P(R_{t+1}|S_t = s_t, A_t = a_t)$ 决定

马尔可夫决策过程

MDP 的核心目的是求出一种选择 $A_t$ 的方式，使得 $E[\sum R_t]$ 或 $E[\sum R_t \gamma^t]$ 等奖励最大。除了这两个重要的变量之外，还有一个结束信号 $Done_t$ ，代表着 MDP 何时结束。我们常常假定马氏链的长度是无穷的，而 MDP 的长度是有限的。在某个状态 $s_t$ 采取动作 $a_t$ 后，会有概率得到一个 $Done$ 信号，代表着 MDP 的结束。至此我们介绍完了 MDP 的所有元素，由于 $Done$ 的信号是包含在 $R$ 中的，我们习惯将其记为四元组 $(S,A,P,R)$

马尔可夫过程与 MDP 的对比

在马氏过程中，如果给定条件概率 $P(S_{t+1}|S_t = s_t)$ ，以及初始状态分布 $P(S_0)$ ，就完全确定了马氏链的分布。这就是说，对于所有的 $s$ 与 $t$ ，我们可以求出所有 $P(S_t = s)$ ；对于所有可能发生的马氏链轨道 $(s_0, s_1, s_2, \dots, s_n)$ ，我们可以求出它发生的概率是多少，即求出 $P(\tau = (s_0, s_1, s_2, \dots, s_n))$ 。总的来说，马氏过程是一个“客观的”过程，当其转移规律确定之后，会发生的一切都被确定了。

在 MDP 中，情况却完全不同。即使我们的 $P$ 、 $R$ 、 $Done$ ，以及初始的分布 $P(S_0)$ 都确定了，后续 $S_t$ 的分布也不能确定。这是因为，有一个“主观的”、“可以自由选择”的 $A_t$ 会影响 $S_t$ 的分布。这个 $A_t$ 应该怎么选择，就是强化学习的核心问题。一般而言，我们会希望找出一个从 $S$ 到 $A$ 的映射，即 $P(A_t|S_t = s_t)$ 。当 $P(A_t|S_t = s_t)$ 确定之后，则 $S_t, A_t, R_t$ 的分布便真正地确定下来。这时候，我们就可以求出 $P(S_t = s)$ ， $P(A_t = a)$ 以及 $P(R_t = r)$ 这些具体分布。对于可能发生的所有轨道 $(s_0, a_0, r_0, s_1, a_1, r_1, s_2, \dots, r_n)$ ，我们也可以求出其发生的概率 $P(\tau = (s_0, a_0, r_0, s_1, a_1, r_1, s_2, \dots, r_n))$ 。这也就是说，当 $P(A_t|S_t = s)$ 确定，一切就确定了。

MDP 的分类

首先，我们最终要求解的强化学习问题应该是一个环境未知且持续多步的 MDP，这导致我们的算法要同时考虑两个方面的困难——如何与环境交互产生数据、如何求解最佳策略。如果 MDP 并非持续多步或者环境未知，这会让我们的问题性质发生改变，大大地简化问题的难度。所以，MDP 中最重要的性质是我们是否知道它的环境，以及是否发生退化。这涉及到问题的基本定义，是我们首要考虑的内容；

其次，我们求解 MDP 意味着找出一个最优策略，使得智能体能够在环境中获得最大的奖励。这个策略是如何为我们选择动作 $A_t$ 的？是仅仅需要根据当前状态 $s_t$ 选择，还是也要考虑当前的时间 $t$ ？它是一个什么形式的函数？对于这一点，我们要考虑 MDP 中状态转移方程是否具有随机性，以及是否具有时齐性。所以，我们在考虑 MDP 的基本性质之后，考虑 MDP 这两方面的性质便可以帮助我们确定我们需要解是什么形式；