「糟糕」的策略梯度

AI 科技评论按:强化学习(reinforcement learning)是机器学习界近几年的一大研究热点,无需先验知识、在环境中反复摸索尝试获得高反馈(reward)进行学习的根本思维符合人类的直觉,DeepMind 的 AlphaGo 系列更是强化学习成功案例的正面典型。不过,强化学习训练极为不稳定、样本利用率非常低、泛化性不好等问题也一直困扰着研究人员们,自蒙特卡洛、策略梯度以来大家也继续找到了 Actor-Critic、Deep-Q Learning 等算法尝试获得更好的表现。

UC 伯克利电子工程和计算机系副教授、《Machine Learning Research》杂志编委 Ben Recht 近期就在自己的个人博客上撰写了一系列强化学习的入门介绍文章,从各个角度剖析讲解强化学习领域的重要知识和概念。其中有一篇《The Policy of Truth》(真正的策略)详细聊了聊强化学习中广泛使用的策略梯度为什么是个不好的算法,并将其喻为「伪装在数学符号和数学黑话里的随机搜索」。AI 科技评论把这篇文章编译如下。

对于各种强化学习问题,人们第一个想到的通用解决方案就是策略梯度(Policy Gradient)。不过让我震惊的是 1993 年的时候人们并没有把策略梯度看作一个糟糕的方法并且弃之不用。策略梯度确实有相当的吸引力,因为它看起来可以用来精细调节一个程序,无需任何领域内知识就可以解决任意问题。任何这样夸下海口的都肯定是为了吹捧自己,实际上当你仔细去研究的时候,你就会发现策略梯度其实就是伪装在数学符号和数学黑话里的随机搜索,仅此而已。

我有必要提前说声抱歉,因为这篇文章接下来会有不少公式。策略梯度中需要用到如此之多的公式,让我们误以为其中仿佛真的有什么严肃深入的东西。我猜策略梯度之所以一直还是活跃的研究课题的原因就是人们并不会尝试实现它,以及这些数学公式单独看来还是很有吸引力的。这其实会迷惑我们的双眼,让我们忽视了真正把方法写成代码之后可能发生的事情。跟我来一起看看那些需要钢铁般信念的关头吧。

不断增加更多的抽象,直到问题解决

我们就从人们用策略梯度解决的最通用的问题开始。在这里我们把动态系统生成的一系列状态 xk 和控制动作 uk 合称为轨迹(trajectory) τ

策略(policy)就是函数 π,它的输入是一个轨迹,然后输出一个新的控制动作。我们的目标就是找到一个能让 L 个时间步骤后的反馈最大化的策略。

在策略梯度中,我们只关注参数化的、随机化的策略。策略 π 中有一系列参数 ϑ 需要调节。以及,相比于输出某一个具体的控制动作,我们通常假设 π 是一个多种控制动作上的概率分布;在实际操作中,按照每个时间步骤对 π 的分布进行采样,然后得出一个控制动作。你可能要问了,为什么要有采样的这一步?这个问题很棒,不过我们先暂且放下这个无比合理的问题,过一会儿再说。

为了体现出策略 π 对参数 ϑ 的依赖,我们把它写作 πϑ 。由于 πϑ 是一个概率分布,把 πϑ 作为策略就引入了一个基于轨迹的概率分布:

进一步地,我们可以再增加几个符号,把轨迹的反馈定义为:

那么,这个强化学习优化问题就变成了看起来很整齐的:

如果我们继续做如下定义的话还可以再简洁一点:

这样,我们的强化学习目标就终于可以写成简短的:

策略梯度

用简洁的公式表述了这个问题之后,策略梯度就可以用下面这样的技巧推导得到:

这个式子表明了 J 相对于 ϑ 的梯度是下面这个式子的预期值

这样,当我们执行策略 πϑ 对轨迹 τ 采样的时候,我们就可以计算 G(τ,ϑ) ,从而得到对 J 的梯度的无偏差估计值。沿着这个方向下去我们就可以对 J 做随机梯度下降。

更神奇的是,计算 G(τ,ϑ) 时可以无需知道整个动态系统的运转规律方程。我们观察到

不是参数组 ϑ 的函数,因此

只要 πϑ 是可微的。以及你安装了最新版的 autograd,这些导数就都是可以计算的。

总结一下,我们就这样得到了下面这个非常美妙的方法,我们可以在不知道系统的任何动态特性的情况下用它优化一个最优化问题。

  1. 选择一组初始的猜测值 ϑ0 和步骤序列 ak。初始 k=0。
  2. 在模拟器中运行策略 πϑk,采样得到轨迹 τk。
  1. 迭代 k=k+1,回到第 2 步

策略梯度吸引人的主要原因就是因为看起来很简单。如果你可以从 πϑ 高效地采样,理论上你就可以用这个算法解决任何问题。可以飞四旋翼,可以冷却数据中心,也可以教机器人开门。那么理所当然的下一个问题就是,能做到多好呢?下面我简单提一下线性化法则(Linearization Principle),你马上就会看清真实状况,从此以后再也不会想要选策略梯度了。

为什么我们又开始用概率策略了?

在聊线性模型之前,我们暂且退一步,考虑一个纯优化问题。我们用一堆符号把强化学习变得公式化,以至于到了最后似乎我们只需要关注一个无限制函数的最大化问题。我们先把所有系统的动态特性撇开不谈,考虑单步最优化问题。给定一个函数 R(u),我要找到让函数值尽可能大的 u。也就是说我要解决这个优化问题

容我说几句可能看起来有点离题的,任何这个形式的优化问题都等价于 u 的概率分布之上的优化问题

做这个等价变换的目标是:如果 u⋆ 是最优解,那么当我们在 u⋆ 附近施加一个 Delta 函数的话也可以得到同样的反馈。进一步地,如果 p 是一个概率分布,那么就很明确,可期待的反馈值永远都不会大于固定的 u 得到的最大反馈。所以我们要优化的要么是 u,要么是 u 的分布。

这里,我们就来到了策略梯度中的第一个逻辑跳跃的地方了。相比于对所有可能的分布构成的空间做优化,我们优化的是一组参数的分布 p(u;ϑ)。如果这组参数中含有所有的 Delta 函数,那么得到的最优解就会和不含随机的优化问题的解一样。而如果参数中不含有 Delta 函数,我们就只能得到优化反馈的下界而已,不管我们找到的概率分布有多好;在这种情况下,如果从策略中采样 u,可以期待得到的反馈肯定是次优的。

这种基于分布的优化范式有一个重大问题,就是我们需要给这一组参数平衡许多不同的要求。我们需要的概率分布应当:

  1. 足够丰富,可以逼近 Delta 函数
  2. 不难通过基于梯度的方法搜索
  3. 易于采样

这其实就对分布提出了很高的要求了,尤其是当你的模型输出的控制动作是连续值的时候。对于连续动作,多数时候人们都会从各种高斯分布中找一个以便让

在这里,f 是某个非线性函数,gt 是一个高斯随机向量。像这样的参数化形式里没有哪个是带有 Delta 函数的。并且做这样的参数化动作的时候我们并不知道到底会损失多少,因为我们并没有办法对强化学习中发生的一切建模

现在就需要重新强调一件重要的事情,在我们研究的基本最优控制问题中并不需要随机化的策略。简单的 LQR (线性二次调节器)问题中当然也不需要。概率策略确实是一种建模的方法,但它永远都不会比确定性策略更好。

非常通用的强化算法

所以上面这样的策略梯度算法实际上是一个找到如下形式的式子的随机梯度的通用方法

它的对数似然也具有完全的泛化性

所以下面这个方法也就是一个完全通用化的方法,用来找到关于参数分布的最大化反馈

  1. 选择某个初始猜测值 ϑ0 和步骤序列 αk。初始 k=0。
  2. 从概率分布 p(u;ϑk) 中独立同分布采样 uk
  1. 迭代 k=k+1,回到第 2 步

这种形式的算法就可以被称为「强化」(reinforce)。它看起来很奇怪:我们得到的是一个随机梯度,然而我们想要优化的函数 R 只能通过函数评估访问。我们从来都不计算 R 自己的梯度。

那么这个算法有任何好处么?答案取决于你想要什么。如果你想要的是一个能和梯度相提并论的算法,那就一点也不好,是一个糟透了的算法。而如果你想要的是能和 R 的有限差分近似相提并论,那么…… 那么它仍然是一个糟透了的算法。只不过其中的数学计算还挺讨人喜欢。

这里要说明的是,线性化法则提醒我们几乎是马上就需要抛弃这个算法。我们来看一个最平凡的线性二次调节器例子:R(u)=−||u−z||2 。设 p(u;ϑ) 为均值为 ϑ、方差为 σ2I 的多元高斯分布。那么策略梯度能起到什么作用呢?首先我们注意到

很显然,此时此刻我们的最佳选择是让 ϑ=z。同时我们注意到预期反馈中含有减去 σ2d 的一项,不过起码现在是一个对 u 的不错的猜测值了。并且,J 作为 ϑ 的函数,明显是凸的,以及需要知道的最重要的事是这样的梯度的预期标准值控制着迭代次数。那么现在,如果你从 ϑ=0 开始,那么梯度就是

其中 ω 是一个正态分布的随机向量,均值为 0,方差为 σ2I。然后这个随机梯度的预期标准值是…… 哦算了吧,你要算一个 6 次的式子,这一点都不好玩。如果忽略一下不重要的细节,你会发现预期标准值大概和这个式子是同阶的:

这个式子很大了!随着维度变高,它的拓展问题也会让人头疼。

很多人都分析过这种方法的复杂性,当然一点都不理想,而且高度取决于搜索空间的维度数目大小。反馈的最大大小 B 也有影响。如果函数值里有很多噪声,那么即便对于凸函数,收敛速率也只是

,这还是在假定了算法的各个参数都刚好设置恰当的情况下。对于非常凸的函数,你有可能能凑出一个

级别的函数解,但是这个结果对于参数的选择将会非常敏感。最后,我们注意到仅仅给反馈加入一个负的常数项就会大大降低算法的速度。如果你选择的反馈函数的取值在 [0,1],然后你给每个反馈值都减去 106 的话,这就会让算法的运行时间变长 106 倍,即便每次的反馈值的大小关系是不变的。

我们还需要看到,当我们在动态系统中考虑这些因素的时候情况只会变得更糟糕。线性二次调节器的策略梯度更新里会含有非常多的噪声,而且它的方差会随着模拟步数 L 增大。更麻烦的是,如果要找一个简单的静态策略的话,搜索 ϑ 的过程显然是非凸的。即便实际操作中能看到一些结果,我们面前如此之多的困难还是提醒着我们可能最好换一换别的方法。

为什么这么多人都说在强化学习中取得了巨大成功?

我们已经看到有许许多多的论文,把策略梯度用在各种各样的问题上,然后得到各种各样的好看的结果。但我希望我们现在都能看清他们其实只是把随机搜索打扮得漂漂亮亮了而已。尤其当你看到另外一批论文里的基因算法和你的算法得到了近似的成果的时候,你需要明白这并不代表着基因算法有了新的发展,它更可能是在告诉你,你的方法只不过是随机搜索的一次糟糕的实现而已。

毕竟,基因算法和策略梯度需要的样本数目都多到夸张。如果你已经准备好了在亚马逊 AWS 上花上百万美元训练,并且根本不打算调节一个实体化的系统的话,想用其实也可以。但是我们肯定是有更好的办法的。

策略梯度和强化学习并没有什么神奇的魔力,我想我已经强调得够多了。不过我还是要继续说,策略梯度和它的各种变体真的是糟糕得很合理的算法。想让它们顺利运行得出结果需要很多的技巧。可是你冷静想想,难以调试、难以复现,而且还不能胜过原原本本的基因算法的算法,真的可以算是很差的算法了。

在这个系列文章中我还会多次谈起这个观点:任选一个策略梯度能得到好结果的问题,都能再找到一个简单得多、鲁棒得多的算法,而且能匹敌或者超越策略梯度的表现。策略梯度从来就不是一个好点子,但我也许一辈子都弄不清为什么它会如此流行。

原文发布于微信公众号 - AI科技评论(aitechtalk)

原文发表时间:2018-02-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

如何瞬间找到视频中的目标片段?这篇顶级论文帮你详解CDC网络如何实现视频的精准定位

作者|周翔 上个月 22 日,备受瞩目的 CVPR 2017 最佳论文在夏威夷会议中心揭晓。本届 CVPR 2017 共有两篇最佳论文(分别被康奈尔和清华团队...

3275
来自专栏数据科学与人工智能

【数据科学】数据科学书上很少提及的三点经验

这是数据科学大行其道的时代。各类课程、博客、培训学校如雨后春笋般出现。然而,每次我浏览这些学习资料时,我发现它们过于强调一些具体的算法。理解逻辑回归或者深度学习...

2076
来自专栏数据科学与人工智能

【陆勤阅读】三个你在书中无法学到的数据分析知识

在大数据特别热门的今天,出现了各种培训课程。但我发现这些课程的重点都放在算法的学习上。如何理解logistic回归或深度学习的确很酷,但一旦你开始处理数据,你会...

1947
来自专栏人工智能头条

Google 的神经网络生成图像 (Inceptionism) 自述(含源码下载)

1992
来自专栏CVer

[计算机视觉论文速递] 2018-05-08

[1]《DCAN: Dual Channel-wise Alignment Networks for Unsupervised Scene Adaptation...

941
来自专栏大数据挖掘DT机器学习

欺诈预测机器学习模型设计:准确率和召回率

Airbnb网站基于允许任何人将闲置的房屋进行长期或短期出租构建商业模式,来自房客或房东的欺诈风险是必须解决的问题。irbnb信任和安全小组通过构建机器学习模型...

2744
来自专栏阮一峰的网络日志

神经网络入门

眼下最热门的技术,绝对是人工智能。 人工智能的底层模型是"神经网络"(neural network)。许多复杂的应用(比如模式识别、自动控制)和高级模型(比如深...

2556
来自专栏程序生活

生物医学文本挖掘BioNLP1、简介2、国内相关资讯3、论文/文章4、BioNLP-ST 20165、论文阅读6、相关实战(待更)

1、简介 BioNLP Shared Task(BioNLP-ST)是一个生物文本挖掘领域的国际比赛,截止到2016年,已经举办了10年,每年都吸引了来自剑桥大...

3565
来自专栏CSDN技术头条

Airbnb欺诈预测机器学习模型设计:准确率和召回率的故事

【编者按】Airbnb网站基于允许任何人将闲置的房屋进行长期或短期出租构建商业模式,来自房客或房东的欺诈风险是必须解决的问题。Airbnb信任和安全小组通过构建...

2018
来自专栏机器学习算法与Python学习

入门 | 用机器学习进行欺诈预测的模型设计

Airbnb网站基于允许任何人将闲置的房屋进行长期或短期出租构建商业模式,来自房客或房东的欺诈风险是必须解决的问题。Airbnb信任和安全小组通过构建机器学习模...

572

扫码关注云+社区