1. 强化学习简介

在机器学习领域，有一类很重要的任务：序列决策（Sequential Decision Making）。这类任务和预测任务不同，它需要我们的智能体作出决策，决策就会带来后果，而负责决策的智能体需要为这个后果负责，根据这一系列的“后果”在未来的时间里进一步作出决策，再为未来的后果负责，如此循环往复。相比而言，预测任务仅针对输入数据产生一个预测信号，并希望预测信号与未来产生的实际信号一致，而不会直接对未来情况发生改变。

所以传统的解决预测任务的机器学习技术不能解决序列决策的问题，强化学习正是为了解决序列决策问题而生。

1.1 什么是强化学习

强化学习是通过机器与环境交互来达成目标的一种计算方法。机器（Agent）在环境的一个状态下做一个动作决策，把这个动作作用到环境当中，这个环境发生相应的改变并且将相应的奖励反馈和下一轮状态传回机器。这种交互是迭代进行的，机器的目标是最大化在多轮交互过程中获得的累积奖励的期望。相比于有监督学习中的“模型”，强化学习中的“智能体”强调机器不但可以感知周围的环境信息，还可以通过做决策来直接改变这个环境，而不只是给出一些预测信号。

这里有三个关键要素，感知、决策和奖励

感知。智能体在某种程度上感知环境的状态，从而知道自己所处的现状。例如，下围棋的智能体感知当前的棋盘情况；无人车感知周围道路的车辆、行人和红绿灯等情况；

智能体根据当前的状态计算出达到目标需要采取的动作的过程叫作决策。例如，针对当前的棋盘决定下一颗落子的位置；针对当前的路况，无人车计算出方向盘的角度和刹车、油门的力度。策略是智能体最终体现出的智能形式，是不同智能体之间的核心区别。

奖励。环境根据状态和智能体采取的动作，产生一个标量信号作为奖励反馈。这个标量信号衡量智能体这一轮动作的好坏。例如，围棋博弈是否胜利；无人车是否安全、平稳且快速地行驶；机器狗是否在前进而没有摔倒。最大化累积奖励期望是智能体提升策略的目标，也是衡量智能体策略好坏的关键指标。

这三个要素可以分别对应到后面要介绍的强化学习任务三大重要环节：感知--状态空间、决策--动作空间、奖励--奖励函数。

1.2 强化学习的目标

从上面的分析可以看出，强化学习就是在与环境的交互中通过一系列决策来达成某个目标。这里的目标应该如何刻画？

智能体和环境每次进行交互时，环境会产生相应的奖励信号。这个奖励信号一般是诠释当前状态或动作的好坏的及时反馈信号，好比在玩游戏的过程中某一个操作获得的分数值。整个交互过程的每一轮获得的奖励信号可以进行累加，形成智能体的整体回报（return），好比一盘游戏最后的分数值。因此，在强化学习中，我们关注回报的期望，并将其定义为价值（value），这就是强化学习中智能体学习的优化目标。

也就是说，强化学习的目标，总是希望能找到一个策略，在给策略下期望回报被最大化。在这一点上，与有监督的学习是一致的，都是在某个分布下优化某个目标的期望，但优化的途径不同，这一点会在后面的分析中体现出来。

1.3 强化学习的数据

在数据层面上，强化学习与有监督的学习有比较明显的差异。

有监督的学习有一个非常重要的假设——所有的训练样本都是从某个数据分布上独立同分布采样得到的，通过优化训练集上的目标函数获得最优模型参数，并且假设未来要预测的数据也是同一个分布采样而来的。

而在强化学习中，数据是由智能体与环境交互采样得到的，如果智能体不采取某个动作，那么这个动作和对应的状态就永远无法被观测到，所以当前智能体的训练数据来自之前智能体的决策结果。因此，智能体的策略不同，与环境交互所产生的数据分布就不同。

所以，从数据层面来说强化学习和有监督学习有着本质的不同

强化学习的策略在训练中会不断更新，智能体看到的数据分布是随着智能体的学习而不断发生改变的。

由于奖励建立在状态动作对之上，因此寻找最优策略对应着寻找最优数据分布。

1.4 与有监督学习的区别

根据上面的介绍，我们可以总结一下强化学习和一般的有监督学习的区别。

对于一般的有监督学习任务，我们的目标是找到一个最优的模型参数，使其在训练数据集上最小化一个给定的损失函数。在训练数据独立同分布的假设下，这个优化目标表示最小化模型在整个数据分布上的泛化误差，给定目标函数L和待优化模型参数w：

对比发现，一般有监督学习和强化学习范式的区别：

一般的有监督学习关注寻找一个模型，使其在给定数据分布下得到的损失函数的期望最小；

强化学习关注寻找一个智能体策略，使其在与动态环境交互的过程中产生最优的数据分布，最大化该分布下给定奖励函数的期望。

总之，强化学习与有监督学习有相似之处，但在大多数情况下，两者虽然同属机器学习的范畴，强化学习表现出了与一般有监督学习不同的思维模式和学习范式，强化学习任务往往更困难，因为一旦策略改变，数据分布也随之改变，这种改变高度复杂，难以用数学公式来刻画。

2. 核心概念

强化学习与其他学习范式有所区别的一个重要特征：它需要用到那些对采取的动作进行评估的信息而不仅仅只是给出一个指导性的信号，这就要求主动探索（Exploration）来寻找好的动作，当某些状态的价值很明确时，就可以对学习到的信息进行利用（Exploitation）。何时应该探索，又何时应该利用，这是强化学习的经典问题。

2.1 探索与利用——多臂老虎机（MAB）

在多臂老虎机（multi-armed bandit，MAB）问题中，有一个拥有K 根拉杆的老虎机，拉动每一根拉杆都对应一个关于奖励的概率分布R。我们每次拉动其中一根拉杆，就可以从该拉杆对应的奖励概率分布中获得一个奖励 。我们在各根拉杆的奖励概率分布未知的情况下，从头开始尝试，目标是在操作若干次拉杆后获得尽可能高的累积奖励。由于奖励的概率分布是未知的，因此我们需要在“探索拉杆的获奖概率”和“根据经验选择获奖最多的拉杆”中进行权衡。“采用怎样的操作策略才能使获得的累积奖励最高”便是多臂老虎机问题。

我们这里假设一种简单的多臂老虎机：拉动每根拉杆的奖励服从伯努利分布（Bernoulli distribution），即每次拉下拉杆有的p概率获得的奖励为 1，有1-p的概率获得的奖励为 0。奖励为 1 代表获奖，奖励为 0 代表没有获奖。

2.1.1 形式化描述

2.1.2 估计累计期望值

2.2 探索与利用的平衡——经典算法

我们现在已经将MAB问题定义清楚并且知道如何估计一台老虎机的期望奖励，但是仍然不知道该如何采取行动。

一个最简单的策略就是一直采取第一个动作，但这就非常依赖运气的好坏。如果运气绝佳，可能拉动的刚好是能获得最大期望奖励的拉杆，即最优拉杆；但如果运气很糟糕，获得的就有可能是最小的期望奖励，所以我们需要在探索与利用中权衡。

探索（exploration）是指尝试拉动更多可能的拉杆，这根拉杆不一定会获得最大的奖励，但这种方案能够摸清楚所有拉杆的获奖情况。对于一个 10 臂老虎机，我们要把所有的拉杆都拉动一下才知道哪根拉杆可能获得最大的奖励。

利用（exploitation）是指拉动已知期望奖励最大的那根拉杆，由于已知的信息仅仅来自有限次的交互观测，所以当前的最优拉杆不一定是全局最优的。例如，对于一个 10 臂老虎机，我们只拉动过其中 3 根拉杆，接下来就一直拉动这 3 根拉杆中期望奖励最大的那根拉杆，但很有可能期望奖励最大的拉杆在剩下的 7 根当中，即使我们对 10 根拉杆各自都尝试了 20 次，发现 5 号拉杆的经验期望奖励是最高的，但仍然存在着微小的概率—另一根 6 号拉杆的真实期望奖励是比 5 号拉杆更高的。

于是在多臂老虎机问题中，设计策略时就需要平衡探索和利用的次数，使得累积奖励最大化。一个比较常用的思路是在开始时做比较多的探索，在对每根拉杆都有比较准确的估计后，再进行利用。目前已有一些比较经典的算法来解决这个问题，例如\epsilon-贪婪算法、上置信界算法和汤普森采样算法等，我们接下来将分别介绍这几种算法。

2.2.2 上置信限算法

设想这样一种情况：对于一台双臂老虎机，其中第一根拉杆只被拉动过一次，得到的奖励为0 ；第二根拉杆被拉动过很多次，我们对它的奖励分布已经有了大致的把握。这时你会怎么做？或许你会进一步尝试拉动第一根拉杆，从而更加确定其奖励分布。这种思路主要是基于不确定性，因为此时第一根拉杆只被拉动过一次，它的不确定性很高。一根拉杆的不确定性越大，它就越具有探索的价值，因为探索之后我们可能发现它的期望奖励很大。

因此，设定一个概率p后，就可以计算相应的不确定性度量了，更直观地说，UCB 算法在每次选择拉杆前，先估计每根拉杆的期望奖励的上界，使得拉动每根拉杆的期望奖励只有一个较小的概率超过这个上界，接着选出期望奖励上界最大的拉杆，从而选择最有可能获得最大期望奖励的拉杆。

2.2.3 汤普森采样算法

MAB 中还有一种经典算法——汤普森采样（Thompson sampling），先假设拉动每个动作的奖励服从一个特定的概率分布（先验分布），然后根据拉动每根拉杆的期望奖励来进行选择。但是由于计算所有拉杆的期望奖励的代价比较高，汤普森采样算法使用采样的方式，即根据当前每个动作 a的奖励概率分布进行一轮采样，得到一组各根拉杆的奖励样本，再选择样本中奖励最大的动作。可以看出，汤普森采样是一种计算所有拉杆的最高奖励概率的蒙特卡洛采样方法。

所以，在这样的数据下，动作a后验的奖励分布服从Beta分布，对每一个动作都这样做，就得到每个动作的后验概率分布，汤普森采样法从后验概率分布中采样最大获奖概率的动作。

2.2.4 小结

探索与利用是与环境做交互学习的重要问题，是强化学习试错法中的必备技术，而多臂老虎机问题是研究探索与利用技术理论的最佳环境。

多臂老虎机问题与强化学习的一大区别在于其与环境的交互并不会改变环境，即多臂老虎机的每次交互的结果和以往的动作无关，所以可看作无状态的强化学习（stateless reinforcement learning）。下面我们将开始在有状态的环境下讨论强化学习，并且介绍强化学习的核心概念马尔可夫决策过程。

2.3 马尔可夫决策过程(MDP)

与多臂老虎机问题不同，马尔可夫决策过程包含状态信息以及状态之间的转移机制。如果要用强化学习去解决一个实际问题，第一步要做的事情就是把这个实际问题抽象为一个马尔可夫决策过程，也就是明确马尔可夫决策过程的各个组成要素。

2.3.1 随机过程

随机过程（stochastic process）是概率论的“动力学”部分。概率论的研究对象是静态的随机现象，而随机过程的研究对象是随时间演变的随机现象（例如天气随时间的变化、城市交通随时间的变化）。

2.3.2 马尔可夫性质

需要明确的是，具有马尔可夫性并不代表这个随机过程就和历史完全没有关系。因为虽然t+1时刻的状态只与时刻t的状态有关，但是时刻t的状态其实包含了时刻t-1的状态的信息，通过这种链式的关系，历史的信息被传递到了现在。马尔可夫性可以大大简化运算，因为只要当前状态可知，所有的历史信息都不再需要了，利用当前状态信息就可以决定未来。

2.3.3 马尔可夫过程

2.3.4 马尔可夫奖励过程

2.3.5 马尔可夫决策过程

我们发现 MDP 与 MRP 非常相像，主要区别为 MDP 中的状态转移函数和奖励函数都比 MRP 多了动作作为自变量。注意，在上面 MDP 的定义中，我们不再使用类似 MRP 定义中的状态转移矩阵方式，而是直接表示成了状态转移函数。这样做

因为此时状态转移与动作也有关，变成了一个三维数组，而不再是一个矩阵（二维数组）；

因为状态转移函数更具有一般意义，例如，如果状态集合不是有限的，就无法用数组表示，但仍然可以用状态转移函数表示。我们在之后的课程学习中会遇到连续状态的 MDP 环境，那时状态集合都不是有限的。

不同于MRP，在MDP中，通常存在一个智能体来执行动作。例如，一艘小船在大海中随着水流自由飘荡的过程就是一个马尔可夫奖励过程，它如果凭借运气漂到了一个目的地，就能获得比较大的奖励；如果有个水手在控制着这条船往哪个方向前进，就可以主动选择前往目的地获得比较大的奖励。

我们同样可以对MDP构造对于的价值函数，由于动作空间的存在，和MRP的价值函数有所不同。

首先定义策略，智能体根据当前状态从动作的集合中选择一个动作的函数，被称为策略。

2.4 贝尔曼方程

贝尔曼方程是目前强化学习的灵魂，具有核心地位，所有的强化学习算法，本质上都是用各种不同的方式在求解贝尔曼方程。

2.5 小结

马尔可夫决策过程是强化学习中的重要概念，强化学习中的环境就是一个马尔可夫决策过程。我们接下来将要介绍的强化学习算法通常都是在求解马尔可夫决策过程中的贝尔曼方程。

3. 动态规划算法

回忆贝尔曼方程的形式，我们发现估计当前状态或动作的价值函数，需要依赖下一状态的状态或价值函数，也就是说将当前价值函数作为目标问题，那么估计下一状态的价值函数可以看作子问题，一旦获得子问题的解，目标问题的就能求解了，这就是动态规划算法的思想。

3.1 策略迭代算法

策略迭代由两部分组成：策略评估（policy evaluation）和策略提升（policy improvement）。具体来说，策略迭代中的策略评估使用贝尔曼期望方程来得到一个策略的状态价值函数，这是一个动态规划的过程，然后根据更新后的状态价值函数更新更好的策略。

3.1.1 策略评估

3.1.2 策略提升

3.1.3 策略迭代算法

我们把策略评估和策略提升组合起来，就得到策略迭代算法：对当前的策略进行策略评估，得到其状态价值函数，然后根据该状态价值函数进行策略提升以得到一个更好的新策略，接着继续评估新策略、提升策略……直至最后收敛到最优策略。

3.2 价值迭代

策略迭代中的策略评估需要进行很多轮才能收敛得到某一策略的状态函数，这需要很大的计算量，尤其是在状态和动作空间比较大的情况下。我们是否必须要完全等到策略评估完成后再进行策略提升呢？

这其实就是将要讲的价值迭代算法，它可以被认为是一种策略评估只进行了一轮更新的策略迭代算法。需要注意的是，价值迭代中不存在显式的策略，我们只维护一个状态价值函数。

价值迭代可以看成一种动态规划过程，它利用的是贝尔曼最优方程：

3.3 小结

策略迭代算法和价值迭代算法都能用于求解最优价值和最优策略。动态规划的主要思想是利用贝尔曼方程对所有状态进行更新。

在利用贝尔曼方程进行状态更新时，我们会用到马尔可夫决策过程中的奖励函数和状态转移函数，也就是我们上期提到的model-based基于模型的强化学习算法。

如果智能体无法事先得知奖励函数和状态转移函数，就只能通过和环境进行交互来采样（状态-动作-奖励-下一状态）这样的数据，我们在之后的章节中讲解如何求解这种情况下的最优策略。

4. 蒙特卡洛和时序差分

动态规划算法要求马尔可夫决策过程是已知的，即要求与智能体交互的环境是完全已知的（例如迷宫或者给定规则的网格世界）。

在此条件下，智能体其实并不需要和环境真正交互来采样数据，直接用动态规划算法就可以解出最优价值或策略。

这就好比对于有监督学习任务，如果直接显式给出了数据的分布公式，那么也可以通过在期望层面上直接最小化模型的泛化误差来更新模型参数，并不需要采样任何数据点。

但这在大部分场景下并不现实，机器学习的主要方法都是在数据分布未知的情况下针对具体的数据点来对模型做出更新的。对于大部分强化学习现实场景（例如电子游戏或者一些复杂物理环境），其马尔可夫决策过程的状态转移概率是无法写出来的，也就无法直接进行动态规划。在这种情况下，智能体只能和环境进行交互，通过采样到的数据来学习，这类学习方法统称为无模型的强化学习（model-free reinforcement learning）。

4.1 蒙特卡洛方法

蒙特卡洛方法（Monte-Carlo methods）也被称为统计模拟方法，是一种基于概率统计的数值计算方法。运用蒙特卡洛方法时，我们通常使用重复随机抽样，然后运用概率统计方法来从抽样结果中归纳出我们想求的目标的数值估计。一个简单的例子是用蒙特卡洛方法来计算圆的面积。

将蒙特卡洛方法运用到估计状态价值函数上，一个很直观的想法就是用策略\pi在 MDP 上采样很多条序列，计算从这个状态出发的回报再求其期望就可以了

4.2 时序差分

时序差分(Temperal Difference)是一种用来估计一个策略的价值函数的方法，它结合了蒙特卡洛和动态规划算法的思想。时序差分方法和蒙特卡洛的相似之处在于可以从样本数据中学习，不需要事先知道环境；和动态规划的相似之处在于根据贝尔曼方程的思想，利用后续状态的价值估计来更新当前状态的价值估计。

4.2.1 时序差分算法

4.2.2 时序差分的优势

显然对比DP(动态规划)算法，不需要事先知道环境和转移概率，从采样中学习。

对比蒙特卡洛方法，时序差分是一种在线增量更新的学习方法，而蒙特卡洛方法需要等到整个采样过程(Episode)结束才能更新。

在学习开始之前，是否有必要等到最终结果已知？ 

每天下班回家前，你都会尝试预测回家需要多长时间。当你离开办公室时，你会记下时间，星期几，天气以及其他可能相关的内容。 这个星期五你正好在6点钟离开，你估计要回家需要30分钟。但是你陷入大规模的交通堵塞之中。 离开办公室后二十五分钟，你仍然在高速公路上等待。你现在估计还需要25分钟才能回家，共计50分钟。 当你在车流中等待时，你已经知道你最初估计的30分钟过于乐观了。 你必须等到回家才增加对初始状态的估计吗？

根据蒙特卡洛方法，你必须等到回家才增加对初始状态的估计，因为你还不知道真正的回报。

另一方面，根据TD方法，你可以立即学习，将初始估计值从30分钟上调到50分钟。

假设你有很多下班开车回家的经验。 然后你搬到一个新的建筑物和一个新的停车场（但你仍然在同一个地方进入高速公路）。现在你开始学习新建筑的预测。TD更新可能会好得多，至少收敛速度更快：你可以快速根据历史的经验随时调整对状态的估计，而不必等到回到家再更新。

5. 总结

这一期主要介绍了强化学习中基础思维和核心原理，并介绍了一些经典的算法来帮助理解，体会强化学习的思维模式。但是万变不离其宗，所有类型的强化学习算法都没有脱离这个思维框架。我们总结几个重要概念和重要组件，它们将贯穿后续整个强化学习领域的探索

马尔可夫决策过程

贝尔曼方程

探索和利用

动作、状态价值函数

时序差分

6. 参考文献

[1] GERAMIFARD A, WALSN T J, TELLEX S, et al. A tutorial on linear function approximators for dynamic programming and reinforcement learning [J]. Foundations and Trends®in Machine Learning, 2013, 6 (4): 375-451.

[2] SZEPESVÁRI C, LITTMAN M L. Generalized markov decision processes: dynamic-programming and reinforcement-learning algorithms [C]//International Conference of Machine Learning, 1996: 96.

[3] JAAKKOLA T, JORDAN M I, SINGH S P. On the convergence of stochastic iterative dynamic programming algorithms [J]. Neural Computation,1994, 6(6):1185–1201.