2 马尔科夫决策过程

2.1 马尔科夫决策过程理论讲解

图2.1解释了强化学习的基本原理。智能体在完成某项任务时，首先通过动作A与周围环境进行交互，在动作A和环境的作用下，智能体会产生新的状态，同时环境会给出一个立即回报。如此循环下去，智能体与环境不断地交互从而产生很多数据。强化学习算法利用产生的数据修改自身的动作策略，再与环境交互，产生新的数据，并利用新的数据进一步改善自身的行为，经过数次迭代学习后，智能体能最终学到完成相应任务的最优动作（最优策略）。

从强化学习的基本原理能看出它与其他机器学习算法如监督学习和非监督学习的一些基本差别。在监督学习和非监督学习中，数据是静态的、不需要与环境进行交互，比如图像识别，只要给出足够的差异样本，将数据输入深度网络中进行训练即可。然而，强化学习的学习过程是动态的、不断交互的过程，所需要的数据也是通过与环境不断交互所产生的。所以，与监督学习和非监督学习相比，强化学习涉及的对象更多，比如动作，环境，状态转移概率和回报函数等。强化学习更像是人的学习过程：人类通过与周围环境交互，学会了走路，奔跑，劳动；人类与大自然，与宇宙的交互创造了现代文明。另外，深度学习如图像识别和语音识别解决的是感知的问题，强化学习解决的是决策的问题。人工智能的终极目的是通过感知进行智能决策。所以，将近年发展起来的深度学习技术与强化学习算法结合而产生的深度强化学习算法是人类实现人工智能终极目的的一个很有前景的方法。

无数学者们通过几十年不断地努力和探索，提出了一套可以解决大部分强化学习问题的框架，这个框架就是马尔科夫决策过程，简称 MDP。下面我们会循序渐进地介绍马尔科夫决策过程：先介绍马尔科夫性，再介绍马尔科夫过程，最后介绍马尔科夫决策过程。

1.第一个概念是马尔科夫性

所谓马尔科夫性是指系统的下一个状态s t+1 仅与当前状态s t 有关，而与以前的状态无关。

定义：状态s t 是马尔科夫的，当且仅当P[s t+1 |s t ]=P[s t+1 |s 1 ，…，s t ]。

定义中可以看到，当前状态s t 其实是蕴含了所有相关的历史信息s 1 ，…，s t ，一旦当前状态已知，历史信息将会被抛弃。

马尔科夫性描述的是每个状态的性质，但真正有用的是如何描述一个状态序列。数学中用来描述随机变量序列的学科叫随机过程。所谓随机过程就是指随机变量序列。若随机变量序列中的每个状态都是马尔科夫的，则称此随机过程为马尔科夫随机过程。

2.第二个概念是马尔科夫过程

马尔科夫过程的定义：马尔科夫过程是一个二元组（S，P），且满足：S是有限状态集合，P是状态转移概率。状态转移概率矩阵为： 。下面我们以一个例子来进行阐述。

如图2.2所示为一个学生的7种状态{娱乐，课程1，课程2，课程3，考过，睡觉，论文}，每种状态之间的转换概率如图所示。则该生从课程 1 开始一天可能的状态序列为：

课1-课2-课3-考过-睡觉

课1-课2-睡觉

以上状态序列称为马尔科夫链。当给定状态转移概率时，从某个状态出发存在多条马尔科夫链。对于游戏或者机器人，马尔科夫过程不足以描述其特点，因为不管是游戏还是机器人，他们都是通过动作与环境进行交互，并从环境中获得奖励，而马尔科夫过程中不存在动作和奖励。将动作（策略）和回报考虑在内的马尔科夫过程称为马尔科夫决策过程。

3.第三个概念是马尔科夫决策过程

马尔科夫决策过程由元组（S，A，P，R，γ）描述，其中：

S 为有限的状态集

A 为有限的动作集

P 为状态转移概率

R 为回报函数

γ 为折扣因子，用来计算累积回报。

注意，跟马尔科夫过程不同的是，马尔科夫决策过程的状态转移概率是包含动作的，即 。

举个例子如图2.3所示。

图2.3为马尔科夫决策过程的示例图，图2.3与图2.2对应。在图2.3中，学生有五个状态，状态集为S={s 1 ，s 2 ，s 3 ，s 4 ，s 5 }，动作集为A={玩，退出，学习，发表，睡觉}，在图2.3中立即回报用R标记。

强化学习的目标是给定一个马尔科夫决策过程，寻找最优策略。所谓策略是指状态到动作的映射，策略常用符号π表示，它是指给定状态s时，动作集上的一个分布，即

这个公式是什么意思呢？策略的定义是用条件概率分布给出的。我相信，一涉及概率公式，大部分人都会心里咯噔一下，排斥之情油然而生。但是，要想完全掌握强化学习这门工具，概率公式必不可少。只有掌握了概率公式，才能真正领会强化学习的精髓。关于概率的知识看本章第二节。

简单解释下概率在强化学习中的重要作用。首先，强化学习的策略往往是随机策略。采用随机策略的好处是可以将探索耦合到采样的过程中。所谓探索是指机器人尝试其他的动作以便找到更好的策略。其次，在实际应用中，存在各种噪声，这些噪声大都服从正态分布，如何去掉这些噪声也需要用到概率的知识。

言归正传，公式（2.1）的含义是：策略π在每个状态s指定一个动作概率。如果给出的策略π是确定性的，那么策略π在每个状态s指定一个确定的动作。

例如其中一个学生的策略为π 1 （玩|s 1 ）=0.8，是指该学生在状态s 1 时玩的概率为0.8，不玩的概率是0.2，显然这个学生更喜欢玩。

另外一个学生的策略为π 2 （玩|s 1 ）=0.3，是指该学生在状态s 1 时玩的概率是 0.3，显然这个学生不爱玩。依此类推，每个学生都有自己的策略。强化学习是找到最优的策略，这里的最优是指得到的总回报最大。

当给定一个策略π时，我们就可以计算累积回报了。首先定义累积回报：

当给定策略π时，假设从状态s 1 出发，学生状态序列可能为

此时，在策略π下，利用（2.2）式可以计算累积回报G 1 ，此时G 1 有多个可能值。由于策略π是随机的，因此累积回报也是随机的。为了评价状态s 1 的价值，我们需要定义一个确定量来描述状态s 1 的价值，很自然的想法是利用累积回报来衡量状态s 1 的价值。然而，累积回报G 1 是个随机变量，不是一个确定值，因此无法描述，但其期望是个确定值，可以作为状态值函数的定义。

（1）状态值函数。

当智能体采用策略π时，累积回报服从一个分布，累积回报在状态s处的期望值定义为状态-值函数：

注意：状态值函数是与策略π相对应的，这是因为策略π决定了累积回报G的状态分布。

图2.4是与图2.3相对应的状态值函数图。图中空心圆圈中的数值为该状态下的值函数。即：υ π （s 1 ）=-2.3，υ π （s 2 ）=-1.3，υ π （s 3 ）=2.7，υ π （s 4 ）=7.4，υ π （s 5 ）=0

相应地，状态-行为值函数为

（2.3）式和（2.4）式分别给出了状态值函数和状态-行为值函数的定义计算式，但在实际真正计算和编程的时候并不会按照定义式编程。接下来我们会从不同的方面对定义式进行解读。

（2）状态值函数与状态-行为值函数的贝尔曼方程。

由状态值函数的定义式（2.3）可以得到：

（2.5）式最后一个等号的证明：

这里需要注意的是对哪些变量求期望。

同样我们可以得到状态-动作值函数的贝尔曼方程：

状态值函数与状态-行为值函数的具体推导过程如下。

图2.5和图2.6分别为状态值函数和行为值函数的具体计算过程。其中空心圆圈表示状态，实心圆圈表示状态-行为对。

图2.5为值函数的计算分解示意图，图2.5B计算公式为

图2.5B给出了状态值函数与状态-行为值函数的关系。图2.5C计算状态-行为值函数为

将（2.8）式代入（2.7）式可以得到：

在2.6C中，

将（2.10）代入（2.8）中，得到状态-行为值函数：

公式（2.9）可以在图2.4中进行验证。选择状态s 4 处。由图2.4知道υ（s 4 ）=7.4，由公式（2.9）得

保留一位小数为7.4。

计算状态值函数的目的是为了构建学习算法从数据中得到最优策略。每个策略对应着一个状态值函数，最优策略自然对应着最优状态值函数。

定义：最优状态值函数υ * （s） 为在所有策略中值最大的值函数，即 ，最优状态-行为值函数q * （s，a）为在所有策略中最大的状态-行为值函数，即

我们由（2.9）式和（2.11）式分别得到最优状态值函数和最优状态-行动值函数的贝尔曼最优方程：

若已知最优状态-动作值函数，最优策略可通过直接最大化q * （s，a）来决定。

如图2.7所示为最优状态值函数示意图，图中虚线箭头所示的动作为最优策略。

至此，我们将强化学习的基本理论即马尔科夫决策过程介绍完毕。现在该对强化学习算法进行形式化描述了。

我们定义一个离散时间有限范围的折扣马尔科夫决策过程M=（S，A，P，r，ρ 0 ，γ，T），其中S为状态集，A为动作集，P：S×A×S→R是转移概率，r：S×A→[-R max ，R max ]为立即回报函数，ρ 0 ：S→R是初始状态分布，γ∈[0，1]为折扣因子，T为水平范围（其实就是步数）。τ为一个轨迹序列，即τ=（s 0 ，a o ，s 1， a 1 ，…），累积回报为 ，强化学习的目标是找到最优策略π，使得该策略下的累积回报期望最大，即 。

2.2 MDP中的概率学基础讲解

本节解释公式（2.1）随机策略的定义。在强化学习算法中，随机策略得到广泛应用，因为随机策略耦合了探索。后面要介绍的很多强化学习算法的策略都采用随机策略，所以，很有必要理解什么是随机策略。随机策略常用符号 表示，它是指给定状态s时动作集上的一个分布。要理解分布首先要理解随机变量 [2] 。

（1）随机变量。

随机变量是指可以随机地取不同值的变量，常用小写字母表示。在MDP中随机变量指的是当前的动作，用字母 表示。在图2.3的例子中，随机变量 可取的值为“玩”、“退出”、“学习”、“发表”和“睡觉”。随机变量可以是离散的也可以是非离散的，在该例子中随机变量是离散的。有了随机变量，我们就可以描述概率分布了。

（2）概率分布。

概率分布用来描述随机变量在每个可能取到的值处的可能性大小。离散型随机变量的概率分布常用概率质量函数来描述，即随机变量在离散点处的概率。连续型随机变量的概率分布则用概率密度函数来描述。在图 2.3 的例子中，指定一个策略 就是指定取每个动作的概率。

（3）条件概率。

策略π（a|s）是条件概率。条件概率是指在其他事件发生时，我们所关心的事件所发生的概率。在我们的例子中π（a|s）是指在当前状态 处，采取某个动作 的概率。当给定随机变量后，状态 处的累积回报 也是随机变量，而且其分布由随机策略 决定。状态值函数定义为该累积回报的期望。下面我们再看看期望和方差的概念。

（4）期望和方差。

函数 关于某分布 的期望是指，当 x 由分布 产生、 作用于 时， 的平均值。对于离散型随机变量，期望公式为

对于连续型随机变量，期望通过积分求得

期望的运算是线性的，即

期望的线性运算在后面的很多推导中都会用到。

（5）方差。

方差是衡量利用当前概率分布采样时，采样值差异的大小，可用如下公式得到：

从定义我们可以看到，方差越小，采样值离均值越近，不确定性越小。尤其是方差很小时，采样值都集中在均值附近，因此不确定性很小（这时，你猜测采样值是均值，那么该猜测离实际采样点很近）。方差的平方根被称为标准差。有了均值和方差，我们现在就可以谈一谈在强化学习中最常用的概率分布了。

最常用的概率分布也就是最常用的随机策略。

（1）贪婪策略。

贪婪策略是一个确定性策略，即只有在使得动作值函数q * （s，a）最大的动作处取概率1，选其他动作的概率为0。

（2）ε-greedy策略。

ε-greedy策略是强化学习最基本最常用随机策略。其含义是选取使得动作值函数最大的动作的概率为 ，而其他动作的概率为等概率，都为 。ε-greedy平衡了利用（exploitation）和探索（exploration），其中选取动作值函数最大的部分为利用，其他非最优动作仍有概率为探索部分。

（3）高斯策略。

一般高斯策略可以写成 。其中 为确定性部分， 为零均值的高斯随机噪声。高斯策略也平衡了利用和探索，其中利用由确定性部分完成，探索由 完成。高斯策略在连续系统的强化学习中应用广泛。

（4）玻尔兹曼分布。

对于动作空间是是离散的或者动作空间并不大的情况，可采用玻尔兹曼分布作为随机策略，即

其中 为动作值函数。该策略的含义是，动作值函数大的动作被选中的概率大，动作值函数小的动作被选中的概率小。

2.3 基于gym的MDP实例讲解

本节我们以机器人找金币为例子，构建其MDP框架。

如图2.8所示为机器人找金币的例子。该网格世界一共8个状态，其中状态6和状态8是死亡区域，状态7是金币区域。机器人的初始位置为网格世界中的任意一个状态，机器人从初始状态出发寻找金币，机器人每探索一次，进入死亡区域或找到金币，本次探索结束。

在2.1节我们已经定义了一个马尔科夫决策过程。我们知道马尔科夫决策过程由元组 来描述。下面我们将机器人找金币的例子建模为MDP。

状态空间： ；动作空间： ；状态转移概率为机器人的运动方程，回报函数为：找到金币的回报为 1，进入死亡区域的回报为-1，机器人在状态1～5之间转换时，回报为0。

下面，我们基于gym构建机器人找金币的gym环境。

一个 gym 的环境文件，其主体是个类，在这里我们定义类名为：GridEnv，其初始化为环境的基本参数，该部分代码在 https：//github.com/gxnk/reinforcement-learning-code的grid_mdp.py文件中。我们先看下源代码。

状态空间：

动作空间：

回报函数：

状态转移概率：

有了状态空间、动作空间和状态转移概率，我们便可以写step（a）函数了。这里特别要注意的是，step（）函数的输入是动作，输出是下一个时刻的动作、回报、是否终止和调试信息。尤其需要注意不要弄错了输出的顺序。对于调试信息，可以为空，但不能缺少，否则会报错，常用{}来代替。我们看下源代码。

step（）函数就是这么简单。下面我们重点介绍如何写 render（）函数。从图 2.8 机器人找金币的示意图我们可以看到，网格世界是由一些线和圆组成的。因此，我们可以调用rendering中的画图函数来绘制这些图像。

整个图像是一个600×400的窗口，可用如下代码实现：

创建网格世界，一共包括 11 条直线，事先算好每条直线的起点和终点坐标，然后绘制这些直线，代码如下：

接下来创建死亡区域，我们用黑色实心圆代表死亡区域，源代码如下：

创建金币区域，用浅色的圆圈来表示：

创建机器人，我们依然用圆来表示机器人，为了跟死亡区域和金币区域不同，我们可以设置不同的颜色：

创建完之后，给 11 条直线设置颜色，并将这些创建的对象添加到几何中，代码如下：

接下来，开始设置机器人的位置。机器人的位置根据其当前所处的状态不同，所在的位置也不同。我们事先计算出每个状态点机器人位置的中心坐标，并存储到两个向量中，在类初始化中给出：

根据这两个向量和机器人当前的状态，我们就可以设置机器人当前的圆心坐标了，即

最后还需要一个返回语句：

以上便完成了render（）函数的建立。

下面我们再看一下reset（）函数的建立。

reset（）函数常常用随机的方法初始化机器人的状态，即

全部的代码可以上github下载学习。下面重点讲一讲如何注册建好的环境，以便通过gym的标准形式进行调用。其实环境的注册很简单，只需要三步，分述如下。

第一步，将我们自己的环境文件（笔者创建的文件名为 grid_mdp.py）拷贝到你的gym安装目录/gym/gym/envs/classic_control文件夹中（拷贝在此文件夹中是因为要使用rendering模块。当然本方法并不是唯一的，也可以采用其他办法。）。

第二步，打开该文件夹（第一步中的文件夹）下的__init__.py文件，在文件末尾加入语句：

第三步，进入文件夹的gym安装目录/gym/gym/envs，打开该文件夹下的__init__.py文件，添加代码：

第一个参数id就是你调用gym.make（‘id’）时的id，这个id可以随便选取，笔者取的名字是GridWorld-v0。

第二个参数就是函数路口了，后面的参数原则上来说可以不必写。

经过以上三步，就完成了注册。下面，我们用一个简单的demo来测试下环境的效果。

我们依然写个终端程序，代码如下。

代码运行后会出现如图2.9所示的效果。

2.4 习题

1.马尔科夫过程与马尔科夫决策过程的区别。

2.随机策略的理解。

3.安装gym并测试其中的CartPole实例。

4.基于gym构建如下迷宫世界： v4LDaSSuaCLUraXmx7SGlR9rCs82R1l2FymiYhAafHy5z6Q6osQBD2TlnmRpvOtG