【干货】吴恩达博士论文：用增强学习做无人机

【新智元导读】吴恩达2003年申请加州大学伯克利分校计算机科学博士的毕业论文。该论文在肯定了增强学习取得的进展的基础上，就“回报函数塑造”（shaping reward）提出一种理论，具体来说，就是选择或者修正回报函数，以帮助算法进行学习。论文还提出了PEGASUS策略搜索方法。论文的最后，作者把这一理论和方法结合用于实践，控制无人机飞行。

论文关键词：回报函数塑造；策略搜索；增强学习；（部分可观察的）马尔科夫决策

增强学习中的回报函数塑造和策略搜索

作者：Andrew Y.Ng （吴恩达）

论文封面

摘要

增强学习为不确定条件中的连续决策提供了一套强大的工具。在这种情况下，算法要学会如何连续地做决策，并且算法的评价应该根据其所做选择的长期质量来进行。举一个具体的例子，想想无人机飞行所面临的难题：每不到一秒，算法都必须反复地选择最佳的行动控制。

对于增强学习来说，最核心的概念是回报函数。回报函数向处于学习过程中的算法显示哪一种状态是好的，哪一种状态是应该回避的。回报函数把学习任务具体化了。为了让增强学习算法在合理的时间内运行，会需要频繁地使用一个经过精心选择的回报函数，以为处于学习状态中的算法提供合适的“提示”。但是，对“提示”的选择，也就是所谓“塑造回报”（shaping rewards）的过程，通常要包含大量的试错，并且，被选中的塑造回报太差，通常会以一种难以预测的方式改变问题本身，导致算法会学到很差的解决方案。在本论文中，我们就“塑造回报”提出了一个理论，展示了这些问题该怎么消除。进一步看，这一理论为选择好的，也就是在实际上能显著地提升学习速度的“塑造回报”提供了指引。我们还展示了“塑造”可以允许我们使用“近视”学习算法，并且依然可以做得很好。

“维数灾难”指的是这样一种现象：许多简单的增强学习算法会随着问题的增加呈指数式的增长，具有稀疏性，这对许多应用来说并没有实际作用。在本论文中，我们考虑把策略搜索方法用于增强学习。我们希望从有限的控制器中为单个任务选择一个控制器。我们发现，在策略搜索中，一个关键的问题是，如何获得对被列入选择范围的控制器的统一的评价。我们发现，简单的蒙特卡洛方法从整体上不会给出答案。随后，我们提出PEGASUS策略搜索方法。

PEGASUS是在一种令人意外的观察中派生出来的，这种观察指的是，所有的增强学习问题都可以转化成一个合集，在这一个问题集中，所有的状态转换（考虑了当下的状态和行为）都是被预先决定的。我们发现，PEGASUS具有样本复杂性，可以根据问题的数量二项式地最大化增长，并且有力地保证了它找到的解决方案的质量。从这些结果延伸，我们还使用了VC维度和样本复杂性的概念，这两个概念是从监督式学习借鉴过来的，我们把它们运用到增强学习环境中，进而把这两个问题至于一个更加平等的背景下。

最后，我们用这些概念为无人机设计了一个控制器。无人机的控制一直被普遍地认为是一个难题。使用“塑造回报函数”和PEGASUS搜索策略方法，我们能够自动地设计出一个稳定的飞行控制器，并且在许多远程遥控直升机竞赛中进行试飞。

目录

论文目录

1、引言

1.1 介绍增强学习

1.2 增强学习与监督式学习的比较

1.3 论文大纲和贡献

2、增强学习和部分可观察马尔科夫决策（POMDPs）

2.1 马尔科夫决策过程

2.2 一些马尔科夫决策（MDPs）特性与算法

2.3 马尔科夫决策算法

2.4 部分可观察的马尔科夫决策过程

3、增强学习中的回报函数塑造（shaping）

3.1 变化中的回报函数

3.2 塑造回报

3.3 主要的塑造结果

3.4 试验

3.5 讨论

4、Pegasus：大型MDPs和POMDPs中的策略搜索方法

4.1 搜索策略

4.2 搜索策略框架

4.2.1 确定性模拟模型

4.2.2 搜索策略术

4.2.3 VC维度和复杂性

4.3 轨迹树

4.4 策略研究方法

4.4.1 (PO)MDPs的转化

4.4.2 PEGASUS：一种策略搜索方法

4.5 主要的理论结果

4.5.1 有限行动空间的例子

4.5.2有限行动空间的例子：“Simple”2 在统一聚合上效果很差的

4.5.3有限行动空间的例子中的统一聚合

4.6 实验

4.7 讨论和相关工作

5、通过增强学习实现的无人机

5.1 引言

5.2 模型定义

5.2.1 局部加权回归

5.2.2 模型选择和先验知识的融入

5.3 飞行学习

5.4 飞行比赛

6、结论

参考文献（略）

论文大纲和主要贡献

第一章是论文的引言部分，包括增强学习及其与监督式学习的比较。

第二章以把马尔科夫决策过程（MDPs）和部分可观察马尔科夫决策过程（POMDPs）正式框架化作为开始，我们还回顾了一些用于解决MDPs的标准算法，指出这些算法在什么时候运行得好，什么时候不好，并讨论了把这些算法延伸到更大的问题，或者POMDPs上时会遇到的困难。

第三章，我们描述了回报函数塑造。这指的是选择或者修正回报函数，以帮助算法进行学习。我们描述了在塑造的过程中，看起来很自然的尝试会怎样产生非常差的学习方案。同时，我们提出了一个关于塑造的理论，展示了这些问题该怎么消除。我们还为设计好的塑造函数提出了的指导规则，进而实际上能显著地加速学习过程。

第四章的开始，我们描述了策略搜索的框架，在这个框架中，我们把注意力聚集在MDPs可能的控制器中的一小部分，我们还提供了一个方法，以“再使用”数据，以评估和发现好的控制器。我们的方法在POMDPs上也运行得很好，并可以很好地延伸到大量的问题上：我们对所需要的数据量进行了限定，依靠的是精确的假设。这些数据要么是没有依赖性，要么是在问题的维度有最大的二项式依赖。

最后，第五章，我把这些概念设计了一个用于直升机飞行的控制器（如下图）。我们首先描述了系统的定义过程，在此，我们学习到了一个非线性的随机直升机动态模型。随后，我们运用了自己的学习算法，第一步是让无人机飞行，第二步是让它在遥控无人机竞赛中的挑战赛中飞行。

伯克利无人机

结论

近几年，增强学习方法在不确定环境中的控制和决策上取得了大量的成功。但是，增强学习算法在实际应用上依然还有许多问题。在本论文中，我们提出了一些用于增强学习的方法，希望能解决这些问题。

其中一个问题是任务描述的具体化，或回报函数。具体地说，塑造回报函数常被用于为学习算法提供必要的线索，让算法可以在合理的时间内学习。但是，在选择塑造回报函数时做得太糟，会导致算法学到的是非常差的策略，在这种情况下，从传统上看，一定数量的人为试错是很有必要的，以设计出更好的塑造回报函数。

在第三章中，我们强调了必要和有效条件，在这些情况下，回报函数的塑造可能会被证明是确保最优化的策略被学习的一个方法。我们的分析还为选择塑造回报函数给出了指导规则。随后，我们展示了塑造能够让算法使用在较少的平行时间内更好地学习，进而在某种程度上，正式地降低了（近视）算法中的增强学习问题的难度。塑造回报函数的提议在其它的一些难题上也展示了良好的效率。

在第四章中，我们思考了策略搜索的问题，并且看到，在策略搜索中的一个关键问题是如何获得对策略实用性的一个规范的、好的衡量方式。我们看到，简单的蒙特卡洛方法不能实现这些。我们也讨论了轨迹树的方法，这种方法可以获得统一的好的评价，但是，是在一个过高的（以指数方式增长）的计算消耗下完成的。随后，我们发现，所有的增强学习难题都能转化到一个种类，在这中间，所有的动态转换都是确定的。这被用于延伸PEGASUS算法，保证了对策略实用性的一致良好评价，并且拥有最多的二项式样本复杂性。在呈现这些结果的过程中，我们还使用了与VC维度相似的概念合成，以及把监督式学习环境中的样本复杂性运用于增强学习，进而把这两个问题置于一个更加平等的基础上。

轨迹树

PEGASUS策略的演进

第五章中，这些概念被统合于设计一个无人机控制器。直升机的自动控制被普遍地认为是一个具有挑战性的难题，但是使用这些算法，我们可以自动地设计出一个非常稳定的飞行控制器，在遥控直升机比赛中参加竞赛。

本论文还在增强学习和可适应性控制上做了一些基础的工作，给出建议的方向。其中还有许多紧要的问题需要解决，它们是：

• 回报函数的具体化（略）
• 安全性和稳定性（略）
• 多智能体系统（略）
• 无监督式学习（略）