【强化学习】易忽略的强化学习知识之基础知识及MDP

2017 年 12 月 22 日 产业智能官

作者：Evan 来源：机器学习算法与自然语言处理

推荐阅读时间：8min~12min

主要内容：容易忽略的强化学习知识之基础知识及MDP

由于我对RL的期望挺大，很看好它的前景，故之后应该会写下一个系列的强化学习文章，标题是易忽略的强化学习知识之XX，也就是说，我写下的是我觉得有必要知道比较重要并容易忽略的知识。也许不会所有强化学习的知识都全面的写，但希望可以对大家有所帮助，同时巩固我自己的知识！

强化学习是什么？和监督学习，无监督学习是什么关系？
强化学习的主要应用是什么？在其他如NLP的应用呢？
模仿学习是什么？和强化学习联系？
强化学习的整体运行流程是什么样的呢？
强化学习的分类
什么是马尔可夫(Markov)性？什么是MP?什么是MRP？
动态规划是什么？为什么可以利用动态规划来解决MDP？

强化学习是什么？和监督学习，无监督学习是什么关系？

强化学习是什么：是多学科多领域交叉的一个产物，它的本质就是解决“decision making”问题，即学会自动进行决策。

在计算机科学领域体现为机器学习算法。
在工程领域体现在决定操作动作的顺序来得到最好的结果。
在神经科学领域体现在理解人类大脑如何做出决策，主要的研究是奖励机制。
在心理学领域，研究动物如何做出决策，动物的行为是由什么导致的。
在经济学领域体现在博弈论的研究。
.......

它是什么可以是如图所示：

以上所有的问题最终都归结为一个问题，人为什么能够并且如何做出最优决策。是怎么样找到最优决策的

然后，它和监督学习，无监督学习是什么关系？

机器学习包括：监督学习、无监督学习、强化学习，故强化学习是机器学习的一个分支，和监督，无监督是并列关系。

无监督学习和强化学习的区别应该容易知道，下面说说监督学习和强化学习的区别，从强化学习的特点出发：

强化学习没有监督数据、只有奖励信号
奖励信号不一定是实时的，而很可能是延后的，有时甚至延后很多。且时间（序列）是一个重要因素。
强化学习面对的输入(状态)总是在变化且不独立，输入不像监督学习是独立同分布的。而每当算法做出一个行为，它影响了下一次决策的输入，我认为这点是最重要的区别。

强化学习的主要应用是什么？在其他领域如NLP的应用呢？

首先强化学习现有具有非常广泛的应用：直升机特技飞行、经典游戏、投资管理、发电站控制、让机器人模仿人类行走等等。

强化学习现有在nlp的应用：文本序列生成，对话策略决策，用户目标模拟等等。

强化学习现有在cv的应用：强化学习的Attention方法在图像的应用，强化学习润色照片等等

然后我认为强化学习在nlp或cv领域是有很大前景的！为什么？

比如强化学习是天然可以在NLP上应用的：

在离散空间的文本生成和序列决策，RL有先天的对应，也就是说，通过agent在离散策略空间的搜索生成下一个词或者序列，结合reward的反馈，是可以很好的work的。
先举个例子，在goal oriented的对话系统的，关键步骤就是决策下一轮对话agent该干什么（提问？确认？结束？），那就可以利用RL的方法来决策。而RL的本质无非就是结合环境的观测加上reward的引导做出下一步的决策。
最后是RL的优势：可以克服其他目标函数如MLE的缺陷，可以模拟大量样本，或者借助先前经验进行学习（如DQN）等等。

cv的话我不是很了解，但也有一些应用RL的论文，只要转为状态到决策问题，应该都是可以做的。

模仿学习是什么？和强化学习有什么区别和联系？

举个CS249（是门好课）的例子，如果我们想让机器学会开车，一个很直接的想法是观察人类行为，并且模仿人类，在相应观测下做出人类所做行为。将这个想法实现起来也很简单，只需要收集该任务的一些观测（路面的画面），以及每个观测人类会做出的反应（转动方向盘），然后像监督学习一样训练一个神经网络，以观测为输入，人类行为为标签，其中行为是离散时是分类任务，连续时是回归任务：

然而这简单的监督学习理论上并不可行，一个直观的原因是由于现实的随机性或者复杂性，使得机器所采用的动作和人类的动作有偏差或者动作所产生的结果有偏差，这样在有偏差的下一状态，机器还会做出有偏差的动作，使得之后状态的偏差积累，导致机器遇到监督学习时没有碰到过的状态，那机器就完全不知道该怎么做了,也就是如下图所示：

需要人类提供的大量数据（尤其是深度学习，需要大量样本）。
人类对一些任务也做的不太好，对于一些复杂任务，人类能做出的动作有限。
我们希望机器能自动学习，即能不断地在错误中自我完善，而不需要人类的指导。

也就是说，直接用模仿学习来解决实际问题很多时候可能比强化学习弱，但是在有些方面比如解决多步决策（sequential decision）中，因学习器不能频繁地得到奖励，且这种基于累积奖赏及学习方式存在非常巨大的搜索空间，传统的强化学习不能很好的解决问题。

而我们先通过模仿学习学得初始策略模型，然后在通过强化学习改进模型，获得更好的策略，就可以较好地解决多步决策问题。更多关于模仿学习的的知识，比如逆强化学习什么的，之后我也可能会写，这里先推荐一篇文章吧，有兴趣可以了解。

主要内容：

强化学习的整体运行流程是什么样的呢？

强化学习的分类

什么是马尔可夫(Markov)性？什么是MP?什么是MRP？

动态规划是什么？为什么可以利用动态规划来解决MDP？

强化学习的运行流程

图来自网上

如上图。对于agent：我们构造出一个agent(图中的大脑部分)，agent能够执行某个策略动作（action），例如决定机器人朝哪个方向走，围棋棋子下在哪个位置。agent能够接收当前环境(图中的地球部分)的一个observation。

注意，这里的假设observation是完全的，例如当前对围棋盘上的已下棋的观测。agent还能接收当它执行某个action后的reward，即在第t步agent的工作流程是执行一个动作 At，获得该动作之后的环境观测状况Ot，以及获得这个动作的反馈奖赏Rt。

对于环境：环境environment(图中的地球部分)则是agent交互的对象，它是一个行为不可控制的对象，agent一开始不知道环境会对不同action做出什么样的反应，而环境会通过observation告诉agent当前的环境状态，同时环境能够根据可能的最终结果反馈给agent一个reward。

例如围棋棋面就是一个环境，它可以根据当前的棋面状况估计一下黑白双方输赢的比例。因而在第t步，environment的工作流程是接收一个At，对这个动作做出反应之后传递环境状况和评估的reward给agent。reward奖赏Rt，是一个反馈标量值，它表明了在第t步agent做出的决策有多好或者有多不好，而整个强化学习优化的目标就是最大化累积reward。

强化学习的分类

分类要好好多说下，因为强化学习中的算法很多，从不同的角度归类的方式也很多，搞清楚什么什么算法是一类的，有助于我们的记忆和理解。首先如图：

图来自网上

强化学习算法可分为策略优化方法和动态规划优化两大类。其中策略优化方法又分为进化算法和策略梯度方法；动态规划方法分为策略迭代算法和值迭代算法。策略迭代算法和值迭代算法可以利用广义策略迭代方法进行统一描述。

根据转移概率是否已知和某个动作带来的奖励可以分为基于模型的强化学习算法和无模型的强化学习算法。

需要注意的是值迭代和策略迭代是基于模型的（base model）的，也就是基于模型的，而蒙特卡洛树搜索或者其他base model是两个不一样的base model的，前者是实实在在的了解环境，在对环境有所了解的基础上（体现在知道等）建模。而后者是用“想象力对环境进行建模”，也就是多出了一个虚拟环境。

上面一图算是一个总结，注意根据model是否free分和以值函数和策略优化分是两回事，他们是有交叉的。

同时，强化学习算法根据策略是否是随机的，分为确定性策略强化学习和随机性策略强化学习。另外，强化学习算法中的回报函数十分关键，根据回报函数是否已知，可以分为强化学习和逆向强化学习。逆向强化学习是根据专家实例将回报函数学出来。

什么是马尔可夫(Markov)性？什么是MP?什么是MRP？

马尔可夫性：所谓马尔科夫性是指系统的下一个状态s(t+1)仅与当前状态st有关，而与以前的状态无关。用公式表示的话，则为：状态st是马尔科夫的，当且仅当

换句话说，当前状态st其实是蕴含了所有相关的历史信息s1,s2,..st，一旦当前状态已知，历史信息将会被抛弃。简单来说，未来只和当前有关，当我们需要去决策未来时，只需要在当下的基础上去估计，因为当下已经包含之前的所有历史。

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

马尔可夫链/过程(Markov Chain/Process)，是具有马尔可夫(markov)性质的随机状态序列s1,s2....st。由[S,P]组成。其中S表示状态，P表示状态转移概率。

下面举例下David Silver公开课中的例子

如下图1圆圈内是状态，箭头上的值是状态之间的转移概率。class指上第几堂课，facebook指看facebook网页，可以看成上网玩耍，pub指去酒吧，pass指通过考试，sleep指睡觉。例如处于class1有0.5的概率转移到class2，或者0.5的概率转移到facebook。

从给定的条件中，可以产生非常多的随机序列，例如C1 C2 C3 Pass Sleep或者C1 FB FB C1 C2 C3 Pub C1 FB FB FB C1 C2 C3 Pub C2 Sleep等。这些随机状态的序列就是马尔可夫链/过程。

马尔可夫奖赏过程(Markov Reward Process)，即马尔可夫过程加上价值估计(value judgement)，即判断一个像上面一个特定的随机序列有多少累积reward，也就是计算出v(s)。它由[S,P,R,γ]组成，R表示估计价值，或者叫即刻价值(immediate reward)，它由当前的状态决定。然后复习下必要概念: 是t时刻之后未来执行一组action能够获得的reward，因未来具有不确定性，故加入一个γ∈[0,1]，其中：

我们知道，一个马尔科夫奖励过程中某一状态的价值函数为从该状态开始的马尔可夫链收获的期望：

先继续举出David Silver公开课中的例子，示意图如下。

可以看出比图1多了红色部分即R，但是R的取值只决定了immediate reward，在实际过程中肯定是需要考虑到后面步骤的reward才能确定当前的选择是否正确。而实际上v(s)由两部分组成，一个是immediate reward，一个是后续状态产生的discounted reward。由

这个推导过程相对简单，仅在导出最后一行时，将G(t+1)变成了v(S(t+1)) 。其理由是收获的期望等于收获的期望的期望。先说说贝尔曼（Bellman）方程：指是用动态规划（Dynamic Programming）解决这些数学最佳化方法能够达到最佳化的必要条件。

此方程把“决策问题在特定时间怎么的值”以“来自初始选择的报酬比从初始选择衍生的决策问题的值”的形式表示。下式是针对MRP的Bellman方程：

通过方程可以看出v(s)由两部分组成，一是该状态的即时奖励期望，即时奖励期望等于即时奖励，因为根据即时奖励的定义，它与下一个状态无关；另一个是下一时刻状态的价值期望，可以根据下一时刻状态的概率分布得到其期望。

如果用s’表示s状态下一时刻任一可能的状态，那么Bellman方程可以写成：

那么每一个状态下能得到的状态值函数取值或者说累积reward如下所示，即原来写着class、sleep状态的地方替换成了数字(这里假设γ=1γ=1)。可以从sleep状态出发，推导出每个状态的状态值函数取值，如右上角红色公式所示。最右的-23与-13，列出二元一次方程组即可求出。

上面的式子表明在遵循策略π时，状态s的价值体现为在该状态下遵循某一策略而采取所有可能行为的价值按行为发生概率的乘积求和。

下面的式子表明某一个状态下采取一个行为的价值，可以分为两部分：其一是离开这个状态的价值，其二是所有进入新的状态的价值于其转移概率乘积的和。

而将两个式子互相代入，可以得到如下的Bellman期望方程：

还是原来的例子，一个MDP的例子，箭头上的单词表示action，与MRP不同的是，这里给出的immediate reward是同时在某个状态s和某个动作a条件下，所以图中R不是只取决于s，而是取决于s和a。右上角的等式表达出了这一个状态的状态值函数求解过程。

然后由于策略是pi(a|s)是可以改变的，因此两个值函数的取值不像MRP一样是固定的，而是能从不同的取值中找到一个最大值即最优值函数。而我们的目的是为了得到最优策略，这里先提一下相关必要定理：

（1）所有的最优策略有相同的最优价值函数，也就是找到最优值函数，也就能对应找到最好策略。
（2）存在至少一个最优策略，比任何其他策略更好，而且所有的最优策略具有相同的行为价值函数。

同样的，第一个式子说明一个状态的最优价值等于从该状态出发采取的所有行为产生的行为价值中最大的那个行为价值：

第二个式子说明在某个状态s下，采取某个行为的最优价值由2部分组成，一部分是离开状态 s 的即刻奖励，另一部分则是所有能到达的状态 s’ 的最优状态价值按出现概率求和。

同非最优方程类似，有以下Bellman优化方程：

最后，注意Bellman最优方程是非线性的，没有固定的解决方案，通过一些迭代方法来解决：价值迭代、策略迭代、Q学习、Sarsa等。后面会讲。

动态规划是什么？为什么可以利用动态规划来解决MDP？

动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。

在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，而最后一个子问题就是初始问题的解。简单来说，动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

举一个动态规划中简单又经典的例子：

给定一个数列，长度为N，求这个数列的最长上升（递增）子数列（LIS）的长度.比如5，3，4，8，6，7为例。答案是这个数列的最长递增子数列是 3,4,6,7，长度为4.

但是怎么求，可能比较短的数列是比较好求的，（一眼就可以看出），但是当数列很长之后，问题也就变得复杂了，下面我们用动态规划的思想去求解：

我们先重新定义问题：定一个数列，长度为N，设为：以数列中第k项结尾的最长递增子序列的长度.求中的最大值.按照这样的定义方式，然后再用递推的方式求解，如下所示：

前1个数的LIS长度d(1)=1(序列：5)
前2个数的LIS长度d(2)=1(序列：3或者5)，这个依赖前1个数的解
前3个数的LIS长度d(3)=2(序列：3，4)，这个依赖前2个数的解
前4个数的LIS长度d(4)=3(序列：3，4，8；) ，这个依赖前3个数的解
....
最后得答案前6个数的最长递增子数列是 3,4,6,7，长度为4.

注意：这个例子的求解中重新定义问题的方式有很多种，上面只是其中一种，而动态规划的核心也如何拆分和重新定义问题，然后用递推（或者说分治）的方式去解决。

怎么利用动态规划来解决MDP？首先，从上文可以总结出利用动态规划可以解决的问题需要满足两个条件：（1）整个优化问题可以分解为多个子优化问题，并且解决了所有子问题后表示原问题也已经解决（2）子优化问题的解可以被存储和重复利用。

然后，对应我们之前讲的MDP，我们先定义两个概念：

对于预测，不使用直接求解的方式，因为复杂度太高或不能直接求解，我们发现是可以把整个问题分成每一次对整体的环境遵循一次给定策略执行来更新的。也就是说，整个预测的问题可以分解成多个子问题，

符合条件（1），然后我们可以把上一次执行策略后得到的值函数的值储存并作为已知条件给下一次执行策略的计算值函数。这个符合上面的条件（2）。也就是说，对于预测，我们是可以用动态规划解决的。

对于控制，同预测一样，也是在动态规划的基础上，分为两种方式，分别为策略迭代：寻找最优策略问题则先在给定或随机策略下计算状态价值函数，根据状态函数贪婪更新策略，多次反复找到最优策略；价值迭代：单纯使用价值迭代，全程没有策略参与也可以获得最优策略，但需要知道状态转移矩阵，即状态s在行为a后到达的所有后续状态及概率。而具体公式如下：

以上是利用动态规划的思想来解决基于模型的强化学习，也就是说是已知的，但通常实际情况中，更多的是无模型的，也就是不清楚做出了某个action之后会变到哪一个state也不知道这个action好还是不好，都是未知的，那无模型的怎么解决呢？敬请期待下期！

人工智能赛博物理操作系统

AI-CPS OS

“人工智能赛博物理操作系统”（新一代技术+商业操作系统“AI-CPS OS”：云计算+大数据+物联网+区块链+人工智能）分支用来的今天，企业领导者必须了解如何将“技术”全面渗入整个公司、产品等“商业”场景中，利用AI-CPS OS形成数字化+智能化力量，实现行业的重新布局、企业的重新构建和自我的焕然新生。

AI-CPS OS的真正价值并不来自构成技术或功能，而是要以一种传递独特竞争优势的方式将自动化+信息化、智造+产品+服务和数据+分析一体化，这种整合方式能够释放新的业务和运营模式。如果不能实现跨功能的更大规模融合，没有颠覆现状的意愿，这些将不可能实现。

领导者无法依靠某种单一战略方法来应对多维度的数字化变革。面对新一代技术+商业操作系统AI-CPS OS颠覆性的数字化+智能化力量，领导者必须在行业、企业与个人这三个层面都保持领先地位：

重新行业布局：你的世界观要怎样改变才算足够？你必须对行业典范进行怎样的反思？
重新构建企业：你的企业需要做出什么样的变化？你准备如何重新定义你的公司？
重新打造自己：你需要成为怎样的人？要重塑自己并在数字化+智能化时代保有领先地位，你必须如何去做？

AI-CPS OS是数字化智能化创新平台，设计思路是将大数据、物联网、区块链和人工智能等无缝整合在云端，可以帮助企业将创新成果融入自身业务体系，实现各个前沿技术在云端的优势协同。AI-CPS OS形成的数字化+智能化力量与行业、企业及个人三个层面的交叉，形成了领导力模式，使数字化融入到领导者所在企业与领导方式的核心位置：

精细：这种力量能够使人在更加真实、细致的层面观察与感知现实世界和数字化世界正在发生的一切，进而理解和更加精细地进行产品个性化控制、微观业务场景事件和结果控制。
智能：模型随着时间（数据）的变化而变化，整个系统就具备了智能（自学习）的能力。
高效：企业需要建立实时或者准实时的数据采集传输、模型预测和响应决策能力，这样智能就从批量性、阶段性的行为变成一个可以实时触达的行为。
不确定性：数字化变更颠覆和改变了领导者曾经仰仗的思维方式、结构和实践经验，其结果就是形成了复合不确定性这种颠覆性力量。主要的不确定性蕴含于三个领域：技术、文化、制度。
边界模糊：数字世界与现实世界的不断融合成CPS不仅让人们所知行业的核心产品、经济学定理和可能性都产生了变化，还模糊了不同行业间的界限。这种效应正在向生态系统、企业、客户、产品快速蔓延。

AI-CPS OS形成的数字化+智能化力量通过三个方式激发经济增长：

创造虚拟劳动力，承担需要适应性和敏捷性的复杂任务，即“智能自动化”，以区别于传统的自动化解决方案；
对现有劳动力和实物资产进行有利的补充和提升，提高资本效率；
人工智能的普及，将推动多行业的相关创新，开辟崭新的经济增长空间。

给决策制定者和商业领袖的建议：

超越自动化，开启新创新模式：利用具有自主学习和自我控制能力的动态机器智能，为企业创造新商机；
迎接新一代信息技术，迎接人工智能：无缝整合人类智慧与机器智能，重新
评估未来的知识和技能类型；
制定道德规范：切实为人工智能生态系统制定道德准则，并在智能机器的开
发过程中确定更加明晰的标准和最佳实践；
重视再分配效应：对人工智能可能带来的冲击做好准备，制定战略帮助面临
较高失业风险的人群；
开发数字化+智能化企业所需新能力：员工团队需要积极掌握判断、沟通及想象力和创造力等人类所特有的重要能力。对于中国企业来说，创造兼具包容性和多样性的文化也非常重要。

子曰：“君子和而不同，小人同而不和。” 《论语·子路》云计算、大数据、物联网、区块链和人工智能，像君子一般融合，一起体现科技就是生产力。

如果说上一次哥伦布地理大发现，拓展的是人类的物理空间。那么这一次地理大发现，拓展的就是人们的数字空间。在数学空间，建立新的商业文明，从而发现新的创富模式，为人类社会带来新的财富空间。云计算，大数据、物联网和区块链，是进入这个数字空间的船，而人工智能就是那船上的帆，哥伦布之帆！

新一代技术+商业的人工智能赛博物理操作系统AI-CPS OS作为新一轮产业变革的核心驱动力，将进一步释放历次科技革命和产业变革积蓄的巨大能量，并创造新的强大引擎。重构生产、分配、交换、消费等经济活动各环节，形成从宏观到微观各领域的智能化新需求，催生新技术、新产品、新产业、新业态、新模式。引发经济结构重大变革，深刻改变人类生产生活方式和思维模式，实现社会生产力的整体跃升。