2.1.马尔可夫决策过程（MDP）的定义

目前出版合同写的是4月18日出版，出版社说上架推广等都在九月前，即秋季学期的强化学习课程可以使用本教材哈。大家敬请期待。最终稿件相比网上写的还是修改了许多，更加严谨。此外，图书封面也确定了。因为书中总是用象棋等举例，别的游戏的也不太合适，所以封面做成象棋元素的，以后昵称叫做象棋书了哈。希望象棋书能做成强化学习领域的标杆，和西瓜书花书一样，还希望各位多多支持，多多宣传！

感兴趣的读者可以关注我获取更多动态哈。

书已经出版上架了，欢迎大家在各大平台购买！

强化学习所研究的是作为主体的智能体与作为客体的环境交互的序贯决策过程。在数学上，我们会将其规范化为一个马尔可夫决策过程（Markov Decision Process，简称为MDP）。由于MDP是强化学习所面对的问题，所以在本书的第一章，我们将首先介绍什么是MDP。我们将循序渐进，先介绍马尔可夫性过程，然后介绍MDP，再介绍MDP的不同分类。

马尔可夫过程

在概率论中，随机过程（Random Process）是一门非常重要的学科。学过这门课的同学可能知道，随机过程的严谨定义涉及到概率空间、事件域、流等等数学概念。在这里，我们可以简单地认为，离散时间的随机过程就是按照时间顺序排列好的一系列随机变量 ，而连续时间的随机过程则可以视为一个含有时间的随机变量 。我们可以想象，渺小如一个人的心率变化、一台机器的功率周期，宏大到一个国家宏观经济的迭起与兴衰、海平面高度的潮起潮落，背后都有一个连续时间的随机过程。不过，我们为了方便研究，也往往将其简化为一个离散时间的随机过程。随机过程与我们的生产、生活、办公等各方面都是息息相关的。

在数学中，我们研究的是具有某些特殊概率性质的随机过程。我们往往会为假定其背后具有某个概率模型，然后就可以研究其期望、方差等概率性质。例如，我们定义“正态白噪声”为独立同分布的正态随机变量 。大自然中毫无信息的噪声、或是在时间序列测量中产生的误差都可以被视为是“正态白噪声”。当然，“正态白噪声”相当于将一些独立同分布的随机变量串在一起，并没有体现出随机过程的特性，没有太多值得我们研究的地方。一般而言，我们会假定时间序列中之间的因果关系、相关性等概率特性与其在时间上的顺序具有一定的关系。例如，假设时间序列中，当前的取值由之前各个时刻的取值所决定，即时间序列由概率模型 （在概率论中，我们用大写字母表示随机变量，用小写字母表示具体取值）生成，等等。这样的时间序列才有值得我们研究的地方。

马尔可夫过程（简称为马氏过程）是最经典、也是应用最为广泛的一类随机过程。关于马尔可夫性的严格定义是需要一定现代概率论的基础的，涉及到有关于事件域、流、条件数学期望、自然事件域等数学概念。一般而言，面向工科及应用数学专业的《应用随机过程》中也不会涉及马氏过程的严谨定义，只有在数学专业的《随机过程》中才能找到其严谨定义。在这里，我们不详细赘述马氏过程的严谨定义，而只是介绍其直观的含义：对于一个马氏过程， 的分布只和 的取值有关，和 前面发生过的事情无关。这也就是说， 。我们可以想象，初始值是$X_1$是一个随机变量，服从某个初始分布。而 的取值决定了 的分布， 的取值又决定了 的分布，以此类推， 的取值决定了 的分布……马氏过程就在这种一环扣一环的因果关系中形成了。

由于我们在定义时没有使用严谨的数学语言，所以难免会产生歧义。我们说 只是和 的取值有关，和 取值无关，这句话是具有歧义的——它并不是真的意味着 的分布和 的取值没有关系——明明 的取值决定了 ，而 的取值又决定了 ，怎么能说 和 没有关系呢？

要强调的是，刚才我们所说的“ 只和 有关系”这句话，指的是在 之前的所有信息（ ）全部已知的情况下， 只和 有关。换句话说，如果我们的手头同时具有 的信息，要计算 的分布，事实上只需用到 就够了。这是因为 对于 的全部影响，都体现在 之中；但是，如果我们手头没有 的信息，只有 的信息，那么这个 的信息对于我们求解 无疑也是很重要的。它能给我们带来的信息不如 这么多，但也绝不是“没有关系”的。在已知 的条件下，我们算出 的分布 ，再乘以即 关于 的条件分布 ，即可得到 的联合分布 。然后，可以求出 的边缘分布 ，这就等于是利用了 的取值求出了 的分布。

上述性质可以加以推广，得到一个马氏链的核心性质：如果我们已知某些条件，去求解某些表达式关于这些条件的期望，则事实上我们只需要那个距离所求事件最接近的条件就够了。例如，求期望表达式 时，在三个条件（ 的取值）之中只需要用到 这一个条件就够了。所以，我们有：

另一方面，如果我们有了更加接近 时刻的信息，比如我们知道了 ，那么 这条信息自然也用不着了，因为 对于 的所有影响又全部被 的信息给包含在内了。所以，我们又有：

如果我们把关于 的函数 换为示性函数 ，则我们可以得到上面所说的概率性质：

如果我们把“信息”、“条件”这些概念替换为“自然事件域”、“流”等概念，便可以得到马氏性的严格数学定义。不过在本书中，我们不苛求严谨的定义，只要求读者对马氏性有一个基本的认识：一方面，我们不能误认为 的分布与 取值没有关系，而另一方面，我们又可以简单而直接地想象马氏链的产生具有时间上的因果性：从 产生 ，从 产生 ，以此类推，形成漫长的随机过程。当我们处在这个时间序列上某个位置判断未来走势的时候，只需要用到当前的信息，而不用过去的信息。到底是“有关”还是“无关”，这需要读者自己理清思路。

除了马氏过程之外，人们感兴趣的随机过程还有许多种。例如在二阶自回归模型中，我们设 ，其中 为常系数， 是一个正态白噪声。在这个过程中，如果我们想估计 ，同时知道 与 的取值相比仅仅知道 无疑是更好的，所以这个时间序列就不具有马氏性。由于马氏过程具有比较好的数学性质以及较成熟的研究成果，所以在实践中人们更加倾向于将问题建模为马氏过程。

打个比方，我们可以用马氏过程来描述某人的一生， 代表他小学的状态， 代表他初中的状态， 代表他高中的状态。如果一个人就读于重点中学，那么他考上985或211的概率也比较大；而如果拥有985的学历，那么取得一份好的工作、走上人生巅峰的概率也比较大。人生就是在这一环紧扣一环的因果中前进的。

对于这个模型，有人可能会有疑问：我以后会经历什么、达到怎样的高度，怎么可能只和现在的我有关、和我小时候发生的事情没有关系？很多童年经历难道不是会影响终生么？如此说来，将现实中某些过程定义为马氏过程是否是不合理的？

这里涉及到一个问题，那就是你定义的“状态”究竟是什么。例如在前面所说的二阶自回归模型中， ，则随机变量 的序列不是一个马氏过程。但是，如果我们设 ，则二维随机向量 的序列就构成了一个马氏过程。因为我们在估计 的分布时，只需要用到 的信息。同理，如果我们将一个人的“状态”定义的比较完备，例如，定义一个人现在的状态既包括他的地位、学历，也包括他的性格、见识。那么，他小时候所经历的事情会对他现在的性格与见识产生影响，继而影响未来。只要将“状态”定义得比较完整，使得童年经历对于他的全部影响都已经被其现在的“状态”所包含，那么将人生历程看成马氏过程就显得相对合理了。

从某种意义上来说，一个随机过程能不能用马氏过程来建模，在于我们能不能很好地定义状态以及状态之间的转移方程。对于人生的问题，我们很难定义性格、学识这些状态，也无法判断童年经历会如何影响这种状态。阻碍我们为人生建模的是状态以及转移方程的定义，而非马氏性本身。“马氏性”成立与否主要取决于我们定义的“状态”以及其之间的转移方程是否成立。一旦将随机过程建模为马氏过程，就意味着我们在数学上有更多的手段去研究它。正确理解“马氏性”的含义对我们理解强化学习算法是十分重要的。

马尔可夫决策过程（MDP）

介绍了马氏过程之后，我们要来介绍马尔可夫决策过程（MDP）。事实上，马氏过程是概率论中的重要内容，而在工程问题中，人们更加关心的是MDP。下面我们来讲述马氏过程与马尔可夫决策过程的区别，以及为什么我们更加关心后者。

在上一节讲马氏过程的时候，我们举了个例子：如果你在一个平庸高中，那么你考上重点大学的概率就会比较小，而考上普通大学的概率比较大；如果你在一个985大学念书，那么找到好的工作的概率就比较大……以上的事实作为一个社会的普遍性现象是可以得到大量的数据支持的。

但是，如果将上述的普遍社会规律套入你的人生之中，你不免会觉得这样的规律过于“死气沉沉”而没有体现出你的“主观能动性”。在你就读于普通的中学的前提下，如果你很努力学习，则你考取重点大学的概率就会相对变高；如果你沉迷于打游戏、不花心思到学习上，那么你考取重点大学的概率就会变得很低很低。这说明，站在你的角度来看待人生的过程，考取重点大学的概率并不只是“客观的规律”决定的，也有你的“主观能动性”的成分。如果你人生将要面对的一切都被“客观规律”决定了，那我们努力拼搏又有什么意义呢？

因此，人们在马氏过程的基础上进行了修改，定义了MDP。在马氏过程中，我们只有内在的状态变量 （为了和下面MDP一致，我们换个符号将其记为 ），则马氏过程相当于只有以及状态之间的内在关系 。而在MDP中，我们为系统增加一个行为（action）变量 与一个“奖励”（reward）变量 。其中 代表了我们“主观能动性”的部分，相当于系统的“输入”；而 代表着在 时刻我们采取的行动带来的回报，相当于系统的“输出”。这样一来，在MDP中状态的转移关系不再是内在的，而是由状态 与输入的行动 共同决定。这也就是说，下一个时刻的状态 由转移概率模型 决定；而系统输出的奖励 同样由概率分布 决定，为了方便起见，也可以用随机变量 表示。

我们可以为“状态”与“动作”的关系打个比方：如果小王当前的状态是在普通中学就读。小王采取的行动是努力学习，则小王下一个状态进入重点大学的概率会高达0.5；而如果小王采取的行动是沉迷于玩王者荣耀，则小王进入重点大学的概率就只有0.2；而另一方面，如果小王本身就在重点高中就读，并且又努力学习，则小王进入重点大学的概率就会更高，高达0.9；而小王如果在重点中学中不务正业、贪图玩耍，那么其考上重点大学的概率可能就只有0.5，和普通中学中努力学习的学生一样，没有享受到重点中学的优势。这样的定义下，状态转移方程就不再是死气沉沉的“客观规律”，而在“客观规律”的基础上还要取决于“主观能动性” 。

奖励 是MDP中另一个重要的元素，它由 与 共同决定。服从概率分布 。我们也可将其直接写为随机变量的形式。 代表reward，即我们在MDP中获得的“奖励”、系统的“输出”。在MDP中，我们的核心目标就是要求出一种选择 的方式，使得我们获得最多的奖励。具体而言，有的时候我们的目标是要获得更大的期望奖励总和 ，有的时候则是要获得最大的“效用”，即奖励乘以时间衰减因子后的期望总和 ，还有的时候我们要在期望意义下极大化上式……无论如何，“奖励”是与我们的目标相关的变量。

例如，我们将 定义为人生各个阶段获得的“幸福”。如果我们在中学采取“努力学习”的行动，可能因为玩的时间更少，而只有较低的“幸福”。但另一方面，由于这帮助我们考上了更好的大学，这个更好的状态有助于我们未来获得更多的“幸福”。我们要在“先苦后甜”与“及时行乐”中进行取舍，选择正确的策略，以获得最幸福的人生。如何能够通过权衡取舍找到最优的解，便是强化学习的核心难点。

除了 这两个重要的变量之外，MDP中其实还有一个很重要的、但是容易被忽略的变量，即结束信号 ，代表着MDP何时结束。在马氏过程中，我们一般不考虑过程何时会“结束”，在MDP中则很不一样。这是因为二者研究的侧重点不同。

在马氏链中，我们常常假定链的长度是无穷的，这样我们就可以研究其一些宏观的数学性质。例如，将一个微粒在一个状态集合中转移跃迁的过程定义为马氏过程，“遍历定理”研究的是某个微粒在无穷长的时间内是否“肯定”会经历某个状态，或无穷次经历某个状态，而“强遍历定理”研究的是微粒处在不同状态之间的概率分布是否“肯定”会收敛于一个稳定的分布等等，其研究的对象往往是具有“宏观”的数学特性的。只有考虑大量微粒在状态之间的空间平均、或者单个微粒在无穷时间内的时间平均，这些规律才会呈现出来。

而在MDP中，我们一般假定链的长度是有限的，并且一般不会太长。例如我们想研究如何控制一辆无人车安全且高速地行驶、如何操控一个工业机器人高效地参与流水线生产、如何让AI下围棋击败人类，等等。我们想要解决具体的任务，而不是求什么“宏观特性”。一个具体任务总是不会无穷地持续下去的（对于较大的任务，我们可以将其拆分为几个子任务），否则就不实用了。因此，MDP的长度都是有限且比较短的。

我们一般假定，在某个状态 采取动作 之后，会有一定概率得到一个 的信号，代表这个MDP结束了。例如将下象棋定义为MDP，则一方被将死之后就会收到这个 的信号。为了与前面的概率形式相统一，我们可以定义一个取值为0或1的随机变量 。每一步我们除了得到 ，也会收到 （我们用 表示随机变量， 表示具体取值）。如果 取值为0，代表MDP还在继续，我们还会进入到 并选择 ；而如果 取值为1，代表MDP已经终止了。

至此，我们已经讲了MDP中的所有要素，它在马氏过程的基础上增加了作为“输入”的动作 以及作为“输出”的奖励 与结束信号 。我们习惯将MDP记作五元组 。其中 与 分别为状态集合与动作集合，可能是有限集或无穷集，而 则为各个变量之间的关系。由于 的信号是包含在 中的，所以也可以将MDP记为一个四元组 。很多书中为了简便，采用了这种四元组的定义。我们也采用四元组来记录MDP，但是要记住不可忽略 的意义。

马尔可夫过程与MDP的对比

在马氏链中，我们只有一个状态变量 ，状态之间具有内在转移关系 ，相对简单；而在MDP中，我们有状态变量 ，动作变量 ，奖励变量 ，以及结束信号 。这四个变量之间的转移关系具有概率分布 ， 以及 ，这就会使得我们面临的问题比马氏链要复杂得多。

无论是马氏链还是MDP，最为重要的性质是它们的各个变量之间的关系必须满足马尔可夫性。即 、 与 只是和 与 的值有关，和更早些时候的的 与 都没有直接关系。马尔可夫性是一个数学上的定义，如果我们要将现实问题定义为MDP，就必须说明它在逻辑上是满足马尔可夫性的。例如在下象棋的时候，当我们处于一个局面 ，之后应该怎么走、局势怎么发展应该只和当前局面 相关，与之前我们怎么走到 无关；又例如如果非要我们将人生过程定义为MDP， 就不能只是简单的“学历”，因为高考爆发来到A大学的人和高考失利来到A大学的人，恐怕后面的发展也是完全不一样的。为了使得马氏性成立，我们应该将状态定义为包括“性格”、“学识”、“意志力”等方方面面。从某种意义上说，对于那些不满足马尔可夫性的过程，如果将状态 设计得更加复杂、包含更多的信息，就可以使其更加接近马尔可夫性。人们提出强化学习，目标是要解决游戏AI、机器人控制、无人驾驶这一类问题。事实上，这一类问题未必天然就是MDP。但是，将其定义为MDP之后，我们就可以利用马尔可夫性去求解它，使得求解它们变得比没有马尔可夫性更简单。所以，我们必须将问题定义为MDP，后面所讲的所有强化学习的算法都会用到MDP的马尔可夫性。

除了都符合马尔可夫性之外，MDP和马氏过程有着很大的区别：

在马氏过程中，如果给定条件概率 ，以及初始状态分布 ，就完全确定了马氏链的分布。这就是说，对于所有的 与 ，我们可以求出所有 ；对于所有可能发生的马氏链轨道 ，我们可以求出它发生的概率是多少，即求出 。总的来说，马氏过程是一个“客观的”过程，当其转移规律确定之后，会发生的一切都被确定了。

在MDP中，情况却完全不同。即使我们的 、 、 ，以及初始的分布 都确定了，后续 的分布也不能确定。这是因为，有一个“主观的”、“可以自由选择”的 会影响 的分布。这个 应该怎么选择，就是我们强化学习的核心问题。一般而言，我们会希望找出一个从 到 的映射，即 。当 确定之后，则 的分布便真正地确定下来。这时候，我们就可以求出 ， 以及 这些具体分布。对于可能发生的所有轨道 ，我们也可以求出其发生的概率 。这也就是说，当 确定，一切就确定了。

我们可以想象， 、 与 是外在环境、客观规律，是题目给出的条件；而 是主观的选择，是我们对问题给出的解；给定客观条件的前提下，每一种 都能对应于一种 的分布，对应一个 的值。强化学习的目标就是要找出能够使得 最大的 。要注意的是， 完全是可以主观选择的，维数非常高、自由度非常大。要从中选择出让 期望最大的一种 无疑是很困难的。

有的时候，“环境”与“MDP”这两个词可以混用，我们可以说四元组 表示的是MDP，也可以说它表示的是一个环境。但是，二者的含义又稍有不同：在说“环境”时，我们一般仅仅代指那个客观的、给定的概率模型；而在说MDP的时候，我们一般隐含着面对这个概率模型我们的目标是力求最大化奖励总和。“MDP”与“环境”含义的区别，有些像是“问题”与“问题的条件”之间的区别。

总结一下马氏链与MDP的差别：马氏过程是一个具有“客观规律”，并因之而运动的系统。它不受到外部输入的影响，没有“主观能动性”发挥的空间。人们更加关心它的宏观数学性质，例如周期性、常返性、遍历性等等；而MDP则是一个不断接受外部输入，受到主观意志控制的系统。人们研究MDP时有着清晰的目的，即选择最佳的行动；与马氏过程相比，MDP是相对“微观的”、“具体的”，且具有“工程意义”与“实践意义”的。正是由于MDP的实用性，强化学习才会在今天得到如此多的关注。

回到本节开头的那个比方：如果我们的目的是要研究当前社会的结构化不公，写一篇社科方面的论文，那我们可以将社会作为客体，去寻找有关的数据；以研究普通中学的升学率是否不如重点中学，论证“寒门难出贵子”、“阶级固化”等客观现象，把社会最真实的一面揭露出来。但如果我们面对的是自己鲜活的人生，为了想要享有最丰盛的生命，那么我们就应该求解这个MDP中应该如何最大化“奖励总和”，做出人生的规划并为之拼搏。无论处在哪个阶级、具有何种初始状态都应该如此。因为只有努力，才有可能使得自己过得更好。马氏链与MDP不但定义有着很大区别，研究的方式与侧重点也有着明显的区别，希望读者可以分清楚。

介绍完MDP的定义后，想象力丰富的读者不免会联想到，在生产、生活、工程等各个领域中很多过程都可以套用到MDP上——只要分别定义出“状态”、“动作”、“奖励”这几大要素，并说明它们之间的转移关系满足马氏性，就可以定义MDP。在下一章中，我们将介绍MDP可以根据哪些标准分类、有哪些不同的MDP。

思考题

1、对于一个在一维直线上开赛车的游戏，将 定义为当前赛车的位置，将 定义为加速、减速，将 定义为到达终点，请问这能构成一个MDP吗？如果不能，应该将 定义为什么，才能使其构成一个MDP？

2、请思考生活中还有哪些场景能够定义为MDP？