论文导读：从强化学习到进化策略
机器之心报道
本文将由简单介绍几篇强化学习论文开始，并随后展示最新提出的进化策略。
Mnih 等人提出了四个强化学习方法的异步方法，包括 Q-learning、SARSA、n-step Q-learning、高级 actor-critic 算法。其中，异步的高级 actor-critic (A3C) 算法的表现最好。并行的执行器使用不同的探索策略来稳定训练过程，所以经历回放 (experience replay) 并没有被使用。与大多数深度学习算法不同，异步方法能够在单个多核 CPU 上运行。以 Atari 游戏为例，A3C 能够在更快的速度下，表现得与之前的算法旗鼓相当，甚至更好。A3C 在连续动态控制问题上也取得了成功：包括赛车游戏 TORCS、物理控制游戏 MujoCo、以及迷宫游戏 Labyrinth。在 Labyrinth 中，随机的 3D 迷宫直接通过视觉输入，每一个章节中，玩家都要面对全新的迷宫，因此该算法也需要学习一个能够探索随机迷宫的指导性战略。
论文链接：https://arxiv.org/pdf/1602.01783.pdf
这篇 Nature 论文可以说引爆了深度强化学习。它介绍了 Deep Q-Networks (DQN) 算法，并且在 49 个 Atari 游戏上取得了很好的性能：基本都超越了以前的算法，大部分比职业玩家要好。这一算法的突出贡献是，在 Q-learning 中引入了深度神经网络，并且通过 experience replay 和 target network 技术稳定学习过程。而在此之前，普遍认为非线性函数近似与 Q-learning 结合就会有不收敛等问题。DQN 使用了端到端机制：输入是游戏几帧的像素，输出是操作策略，中间不需要人为进行特征标记工程。更令人惊讶的是，它用一个神经网络结构，一套超参数设置，就可以玩好 49 个游戏。DQN算法出现之后，许多改进版本和其它Deep RL工作也相继出现。
论文地址：http://www.nature.com/nature/journal/v518/n7540/full/nature14236.html
摘要：
强化学习理论为动物行为提供了一个根植于心理学和神经科学视角的规范化解释，它告诉我们主体（agent）是如何优化他们对环境的控制。然而，为了在接近现实复杂性的情况下成功地使用强化学习，主体面临着一个艰巨的任务：他们必须从高维的感官输入的环境中获得有效的表征，并使用这些表征来将过去的经验应用到新的情境中。值得注意的是，人类和其他动物看起来已经通过结合强化学习和等级知觉处理系统解决了这个问题。人类身上体现出的强化学习理论被丰富的神经数据证实，这些神经数据揭示了多巴胺能神经元释放的相位信号与时域差分强化学习算法之间的显着相似之处。
虽然强化学习的主体已经在多个领域实现了一些成功，但是它们的应用一直局限于只能指定有用表征的领域，或者能被完全观察的低维状态空间中。我们使用了最近在神经元训练上取得了一些进展，开发出一个新型人工主体，称为 deep Q-network，它可以使用端到端的强化学习，直接从高维知觉输入中学习成功的策略。我们用经典 Atari2600 游戏中具有挑战性的领域测试了这个主体。我们证明，只接收像素和游戏得分作为输入的 deep Q-network 的表现，能超越之前所有算法，并在一组 49 场比赛中达到了相当于专业人类游戏测试者的水平。DQN 使用同样的算法、网络架构和超参数。这个成果在高维知觉输入和行为之间架起了一座桥梁，创造出了世界上第一个具备学习执行多元化的挑战任务能力的人工主体。
进化策略（ES：evolution strategy）是一种已存在了数十年的优化技术，其在现代强化学习基准（如 Atari/MuJoCo）上的表现可以比肩标准的强化学习技术，同时还能克服强化学习的许多不便。
特别的几点包括：进化策略的实现更加简单（不需要反向传播），更容易在分布式环境中扩展，不会受到奖励稀疏的影响，有更少的超参数。这个结果令人吃惊，因为进化策略就好像是在一个高维空间中简单地爬山，每一步都沿着一些随机的方向实现一些有限的差异。
我们的发现是这种已有数十年之久思想强大结果的现代延续。比如说，在 2012 年，AlexNet 论文表明可以如何设计、扩展和训练卷积神经网络（CNN）以在图像识别任务上实现极其优秀的结果，而那时候大多数研究者还认为 CNN 并不是一种有希望的计算机视觉技术。类似地，在 2013 年，深度 Q 学习（Deep Q-Learning）论文表明可以将 Q 学习与 CNN 结合起来以成功地解决 Atari 游戏，从而使强化学习（RL）发展成为了一个有激动人心的实验结果的研究领域，而不再只是理论构想了。同样，我们的研究也表明进化策略可以在强化学习基准上实现优秀的表现，从而消除了人们之前普遍认为的进化策略方法不能用于高维问题的观点。
进化策略易于实现和扩展。我们的实现运行在一个包含了 80 台机器和 1440 个 CPU 内核的计算集群上，其可以仅在 10 分钟内就训练出一个 3D MuJoCo 人形步行者（在 32 核上，A3C 需要大约 10 小时）。使用 720 核，我们也能在 Atari 上实现可与 A3C 媲美的表现，同时还能将训练时间从 1 天降低至 1 小时。
强化学习
首先让我们简单看看强化学习的工作方式。假设我们有一些环境（比如游戏），我们想要在其中训练一个代理。为了描述该代理的行为，我们要定义一个策略函数（policy function），这是该代理的大脑，用于计算该代理如何在一个给定的情形中采取行动。在实践中，这个策略通常是一个神经网络，其输入是该游戏的当前状态，然后计算可用的所有允许动作的概率。一个典型的策略函数可能有大约 1,000,000 个参数，所以我们的任务就是找到这些参数的确切配置，以使得该策略能够实现良好的表现（即在很多游戏中获胜）。
上图：在 Pong 游戏中，策略根据输入的屏幕像素来计算移动玩家拍子的概率（右边绿色的拍子）：上、下或不动。
该策略的训练过程如下所示。首先是一个随机初始化，我们让该代理与环境进行一阵交互，然后收集交互的「剧情（episode）」（比如，每个 episode 就是一局 Pong 游戏）。由此我们就能得到情况的完整记录：遇到了什么样的状态序列、在每个状态采取了什么动作、每一步的奖励如何。下图给出了一个例子，这三个 episode 每个都表示在一个假想环境中的 10 个时间步骤。其中每个矩形都是一个状态，如果奖励是正面的（比如把球击回给了对方），那么矩形就是绿色；如果奖励是负面的（比如没有接到球），那么矩形则为红色：
这幅图给出了改善策略的一个方法；导致绿色状态的行为是好的行为，导致红色的行为则很糟糕。然后我们可以使用反向传播来计算该网络参数的一次小的更新，该更新将使得未来的状态更有可能是绿色、更少可能是红色。我们预计更新后的策略会更好一点。然后我们迭代这一过程：收集另一批 episode，进行另一次更新…
通过在这些动作中注入噪声来进行探索。我们在强化学习中通常使用的策略是随机的，它们仅计算采取任何动作的概率。通过这种方法，代理可能会在训练过程中发现自己在不同时间处在同一个特定状态，而且由于采样的情况，它也将在不同的时间采取不同的动作。这能提供学习所需的信号：这些动作中有一些会导致好的结果，这些动作就会得到鼓励；另一些则不会奏效，就会被抑制。因此我们可以说，我们通过向代理的动作注入噪声而为其学习过程引入了探索（exploration）——我们可以通过在每个时间步骤从动作分布中采样来做到这一点。这与进化策略不同。
进化策略
关于「进化（Evolution）」。在我们探讨进化策略（ES）之前，有必要强调一下尽管这种方法名字中有「进化」这个词，但进化策略和生物进化关系不大。也许这项技术的早期版本从生物进化上获得了一些启发——在一定的抽象程度上，这种方法可被视为这样一个过程：从个体构成的群体中采样并让其中成功的个体引导未来后代的分布。但是，其数学细节在生物进化方法的基础上实现了很大的抽象，我们最好将进化策略看作是一类黑箱的随机优化技术。
黑箱优化。在进化策略中，让我们完全忘记代理、环境、涉及的神经网络和其中的交互吧。进化策略的整个设置就是一大堆数字输入（假设和前面提到的策略网络的参数数量一样，有 1,000,000 个数字），然后输出 1 个数字（对应总奖励），我们需要找到这 1,000,000 个数字的最好配置。在数学上，我们可以说是根据输入向量 w（该网络的参数/权重）来优化一个函数 f(w)，但我们不对 f 的结构做出任何假设，我们只能对其进行评估（因此被称为「黑箱」）。
进化策略算法。直观上来讲，这种优化就是一种「猜测然后检测」的过程，即我们从一些随机参数开始，然后重复执行以下过程：1）随机对该猜测进行一点调整，2）让我们的猜测向效果更好的方向移动一点。具体而言，就是在每个步骤输入一个参数向量 w，然后通过高斯噪声对 w 进行抖动来生成一群（比如 100 个）有稍微改变的参数向量 w1, w2……w100。然后我们在环境中分别运行这 100 个候选项所对应的策略网络，从而独立地对这 100 候选项分别进行评估，然后将每个案例中的奖励加起来。然后其更新后的参数就变成了这 100 个向量的加权和，其中每个权重都正比于其总奖励。（即，我们想让更成功的候选项有更高的权重。）在数学上，你也会注意到这就相当于使用有限差分法（finite difference）来估计参数空间中预期奖励的梯度，只是我们是沿着 100 个随机方向来做的。
我们要看的另一种方法是仍然使用强化学习（策略梯度，具体来说是 REINFORCE），其中的代理的动作是使用高斯策略得出整个参数向量。
上图：进化策略优化过程，这个环境中只有两个参数和一个奖励函数（红色=高、蓝色=低）。在每次迭代，我们都会展示当前参数值（白色）、一群经过抖动的样本（黑色）和估计的梯度（白色箭头）。我们不断将该参数移动到该箭头的顶点，直到我们收敛到了一个局部最优值。
进化策略和强化学习间的权衡
相比于强化学习算法，进化策略有多个优势（一些优势有些技术性）：
不需要反向传播。进化策略只需要策略的前向通过，不需要反向传播（或价值函数评估），这使得代码更短、在实践中速度快了 2-3 倍。在内存有限的系统中，也不需要保留 episode 的记录从而进行后续的更新。我们也不需要担心 RNN 中的梯度爆炸问题。最后，我们能够探索更大类别的策略函数，包括不可微分的网络（比如二值网络），或者包括复杂模块的网络（例如包括 pathfinding 或多种优化层）。
高度可并行。进化策略只需要工作器彼此之间进行少量纯数量的通信，然而在强化学习中需要同步整个参数向量（可能会是百万数值的）。直观来看，这是因为我们在每个工作器（worker）上控制随机 seeds，所以每个工作器能够本地重建其他工作器的微扰（perturbations）。结果是，在实验中我们观察到，随着我们以千为单位增加 CPU 进行优化时，有线性的加速。
高度稳健。在强化学习实现中难以设置的数个超参数在进化策略中被回避掉了。例如，强化学习不是「无标度（scale-free）的」，所以在 Atari 游戏中设置不同的跳帧（frame-skip）超参数会得到非常不同的学习输出。就像我们所展现的，进化策略在任何跳帧上有同样的结果。
架构探索。一些强化学习算法（特别是策略梯度）用随机策略进行初始化，这总是表现为在一个位置有长时间的随机跳跃。这种影响在 Q 学习方法中因为 epsilon-greedy 策略而有所缓和，其中的 max 运算能造成代理暂时表现出一些一致的动作（例如，维持一个向左的箭头）。如果代理在原地跳动，在游戏中做一些事情是更有可能的，就像策略梯度的例子一样。类似于 Q 学习，进化策略也不会受这些问题的影响，因为我们可以使用确定性策略来实现一致的探索。通过研究进化策略和强化学习梯度评估器，我们能看到进化策略是一个有吸引力的选择，特别是在 episode 中的时间步骤量很长的时候，也就是动作会有长时间的影响。或者是在没有好的价值函数评估的时候进化策略也是好的选择。