强化学习入门第一讲马尔科夫决策过程

强化学习算法理论的形成可以追溯到上个世纪七八十年代，近几十年来强化学习算法一直在默默地不断进步，真正火起来是最近几年。代表性的事件是DeepMind 团队于2013年12月首次展示了机器利用强化学习算法在雅达利游戏中打败人类专业玩家，其成果在2015年发布于顶级期刊《自然》上；2014年，谷歌将DeepMind 团队收购。2016年3月，DeepMind开发的AlphaGo程序利用强化学习算法以4:1击败世界围棋高手李世石，至此强化学习算法引起更多学者的关注。如今，强化学习算法已经在如游戏，机器人等领域中开花结果。各大科技公司，如谷歌，facebook，百度，微软等更是将强化学习技术作为其重点发展的技术之一。可以说强化学习算法正在改变和影响着这个世界，掌握了这门技术就掌握了改变世界和影响世界的工具。

现在网上有一些强化学习的教程，这些教程都来自世界顶尖名校，如2015年David Silver的经典课程Teaching ，2017年加州大学伯克利分校Levine, Finn, Schulman的课程 CS 294 Deep Reinforcement Learning, Spring 2017 ，卡内基梅隆大学的2017 春季课程Deep RL and Control 。据我所了解，国内还没有一门与之对应的中文课程，为了填补这个空白，因此决定写这个中文讲义。由于个人水平有限，理解的难免会有偏差的地方，有些地方也会有疏漏，不对的地方望各位见谅，也欢迎各位交流、批评、指正。以文会友也是本文写作的另外一个目的。公布个qq交流群202570720，有问题群里留言。

图1.1 强化学习原理解释

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

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

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

第一个概念是马尔科夫性：所谓马尔科夫性是指系统的下一个状态 $s_{t+1}$ 仅与当前状态 $s_t$ 有关，而与以前的状态无关。

定义：状态 $s_t$ 是马尔科夫的，当且仅当 $[ Pleft[s_{t+1}|s_t ight]=Pleft[s_{t+1}|s_1,cdots ,s_t ight] ]$ 。

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

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

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

马尔科夫过程的定义：马尔科夫过程是一个二元组 $left(S,P ight)$ ，且满足： $S$ 是有限状态集合， $P$ 是状态转移概率。状态转移概率矩阵为：

$[ P=left[egin{matrix} P_{11}& cdots& P_{1n}\ vdots& vdots& vdots\ P_{n1}& cdots& P_{nn}\ end{matrix} ight] ]$ 。下面我们以一个例子来进行阐述。

图1.2 马尔科夫过程示例图

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

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

课1-课2-睡觉

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

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

马尔科夫决策过程由元组 $left(S,A,P,R,gamma ight)$ 描述，其中： $S$ 为有限的状态集, $A$ 为有限的动作集, $P$ 为状态转移概率, $R$ 为回报函数, $gamma$ 为折扣因子，用来计算累积回报。注意，跟马尔科夫过程不同的是，马尔科夫决策过程的状态转移概率是包含动作的即： $P_{ss'}^{a}=Pleft[S_{t+1}=s'|S_t=s,A_t=a ight]$

举个例子：

图1.3 马尔科夫决策过程示例图

图1.3为马尔科夫决策过程的示例图，图1.3与图1.2对应。在图1.3中，学生有五个状态，状态集为 $S=left{s_1,s_2,s_3,s_4,s_5 ight}$ ，动作集为A={玩，退出，学习，发论文，睡觉}，在图1.3中立即回报用红色标记。

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

$[ pileft(a|s ight)=pleft[A_t=a|S_t=s ight] ]$ (1.1)

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

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

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

例如其中一个学生的策略为 $[ pi_1left( extrm{玩}|s_1 ight)=0.8 ]$ ，是指该学生在状态 $s_1$ 时玩的概率为0.8，不玩的概率是0.2，显然这个学生更喜欢玩。

另外一个学生的策略为 $pi_2left( extrm{玩}|s_1 ight)=0.3$ ，是指该学生在状态 $s_1$ 时玩的概率是0.3，显然这个学生不爱玩。依此类推，每学生都有自己的策略。强化学习是找到最优的策略，这里的最优是指得到的总回报最大。

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

$[ G_t=R_{t+1}+gamma R_{t+2}+cdots =sum_{k=0}^{infty}{gamma^kR_{t+k+1}}\\ left(1.2 ight) ]$

当给定策略 $pi$ 时，假设从状态 $s_1$ 出发，学生状态序列可能为：

$s_1 ightarrow s_2 ightarrow s_3 ightarrow s_4 ightarrow s_5 ;\ s_1 ightarrow s_2 ightarrow s_3 ightarrow s_5 \ ......$

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

状态值函数：

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

$upsilon_{pi}left(s ight)=E_{pi}left[sum_{k=0}^{infty}{gamma^kR_{t+k+1}|S_t=s} ight]$ (1.3)

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

图1.4 状态值函数示意图

如图1.4所示为与图1.3相对应的状态值函数图。图中白色圆圈中的数值为该状态下的值函数。即：

$upsilon_{pi}left(s_1 ight)=-2.3,\ upsilon_{pi}left(s_2 ight)=-1.3,\ upsilon_{pi}left(s_3 ight)=2.7,\upsilon_{pi}left(s_4 ight)=7.4,\ upsilon_{pi}left(s_5 ight)=0$

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

$[ q_{pi}left(s,a ight)=E_{pi}left[sum_{k=0}^{infty}{gamma^kR_{t+k+1}|S_t=s,A_t=a} ight] ]$ (1.4)

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

状态值函数与状态-行为值函数的贝尔曼方程

由状态值函数的定义式(1.3)可以得到：

$upsilonleft(s ight)=Eleft[G_t|S_t=s ight] \ =Eleft[R_{t+1}+gamma R_{t+2}+cdots |S_t=s ight] \ =Eleft[R_{t+1}+gammaleft(R_{t+2}+gamma R_{t+3}+cdots ight)|S_t=s ight] \ =Eleft[R_{t+1}+gamma G_{t+1}|S_t=s ight] \ =Eleft[R_{t+1}+gammaupsilonleft(S_{t+1} ight)|S_t=s ight]$ (1.5)

最后一个等号的补充证明：

$\ Vleft(S_t ight)=E_{s_t,s_{t+1},cdots}left(Rleft(t+1 ight)+gamma Gleft(S_{t+1} ight) ight) \ =E_{s_t}left(Rleft(t+1 ight)+gamma E_{s_{t+1},cdots}left(Gleft(S_{t+1} ight) ight) ight) \ =E_{s_t}left(Rleft(t+1 ight)+gamma Vleft(S_{t+1} ight) ight) \ =Eleft(Rleft(t+1 ight)+gamma Vleft(S_{t+1} ight) ight)$

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

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

$[ q_{pi}left(s,a ight)=E_{pi}left[R_{t+1}+gamma qleft(S_{t+1},A_{t+1} ight)|S_t=s,A_t=a ight]\\ left(1.6 ight) ]$

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

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

图1.5 状态值函数的计算示意图

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

$[ upsilon_{pi}left(s ight)=sum_{ain A}{pileft(a|s ight)q_{pi}left(s,a ight)}\\left(1.7 ight) ]$

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

$[ q_{pi}left(s,a ight)=R_{s}^{a}+gammasum_{s'}{P_{ss'}^{a}}upsilon_{pi}left(s' ight)\\left(1.8 ight) ]$

将(1.8)式带入到(1.7)式可以得到：

$[ upsilon_{pi}left(s ight)=sum_{ain A}{pileft(a|s ight)left(R_{s}^{a}+gammasum_{s'in S}{P_{ss'}^{a}upsilon_{pi}left(s' ight)} ight)}\\left(1.9 ight) ]$

图1.6 状态-行为值函数计算

在1.6C中，

$[ upsilon_{pi}left(s' ight)=sum_{a'in A}{pileft(a'|s' ight)q_{pi}left(s',a' ight)}\\left(1.10 ight) ]$

将(1.10)带入到(1.8)中，得到行为状态-行为值函数：

$[ q_{pi}left(s,a ight)=R_{s}^{a}+gammasum_{s'in S}{P_{ss'}^{a}sum_{a'in A}{pileft(a'|s' ight)q_{pi}left(s',a' ight)}}\\left(1.11 ight) ]$

公式(1.9)可以在图1.4中进行验证。选择状态 $s_4$ 处。由图1.4知道 $upsilonleft(s_4 ight)=7.4$ ，由公式(1.9)得：

$[ upsilonleft(s_4 ight)=0.5*left(1+0.2*left(-1.3 ight)+0.4*2.7+0.4*7.4 ight)+0.5*10=7.39 ]$

保留一位小数为7.4

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

定义：最优状态值函数 $upsilon^*left(s ight)$ ,为在所有策略中值最大的值函数即： $upsilon^*left(s ight)=max_{pi}upsilon_{pi}left(s ight)$ ，最优状态-行为值函数 $q^*left(s,a ight)$ 为在所有策略中最大的状态-行为值函数，即：

$q^*left(s,a ight)=max_{pi}q_{pi}left(s,a ight)$

我们由(1.9)式和(1.11)式分别得到最优状态值函数和最优状态-行动值函数的贝尔曼最优方程：

$[ upsilon^*left(s ight)=max_aR_{s}^{a}+gammasum_{s'in S}{P_{ss'}^{a}upsilon^*left(s' ight)\\left(1.12 ight)} ]$

$[ q^*left(s,a ight)=R_{s}^{a}+gammasum_{s'in S}{P_{ss'}^{a}max_{a'}q^*left(s',a' ight)}\\left(1.13 ight) ]$

若已知最优状态-动作值函数，最优策略可通过直接最大化 $q^*left(s,a ight)$ 来决定。

$[ pi_*left(a|s ight)=left{egin{array}{c} 1 if a=underset{ain A}{argmax}q_*left(s,a ight)\ 0 otherwis\ end{array} ight. ]$ (1.14)

图1.7 最优值函数和最优策略

图1.7为最优状态值函数示意图，图中红色箭头所示的动作为最优策略。

至此，我们将强化学习的基本理论介绍完毕。现在是时候该对强化学习算法进行形式化描述了。

我们定义一个离散时间有限范围的折扣马尔科夫决策过程 $[ M=left(S,A,P,r, ho_0,gamma ,T ight) ]$ ，其中 $S$ 为状态集， $A$ 为动作集， $P:S imes A imes S ightarrow R$ 是转移概率， $[ r:S imes A ightarrowleft[-R_{max},R_{max} ight] ]$ 为立即回报函数， $[ ho_0:S ightarrow R ]$ 是初始状态分布， $[ gammainleft[0,1 ight] ]$ 为折扣因子， $T$ 为水平范围（其实就是步数）. $au$ 为一个轨迹序列，即 $au =left(s_0,a_0,s_1,a_1,cdots ight)$ ，累积回报为 $[ R=sum_{t=0}^T{gamma^t}r_t ]$ ，强化学习的目标是：找到最优策略 $pi$ ，使得该策略下的累积回报期望最大，即： $[ max_{pi}int{Rleft( au ight)}p_{pi}left( au ight)d au ]$ 。

根据策略最优定理知道，当值函数最优时采取的策略也是最优的。反过来，策略最优时值函数也最优。

图1.8 强化学习算法分类

如图1.8所示，强化学习算法根据以策略为中心还是以值函数最优可以分为两大类，策略优化方法和动态规划方法。其中策略优化方法又分为进化算法和策略梯度方法；动态规划方法分为策略迭代算法和值迭代算法。策略迭代算法和值迭代算法可以利用广义策略迭代方法进行统一描述。

另外，强化学习算法根据策略是否是随机的，分为确定性策略强化学习和随机性策略强化学习。根据转移概率是否已知可以分为基于模型的强化学习算法和无模型的强化学习算法。另外，强化学习算法中的回报函数 $r$ 十分关键，根据回报函数是否已知，可以分为强化学习和逆向强化学习。逆向强化学习是根据专家实例将回报函数学出来。

强化学习入门第一讲 马尔科夫决策过程

强化学习入门第一讲马尔科夫决策过程