强化学习算法初探

专家审核：石海龙

或许很多人知道机器学习是因为强化学习，因为阿尔法狗的一战成名。本文对强化学习进行了入门级的介绍，全文数学公式不多给，估计阅读时间13分钟

强化学习(Reinforcement Learning)是机器学习中的一个领域，强调如何基于环境而行动，以取得最大化的预期利益。其灵感来源于心理学中的行为主义理论，即智能体如何在环境给予的奖励或惩罚的刺激下，逐步形成对刺激的预期，产生能获得最大利益的习惯性行为。就像婴儿学习一样，刚开始脑袋里一点想法什么都没有，通过不断的尝试，从错误中学习，找到规律，最终达到目标的方法。本文将从以下几个方面简要介绍强化学习:

与监督学习非监督学习的区别

基本要素和马尔可夫决策过程

状态价值函数和动作价值函数

最优策略

强化学习的分类

一 与监督学习非监督学习的区别

强化学习既然是机器学习的一种，它与监督学习，非监督学习之间的关系可以用下图简单描述。

它们之间的区别在于：

与非监督学习的区别：非监督式不是学习输入到输出的映射，而是模式的学习。例如向用户推荐新闻文章的任务中，非监督式学习会通过聚类找到用户先前已经阅读过类似的文章并向他们推荐其一。而强化学习将通过向用户先推荐少量的新闻，并不断获得来自用户的反馈，最后构建用户可能会喜欢的文章的“知识图”。

与监督学习的区别：监督式学习是需要大量已标记的数据来训练，所以黑白分明，非对即错，其准确度依赖于用于训练数据的标签的质量。而强化学习，没有一个明确的规定说这个行动是绝对的对或者错，只有好与不好之分，好的话给你奖励(Reward)，越好奖励越高，坏的话给你惩罚(-Reward)，越坏惩罚越痛，它不是那么的黑白分明，是容许有灰度的存在。通过对结果是对是错的反馈，调整之前的行为，就这样不断地整，算法能够学习到在什么样的情况下，选择什么样的行为可以得到最好的结果。

除此之外，强化学习还有以下几个特点:

强化学习针对某个行动(输入数据项)的反馈有些是延迟的，有时候可能学习了很多步以后才知道以前的某一步的选择是好还是坏。

强化学习面对的输入总是与环境互动变化的，每当算法做出一个行为，它影响下一次决策的输入，整个过程是连续的(sequential)。

二 基本要素及马尔可夫决策过程

强化学习的基本场景可以由下图来描述，主要由Environment(环境), Agent(智能体), State (状态), Action(动作), Reward(奖励)等基本概念构成。

整个场景可以描述为一个马尔可夫决策过程(Markov Decision Process，简称MDP)，在马尔可夫决策过程中，智能体在环境中会做各种动作，环境会接受动作，并引起自身状态的变迁，同时给智能体以奖励或惩罚。智能体的目标就是使用一些策略，做合适的动作，最大化自身的收益。

MDP包括以下几个要素，即常说的五元组：

状态：所有状态的集合，记作S

动作：所有可能做出的动作的集合，记作A。动作和状态集合可以是离散，也可以是连续的实数，对于前者，动作和状态集合是有限集，对于后者，集合是无限集。

奖励：执行动作后，智能体可能受到的奖励，一般是一个实数，记作r，该奖励和当前状态、当前采取的动作以及下一时刻进入的状态有关。

时间:在每个时间点t(t=1,2,3 …)，智能体会发出一个动作，收到环境给的奖励，同时环境进入下一个状态。

状态转移：满足，也就是说，从当前状态到下一状态的转移，只与当前状态以及当前所采取的动作有关。这就是所谓的马尔可夫性。智能体从某一初始状态开始，在每个时刻t，选择执行一个动作a，之后进入下一个状态, 环境给出奖励值，如此反复，可表示为:,其中有一种特殊的状态称为终止状态(也称吸收状态)，到达该状态后不会再进入其他后续状态。

马尔可夫决策过程举例

假设有个3*3的棋盘，如下图所示，编号从A到I，I为终点，现在我们要以任意一个位置为起点，走到终点。

根据问题表述，得知状态有9种，即当前所处的位置，其中I为终止状态，于是可得状态集合为：S=。

在每个状态可以执行的动作有4种：上、下、左、右移动，可得动作集合为：A=。

无论在什么位置，执行一个动作后下一步的位置是确定的，因此状态转移概率p为1，假定每移动一步得到的回报是0，到达终点后的回报值为100，用马尔可夫决策过程表示上面问题，可得下图

智能体要做的就是通过在环境中，不断地尝试学到一个策略π，根据这个策略，在状态s下就能得知要执行一个动作a=π(s)，最大化累计收益。比如在F状态，知道往下走能走到终点I

长期回报奖赏有多种计算方式，常用的是：

其中是折扣因子，是 [0,1] 区间的一个数。

在每个时刻 t 执行完动作，得到的奖励是，使用折扣因子是因为未来具有更大的不确定性，所以奖励值要随着时间衰减折扣越小。越大，折扣越小，意味着智能体更关心长期奖励，另一方面，越小，折扣越大的，意味着智能体更关心短期奖励。

三 状态价值函数和动作价值函数

类似监督学习中需要定义损失函数来评价预测函数的优劣，在强化学习中，也需要对策略函数的优劣进行评价，为此定义了状态价值函数和动作价值函数。

状态价值函数

智能体在某个状态s下，按照策略π执行动作，累计回报的数学期望，衡量按照某一策略执行之后的累计回报。计算公式为

函数的自变量是状态与策略函数，将它们映射成一个实数，每个状态的价值函数依赖于从该状态执行动作后能到达的后续状态的价值函数。在状态s下执行动作π(s),下一个时刻的的状态是不确定的，进入每个状态的概率是，当前获得的回报是，因此对下个时刻的所有状态求数学期望，即概率意义上的均值，而总的回报包括当前回报和后续时刻的回报值之和，R(s)表示当前时刻获得的回报。

动作价值函数

智能体在状态s下，按照策略π执行具体动作a后的预期回报，衡量的是按照某个策略，在某个状态时执行各种动作的价值。计算公式为

动作价值函数除了指定初始状态s与策略π外，还制定了在当前的状态s时执行的动作a。这个函数衡量的是按照某一策略，在某一状态时执行各种动作的价值。这个值等于在当前状态s下，执行一个动作后的立即回报，以及在下一个状态时按照策略π执行所得的状态价值函数之和，也要对状态转移概率求数学期望。

状态价值函数和动作价值函数的计算公式为贝尔曼方程，这是马尔可夫决策过程的核心。

四 最优策略

强化学习需要得到最优策略，根据状态价值函数和动作价值函数计算函数值，根据算出的函数值对策略的优劣进行排序。对两个不同的策略π和π’，任意状态都有，则称策略π优于π’。

根据最优策略的定义和性质，马尔可夫决策过程的优化目标如下：

即寻找任意状态s的最优策略函数。

找到了最优价值函数，根据它就可以得到最优策略，就是在每个状态执行动作价值函数最大的那个动作，表示为：

其中所有的最优策略有相同的状态价值函数和动作价值函数值。

五 强化学习算法分类

(一) 根据最优化问题求解算法分类

最优化问题的求解目前有3种主流方法，分别为动态规划算法、蒙特卡洛算法和时序分差算法。

1.动态规划算法

通过求解子问题的最优解得到整个问题的最优解，基本原理是如果要保证一个解全局最优，则每个子问题的解也是要最优的。包括价值迭代算法和策略迭代算法，但策略迭代算法和价值迭代算法虽然都可以得到理论上的最优解，但计算过程依赖于事前知道状态转移概率和立即回报值。而实际很多次场景中，无法得到状态转移概率和立即回报值。

对无法精确建立环境模型的问题，只能根据一些状态、动作、回报值序列进行计算，估计出价值函数和最优策略，基本思想是按照某种策略随机执行不同的动作，观察得到的回报，然后进行改进，即通过随机试探来学习。下面的蒙特卡洛和时序差分算法就是随机方法的典型代表。

2.蒙特卡洛算法

蒙特卡洛算法通过使用随机数来近似求解某些难以直接求解的问题，在强化学习中，可以根据样本得到状态价值函数和动作价值函数的估计值，用来计算近似它们的数学期望值。

3.时序差分算法

蒙特卡洛算法需要使用完整的片段进行计算，而实际情况中可能无法得到完整片段，比如没有终止状态的问题，时序差分算法基于蒙特卡洛算法进行改进，执行完一个动作之后就进行价值函数估计，无需使用包括终止状态的完整片段。

(二) 其他分类

Model-free：不尝试去理解环境, 环境给什么就是什么，一步一步等待真实世界的反馈, 根据反馈采取下一步行动。

Model-based：先理解真实世界是怎样的, 并建立一个模型来模拟现实世界的反馈，通过想象来预判接下来将要发生的所有情况，然后选择这些想象情况中最好的那种，并依据这种情况来采取下一步的策略。它比 Model-free 多出了一个虚拟环境，还有想象力。

Policy based：通过感官分析所处的环境, 直接输出下一步要采取的各种动作的概率, 然后根据概率采取行动，每种行动都有可能被选中，只是可能性不同。

Value based：输出的则是所有动作的价值，我们会根据最高价值来选择动作，相比基于概率的方法，基于价值的决策部分更为铁定，毫不留情，就选价值最高的，而基于概率的，即使某个动作概率最高，也不一定选中它。

结合两者的优势，创造一个很牛的算法Actor-Critic，其中Actor会基于概率做出动作，Critic会根据做出的动作给出价值。

Monte-carlo update：游戏开始后, 要等待游戏结束, 再总结这一回合中的所有转折点, 之后更新行为准则。

Temporal-difference update：在游戏进行中每一步都在更新, 不用等待游戏的结束, 这样就能边玩边学习了。因为单步更新更有效率，所以现在大多数方法都是单步更新。

On-policy：必须本人在场, 并且一定是本人边玩边学习。

Off-policy：也是从过往经验中学习，但这些过往经验没有必须是自己的经历，任何人的经历都可以被学习，或者也不用边玩边学，可以白天储存下来玩耍时的记忆，等到晚上通过离线学习来学习白天的记忆。可以选择自己玩, 也可以选择看着别人玩, 通过看别人玩来学习别人的行为准则。

下图是各类强化学习算法根据不同分类的统计：

以上内容就是强化学习算法初探，之后ARGO会深入探讨每种算法。

参考资料：

https://zhuanlan.zhihu.com/p/26608059

谢谢大家关注我们的公众号，新年开工，祝大家开工大吉！