Press "Enter" to skip to content

NeurIPS 2020 | 俄亥俄州立大学: DQL算法首次有限时长分析及收敛速率刻画

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

 

作者: 俄亥俄州立大学五年级博士生 熊华清

 

 

NeurIPS 2020 文章专题

 

第·4·期

 

 

NeurIPS 2020工作分享 火热报名中…

 

投稿方式:

 

① 点击文末“ 阅读原文 ”

 

② 在公众号后台回复“ 投稿 ”查看详情

 

本文将分享 俄亥俄州立大学 发表于 NeurIPS 2020 的工作: 《Double Q-learning的有限时长分析》 。

 

这项工作从理论角度探索了在深度强化学习中有着广泛应用的double Q-learning算法,并 首次给出了在有限状态-行为空间(finite state-action space)下该算法的有限时长分析(收敛的时间复杂度)。

 

通过进一步比较double Q-learning与已有工作中Q-learning的收敛速率,本文还得出了 double Q-learning更适合用于高精度任务 的结论。通过刻画double Q-learning算法收敛的时间复杂度,本文旨在帮助加深对该算法的理解,并为进一步理解深度强化学习做铺垫。

 

 

论文链接:

 

https://arxiv.org/pdf/2009.14257.pdf

 

一、研究背景

 

虽然在引言中我们已介绍本文首次给 出了double Q-learning (以下用DQL代替) 的收敛速率分析,但这并不意味着该算法是强化学习芸芸算法中的“新贵”或是“无名小卒”。事实上,DQL是一个已有十年历史,并在深度强化学习中 有着极广泛应用的算法。

 

首先来简单看一下DQL为什幺会被提出。从算法的名字,我们很自然会联想到强化学习中最基础最重要的算法之一—— Q-learning算法 。的确,DQL的提出正与之息息相关。虽然Q-learning已被理论证明可以找到最优策略 (policy) ,但在实际应用中,由于采样过程以及回报函数估计中存在的随机性和误差,Q-learning中的最大值函数往往会造 成过估计 (overestimation) 问题 (这一点 将在算法回顾部分重点分析) ,进而可能导致只能学习到次优策略,而 DQL就是通过引入双估计器 (double Q estimators) 的办法 (Q-learning采用单估计器) 来有效控制这种过估计问题。

 

DQL虽然设计思路清晰,应用简洁方便,但却也并非一炮而红。与历史上许多其他模型或算法 (如神经网络) 一样,DQL虽然好用,但也需要一个舞台,一个契机让它进入人们视野,发挥自身价值。在这个契机来临之前,DQL也只能在浩瀚的论文库中默默等待。

 

2015年底2016年初, 由谷歌Deepmind研 发的围棋机器人AlphaGo横空出世,击败了李世石九段后,随着AlphaGo一起成为热门话题的,是深度强化学习技术。而 AlphaGo中的核心算法—— 深度Q网络 (DQN)  ,也于2016年初登上了Nature期刊,自此也成为了学界炙手可热的研究课题。除了DQN在Atari游戏和AlphaGo中的大放异彩,还有一个重要契机,便是 DQL的原作者Hasselt,此时 正在Deepmind工作。

 

于是很自然地, Hasselt和David Silver等人也将DQL应用到了DQN中 ,并重新刷新了几乎所有Atari游戏的最好成绩 ,也是从这篇论文开始,DQL几乎就成了和DQN如影随形的存在,在实际应用中非常广泛,效果也非常好。

 

那幺问题来了,既然DQL历史也不算短,知名度也不低,为什幺之前一直没有收敛速率的理论工作出现呢?除了研究强化学习理论的课题组不多的无奈事实外,还有一个重要因素,那就是与Q-learning相比, DQL的理论分析中有其独特的难点存在 。 为了理解这些难点,我们首先需要理解算法设计及其思想,特别是理解DQL与Q-learning的差异。

 

二、算法回顾

 

接下来我们首先回顾一下Q-learning的算法及其问题,进而理解DQL的设计理念。

 

Q-learning和DQL都是为了学习得到最优Q函数——Q*,众所周知,Q*是Bellman方程的唯一不动点 (fixed point) :

 

在上面公式中,s,a,R分别代表状态 (state) ,行为 (action) ,回报函数 (reward) ,s’则表示任务中从 (s,a) 出发得到的下一状态。自然地,我们就可以用解方程不动点的方法 得到Q-learning的基本迭代规则:

 

在这里,由于期望在实际中不可得知 (因为s’的分布未知) ,因此我们通过采样s’来估计回报函数以及每一步中的最优行为a’。

 

在理解Q-learning是一个解方程不动点的算法后,我们来看一下这个算法有什幺问题。首先,它的算法设计是清晰简洁的,理论上也被证明了可以收敛到Q*。但在实际应用中,算法中的最大值函数会带来问题,这就是 过估计 (overestimation) 。

 

要理解过估计,首先要意识 到Q-learning的最大值函数,事实上是在估计一个求完最大值后的平均值,而Bellman方程中的最大值函数,则是取 期望值中的最大值。

 

举例来说,如果将一些独立同分布的随机变量表示为 , 我们希望得到 ,而Q-learning中估计的则是 。显然, 。 因此,在实际应用中,Q-learning往往会引入正向偏差,也就是过估计 。这种过估计,在回报函数估计存在随机误差,或在算法执行过程中存在其他估计误差时,便尤为明显。

 

上面我们已经分析,Q-learning的过估计问题主要是因为在每一步都采用了最大估计值,那幺,由此想到的一个很自然的解决方案,就是 避免在每一步都用这幺激进的迭代,DQL正是基于此诞生的 。下 面是DQL的核心迭代步骤:

 

 

可以看出, DQL每一步还是用了贪心策略, 但它引入了两个Q估计器 (Q estimators)  ,从一个Q估计器中取出最优行为后,却用了另一个Q估计器来得到该行为的Q估计值。比如说,如果当前A估计器被选中更新,并用A估计器得到了最优行为a*,虽然a*在A估计器中对应最大估计值,但它在B估计器中很可能并非对应最大估计值。

 

还有一点,那就是每一步A估计器和B估计器被随机选中的概率是一样,所以可以认为 这两个估计器是对称迭代的 。综合以上两点, 可以预计DQL在迭代过程中 避免了每一次都用最大估计值,也因此可以改善过估计问题。

 

三、结果及分析

 

本文首次对DQL算法进行了 有限时长分析 (或非渐进分析) 。 目前针对DQL仅有的渐进收敛 (asymptotic convergence) 分析并不能刻画出算法的收敛速率,因而能提供的理解也很有限。 有限时长分析关注的恰恰就是 收敛速率问题 ,只有刻画出了收敛速率,我们才能对算法的设计有更多的理解,才能对不同算法进行比较。这种收敛速率的刻画,可以想见也比渐进分析难度更大。

 

从设计思路上可以看出,DQL通过引入两个Q估计器来改善过估计问题,但两个估计器在迭代中互相影响互相耦合, 这种耦合是理论分析中的一大难点 ,而对这一难点的处理,也是本文的一大贡献。对于算法的收敛时间复杂度及其证明的细节,在此不详述,请对理论推导感兴趣的读者前往原文阅读。

 

接下来,我们主要介绍一下基于理论结果的引申讨论。由于DQL是改进Q-learning算法而来的,将两者的理论结果进行比较,也自然是理解DQL的重要途径。

 

通 过比较DQL和Q-learning在相同条件下收敛到最优解邻域的时间复杂度,我们发现在高精度任务下,DQL与Q-learning收敛速度相当,而在低精度任务下,DQL收敛速率则要慢于Q-learning。因此,本 文也指出 DQL更适合应用于高精度的任务 。

 

这个结果并不意外,从算法设计中,可以看出Q-learning每一步都用最大值函数实现了贪心策略,这是一种更激进的迭代方法。与之相对的,DQL每一步则有意避开了这种激进的迭代,转而用一种相对“消极”的贪心策略,在贪心策略本质没有改变的情况下,收敛速度放慢也在意料之中。

 

四、未来工作展望

 

有关Q-learning,前后有近三十年不间断的理论研究,相较于此, 有关DQL的理论理解仍处于起步阶段,因此也有着更多的潜在问题 ,比如DQL在状态-行为空间很大甚至无穷时的收敛性问题。

 

在状态-行为空间极大时,Q估计器不再能由表格函数表示,此时往往需要用一些参数函数 (如神经网络) 来估计Q函数并迭代。可以看出这种设定更接近如今在DQN中广泛使用的DQL,因此该设定下的收敛性分析也自然非常重要。然而,这种设定下的分析难度也将进一步变大,有待未来更多的探究。

 

//

 

作者介绍:

 

熊华清 ,俄亥俄州立大学五年级博士生 (联合导师:俄亥俄州立大学梁颖斌教授,南方科技大学张巍教授) ,此前于2016年7月从浙江大学控制科学与工程学院获得学士学位。他目前的研究方向包括强化学习算法,加速算法的收敛性分析,以及非凸优化理论等。

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注